[Dbix-class] Representing directory structures

[Peter Rabbitson]

On Mon, Apr 08, 2013 at 02:43:12AM -0400, Len Jaffe wrote:
> On Sun, Apr 7, 2013 at 6:19 PM, Bill Moseley <moseley at hank.org> wrote:
> 
> >
> > On Sun, Apr 7, 2013 at 12:40 PM, Len Jaffe <lenjaffe at jaffesystems.com>wrote:
> >
> >> In my opinion, the best way to model a tree in an RDBMS is to use
> >> Materialized Path.
> >>
> >> I found the amount of work involved in each insert/delete of a nested set
> >> to be too great, and adjacency lists (parent pointer) fails to allow for
> >> retrieving all of a tree or subtree with one round-trip to the db.
> >>  Materialized Path does not suffer these drawbacks.
> >>
> >> I recall there being a couple of MP modules available for DBI and DBIC.
> >>
> >
> > Thanks, I will look at these again.  When I looked at using Materialized
> > Path before the expense of updates (e.g. moving a node from one location to
> > another) for a very large tree could be prohibitive.  That is, moving a
> > parent involved updating every child item's path.
> >
> > I agree. But when you compare that cost to the cost of doing any
> insert/delete/move using nested sets, MP looks like a clear winner.  Plus,
> the good** RDBMSes have functions that will allow you to implement updates
> of the form s/XXXX/YYYY/ (syntax will vary).
> 
> In postgres you can say update something set mpath = regexp_replace(mpath,
> oldprefix, new prefix) where mpath like 'old_prefix%';
> 
> 
> ** for various values of good
> 
> 
> > For representing a "file system" I would normally only need to show the
> > contents of a single node (folder) at any giving time which would be a
> > single query for Adjacency model -- but to show the path to any given node
> > would require a recursive query up the tree -- e.g. to fetch the path to
> > the current node.
> >
> 
> This is where materialized path excels.
> 

For completeness (and mostly off original topic) there is another 
approach to represent the materialized path via continuous fractions [1] 
and there is a DBIC-based implementation on CPAN [2]. While it is 
"metadata-heavy" and it has constraints on the tree depth, it has the
distinct advantage of *not* requiring update of "sibling" records when 
you remove something from a set.

Cheers

[1] http://arxiv.org/pdf/cs.DB/0402051
[2] https://metacpan.org/release/DBIx-Class-Tree-Mobius