Re: Functional Dependencies > Uniqueness Constraints

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. Can you point me to an on-line proof of the NP-completeness or even provide one if it's not so long? More specifically 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. Thanks in advance.

> > Perhaps I'm missing something, but I don't see the hard
> > in here. Maybe I should try to code it up.
>
> Pleas do. If you come up with a PTIME algorithm you would
> have proven P=NP.

Or proven that the proof of NP-completeness was flawed ;-)

• Keith -- Fraud 6