Re: Functional Dependencies > Uniqueness Constraints

Marshall wrote:
> Wait, isn't it the case that all we really care about is *whether* we
> have a candidate key? At least logically I don't see why we'd need
> any more.

Now you confuse me. Any relvar has by definition always at least one (candidate) key. And I definitely want to know *all* the keys of a given relational expression. (Or would I be happy knowing just the FDs? Maybe I should think more about this.)

> And at the physical level, it seems to me that what you
> really want is the FDs themselves. Am I missing something?

I would have thought that keys in the form of unique indexes are very important at the physical level. What am I missing?

> It would be my expectation that I could take a user-supplied
> set of FDs and reduce it to an irreducible set fairly easily.
> Once I have that, I can determine *whether* I have at least
> one key again fairly easily. Further, the number of FDs and
> the number of attributes are typically going to be pretty small
> numbers, wouldn't you think?
>
> Perhaps I'm missing something, but I don't see the hard
> in here. Maybe I should try to code it up.

I am also a little surprised that checking the key-ness of a set of attributes is NP-complete, since the algorithm is a five-liner, and is a staple of introductory database exams where I work---it's unintuitive to think of it as "hard" :). I guess the point is that it is extremely inefficient when the number of attributes and FDs is very big.

-- 
Jon