Re: Foreign keys

From: Brian Selzer <>
Date: Wed, 16 Jan 2008 08:42:43 -0500
Message-ID: <oRnjj.141$>

"Kira Yamato" <> wrote in message news:2008011602453916807-kirakun_at_earthlinknet...
> On 2008-01-16 01:11:22 -0500, "Brian Selzer" <>
> said:
>> "Kira Yamato" <> wrote in message
>> news:2008011600092016807-kirakun_at_earthlinknet...
>>> On 2008-01-15 22:05:24 -0500, "Brian Selzer" <>
>>> 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; if they weren't, then it could only be said that

A --> BC IFF A --> B /OR/ A --> C. 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.

> --
> -kira
Received on Wed Jan 16 2008 - 14:42:43 CET

Original text of this message