Determine Keys from Functional Dependencies

Question

I'm taking a database theory course, and it's not clear to me after doing the reading how I can infer keys, given a set of functional dependencies.

I have an example problem:

Find all keys of the relation R(ABCDEFG) with functional dependencies

AB → C
CD → E
EF → G
FG → E
DE → C
BC → A

Demonstrate your knowledge by identifying which of the following is a key.

a. BCDEF             
b. ADFG           
c. BDFG           
d. BCDE 

Can someone walk me through how I should decompose the functional dependencies to conclude that some combination of attributes is a key? I expect I'll face a number of these types of problems and I need to understand how to approach it.

Ventris

The video in yrazlik's answer actually uses the approach introduced in [1], if you are interested to know why it works. (The proofs are short and straightforward.) [1] H. Saiedian and T. Spencer, “An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema,” The Computer Journal, vol. 39, no. 2, Feb. 1996 [Online]. Available: pdfs.semanticscholar.org/ab3f/…. [Accessed: 31-Jul-2019] – Koan

@Koan The introduction to the bulleted algorithm you gave in some deleted answers similar to your deleted answer here is incorrect. The algorithm requires that F be a cover for the FDs that hold, not just be a set of FDs that hold. PS Please use text, not images/links, for text--including tables & ERDs. Paraphrase or quote from other text. Use images only for what cannot be expressed as text or to augment text. Images cannot be searched for or cut & pasted. Include a legend/key & explanation with an image. – Skyler

Answer 1

Take an FD, e.g. AB→C

Augment until all attributes are mentioned, e.g. ABDEFG → CDEFG (note that this is equivalent to ABDEFG → ABCDEFG because it is trivially true that A->A and B->B).

This tells you that ABDEFG is a superkey.

Check the other FDs in which the LHS is a subset of your superkey, and that on its RHS contains some other attribute of your superkey.

There are two. EF→G and FG→E. Remove the attributes of the RHS of these from your superkey. Doing so gives you two keys, that are certainly superkeys, but not necessarily irreducible ones: ABDEF and ABDFG.

However, from AB→C and CD→E we can also derive that ABD→E. Hence we can also remove the E from our ABDEF key. The nasty thing here is that when I said "Check the other FDs", that apparently means that you should also check any FD that appears in the closure of your set of FDs (i.e. any FD that is derivable from your given set of FDs)... And that's a bit impractical to do by hand ...

A useful site for verifying whether your results are correct:

http://raymondcho.net/RelationalDatabaseTools/

You should now be able to determine that option c is a key.

Tarpon

Isn't BDF the candidate key? Since DF->C, EF->G, CD->E we have G from BDF. – Facing

@NickRosencrantz: There are four candidate keys. BDF isn't one of them; they all happen to have four attributes. I don't follow your deductive logic at all; none of the FDs you mention contains B. – Dagmar

He mentioned DF->C but that one wasn't stated. Maybe he misread DE->C. – Tarpon

@ErwinSmout Could you go through step by step how you augment AB→ C to become ABDEFG → CDEFG? I don't really understand it. – Nullifidian

The augmentation rule says that if S1->S2 and S3->S4, then (S1 U S3) -> (S2 U S4). S1,S2,S3,S4 are sets, U is union. Simply apply to {AB}->{C} and the trivial {D}->{D} (and the others). – Tarpon

It's interesting that you updated your answer on the same day, four years later :) Besides that, nice explanation. – Trumaine

Answer 2

Well this should be rather straightforward. All you need to do is to take the closure of every key given and see if it contains all attributes of R. For example, closure of BCDEF = ABCDEFG since BC -> A and BC is a subset of BCDEF and so if EF for FD EF -> G. Since this closure contains all attributes of R, BCDEF is the key. The main aim of taking closures is to see if we can "reach" every attribute from a given set of attributes. The closure is the set of attributes that we can actually reach by navigating the FDs.

Republicanize

BCDEF isn't a candidate key, because it's reducible. (BC->E) But BCDF is one of the candidate keys. – Dagmar

Answer 3

Since you're in a db theory course, I'm going to assume you have SQL experience and try and relate the theory to the implementation context.

