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

Целью этого этапа является оптимизация функционирования существующей системы путем реорганизации базы данных и/или внесения изменений в программное обеспечение.

7.2. Функциональные зависимости

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

Понятие функциональной зависимости

По сути, функциональная зависимость является связью типа «многие к одному» между множествами атрибутов внутри данного отношения.

Пусть R — семейство всевозможных отношений с одинаковым заголовком HR (можно называть

переменной типа отношения, а всякое r P R — значением этой переменной (или допустимым отношением)). Пусть A Ď HR и B Ď HR — некоторые подмножества атрибутов заголовка переменной отношения R.

Определение 1. Множество атрибутов B функционально зависимо от A (и обозначают A Ñ B) тогда и только тогда, когда каждое значение атрибутов A любого допустимого отношения r связано ровно с одним значением атрибутов B отношения r, т. е. если два кортежа совпадают по значению атрибутов A, то они совпадают и по значению атрибутов B. Формально:

pA Ñ Bq ô @r HR; Br P R @T1; T2 P Br p@a P A T1:a T2:aq Ñ p@b P B T1:b T2:bq :

Замечание. Аналогично определяется как частный случай понятие функциональной зависимости и для отдельного обычного отношения r.

Определение 2. Если A Ñ B, то множество атрибутов A называют детерминантом, а B — зави-

симой частью.

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

Далее в основном будут рассматриваться методы сокращения обширного множества функ-

циональных зависимостей до некоторых допустимых размеров. Почему эта цель важна? Одна из причин состоит в том, что многие функциональные зависимости являются ограничениями целостности, поэтому желательно, чтобы СУБД обеспечивала их соблюдение. Следовательно, для каждого заданного множества функциональных зависимостей S желательно найти такое множество T, которое(в идеальной ситуации) было бы существенно меньше множества S по мощности и при этом каждая функциональная зависимость в множестве S могла бы быть заменена функциональной зависимостью из множества T. Если бы такое множество T было найдено, то СУБД достаточно было бы контролировать выполнение функциональных зависимостей из множества T, что автоматически обеспечивало бы соблюдение всех функциональных зависимостей из множества S. Именно поэтому задача поиска подходящего множества T представляет большой практический интерес.

Тривиальные и нетривиальные зависимости

Определение 3. Функциональная зависимость называется тривиальной, если она не может не выполняться, т. е. справедлива при любых условиях.

Определение 3’. Функциональная зависимость A Ñ B называется тривиальной тогда и только тогда, когда B Ď A, иначе она называется нетривиальной.

36

Как подразумевается самим их названием, тривиальные зависимости не представляют особого интереса с точки зрения практики; обычно в процессе проектирования намного важнее определить нетривиальные зависимости, поскольку именно они представляют ограничения целостности для отношения. Поэтому очевидным способом сократить множество функциональных зависимостей — это устранение тривиальных зависимостей.

Замыкание множества зависимостей

Из одних функциональных зависимостей могут следовать другие функциональные зависимости. Пусть есть переменная отношения R, а A Ď HR, B Ď HR и C Ď HR — некоторые подмножества

его атрибутов.

Определение 4. Функциональная зависимость A Ñ C называется транзитивной (или проходящей через B), если существуют функциональные зависимости A Ñ B и B Ñ C.

Определение 5. Множество S всех функциональных зависимостей, которые следуют из заданного множества функциональных зависимостей S, называется замыканием множества S.

Из приведенного определения следует, что для решения сформулированной задачи (сокращение множества зависимостей) необходимо найти алгоритм вычисления S на основе S.

Первая попытка решить эту проблему была предпринята Армстронгом [1]: он предложил набор правил вывода (называемые аксиомами Армстронга1) новых функциональных зависимостей на основе заданных.

Пусть A Ď HR, B Ď HR, C Ď HR — некоторые подмножества атрибутов переменной отношения R.

Базовые аксиомы Армстронга:

1.Правило рефлексивности (reflexivity): если B Ď A, то A Ñ B.

2.Правило дополнения (augmentation): если A Ñ B, то A Y C Ñ B Y C.

3.Правило транзитивности (transitivity): если A Ñ B и B Ñ C, то A Ñ C.

Доказательство: Первая аксиома справедлива, т. к. A Ñ B при B Ď A является тривиальной функ-

1 Но справедливость «аксиом» Армстронга доказывается с помощью определения функциональной зависимости.

37

Аксиому транзитивности тоже докажем от противного. Предположим, что A Ñ B и B Ñ C, но A ­ÑC. Тогда Dr P R: DT1; T2 P Br такие, что

T1:a T2:a @a P A

Данная система правил является:

•Полной — для заданного множества функциональных зависимостей S минимальный набор функциональных зависимостей, которые подразумевают все зависимости из множества S, может быть выведен из зависимостей множества S на основе только этих правил.

•Непротиворечивой — с помощью этих правил не могут быть выведены никакие дополнительные функциональные зависимости (т. е. зависимости, которые не обусловлены функциональными зависимостями множества S).

Таким образом, эти правила могут использоваться для получения замыкания S множества зависимостей S.

Вцелях упрощения нахождения S можно ввести дополнительные правила вывода (D Ď HR):

4.Правило самоопределения: A Ñ A.

5.Правило декомпозиции: если A Ñ B Y C, то A Ñ B и A Ñ C.

6.Правило объединения: если A Ñ B и A Ñ C, то A Ñ B Y C.

7.Правило композиции: если A Ñ B и C Ñ D, то A Y C Ñ B Y D.

8.Общая теорема объединения (Дарвен): если A Ñ B и C Ñ D, то A Y pCzBq Ñ B Y D.

Замыкание S для заданного множества функциональных зависимостей S можно вычислить тривиальным образом: повторно применять правила вывода до тех пор, пока остается возможным создание новых функциональных зависимостей.

Неприводимые множества зависимостей

Пусть S1 и S2 — два множества функциональных зависимостей.

Определение 6. Множество S2 называется покрытием для множества S1, если любая функциональная зависимость, которая следует из множества зависимостей S1, следует также из множества зависимостей S2, т. е. S1 Ď S2 .

Замечание. Это означает, что если СУБД обеспечит соблюдение ограничений, представленных зависимостями множества S2, то автоматически будут соблюдены и все ограничения, устанавливаемые зависимостями множества S1.

Определение 7. Множества зависимостей S1 и S2 называются эквивалентными, если S1 является покрытием для S2 и S2 является покрытием для S1, т. е. S1 S2 .

Определение 8. Множество функциональных зависимостей S называется неприводимым (минимальным) тогда и только тогда, когда оно обладает всеми тремя свойствами:

1.Зависимая часть каждой функциональной зависимости из S содержит только один атрибут.

2.Детерминант каждой зависимости из S является неприводимым, т. е. ни один атрибут из де-

терминанта не может быть опущен без изменения замыкания S 1 (т. е. без преобразования S

в неэквивалентное множество зависимостей).

3.Ни одна функциональная зависимость из множества S не может быть удалена без изменения его замыкания S (т. е. без преобразования множества S в неэквивалентное множество зависимостей).

1 Такая функциональная зависимость называется неприводимой слева.

38

Иначе называется приводимым.

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

Доказательство: Пусть дано исходное множество зависимостей S.

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

2.Далее для каждой зависимости f P S следует проверить каждый атрибут a в детерминанте зависимости f: если удаление атрибута a из левой части зависимости f не приводит к изменению замыкания S , то этот атрибут следует удалить.

3.Затем для каждой зависимости f, оставшейся в множестве S, необходимо проверить, приводит ли ее удаление из множества S к изменению замыкания S : в случае отрицательного ответа следует удалить зависимость f из множества S.

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

Определение 9. Множество функциональных зависимостей T, которое неприводимо и эквивалентно другому множеству функциональных зависимостей S, называется неприводимым эквивалентом множества S.

Таким образом, в системе вместо исходного множества функциональных зависимостей S может использоваться его неприводимый эквивалент T. Однако для заданного множества функциональных зависимостей не всегда существует уникальный неприводимый эквивалент.

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

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

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

операция соединения, что показывается теоремой Хита:

Теорема (Хит; Heath). Пусть задана переменная отношения R с заголовком HR A Y B Y C, где A; B; C — попарно непересекающиеся множества атрибутов переменной отношения R. Если R удовлетворяет функциональной зависимости A Ñ B, то можно провести декомпозицию без потерь в виде

R1 AYBpRq; R2 AYCpRq;

которая обратима с помощью естественного соединения: R R1 ' R2.

В качестве следствия-обобщения можно (неформально) отметить, что декомпозиция переменной отношения R на проекции Rl; R2; : : : ; Rn выполняется без потерь, если R Rl ' R2 ' : : : ' Rn.

Диаграммы функциональных зависимостей

Пусть R — переменная отношения, а T — неприводимое множество его функциональных зависимостей. Множество T можно визуально представить в виде диаграммы функциональных зависимо-

стей:

•Каждый атрибут изображается прямоугольником с именем атрибута в нем.

•Каждое множество атрибутов изображается в виде прямоугольника, внутри которого находятся прямоугольники-атрибуты, которые входят в множество атрибутов.

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

39