Этап 1

Итак, имеем следующие сущности с указанием их первичных ключей:

АБИТУРИЕНТЫ (НомерАбитур,...)

ПРЕПОДАВАТЕЛИ (НомерПрепод,...)

ЭКЗАМЕНЫ (НомерЭкзам,...)

СПЕЦИАЛЬНОСТИ (КодСпец,...)

Этап 2. Описание ER-диаграммы:

АБИТУРИЕНТЫ (М, Н) сдают (М, Н) ЭКЗАМЕНЫ (правило 6)

АБИТУРИЕНТЫ (М, О) выбирают (1, О) СПЕЦИАЛЬНОСТИ (правило 4)

ПРЕПОДАВАТЕЛИ (М, Н) принимают (М, О) ЭКЗАМЕНЫ (правило 6)

Этап 3. В соответствии с правилами формируем набор предварительных отношений:

· Для связи сдают (правило 6):

АБИТУРИЕНТЫ (НомерАбитур,...)

ЭКЗАМЕНЫ (НомерЭкзам,...)

АБИТУРИЕНТЫ_ЭКЗАМЕНЫ (НомерАбитур,НомерЭкзам,...)

· Для связи выбирают (правило 4):

АБИТУРИЕНТЫ (НомерАбитур, КодСпец...). Здесь КодСпец добавлен по правилу 4 как простой атрибут.

СПЕЦИАЛЬНОСТИ (КодСпец,...)

· Для связи принимают (правило 6):

ПРЕПОДАВАТЕЛИ (НомерПрепод,...)

ЭКЗАМЕНЫ (НомерЭкзам,...)

ПРЕПОДАВАТЕЛИ_ЭКЗАМЕНЫ (НомерПрепод, НомерЭкзам,..)

Этап 4. Добавляем в полученные отношения неключевые атрибуты из таблицы 1 примера 34. Получим набор результирующих отношений (таблиц):

R1: АБИТУРИЕНТЫ (НомерАбитур, ФиоАбитур, Адрес, Телефон, КодСпец, Льгота)

R2: ЭКЗАМЕНЫ (НомерЭкзам, предмет, Дата)

R3: АБИТУРИЕНТЫ_ЭКЗАМЕНЫ (НомерАбитур,НомерЭкзам)

R4: СПЕЦИАЛЬНОСТИ (КодСпец, НазваниеСпец, Проходной_балл)

R5: ПРЕПОДАВАТЕЛИ (НомерПрепод, ФиоПрепод, Должность)

R6: ПРЕПОДАВАТЕЛИ_ЭКЗАМЕНЫ (НомерПрепод, НомерЭкзам)

или в обозначениях таблицы 3 из примера 35:

R1 = A BE R2 = M N R3 = AM R4 = E K R5 = C D R6 = CM

Для проверки свойства соединения без потерь информации воспользуемся множеством функциональных зависимостей из примера 35:

F = {A → BE, C→ D, E → K, M → N}

Проверка показала, что свойство соединения без потерь информации не выполняется. Что надо сделать, чтобы это свойство выполнялось?

Как было сказано ранее, Мейер показал [4], что необходимым условием выполнимости свойства соединения без потерь информации является наличие суперключа (не обязательно минимального) хотя бы в одной декомпозиционной подсхеме из результирующей декомпозиции.

Задача поиска универсального ключа может быть решена по одному из алгоритмов, изложенных в разделе 1.5.

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

В рассматриваемом примере таким ключом является набор атрибутов ACM, так как

ACM ⁺ = ACMBEKDN = U

Таким образом, добавление к полученному набору отношение R7 = ACM или с реальными данными

R7: АБИТУРИЕНТЫ_ПРЕПОДАВАТЕЛИ_ЭКЗАМЕНЫ (НомерАбитур, НомерПрепод, НомерЭкзам), как показала проверка, успешно решает проблему.

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

В работе [5] предложены еще два правила, которые используют связи более высоких порядков. Рассмотрим их подробнее.

Правило 7 сформулировано для случая, когда связываются одновременно три сущности. Такая связь названа триплетом. На рис.12 приведен пример ER – диаграммы связи-триплета.

