Re: Constraints and Functional Dependencies

From: NENASHI, Tegiri <tnmail42_at_gmail.com>
Date: Mon, 26 Feb 2007 05:13:09 +0100 (CET)
Message-ID: <Xns98E2ECA00D8DEasdgba_at_194.177.96.26>


"Marshall" <marshall.spight_at_gmail.com> wrote in news:1172444365.872334.49350_at_t69g2000cwt.googlegroups.com:

> On Feb 25, 9:02 am, paul c <toledobythe..._at_oohay.ac> wrote:

>>
>> I thought Marshall had retracted "foreign key" and meant it to be
>> replaced with "referential integrity".

>
> Yes.
>
>
>> My only problem with the latter
>> is that I haven't been able to find a quote that I can trust where
>> Codd indicated whether "referential integrity" involves a "candidate
>> key". 

>
> Agreed.
>
> In fact, it seems to me the useful property of a SQL foreign key
> is exactly the forall ... exists property I described in the OP. As
> you've said, SQL also has the requirement that the attribute(s)
> named in the exists clause must be a (primary?) key, but neither
> of us can see a hard, logical reason for that restriction. Even
> though it does capture what is probably the 99% use case.
>
> I pulled about 10 definitions of "referential integrity" off the
> web and about 7-8 of them matched my forall ... exists
> construct.
>
> The funny thing is, my mentioning of FKs was offhand, and
> only meant to indicate roughly that we can dispense with
> "special purpose" constraints as found in SQL. Mostly I
> wanted to talk about FDs. But this conversation is good too.
>
>
> Marshall
>

This is a fact that is very well known that one can express constraints as implications. Like Abiteboul said in some place "the presence of some tuples *implies* the presence of some other tuples" (or something like this).

"Referential integrity" is the argot of SQL programmers. In the theory of relational databases one uses the term of "inclusion dependency" and "referential integrity is a particular case of that.

The inclusion dependency can be formulated in terms of the relational algebra. Let R(X,Y,U) and S(M,X,Y) be some relations. Then in terms of the relational algebra ProjectAttrXY(R) is_a_subset of ProjectAttrXY(S), or the equivalent in tuple relational calculus: forall(r in R)exists(s in S)(r[X,Y] = s[X,Y]), is an example of inclusion dependency. In terms of first order logic it is: forall(x)forall(y)forall(u) (R(x,y,u) --> exists(m)S(m,x,y) ) where "-->" is the sign of implication.

Other dependencies like functional dependencies or join dependencies are also implications. For example FD for R(X, Y, Z) can be XY --> Z. Et cetera. Abiteboul explicates it very well.

The inclusion dependency does not utilize the notion of the candidate key. Date, in some place perhaps Tutorial D, has said that the key is not necessary for the inclusion dependency. The SQL designers made the referential integrity like a special case because it is efficient to use the primary key to validate the constraint. Of fcourse SQL permits to define the inclusion dependency with the "check" constraint.

--
Tegi
Received on Mon Feb 26 2007 - 05:13:09 CET

Original text of this message