Re: RM and abstract syntax trees

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Sun, 11 Nov 2007 19:45:22 -0400
Message-ID: <47379231$0$5280$9a566e8b@news.aliant.net>

David Cressey wrote:

> "David BL" <davidbl_at_iinet.net.au> wrote in message
> news:1194798913.080431.70540_at_i38g2000prf.googlegroups.com...
>

>>On Nov 11, 1:08 am, "David Cressey" <cresse..._at_verizon.net> wrote:
>>
>>>"David BL" <davi..._at_iinet.net.au> wrote in message
>>
>>>>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.
>

>>Yes the term "pointer" originates in computer science and its meaning
>>is not at all precise.  Wouldn't it be nice if the software
>>development discipline was generally treated as a branch of
>>mathematics, and there were many standardised axiomatic definitions to
>>give it the proper foundations.
>>
>>
>>>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.
>>
>>This is an interesting and important distinction.  I assume you are
>>suggesting pointers by definition never use content based addressing.
>>However I regard the following as a counter example...

>
> I am claiming that the word "pointer" as used in computer science and going
> back at least as far as the invention of Lisp in the 1950s, by definition
> refers to address based addressing. That any use of the word "pointer" that
> conflicts with this use is technically incorrect, and may be useful only to
> the extent that it suggests an analogy to the purpose for which pointers are
> used.
>
> An analogy is only an analogy. It isn't a definition.

A pointer is defined as something that points. One can specify a computational model that depends entirely on pointers without requiring addressible memory.

>>In the literature on pointer swizzling, persistent OIDs are classified
>>as being of two different types : physical or logical.  This is
>>exactly your distinction above with different terminology.

>
> Fien. I don't propose to criticise you for the terminology you've been
> exposed to, nor do I intend to accept criticism for my use of terminology
> that I've been exposed to. A trend towards more uniform terminology would
> be welcome, but we won't make any progress in that direction by finger
> pointing.

In which case, a finger is also a pointer. Regardless whether physical or logical, OIDs point.

>>A physical
>>OID directly specifies the location of the object on disk.  For
>>example, in the commercial product ObjectStore, the low 32 bits of the
>>OID represents a seek position within a "cluster".

>
> A physical OID corresponds to what I call a "pointer".

Any OID corresponds to a "pointer".

>>By contrast a
>>logical OID uses an indexing data structure allowing for objects to be
>>relocated.   A Log Structured Store for example will typically use
>>this latter approach.

>
> The only indexing structures I'm directly familiar with are the ones in SQL
> DBMS products like Oracle RDBMS, or in indexed file systems like RMS (a
> facility within VMS). In the former case, the index is a data structure
> that serves to map what you are calling a "logical OID" to what I am
> calling a "pointer". The pointer that the DBMS retrieves from an index
> serves for direct lookup of the thing pointed to (a table row or table row
> fragment, in this case)
>
>

>>Despite such an important and useful
>>distinction, it is only relevant to the underlying physical
>>implementation of the Persistent Object Store (POS).  It has no impact
>>whatsoever on the fact that clients of a POS like to think of OIDs as
>>persistent pointers between objects.

>
> I tend to use the acronym "POS" with a different expansion, but we'll let
> that pass for now.

An appropriate expansion in this case, I might add.

> It may or may not have any impact on what the clients like to think. It
> does however have a great impact on the delay time needed to access the
> thing referenced by the pointer. It also has a great impact on the
> consequences of shuffling data within the address space. (What you are
> calling "swizzling" might be the same as what I'm calling "shuffling".
>
> If there are physical pointers beyond the control of the DBMS, then
> shuffling data can result in the invalidation of such pointers with no
> possibility of raising an exception at the appropriate point in time.
>
> So we can at least table the discussion on terminology by agreeing that
> "pointer", in strict usage, should ONLY refer to physical OIDs.

I disagree. I see no reason to redefine pointer to mean something new and overly constrained. An OID is a pointer based on the fact that it points.

[snip] Received on Sun Nov 11 2007 - 17:45:22 CST