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 (bigint), lft and rgt (double float) and is_inner (boolean). See the add_mobius_tree_columns method to change the default names.
CREATE TABLE employees ( name TEXT NOT NULL mobius_a BIGINT unsigned, mobius_b BIGINT unsigned, mobius_c BIGINT unsigned, mobius_d BIGINT unsigned, lft DOUBLE unsigned NOT NULL DEFAULT '1', rgt DOUBLE unsigned, is_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 );
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 that 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.
In general, a 'Nested Intervals' model has the same advantages that 'Nested Sets' over the 'Adjacency List', that is to say obtaining all descendants requires only one SQL query rather than several recursive queries.
Additionally, a 'Nested Intervals' model has two more advantages over 'Nested Sets' :
- Encoding is not volatile (no other node has to be relabeled whenever a new node is inserted in the database).
- There are no difficulties associated with querying ancestors.
The Möbius encoding is a particular encoding scheme 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).
This implementation allows you to have several root trees and corresponding trees in your database.
To allow better performance and scaling, Tree::Mobius uses the same Möbius encoding for all leaves (non inner children) of a given node. A unique Möbius encoding is later calculated only if a node becomes 'inner' (having at least one descendant).
The encoding is not volatile, but the depth is constrained by the precision of SQL float type in the right and left column. The maximum depth reachable is 8 levels with a simple SQL FLOAT, and 21 with a SQL DOUBLE. The number of inner nodes of your trees are also constrained by the maximum integer allowed for mobius_a, mobius_b, mobius_c and mobius_d column (see CAVEATS AND LIMITATIONS).
Finally, a tradeoff of DBIx::Class::Tree::Mobius over other models is the non-economical use of 7 SQL columns to encode each node.
Declare the name of the columns for tree encoding and add them to the schema.
None of these columns should be modified outside of this module.
Multiple trees are allowed in the same table, each tree will have a unique value in the mobius_a_column.
Attach a new child to a node.
If the child already has descendants, the entire sub-tree is moved recursively.
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 });
Returns a DBIx::Class Row of the parent of a node.
Returns a DBIx::Class resultset of all children (direct descendants) of a node.
Returns a DBIx::Class resultset of all children (direct descendants) of a node that do not possess any child themselves.
Returns a DBIx::Class resultset of all children (direct descendants) of a node that possess one or more child.
Returns a DBIx::Class resultset of all descendants of a node (direct or not).
Returns a DBIx::Class resultset of all descendants of a node that do not possess any child themselves.
Returns a DBIx::Class resultset of all descendants of a node that possess one or more child.
Returns a DBIx::Class resultset of all ancestors of a node.
An alias method for ancestors.
Returns a DBIx::Class resultset containing the root ancestor of a given node.
Returns a DBIx::Class resultset containing all the nodes with the same parent of a given node.
Returns 1 if the node has no parent, and 0 otherwise.
Returns 1 if the node has at least one child, and 0 otherwise.
Returns 1 if the node has at least one child and is not a root node, 0 otherwise.
Returns 1 if the node has no child, and 0 otherwise.
Returns the smallest mobius index available in the subtree of a given node.
Given a mobius index, return the mobius a,b,c,d column values.
Return the depth of a node in a tree (depth of a root node is 1).
Force a node to become a new tree root (if this node possess a subtree of descendants, it becomes a new tree).
All functions should work as expected until a tree reaches the 'left-right' maximum depth. That is to say 8 levels if you declared the two special columns 'lft' and 'rgt' as a SQL FLOAT, and 21 levels if you declared them as a SQL DOUBLE. In the default 'strict mode', the library will enforce this 'left-right' maximum and will die if you try to add a child deeper.
You may desactivate this check and allow Tree::Mobius to create nodes deeper than this maximum level.
__PACKAGE__->strict_mode( 0 );
In this relaxed mode, only the function 'children' and 'parent' will work correctly and you should not trust the results returned by 'descendants', 'leaves', 'inner_descendants', 'ancestors' for any node deeper than the maximum level.
Please also note that there is a bug in SQLite http://www.sqlite.org/src/tktview?name=1248e6cda8 that prevent use of more than 15 decimal precision FLOAT. A workaround consists of manually restricting the accuracy of float in Tree::Mobius after the add_mobius_tree_columns call :
Math::BigFloat->accuracy(15);
The Möbius representation (using 4 integers a,b,c,d) is limited by the maximum value of the type 'integer' of the corresponding columns in your SQL database. Specifically, this encoding only limits the number of inner nodes (nodes with at least one child) representable on the right side of the tree. The upper limit can be calculated using the least favorable Tree::Mobius inner node materialized path (with the highest index at each level, not counting leaves), either recursively or using matrix multiplication.
For example, a 4 levels depth tree with 5 inner nodes at level 1, 5 children inner nodes at level 2 attached to the rightmost level 1 node, and again 5 children inner nodes at level 3 attached to the rightmost level 2 node, the least favorable inner node materialized path is '5.5.5' The corresponding Tree::Mobius path is derived adding 2 to each index, thus '7.7.7'. The least favorable Möbius representation can now be calculated using the following matrix multiplication:
( 7 1 ) . ( 7 1 ) . ( 7 1 ) = ( 2549 357 ) ( 1 0 ) ( 1 0 ) ( 1 0 ) ( 357 50 )
In our example, a=2549, b=357, c=357 and d=50 and all numbers are within the limits of the database INT or BIGINT type. Thus this tree can be encoded by Tree::Mobius.
Using this method, we can calculate the worst case inner node materialized path for the following inner node depth and the maximum value of a MySQL UNSIGNED INT, that is to say 4294967295.
- 2 levels : 1623.1623 (the 1623th level 1 inner node has maximum 1623th inner descendants) - 3 levels : 253.253.253 - 4 levels : 82.82.82.82 - 5 levels : 38.38.38.38.38 - 6 levels : 21.21.21.21.21.21 - 7 levels : 13.13.13.13.13.13.13
The limits with MySQL UNSIGNED BIGINT (18446744073709551615) are :
- 3 levels : 2642243.2642243.2642243 - 4 levels : 65533.65533.65533.65533 - 5 levels : 7129.7129.7129.7129.7129 - 6 levels : 1623.1623.1623.1623.1623.1623 - 7 levels : 563.563.563.563.563.563 - 8 levels : 253.253.253.253.253.253.253.253 - 9 levels : 136.136.136.136.136.136.136.136.136 - 10 levels : 82.82.82.82.82.82.82.82.82 - 11 levels : 54.54.54.54.54.54.54.54.54.54.54 - 12 levels : 38.38.38.38.38.38.38.38.38.38.38.38 - 13 levels : 28.28.28.28.28.28.28.28.28.28.28.28.28 - 14 levels : 21.21.21.21.21.21.21.21.21.21.21.21.21.21 - 15 levels : 17.17.17.17.17.17.17.17.17.17.17.17.17.17.17 - 16 levels : 13.13.13.13.13.13.13.13.13.13.13.13.13.13.13.13 - 17 levels : 11.11.11.11.11.11.11.11.11.11.11.11.11.11.11.11.11 - 18 levels : 9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9 - 19 levels : 8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8 - 20 levels : 7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7.7 - 21 levels : 6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6.6
For all these scenarios, there are no constraint with the number of leaves at any level.
Finally, early testers should note that the encoding used since version 0.2000 is not compatible with the old encoding tested in experimental developper versions 0.00002_01 and 0.00001_04.
The Möbius encoding (ax+b)/(cx+d) can represent a tree giving the following relationship between each parent node and it's nth child :
Parent encoding = [ Pa, Pb, Pc, Pd ] Child encoding = [ Pa * n + Pc, Pb * n + Pd, Pa, Pb ]
Tree::Mobius can encode several trees using the convention that root nodes of these trees are in fact children of an abstract mathematic super root node (there will be no row in your database for it).
The Möbius represention of this super root node is (a, b, c, d) = ( 1, 0, 0, 1 )
To install DBIx::Class::Tree::Mobius, copy and paste the appropriate command in to your terminal.
cpanm
cpanm DBIx::Class::Tree::Mobius
CPAN shell
perl -MCPAN -e shell install DBIx::Class::Tree::Mobius
For more information on module installation, please visit the detailed CPAN module installation guide.