Re: Generalised approach to storing address details

On Dec 13, 11:31 am, "JOG" <j..._at_cs.nott.ac.uk> wrote:
> vc wrote:
>
> > It has been known for quite a while that the ancestor relation cannot
> > be expressed in f.o.l. and r.a. See "EF - games" in any finite model
> > theory textbook.
>
> This currently is unclear to me - an ancestor relation is a relation
> like any other, and can be enumerated like any other. Take a domain D =
> {grandfather, father, son}. The ancestor relation would be A = {
> (Grandfather, father), (Grandfather, son), (father, son) }. What is so
> inexpressible there? Given that the above is no doubt obvious to you,
> if you have the inclination, perhaps you clarify/expand what you mean
> by "the ancestor relation cannot be expressed in f.o.l. and r.a".

Yes, we can represent an ancestor relation by "fully populating" it, such that for all ancestors A of X, the pair (A, X) is in the relation. What we can't do is, given a parent relation, construct the ancestor relation. (We can write a query that will work to a depth of 3, or to a depth of four, or to a depth of one million, but we can't write a query that will do it to any depth.) The relational algebra lacks the computational power needed to compute the transitive closure.

Marshall Received on Thu Dec 14 2006 - 04:49:39 CET