Re: RM and abstract syntax trees
Date: Wed, 31 Oct 2007 05:53:33 -0700
Message-ID: <1193835213.716681.17810_at_v23g2000prn.googlegroups.com>
On Oct 31, 12:23 pm, paul c <toledobythe..._at_ooyah.ac> wrote:
> David BL wrote:
>
> ...
>
> > Yes RM references things uniquely with values, but pointers are "value
> > types"! ...
>
> Sure, but what good does it do to think of them that way, when plain old
> "values" suffices?
A fair question.
Using Prolog notation, consider the following relations
var(N,S) :- node N is a variable named S number(N,I) :- node N is a number with value I add(N,N1,N2) :- node N is the addition of nodes N1,N2 mult(N,N1,N2) :- node N is the product of nodes N1,N2
Suppose we define a view called nodes(N) which is a union of projections as follows
nodes(N) :- var(N,_). nodes(N) :- number(N,_). nodes(N) :- add(N,_,_). nodes(N) :- mult(N,_,_).
Note that I use underscores for attributes to be projected away.
There are numerous integrity constraints. Each of the following SPJ queries must be empty.
var(N,S1), var(N,S2), S1 <> S2?
number(N,I1), number(N,I2), I1 <> I2?
add(N,N1,_), add(N,N2,_), N1 <> N2?
add(N,_,N1), add(N,_,N2), N1 <> N2? mult(N,N1,_), mult(N,N2,_), N1 <> N2? mult(N,_,N1), mult(N,_,N2), N1 <> N2? var(N,_), number(N,_)? var(N,_), add(N,_,_)? var(N,_), mult(N,_,_)?
number(N,_), add(N,_,_)?
number(N,_), mult(N,_,_)?
add(N,_,_), mult(N,_,_)? add(_,N,_), not nodes(N)? add(_,_,N), not nodes(N)?
mult(_,N,_), not nodes(N)?
mult(_,_,N), not nodes(N)?
>From these integrity constraints we can deduce that joins used to
traverse down through the AST give us back precisely one tuple in the
result set.
Isn't it helpful to see the analogy with a pointer dereference (which also gives us a single result)?
I'll leave it up to you as to whether you dislike the analogy between node identifiers and pointer values, and the idea that a join can be compared to a pointer dereference. Perhaps you are right and the analogy creates confusion.
I find it particularly telling that Prolog provides the choice of
and the clear winner is 2.
Received on Wed Oct 31 2007 - 13:53:33 CET