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

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

{S#, P#} ® S#

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

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

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

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

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

{S#, P#} ® {CITY, QTY}

Она подразумевает следующие ФЗ:

{S#, P#} ® CITY

{S#, P#} ® QTY

В качестве более сложного примера рассмотрим переменную-отношение R с атрибутами A, B, C, для которых выполняются ФЗ A  B и B  C. Нетрудно заметить, что в этом случае выполняется и ФЗ A  C, которая называется транзитивной ФЗ, т.е. C зависит от A транзитивно, через B.

Множество всех ФЗ, которые подразумеваются заданным множеством ФЗ S, называется замыканием множества S и обозначается символом S⁺.

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

Пусть A, B и C – произвольные подмножества множества атрибутов заданной переменной-отношения R. Условимся, что запись AB представляет объединение множеств A и B. Тогда правила определяются следующим образом.

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

2. Правило дополнения: если A  B, то AC  BC.

3. Правило транзитивности: если A  B и B  C, то A  C.

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

Для упрощения задачи практического вычисления замыкания S⁺ из трех приведенных выше правил выводимы следующие несколько дополнительных правил (здесь D – другое произвольное подмножество множества атрибутов переменной-отношения R):

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

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

6. Правило объединения: если A  B и A  С, то A  BC.

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

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

8. Если A  B и С  D, то A  (C - B) BD.

Пример 4.2. Пусть дана переменная-отношение R с атрибутами A, B, C, D, E, F и следующими ФЗ:

A  BC

B  E

CD  EF

Можно показать, что для переменной-отношения R выполняется ФЗ AD  F, которая вследствие этого принадлежит замыканию множества ФЗ.

1. A  BC (дано)

2. A  C (декомпозиция из п.1)

3. AD  CD (дополнение из п.2)

4. CD  EF (дано)

5. AD  EF (транзитивность из пп.3 и 4)

6. AD  F (декомпозиция из п.5)