Tag Archives: Minimum Cardinality Key

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.

Minimum Cardinality Key

Now we enter the “Database Problems” subsection of the chapter.  I’ll admit that I’ve had trouble with a lot of these, partially because databases isn’t an area I know a ton about, but also because the definitions of the problems often obscure what’s really happening.

The problem: Minimum Cardinality Key.  This is problem SR26 in the appendix.

The description: Given a set A of attributes, a collection F of ordered pairs of subsets of A (“functional dependencies”), and a positive integer M, can we find a set K of A attributes or less that form a key for the relational system <A,F>.

G&J defines “form a key” as the ordered pair (K,A) belongs to the closure F* of F, with the following properties:

  • F ⊆ F*
  • B⊆C⊆A implies (C,B) ⊆ F*  (the “projective” closure)
  • (B,C) and (C,D) ⊆ F* implies (B,D) ⊆ F*  (the “transitive” closure)
  • (B.C) and (B,D) ⊆ F* implies (B,C∪D) ⊆ F* (the “additive” closure)

Example: The paper by Lucchesi and Osborn that has the reduction has a good example:

Suppose we have a database table for student records.  The attribute set A could be {Name, ID, Course, Professor, Time}.  Some functional dependencies, written as ordered pairs, could be:

  • ({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)

If these relations are F, then we can derive all of the attributes just from knowing the name of the student and the course they are taking.  In other words, F* contains the pair ({name, course}, (name, ID, course, professor, time).

Reduction:  The Lucchesi and Osborn paper use different terminology than G&J’s.  They define a relation D, defined in a series of inductive steps, where D[0] is F, and each D[i] is created from D[i-1] by doing one step of one of the closures on the elements in D[i-1].  The final closure (what G&J call F*) they call D.

They also define an expansion of a relation D: Given a subset B of our attribute set A, if a relation (L,R) is in D, where L is in B, but R isn’t, the set B∪R is a D-expansion of B.

They first show that if B is a subset of A, and B’ is a D[0]-expansion of B, then (B,B’) and (B’,B) are in D.  They then show that a subset B of A is D[i]-expansible  (and thus D-expansible) if and only if it is D[0]-expansible.

Then, they do the reduction from VC. A will have one attribute for each vertex in G.  D[0] (G&J’s F) will, for each vertex v, relate the set of v’s neighbors to v.  They show that a subset K of A is a key if and only if it’s a vertex cover of V.  They do this by induction: if K=A, it’s obviously a cover.  If K is smaller than A, then K is a key if and only if there is a D[0] expansion that is also a key. K has a D[0] expansion if and only if there is some vertex v not in K such that all of the vertices adjacent to v are reachable by K.  So, K is a key (and also a cover of A).

Difficulty: 8. There must be an easier way to explain this problem.