Функциональные зависимости: тривиальные и нетривиальные зависимости; замыкание множества зависимостей; правила вывода Армстронга; неприводимое множество зависимостей |
Очевидным способом сокращения существующего набора функциональных зависимостей является исключение из него тривиальных зависимостей. Зависимость называется тривиальной, если она не может не выполняться. В качестве примера приведем следующую тривиальную функциональную зависимость, существующую в переменной отношения SCP, которая обсуждалась в предыдущем разделе. { S#, Р# } → S# Действительно, функциональная зависимость является тривиальной тогда и только тогда, когда правая часть ее символической записи является подмножеством (не обязательно строгим подмножеством) левой части. Как подразумевается в самом их названии, с практической точки зрения подобные зависимости не представляют значительного интереса, в отличие от нетривиальных зависимостей, которые действительно являются ограничениями целостности в полном смысле этого понятия. Однако с точки зрения формальной теории зависимостей необходимо учитывать все зависимости, как тривиальные, так и нетривиальные. Множество всех функциональных зависимостей, которые следуют из заданного множества функциональных зависимостей s, называется замыканием множества s и обозначается символом S+ (необходимо учитывать то, что оно не имеет ничего общего с понятием замыкания, которое рассматривается в реляционной алгебре). Из приведенного определения следует, что для решения сформулированной задачи необходимо найти алгоритм вычисления S+ на основе S. Первая попытка решить эту проблему была предпринята в статье Армстронга (Armstrong) [11.2], в которой автор предложил набор правил вывода новых функциональных зависимостей на основе заданных (эти правила также часто называют аксиомами Армстронга).Эти правила вывода могут формулироваться разными способами, из которых самым простым является следующий. Пусть А,ви С — произвольные подмножества множества атрибутов заданной переменной отношения R. Условимся также, что символическая запись АВ означает объединение множеств А И В. Тогда правила вывода определяются следующим образом. 1. Правило рефлексивности. Если множествовявляется подмножеством множества А, ТО А → В. 2. Правило дополнения. Если А → B, то АС → ВС. 3. Правило транзитивности. Если А → B и B→C, то А → С. Каждое из этих трех правил может быть непосредственно доказано на основе определения функциональной зависимости (безусловно, первое из них — это просто само определение тривиальной зависимости). Более того, эти правила являются полными в том смысле, что для заданного множества функциональных зависимостей s минимальный набор функциональных зависимостей, которые подразумевают все зависимости из множества S, может быть выведен из ФЗ множества s на основе только этих правил. Они являются также непротиворечивыми, поскольку с их помощью не могут быть выведены никакие дополнительные функциональные зависимости (т.е. зависимости, которые не обусловлены функциональными зависимостями множества S). Иначе говоря, эти правила могут использоваться для получения замыкания S+. В целях упрощения задачи практического вычисления замыкания S+, из трех приведенных выше правил можно вывести несколько дополнительных правил. (В дальнейшем предполагается, что D — это еще одно произвольное подмножество множества атрибутов R.) 4. Правило самоопределения. А → А. 5. Правило декомпозиции. Если А → ВС, то А → Bи A → C. 6. Правило объединения. Если А → В И А → С, то А → ВС. 7. Правило композиции. Если А → B и С → D, то АС → BD. Кроме того, Дарвен (Darwen) в своей работе [11.7] доказал следующее правило, которое он назвалобщей теоремой объединения. 8. Если А→ B и C → D, то А ∪ ( С В ) → BD (здесь символ " ∪ " обозначает операцию объединения множеств, а символ "-" — операцию разности множеств). Множество функциональных зависимостей называется неприводимым тогда и только тогда, когда оно обладает всеми тремя перечисленными ниже свойствами:
множества S содержит только один атрибут (т.е. является одноэлементным множеством). множества S, в свою очередь, является неприводимой, т.е. ни один атрибут из детерминанта не может быть опущен без изменения замыкания S+ (без преобразования множества S в какое-то другое множество, не эквивалентное множеству S). В этом случае функциональная зависимость называется неприводимой слева. удалена из множества s без изменения его замыкания S+ (т.е. без преобразования множества s в некоторое иное множество, не эквивалентное множеству S). |