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: Wed, 31 Oct 2007 18:20:34 -0700
Message-ID: <>

On Oct 31, 11:55 pm, Marshall <> wrote:
> On Oct 31, 5:53 am, David BL <> wrote:
> >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.
> I have to give you credit as the best educated, best argued
> "the RM doesn't work well here" arguer I've seen. And in
> fact you've picked the one example I've wanted to look
> at for a while now: parse trees.
> But I still don't agree with you. Not yet anyway.
> > I find it interesting that LISP and Prolog have far simpler integrity
> > constraints. RM is trying to *emulate* pointers, and the shoe
> > doesn't fit too well.
> If we are using nested structures, then the structure itself
> provides the integrity.

Exactly, that's what I was trying to say. My somewhat vague notion is that the RM representation loses that simplicity because it is *too flexible* - hence the need for complex integrity constraints

> (I don't think "trying to emulate
> pointers" is accurate, at least not strictly.)

> > Anyway, what matters is whether RM is suited to representing ASTs. I
> > find it significant that RM forces one to generate unique but
> > otherwise meaningless identifiers on all the nodes and exposes them
> > for all to see, whereas LISP, Prolog and even C/C++ allow the user/
> > programmer to work at a level of abstraction where node identifiers
> > are hidden.
> I think this is largely a distraction of no real import.
> > I find it particularly telling that Prolog provides the choice of
> > 1. using the approach above (which is how RM would be used); or
> > 2. using nested terms, (which is outside of RM's scope)
> > and the clear winner is 2.
> Your conception of the RM is too narrow. There is nothing in
> the RM that precludes nested structures, nor union types.

I assume you are referring to the idea of using complex domain types. My understanding is that C.J. Date "weakens" 1NF to the requirement that for a given tuple, an attribute name is mapped to a *single* value, without imposing any restrictions on how "atomic" that value should be. In other words, 1NF is vacuous because it is implied by the definition of tuple. Quite rightly, there doesn't appear to be any formal way to define what "atomic" means.

This is rather vague, but to my way of thinking, the scope of RM/RA concerns the relations and tuples and whilst it has access to the operators on the domain types (and most importantly equality testing), the domain types are nevertheless to be treated as outside the scope of RM.

Were you thinking specifically about RVAs? Received on Wed Oct 31 2007 - 20:20:34 CDT

Original text of this message