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.

Leave a Reply

Your email address will not be published. Required fields are marked *