Re: Modeling question...
Date: Fri, 24 Oct 2008 23:24:12 -0700 (PDT)
Message-ID: <01aabbae-291d-4987-a105-c14c1837bcb0_at_1g2000prd.googlegroups.com>
On Oct 24, 6:13 pm, David BL <davi..._at_iinet.net.au> 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).
and
% 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:
ancestor(N1,N2),ancestor(N2,N1)?
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