Re: Generalised approach to storing address details
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.