SYNOPSIS

Create a table for your tree data with the 7 special columns used by Tree::Mobius. By default, these columns are mobius_a mobius_b mobius_b and mobius_d (integer), lft and rgt (float) and inner (boolean). See the add_mobius_tree_columns method to change the default names.

            

              
              
CREATE TABLE employees (
  name TEXT NOT NULL
  mobius_a integer(11) unsigned,
  mobius_b integer(11) unsigned,
  mobius_c integer(11) unsigned,
  mobius_d integer(11) unsigned,
  lft FLOAT unsigned NOT NULL DEFAULT '1',
  rgt FLOAT unsigned,
  inner boolean NOT NULL DEFAULT '0',
);
            
          

In your Schema or DB class add Tree::Mobius in the component list.

            

              
              
__PACKAGE__->load_components(qw( Tree::Mobius ... ));
            
          

Call add_mobius_tree_columns.

            

              
              
package My::Employee;
__PACKAGE__->add_mobius_tree_columns();
            
          

That's it, now you can create and manipulate trees for your table.

            

              
              
#!/usr/bin/perl
use My::Employee;
my $big_boss = My::Employee->create({ name => 'Larry W.' });
my $boss = My::Employee->create({ name => 'John Doe' });
my $employee = My::Employee->create({ name => 'No One' });
$big_boss->attach_child( $boss );
$boss->attach_child( $employee );
            
          

DESCRIPTION

This module provides methods for working with trees of data using a Möbius encoding, a variant of 'Nested Intervals' tree encoding using continued fraction. This a model to represent hierarchical information in a SQL database. This model takes a complementary approach of both the 'Nested Sets' model and the 'Materialized Path' model.

The implementation has been heavily inspired by a Vadim Tropashko's paper available online at http://arxiv.org/pdf/cs.DB/0402051 about the Möbius encoding.

A 'Nested Intervals' model has the same advantages that 'Nested Sets' over the 'Adjacency List', that is to say that obtaining all descendants requires only one query rather than recursive queries.

Additionally, a 'Nested Intervals' model has two advantages over 'Nested Sets' :

- Encoding is not volatile (no other node should be relabeled whenever a new node were inserted).

- There are no difficulties associated with querying ancestors.

The Möbius encoding is a particular encoding schema of the 'Nested Intervals' model that uses integer numbers economically to allow better tree scaling and directly encode the material path of a node using continued fraction (thus this model also relates somewhat with the 'Materialized Path' model).

The tradeoffs over other models is in this implementation the use of 7 SQL columns to encode each node.

Since the encoding is not volatile, the depth is constraint by the precision of FLOAT in the right and left column. The maximum depth reachable is 8 levels with a simple SQL FLOAT, and 21 with a SQL DOUBLE.

This implementation allows you to have several trees in your database.

METHODS

add_mobius_tree_columns

Declare the name of the columns for tree encoding and add them to the schema.

None of these columns should be modified outside if this module.

Multiple trees are allowed in the same table, each tree will have a unique value in the mobius_a_column.

attach_child

Attach a new child to a node.

If the child has descendants, the entire sub-tree is moved recursively.

insert

This method is an override of the DBIx::Class' method.

The method is not meant to not be used directly but it allows one to add a parent virtual column when calling the DBIx::Class method create.

This virtual column should be set with the primary key value of the parent.

            

              
              
My::Employee->create({ name => 'Another Intern', parent => $boss->id });
            
          

parent

Returns a DBIx::Class Row of the parent of a node.

children

Returns a DBIx::Class resultset of all children (direct descendants) of a node.

leaf_children

Returns a DBIx::Class resultset of all children (direct descendants) of a node that do not possess any child themselves.

inner_children

Returns a DBIx::Class resultset of all children (direct descendants) of a node that possess one or more child.

descendants

Returns a DBIx::Class resultset of all descendants of a node (direct or not).

leaves

Returns a DBIx::Class resultset of all descendants of a node that do not possess any child themselves.

inner_descendants

Returns a DBIx::Class resultset of all descendants of a node that possess one or more child.

ancestors

Returns a DBIx::Class resultset of all ancestors of a node.

ascendants

An alias method for ancestors.

root

Returns a DBIx::Class resultset containing the root ancestor of a given node.

siblings

Returns a DBIx::Class resultset containing all the nodes with the same parent of a given node.

is_root

Returns 1 if the node has no parent, and 0 otherwise.

is_inner

Returns 1 if the node has at least one child, and 0 otherwise.

is_branch

Returns 1 if the node has at least one child and is not a root node, 0 otherwise.

is_leaf

Returns 1 if the node has no child, and 0 otherwise.

available_mobius_index

Returns the smallest mobius index available in the subtree of a given node.

child_encoding

Given a mobius index, return the mobius a,b,c,d column values.

depth

Return the depth of a node in a tree (depth of a root node is 1).

cpanm DBIx::Class::Tree::Mobius

perl -MCPAN -e shell
install DBIx::Class::Tree::Mobius