Search code examples
databaserelational

Database Relational Homework help

The Problem "Consider a relation R with five attributes ABCDE. You are given the following dependancies

  1. A->B
  2. BC->E
  3. ED->A

List all the keys for R.

The teacher gave us the keys, Which are ACD,BCD,CDE

And we need to show the work to get to them.

The First two I solved.

For BCD, the transitive of 2 with 3 to get (BC->E)D->A => BCD->A. and for ACD id the the transitive of 1 with 4 (BCD), to get (A->B)CD->A => ACD->A

But I can't figure out how to get CDE.

So it seems I did it wrong, after googling I found this answer

  1. methodology to find keys: consider attribute sets α containing: a. the determinant attributes of F (i.e. A, BC, ED) and b. the attributes NOT contained in the determined ones (i.e. C,D). Then do the attribute closure algorithm: if α+ superset R then α -> R Three keys: CDE, ACD, BCD Source

From what I can tell, since C,D are not on the left side of the dependencies. The keys are left sides with CD pre-appended to them. Can anyone explain this to me in better detail as to why?

Solution

  • To get they keys, you start with one of the dependencies and using inference to extend the set.

    Let me have a go with simple English, you can find formal definition the net easily.

    e.g. start with 3).

    ED -> A

    (knowing E and D, I know A)

    ED ->AB

    (knowing E and D, I know A, by knowing A, I know B as well)

    ED->AB

    Still, C cannot be known, and I have used all the rules now except BC->E, So I add C to the left hand side, i.e.

    CDE ->AB

    so, by knowing C,D and E, you will know A and B as well, Hence CDE is a key for your relation ABCDE. You repeat the same process, starting with other rules until exhausted.