[Rails] To RForum devs: Writing a reusable NestedSet implementation

[Rick Bradley]

* Sascha Ebach (se at digitale-wertschoepfung.de) [041204 11:03]:
> Wouldn't it be great if we had a "module NestedSet" the would not be 
> dependent on RForum, my CMS (or any other package that might use it) or 
> even Rails/AR. This strikes me as something very useful for development 
> of web apps with complexer content repositories.
> 
> I could imagine myself the following features.
> 
> - CRUD of nodes and trees of course
> - defining your own table layout (maybe you don't want to call your left 
> and right fields 'l' and 'r', but 'lft' and 'rgt'), this would make it 
> possible to hook it into legacy systems
> - fetching the children (subtrees) of a node (all or upto x levels)
> - fetching only the immediate children of a node (by using parent_id)
> - copy/move nodes an whole trees
> - rebuild the the nested set from the parent_id field (already have a 
> method for this)
> - fetching the path to a node (for those breadcrumb trails)
> - displaying the tree by all means of outputs via a separat adapter 
> (class NestedSetOutput), for ex. nested HTML lists 
> (<ul><li><ul><li></li></ul></ul>), graphical trees by GraphViz, forum 
> posts of course, DHTML menus (if one must) and whatever you can think of.
> - being able to use the module without Rails, i.e. AR (like any sane 
> person would ever want to ;)
> - everything well tested, so the developer can concentrate on testing 
> other parts of the system.
> 
> Does that sound interesting to you, too? And this would work by simply doing
> 
> class Post < ActiveRecord::Base
>   inlcude NestedSet::Base
>   include NestedSet::Output::ForumPost
> 
>   # overwrite the standard field names
>   def nested_set_fields
>     {'id'     => 'id',       # key, by which a node is identified
>      'left'   => 'lft',      # left key for nested set
>      'right'  => 'rgt',      # right key for nested set
>      'order'  => 'priority', # for sorting siblings
>      'level'  => 'level',    # level or depth of node
>      'parent' => 'parent_id' # for adjacency list stuff
>     }
>   end
> 
>   # we are good to go. you just saved yourself days of developing
>   # and testing your own tree structure
> 
> end

At first I misread (I think) this to imply that these were binary trees,
but I take it that the 'left' and 'right' fields simply point to the
leftmost and rightmost nodes in the child list of this set/tree node(?).

In a previous lifetime I wrote proprietary CMS software, unfortunately
in PHP, and (un?)fortunately anything worth looking at is all
open-sourced by now.  The product that had the most success was a CMS [0] 
my business partner and I started selling back in 1998 that was based on
a graph model, which looks to be a generalization of the nested set
model.  If nothing else, it's a testament to the fact that there's
someone out there who will pay good money for just about anything.

I did like the way the graph content model worked though.  If I wanted
to re-implement the basic Model in Rails today (which I've considered,
but my calendar hasn't been inclined to entertain) I'd use a few model
classes for the content:

  Graph (id, default root node, some metadata)
  Node  (id, default graph, various data/metadata fields)
  Edge  (id, graph, from node, to node, order)

Nodes contain the content.  Graphs are collections of Nodes and Edges.
Graphs are really multigraphs (i.e., you can have multiple edges from
A->B in a single graph).  A node can appear in any number of graphs.
Edges are ordered, for view rendering purposes.  In the CMS I also had
node names.  A node name is just an alphanumeric unique key (so users
can refer to meaningful names instead of always using numbers) and is
just a convenience.

To render a view you are given either a graph id, a node_id/name, or a
graph id and node id/name.  Then the system basically figures out which
graph this is going to render, and from whence the rendering will start
(a node), using the various defaults available (default graph for a node
or default root node for a graph) if necessary.

The edges for the graph are pulled in from the database and an in-memory
tree is made, starting with a graph traversal from the start node:
basically, do not follow an edge to a node which has already been seen
on the current root-path, which happens to be sufficient to avoid loops,
hence we have a tree suitable for rendering as (say) XHTML.  Then the
nodes actually used in that in-memory traversal are pulled in from
storage and the actual (tree) view is displayed.

For example (leaving out edge ordering information), a graph and 3 views
(based on different start nodes):

    A -> B       (start @ A)      (start @ D)    (start @ C)   
    |    ^         +A               +D             +C         
    v    |           +-B              +-E            +-D       
    C -> D   =>      +-C              +-B              +-E           
         |             +-D                             +-B  
         v               +-E                            
         E                                    

Since the edges for a graph can be pulled in in one operation (a single
query if SQL is the backend), the in-memory traversal is at most linear
in the number of edges (not all nodes will necessarily be encountered),
and the rendered nodes can then be pulled in in one operation, this
tends to be very efficient.

The reason this particular breakdown (mainly separating things into
"graphs") was used was to avoid some of the costs associated with
transitive closure/reduction [1] [2] as stores of content objects get
larger.  The problem is always going to be there, though, it's just a
question of where you draw the boundaries.  Once you allow inclusion of
a tree of outside comment threads in the current comment threads, or in
our case introduce graph-to-graph links (for example to reuse graphs,
even in summary), you start fighting with transitivity again.  By
keeping the level of aggregation near the size of the viewable chunk the
effects of transitivity can be kept under control.

Most of the common operations on trees are trivial to support with this
model, including zooming (view this node and all "children", or follow
"parent" "trees" up a level), reordering, reparenting, reuse, etc.  As
well as some normally difficult CMS operations such as tracking reuse of
content (where else does this item appear?), true objectification
(change this content here and all "copies" change), "copy and paste"
semantics, as well as alternate views with arbitrary multigraph
semantics.

This is just an alternate formulation to nested sets.  The one thing we
learned from building systems in this way (really, before building them
this way) was that transitive closure/reduction really can kill
performance.  In the SQL world if you have to issue a database query for
every layer in a tree (for us every layer in a spanning tree) you will
eventually pay a high price.  If you can aggregate connected components
together so that they can be easily retrieved (/stored/updated/etc.)
then you hopefully won't have to devote as much time to later optimizing
around a slow storage implementation.


[0] http://www.rickbradley.com/code/ce/ (please, forgive the egregious
    PHP, as well as the complete lack of good MVC separation)
[1] http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE163.HTM
    (shame the original book's website appears to be having DNS problems)
[2] http://www.cs.hut.fi/~enu/tc.html

Rick
-- 
 http://www.rickbradley.com    MUPRN: 307
                       |  would have won that game
   random email haiku  |  (as they were eating Auburn
                       |  up there at the stripe).