vdg wrote:
Hello all,
I have implemented a new dbic component to manage trees.
It's an alternative method to DBIx::Class::Tree::AdjacencyList and
DBIx::Class::Tree::NestedSet.
Basically it's the implementation of the general method describe in this
paper :
http://arxiv.org/pdf/cs.DB/0402051
with this model, you keep the advantage of NestedSet to query
descendants without difficulties querying ancestors.
Plus the encoding is not volatile (no need to recalculate half of the
tree encoding after an insert) and there is
a direct correspondence between the materialized path of a node and its
encoding. The model is described in the paper
are more scalable, but i've yet to make some tests to get an idea how
deep you can build down in a tree.
This implementation don't use at all the primary key of the table (if
any) and don't try to order children.
Ordered tree could be a sub component i guess.
The only trade-off is that i use 7 (!) columns to do the encoding.
github : http://github.com/vdg/DBIx-Class-Tree-Fast
Comments and ideas very welcome off course.
This looks very VERY interesting. I can not comment much on the code, as
I have to admit I don't understand much of it :D (time to read the paper)
However may I kindly request to not release the module with this
particular name? ::Fast (just like ::Simple) does not convey what in fact
the module implements. Also I suspect a single-column MatPath implementation
(using anchored LIKE) will be faster than your module when dealing with shallow
trees, thus making the name even more misleading.
Is there maybe some sort of formal name for the technique you implemented, which
you can use instead of ::Fast?
Awesome work otherwise!
Cheers
_______________________________________________
List: http://lists.scsys.co.uk/cgi-bin/mailman/listinfo/dbix-class
IRC: irc.perl.org#dbix-class
SVN: http://dev.catalyst.perl.org/repos/bast/DBIx-Class/
Searchable Archive: http://www.grokbase.com/group/[email protected]
