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

Question

Fd1 = {AB -> C, D -> E, E -> C}

Fd2 = {AB -> C, D -> E, AB -> E, E -> C}

эти два FD эквивалентны или нет, я думаю, что они. Но в ответе он показан как не эквивалентный.

Answer 1

Вы не можете создать AB → E из зависимостей в первом наборе.

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

Есть несколько простых правил индукции для построения замыкания. Цитируя Википедию о функциональной зависимости, аксиомы таковы:

• Рефлексивность: если Y является подмножеством X, то X → Y
• Увеличение: если X → Y, то XZ → YZ
• Транзитивность: если X → Y и Y → Z, то X → Z

с несколькими правилами, которые следуют из них:

• Объединение: если X → Y и X → Z, то X → YZ
• Разложение: если X → YZ, то X → Y и X → Z
• Псевдотранзитивность: если X → Y и WY → Z, то WX → Z
• Состав: если X → Y и Z → W, то XZ → YW

Используя эти правила и аксиомы, можно построить замыкание для FDS.

Опуская тривиальные зависимости (те, в которых правая часть входит в левую часть), первый набор {AB → C (1), D → E (2), E → C (3) } дает:

AB → C                       (1)
ABD → CE, ABD → C, ABD → E   (composition 1+2, decomposition)
ABDE → CE, ABDE → C          (composition 1+2+3, decomposition)
ABE → C                      (composition 1+3)
D → E, D → C, D → CE         (2, transitivity 2+3, union)
DE → CE, DE → C              (composition 2+3, decomposition)
E → C                        (3)

И второе множество {AB → C (1), D → E (2), E → C (3), AB → E (4) } дает:

AB → C, AB → E, AB → CE      (1, 4, union 1+4)
ABD → CE, ABD → C, ABD → E   (composition 1+2, decomposition)
ABDE → CE, ABDE → C          (composition 1+2+3, decomposition)
ABE → C                      (composition 1+3)
D → E, D → C, D → CE         (2, transitivity 2+3, union)
DE → CE, DE → C              (composition 2+3, decomposition)
E → C                        (3)

Второе закрытие имеет AB → E, AB → CE, чего нет в первом замыкании, поэтому оригинальные наборы разные.