Re: Generalised approach to storing address details
Date: Sat, 16 Dec 2006 18:00:22 GMT
Message-ID: <WuWgh.487439$1T2.31747_at_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).
p
>
>>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 - 19:00:22 CET