Алгоритм метода синтеза отношений
В данном разделе приводится лишь некоторый обзор алгоритма синтеза отношений.
Мы уже рассматривали примеры декомпозиции с потерей ФЗ. Причиной потери ФЗ является некоторая ФЗ
На пути решения этой проблемы было бы неплохо усилить все ФЗ, связав их с уникальными ключами, скажем, описывая для них уникальные индексы. Тогда можно контролировать целостность базы данных. Для этого нужно усилить минимальное покрытие. Грубо говоря, усиливаемость минимального покрытия означает, что выделено множество первичных ключей и все ФЗ из минимального покрытия пересмотрены в призме этого множества с точки зрения выводимости ФЗ рассматриваемой базы данных.
Введем определение.
Определение 4. Реляционная база данных называется полной, если:
- все ФЗ усилены ключами;
- все отношения находятся в 3НФ;
- не существует варианта базы данных с меньшим числом схем, удовлетворяющим вышеперечисленным свойствам.
Почти всегда в предметной области базы данных можно выделить набор отношений, обладающих свойством полноты. Доказана теорема [Мейер], что существует алгоритм, который выводит полную базу данных из множества заданных ФЗ.
Поскольку такой алгоритм строит схему базы данных непосредственно из заданного набора ФЗ, он называется алгоритмом синтеза базы данных. При этом на первый план выступает проблема правильного представления отношения с заданной схемой своими проекциями, т.е. соединения по результирующей схеме базы данных могут оказаться ложными. Однако если минимальное покрытие исходного набора ФЗ будет усилено, то подобного явления можно избежать.
Пример. Универсальный ключ и ложные соединения
Пусть отношение R имеет кортежи:
| 1 1 1 1 | 4 1 2 2 |
Случай 1.
Отсутствие ложных соединений
Разбиение на отношения
R1=ABC и R2=BCD
Случай 2. Наличие ложных соединений
Разбиение на отношения
R1 = AB и R2= BCD
ABCD
| 1 1 1 1 | 1 1 2 2 |
| 4 1 1 1 | 4 1 2 2 |
Поскольку
AC
Заметим, что атрибут А выступает в качестве ключа практически во всех ФЗ. Выделенный или добавленный атрибут, обладающий подобным свойством, называется универсальным ключом. Таким образом, решение проблемы ложных соединений заключается в добавлении подсхемы, которая содержит универсальный ключ, и выполнении соединения с ее использованием.
Теперь можно перейти к обзору алгоритма синтеза реляционной базы данных.
Теоретически показано, что для того, чтобы синтезировать полную базу данных, необходимо построить кольцевое минимальное покрытие для исходного набора ФЗ.
Введем некоторые обозначения. Составной ФЗ называется ФЗ:
В принятых обозначениях основные этапы алгоритма синтеза отношений приведены ниже.
Алгоритм поэтапного синтеза отношений
Вход: F - множество ФЗ предметной области базы данных
Выход: схема полной базы данных
Этап 1. Нахождение неизбыточного покрытия F1 для F
Для каждой ФЗ из F проверяется, может ли данная ФЗ быть выведена из оставшихся ФЗ. Если да, то ФЗ удаляется. Этап завершается после перебора всех ФЗ из F. В результате выполнения этапа получается множество ФЗ F1.
Этап 2. Сокращение слева элементов F1
Удаляются последовательно один за другим атрибуты из левых частей ФЗ F1; проверяется, может ли полученная ФЗ быть выведена из исходных ФЗ F1. Если да, то исходная ФЗ заменяется на новую ФЗ. Этап завершается после перебора всех ФЗ F1.
В результате получается множество ФЗ F2.
Этап 3. Сокращение справа элементов F2
Удаляются последовательно один за другим атрибуты ФЗ из правых частей ФЗ F2; проверяется, может ли исходная ФЗ быть выведена из полученной ФЗ и имеющихся ФЗ F2. Если да, то исходная ФЗ заменяется на новую ФЗ. Этап завершается после перебора всех ФЗ F2. В результате получается множество ФЗ F3.
На этом сокращение ФЗ закончено. Избыточность отсутствует. Необходимо приступать к построению минимального покрытия.
Этап 4. Разделение F3 на классы эквивалентности по правым частям
Строится разбиение F3 на группы: две ФЗ принадлежат одной и той же группе тогда и только тогда, когда их правые части эквивалентны. В результате получается множество классов эквивалентности ФЗ
Этап 5. Удаление в классах эквивалентности избыточных ФЗ
Для всех пар ФЗ fdi и fdj из одной и той же группы проверяется, может ли ФЗ левой стороны fdj от правой стороны fdj быть выведена из этой группы ФЗ. Если да, то из fdj ФЗ удаляется и добавляется в правую часть этой ФЗ к правой fdi. Новая ФЗ будет находиться в той же группе, что и исходная ФЗ. В результате получается минимальное число ФЗ F5, покрывающих F3.
Этап 6. Получение классов эквивалентности по левым частям F5 и составных ФЗ C1
Для каждого множества ФЗ с эквивалентными левыми частями из F5 создается составная ФЗ
Этап 7. Удаление избыточных зависимостей из С1
Для каждой составной ФЗ из С1 и для каждого атрибута Xi из левой части С сдвигаются атрибуты в правую часть. В результате получается множество составных ФЗ С'. Если fd(C') эквивалентно fd(C1), то С1 заменяется на С'. В результате получается множество ФЗ С2.
Этап 8. Формирование кольцевого минимального покрытия
Для каждой составной ФЗ c из С2 и каждого атрибута A из правой части c удаляется атрибут А. В результате получается С', состоящее из с'. Если fd(C') эквивалентно fd(C2), то С2 заменяется на С'.В результате получается множество ФЗ С3.
Этап 9. Формирования схемы полной базы данных
Для каждой составной ФЗ с из С3 формируется таблица атрибутов, которые появляются в с. Ключами для этой таблицы являются Хi из левой части с. Таблица послужит для усиления ФЗ в F.
Алгоритм поэтапного синтеза отношений обладает хорошей сходимостью, его целесообразно использовать в запрограммированном виде. Для этого можно воспользоваться уже готовой программой, или написать свою программу с учетом специфики своих задач, обратившись к монографии Д. Мейера [3].
В результате получается множество ФЗ С3.
Этап 9. Формирования схемы полной базы данных
Для каждой составной ФЗ с из С3 формируется таблица атрибутов, которые появляются в с. Ключами для этой таблицы являются Хi из левой части с. Таблица послужит для усиления ФЗ в F.
Алгоритм поэтапного синтеза отношений обладает хорошей сходимостью, его целесообразно использовать в запрограммированном виде. Для этого можно воспользоваться уже готовой программой, или написать свою программу с учетом специфики своих задач, обратившись к монографии Д. Мейера [3].
Пример. Применение алгоритма синтеза
Пример иллюстрирует работу алгоритма на каждом из его этапов.
- Если , то
может быть удалена.
- Пусть , тогда или A, или B могут быть удалены из
.
иливыводится из F1 следующим образом: Из
(по аддитивности); из
и
(по транзитивности).
- Пусть , тогда С может быть удалена из
. Из
и
(по транзитивности); из
(по аддитивности).
- Пусть . Тогда так как
, то имеется одна группа
. Так как
(по расширяемости и аддитивности), то другая группа есть
.
- Из иТак как
принадлежит к другой группе, чем
и
, то последние ФЗ могут быть заменены на
. - Имеем .
- Пусть с=(A;B;A,B). . Сдвигаем A,B в правую часть с и получаем с' = (A;B). Тогда
. A,B может быть удалена из с, так как они есть в левой части с'. Так как
могут быть выведены из
, то с может быть заменена на с'.
- Пусть .
. D удаляется из
и
.
. Так как
может быть выведена из
, то С2 может быть заменена на С'.
- Пусть . Тогда первое отношение есть ABCD c ключом (A,{B,C}); второе отношение есть BD с ключом {B}; третье отношение есть FG с ключом {F,G}.
Выводы
- В рамках теории реляционных баз данных предлагается два основных подхода к построению логических моделей баз данных: метод декомпозиции и метод синтеза схем отношений.
- Метод декомпозиции основывается на разбиении некоторого универсального отношения на два или более отношений с помощью реляционной операции проекции.
- Метод синтеза основывается на обработке исходного множества ФЗ предметной области базы данных.
- Метод декомпозиции нагляден, достаточно просто реализуется в инструментальных CASE-средствах проектирования, но имеет ряд потенциальных недостатков, связанных с потерей данных при соединениях и с потерей ФЗ.
- Метод синтеза не приводит к потерям ФЗ, но имеет ряд потенциальных угроз потери информации при соединениях и обладает высокой вычислительной стоимостью.
- Предлагается ряд технических приемов по преодолению потенциальных недостатков в обоих подходах, позволяющих строить эффективные логические модели данных.
- На практике при построении логической модели реляционной базы данных целесообразно комбинировать оба подхода, отдавая предпочтение методу декомпозиции.
Создание логической модели реляционной базы данных методом декомпозиции: преобразование ER-диаграмм в отношения базы данных
Практика проектирования реляционных баз данных методом декомпозиции отношений показала ряд его недостатков, связанных с потерей данных при соединениях и с потерей ФЗ. Однако метод декомпозиции достаточно прост для понимания, нагляден, легко реализуется в инструментальных CASE-средствах проектирования и в настоящее время является наиболее часто применяемым при проектировании баз данных.
Для построения логических моделей реляционных баз данных методом декомпозиции сформулирован ряд правил, получивших название правила преобразования ER-диаграмм в отношения базы данных. Правила позволяют исключить потенциальные недостатки метода декомпозиции и нацелены на приведения схемы отношений базы данных к нормальным формам.
Рассмотрим правила преобразования на примере базы данных о преподавателях, читающих лекции в институте. Сущность Преподаватель соотносится с сущностью Предмет посредством связи Читает. При этом возможны следующие варианты поведения данной предметной области:
- каждый преподаватель читает только один курс, и каждый курс читается только одним преподавателем, т.е. классы принадлежности обеих сущностей являются обязательными;
- каждый преподаватель читает только один курс, и каждый курс читается не более чем одним преподавателем, т.е. класс принадлежности первой сущности является обязательным, а второй сущности - необязательным;
- каждый преподаватель читает не более одного курса, и каждый курс читается не более чем одним преподавателем, т.е. классы принадлежности обеих сущностей не являются обязательными;
- каждый преподаватель читает не более одного курса, а каждый курс читается только одним преподавателем.
Возможны варианты с иной степенью связи, например когда каждый преподаватель может читать несколько курсов.
Каждый из этих вариантов может быть представлен ER-диаграммой. Однако следует помнить, что каждая ER-диаграмма представляет свой собственный набор правил поведения предметной области и только одна из них может быть истинной в каждый момент времени.
Если степень бинарной связи определена, то предварительные отношения могут быть получены путем просмотра нескольких альтернатив и выбора варианта, наиболее подходящего с точки зрения правил предметной области и личных предпочтений проектировщика. Определяющими признаками выбора одного из альтернативных вариантов представления отношения являются степень связи и класс принадлежности сущности.
Сформулируем первое правило.
Правило 1. Если степень бинарной связи 1:1 и класс принадлежности обеих сущностей является обязательным, то требуется построение только одного отношения. При этом первичным ключом отношения может быть ключ любой сущности.
Исходное отношение является одновременно и конечным отношением.
Пример.
ПРЕПОДАВАТЕЛЬ (Табельный_номер, Фамилия, Предмет, Количество_часов)
Это правило может быть применено для первого варианта поведения предметной области, когда исходное отношение не требует декомпозиции, так как не содержит избыточных данных и нуль-значений.
Сформулируем второе правило.
Правило 2. Если степень бинарной связи 1:1 и класс принадлежности одной сущности является обязательным, а другой сущности - не обязательным, то требуется построение двух отношений - по одному на каждую сущность. При этом первичным ключом каждого отношения является ключ его сущности, а ключ сущности с необязательным классом принадлежности добавляется в отношение для сущности с обязательным классом принадлежности в качестве атрибута (миграция ключа). Пример.
Исходное отношение:
ПРЕПОДАВАТЕЛЬ_1 (Табельный_номер, Фамилия, Предмет, Количество_часов)
Результирующие отношения:
ПРЕПОДАВАТЕЛЬ_2 (Табельный_номер, Фамилия, Предмет) ПРЕДМЕТЫ (Предмет, Количество_часов)
Это правило может быть применено во втором варианте, когда исходное отношение уже требует декомпозиции. Исходное отношение ПРЕПОДАВАТЕЛЬ_1 содержит проблему нуль-значений: данные о предметах, которые не читаются в данный момент, не могут быть внесены в базу данных.
Результирующее отношение ПРЕПОДАВАТЕЛЬ_2 не имеет проблемы нуль-значений.
В результирующем отношении ПРЕДМЕТЫ эта проблема исключается: для предмета, который в данный момент не читается, определяется специальное непустое значение по умолчанию. Миграция ключа необходима для восстановления исходного отношения. Таким образом, миграция ключа в методе декомпозиции представляет собой перенос первичного ключа одного отношения в другое отношение для предотвращения потери данных при соединении.
Сформулируем третье правило.
Правило 3. Если степень бинарной связи 1:1 и класс принадлежности обеих сущностей не является обязательным, то требуется построение трех отношений - по одному на каждую объектную сущность и одному для связывающего отношения. При этом ключ каждой сущности является первичным ключом соответствующего отношения и одного отношения для связи, с первичным ключом, составленным из ключей объектных сущностей.Пример.
Исходное отношение:
ПРЕПОДАВАТЕЛЬ_1 (Табельный_номер, Фамилия, Предмет, Количество_часов)
Результирующие отношения:
ПРЕПОДАВАТЕЛЬ_2 (Табельный_номер, Фамилия) ПРЕДМЕТЫ (Предмет, Количество_часов) ЧИТАЕТ (Табельный_номер, Предмет)
Это правило можно применить в третьем варианте поведения предметной области, когда исходное отношение необходимо разбить на три отношения. Разбиение на два отношения не позволит исключить проблему нуль-значений. В случае трех отношений такая проблема исключается: в отношение ПРЕДМЕТЫ для предмета, который в данный момент не читается, определяется непустое значение по умолчанию.
Сформулируем четвертое правило.
Правило 4. Если степень бинарной связи 1:N, и класс принадлежности n-связной сущности является обязательным, то достаточно построить два отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения, а ключ 1-связной сущности добавляется в отношение для n-связной сущности в качестве атрибута.
Пример.
Исходное отношение:
ПРЕПОДАВАТЕЛЬ_1 (Табельный_номер, Фамилия, Предмет, Количество_часов)
Результирующие отношения:
ПРЕПОДАВАТЕЛЬ_2 (Табельный_номер, Фамилия) ПРЕДМЕТЫ (Предмет, Количество_часов, Табельный_номер)
Сформулируем пятое правило.
Правило 5. Если степень бинарной связи 1:N и класс принадлежности n-связной сущности не является обязательным, то необходимо построить три отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения и одного отношения для связи. Ключи сущностей должны быть атрибутами последнего отношения. Пример.
Исходное отношение:
ПРЕПОДАВАТЕЛЬ_1 (Табельный_номер, Фамилия, Предмет, Количество_часов)
Результирующие отношения:
ПРЕПОДАВАТЕЛЬ_2 (Табельный_номер, Фамилия) ПРЕДМЕТЫ (Предмет, Количество_часов) ЧИТАЕТ (Предмет, Табельный_номер)
Отметим, что если степень бинарной связи 1:N, то фактором, определяющим выбор одного из правил (правила 4, 5), является класс принадлежности n-связной сущности. Класс принадлежности 1-связной сущности не влияет на конечный результат декомпозиции. В ситуации правила 4 имеет место проблема нуль-значений по атрибуту Предмет, в ситуации правила 5 имеет место проблема нуль-значений по атрибутам Предмет и Преподаватель. Поэтому во избежание дублирования и нуль-значений в ситуации правил 4 и 5 необходимо строить два и три результирующих отношения соответственно. Миграция ключа 1-связной сущности выполняется для восстановления исходного отношения при соединении.
Если степень бинарной связи N:M, то во избежание дублирования и нуль-значений необходимо всегда строить три отношения. Сформулируем шестое правило.
Правило 6. Если степень бинарной связи M:N, то необходимо построить три отношения - по одному для каждой сущности и одно отношение для связи. При этом ключ каждой сущности является первичным ключом соответствующего отношения, и входит в составной первичный ключ отношения для связи. Пример.
Исходное отношение:
ПРЕПОДАВАТЕЛЬ_1 (Табельный_номер, Фамилия, Предмет, Количество_часов)
Результирующие отношения:
ПРЕПОДАВАТЕЛЬ_2 (Табельный_номер, Фамилия) ПРЕДМЕТЫ (Предмет, Количество_часов) ЧИТАЕТ (Предмет, Табельный_номер)
Для отношения с трех- и более сторонней связью во избежание избыточности и нуль-значений требуется построение не менее четырех отношений.
Сформулируем седьмое правило.
Правило 7. Если связь является трехсторонней, необходимо построить четыре отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения и одного отношения для связи. Ключи сущностей должны быть атрибутами последнего отношения.
Аналогично для отношения с n-сторонней связью требуется построение n+1 отношений.
Отметим, что все вышесформулированные правила построены по одному общему принципу: каждому неключевому атрибуту - свое отношение, т.е. миграция неключевых атрибутов запрещена.
Следует помнить, что после предварительного разбиения исходного отношения необходимо показать, используя ФЗ и ключи отношений, что полученная схема реляционной базы данных находится в НФ Бойса-Кодда (НФБК) (или 3НФ). Только тогда полученная схема отношений может считаться окончательной. Обычно проектировщики баз данных при использовании метода декомпозиции не выполняют таких действий, так как в большинстве случаев (но не всегда!) применение правил преобразования дает НФБК.
В некоторых случаях может оказаться, что для создания логической модели предметной области базы данных недостаточно имеющихся сущностей и связей. Одним из них является ситуация, когда экземпляры одной сущности играют разные роли (супертип/подтип) в предметной области базы данных. Это обусловливается наличием между экземплярами сущности отношения иерархии или агрегации по включению. При этом сущность представляет собой множество с отношением порядка на экземплярах, что приводит к наличию классов эквивалентности, имеющих различную семантическую интерпретацию в предметной области.
Так, например, база данных кафедры института содержит две категории служащих - преподаватели и заведующий кафедрой. Заведующий кафедрой также может читать лекции по предметам, но получает обычно фиксированный оклад; преподаватели имеют почасовую ставку оплаты. Попробуем представить информацию о служащих кафедры более подходящим образом. Выделим для каждой категории служащих кафедры отдельную сущность и рассмотрим ER-диаграмму Зав.
кафедрой Руководит Преподавателями.
При этом ключом каждой сущности будет являться табельный номер служащего. Поскольку связь Руководит имеет степень 1:N, и класс принадлежности обеих сущностей является обязательным, то согласно правилу 4 достаточно построить два предварительных отношения. Поскольку неключевые атрибуты Фамилия и Адрес_служащего помещены в оба предварительных отношения, то согласно общему принципу правил преобразования они должны быть переопределены для одного из отношений. Переименование атрибутов в одном из отношений порождает проблему ответа на запрос: для того чтобы найти домашний телефон конкретного служащего, необходимо пересмотреть оба отношения и построить объединение результатов просмотра. Таким образом, переименование атрибутов, к которому иногда поспешно прибегают проектировщики, не является хорошим решением.
Рассмотрим иной вариант представления данных о служащих кафедры. Будем считать заведующего кафедрой и преподавателей служащими, и представим их функции как роли, которые данный служащий может играть. Тогда Отношение СЛУЖАЩИЙ представляет собой родительское отношение - супертип для двух подчиненных отношений - подтипов ЗАВ. КАФЕДРОЙ и ПРЕПОДАВАТЕЛЬ, которые соединяются связью Руководит (см. рис. 7.1).
Рис. 7.1. Отношение "супертип/подтип"
Родительское отношение - супертип - содержит общие с подчиненными отношениями-подтипами атрибуты. Подчиненные отношения - подтипы содержат специфическую для их ролей информацию. Каждое порождаемое ролью отношение связано с общим отношением через атрибут общего домена, в данном случае табельный номер. Окончательный набор отношений будет состоять из трех отношений.
Результирующие отношения:
СЛУЖАЩИЙ (#служащий, общие атрибуты для всех служащих) ЗАВЕДУЮЩИЙ (#заведующий, .... ) ПРЕПОДАВАТЕЛЬ (#преподаватель, ..., #заведующий)
Заметим, что связь, которая соединяет две роли одной исходной сущности, называется рекурсивной (служащие руководят служащими). Связь, которая соединяет роли двух различных сущностей, не является рекурсивной.
Чтобы избежать поиска с целью выявления типа работы служащего, можно ввести в родовое отношение дополнительный атрибут, определяющий, кем является служащий. Несмотря на то, что с точки зрения теории реляционных баз данных такой прием приводит к избыточности данных, к нему прибегают в целях увеличения производительности системы.
Сформулируем восьмое правило.
Правило 8. Исходная сущность служит источником генерации одного отношения. Ключ сущности есть ключ отношения. Подчиненные сущности (ролевые элементы) и связи, соединяющие их, порождают такое количество отношений, которое определяется набором правил 1-7, причем каждый ролевой элемент трактуется как обычная сущность.
