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

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

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

{S#, P#} ® S#

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

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

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

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

{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)

Дата добавления: 2015-05-09