database-designrelational-databasedatabase-schemafunctional-dependenciescanonical-form

What is canonical cover, closure and extraneous attribute?


I'm studying database concepts and there are 3 concepts that I don't understand: canonical cover, extraneous attribute and closure. I read the definition about canonical cover but I don't get the picture of how it relates to 3NF and BCNF. The definition of canonical cover appears to be that there are no extraneous attributes and extraneous attributes are attributes that don't change the closure of the set of functional dependencies and closure is the set of all functional dependencies implied by F, a set of functional dependencies.

But all this is a little fuzzy and I'd like to know both an intuitive definition and how to calculate

  • Canonical cover
  • Closure
  • Extraneous attribute

Functional dependency I believe I understand--it's like what would have been the PK in a table if we had those attributes in a table.

There is a rather extensive answer at database refinement - minimal cover of F (extraneous attributes) but I found it difficult to read all the set definitions and algebra and I'd rather have definitions in plain English.

For example, having the schema U={A,B,C,D,E,F,G} and the functional dependencies

AB → C
B → E
CF → D
C → A
B → F
CE → F
CD → B
B → C

Are the closures A+,B+,C+,D+,E+,F+ calculated this way?

A+ = A
B+ = BCDEF
C+ = A
D+ = D
E+ = E
F+ = F

If I'm not mistaken then BCDEFG is a superkey (”the whole key”) in 1NF/2NF but is it minimal (3NF)?

What else should be done to normalize this example to 1NF, 2NF and 3NF with the help of closures and canonical covers? Is canonical cover the same as minimal cover?


Solution

  • You made some mistakes:

    For the closures:

    • B+ should be ABCDEF rather than BCDEF because of the FD C → A
    • C+ should be AC (the closure of an attribute always contains itself)
    • G+ is G, see reason of the second bullet

    To calculate the canonical cover, follow this algorithm. You need to look at your list of functional dependencies:

    1. Left reduction: try to remove all attributes of the left side of the arrow that are not necessary to create the same closure. To make the first example, AB → C, you can calculate ABs closure, which would be ABCDEF. You then try to remove A, ending up with B → C. Now you calculate the closure of B only, which is still ABCDEF -> you can remove A. At the end of this step, your FD should look like {B → C, B → E, C F → D, C → A, B → F, C E → F, C D → B, B → C, G → G}.
    2. Now you make the same thing for the right hand side. Note that you can remove all attributes here if you want, ending up with the empty set. As an example, look at B → F: the closure of B is ABCDEF. If you remove the F from the functional dependency, ending up with B → ∅, you still got the same closure for B as before. Repeat that for the other FDs. You should end up with {B →∅, B → E, C F → D, C → A, B →∅, C E → F, C D → B, B → C, G →∅}.
    3. Remove all FDs of the form X → ∅. You end up with {B → E, C F → D, C → A, C E → F, C D → B, B → C}.
    4. Combine all FDs that have the same left-side of the arrow, which leads to a canonical cover of {B → C E, C F → D, C → A, C E → F, C D → B} .

    For the superkeys: see this SO answer