1.6. Сетевая и иерархическая модели данных
В основе сетевой схемы (модели) находится сеть из объектов и взаимосвязей (отношений) между ними.
В основе иерархической схемы (модели) находится дерево из объектов и взаимосвязей (отношений) между ними.
Сетевые и иерархические модели удобны в тех случаях, когда реальные объекты связаны аналогично сети или дереву. Например, структура предприятия (учреждения) подобна дереву с корнем — руководителем предприятия.
Сетевые и иерархические базы данных используют списковые структуры. По этой причине они занимают меньше места в памяти ЭВМ, чем реляционные базы данных. Однако обращение по индексу обеспечивает реляционным базам большее быстродействие. По приведенным соображениям в настоящее время применяют все три вида баз данных, но реляционные базы заметно опередили остальные в последних комерческих пакетах.
Для проектирования баз данных применяют хорошо отработанные к настоящему времени методы. Для небольших баз данных можно использовать результаты анализа функциональных зависимостей между атрибутами, для баз данных с большим числом атрибутов лучше применять ER-диаграммы, применяемые в CASE-методах проектирования.
В процессе проектирования базы данных выполняют декомпозицию первичного отношения, которое содержит все выявленные при обсуждении проекта атрибуты. Необходимость декомпозиции на совокупность отношений диктуется тем, что если ее не выполнять, то приходится хранить в таблицах многократно повторяющиеся одинаковые значения. Первичную и промежуточные формы выражения исходного отношения классифицируют на пять, так называемых, нормальных форм.
1.7. Case — методы проектирования баз данных
CASE — методы (Computer-Aided Software Engineering — методы) проектирования баз данных основаны на понятиях “сущность” (‘entity’) и взаимосвязь (‘relationship’). CASE — методы используют графическую форму отражения взаимосвязей объектов и незначительно различаются изобразительными средствами. Известны модель Chen’а, модель IEM (Information Engineering Metod), модель SSADM (Structured Systems Analysis Design Metod), модель IDEF1X и т.п..
CASE-методы широко используют ER-диаграммы (Entity — Relationship диаграммы) и потому нередко называются ER-методами, ER — технологией проектирования, методами диаграмм “сущность — связь”, “сущность — взаимосвязь”.
1.8. Понятия “сущность” и “взаимосвязь”
Понятия “сущность” и “взаимосвязь” не имеют четкого определения в рассматриваемой области знаний. Рекомендуется называть “сущностью” объект, сведения о котором должны храниться в базе данных. Общепризнано, что “сущность” задается существительным, например, ЧЕЛОВЕК, СТУДЕНТ, САМОЛЕТ, КОМПЬЮТЕР.
Свойства сущности называют атрибутами. В реляционной модели данных сущность — это имя отношения, а атрибуты — имена элементов кортежей.
Ключ сущности — совокупность атрибутов, значения которых однозначно характеризуют экземпляр сущности.
Взаимосвязью, или просто связью, называют отношение между сущностями.
Взаимосвязи рекомендуется сопоставлять глагол или глагол с обстоятельствами,
например, СОСТОИТ ИЗ, ПОКУПАЮТ, ПОКУПАЮТ ЗИМОЙ и т.п.
Сущность и взаимосвязь образуют естественные конструкции при описании отношений между объектами. Например,
Взаимосвязь характеризуется арностью и степенью. Если взаимосвязь объединяет k — сущностей, то она называется k — арной. Двух-арную взаимосвязь называют бинарной.
Степень взаимосвязи определяется видом соответствия между экземплярамисущностей. Если экземпляру одной сущности может соответствовать один и только один экземпляр другой сущности, то степень взаимосвязи 1 : 1 (один к одному).
Если экземпляру одной сущности может соответствовать не обязательно один, а именно, или один, или больше одного или ни одного экземпляра другой сущности, то степень взаимосвязи 1 : M (один ко многим). Эта же взаимосвязь, прочитанная в обратном направлении, имеет степень M : 1 (много к одному).
Наконец, возможен случай степени взаимосвязи M : N (многие ко многим). Эту взаимосвязь нередко исключают путем создания фиктивной сущности и двух взаимосвязей степеней M : 1 и 1 : N .
Степень взаимосвязи используется потому, что в ней заключен характер функциональной зависимости между атрибутами: однозначная функция, многозначная функция, отсутствие функциональной зависимости.
Каждую из двух точек соединения сущностей и взаимосвязи характеризуют классом принадлежности сущности к данной взаимосвязи. Если все экземпляры сущности участвуют во взаимосвязи, то класс принадлежности сущности называют обязательным. Если отдельные экземпляры сущности могут не участвовать во взаимосвязи, то класс принадлежности сущности будет необязательным.
Рис. иллюстрирует определение класса принадлежности; точки соответствуют экземплярам сущностей.
необязательный обязательный необязательный необязательный
1.9. ER — диаграммы в модели Chen’а
Сущность и взаимосвязь изображают графически.
В модели Chen’а применяют трехдольный нагруженный граф. В вершине первого вида, которую рисуют в форме прямоугольника, указывают сущность; в вершинах второго вида в форме овалов — атрибуты сущности; в вершине третьего вида в форме ромбов — взаимосвязь. Ключ сущности отмечают двойным овалом. Дуги графа помечают “1” или “не 1” (“буквой”).
Прямоугольники сущностей могут иметь дополнительный прямоугольник в точке присоединения взаимосвязи для отражения того свойства сущности, что класс ее принадлежности взаимосвязи является обязательным.
На рис. вместо двойных овалов использован символ (*) для отметки ключей.
1.10. ER-диаграммы в модели IDEF1X
В модели IDEF1X, которая используется в программном пакете ERwin/ERX2.1, не рисуют ромбы, а название взаимосвязи надписывают над дугой.
Кроме того не пишут “1”, а случай “не 1” изображают жирной точкой.
В вершинах графа, по-прежнему сопоставляемых сущностям, указывают сущность и ее атрибуты, причем прямоугольник делят на две части: область ключа выше разделительной линии и область данных ниже разделительной линии. Ключевые атрибуты записывают в области ключа.
В случае ввода диаграммы при помощи пакета ERwin атрибут сущности можно помечать как внешний ключ (foreign key) с указанием родительской сущности. Внешний ключ (foreign key) — атрибут, значения которого не могут бытьне из значений атрибута родительской сущности. Часто имена родительского и дочернего атрибутов одинаковы, хотя это и не обязательно. Кстати, при вводе данных следует сначала ввести значения в родительскую таблицу и только затем в атрибут, помеченный как внешний ключ.
В зависимости от использования внешних ключей сущности подразделяют на зависимые и независимые. Независимые сущности не имеют внешних ключей и изображаются обычным прямоугольником, а зависимые — прямоугольником со скругленными углами, от которого протягивается линия взаимосвязи с родительской сущностью. Взаимосвязь может быть идентифицирующей (identifying relationship) и неидентифицируюшей (non-identifying relationship) в зависимости от того, в какой области находится внешний ключ: в области ключа для идентифицирующей взаимосвязи и в области данных для неидентифицирующей взаимосвязи. В случае неидентифицирующей взаимосвязи соединительную линию между сущностями изображают пунктиром.
Если сущность желательно разделить на категории, то в цепи связи между сущностями изображают дискриминатор, показанный на рис. .
Переход от ER-диаграммы к реляционной (табличной) модели
Реальным объектам и их взаимодействиям можно сопоставить бесконечное число ER-диаграмм. Можно ввести одну, единственную сущность со всеми атрибутами и сопоставить ей одну таблицу с теми столбцами, имена которых встречаются в атрибутах сущности. Такой вариант построения базы фактически игнорирует ER-диаграмму и практически не используется, так как имеет низкую эффективность уже в базах среднего объема (сотни записей). Единая таблица используется ниже только для иллюстрации рассуждений.
Единственная сущность и одна таблица — это первая нормальная форма представления базы данных. С целью сокращения объема хранимой информации и для ускорения поиска данных выполняют декомпозицию единственной сущности (отношения). Известны описываемые ниже формальные правила декомпозиции сущностей (отношений).
“Лобовое” преобразование ER-диаграммы в реляционную (табличную) модель базы данных состоит в том, что каждой сущности сопоставляется таблица, а взаимосвязи учитываются путем копирования ключа одной таблицы в другую (взаимосвязанную) таблицу. Такой способ применен в пакете ERwin. Недостаток этого способа преобразования заключается в том, что в таблицах часто возникает дублирование данных, а также “пустоты”.
Г.Джексоном сформулированы широко известные в данной области знаний правила для перехода от ER-диаграмм к табличной модели, позволяющие получить минимальное число таблиц, не содержащих “пустот” и дублированных данных. Однако, как будет видно из приведенных далее примеров, общее число столбцов всех таблиц после преобразования нередко увеличивается за счет дублирования ключей. Как следствие этого явления в некоторых ситуациях размер базы после преобразования увеличивается. Поэтому следует критически отнестись к рассматриваемым ниже преобразованиям.
Эти же правила можно использовать для преобразования ER -диаграмм.
Правило 1. Если степень взаимосвязи 1: 1 и классы принадлежности обеих сущностей обязательны, то для представления взаимосвязи и обеих сущностей достаточно одного отношения (одной таблицы), в схему которого включают все атрибуты обеих сущностей. Ключом отношения может быть ключ любой сущности.
Этим правилом можно пользоваться для объединения двух сущностей.
Пример. Каждый студент имеет зачетную книжку и только одну.
ER — диаграмма имеет следующий вид.
Согласно правилу 1 составим следующее отношение (таблицу).
Сетевая модель данных
Сетевая модель данных является развитием иерархической модели. В сетевой модели, так же как и в иерархической модели, есть понятие элемента данных и связи, которая может быть именована. Главное отличие сетевой модели от иерархической заключается в том, что к каждому элементу может идти связь не от одного элемента (“родителя”), а от нескольких.
Например, генеалогическое дерево, построенное только по мужской линии (или, только по материнской), является древовидной, иерархической структурой — у каждого человека (элемента), есть только один родитель. Если же включать в генеалогическое дерево всех родителей, то такое дерево с точки зрения структур данных будет уже не деревом, а сетью:
Рис.2.3. Представление фрагмента генеалогического дерева на основе сетевой модели данных
На данном рисунке представлены элементы только одно класса — описание людей, и на этом множестве для некоторых конкретных пар людей существуют связи, именуемые “муж”, “жена”, “отец”, “мать”, “ребенок”. Поэтому с точки зрения графического представления схемы этой базы данных (а не конкретных данных о семье Петровых), можно использовать следующий рисунок:
Рис.2.4. Представление схемы базы данных генеалогического дерева на основе сетевой модели данных
Сетевая модель данных основывается на понятии элемента данных и связей, задающих логику взаимоотношениями между данными. Связи от каждого элемента могут быть направлены на произвольное количество других элементов. На каждый элемент могут быть направлены связи от произвольного числа других элементов. Каждый элемент данных описывает некоторое понятие из предметной области и характеризуется некоторыми атрибутами. Для каждого элемента данных (элемент — это часть схемы) в реальной базе данных может существовать несколько экземпляров этого элемента. С каждым конкретным экземпляром по конкретной связи может быть связано разное число экземпляров другого элемента (например, у каждого человека разное число детей), но число видов связи одинаково для всех экземпляров одного элемента.
Если мы вернемся к нашему примеру про издательства тематических сборников (этот пример рассматривался в разделе про иерархические СУБД) и попытаемся расширить его, для того чтобы он более полно соответствовал реальным взаимоотношениям, то схема базы данных будет выглядеть следующим образом:
Рис.2.5. Представление расширенной схемы базы данных для описания издательств на основе сетевой модели
К достоинствам сетевой модели относится очень высокая скорость поиска и возможность адекватно представлять многие задачи в самых разных предметных областях. Высокая скорость поиска основывается на классическом способе физической реализации сетевой модели — на основе списков.
Главным недостатком сетевой модели, как, впрочем, и иерархической, является ее жесткость. Поиск данных, доступ к ним, возможен только по тем связям, которые реально существуют в данной конкретной модели. При поиске данных сетевая СУБД требует перемещаться только по существующим, заранее предусмотренным связям.