Oracle FAQ Your Portal to the Oracle Knowledge Grid

Home -> Community -> Usenet -> comp.databases.theory -> Re: RM and abstract syntax trees

Re: RM and abstract syntax trees

From: David BL <>
Date: Tue, 30 Oct 2007 17:34:48 -0700
Message-ID: <>

On Oct 31, 2:46 am, paul c <> wrote:
> Okay, from your original post:
> "So RM is forced
> to expose the equivalent of pointers directly in the representation.
> Furthermore, the RM has no mechanism for hiding these pointers or
> giving the user an interface that promotes the idea that a node
> logically represents a value."
> Where does RM ever mention pointers? Eg., What are the pointer
> operations that RM supports?

I'm associating a "pointer" with the idea to give a thing (like a node of an AST) some meaningless identifier, and using that identifier elsewhere as a means to uniquely reference that thing. With that *analogy*, RM performs a pointer dereference when performing a natural join.

Consider a representation of (x+1) * 3 using the following relations

var(n,s) :- node n is a variable with name s number(n,i) :- node n is a number with value i plus(n,n1,n2) :- node n represents the addition of n1,n2 prod(n,n1,n2) :- node n represents the product of n1,n2

Algorithms that process the AST will use joins on node attributes, basically emulating pointer dereference.

Whether you accept the analogy with pointers or not, the result is hideous all the same. For example, consider the integrity constraints needed - eg that a node can't represent a number and a variable at the same time.

Assuming there isn't some decent way to represent AST's using RM that I'm not aware of, my conclusion that RM is ill suited seems valid.

> (ps: I don't agree that RM can't represent nested lists but I would
> agree that it's not much fun to manipulate them, I wish Codd had said
> more about nested relations as I have a feeling he spent some time
> considering them.)

I never said that RM cannot represent nested lists. Received on Tue Oct 30 2007 - 19:34:48 CDT

Original text of this message