Database extraneous attributes and decomposition

问题:

I am kind of confused on the notion of extraneous attributes and a proper decomposition into 3NF.

For example, I have the following relation:

r(A,B,C,D,E,F)

F = FD's
F = {A-> BCD, BC-> DE, B->D, D->A}

I want to compute the canonical cover in order to decompose it into 3NF using an algorithm. So I have to remove extraneous attributes from the FD's.

I computed A+. B+, C+, D+ (A+ = ABCDE, B+ = BD, C+ = C, D+ = AD) I started trying to find extraneous attributes. First I looked at attributes in β

I tried to find if D is extraneous in

BC -> DE

and using BC+ I found D is extraneous (Since BC+ contains the attribute D). So now my FD changed from BC -> DE to BC -> E Now I tried to compute extraneous attributes for α.

I looked to see if B or C is extraneous in FD BC -> DE (Computing B+ and C+ led me to neither B or C being extraneous since none of them contain E).

I also looked at extraneous attributed in A -> BCD and found both B and C to be extraneous (Since A+ contains all attributes). So I was left with following:

A -> D
BC -> E
B -> D
D -> A

Sorry for the extremely long question, I just wanted to write down what I did.

I am confused as to if this is correct or if I am even doing this correctly. I am trying to follow some notes and some online references but it would be nice if someone could point out if I am doing this right and if not try and explain somewhat as to properly find extraneous attributes and decomposing.

回答1:

Some of your closures are wrong (B+ = ABCDE, for instance due to B->D,D->A,A->BCD,BC->DE).

B and C are not extraneous in A->BCD. Indeed, the closure of A with respect to

{A -> D, BC -> E, B -> D, D -> A}

is AD rather than ABCDE.

So let us backtrack to your previous step:

{A-> BCD, BC-> E, B->D, D->A}

D is extraneous in A->BCD since A->B and B->D. We eliminate D from A-> BCD and obtain:

{A-> BC, BC-> E, B->D, D->A}

C is extraneous in BC->E. Indeed, B->D, D->A, A-> BC. Hence,

{A-> BC, B-> E, B->D, D->A}

Next we combine all fds with the same left-hand side:

{A-> BC, B-> DE, D-> A}

This set of functional dependencies does not contain redundant dependencies or extraneous attributes, and, hence, is a canonical cover.