Пример 41 [5]. В качестве предметной области выбран ВУЗ. Имеются преподаватели, которые читают лекции потокам студентов. Выделим три сущности: ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА и ПОТОК с первичными ключами Номер_преподавателя, Название_дисциплины и Номер_потока соответственно. Пусть лекции по одному и тому же предмету могут читать несколько преподавателей. Одному преподавателю разрешается читать несколько предметов. На рис. 12 изображена ER – диаграмма для этого случая.

Рисунок 12 – ER-диаграмма для связи-триплета

Правило 7 [5]. В случае М-сторонней связи необходимо сгенерировать М + 1 предварительное отношение – по одному отношению на каждую из М сущностей с ключами, совпадающими с ключами сущностей, и одно отношение для связи с составным ключом, составленным из первичных ключей связываемых сущностей. Классы принадлежности (КП) сущностей не имеют значения.

Здесь под М-сторонней связью понимается связь М:М между каждой парой сущности (Преподаватель – Поток, Преподаватель – Дисциплина и Поток –Дисциплина). Так, для рассматриваемого примера, изображенного на рисунке 12, должны быть сформированы согласно правилу 7 четыре отношения (первичные ключи выделены):

R1 (Номер преподавателя,...)

R2 (Название дисциплины,...)

R3 (Номер_потока,...)

R4 (Номер преподавателя, Название дисциплины, Номер_потока,...)

Далее, логически рассуждая, автор этого примера приходит к выводу, что в отношении R4 можно оставить в качестве первичного ключа только два атрибута, а третий атрибут “Номер преподавателя сделать неключевым”:

R4 (Название дисциплины, Номер_потока, Номер преподавателя,...)

И в этом автор прав, что можно легко показать [6], используя для проектирования формальный метод синтеза, рассмотренный в разделе 2.2.

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

Итак, пусть имеем исходный набор атрибутов U = ABCDEKL, где

A – номер преподавателя,

B – номер кафедры, на которой работает преподаватель,

C – стаж работы преподавателя,

D – название дисциплины, которую читает преподаватель,

E – количество часов, отводимых на дисциплину,

K – номер потока, которому читается дисциплина,

L – количество групп в потоке.

Предположим, что для каждого предмета отведено фиксированное количество часов. Такое предположение можно сделать, не нарушая строгости данного случая.

На множестве атрибутов U можно определить функциональные зависимости:

F = {A ® BC, DK ® A, K ® L, D ® E}

Условно неизбыточное покрытие ℱ₀ расширенного множества зависимостей будет таким:

ℱ₀ = {A ® BC, DK ® ABCEL, K ® L, D ® E}.

Поскольку в полученном множестве имеется зависимость с полным набором атрибутов (подчеркнута), тривиальную зависимость U ® Æ добавлять не надо.

Проверку зависимостей на элементарность опускаем.

На рисунке 13 приведена диаграмма, на которой проведена операция транзитивной редукции зависимостей.

Рисунок 13 – Результирующая диаграмма зависимостей

Из диаграммы получим результирующую декомпозицию:

R₁ = A BC соответствует отношению R1 (Номер преподавателя,...)

R₂ = D E соответствует отношению R2 (Название предмета,...)

R₃ = K L соответствует отношению R3 (Номер потока,...)

R₄ = DK A соответствует отношению R4 (Название предмета, Номер потока,

Номер_преподавателя,...)

Легко заметить, что набор атрибутов DK является суперключом, причем минимальным, так как DK⁺ = DKABCLE = U, но D⁺ = DE ≠ U и K⁺ = KL ≠ U. Это обстоятельство и позволило заменить первичный ключ в отношении

R4 (Номер преподавателя, Название дисциплины, Номер_потока,...)

на набор из двух атрибутов:

R4 (Название дисциплины, Номер_потока, Номер преподавателя,...).

Следует отметить, что в некоторых случаях использование правила 7 позволяет уменьшить количество таблиц в реляционной базе данных. В данном случае количество таблиц при проектировании методом ER – диаграмм совпадает с количеством таблиц, полученных при проектировании методом синтеза, однако синтез сразу дает ключ в таблице R4, состоящий из двух атрибутов вместо трех.

