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

.

Relevant Pages

  • Re: Functional Dependencies > Uniqueness Constraints
    ... I propose that a good relational DBMS should ... not have any special feature for enforcing uniqueness constraints. ... Obviously a DBMS that can express general FDs can express more than one ... Am I missing something? ...
    (comp.databases.theory)
  • Re: Lucid statement of the MV vs RM position?
    ... point of view that says that there is no TRULY Relational DBMS because ... of incompetance or wickedness on the part of the SQL DBMS providers is ... complex lower-level code to implement a clearer ...
    (comp.databases.theory)
  • Re: Lucid statement of the MV vs RM position?
    ... enable a total application system to be as good as a relational DBMS ... Perhaps I should have called it a database construction kit, ...
    (comp.databases.theory)
  • Re: difference between RDBMS $DBMS
    ... DBMS = Database Management System ... That is, the RDBMS set is a true subset of the DBMS set, which also includes ... Relational DBMS completely dominate the ...
    (microsoft.public.sqlserver.programming)