Search code examples
databasefunctional-dependencies

Determine keys with functional dependency

please can someone explain to me how to determine keys in Table R R(A,B,C,D,E,F,G,H,I,J)

C => BD
E => AC
E => D
G => J
BG => F
F => H

Thank you so much

Solution

  • First, you need to know how to determine the closure of an attribute (or attributes) in a relation. What this means is that, given a starting set of attributes, you calculate the total set of attributes determined by that initial set via all possible functional dependencies. In order to do this, you need to know some basic logical axioms and apply them to combine functional dependencies.

    The axioms we'll be using is the law of identity and Armstrong's axioms, specifically:

    • identity: X -> X
    • transitivity: if X -> Y and Y -> Z then X -> Z
    • union: if X -> Y and X -> Z then X -> YZ
    • augmentation: if X -> Y then XZ -> YZ for any Z

    Now, if we apply that to your given set of functional dependencies with respect to attribute E, we get:

    1. E -> E (identity)
    2. E -> AC (given)
    3. E -> D (given)
    4. C -> BD (given)
    5. E -> ACD (union of 2 and 3)
    6. E -> ACDE (union of 1 and 5)
    7. E -> ABCDE (transitive composition of 4 and 6)

    In the same way, we can compute the closure of all the other attributes in R with respect to the given functional dependencies. You should do this as an exercise. With practice you'll be able to quickly see which ones to focus on.

    Our goal is normally to find a minimal set of attributes that determine the whole relation. In this case, EGI -> ABCDEFGHIJ and that's a candidate (minimal) key. You should compute this result for yourself to verify. A relation may have more than one candidate key.

    There are other keys that aren't minimal, like ABCDEFGHIJ. Trivially, the whole relation determines itself. Between the extremes of candidate keys and the whole relation are superkeys, like EFGHI - any superset of a candidate key is a key, we call these superkeys.