in Databases edited by
14,096 views
39 votes
39 votes

Relation $R$ has eight attributes $\text{ABCDEFGH}$. Fields of $R$ contain only atomic values. $F$=

$\text{{CH→G, A→BC, B→CFH, E→A, F→EG}}$ is a set of functional dependencies $(FDs)$ so that $F^+$ is exactly the set of $FDs$ that hold for $R$.

How many candidate keys does the relation $R$ have?

  1. $3$
  2. $4$
  3. $5$
  4. $6$
in Databases edited by
by
14.1k views

4 Comments

building a dependency graph helps
0
0

how to make one in this case?

0
0

@Pranavpurkar

Create a node for each of the eight attributes. (here i excluded $D$ as can be added later,

 we can see that $D$ is not part of any $FD′s$) Each directed edge indicates a $FD$, for example $B→CFH$,

by this we can easily find out $CKs$.

2
2

3 Answers

40 votes
40 votes
Best answer

Here, we can see that $D$ is not part of any $FD's$, hence $D$ must be part of the candidate key.

Now $D^{+}$=$\left \{ D \right \}$.

Hence, we have to add A$,B,C,E,F,G,H$ to $D$ and check which of them are Candidate keys of size $2$.

We can proceed as:

AD+= {A,B,C,D,E,F,G,H}

Similarly we see BD+ , ED+ and FD+ also gives us all the attributes. Hence, AD,BD,ED,FD are definitely the candidate keys.

But CD+, GD+ and HD+ doesnnt give all the attributes hence, $CD,GD$ and $HD$ are not candidate keys.

Now we need to check the candidate keys of size $3$. Since $AD, BD, ED, FD$ are all candidate keys hence we can't find candidate keys by adding elements to them as they will give us superkeys as they are already minimal. Hence, we have to proceed with $CD$, $GD$ and $HD.$

 Also, we can't add any of ${A,B,E,F}$ to $CD$, $GD$, $HD$ as they will again give us superset of ${AD,BD,ED,FD}$. 

Hence, we can only add among ${C,G,H}$ to $CD, GD, HD.$

Adding $C$ to $GD$ and $HD$ we get $GCD$, $HCD$. Taking closure and we will see they are not candidate keys.

Adding H to GD we get GHD which is also not a candidate key.(no more options with $3$ attributes possible)

Now we need to check for candidate keys with $4$ attributes. Since, only remaining options are $CGH$ and we have to add $D$ only possible key of size $4$ is $CGHD$ whose closure also doesn't give us all of the attributes in the relation (All possible options covered)

Hence, no of candidate keys are $4$ : AD,BD,ED,FD.

Correct Answer: $B$

edited by

2 Comments

Indranil Maji There is a typo in the last line

Hence no of candidate keys are 4 : AD,BD,ED,HD.

It should be

Hence no of candidate keys are 4 : AD,BD,ED,FD.

2
2
Thank You so much , made the changes :)
0
0
22 votes
22 votes

54) B.

4 candidate keys namely DA,DB,DE,DF.

4 Comments

F={CH→G, A→BC, B→CFH, E→A, F→EG}

let's check it for DB and DF one by one.

B→CFH,  reachable C ,F and H.

F→EG     reachable E,G

E→A       reachable A

A→BC    reachable B and C

covered- ABCDEFGH.

HOPE IT HELPS!

you can try for DF on your own.

1
1

yes, 4 candidate keys are there.
But finding the answer is not as simple as it seems.

After finding it out by taking 2 attributes each, we have to again check with 3 and 4 attributes..... which are not supersets.

Though in this question, they do not make any difference, it is important to check.

4
4
That’s true, we really can’t be sure very soon :( Easy but time-consuming.
0
0
15 votes
15 votes

Here if we observe all the FD's none of them are determining attribute D 

So the Candidate key must contain D as their attribute 

Futher all the combinations of the attributes with D can be checked and DA,DB,DE,DF are candidate key here and DC.DG,DH does not determine all the attributes therefore they are not CK's 

Totally 4 CK's possible 

Answer:

Related questions