Правило 7 было сформулировано для случая, когда связываются одновременно три сущности. Такая связь названа в работе [5] триплетом. Однако можно это правило обобщить на случай большего количества М-сторонних связей между сущностями. Кроме того, модификация этого правила позволила найти процедуру уменьшения таблиц в результирующей декомпозиции, полученной только с использованием шести правил. Эта процедура будет подробно описана в разделе 2.6. Здесь же рассмотрим процедуру для триплета.

Поскольку между сущностями ПРЕПОДАВАТЕЛИ, ПОТОКИ и ДИСЦИПЛИНЫ существуют только М-сторонние связи, то независимо от класса принадлежности сущностей по правилу 6 для каждой М-сторонней связи должно быть получено по три таблицы.

В этом случае описание ER-диаграммы будет таким:

ПРЕПОДАВАТЕЛИ (М) читают (М) ДИСЦИПЛИНЫ (правило 6)

ДИСЦИПЛИНЫ (М) читаются (М) ПОТОКАМ (правило 6)

С ПОТОКАМИ (М) работают (М) ПРЕПОДАВАТЕЛИ (правило 6)

Результирующие таблицы будут такими:

R1: ПРЕПОДАВАТЕЛИ (Номер преподавателя,...)

R2: ДИСЦИПЛИНЫ (Название дисциплины,...)

R3: ПРЕПОДАВАТЕЛИ_ДИСЦИПЛИНЫ (Номер преподавателя, Название

дисциплины)

R4: ПОТОКИ (Номер_потока,...)

R5: ДИСЦИПЛИНЫ_ПОТОКИ (Название дисциплины,Номер_потока)

R6: ПРЕПОДАВАТЕЛИ_ПОТОКИ (Номер преподавателя, Номер_потока).

Спроектированная база данных содержит 6 таблиц.

Если теперь удалить таблицы R3, R5 и R6 и вместо них добавить таблицу

R7: ПРЕПОДАВАТЕЛИ_ДИСЦИПЛИНЫ_ПОТОКИ (Номер преподавателя,

Название дисциплины, Номер_потока,...),

как показано на рисунке 14, то результат проектирования будет такой же, как и при использовании правила 7.

Рисунок 14 – Операция уменьшения количества таблиц в базе данных для триплета

Из рисунка 14 видно, что М-связанные сущности ПРЕПОДАВАТЕЛИ, ДИСЦИПЛИНЫ и ПОТОКИ образуют кольцо. Причем, добавленная таблица R7 содержит не минимальный суперключ (Номер преподавателя, Название дисциплины, Номер_потока) или в обозначениях, данных выше, - набор атрибутов ADK. Минимальным суперключом является набор атрибутов DK. Поэтому в таблице R7 в качестве первичного ключа можно оставить набор атрибутов DK, а атрибут A сделать неключевым, как интуитивно предложено в работе [5]. Тогда таблица R7 будет такой:

R7: ПРЕПОДАВАТЕЛИ_ДИСЦИПЛИНЫ_ПОТОКИ (Название дисциплины,

Номер_потока, Номер преподавателя,...)

Теперь база данных, спроектированная по методу ER-диаграмм, состоящая из таблиц R1, R2, R4, R6, R7 полностью совпадает с результатами проектирования по методу синтеза.

В работе [5] предлагается еще использовать правило 8, учитывающее ролевые связи между сущностями. Этот случай, как правило, не дает выигрыша по количеству результирующих таблиц, однако делает прозрачной структуру таблиц. Метод синтеза для этого случая дает меньше таблиц. Продемонстрируем этот факт примером.

Пример 42. [6] Развивая предыдущий пример о преподавателях, предположим, что некоторые из преподавателей являются заведующими кафедр, то есть являются руководителями для других (обычных) преподавателей. Графически это показано на рисунке 15.

