Лекции по "Информатике"

III.Множество. Кортеж.

Под множеством понимается совокупность объектов, удовлетворяющих условию принадлежности каждого объекта данному множеству. Множество описывается (задается) следующим образом:     имя множества =  { описание элементов } .

Множество может быть задано экстенсионально  и интенсионально. В первом случае в фигурных скобках перечисляются  все элементы, которые допустимы в множестве (составляют это множество). Например, М={0,1,2,3,4,5,6,7,8,9}.При интенсиональном способе в фигурных скобках указываются 2 части, разделенные вертикальной чертой (слева от нее – условное обозначение любого элемента  множества, справа – условие принадлежности).

Например, М = {а|а – целое, 0≤a≤9}.

Условие принадлежности можно записывать по-разному. Например, множества R={x|x=0 или x=1}и Q={y | y – двоичное число} эквивалентны.

В множестве  допустимо дублирование элементов  и их расположение в любом порядке. Например, эквивалентными считаются множества М₁={1,2,3}и М₂={2,1,3,2,3}.

Кортеж – упорядоченное множество элементов, т.е. в кортеже элементы расположены в строго определенном порядке.

Формально кортеж записывается следующим образом: R=<m₁,m₂…m_n>. В кортеже дублирование элементов и изменение их порядка приводит к образованию другого кортежа, т.к. элементы будут находиться в других позициях. Например, кортежи R₁=<1,2,3> и R₂=<3,1,2,3> различны.

В зависимости  от количества элементов различают одноместные, двухместные …и n-местные кортежи. Например, R – n-местный, R₁ – трехместный, R₂ – четырехместный. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

IV.Домены и атрибуты.

Каждый  объект характеризуется рядом свойств, для отображения этих свойств в моделировании используют так называемые атрибуты. Они характеризуются интенсионалом и экстенсионалом. Интенсионал атрибута задается его именем и множеством допустимых значений. Например, для атрибута Номер можно определить разные множества допустимых значений:

ЦЕЛЫЕ = {x|x – целый, 1≤x≤999999}

ЦЕЛЫЕ = {x|x – целый, шестизначный, положительный}.

Это приводит к разному интенсиональному определению  атрибута. Подобные множества допустимых значений для атрибута в моделировании  данных называются доменами. При этом говорят: «атрибут определен на домене». Несколько атрибутов могут быть определены на одном домене, в этом случае его можно рассматривать как обобщение этих атрибутов. Атрибуты, определенные на общем домене, наследуют его свойства => для описания определения нескольких атрибутов на одном и том же домене можно использовать схему обобщение.

Например,

                                               ВЕЩЕСТВЕННЫЕ    - домен 

                 Зарплата               Заем                   Залог             Прибыль       -   атрибуты 

Множество конкретных значений атрибута, имеющихся  в данных, определяются экстенсионалом этого атрибута. Для атрибута Имя  Клиента  экстенсионалом будут являться все имена, реально существующих клиентов фирмы.

Атрибуты существуют в модели не сами по себе, а как компоненты других объектов. С помощью агрегации они объединяются и составляют типы объектов и типы связей. Типы объектов необходимы, чтобы можно было описывать конкретные объекты, а типы связей – чтобы отражать в моделях связи между конкретными объектами разных типов. Кортеж конкретных значений атрибутов, составляющих тип, называется экземпляром этого типа. Например, КЛИЕНТ (Номер, Имя, Адрес). Конкретным экземпляром этого типа будет являться трехместный кортеж, на первом месте которого значение атрибута Номер, на втором – конкретное значение атрибута Имя, на третьем – Адрес. Например, 20, Иванов, Томск.

Атрибуты, по значению которых можно однозначно определить значение других атрибутов, называются ключевыми (ключами). С помощью таких ключей составляются типы связей, осуществляется поиск экземпляра в базе данных. Ключ может быть составным, т.е. состоять из нескольких атрибутов, если обладает таким свойством (например, совокупность атрибутов Имя и Адрес). Если в типе объекта несколько ключей, то они называются возможными. Обычно один из них выбирается в качестве так называемого первичного ключа. С помощью первичных ключей составляются типы связей. В типе связей эти ключи называются внешними. Внешние ключи являются первичными в связываемых типах объектов. Значение внешнего ключа (в типе связей) однозначно указывает на экземпляр типа объекта, т.к. этот атрибут является первичным ключом в типе объектов. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

V.Отношение

Декартовым (прямым) произведением множеств S₁,S₂…S_n называется множество

                                                                                                      R={<a₁,a₂…a_n>| a_{1 Є} S_1, a_{2 Є} S_{2, …}a_{n  Є} S_n}.

Для краткости  записи часто используют следующую  формулу R= S₁×S₂×…×S_n , здесь знак «×» не имеет смысла операции «умножение», а используется лишь для краткости записи декартова произведения.

