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

      

                                                               Номер

 

                                      

                                         Имя              Возраст            Адрес     
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

VIII.Отображение

Правило (R), которое элементам одного множества  (S₁) ставит в соответствие элементы другого множества (S₂), называется отображением из S₁ в  S₂. Кратко это записывается следующим образом: R: S₁→ S₂

Отображение описывает связь элементов одного множества с элементами другого. Например, если есть множество клиентов  КЛИЕНТ и множество счетов  СЧЕТ, то таблица ВЛАДЕНИЕ, в которой  для каждого конкретного клиента  указаны все счета, которыми он владеет, является отображением из множества КЛИЕНТ в множество СЧЕТ, т.е. ВЛАДЕНИЕ: КЛИЕНТ → СЧЕТ.

Если  a – элемент множества S₁, т.е. a Є S₁, то множество соответствующих ему элементов в S₂ называется его образом при отображении R и обозначается R(a).

                              

                                               S₁                                   R                                         S₂

                                                                                                                       

                         
 
 
 
 
 
 

                                                                            Q                    

                                                                    Q: S₂ → S₁ 

Q: S₂ → S₁- обратное R: S₁→ S₂, если оно любому элементу b Є S₂ ставит в соответствие такое множество Q(b) элементов в S₁, образом которых при отображении R является данный элемент b, т.е. R(Q(b)) =b.

Заметим, что для любого отображения существует обратное ему отображение. Отображение, обратное R: S₁→ S₂, обозначается R^-1: S₂→ S₁.

               k Є КЛИЕНТ

   <k,s>   s Є СЧЕТ

               s Є ВЛАДЕНИЕ (k)     

Если  для каждого a Є S₁ существует образ R(a)   S₂ (т.е. подмножество совпадает), то R называется полным отображением. Если  в S₁ существуют элементы, для которых нет образов в S₂, то R – частичное (неполное) подмножество.

Количество  элементов одного множества, связанных  с одним элементом другого (т.е. количество элементов в образе этого  элемента), называется кардинальным числом данного элемента.

Для любого отображения можно определить минимальное  и максимальное кардинальные числа. Минимальным (максимальным) кардинальным числом при R: S₁→ S₂ называется минимальное (максимальное) количество элементов в образах элементов множества S₁. Например, S₁ – min = 0,max = 2. 

Бинарное  отношение Т множеств S₁ и S₂ определяет 2 отображения: R: S₁→ S₂ и R^-1: S₂→ S₁, каждое из которых является обратным по отношению к другому => будем записывать бинарное отношение, указывая min и max кардинальные числа для каждого отображения следующим образом: T(S₁(n₁,n₂) : S₂(m₁,m₂)).

Такая запись означает, что множества S₁ и S₂ связаны отношением Т, причем каждый элемент множества S₁ может быть связан с любым количеством от m₁ (min кардинальное число) до m₂ (max кардинальное число) элементов в множестве S₂, а каждый элемент из S₂, в свою очередь, может быть связан с любым количеством от n₁ до n₂ элементов в множестве S₁.

Такая запись позволяет указать ограничения  на связи между элементами множеств.

Если  на отображение не наложено никаких  ограничений с точки зрения max кардинального числа, то считается, что это число не определено и вместо него указывается знак «∞».

Например, T(S₁(n₁,n₂) : S₂(m₁,∞)) означает, что каждый элемент S₁ может быть связан с любым количеством элементов в множестве S₂, но не менее, чем с m₁ элементами. Значения min кардинальных чисел показывает полноту отображения. Нулевое значение указывает на частичность отображения, а не нулевое – на полноту.

Вид связи  между множествами определяется значениями max кардинальных чисел. Различают 3 вида связи:

• один-к-одному = взаимно однозначная связь
• один-ко-многим = функциональная связь
• многие-ко-многим

Если  оба max кардинальных числа >1, то такое отношение называется связью многие-ко-многим или (N:M)-связью. Для типов объектов это означает, что каждый экземпляр одного типа объекта может быть связан с несколькими экземплярами другого. Например, ВЛАДЕНИЕ (КЛИЕНТ(0,2(∞)):СЧЕТ(1,3)). Здесь записано, что отображение R:КЛИЕНТ→СЧЕТ является полным, а R^-1:СЧЕТ→КЛИЕНТ – частичное. Кроме этого здесь указан вид связи многие-ко-многим.

Если  одно max кардинальное число=1, а другое - >1, то такое отношение называется связью один-ко-многим, функциональной или (1:N)-связью. При функциональной связи типов объектов каждый экземпляр одного типа объекта может быть связан с несколькими другого, но не наоборот. Например, ВЛАДЕНИЕ(КЛИЕНТ(0,1):СЧЕТ(1,3)).

Если  оба max кардинальных числа=1, то такое отношение называется связью один-к-одному, взаимно однозначной или (1:1)-связью. Эти виды связи могут быть характерны не только для типов объектов, но и для атрибутов. Взаимно однозначная связь для атрибутов означает, что каждое значение одного атрибута может быть связано только с одним значением другого атрибута. Соответственно понимаются и другие виды связей для атрибутов.

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

Например,

                        КЛИЕНТ                                 СЧЕТ

                                 

Функциональность  связей обозначается дугой, на одном  конце которой находится одинарная  стрелка, на другом – двойная (направлена от одного ко многим).

Например,

                       КЛИЕНТ                               СЧЕТ 

Связь многие-ко-многим указывается на схеме  дугой с двойными стрелками на обоих концах.

Например,

                       КЛИЕНТ                                    СЧЕТ 

Здесь показано, что каждый клиент может  владеть несколькими счетами, и  у каждого счета может быть несколько владельцев. 

IX.Типы моделей представления данных

В данном случае рассматриваются типовые  модели представления данных, лежащие  в основе реализации систем управления базами данных.

Основными являются 3 типа моделей:

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

              -    иерархическая – модель представляет собой граф в виде древовидной структуры. Вершины называются узлами и сопоставляются типам объектов. Наивысший узел называется корнем или коневым узлом. В такой модели корневой узел единственный. Зависимые узлы располагаются на более низких уровнях иерархии. Уровень, на котором находится узел, определяется «расстоянием» от корневого узла, измеряемым количеством узлом высшей иерархии вместе с данным узлом.

Иерархическую модель можно представить  в виде перевернутого дерева (корень – вверху,ветви направлены вниз). 

Уровень 1                      - корневой узел 

Уровень 2

Уровень3                                       

                                                           - листья

                        - исходный             

Уровень 4           - порожденный

Узел, находящийся  на каком-либо уровне, называется исходным для связанных с ним узлов следующего уровня. Узлы называются порожденными (зависимыми) узлом, находящемся на предыдущем уровне, если они связаны с ним. Узлы, не имеющие порожденных, называются листьями. В данной модели требуется, чтобы каждый узел был соединен только с одним узлом, находящемся на предыдущем уровне.

Другими словами, в данной модели представляются только функциональные и взаимно  однозначные связи. Реализация связи  многие-ко-многим возможна только при  условии искусственного включения дополнительных  узлов для превращения этих связей в функциональные. В результате структура базы данных становится громоздкой. Основным преимуществом этой модели является то, что доступ к любому узлу уникален. В иерархической модели все пути доступа линейные =>соответствующие СУБД – самые быстродействующие. Экстенсионал каждой вершины обычно представляется таблицами записей.

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

Например,

                          ПОСТАВЩИК                 ПАРТИЯ ТОВАРА

                                                                         - сложная

                                                                              связь