Misplaced Pages

Canonical cover

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

A canonical cover F c {\displaystyle F_{c}} for F (a set of functional dependencies on a relation scheme) is a set of dependencies such that F logically implies all dependencies in F c {\displaystyle F_{c}} , and F c {\displaystyle F_{c}} logically implies all dependencies in F.

The set F c {\displaystyle F_{c}} has two important properties:

  1. No functional dependency in F c {\displaystyle F_{c}} contains an extraneous attribute.
  2. Each left side of a functional dependency in F c {\displaystyle F_{c}} is unique. That is, there are no two dependencies a b {\displaystyle a\to b} and c d {\displaystyle c\to d} in F c {\displaystyle F_{c}} such that a = c {\displaystyle a=c} .

A canonical cover is not unique for a given set of functional dependencies, therefore one set F can have multiple covers F c {\displaystyle F_{c}} .

Algorithm for computing a canonical cover

  1. F c = F {\displaystyle F_{c}=F}
  2. Repeat:
    1. Use the union rule to replace any dependencies in F c {\displaystyle F_{c}} of the form a b {\displaystyle a\to b} and a d {\displaystyle a\to d} with a b d {\displaystyle a\to bd} .
    2. Find a functional dependency in F c {\displaystyle F_{c}} with an extraneous attribute and delete it from F c {\displaystyle F_{c}}
  3. ... until F c {\displaystyle F_{c}} does not change

Canonical cover example

In the following example, Fc is the canonical cover of F.

Given the following, we can find the canonical cover: R = (A, B, C, G, H, I), F = {A→BC, B→C, A→B, AB→C}

  1. {A→BC, B→C, A→B, AB→C}
  2. {A → BC, B →C, AB → C}
  3. {A → BC, B → C}
  4. {A → B, B →C}

Fc =  {A → B, B →C}

Extraneous attributes

An attribute is extraneous in a functional dependency if its removal from that functional dependency does not alter the closure of any attributes.

Extraneous determinant attributes

Given a set of functional dependencies F {\displaystyle F} and a functional dependency A B {\displaystyle A\rightarrow B} in F {\displaystyle F} , the attribute a {\displaystyle a} is extraneous in A {\displaystyle A} if a A {\displaystyle a\subset A} and any of the functional dependencies in ( F ( A B ) ( A a ) B ) {\displaystyle (F-(A\rightarrow B)\cup {(A-a)\rightarrow B})} can be implied by F {\displaystyle F} using Armstrong's Axioms.

Using an alternate method, given the set of functional dependencies F {\displaystyle F} , and a functional dependency X → A in F {\displaystyle F} , attribute Y is extraneous in X if Y X {\displaystyle Y\subseteq X} , and ( X Y ) + A {\displaystyle (X-Y)^{+}\supseteq A} .

For example:

  • If F = {A → C, AB → C}, B is extraneous in AB → C because A → C can be inferred even after deleting B. This is true because if A functionally determines C, then AB also functionally determines C.
  • If F = {A → D, D → C, AB → C}, B is extraneous in AB → C because {A → D, D → C, AB → C} logically implies A → C.

Extraneous dependent attributes

Given a set of functional dependencies F {\displaystyle F} and a functional dependency A B {\displaystyle A\rightarrow B} in F {\displaystyle F} , the attribute a {\displaystyle a} is extraneous in A {\displaystyle A} if a A {\displaystyle a\subset A} and any of the functional dependencies in ( F ( A B ) { A ( B a ) } ) {\displaystyle (F-(A\rightarrow B)\cup \{A\rightarrow (B-a)\})} can be implied by F {\displaystyle F} using Armstrong's axioms.

A dependent attribute of a functional dependency is extraneous if we can remove it without changing the closure of the set of determinant attributes in that functional dependency.

For example:

  • If F = {A → C, AB → CD}, C is extraneous in AB → CD because AB → C can be inferred even after deleting C.
  • If F = {A → BC, B → C}, C is extraneous in A → BC because A → C can be inferred even after deleting C.

References

  1. Silberschatz, Abraham (2011). Database system concepts (PDF) (Sixth ed.). New York: McGraw-Hill. ISBN 978-0073523323. Archived from the original (PDF) on 2020-11-08.
  2. ^ Elmasri, Ramez (2016). Fundamentals of database systems. Sham Navathe (Seventh ed.). Hoboken, NJ: Pearson. ISBN 978-0-13-397077-7. OCLC 913842106.
  3. ^ K, Saravanakumar; asamy. "How to find extraneous attribute? An example". Retrieved 2023-03-14.
Categories: