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→bfrom 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