Отношением между множествами называется подмножество прямого произведения этих множеств, т.е. множество кортежей, удовлетворяющих дополнительному условию. Например, если множество A={1,3,8,9} и множество B={2,5}, то декартовым произведением этих множеств будет являться: S=A×B={<1,2>,<1,5>,<3,2>,<3,5>,<8,2>,<8,5>,<9,2>,<9,5>}.Тогда отношением, выражающим связь между этими множествами, «элемент множества А < элемента множества В» (условно А < В) является следующее: Q={< x, y >|x  _Є A, y _Є B, x < y}(интенсиональная формула) = {<1,2>,<1,5>,<3,5>}(экстенсиональная формула).

Каждый  кортеж отношения показывает конкретную связь между конкретными элементами, связанных множеств  => отношение – множество, выражающее связь (соответствие) между элементами двух или более множеств. Бинарное отношение выражает связь между элементами двух множеств, тернарное – трех множеств, четырехарное – четырех множеств и т.д. n-арное – n множеств.

Заметим, что, как и любое множество, отношение  можно записать как интенсионально, так и экстенсионально. Однако экстенсиональный способ записи отношения невозможен, если связанные множества бесконечны или количество элементов этих множеств неизвестно.

В моделировании  данных термин «отношение» применяется  к определению типа, при этом отношениями  представляются как типы объектов (отношение  между множествами атрибутов, составляющих тип объекта), так и типы связей (отношение между конкретными объектами, относящимися к разным типам объектов). Связь, как и любое отношение, характеризуется интенсионалом (тип связи) и экстенсионалом (множество конкретных реализаций связи). Типы связи, как и типы объектов, являются агрегатами двух и более атрибутов. Тип связи может быть обобщением других типов связи.

Тип связи  определяется для описания связи  между конкретными экземплярами разных типов объектов. Интенсионал  типа связи составляется из атрибутов  тех типов объектов, которые связаны  между собой. Если у этих типов объектов есть ключевые атрибуты, то тип связи может состоять только из них. В случае, если у типов объектов (у обоих или одного из них) ключевых атрибутов нет, то в тип связи приходится включать все атрибуты таких типов объектов. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

VI.Табличное представление данных.

Табличные формы характерны для большинства  моделей данных, в таких моделях  экстенсионалы типов  объектов и  типов связей записываются в виде таблиц.

Каждая  таблица представляет экстенсионал какого-либо типа. В строках содержатся экземпляры данного типа, а в столбцах – экстенсионалы атрибутов. Таблицам присваивают имена тех типов, которые они представляют, а столбцам – имена соответствующих атрибутов.

В моделировании  данных используют 2 вида таблиц:

1)реляционные

2)таблицы записей.

В первом случае таблица представляет собой  отношение, т.е. множество кортежей, каждый из которых является экземпляром соответствующего типа объекта или типа связи => порядок расположения кортежей в таблице не играет роли и одинаково изображенные кортежи считаются одинаковыми по смыслу => их дублирование не допускается. В связи с этим такие таблицы часто называют отношениями или реляционными таблицами (relation – отношение).

Если  в таблице порядок расположения экземпляров в строках имеет значение, то эта таблица представляет собой кортеж экземпляров соответствующего типа  объекта или типа связи => в такой таблице допускается дублирование экземпляров. Эти таблицы называются таблицами записей, а строки – записями. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

VII. Представление данных в виде графа

Графом называется кортеж двух множеств Q = <X,Y>, где X={ x₁,x₂…x_n }  -  множество вершин, а Y = { y₁,y₂…y_n } – множество дуг (ребер), соединяющих вершины множества X. Каждое из y_i соединяет вершины, например, x_j и y_k, т.е. y_i = <x_j,y_k>. В данном случае дуги имеют направление, поэтому граф называется ориентированным.

На первом месте кортежа указывается вершина, из которой дуга исходит, на втором – вершина, к которой эта дуга направлена.

Чаще  всего граф изображается в виде рисованной схемы. Например:

                                                          y₁   x₁

                                                

                                                     x₂       y₄

                                                                        x₃                                     

                                                          y₃

                                                                                     y₂

                                           x₄         

                                                                                                                       x₅ 

Если  в графе направление дуг не указывается, то он называется неориентированным, а каждая дуга может быть записана в виде множества двух элементов, которые она соединяет.

Граф  используется для описания связей между  элементами, вершины сопоставляются элементам, а дуги показывают связи  между ними. Таким графом  может  быть представлен агрегат атрибутов (схема агрегации), образующий тип объекта или тип связи. Схема обобщения, единая схема обобщения агрегации являются графом.

В представлении  интенсионала вершинам сопоставляются типы объектов, а дуги показывают связи  между ними. В представлении экстенсионалов вершины графа соответствуют значениям атрибутов, а дуги соединяют значения атрибутов, составляющих реализацию типа объекта. Если какой-либо атрибут является ключевым, то это показывается графом, в котором соответствующую вершину соединяют дугами с вершинами, соответствующими другим атрибутам. Например,