Основы информатики

                                                                                                                       x5

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

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

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

                                                                           Номер

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

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

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

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

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

                                                                    S1                                   R                                         S2

                                                                            Q                    

                                                                    Q: S2 → S1

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

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

               k Є КЛИЕНТ

   <k,s>   s Є СЧЕТ

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

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

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

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

Бинарное отношение Т множеств S1 и S2 определяет 2 отображения: R: S1→ S2 и R-1: S2→ S1, каждое из которых является обратным по отношению к другому => будем записывать бинарное отношение, указывая min и max кардинальные числа для каждого отображения следующим образом: T(S1(n1,n2) : S2(m1,m2)).

Такая запись означает, что множества S1 и S2 связаны отношением Т, причем каждый элемент множества S1 может быть связан с любым количеством от m1 (min кардинальное число) до m2 (max кардинальное число) элементов в множестве S2, а каждый элемент из S2, в свою очередь, может быть связан с любым количеством от n1 до n2 элементов в множестве S1.

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

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

Например, T(S1(n1,n2) : S2(m1,∞)) означает, что каждый элемент S1 может быть связан с любым количеством элементов в множестве S2, но не менее, чем с m1 элементами. Значения 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               - порожденный

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

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

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

Например,

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

                                                                                       - сложная

                                                                                        связь

                                                         РАСЦЕНКА                                  ЗАКАЗ НА ПОКУПКУ

               СТАТЬИ ЗАКУПКИ

X.Ограничение целостности

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

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