Лекция №4, Проектирование реляционной (табличной) базы данных через функциональные зависимости

« Назад

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

Алгоритм проектирования базы данных состоит из следующих этапов.

1. Построение универсального отношения.

2. Установление функциональных зависимостей между атрибутами универсального отношения.

3. Преобразование функциональных зависимостей с целью проверки, находится ли отношение в нормальной форме Бойса-Кодда.

4. В случае отрицательного результата проверки декомпозиция отношения на два с выделением того отношения, которое не соответствует требованиям нормальной формы Бойса-Кодда и переход на пункт 3 для дальнейших преобразований отделенного отношения.

5. Сопоставление таблиц полученным отношениям.

Универсальное отношение - отношение, включающее в себя все атрибуты.

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

Первой нормальной формой (НФ) называют отношение, в каждом элементе которого используется только атомарное значение, то есть отсутствует перечисление (список) значений.

В процессе преобразований универсального отношения используются функциональные зависимости (ФЗ) между атрибутами универсального отношения.

Говорят, что атрибут или агрегат атрибутов B находится в функциональной зависимости от атрибута или агрегата атрибутов A, если каждому значению A соответствует одно и то же значение B.

В краткой форме функциональную зависимость B от A записывают в виде:

A --> B или B<-- A.

Возможно графическое изображение зависимости:

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

Если в функциональной зависимости (A --> B) A либо одиночный атрибут, либо A является агрегатом, но B не зависит функционально ни от одного подмножества A, то A называется детерминантом B.

Преобразования универсального отношения имеют конечной целью нормальную форму Бойса-Кодда.

Отношение находится в нормальной форме Бойса-Кодда (НФБК), если и только если каждый детерминант отношения является возможным ключом.

Правило. Если после преобразований получается совокупность функциональных зависимостей между всеми атрибутами, соответствующая НФБК, то отношение следует оставить без изменения и и сопоставить ему одну общую таблицу или несколько таблиц из соображений экономичной реализации. Если же среди функциональных зависимостей есть зависимости, в которых детерминант не является возможным ключом, то есть из-за этих зависимостей нарушается условие НФБК, то эти зависимости следует выделить в отдельное отношение. Отделенное отношение нужно преобразовывать далее к НФБК.

Например, приведенное ниже отношение ДЕТИ СТУДЕНТОВ находится в первой нормальной форме. Оно не будет в указанной форме, если родители детей будут перечислены “через запятую”.

ОТНОШЕНИЕ: ДЕТИ СТУДЕНТОВ

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

Роль человека однозначно зависит от его фамилии:

ФИО —> Роль.

Домашний адрес студента, студентки и ребенка однозначно определяется фамилией:

ФИО —> Адрес.

Номер телефона однозначно задан адресом:

Адрес —> Телефон.

Фамилия ребенка однозначно задает его родителей и год рождения:

(ФИО, роль)—>(Отец, Мать, Год рожд.) .

Возможным ключом в исходном отношении может быть только атрибут ФИО. Поэтому среди приведенных функциональных зависимостей только в зависимости “Адрес —> Телефон” детерминант не является возможным ключом; эта зависимость подлежит отделению во второе отношение, и оно далее преобразуется в отдельную таблицу.

Правила преобразования функциональных зависимостей (ФЗ).

1. Использование свойства транзитивности.

В наборе ФЗ A --> B, B --> C, A --> C

зависимость A --> C является избыточной.

2. Выделение детерминанта.

В наборе ФЗ       A --> B, (A, Z) --> B

вторая зависимость является избыточной.

3. Избыточное пополнение.

Функциональная зависимость (A, Z) --> (B, Z) может быть

заменена на зависимость (A, Z) --> B.

4. Объединение.

Набор A --> B, A --> C можно заменить на A --> (B, C).

5. Распределение.

Зависимость A --> (B, C) можно заменить на набор зависимостей

 A --> B, A --> C.

6. Псевдотранзитивность.

В наборе ФЗ A --> B, (B, C) --> D, (A, C) --> D последняя зависимость (A, C) --> D является избыточной.

Применение правил преобразования изменяет семейство функциональных зависимостей.

Пусть F - исходная совокупность функциональных зависимостей данного отношения. Замыканием F называется множество функциональных зависимостей, которые логически следуют из F.

Замыкание F обозначают F+. Если F = F+, то F - полное множество зависимостей.

Вычисление F+, то есть замыкания F, может оказаться трудоемкой задачей. Например, пусть F={A-->B1, A-->B2,..., A-->Bn}. Пользуясь правилом объединения получим замыкание F+ в виде набора зависимостей с характерной закономерностью {A-->B1, A-->(B1,B2), A-->(B1,B2,B3),...}. Если атрибутам Bi сопоставить разряд с единичным значением, то возможные функциональные зависимости можно отобразить как возможные “единицы” в двоичном числе. Следовательно, множество F+ состоит из 2 в степени n функциональных зависимосте, и действительно, получение замыкания F+ может представить проблему при большом n.

На основе рассмотренных теоретических понятий можно дать формальное определение ключу. Атрибут или агрегат атрибутов X для отношения R с атрибутами A1, A2,..., An и функциональными зависимостями F будет ключом, если выполняются следующие условия:

1) Зависимость X-->(A1, A2,...,An) принадлежит замыканию F+.

2) Ни для какого подмножества Y агрегата X зависимость Y-->(A1, A2,..., An) не принадлежит замыканию F+.

Пример. Пусть R=(A, B, C) и F={ A-->B, B-->C }. Атрибут A суть ключ, так как в замыкание F+ входит A-->( A, B, C) и атрибут A неделим.

Проверка декомпозиции

Результат декомпозиции проверяют на свойство соединение без потерь.

Пусть универсальное отношение, имеющее схему R=(A1, A2,...,An), разложено на k отношений со схемами (R1, R2,...,Rk), использующих множество F функциональных зависимостей. Алгоритм проверки на свойство соединение без потерь заключается в следующем.

Строится таблица с n столбцами и k строками, причем j-ый столбец сопоставляется j-ому атрибуту Aj, а i-ая строка i-ой схеме отношения Ri. На пересечении i-ой строки и j-ого столбца записывается символ aj, если атрибут Aj входит в схему отношения Ri ; в пртивном случае записывается символ bij. После составления таблицы перебираем поочередно функциональные зависимости X-->Y из множества F. В таблице выделяем столбцы с атрибутами из агрегата X и проходим по строкам. В случае обнаружения одинаковых в пределах агрегата X строк преобразуем столбцы из агрегата Y по следующему правилу: если в столбцах из агрегата Y один из символов aj, то и другие делаем равными aj; если же ни один из символов не равен aj, то другие символы делаем одинаковыми, а именно равными одному из bij.

Если после преобразований образуется хотя бы одна строка только из aj, то свойство соединения без потерь присутствует.

Пример. Пусть R=(A, B, C, D, E),

R1=(A, D), R2=(A, B), R3=(B, E), R4=(C, D, E), R5=(A, E)

и множество F:   A-->C, B-->C, C-->D, (D, E)-->C, (C, E)-->A.

Создаем исходную таблицу по схемам R:

Обрабатываем зависимость A-->C:

Обрабатываем зависимость B-->C:

Обрабатываем зависимость C-->D:

Обрабатываем зависимость (D, E)-->C:

Обрабатываем зависимость (C, E)-->A:

Строка 3 состоит только из символов aj, что говорит о том, что свойство соединения без потерь имеет место и, следовательно, декомпозиция отношения была выполнена без ошибок.