Re: An alternative to possreps

From: Erwin <e.smout_at_myonline.be>
Date: Sun, 12 Jun 2011 17:11:06 -0700 (PDT)
Message-ID: <735a963b-b419-4a12-bf31-b2945b964b93_at_k16g2000yqm.googlegroups.com>


On 12 jun, 09:23, David BL <davi..._at_iinet.net.au> wrote:
> 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).- Tekst uit oorspronkelijk bericht niet weergeven -
>
> - Tekst uit oorspronkelijk bericht weergeven -

It's hard to see the "elegance" of your examples. I also have a few doubts as to the Haskell Tree example. How is a Leaf different from a Node (Empty * Empty) ? Isn't Leaf a redundant construct here ? Or if Empty trees are not permitted as members of a Node, then how about Nodes with only one Child ?

It's also hard for me to see your point what you mean where you said that there is a "limitation" in relational algebra, because it has no way of "allocating abstract identifiers". Sounds like nonsense to me, to be frank. Algebra operates on values. That's all. I don't see why any algebra would need to be able to "allocate abstract identifiers". Received on Mon Jun 13 2011 - 02:11:06 CEST

Original text of this message