Re: Foreign keys

From: Kira Yamato <kirakun_at_earthlink.net>
Date: Wed, 16 Jan 2008 11:28:13 -0500
Message-ID: <2008011611281316807-kirakun_at_earthlinknet>

On 2008-01-16 08:42:43 -0500, "Brian Selzer" <brian_at_selzer-software.com> said:

>
> "Kira Yamato" <kirakun_at_earthlink.net> wrote in message
> news:2008011602453916807-kirakun_at_earthlinknet...

>> On 2008-01-16 01:11:22 -0500, "Brian Selzer" <brian_at_selzer-software.com>
>> said:
>> 
>>> 
>>> "Kira Yamato" <kirakun_at_earthlink.net> wrote in message
>>> news:2008011600092016807-kirakun_at_earthlinknet...
>>>> On 2008-01-15 22:05:24 -0500, "Brian Selzer" <brian_at_selzer-software.com>
>>>> said:
>>>> 
>>>> In relational algebra, say I have a relation Person(Name, Age).  Then
>>>> there is functional dependency
>>>> Name --> Age.
>>>> Now, the domain for Age can be any non-negative integer.  However, the
>>>> extensional relation will not have a tuple for every possible value of
>>>> Age.
>>>> 
>>> 
>>> [...]
>>> 
>>>> Are you saying that Name --> Age is not a functional dependency because
>>>> it
>>>> is not surjective?
>>>> 
>>> 
>>> No.  What I'm saying is that not only is it the case that for every Name
>>> in
>>> the extension there is one and only one Age, but also that whenever there
>>> is
>>> an Age in the extension, there must also be a Name.  This is due to the
>>> fact
>>> that Name and Age appear in the same relation schema.  So in that sense
>>> Name --> Age /is/ surjective.
>>> 
>>> I keep wanting to mention active domains, and for a database with a
>>> single
>>> relation, it would be valid to say that Name --> Age describes a
>>> surjection
>>> between the active domain for Name and the active domain for Age, but for
>>> databases with multiple relations, an active domain is the set of all
>>> values
>>> from a domain that are in any relation in the database.
>> 
>> Ok.  I'm beginning to see your point.
>> 
>> So, in the case of a single relation, the surjectivity holds trivially
>> from the definition of functional dependency.
>> 
>> However, in the case of foreign key where 2 relations are involved, the
>> foreign key does not necessarily maps to every possible primary key in the
>> other relation.  So, it is possible to not have surjectivity between
>> attributes across 2 relations.
>> 
>> So, I do have one more question.  Why do we want to require functional
>> dependencies to be surjective?  What desirable property of relational
>> algebra do we lose if we introduct functional dependencies that are not
>> surjective?
>> 
>> Thanks.
>> 

>
> Since functional dependencies are surjective, it can be said that
>
> A --> BC IFF A --> B /AND/ A --> C;
This property sounds like what Date, in his book "Introduction to Database System," defines as Join-dependency.

>
> if they weren't, then it could only be said that
>
> A --> BC IFF A --> B /OR/ A --> C.
Or that we can only say that

        if A --> B and A --> C, then A --> BC. However, the converse statement is not necessarily true.

>
> Similarly, the relation schema,
>
> R {A, B, C} where A --> BC,
>
> can represent exactly the same information as the pair of relation schemata,
>
> S {A, B} where A --> B, T {A, C} where A --> C,
>
> if and only if the cyclical inclusion dependency,
>
> S[A] = T[A] (mutual foreign keys)
>
> also holds.

Ok. So the property we want with surjectivity is that of equivalence of representation through joins.

-- 

-kira

Received on Wed Jan 16 2008 - 17:28:13 CET