pangyre / p5-dbicx-materializedpath Goto Github PK

NAME
    DBICx::MaterializedPath - DBIx::Class plugin for automatically tracking
    lineage paths in simple data trees.

PREFER
    Please see DBIx::Class::Tree::Mobius, DBIx::Class::Graph, and
    DBIx::Class::Tree instead of this experimental package.

SYNOPSIS
    We need a table, or tables, which represents a tree.

     CREATE TABLE tree_data (
        id INTEGER PRIMARY KEY NOT NULL,
        parent INT(10),
        content TEXT NOT NULL,
        path VARCHAR(255),
        created DATETIME(19) NOT NULL
     );
 
     CREATE INDEX tree_data_idx_parent ON tree_data (parent);

    In your DBIx::Class add this to your components–

     use warnings;
     use strict;
     use parent qw( DBIx::Class );
 
     __PACKAGE__->load_components(qw(
                                     +DBICx::MaterializedPath
                                     Core
                                     ));
     # Et cetera.
     __PACKAGE__->parent_column("parent"); # default "parent"
     __PACKAGE__->path_column("path");     # default "materialized_path"
     __PACKAGE__->path_separator(".");     # default "/"
     __PACKAGE__->max_depth(10);           # default "500"

DESCRIPTION
    Note, this is an experimental package and not sanctioned by the DBIC
    core devs.

    Uses a column of a table with a tree structure to keep track of lineage.
    An example lineage showing primary key ids–

     #  1 -> 2 -> 3 -> 10 -> 999 -> 8 -> 42

     my $rec = $result_source->find(999);
     say $rec->parent->id; # prints "10"

    It's trivial to find the parent and easy to recurse on the parent to
    find all ancestors. With a deep tree it becomes somewhat expensive. Take
    the example above, for example. If you want to get the entire lineage
    for the record with id "42" you have to do six queries against the
    database. If you maintain a materialized path you only have to do one.

    Consider our record "42" again. With its path 1/2/3/10/999/8/42 we can
    easily find all its parents–

     my $path = "1/2/3/10/999/8/42";
     my @ancestor_ids = split '/', $path;
     pop @ancestor_ids; # Remove the self id.
     my @ancestors = $result_source
                          ->search({ parent => { -in => \@ancestor_ids },
                                   { order_by => \"LENGTH(path)" });

    We can thank the great and powerful Ovid's co-worker Mark
    Morgan—<http://use.perl.org/~Ovid/journal/39460>—for the sorting
    solution for ensuring the proper order of ancestors is returned.

    See also *Trees in SQL: Nested Sets and Materialized Path*, Vadim
    Tropashko, <http://www.dbazine.com/oracle/or-articles/tropashko4>.

  CAVEAT
    This package requires your table has a single primary key and a method
    to look up a parent record by its single primary key.

METHODS
    [path method]
        Whatever column you set for your materialized path. In the
        "SYNOPSIS" code it is set to "path" to match the sample table
        definition. The default if you don't set one is "materialized_path".
        This will, of course, cause errors if there is no such column in the
        table.

    ancestors
        Searches on the materialized path ids excepting the object's own.
        This is generally cheap because it uses the path instead of
        recursion.

    get_root
        Returns the root object for a given record.

    grandchildren
        Return all children and grandchildren.

    node_depth
        Returns 1 for a record with no parent.

    root_node
    siblings
    max_depth
        Set this to assert a maximum tree depth. Default is 500.

    set_materialized_path
        Probably shouldn't mess with this. It's used by "insert" and
        "delete".

  OVERRIDDEN METHODS
    insert
        Sets the materialized path.

    update
        Updates which change the parent of a record necessarily cascade
        through all their children and grandchildren to recompute and set
        their new materialized paths. E.g., given this tree–

                          1
                          |
                          3
                         / \
                       12   8
                      /\    /\
                     5 13  7  4

        You get paths including 1/3/12/13 and 1/3/4. Let's say we change
        record 3's parent from 1 to 2–

                          2
                          |
                          3
                         / \
                       12   8
                      /\    /\
                     5 13  7  4

        The change is simple and it's obvious you have to update record 3
        but you just broke the materialized path for records 4, 5, 7, 8, 12,
        and 13. In a big tree you may have broken hundreds or even thousands
        of paths with a single parent change. So we have to process all
        descendants. Our example paths become 2/3/12/13 and 2/3/4. Again, it
        may seem trivial but it may be expensive depending on the tree's
        depth and breadth. This simplistic example will require three
        database reads—children of 3, children of 12, children of 8—and six
        updates—each of 4, 5, 7, 8, 12, and 13. This doesn't even count the
        original expense of finding and updating 3 itself. But the point
        here is that we should have a write seldom, read often situation and
        this up front expense may save exponentially with regards to ongoing
        query costs.

CAVEATS
    If your materialized path column is insufficiently large you're going to
    have problems. A "VARCHAR(255)" is only wide enough to support a tree
    which is 35 nodes deep if the average PK values are integers in the
    millions. This might be fine for your usage. Just be aware path tracking
    is not arbitrary, it's limited to the column's width.

TO DO
    Better documents; obviously.
    More tests; what else is new?
        One set with nothing changed: use default column names.

        One set with everything changed.

CODE REPOSITORY
    <http://github.com/pangyre/p5-dbicx-materializedpath>.

SEE ALSO
    DBIx::Class::Ordered, DBIx::Class.

  WHY NOT DBIx::Class::Ordered?
    There are data sets which have implicit, or even tacit,
    ordering—�position“ in DBIx::Class::Ordered parlance– in the data
    already. Published articles, for example, will be naturally ordered
    chronologically. Additional position tracking becomes complex and
    redundant in this kind of case. You can even run into cases where both
    types of ordering are necessary like a collection of dictionaries. Each
    dictionary's terms are ordered alphabetically while each term's
    definitions would be ordered by a position set at editorial discretion.

AUTHOR
    Ashley Pond V · [email protected] · <http://pangyresoft.com>.

LICENSE
    You may redistribute and modify this software under the same terms as
    Perl itself.

DISCLAIMER OF WARRANTY
    Because this software is licensed free of charge, there is no warranty
    for the software, to the extent permitted by applicable law. Except when
    otherwise stated in writing the copyright holders and other parties
    provide the software "as is" without warranty of any kind, either
    expressed or implied, including, but not limited to, the implied
    warranties of merchantability and fitness for a particular purpose. The
    entire risk as to the quality and performance of the software is with
    you. Should the software prove defective, you assume the cost of all
    necessary servicing, repair, or correction.

    In no event unless required by applicable law or agreed to in writing
    will any copyright holder, or any other party who may modify or
    redistribute the software as permitted by the above license, be liable
    to you for damages, including any general, special, incidental, or
    consequential damages arising out of the use or inability to use the
    software (including but not limited to loss of data or data being
    rendered inaccurate or losses sustained by you or third parties or a
    failure of the software to operate with any other software), even if
    such holder or other party has been advised of the possibility of such
    damages.