Пусть ключом сущности ПРЕПОДАВАТЕЛЬ является Таб_номер. Экземпляры данной сущности могут играть роль либо заведующего кафедрой, либо обычного преподавателя. Два ролевых набора ЗАВ_КАФЕДРОЙ и ОБЫЧН_ПРЕПОД соединяются связью руководит.

На ER – диаграмме ролевая связь изображается стрелками от сущности, порождающей роли (ПРЕПОДАВАТЕЛЬ), к ролевым сущностям (ЗАВ_КАФЕДРОЙ и ОБЫЧН_ПРЕПОД). Ключи всех этих сущностей принадлежат одному домену.

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

На рисунке 16 приведен общий случай ER – диаграммы для ролевой связи.

Рисунок 15 – Пример ER-диаграммы для ролевой связи

Рисунок 16 – Общий вид ER-диаграммы ролевой связи

Правило 8. [5] Исходная сущность, порождающая роли, является источником одного предварительного отношения, причем ключ этой сущности служит ключом отношения. Ролевые элементы порождают еще по одному отношению с теми же ключами, что и исходная сущность. Связи, соединяющие ролевые отношения, генерируют столько отношений, сколько требуется для данного вида связи по соответствующим правилам.

Таким образом, согласно правилу 8 для ER–диаграммы, изображенной на рисунке 16, необходимо иметь следующий набор предварительных отношений:

R (Ключ,...) - соответствует сущности, порождающей роли,

R1 (Ключ_1,...) - соответствует сущности для первого ролевого элемента,

R2 (Ключ_2,...) - соответствует сущности для второго ролевого элемента,

и так далее,

R_К (Ключ_К,...) - соответствует сущности для К-го ролевого элемента.

Применяя правило 8 для ER–диаграммы, изображенной на рисунке 15, получим следующий набор предварительных отношений:

R1 (Таб_номер,...) - соответствует сущности ПРЕПОДАВАТЕЛЬ, порождающей роли;

R2 (Таб_номер1,...) - соответствует ролевому элементу ЗАВ_КАФЕДРОЙ;

R3 (Таб_номер2, Таб_номер1,...) - соответствует ролевому элементу

ОБЫЧН_ПРЕПОД.

Отношение R3 содержит в качестве простого атрибута первичный ключ ролевого элемента ЗАВ_КАФЕДРОЙ (по правилу 4).

При наличии ролевых связей метод синтеза может дать меньшее количество таблиц. Покажем это на том же примере.

Итак, пусть имеем исходный набор атрибутов U = ABCDE, где

A – Таб_номер_преподавателя,

B – Номер_кафедры, на которой работает преподаватель,

C – ФИО преподавателя,

D – Номер_трудовой_книжки преподавателя.

E – Номер заведующего кафедрой (совпадает с номерами Таб_номер преподавателя

для заведующих кафедрами).

На множестве атрибутов U можно определить функциональные зависимости:

F = {A ® BCD, B ® E}

Условно неизбыточное покрытие ℱ₀ расширенного множества зависимостей будет таким:

ℱ₀ = { A ® BCDE, B ® E}.

Поскольку в полученном множестве имеется зависимость с полным набором атрибутов (подчеркнута), тривиальную зависимость U ® Æ добавлять не надо.

На рисунке 17 приведена ранжированная диаграмма, на которой проведена операция транзитивной редукции зависимостей.

Рисунок 17- Результирующая диаграмма зависимостей

Из диаграммы получим результирующую декомпозицию:

R₁ = A BCD и R₂ = B E или в терминах реальных данных:

R1 (Таб_номер, Кафедра, ФИО, Номер_труд_книжки) – таблица Преподаватели

R2 (Кафедра, Таб_номер) – таблица Заведующие

Тогда получить сведения о преподавателе, являющемся заведующим заданной кафедры, можно, например, с помощью запроса с параметром вида (в стандарте JET-SQL):

SELECT Преподаватели.*

FROM Заведующие INNER JOIN Преподаватели ON

Заведующие.каф = Преподаватели.каф

WHERE (((Заведующие.каф) = [кафедра?]) AND ((Преподаватели.таб_номер)

In (select Таб_номер From Заведующие)));

В этом случае метод синтеза дает меньше таблиц.