Suggested implementation for Trees in Propel

-- submitted by Joe Simms

Trees can be stored using several approaches in databases: http://www.sitepoint.com/article/hierarchical-data-database

Adjacency List Model

  • id
  • parent_id (self referencing, store id)
  • name

Modified Preorder Tree Traversal (Nested Set)

  • id
  • lft
  • rgt
  • name

And the current approach integrated into Propel, which doesn't seem to have an official name, but i have called it the Path List Model, where it actually stores the path to the root node as oppose to just the parent, like adjacency list does.

Path List Model Materialized Path (thanks Ants)

  • id
  • path (example 1.13.16.21)
  • name

So for the purpose of Propel, these will be known as:

  1. Adjacency List
  2. Path List Materialized Path
  3. Nested Set

How to unify the integration of these within Propel.

Firstly, within all trees, we must traverse the tree, see: http://en.wikipedia.org/wiki/Pre-order_traversal

The above describes different methods of traversing the tree, the most common in website development is pre-order, hence why the nested set model is so good (Modified Pre Order Traversal).

Also, the current integration of trees in Propel, the now known as the Path List Model, uses the PHP5 standard library Iterator classes, please see here for more information (have a look at these classes as well, just add isTree="true" to your table and build-om): http://www.sitepoint.com/print/php5-standard-library http://uk.php.net/manual/hk/language.oop5.iterations.php

So, to cut to the chase, to implement tree manipulation properly into Propel, i believe the following approach to be the best: tree="nestedset | pathlist | adjacencylist"

If tree is set then each individual approach has its own Peer Builder to produce the Peer classes:

  • PHP5NestedSetTreePeerBuilder produces ObjectTreePeer
  • PHP5AdjacencyListTreePeerBuilder produces ObjectTreePeer
  • PHP5PathListTreeBuilder produces ObjectTreePeer

Now all these builders must build classes that implement PropelTree, a class that defines all the method names used for tree manipulation in Propel, to ensure they use the correct naming conventions

So, depending on the table name the builder will produce:

  • ObjectTreePeer (implements PropelTree)

People can override these builder classes in the propel-properties file, like so: 

propel.builder.node.class = propel.engine.builder.om.php5.PHP5NodeBuilder
propel.builder.nestedsetpeer.class = propel.engine.builder.om.php5.PHP5TreeNestedSetPeerBuilder
propel.builder.ajacencylistpeer.class = propel.engine.builder.om.php5.PHP5TreeAdjacencyListPeerBuilder
propel.builder.pathlistpeer.class = propel.engine.builder.om.php5.PHP5TreePathListPeerBuilder

So we need to decide what methods this peer class should have and what methods we should have in the PropelNode class, i will put these together as i am now looking into more detail how the previous guy did his integration, as i didn't understand the Iterator stuff before ;)

Also, now the interesting bit, remember Iterators discussed above, Propel must supply the following, to allow us to Traverse the Trees for each of the traversal methods mentioned above and for each approach, so it would have: 

NestedSetPreOrderNodeIterator implements Iterator

NestedSetPostOrderNodeIterator implements Iterator

NestedSetLevelNodeIterator implements Iterator

and the same for AdjacencyList and PathList

and then the class Node implements IteratorAggregate (which when getIterator() is called returns appropriate one of the above). Reading the above will make more sense, also see the other guys stuff.

So, how does this all come together. We will simply have PHP5NodeBuilder, which is used for all trees, it will build an ObjectNode Class.

I believe that as this is INHERENT to the model, that the BaseModel class should inherit the ModelNode class which inherits BaseObject. This follows the Propel inheritance approach as well, so:

  • Model < BaseModel < ModelNode (implements IteratorAggregate) < BaseObject
  • Peer < BasePeer
  • ModelTreePeer

And the resultant classes built are therefore:

  • Model, BaseModel, ModelNode
  • Peer, BasePeer, TreePeer

Therefore no additional stubs are produced at all!!!!! Why does TreePeer need a stub class, it doesn't, any additional peer methods can be added to the object peer, and wrap the peer tree methods if necessary. Why does the node need a stub, it can't as it is now inherited, which makes more sense.

The BasePeer could also inherit the TreePeer so:

????Peer < ????BasePeer < ????TreePeer

OK, so it has taken a while for me to get to this way of thinking, but i feel really happy that this would be the best approach.

Any feedback, apart from lots to read.

Hope this all makes sense, just need to finalise the approach and then eventually write an AdjacencyListBuilder and we have fully supported trees in Propel. Brilliant!

Attachments