Canonical cover

A canonical cover $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}$ , and $F_{c}$ logically implies all dependencies in F.

The set $F_{c}$ has two important properties:

No functional dependency in $F_{c}$ contains an extraneous attribute.
Each left side of a functional dependency in $F_{c}$ is unique. That is, there are no two dependencies $a\to b$ and $c\to d$ in $F_{c}$ such that $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}$ .

Algorithm for computing a canonical cover

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

[1]

Canonical cover example

In the following example, F_c 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}

{A→BC, B→C, A→B, AB→C}
{A → BC, B →C, AB → C}
{A → BC, B → C}
{A → B, B →C}

F_c = {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.[2]

Extraneous Determinant Attributes

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

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

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$ and a functional dependency $A\rightarrow B$ in $F$ , the attribute $a$ is extraneous in $A$ if $a\subset A$ and any of the functional dependencies in $(F-(A\rightarrow B)\cup \{A\rightarrow (B-a)\})$ can be implied by $F$ using Armstrong's Axioms.[3]

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.[2]

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

Silberschatz, Abraham (2011). Database system concepts (PDF) (Sixth ed.). New York: McGraw-Hill. ISBN 978-0073523323.
Elmasri, Ramez (2016). Fundamentals of database systems. Sham Navathe (Seventh ed.). Hoboken, NJ. ISBN 978-0-13-397077-7. OCLC 913842106.{{cite book}}: CS1 maint: location missing publisher (link)
K, Saravanakumar; asamy. "How to find extraneous attribute? An example". Retrieved 2023-03-14.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Silberschatz, Abraham (2011). Database system concepts (PDF) (Sixth ed.). New York: McGraw-Hill. ISBN 978-0073523323.

[:1-2] Elmasri, Ramez (2016). Fundamentals of database systems. Sham Navathe (Seventh ed.). Hoboken, NJ. ISBN 978-0-13-397077-7. OCLC 913842106.{{cite book}}: CS1 maint: location missing publisher (link)

[:0-3] K, Saravanakumar; asamy. "How to find extraneous attribute? An example". Retrieved 2023-03-14.