Re: Foreign keys

On 2008-01-16 08:42:43 -0500, "Brian Selzer" <brian@xxxxxxxxxxxxxxxxxxx> said:


"Kira Yamato" <kirakun@xxxxxxxxxxxxx> wrote in message
news:2008011602453916807-kirakun@xxxxxxxxxxxxxxx
On 2008-01-16 01:11:22 -0500, "Brian Selzer" <brian@xxxxxxxxxxxxxxxxxxx>
said:


"Kira Yamato" <kirakun@xxxxxxxxxxxxx> wrote in message
news:2008011600092016807-kirakun@xxxxxxxxxxxxxxx
On 2008-01-15 22:05:24 -0500, "Brian Selzer" <brian@xxxxxxxxxxxxxxxxxxx>
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

.

Relevant Pages

  • Re: Foreign keys
    ... values in the extension of a database states /what is/. ... dependency does not limit the possible values in each domain: ... a functional dependency does not limit the possible values in each ... In relational algebra, say I have a relation Person(Name, Age). ...
    (comp.databases.theory)
  • Re: Foreign keys
    ... In relational algebra, say I have a relation Person(Name, Age). ... between the active domain for Name and the active domain for Age, ... So, in the case of a single relation, the surjectivity holds trivially ... from the definition of functional dependency. ...
    (comp.databases.theory)
  • Re: Foreign keys
    ... In relational algebra, say I have a relation Person(Name, Age). ... between the active domain for Name and the active domain for Age, ... So, in the case of a single relation, the surjectivity holds trivially from the definition of functional dependency. ...
    (comp.databases.theory)
  • Re: Foreign keys
    ... Then the foreign key B1 represents the functional dependency ... The possible values of "age" can be defined as the set of non-negative integers. ... So, if I have a "person" relation with a finite number of tuples, then I cannot possibly have all possible non-negative integers. ...
    (comp.databases.theory)
  • Re: 3vl 2vl and NULL
    ... >>Dot as everyone else, including Uncle Vernon in this 2VL scenario, has ... >>If the data are changed so that Aunt Marge also has a null set age, ... >>someone whose age (in this database) is less than or equal to Marge's ...
    (comp.databases.theory)