Действительно, если переменная-отношение R удовлетворяет функциональной зависимости А -> В и А we является потенциальным ключом, то R будет характеризоваться некоторой избыточностью. Например, если обратиться к переменной-отношению SCP, наличие в ней функциональной зависимости S# CITY приведет к тому, что сведения о месте расположения поставщика в определенном городе повторятся много раз (это хорошо видно на рис. 10.1). Подробнее данный вопрос обсуждается в следующей главе.

Теперь, даже если ограничиться рассмотрением функциональных зависимостей, которые имеют место в любой момент, полный набор функциональных зависимостей, выполняющихся для всех допустимых значений заданной переменной-отношения, может быть все еще очень большим, что можно видеть на примере переменной-отношения SCP. {Упражнение. Попробуйте записать полное множество функциональных зависимостей, существующих в переменной-отношении SCP.) Большая часть оставшегося в этой главе материала посвящена поискам методов сокращения обширного множества функциональных зависимостей до некоторых допустимых размеров.

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

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

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

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

{ S#, Р# } S#

Эта функциональная зависимость не является тривиальной (раздел 10.3), причем А не является суперключом (раздел 10.5), а R содер.жит по крайней мере два корте.жа.

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

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

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

Как упоминалось выше, одни функциональные зависимости могут подразумевать другие функциональные зависимости. Например, рассмотрим приведенную ниже зависимость.

{ S#, Р# } { CITY, QTY }

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

{ S#, Р# } CITY { S#, Р# } QTY

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

Множество всех функциональных зависимостей, которые подразумеваются заданным множеством функциональных зависимостей S, называется замыканием множества S и обозначается символом Из приведенного определения следует, что для решения сформулированной задачи необходимо найти способ вычисления на основе S. Первая попытка решить эту проблему была предпринята в статье Армстронга (Armstrong) [10.1], в которой автор предложил набор правил вывода новых функциональных зависимостей на основе заданных (эти правила также называются аксиомами Армстронга). Правила вывода могут формулироваться разными способами, и самым простым из них является следующий. Пусть А, В и С - произвольные подмножества множества атрибутов заданной переменной-отношения R. Условимся также, что символическая запись АВ означает объединение множеств А и В. Тогда правила вывода определяются следующим образом.

1. Правило рефлексивности: если множество В является подмножеством множества А, то А В.

2. Правило дополнения: если А В, то АС ВС.

3. Правило транзитивности: если А В и В С, то А С.

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

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

С целью упрощения задачи практического вычисления замыкания из трех приведенных выше правил можно вывести несколько дополнительных правил. (Примем, что D - это другое произвольное подмножество множества атрибутов R.)

4. Правило самоопределения: А -> А.

5. Правило декомпозиции: если А ВС, то А ВиА -> С.

6. Правило объединения: если А -> В и А С, то А -> ВС.

7. Правило композиции: если А -> В и С -> D, то АС BD.

Кроме того, Дарвен (Darwen) в своей работе [10.6] доказал следующее правило, которое называется общей теоремой объединения.

8. Если А-ВиС-D, ToAu (С - В) -BD (здесь символ и обозначает операцию объединения множеств, а символ - - операцию разности множеств).

Название общая теорема объединения указывает на то, что некоторые из перечисленных выше правил могут быть выведены как частные случаи этой теоремы [10.6].

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

А ВС В Е CD EF

Обратите внимание, что способ записи несколько изменился (без ущерба для смысла); например, символы ВС означают множество, состоящее из атрибутов В и С, хотя ранее они означали объединение В и С, где В и С были множествами атрибутов.

Замечание. Если необходимо, то этому примеру можно придать более конкретный смысл, а именно: А- личный номер сотрудника, В- номер отдела, С- личный номер руководителя (начальника) данного сотрудника, D - номер проекта, возглавляемого данным руководителем (уникальный для каждого отдельно взятого руководителя), Е - название отдела, F - доля времени, уделяемая данным руководителем заданному проекту.

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

1. А ВС (дано)

2. А -> С (следует из п. 1 согласно правилу декомпозиции)

3. AD -> CD (следует из п. 2 согласно правилу дополнения)