Re: RM and abstract syntax trees

From: David Cressey <>
Date: Sat, 10 Nov 2007 16:08:44 GMT
Message-ID: <gIkZi.1933$ET.389_at_trndny03>

"David BL" <> wrote in message
> On Nov 10, 7:29 am, "David Cressey" <> wrote:
> > One of the fundamental properties of a pointer is that you can
> > it by using it as an address in an address space, in order to retrieve
> > thing pointed to directly. There is no corresponding property in
> > sequentially generated arbitrary meaningless identifiers.
> The mathematician in me axiomatizes the concept of pointer in terms of
> its abstract properties, which (ignoring null pointers) are
> 1) the existence of an associated address space, which is just a
> set of objects
> 2) a bijection between objects in the address space and pointer
> values
> In one direction this bijection is "address of" and in the
> other
> it is "dereference"
> 3) the ability to compare pointer values
> This encompass physical address spaces, virtual address spaces, C++
> smart pointers, persistent OIDs and pointer swizzling etc.
> It also encompass node identifiers of an AST if we regard the DB as
> defining an address space of AST nodes, and an appropriate select
> query represents a dereference that logically binds to precisely one
> node of the AST.
> My perspective conflicts with your statement above.

First, the term "pointer" originates in computer science, not mathematics. This is unlike the term "relation" which originates in mathematics and is transferred to the world of computer science, where it presumably retains all the properties that made it important from a mathematical perspective.

Second, your analysis overlooks the difference between address based addressing and content based addressing. If you retrieve a row by specifying an OID to be matched, you are still engaging in content based addressing. If you specify a pointer, there is no law that says that the object pointed to is going to contain a copy of the pointer you used for access.

In most pointer based systems, the pointer is not included in the contents, being seen as redundant to its location.

The distinction between content based addressing and pointer based addressing is fundamental to the comparison of databases built on the relational model and databases built on the graph model.

It is possible, by suitable abstraction and by poor design choices, to create a database that offers none of the advantages claimed for the relational model, while appearing to conform to the relational model superficially. Sad to say, thousands of such databases have been constructed over the years, and have led many uneducated database newbies to believe that the relational model doesn't really offer the advantages that its proponents cliam. Received on Sat Nov 10 2007 - 17:08:44 CET

Original text of this message