Monthly Archives: September 2017

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.

Boyce-Codd Normal Form Violation

This week’s and next week’s problems use basically the same construction in their reduction.  We’re going to do them in reverse order, because that’s the order they’re presented in the paper.

The problem: Boyce-Codd Normal Form Violation.  This is problem SR29 in the appendix.

The description: Given a set of attributes A, a collection F of functional dependencies, and a subset A’ of A, does A’ violate Boyce-Codd normal form?

G&J’s definition of BCNF is: A’ violates BCNF if we can find a subset X of A’ and 2 attributes y and z in A’-X such that the pair (X,y) is in the closure of F, and (X,z) is not in the closure of F.

The paper by Beeri and Bernstein define BCNF as: for all disjoint nonempty sets of attributes X and Y in A, If Y is functionally dependent on X, then all attributes in A depend on X.

Example: Here is an example from the Beeri and Bernstein paper that has the reduction:

Let A = {Apartment_Type, Address, Size, Landlord, Apartment_Num, Rent, Tenant_Name}

(I’m pretty sure “Apartment_Type” means something like “Two Bedroom”, “Size” is in square feet, “Address” is the street address of the apartment building, at which there are potentially many apartments each with a different “Apt_Num”)

With these functional dependencies:

  • ({Apartment_Type, Address}, {Size})
  • ({Address}, {Landlord})
  • ({Address, Apt_Num},{Rent})
  • ({Name}, {Address, Apt_Num})

If A’ is {Name, Address, Apt_Num, Rent} then BCNF is violated because Rent is functionally dependent on Name (through the pair of attributes {Address, Apartment_Num}, but other attributes (for example, Size) is not.

Reduction: Beeri and Bernstein reduce from Hitting Set.  So we start with a set S, and a collection C of subsets of S, and an integer K.  We need to create a set of attributes and functional dependencies.

Each element in S will be an attribute in A.  If we have a hitting set S’ of the attributes, then we could create a BCNF violation by making some of the attributes (but not all) of A functionally dependent on S’.

So we create a new attribute for each subset in C.  We create dependencies between the element attribute of each element in each C and its “set” attribute.  Now if we have a hitting set S’, then that set is functionally dependent on each element attribute.  So then if we make some but not all attributes in A dependent on the set of all element attributes, we get a BCNF violation.

That’s the basic idea, but the actual proof has a lot of special cases to worry about and resolve.

Difficulty: 8.  The general idea isn’t too hard (though you have to learn the definition of BCNF to even get started), but there is a ton of details and special cases to worry about to do it right.

Prime Attribute Name

We’re skipping ahead a bit because this reduction is from the same paper as last week’s (and reduces from last week’s problem).

The problem: Prime Attribute Name.  This is problem SR28 in the appendix.

The description: Given a set A of attribute names, and a collection F of functional dependencies like in the last problem, and a specific attribute x in A, is x in some key K for the relational system <A,F>?  (Recall that keys need to be of minimal size).

Example: Using the example from last week- the list of attributes was {Name, ID, Course, Professor, Time}.  The functional dependencies were:

  • ({Name},{ID})  (If you know a student’s name, you can figure out their ID)
  • ({ID},{Name})  (If you know a student’s ID, you can figure out their name)
  • ({Name, Course}, {Professor, Time}) (If you know a student’s name and a course they are in, you can figure out the professor teaching it and what time the course is)
  • ({Professor, Time), {Course}) (If you know the professor of the course and the time it is being taught, you can figure out the course being taught.  Note that you can’t figure out the student because more than one student will be in the course)

Recall that we said the pair of attributes {Name, Course} was a key for this system.  (So, if x was “Key” or “Course”, a solver for this problem should answer “yes”.)  But since Name and ID are related, ID is also a prime attribute.  I think  Professor and Time are not prime, because any subset of A that includes them and has the required characteristic is not minimal (If you take Professor, you’d have to add two other things- for example Course and ID).

Reduction: This reduction is in the same paper that has the Minimum Cardinality Key reduction, and in fact reduces from Minimum Cardinality Key.  Their terminology differs from what I typically use, but I’ll try to do it their way to be close to the paper.

The MCK instance starts with a set of attributes A’, a set of relations D[0]’ (what they call F), and a key size m (what we call k).  We need to build an instance of the PAN problem: a set of attributes A, a new set of functional dependencies D[0], and a specific attribute we want to check: b (what our definition calls x).

First, they define a set A”, which is “a set whose cardinality if the smaller of |A’| and m”. (I guess of all new elements).  They define A to be A”xA’ unioned with A’ unioned with a new attribute b.  They define D[0] with the following characteristics:

  • For all subsets E and F of A’, if E relates to F in D[0]’, E unioned with B relates to F in D[0]
  • A’ unioned with b relates to A”xA’
  • for each ordered pair (i,e) in A”xA’, b unioned with (i,e) relates to e.
  • for each element i in A’ and all distinct e,f in A, the set {(i,e), (i,f)} relates to b.
  • Each element e in A’ relates to b.

The idea now is that if D[0] has a minimal key that contains b, you need a bunch (N) of the (i,e) sets as well in the key to distinguish which ones relate to b.  Then the A’ part of the ordered pair gives you n elements in A’ that are a key for A’.

If A’ has a key of cardinality n <= m, then we know that A” has at least n elements, and adding b to the pairs of items in A’ and A” gets you a key for A.

Also, b has to be in the key for A, since removing it gets you a set that is not D[0] expandible,

Difficulty: 9.  This is really a lot to digest.  I’m not entirely sure I get what’s happening myself.

Protected: Minimum Cardinality Key

This content is password protected. To view it please enter your password below: