СЕТЕВАЯ МОДЕЛЬ ДАННЫХ РГБД КОДАСИЛ

МОДЕЛИ ДАННЫХ

СЕТЕВЫЕ СИСТЕМЫ

Сетевые СУБД используют сетевую модель данных. С точки зрения теории графов сетевой модели соответствует произвольный граф (возможно, имеющий циклы и петли). В узлах графа помещаются типы записей, а ребра интерпретируются как связи между типами записей. На рис. 3 показана сетевая схема и соответствующая этой схеме база данных.

Приведенное определение является слишком общим для целей реализации, так как в нем отсутствуют ограничения на способы соединения типов записей в схеме базы данных. Рабочая группа по базам данных (РГБД) ассоциации КОДАСИЛ (CODASYL) сформулировала некоторые ограничения на сетевую модель данных, рассматриваемые в следующем разделе.

Рис.3.

Схема сетевой базы данных модели РГБД состоит из множества типов записей, которые могут быть владельцами или членами типов наборов, определяемых в схеме. Тип набора определяет связь между типами записи-члена и записи-владельца следующим образом:

а) Тип набора определяет отображение 1 : N между типом записи-владельца и типами записей-членов набора.

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

в) Тип записи-владельца в типе набора не может совпадать с типом записи-члена.

В п. а) имеется одно отличие от строго иерархической системы. Оно состоит в том, что допускаются записи-члены, не участвующие в наборах. Это соответствует порожденным узлам дерева, не имеющим исходных. Таким образом, вместо полной функциональной зависимости «члены — владелец» допускается частичная функциональная зависимость. Кроме того, в сетевой модели РГБД можно определить несколько типов наборов между двумя типами записей, так что между ними могут быть заданы различные отношения в отличие от единственного отношения исходный — порожденный, допустимого в иерархических структурах.

Существуют различные способы преобразования общих сетевых структур в структуры РГБД с учетом ограничений а) — в).

Для преобразования общей сетевой структуры, показанной на рис. 3,а, можно ввести запись-связку. Таким образом, связь М : N, примером которой является связь между поставщиками и деталями, преобразуется в совокупность связей 1 : N (т. е. иерархий), удовлетворяющих ограничению а). Экземпляры записи-связки можно выбирать так, чтобы удовлетворялось ограничение б). Кроме того, записи-связки могут содержать дополнительную информацию (например, в записи-связке может храниться величина поставки). Эти преобразования показаны на рис. 4.

Рис.4

Из рис. 4 видно, что для преобразования общей структуры в структуру с ограничениями необходимо ввести несколько типов наборов и типов записей. Это еще один пример, показывающий необходимость дублирования для представления сложных и мощных структур с помощью примитивных и/или ограниченных структур.

Что касается ограничения в), то рассмотрим связь «руководит», показанную на рис. 4,а и 5,в. В терминах предложений РГБД тип записи-члена здесь должен совпадать с типом записи-владельца, что недопустимо. В этом случае по аналогии с решением для ограничений а) и б), рассматриваемуюсвязь можно отобразить либо вводя различные типы записей для разных ролей одного и того же типа записи, либо добавляя запись-связку и два типа наборов. Оба случая представлены на рис.6.

Рис.5. Рис.6

РЕЛЯЦИОННЫЕ СИСТЕМЫ

Реляционные СУБД используют реляционную модель данных. С помощью уже введенных понятий можно рассматривать отношение как набор связей между п атрибутами, т. е. как n-арную атрибутную связь. В соответствующее представление данных включаются только имеющие смысл и/или допустимые комбинации связей атрибутов. Ниже приведен ряд формальных определений:

а) Доменом называется совокупность однотипных значений данных. Примерами являются домен денежных сумм, домен имен, домен целых чисел и т. д.

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

