Re: Concurrency in an RDB

From: David <davidbl_at_iinet.net.au>
Date: 31 Dec 2006 17:45:43 -0800
Message-ID: <1167615943.490821.272040@h40g2000cwb.googlegroups.com>

Marshall wrote:
> On Dec 24, 5:39 pm, "David" <davi..._at_iinet.net.au> wrote:
> > Marshall wrote:
> >
> > > And looking at an individual paragraph, what is that?
> > > It is a string, which is to say a sequence of characters,
> > > which is a map from the natural numbers to the
> > > target set characters, which is a relation. How
> > > would you go about representing the paragraph
> > > as a tree? A right-heavy binary tree of characters?
> >
> > > /\
> > > T/\
> > > h/\
> > > a/\
> > > t/\
> > > /\
> > > w/\
> > > o/\
> > > u/\
> > > l/\
> > > d/\
> > > /\
> > > s/\
> > > u/\
> > > c/\
> > > k/\
> > > ./\
> > Let's assume the right heavy binary tree - ie a head-tail list as used
> > commonly in Lisp or Prolog. I imagine in an RDB there would be a
> > table with the attributes (Id,HeadChar,TailId). Each record needs a
> > unique id (the primary key) and represents a string with the given head
> > character and tail string.

>

> Whoops, you misread me. You said "hierarchical chapters
> of paragraphs of text" which I took to be a commendation
> of trees as logical representation.

I meant that each chapter contains a linear list of paragraphs of text characters as well as a linear list of child chapters, allowing chapters to form trees. Do you regard this as a physical description?   The intention is to describe most closely how the end user understands the data in this particular example.

I'm aware of the importance of distinguishing logical versus physical representation, and how the relational approach is very good at providing this separation of concerns. This is one of the reasons why an RDB is mostly a better choice than an OODB. An OODB exposes too many implementation details - such as what type of collection to use (eg array, list, bag, set). This is one of the ways in which OO modelling is lower level than RM.

Do you regard "logical" as simply referring to some higher-level representation close to the problem domain and possibly divorced from the underlying physical representation (and performance concerns), or is it more specifically associated with FOPL?

When the problem domain is expressed and understood by the end user in terms of a tree a direct physical representation of the tree is very effective. Given a node, you can directly iterate through the child nodes. This maps well to algorithms that recurse down through the tree. This seems more parsimonious than the relational approach which needs a select+project query at each node of a recursive algorithm. Of course if RA is extended to support transitive closure of relations then the relational approach is more satisfying.

> I countered with "a map
> from the natural numbers to the target set characters."
> Further countering the idea of trees, I said of using trees
> to represent paragraphs, specifically, "That would suck."

>
>


> > It is easy to write all sorts of algorithms in this way.  I

> > particularly like the use of Prolog to process head-tail lists

> > recursively. I don't know SQL very well but I imagine it would be
> > similar although far less elegant?

>

> I share your like of inductive data structures and algorithms over
> same. (I associate these more with SML and Haskell than Lisp
> or Prolog, but I suppose that's po-ta-to po-tah-to.) The relational
> way however would be to operate on the entire structure at
> once, in a set-based way.

That really illustrates RM's high-level focus.

> > Despite the logical purity there are disadvantages to be considered.
> > Modern CPUs are quite adept at manipulating strings in the normal
> > representation. The space and time overheads of your suggestion are
> > significant.

>

> Here you have moved from discussing the logical model to discussing
> the "representation" seemingly without noticing that you have done
> so. The two can (and should) be as decoupled as possible.

I like the idea of such extreme decoupling. I'm sure this is the future for computer science.

I imagine no DBMS today would utilise an efficient physical representation of text strings based on a relational model.

I'm not convinced that text strings should be dealt with relationally - even at a logical level. Note that using an OO string class as an ADT also decouples the physical and logical. Putting all strings into a single huge relation (even if only conceptually) doesn't seem appealing. I don't like the way the RM approach inevitably exposes all those "internal" record id's. If anything it seems to break the nice encapsulation offered by an ADT.

> When
> I speak of a logical list, do I mean linked list or array list? The
> answer
> is "neither" because I am talking about the logical list, not its
> implementation,
> which might be a linked list, an array list, a stack of 3x5 cards, or
> nothing
> at all.

Cheers,
David Received on Sun Dec 31 2006 - 19:45:43 CST