Re: Generalised approach to storing address details

From: JOG <jog_at_cs.nott.ac.uk>
Date: 13 Dec 2006 11:31:42 -0800
Message-ID: <1166038302.204511.122970_at_79g2000cws.googlegroups.com>


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?

> 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 Wed Dec 13 2006 - 20:31:42 CET

Original text of this message