Эквивалентность множеств функциональных зависимостей

Понятие эквивалентности множеств функциональных зависимостей атрибутов часто используется при проектировании и анализе баз данных. Укажем хотя бы два случая, когда оно может использоваться [6].

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

Второй случай. Полученное множество функциональных зависимостей может по каким-то причинам не устраивать разработчика. Тогда следует перейти к другому, но эквивалентному множеству зависимостей, которое отвечало бы требованиям разработчика, иначе будет нарушена семантика базы данных. Именно этот случай мы имеем в алгоритме синтеза, который будет рассмотрен в разделе 2.2.

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

Пусть F и G - два множества функциональных зависимостей, заданных на одном и том же множестве атрибутов U.

Множества F и G называются эквивалентными (обозначается как F º G), если равны их замыкания, т.е. F⁺ = G⁺.

Чтобы проверить, являются ли два множества F и G эквивалентными, используют следующую процедуру [3], [6].

1. Для каждой зависимости (X ® Y) Î F проверяется ее принадлежность замыканию G⁺. Для этого используется факт выводимости одной зависимости из других (теорема 1 из раздела 1.4), а именно: вычисляется замыкание атрибутов X⁺ левой части зависимости по множеству G, и проверяется условие Y Í X⁺. Если оно выполняется, то (X ® Y) Î G⁺.

Если каждая зависимость из F удовлетворяет этому условию, то можно указать следующую цепочку вложений множеств:

F Í F⁺ Í G⁺.

2. Аналогично для каждой зависимости (P ® Q) Î G проверяется ее принадлежность F⁺. Если каждая зависимость из G удовлетворяет условию (P®Q) Î F⁺, то можно указать следующую цепочку вложений множеств:

G Í G⁺ Í F⁺.

Очевидно обе цепочки вложений могут одновременно выполняться только при условии F⁺ = G⁺, т.е. множества функциональных зависимостей F и G эквивалентны.

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

Как только найдется зависимость, для которой это условие не выполняется, то дальнейшая проверка не проводится, и делается вывод о неэквивалентности заданных множеств зависимостей.

Пример 19. Проверим эквивалентность множеств функциональных зависимостей

F = {A ® BC, A ® D, CD ® E } и G = {A ® BCE, A ® BD, CD ® E }.

Прежде чем решать вопрос об эквивалентности заданных множеств зависимостей, нужно проверить, на одном и том же множестве атрибутов заданы данные множества или нет. Легко увидеть, что множества F и G определены для одного и того же набора атрибутов U = ABCDE. Кроме того, зависимость CD ® E присутствует как в множестве F, так и в множестве G, поэтому из проверки может быть исключена.

Как было сказано выше, эквивалентность множеств зависимостей проверяется за два шага.

1. Для каждой зависимости (X ® Y) Î F проверяем ее принадлежность замыканию G⁺, то есть справедливость выражения (X ® Y) Î G⁺. Если это выражение справедливо, то исследуемая зависимость или содержится в G или выводится из G.

Для (A ® BC) Î F имеем A⁺_{(по G)} = ABCED и BC Ì A⁺. Поэтому
по факту выводимости (A ® BC) ÎG⁺.

Для (A ® D) Î F имеем A⁺_{(по G)} = ABCED и D Ì A⁺. Поэтому
(A ® D) Î G⁺.

2. Для каждой зависимости (P ® Q) Î G проверяем справедливость выражения (P ® Q) Î F⁺.

Для (A ® BCE) Î G имеем A⁺_{(по F)} = ABCDE и BCE Ì A⁺. Поэтому
(A ® BCE) Î F⁺.

Нетрудно проверить, что зависимость A ® BD также принадлежит замыканию F⁺. Следовательно, F⁺ = G⁺ и множества F и G эквивалентны.

Пример 20. Проверим эквивалентность множеств функциональных зависимостей

F = {A ® BC, A ® D, CD ® E} и G = {A ® BE, A ® B, C ® ED}.

Убеждаемся, что множества зависимостей заданы на одном и том же множестве атрибутов U = ABCDE. Делаем первый шаг.

1. Для каждой зависимости (X ® Y) Î F проверяем ее принадлежность замыканию G⁺, то есть справедливость выражения (X ® Y) Î G⁺.

Для (A ® BC) Î F имеем A⁺_{(по G)} = ABE и BC ⊈ A⁺. Поэтому (A ® BC) Ï G⁺. Следовательно, дальнейшую проверку делать не надо, а сразу делаем вывод о неэквивалентности заданных множеств функциональных зависимостей.

Понятие эквивалентности множеств функциональных зависимостей дает возможность замены исходного множества F другим, эквивалентным ему множеством зависимостей G без искажения семантики данных.