в) Пусть имеется п доменов D₁, D₂, ..., D_n (необязательно различных). Отношение R определяется как множество упорядоченных п-ок (кортежей), являющееся подмножеством декартова произведения доменов. Домен (множество) D_i представлен в кортежах i-м элементом. Требование упорядоченности элементов кортежа можно устранить, идентифицируя в кортеже каждое вхождение домена уникальным именем атрибута.

Приведенный ниже простой пример иллюстрирует тот факт, что отношение представляет подмножество декартова произведения доменов. Пусть необходимо построить бинарное отношение (т. е. отношение с двумя атрибутами), содержащее атрибуты «имя» и «возраст». Предположим, что в соответствующих доменах определены следующие значения:

Отношение R (ИМЯ, ВОЗРАСТ) — имена атрибутов могут перечисляться в любом порядке — представляет подмножество декартова произведения доменов ИМЯ и ВОЗРАСТ, состоящего из девяти кортежей, R Í ИМЯ Ä ВОЗРАСТ (Ä обозначает операцию декартова произведения):

ИМЯ Ä ВОЗРАСТ = (Доу,25),(Кларк,25),(Джонсон,25),

(Доу,37),(Кларк,37),(Джонсон,37),

(Доу,43),(Кларк,43),(Джонсон,43).

Поскольку возраст человека определен однозначно, смысл имеют лишь три варианта сочетания возраста и имени. Например, отношение

R (ИМЯ, ВОЗРАСТ) = (Доу,43),(Кларк,25),(Джонсон,37) представляет модель реальной ситуации, являясь подмножеством рассмотренного декартова произведения.

СВОЙСТВА ОТНОШЕНИЙ

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

б) Нормализованное отношение представляется в виде табличной структуры. Имя таблицы соответствует имени отношения, имена столбцов — именам атрибутов, а строки таблицы — кортежам.

в) Упорядочение кортежей теоретически несущественно, однако оно может влиять на эффективность доступа к кортежам.

г) Все строки (кортежи) отношения должны быть различными.

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

е) Реляционная база данных является совокупностью изменяющихся во времени нормализованных отношений различных степеней, которые могут быть связаны друг с другом через общие домены.

Сделаем несколько замечаний по поводу свойства е). Различие между математическим отношением и отношением базы данных состоит в том, что состояние последнего может меняться со временем при добавлении и/или удалении отдельных кортежей. Число атрибутов, входящих в отношение, называется степенью отношения, а число кортежей отношения — кардинальным числом или мощностью отношения. Навигация по отношениям базы данных осуществляется путем их соединения с помощью атрибутов, определенных над общими или сравнимыми доменами. Операция соединения включает сравнение значении «атрибутов соединения» кортежей одного отношения (исходного) с кортежами другого отношения (целевого) и выборку пар кортежей, удовлетворяющих сравнению. Эта операция подробно рассмотрена ниже.

РЕЛЯЦИОННАЯ АЛГЕБРА

В этом разделе на ряде примеров рассматриваются операции реляционной алгебры. Для представления каждой операции будем использовать терминологию как алгебры, так и исчисления. Последняя базируется на системе понятий, использованной Коддом [53]. Пять операций являются основными: проекция, объединение, разность, декартово произведение и селекция. Другие часто используемые операции пересечения, соединения и деления можно выразить через пять основных операции. Ниже представлены отношения, используемые в примерах:

Р (D₁, D₂, D₃) Q (D₄, D₅,) R (М, Р, Q, Т) S (A, В)

1 11 х х 1 х 101 5 a 5 а

2 11 у x 2 у 105 3 а 10 b

3 11 z у 1 z 500 9 а 15 с

4 12 х w 50 1 b 2 d

w 10 2 b 6 а

w 300 4 b 1 b

Описание каждого отношения состоит из имени отношения, за которым в круглых скобках следует список атрибутов (это описание называется также интенсионалом или схемой отношения). Под описанием приведено некоторое заполнение кортежей отношения (экстенсионал отношения). В последующих примерах буквы R и S используются для обозначения отношений, а буквы А и В — для обозначения списка атрибутов (для простоты можно считать, что список состоит из единственного атрибута).