Re: Functional Dependencies > Uniqueness Constraints

Keith H Duggar wrote:
> Jan Hidders wrote:
> > Marshall wrote:
> > > Jan Hidders wrote:
> > > > Determining if a set of fields is a CK on the basis of
> > > > the known FDs is actually an NP-complete problem, so
> > > > if the user is so kind to indicate them explicitly
> > > > that is useful. :-)
> > >
> > > Hmmm. That doesn't seem right to me. (Although in an
> > > issue like this, were I a betting man, my money would be
> > > on you.)
> >
> > You can look it up in Garey and Johnson under the list of
> > NP-complete problems, along with checking whether a
> > relation is in BCNF and if a field is in one of the
> > candidate keys.
>
> I'm curious, does the problem have a standard name? Something
> other than "determining if a set of fields is a CK" perhaps.

Not that I'm aware of, but the BCNF problem is usually known as "Boyce Codd normal form violation" or "BCNF violation" and the hardness of checking a CK follows from the NP-hardness of this problem straightforwardly: if you could check a potential CK in PTIME there would be a PTIME algorithm for checking BCNF violation. You can probably come up with the proof of that yourself. (Hint: irreducible set of FDs)

> I'm curious to know how one verifies key-ness in polynomial
> time and if the proof involved mapping to a proven NP-hard
> problem then which problem.

The BCNF violation problem was proven NP-hard by reduction to the hitting set problem by Beeri and Bernstein. The proof is not that easy but can be found in:

http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=320066

Let me know if you cannot can access to that and I'll see what I can do.

The NP upper bound follows from the fact that you can non-deterministically guess a proper subset and show in PTIME that (1) all other fields depend on it and (2) it cannot be immediately reduced by any of the FDs. Note that this shows the NP upper bound for the problem "check if a set of fields is *not* a CK" so I should correct myself here and say that the problem of checking a CK is known to be coNP complete.

• Jan Hidders