database - Minimal cover of functional dependency -
i having trouble textbook question
consider set of functional dependencies f = { → b, b → c, cd → a, ac → d }
compute minimal cover of f.
am trying follow simple steps so. first can see there no right hand singleton do. possible single out cd , ac on left hand side? have to?
this attempt @ it, not following steps approach. correct?
f = { a→ b, b→c, cd→a, ac → d} => f = { → c, cd → a, ac → d} => f = { cd → c, ac → d} => f = { d→ c, ac → d} => f = {ac → c} => f = {a->c}
if understand notation, minimal cover contains a→c
, not cover of starting f
, since many dependencies in f
cannot derived single dependency a→c
. example, how derive a→b
from a→c
? in minimal cover “simplify” set of functional dependencies without loosing information.
so, let's start beginning , see how 1 should proceed obtain minimal cover.
first should rewrite dependencies more 1 attribute on right hand and, note, not necessary.
then, each dependence has more 1 attribute on left, should see if of them can eliminated. there 2 cases, cd→a
, ac→d
. check performed in way. attribute can eliminated if closure of other attribute respect f
include right hand. have calculate both c+ , d+ first dependence, , a+ , c+ second one.
c⁺ = {c} d⁺ = {d}
both closure not contain a
, dependence cd→a
must maintained.
a⁺ = {a, b, c, d} c⁺ = {c}
since closure of attribute a
contains d
, c
can eliminated left hand, , new set of dependencies is:
f' = {a→b, b→c, cd→a, a→d}
at point need check if functional dependence can eliminated, calculating closure of left part respect other dependencies, , see if closure contains right hand part.
a⁺ = ad b⁺ = b cd⁺ = cd a⁺ = abc
in no case closure contains right hand, minimal cover of f
f'
.
Comments
Post a Comment