Re: Generalised approach to storing address details
From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Thu, 14 Dec 2006 14:00:24 GMT
Message-ID: <YNcgh.32734$cz.487604_at_ursa-nb00s0.nbnet.nb.ca>
>
> 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.
Date: Thu, 14 Dec 2006 14:00:24 GMT
Message-ID: <YNcgh.32734$cz.487604_at_ursa-nb00s0.nbnet.nb.ca>
Marshall wrote:
> 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.
Your assertion depends entirely on whether one includes transitive closure or recursion in the algebra. Does the integer algebra have the computational power needed to compute factorial? Received on Thu Dec 14 2006 - 15:00:24 CET