Basically, a relation is what you would refer to as a table in implementation and a key is ANY set of attributes (read columns) which can be used to identify a UNIQUE row (in db theory this would be a tuple). The simplest analogy here is that a key is your primary key, as well as any other possible set of columns you can use to identify a single tuple in your relation (row in your table). So, here are the basic steps for doing this (I'll walk through example A, and then you can try the rest):

1. List all of the attributes which are NOT in your proposed key (so BCDEF does not include A and G).

2. For each attribute you're missing, go through the list of functional dependencies and see if your proposed key is capable of inferring the attribute you're missing.

                a. So for A, you have BC -> A.  Since both B and C are in the proposed
                   key BCDEF, you can infer that BCDEF -> A.  Your set now becomes
                   BCDEFA.
                b. For G, again going through your FDs you find EF -> G.  Since both
                   E and F are in BCDEFA, you can infer BCDEFA -> G.
   

Because you were able to infer both A and G from BCDEF, option a is a key of the relation ABCDEFG. I know there is an algorithm for this, and it is probably in your course text somewhere. There is also probably an example. You should step through it manually until the pattern is intuitive.

EDIT: The reason I would go back through the text to look for this algorithm is that chances are your exam is going to be written as opposed to multiple choice since it is a db theory course. If this is true then you would get more partial credit if you can methodically follow notation demonstrated in your course text/notes.

The main goal is to turn the key into the relation, which should prove that the proposed key is in fact a key.

Marlinmarline

Option a is indeed a key, but not an irreducible one. The irreducible one is option c. – Tarpon

Ya, I just really looked at option a. I didn't really consider specifying/figuring out which keys were minimal keys because it wasn't part of the question. I remember from my db theory courses that identifying minimal keys was a different topic from identifying any key. So I chose to leave that out from my answer to avoid confusion. – Marlinmarline

@Erwin, after looking into it a little more I see your point. I think that the use of "key" in the question is vague. The answer to this question would vary depending on if "key" is meant to be a candidate key. In that case, you would be right and option a would not be a key because there is a subset of option a which still is a valid superkey. – Marlinmarline

Yes, my apologies for the lack of clarity. I am strong with SQL and designing relational models in a database, but the theory side of it is new to me. This response helped me as well. Thanks! – Ventris

Answer 4

well, i'm no expert for this stuff, so correct me if i'm wrong, but my approach would be to eliminate impossible answers

in this case:

none of your FDs "gives" you B, D or F ... since those are part of the relation there can be no super key that does not contain B, D and F ... remove answer b (B is missing) ... remove answer d (F is missing)

now let's check the remaining answers if they contain enough information to get all parts of the relation

answer a (BCDEF) will "give" you B, C, D, E and F so you need to find A and G using the FDs ... A can be reached by BC and G can be reached by EF, so answer a is a key

answer c (BDFG) will "give" you B, D, F and G so you need to find A, C and E using the FDs ... E can be reached by FG ... C can be reached by DE (after reaching E by FG) ... and finally A can be reached by BC (after reaching C) ...

so answer c is some sort of key since the whole relation can be accessed this way ... but i don't know if this is enough to fit the formal definition ... if i'd have to guess, i'd say no

Archaeopteryx

Answer a is a proper superkey, meaning that some proper subset of it exists that is also a key. Often the term 'key' is intended to mean "irreducible", which is not the case for a. But such details can vary from one course to another ... – Tarpon

Answer 5

Code

If code talks to you more than long explanations, here is a 25 lines implementation of an algorithm that finds keys based on functional dependencies:

https://github.com/lovasoa/find-candidate-keys/blob/master/find-candidate-keys.js

Example

candidate_keys(["A","B","C","D","E","F","G"], [ [['A','B'], 'C'], [['C','D'], 'E'], [['E','F'], 'G'], [['F','G'], 'E'], [['D','E'], 'C'], [['B','C'], 'A'] ]) returns [["B","D","F","G"],["B","D","E","F"],["B","C","D","F"],["A","B","D","F"]]

Diaconal

Answer 6

step1: since AB->C and CD->E.  then we get ABD->ABCDE(1)
step2: Given (1) and EF->G, then we get ABDF->ABCDEF, then ABDF->ABCDEFG(2), 

so ABDF is a super Key. Then we will use the result of the depnedencies to determine whether they are keys. (here why I use BC->A, because A is part of my superkey, which is dependent on BC).

step3: Given (2) and BC->A, we get BCDF->ABDF, so BCDF->ABCDEFG(3)   
step4: Given (3) and DE->C, we get BDEF->BCDE, so BDEF->ABCDEFG(4)   
step5: Given (4) and FG->E, we get BDFG->BDEF, so BDFG->ABCDEFG,    
So the Answer BDFG is right.

Servetnick