Re: An alternative to possreps

On Jun 13, 8:11 am, Erwin <e.sm..._at_myonline.be> wrote:

> It's hard to see the "elegance" of your examples.

In the example given I find the approach using abstract identifiers to be hideous. I note that the number of constraints grows quadratically with the size of the "grammar", making it very impractical for general models appropriate to scalable vector graphics.

> 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 ?

Me too! The "grammar" is what it is. However if you don't like it then it's easy to change. E.g. the following is more constrained:

  type NonEmptyTree;
  type Tree;

  NonEmptyTree isa Tree;

  NonEmptyTree <--- leaf(Integer);
  NonEmptyTree <--- unarynode(NonEmptyTree);
  NonEmptyTree <--- binarynode(NonEmptyTree, NonEmptyTree);

If you want a /strict binary tree/ (i.e. every non-leaf node has two children) then remove the unarynode operator.

It is possible to define constraints that are not so easy to express (e.g. a /complete binary tree/ - i.e. full at every level except possibly the last, which is filled from left to right). Fortunately such constraints seem artificial when one associates the "production rules of the grammar" with operators and the tree structures themselves are only seen as possible logical representations of values (and the values actually being represented are not generally regarded as trees).

I hope you don't read too much into the Haskell example because there are important differences in perspective with the approach I've been suggesting. That's why I moved on to the example involving Set<Point>. I've been assuming the declared types are rather directly justified by the application requirements. It is not made clear from the Haskell example, what the tree structure is actually for (and whether it has more to do with physical implementation). Perhaps the purpose of the tree is really to represent something else (e.g. a set of integers).

> 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".

I learnt this from Jan Hidders on this newsgroup. Look for his posts to the thread "database design method" made on Nov 13 2002, particularly where he cites a paper titled "On the completeness of object-creating query languages".

The defining characteristic of an abstract identifier is that its value can be changed without changing the value represented by the structure using the abstract identifier. This assumes the structure is mapped to the value it represents by some non-injective function. For example consider the /canonical projection map/ that maps a graph to an equivalence class over all graphs that are isomorphic to that graph. This leads to the idea that the node identifiers are abstract identifiers.

Consider a pure mathematical function that returns all perfect binary trees of a given height over some finite set of leaf node values. This cannot be regarded as a pure mathematical function if the trees require the allocation of abstract identifiers for their logical representation, such that they are not allowed to clash with independently generated trees. I note that this is exactly what is needed when a function is expressed in terms of other functions that return trees that are to be incorporated into larger trees.

It is noteworthy that Prolog easily supports enumeration of the binary trees of a given height, and an important reason for this is that there are no abstract identifiers involved in the representation.

BTW I don't dismiss the need for abstract identifiers and graph structures more generally. For example, they are required for a representation of an electronic circuit (which cannot be simply expressed in terms of algebraic data types). It is therefore true that a complete query language must be able to allocate abstract identifiers. Received on Mon Jun 13 2011 - 09:40:48 CEST