Tag Archives: SR27

Additional Key

After skipping around it for a while, we’re finally ready to return to this problem.

The problem: Additional Key.  This is problem SR27 in the appendix.

The description: Given a set A of attributes, and a set F of functional dependencies, a subset R of A, and a set K of keys on R,  can we find an additional key on R for F?  (Which is an additional subset R’ of R, that is not in K, that serves as a key for F)

Example: This example is from the Beeri and Bernstein paper that had last week’s reduction, and has this week’s as well:

  • ({A,B), {C}
  • ({C}, {B}

If R = A = {A,B,C}, and K = the single key {A,B}, then {A,C} is an additional key.

Reduction: The Beeri and Bernstein paper uses a similar construction from last week’s.  Again, we reduce from Hitting Set.

They build the same construction as in the BCNF violation reduction.  Recall that the set was set up so that there was a BCNF violation if there was a hitting set, and that violation happened because some but not all attributes were functionally dependent on the hitting set.  So if we add those extra attributes to the set of attributes in the hitting set, we get an additional key.

That’s the basic idea, but the paper has some parts I have trouble following (there are some notation issues I can’t parse, I think.  For example, it’s not immediately obvious to me what K is for this problem.  I think it’s the set of new attributes, but I’m not sure.

Difficulty: 9 One step harder than the last problem, since it builds on it.