Re: Functional Dependencies > Uniqueness Constraints

Marshall wrote:
> Jan Hidders wrote:
> > Marshall wrote:
> > > Geeze, it's deader than a dotcom startup in here.
> > >
> > > Okay, fine. I propose that a good relational DBMS should
> > > not have any special feature for enforcing uniqueness constraints.
> > > Instead, it should be able to record and enforce functional
> > > dependencies.
> >
> > Obviously a DBMS that can express general FDs can express more than one
> > that can just express CKs, except if you alway normalize to BCNF. But
> > that doesn't mean there shouldn't be a special notion of CK.
>
> Special notion or special notation?

Both. Having this notion makes things easier for the user (DKs are easier to understand for most people than FDs) and for the DBMS (CKs are important for indexes and are easier to maintain then general FDs).

> > 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.

> Wait, isn't it the case that all we really care about is *whether* we
> have a candidate key?

There is always one, by definition.

> [...] Further, the number of FDs and
> the number of attributes are typically going to be pretty small
> numbers, wouldn't you think?

Often they will, sometimes they won't.

> 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.

• Jan Hidders