Re: Modeling question...

From: David BL <>
Date: Fri, 24 Oct 2008 23:24:12 -0700 (PDT)
Message-ID: <>

On Oct 24, 6:13 pm, David BL <> wrote:

> The following is the example I used when I talked about this 12 months
> ago:
> Using Prolog notation, consider the following relations which allow
> for representing an expression such as (x+1)*3:
> var(N,S) :- node N is a variable named S
> number(N,I) :- node N is a number with value I
> add(N,N1,N2) :- node N is the addition of nodes N1,N2
> mult(N,N1,N2) :- node N is the product of nodes N1,N2
> Define a view called nodes(N) which is a union of projections as
> follows:
> nodes(N) :- var(N,_).
> nodes(N) :- number(N,_).
> nodes(N) :- add(N,_,_).
> nodes(N) :- mult(N,_,_).
> The following are the integrity constraints (each query must be
> empty):
> var(N,S1), var(N,S2), S1 <> S2?
> number(N,I1), number(N,I2), I1 <> I2?
> add(N,N1,_), add(N,N2,_), N1 <> N2?
> add(N,_,N1), add(N,_,N2), N1 <> N2?
> mult(N,N1,_), mult(N,N2,_), N1 <> N2?
> mult(N,_,N1), mult(N,_,N2), N1 <> N2?
> var(N,_), number(N,_)?
> var(N,_), add(N,_,_)?
> var(N,_), mult(N,_,_)?
> number(N,_), add(N,_,_)?
> number(N,_), mult(N,_,_)?
> add(N,_,_), mult(N,_,_)?
> add(_,N,_), not nodes(N)?
> add(_,_,N), not nodes(N)?
> mult(_,N,_), not nodes(N)?
> mult(_,_,N), not nodes(N)?

It occurred to me that there are more integrity constraints required.

Consider that we define

  % parent(P,C) :- node P is a parent of node C

  parent(P,C) :- add(P,C,_).
  parent(P,C) :- add(P,_,C).
  parent(P,C) :- mult(P,C,_).
  parent(P,C) :- mult(P,_,C).


  % ancestor(N1,N2) :- node N1 is an ancestor of N2.   ancestor(N1,N2) :- parent(N1,N2).
  ancestor(N1,N2) :- parent(N1,N), ancestor(N,N2).

The following goal must return failure to express the integrity constraint that there are no cycles:


In addition we would like to express the constraint that there is no garbage (ie unreachable nodes) with respect to a defined set of root nodes.

  % root(N) :- node N is the root of an expression.

  % reachable(N) :- node N is reachable from a root   reachable(N) :- root(N).
  reachable(C) :- parent(P,C), reachable(P).

  % integrity constraint - must be empty   node(N), not reachable(N)?

As you can see, it's rather low level. I don't think it's surprising that the RM is capable of that (since it's so flexible).

A common theme on this ng is the idea of physical independence. It tends to be assumed that a program written in C and using pointers is "low level" and "close to the physical hardware", whereas anything using the RM is necessarily "high level" and "divorced from the physical hardware". This I agree is usually the case.

I think there is evidence here that an inappropriate use of the RM can actually be low level in a similar way to how C is low level. ie algorithms can easily have bugs that resemble the creation of dangling pointers or memory leaks!

Now consider again the following C++ struct

  using namespace std;

  struct Chapter

      string title;
      vector<string> paragraphs;
      vector<Chapter> subchapters;


This recursive type definition compiles without any problem and is able to grow dynamically and enforces the integrity constraints. Nevertheless there isn't a pointer in sight. Behind the scenes there is a physical implementation of the STL string and vector classes using pointers, heap allocations and so on.

The striking thing to me is that we are able to work at a higher level than the RM in this particular case. Received on Sat Oct 25 2008 - 08:24:12 CEST

Original text of this message