Неприводимые множества зависимостей

Пусть S1 и S2 – два множества ФЗ. Если любая ФЗ, которая выводится из множества ФЗ S1, также выводится из множества ФЗ S2 (т.е. S1⁺ - подмножество S2⁺), то множество S2 называется покрытием множества S1. Это означает, что если СУБД поддерживает все ограничения целостности, представленных ФЗ S2, то она автоматически поддерживает и все ограничения целостности, представленные ФЗ S1.

Если множество S1 является покрытием для множества S2, а множество S2 одновременно является покрытием для множества S1 (S1⁺=S2⁺), то множества S1 и S2 называются эквивалентными.

Множество ФЗ S называется неприводимым тогда и только тогда, когда оно обладает всеми перечисленными ниже свойствами:

1. Зависимая часть каждой ФЗ из множества S содержит только один атрибут (т.е. является одноэлементным множеством).

2. Детерминант каждой ФЗ из множества S является неприводимым, т.е. ни один атрибут из детерминанта не может быть удален без изменения замыкания S⁺. В этом случае ФЗ называется неприводимой слева.

3. Ни одна ФЗ из множества S не может быть удалена без изменения его замыкания S⁺.

Для любого множества ФЗ существует, по крайней мере, одно эквивалентное множество ФЗ, которое является неприводимым. Это достаточно очевидное утверждение, истинность которого продемонстрируем на примере.

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

A ® BC

B ® C

A ® B

AB ® C

AC ® D

Найдем неприводимое множество ФЗ, эквивалентное данному множеству.

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

A ® B

A ® C

B ® C

AB ® C

AC ® D

2. Затем в детерминанте ФЗ AC ® D может быть опущен атрибут C, поскольку имеется зависимость A ® C, из которой по правилу дополнения можно получить зависимость A®AC. Кроме того, дана ФЗ AC ® D, из которой по правилу транзитивности можно получить ФЗ A ® D. Таким образом, атрибут C в детерминанте ФЗ AC ® D является избыточным.

3. Далее, ФЗ AB ® C может быть исключена, поскольку дана зависимость A ® C, из которой по правилу дополнения можно получить ФЗ AB ® CB, а затем по правилу декомпозиции – ФЗ AB ® C.

4. Наконец ФЗ A ® C подразумевается зависимостями A ® B и B ® C, а следовательно может быть отброшена. В результате получаем неприводимое множество ФЗ:

A ® B

B ® C

A ® D

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

11.Нормализация: формы 1НФ, 2НФ, 3НФ и НФБК

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