Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Determine Keys from Functional Dependencies

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.

like image 561
David Avatar asked Apr 20 '11 19:04

David


People also ask

What is key in functional dependency?

A key is an attribute or a combination of attributes that uniquely identifies each row within a table. A key implies uniqueness, so in other words, a key functionally determines the entire row. A determinant is not necessarily a key as determinants do not imply uniqueness.

How do I find candidate keys in a table?

Candidate Key is minimal set of attributes of a relation which can be used to identify a tuple uniquely. For Example, each tuple of EMPLOYEE relation given in Table 1 can be uniquely identified by E-ID and it is minimal as well. So it will be Candidate key of the relation.


1 Answers

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/RelationalDatabaseTools

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

like image 181
Erwin Smout Avatar answered Oct 12 '22 23:10

Erwin Smout