Re: RM and abstract syntax trees

On Oct 31, 6:20 pm, David BL <davi..._at_iinet.net.au> wrote:
> On Oct 31, 11:55 pm, Marshall <marshall.spi..._at_gmail.com> wrote:
>
>
>
> > On Oct 31, 5:53 am, David BL <davi..._at_iinet.net.au> 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

Sure.

It is a general engineering truism that a solution designed for some specific narrow purpose may be better *at that purpose* than something general purpose.

So it's no particular surprise that a structure of heterogeneous trees will model an application (parsing) of heterogeneous trees.

We might prefer a general solution still, for general reasons. And I think we will also find that at least some queries are going to be easier with a relational approach even so. Off the top of my head ... oh, I dunno. Dump all the symbol names or something.

> > 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.

That was what I meant by nested structures, yes.

Actually, Paul had a pretty good take on atomic just now: it means the relational operators can't decompose them. As has been said a bunch of times, the only operation the RM requires on attribute domains is the equality test.

I also mentioned union types, which could also be included into RM (as a scalar type generator.) However lately I suspect that this doesn't really add all that much if anything.

> 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?

Yes, and union types.

Marshall Received on Thu Nov 01 2007 - 04:35:46 CET