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

1. Р# { PNME, COLOR } Р# WEIGHT

Р# CITY

(Правая часть первой ФЗ не является одноэлементным множеством.)

2. ( Р#, PNME ) COLOR Р# PNME

Р# -> WEIGHT Р# CITY

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

3. Р# -> Р#

Р# -> PNAME Р# COLOR Р# WEIGHT

Р# -> С1ТУ(Здесь первую ФЗ можно опустить без изменения замыкания.)

Теперь можно сделать утверждение, что для любого множества функциональных зависимостей существует по крайней мере одно эквивалентное множество, которое является неприводимым. Это достаточно легко продемонстрировать на следующем примере. Пусть дано исходное множество зависимостей S. Тогда благодаря правилу декомпозиции можно без утраты общности предположить, что каждая функциональная зависимость в этом множестве S имеет одноэлементную правую часть. Далее для каждой зависимости f из этого множества S следует проверить каждый атрибут А в левой части зависимости f. Если множество S и множество зависимостей, полученное в результате устранения атрибута А в левой части зависимости f, эквивалентны, значит, этот атрибут следует удалить. Затем для каждой оставшейся в множестве S зависимости f, если множества S и S - f эквивалентны, следует удалить зависимость f из множества S. Получившееся в результате таких действий множество S является неприводимым и эквивалентно исходному множеству S.

Пример. Пусть дана переменная-отношение R с атрибутами А, В, С, D и следующими функциональными зависимостями.

А -> ВС В С А В АВ -> С АС -> D

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

1. Прежде всего следует переписать заданные ФЗ таким образом, чтобы каждая из них имела одноэлементную правую часть.

А -> В А С В С А В АВ С АС D

Нетрудно заметить, что зависимость А В записана дважды, так что одну из них можно удалить.

2. Затем в левой части зависимости АС D может быть опущен атрибут С, поскольку дана зависимость А С, из которой по правилу дополнения можно получить зависимость А -> АС. Кроме того, дана зависимость АС D, из которой по правилу транзитивности можно получить зависимость А D. Таким образом, атрибут С в левой части исходной зависимости АС D является избыточным.

3. Далее можно заметить, что зависимость АВ -> С может быть исключена, поскольку дана зависимость А С, из которой по правилу дополнения можно получить зависимость АВ -> СВ, а затем по правилу декомпозиции - зависимость АВ С.

4. Наконец зависимость А С подразумевается зависимостями А -> В и В С, так что она также может быть отброшена. В результате мы получили неприводимое множество зависимостей.

А В В С А -> D

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

10.7. Резюме

Функциональная зависимость - это связь типа многие к одному между двумя множествами атрибутов заданной переменной-отнощения. Для заданной переменной-отнощения R зависимость А -> В (где А и В являются подмножествами множества атрибутов переменной-отнощения R) выполняется для переменной-отнощения R тогда и только тогда, когда любые два кортежа переменной-отнощения R с одинаковыми значениями атрибутов множества А имеют одинаковые значения атрибутов множества В.

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

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

Для данного подмножества Z множества атрибутов переменной-отношения R и множества функциональных зависимостей S, которые выполняются в переменной-отношении R, замыканием подмножества Z для множества S называется такое множество всех атрибутов А переменной-отношения R, что функциональная зависимость Z -> А является членом замыкания S. Если замыкание Z состоит из всех атрибутов переменной-отношения R, то подмножество Z называют суперключом переменной-отношения R (а неприводимый суперключ, в свою очередь, называется потенциальным ключом). В этой главе было дано описание простого алгоритма для получения замыкания Z на основе Z и S и, следовательно, для определения, является ли данная зависимость X -> Y членом замыкания (функциональная зависимость X Y является членом замыкания тогда и только тогда, когда множество Y является подмножеством замыкания Х).

Два множества функциональных зависимостей S1 и S2 эквивалентны тогда и только тогда, когда они являются покрытиями друг для друга, т.е. Sl=S2. Каждое множество функциональных зависимостей эквивалентно по крайней мере одному неприводимому множеству. Множество функциональных зависимостей является неприводимым, если, во-первых, каждая функциональная зависимость этого множества имеет одноэлементную правую часть; во-вторых, если ни одна функциональная зависимость множества не может быть устранена без изменения замыкания этого множества; в-третьих, если ни один атрибут не может быть устранен из левой части любой функциональной зависимости данного множества без изменения замыкания множества. Если I является неприводимым множеством, которое эквивалентно множеству S, то проверка выполнения функциональных зависимостей из множества I автоматически обеспечит выполнение всех функциональных зависимостей из множества S.

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

Некоторые офаничения целостности являются тривиальными,

Одни Офаничения целостности подразумевают другие офаничения.

Множество всех офаничений, подразумеваемых заданным множеством, может рассматриваться как замыкание этого заданного множества.