xml-dev - RE: The Power of Groves: The VRML View

["Didier PH Martin" <martind@netfolder.com>]

Hi,

Steve said:
I started this thread because
I wanted some feedback, some assurance that I wasn't heading down a
dead-end path. I wanted to hear success stories, but I also wanted to
hear failure stories, from people who tried groves or DSSSL or HyTime
or XML or something similar, and couldn't get it to work. That's why
I'm curious about the history of VRML. It's all part of the analysis.

Didier replies:
I would answer that the limits of the DOM are probably also the limit of the
actual data structures. Not more, not less. So, this is not a gold bullet
made to replace the silver bullet :-)

Now a bit of reflection and less politics :-)

Question: what can you do with a recursive construct? You get the answer
from the last 20 years especially from the functional programming area where
loops are most of the time replaced by recursive construct.

Question: Have you heard about the composite pattern (Gamma & al.)? This is
a recursive construct used to build tree or hierarchical structures.

Question: What is a tree or hierarchical structure from the data structure
point of view? A tree can be perceived as an array of arrays. If each
element of an array can be an array, you then have a tree. We call this a
recursive structure.

Question: What is the Grove atom? Its the node. A node could be used to
build recursive constructs such as hierarchical structures if one of the
node's properties is a list of nodes. And that each member of this last
collection can also contain a list of nodes property.

Question: what is a node? A node is a collection of properties.

Question: How can we create nodes? nodes are created directly through an API
or by an XML/SGML interpreter.

Question: Is there a direct relationship between XML elements and nodes? yes
but not necessarily. The nodes may or may not include the information
contained in the document. It is the interpreter that decide which
information to include in the nodes. The interpreter may include the
information contained in the XML document, or add additional information
based on its interpretation of the orginal document information. There is no
necessary one to one relationship between the oginal document and the Grove.
The interpreter interprets the data contained in the document and update the
data model in accordance to its interpretation of the data. Maybe, this is
why we call this gizmo an interpreter :-)

Question: What is the kind of procedural breakdown that you experiment with
the relational model? The relational model is based on the array structure
(or more precisely on the associative array structure). You can model
hierarchies with this latter but at the expense of redundancy of data. If a
hierarchical structure is a an array of array, in contrast, the relational
model is simply a model based on arrays. Groves hierarchies could be built
on arrays of arrays if you choused so. We can also say that a Grove could be
build on a list of lists if you choused so. Or a Grove could be built on the
relational model if a record's field can point to a table. Thus, it is even
possible to implement a Grove on a RDB.

Question: What are the different choices of mapping between the abstract
Grove and classical data structures? Mainly list of lists to keep the order.
You can also choose vectors or dynamic arrays (that also keeps the order but
at the expense of the update time). If you want direct access by name to the
list members, you may also choose to keep an associative array or hash table
in addition to the list. Or use a B+ tree which combine both (but is more
expensive than a combination of hash table and list). In all cases, the
Grove is somewhat independent of the data structure chosen. What is
important is that a Grove is a collection of nodes, each node in this
collection can also contain a collection of nodes. The collection
implementation is yours. Don't get fooled by the word "nodelist". You
internal structure may have nothing to do with list. What is important is
that the collection is to be an ordered collection.

Why don't we talk about the real stuff instead of talking like politicians?

Your question is: Can I use Grove to model things? the answer is: Yes as
long as the domain problem to be resolved requires a hierarchical structure
of frames.

Did people experimented problems with the Grove model? yes if they tried to
resolve a problem domain that could have been better resolved with a
different structure (or more efficiently with a different structure). For
instance, I would use a relational DB to store my address list because it is
implemented to be very efficient to store and retrieve elements from an
associative array. However, if a Grove implementation offers that - in
addition to having strictly ordered collection - I have, an associative
array access. And that, on top of all this, it is as fast as actual highly
optimized RDBs, then I would use a Grove. The limits therefore are not the
Grove paradigm but more the implementation. The grove paradigm include the
notion of RDB and can even be implemented on a RDB.

Is it possible to have a fast implementation? yes, I personally implemented
a fast grove model using STL lists to store the strictly ordered collection
and STL maps to provide an associative array access to the collection
elements. This way, I can navigate the list in a strictly ordered way and
have access to any of the collection member by name. The whole stuff is
written in C++ and store in a object data base allowing memory mapped
access. My first implementation used Black and red based maps, my latest
uses hash table based maps. My next one will probably let you fine tune the
kind of collection based on the type of keys used. So, as you can see, it is
possible to have a very fast access Grove implementation. Grove is not so
hard stuff: it is a collection of collections.

Implementation hints?
when you create a collection with the basic requirement of keeping the
element's order then, if you have also to insert elements everywhere in the
collection, use a list. You now have an ordered collection. Then, if you
also need a fast access by keys, use either an associative array (i.e. an
STL map) or a hash table. Each element that you include in your collection
could be (a) an object, (b) a structure, as long as it contains:
- a property name
- a pointer to a data, the data could be an other collection.

The pointer to the data allows you to include any kind of data. However, you
may as certain script languages choused to implement this as a Variant or
structure allowing you more than one data type. The Variants are used mainly
in interpreted languages.

Definitions:
frame: a property set. Term used in AI. Is equivalent to a record or a
collection of properties. It allows more complex propertiy data type such as
collections than usual records that only allows simpler data elements.

recursive structure: a hierarchical structure could also be said to be a
recursive structure if it is constructed with the same entities. For
instance, a Grove structure is a recursive structure because its basic
element is the node. Each node can itself contains a collection of nodes.

Steve, was I clear enough, do you need more explanations?

Cheers
Didier PH Martin
----------------------------------------------
Email: martind@netfolder.com
Conferences: Web New York (http://www.mfweb.com)
Book to come soon: XML Pro published by Wrox Press
Products: http://www.netfolder.com