Re: An alternative to possreps

From: David BL <davidbl_at_iinet.net.au>
Date: Sun, 12 Jun 2011 00:23:55 -0700 (PDT)
Message-ID: <b6258320-454a-46b2-9206-4f2e6e5bef08_at_r35g2000prj.googlegroups.com>


On Jun 11, 10:49 pm, Erwin <e.sm..._at_myonline.be> wrote:
> On 9 jun, 11:49, David BL <davi..._at_iinet.net.au> wrote:
>
>
>
> > I think there are some interesting differences to consider. Consider
> > the following wikipedia article on algebraic data types:
>
> > http://en.wikipedia.org/wiki/Algebraic_data_type
>
> > This has an example of a recursive type named 'Tree' written in
> > Haskell as follows:
>
> > data Tree = Empty
> > | Leaf Int
> > | Node Tree Tree
>
> > Assuming Tutorial D doesn't balk at recursive types,
>
> It does.
>
> Furthermore, the concept of wanting to fit graph structures in a
> scalar type definition seems inappropriate. I'm inclined to suggest
> that your "proliferation of types" derives from this (inappropriate)
> desire (to make graphs fit with the scalar types feature) (or at least
> to make them fit in a way that is really inappropriate - see further).
>
> The canonical way for dealing with trees (and in fact arbitrary
> graphs), is to observe that they are a set of nodes plus a set of
> edges. So a "graph" type is a type that has two components : NODES
> and EDGES. This means that a graph type can be considered as being a
> TUPLE type with two attributes, or it can be considered as being a
> scalar type with two components NODES and EDGES. The difference
> between these two options is in fact negligible.

Canonical? It's only a possible way to deal with trees and often exceedingly cumbersome. I think it's important to observe that languages such as Prolog or Haskell provide direct support for algebraic data types and (if we ignore underlying physical implementations) do so without any need to introduce abstract identifiers for the "nodes". Instead "nodes" only have identity as literal expressions that denote values. This is a striking distinction.

An algebraic type definition very elegantly declares the applicable constraints.

I'll use a simple example to illustrate. Let's focus attention on a single abstract type Set<Point> associated with sets of 2D geometrical points, together with a number of operators that give rise to particular well formed literal expressions that represent certain sets of points:

  type Set<Point>;

  Set<Point> <--- circle(Point centre, Real radius) on radius >= 0;
  Set<Point> <--- triangle(Point p1, Point p2, Point p3);
  Set<Point> <--- union(Set<Point>, Set<Point>);
  Set<Point> <--- intersection(Set<Point>, Set<Point>);
  Set<Point> <--- difference(Set<Point>, Set<Point>);

Now consider that the nested literal expressions be regarded as trees and modelled instead with abstract identifies for the nodes. This can be achieved using the following relations. For convenience I'll treat the relations as predicates in the style of Prolog:

  circle(N,C,R) :- node N represents a circle with centre C and radius R.

  triangle(N,P1,P2,P3) :- node N represents a triangle with vertices P1,P2,P3.

  union(N,N1,N2) :- node N represents the set of points equal to the union of the sets of points represented by nodes N1, N2.

  intersection(N,N1,N2) :- node N represents the set of points equal to the intersection of the sets of points represented by nodes N1, N2.

  difference(N,N1,N2) :- node N represents the set of points equal to the difference of the sets of points represented by nodes N1, N2.

Ok brace yourself; here is my attempt at defining the integrity constraints. First some preliminaries - I need some helper predicates

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

  % node(N) :- N is a node.
  % This can be regarded as a view which is a union of projections.
  % Underscores are used for attributes to be projected away
  nodes(N) :- circle(N,_,_).
  nodes(N) :- triangle(N,_,_,_).
  nodes(N) :- union(N,_,_).

  nodes(N) :- intersection(N,_,_).
  nodes(N) :- difference(N,_,_).

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

  parent(P,C) :- union(P,C,_).
  parent(P,C) :- union(P,_,C).
  parent(P,C) :- intersection(P,C,_).
  parent(P,C) :- intersection(P,_,C).
  parent(P,C) :- difference(P,C,_).
  parent(P,C) :- difference(P,_,C).

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

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

Now here are the constraints. Each of the following SPJ queries must be empty:

  % nodes must not be ambiguous within a relation

  circle(N,C1,_), circle(N,C2,_), C1 <> C2?
  circle(N,_,R1), circle(N,_,R2), R1 <> R2?
  triangle(N,P1,_,_), triangle(N,P4,_,_), P1 <> P4?
  triangle(N,_,P2,_), triangle(N,_,P5,_), P2 <> P5?
  triangle(N,_,_,P3), triangle(N,_,_,P6), P3 <> P6?
  union(N,N1,_), union(N,N2,_), N1 <> N2?   union(N,_,N1), union(N,_,N2), N1 <> N2?   intersection(N,N1,_), intersection(N,N2,_), N1 <> N2?
  intersection(N,_,N1), intersection(N,_,N2), N1 <> N2?
  difference(N,N1,_), difference(N,N2,_), N1 <> N2?
  difference(N,_,N1), difference(N,_,N2), N1 <> N2?

  % nodes must not be ambiguous between relations

  circle(N,_,_),  triangle(N,_,_,_)?
  circle(N,_,_),  union(N,_,_)?
  circle(N,_,_),  intersection(N,_,_)?
  circle(N,_,_),  difference(N,_,_)?
  triangle(N,_,_,_), union(N,_,_)?
  triangle(N,_,_,_), intersection(N,_,_)?
  triangle(N,_,_,_), difference(N,_,_)?

  union(N,_,_), intersection(N,_,_)?
  union(N,_,_), difference(N,_,_)?
  intersection(N,_,_), difference(N,_,_)?

  % no dangling references
  union(_,N,_), not nodes(N)?
  union(_,_,N), not nodes(N)?

  intersection(_,N,_), not nodes(N)?
  intersection(_,_,N), not nodes(N)?
  difference(_,N,_), not nodes(N)?
  difference(_,_,N), not nodes(N)?

  % no cycles
  ancestor(N1,N2),ancestor(N2,N1)?

  % no "memory leaks" (i.e. unreachable nodes) with respect   % to a defined set of root nodes.
  node(N), not reachable(N)?

There is also an inherent limitation of the relational algebra (even extended with transitive closure), in that it cannot in itself output new trees as the results of pure functions since there is no mechanism for allocating new abstract identifiers (and such allocations cannot be regarded as the evaluation of mathematical functions). Received on Sun Jun 12 2011 - 09:23:55 CEST

Original text of this message