# Re: Foreign keys

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

*>*

**This property sounds like what Date, in his book "Introduction to Database System," defines as Join-dependency.**

*> 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.
**
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.

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