Re: Generalised approach to storing address details

From: paul c <toledobythesea_at_oohay.ac>
Date: Sat, 16 Dec 2006 18:00:22 GMT
Message-ID: <WuWgh.487439$1T2.31747@pd7urf2no>

JOG wrote:
> vc wrote:
>

>>JOG wrote:
>>
>>
>>
>>>True, but parents and ancestors are two completely separate relations -
>>>ancestry is transitive, parentage is not for example (my parent's
>>>parent is not in turn my parent too. Well lets hope not eh.). If we
>>>just have a parentage heirarchy, we externally know a semantic
>>>relationship between parentage and ancestry that allows us to infer who
>>>ancestors are - but vitally we are applying two extra inference rule
>>>from our external knowledge:
>>>
>>>1) Parent(x,y) => Ancestor(x,y)
>>>2) Ancestor(x,y) & Ancestor(y,z) => Ancestor(x,z)
>>
>>If read as a first-order logic implication,  the above does not
>>uniquely define the Ancestor relation.

>
>
> No, but am I correct in thinking that the above statements could be
> used to define the set of propositions in an Ancestry table via a
> Recursive Definition, with the basis clause referencing the already
> established Parent relation?
> ...

Seems as if I've been pondering something along that line for ages, don't know why. If this "Recursive Definition" is possible/useful without introducing new operators, I wonder if the following makes any sense:

Both relations must be recursively defined because I think JOIN would need to operate on "subtrees" of tuples rather than singleton values of attributes.
Because of the recursion in 1), all values would need to be sets, eg., if R has attributes A and B and B is of the same type as R, then we sometimes need an empty set to stand for a value of B.

I've been trying to reconcile this with the formal definitions starting on page 14 of ALGEBRA at http://www.dcs.warwick.ac.uk/~hugh/TTM/APPXA.pdf especially <AND>.

Haven't gotten very far except wherever "v" is mentioned, eg., in the triple <A,T,v> I treat it as a set (could be a singleton) and just to help me think in a parallel fashion, translate "conjoin" to "subjoin" (my little pun since this is all very subjunctive. Likely crazy too since I'm assuming conjoin is just a special case of subjoin).

>>Consider Ancestor(X,Y) = true.
>>If read as a Prolog program,  the above is more expressive than any
>>relational algebra query because Prolog has recursion(resolution)  and
>>r.a. does not.
>>
>>
>>>These rules could still be encoded and applied relationally. The tools
>>>do not currently exist to do this without recursive querying, but
>>>(without thinking to hard about it ) I don't envisage a theoretical
>>>reason why they could not be encoded as part of the predicate for a
>>>virtual table, generated from the parentage table itself. Good idea for
>>>a research paper maybe.
>>
>>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".
> Thanks, J.
>
>
>
Received on Sat Dec 16 2006 - 12:00:22 CST