Question

There are the set of FD for a Relation R(A, B,C,D,E,F,G)
F= (A->B, BC->DE, AEF->G, AC->DE) Then
a) What are the Candidate keys for R? Justify your answer.
b) Is R in BCNF? Justify your answer.
c) Give a 3NF decomposition of this Relation.
d) Is your answer above is Lossless join and Dependency Preserving.?

Answer 1

R(A,B,C,D,E,F,G)

Candidate Keys of relation are minimal set of attributes that are uniquely identifying row in the relation.

Method to find candidate keys:

Finding closure: if closure contains all attributes present in the relation then it is candidate key.

This set should be minimal set.

Closure of attribute lists all attributes that are present in the right hand side of current attribute.

Funtional dependencies:

A->B

BC->DE

AEF->G

AC->DE

A closure={A,B} not all attributes listed in the set hence A only is not candidate key.

{ACF} closure =>{ A,C,F,G,B,D,E } all attributes listed in the set hence {ACF} is candidate key.

BDE closure => { B,D,E } not all attributes listed in the set.

Hence, ACF is the candidate key.

b)

Rule for BCNF:

Every functional dependency must have super key on left side.

Super key: set of attributes that are uniquely identifying row in the relation.

Method to find super keys:

Finding closure: if closure contains all attributes present in the relation then it is super key.

Closure of attribute lists all attributes that are present in the right hand side of current attribute.

Funtional dependencies:

A->B

A closure ={ A,B} hence not super key

BC->DE

BC closure ={ B,C } hence not super key

AEF->G

AEF closure ={A,E,F,G,B} hence not super key

AC->DE

AC closure={A,C,B,D,E} hence not super key

Hence, it is not BCNF

C)

3NF:

If a->b is Functional dependency then a and b should not be non-prime attributes. This is rule for 3NF

Candidate Keys of relation are minimal set of attributes that are uniquely identifying row in the relation.

In this set, each attribute is called prime attributes. Attributes which are not belongs to any candidate key are non-prime attributes.

Funtional dependencies:

Candidate key is { A,C,F }

A->B Since A is prime attribute, it is following 3NF

BC->DE it is not following

AEF->G it is not following

AC->DE it is following 3NF

Now 3 NF decomposition:

R(A,B,C,D,E,F,G)

BC->DE not following

Step 1:

Find closure of BC

BC closure={B,C,D,E}

Step 2:

Apart from BC,Extra attributes D,E should be eliminated from R(A,B,C,D,E,F,G)

And should form new relation as follows.

R(A,B,C,D,E,F,G)

Decomposed into

R1(A,B,C,F,G)

R2(B,C,D,E)

Again R1 table should be decomposed to new table as AEF->G it is not following

AEF closure={ A,B,E,F,G}

Apart from AEF, extra attributes B,G should be elimited from R1(A,B,C,F,G)

R(A,B,C,D,E,F,G)

Decomposed into

R1(A,C,F)

R2(B,C,D,E)

R3(A,B,E,F,G)

R3(A,B,E,F,G) no significance B here, hence while decomposition we can leave attribute in the R1 relation.

Finally R(A,B,C,D,E,F,G)

Decomposed into

R1(A,B,C,F)

R2(B,C,D,E)

R3(A,E,F,G)

D)

Lossless join:

Relation should have common attributes with atleast one relation and those attributes should be primary key for one of those relations. Then it is lossless join. Otherwise it is lossy.

R1 and R2 have common BC . BC is key for R2

R1 and R3 have common AEF. AEF is key for R3

Hence it is lossless

Dependency preserving: After decomposition, final relations should follow given functional dependencies.

R1(A,B,C,F) R2(B,C,D,E) R3(A,E,F,G)

A->B : it is followed by R1

BC->DE : it is followed by R2

AEF->G: it is followed by R3

AC->DE

A->B if we apply C on both sides, it becomes AC->BC

R2 follows BC->DE

By transitive law, if AC-> BC and BC->DE then AC->DE

Hence, all functional depencies are followed by decomposed relations. It is dependency preserving.