минимальное покрытие для функциональных зависимостей

Question

У меня есть следующая проблема:

AB -> CD 
H->B 
G ->DA 
CD-> EF 
A -> HJ 
J>G 

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

AB -> C 
AB -> D 
H -> B 
G -> D 
G -> A 
CD -> E 
CD -> F 
A -> H 
A -> J 
J -> G 

Я понимаю, что А -> ч и ч -> Ь, следовательно, можно удалить в из AB -> с и AB -> D, чтобы получить:

A -> C 
A -> D 
H -> B 
G -> D 
G -> A 
CD -> E 
CD -> F 
A -> H 
A -> J 
J -> G 

шаг, который Fo llows - это то, что я не могу вычислить (уменьшить левую сторону)

Любая помощь будет принята с благодарностью.

Answer 1

Вы уже уменьшили левую сторону каждого FD в крышке. Следующим шагом является сокращение числа FD в этой обложке до минимума.

ли это, игнорируя один FD на время, а затем увидеть, если вы можете придумать и тот же набор зависимых атрибутов (закрытия) с помощью других FD-й в крышке с помощью LHS игнорируемых FD в качестве отправного точка. Если вы можете, то игнорируемый вами FD является избыточным и может быть сброшен с крышки. Сделайте это для каждого оставшегося FD. Осталось минимальное покрытие.

Сначала, используя все FD в исходной крышке, вы получите набор атрибутов , определяемый LHS FD, который вы проигнорируете. Для A закрытия является:

A, B, C, D, E, F, G, H, J 

Try remvoving A -> D и пересчитывать закрытие ...

initial closure: A 
use A -> C closure: A, C 
use A -> H closure: A, C, H 
use A -> J closure: A, C, H, J 
use J -> D closure: A, C, D, H, J 
use J -> G closure: A, C, D, G, H, J 
use H -> B closure: A, B, C, D, G, H, J 
use CD -> E closure: A, B, C, D, E, G, H, J 
use CD -> F closure: A, B, C, D, E, F, G, H, J 

можно получить тот же набор атрибутов никогда не ссылается на FD A -> D так этот ФО является избыточным и может быть сброшен с крышки. Фактически мы могли бы остановить процесс после того, как D появился в производном наборе атрибутов, но для завершения процесс был продолжен, чтобы доказать, что тот же набор атрибутов может быть достигнут с A -> D.

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