[Dbix-class] RFC: DBIx-Class-Tree

Or from the nightly snapshots -

http://dev.catalyst.perl.org/snapshots/bast/

Oh, and I'd like to add that the first release of this will depend on
DBIx::Class 0.07000 shipping, so it will most likely be a bit longer
than a week! This is because DBIC:Tree::AdjecencyList::Ordered depends
on the new DBIC:Ordered module, which is not in 0.06000, but has been in
the DBIC subversion repo for a while.

Aran

If nobody's massively offended by the idea I think I'd like to roll the
::Ordered component into 0.06001 along with the SQLT deploy improvements in
-current.

What do people think of this idea?

If nobody's massively offended by the idea I think I'd like to roll the
::Ordered component into 0.06001 along with the SQLT deploy improvements in
-current.

What do people think of this idea?

Alan,

There is this fuzzy dividing line between what should and should not be
included in the core DBIC distro. The general idea is that anything
that does not add external dependencies, and is a common paradigm that
people deal with on a regular basis, then it is a potential candidate
for inclusion. Ordered was deamed worthy, and thus included.

The docs can be easly read by perldoc'ing the source at:

http://dev.catalyst.perl.org/repos/bast/branches/DBIx-Class-current/lib/DBIx/Class/Ordered.pm

Aran

Thanks Aran. After looking at the code here are my questions/comments:

- The module requires a "position" column in the underlying table to
maintain some notion of order. How common is this practice? I've never
done it, but that doesn't mean anything.

- How well will the module play with auto-increment columns? I see the
insert and delete methods expect to be able to update the position column at
will, so you probably wouldn't want to use an auto-increment column for your
position. Maybe a note in the doc?

- What's a typical use case for this? Since every move_* method results in
a call to the database, you wouldn't want to use it for rapid traversal of a
table. When would you use it?

I'm not convinced it belongs in the main distribution.

- Alan

-----Original Message-----
From: dbix-class-bounces at lists.rawmode.org
[mailto:dbix-class-bounces at lists.rawmode.org] On Behalf Of Aran Deltac
Sent: Monday, April 03, 2006 9:14 AM
To: dbix-class at lists.rawmode.org
Subject: Re: [Dbix-class] RFC: DBIx-Class-Tree

Alan,

There is this fuzzy dividing line between what should and should not be
included in the core DBIC distro. The general idea is that anything
that does not add external dependencies, and is a common paradigm that
people deal with on a regular basis, then it is a potential candidate
for inclusion. Ordered was deamed worthy, and thus included.

The docs can be easly read by perldoc'ing the source at:

http://dev.catalyst.perl.org/repos/bast/branches/DBIx-Class-current/lib/DBIx
/Class/Ordered.pm

Aran

_______________________________________________
List: http://lists.rawmode.org/cgi-bin/mailman/listinfo/dbix-class
Wiki: http://dbix-class.shadowcatsystems.co.uk/
IRC: irc.perl.org#dbix-class
SVN: http://dev.catalyst.perl.org/repos/bast/trunk/DBIx-Class/

document has_many pages: pages need to be ordered

menu has_many links: links need to be ordered

host has_many MXes: MXes need to be ordered

ACL has_many rules: rules need to be ordered
If "Don't use auto-increment for a column containing actual application data"
isn't obvious to somebody, the odds of them being able to design a database at
all seem pretty minimal to me.
I think given it's lightweight, self-contained and represents a fairly common
case any time you're modeling semantic data it might as well be.

I think it's a nice idea.
But while reading its source code something seemed odd to me:

sub insert {
my $self = shift;
my $position_column = $self->position_column;
$self->set_column( $position_column =>
$self->result_source->resultset->search( {$self->_grouping_clause()}
)->count()+1 )
if (!$self->get_column($position_column));
return $self->next::method( @_ );
}

There really isn't a better (i.e. more efficient) way of doing this?
Or is this preferred as it's probably the most "portable" solution
accross the various database backends?

I also couldn't figure out from the docs how that "grouping" stuff
really works, but this is probably just my slow brain. ;-)

-Nilson Santos F. Jr.

I'm not seeing how this is inneficient - the only query that is actually
run against the DB is a COUNT(*). All the rest of this code is
detecting whether that query needs to be run.
The docs cover all the methods, but are not verbose by any means. I bet
you are right that the grouping stuff needs a little more TLC. If you
can tell me what about it didn't make sense then I will have a better
time making the docs for grouping easier to read.

Thanks,

Aran

Well, I don't know what it didn't make sense because I really didn't get it.
I still don't know what it does, maybe when I get home I'll play a
little bit with it and find out.

-Nilson Santos F. Jr.

Here's an example: You are writing a tool for storing bookmarks of web
pages. You want to be able to change the order of the bookmarks and
have the ability to support multiple users having their own bookmarks
seperate from everyone else, so you'd make the table look like:

bookmarks ( bookmark_id, user_id, position, title, url );

Then you'd position_column('position') and
grouping_column('user_id'). Then whenever you call one of the move_*,
insert, or delete methods it will only modify the position of objects
that have the same user_id as the one that you called the method on.

Make sense?

Aran

Yes, it does make sense. Thanks for clarifying.
Maybe you could explain this just a little bit more in the docs
(although, now it seems obvious to me, but maybe it's better to
"over-document").

-Nilson Santos F. Jr.

I don't use DBIC yet - I'll likely change from CDBI next time I revisit
my model code - but I do use trees, so I was interested to see this.


AdjacencyList

parent - what does the code actually do if you try to make an object the
root? The Description says the root is the 'row with a Parent ID of 0'
but I can't see how that would ever get set.

method return values - the docs don't state the return values. Since
accessor/mutators normally always return the current attribute value,
the fact that these don't really needs to be made VERY clear. BTW,
what's the rationale for the values that are returned?

attach_child - DBIC follows the CDBI convention of add_to_*. So why not
call this method add_to_children? The description could also be clearer.
The method could also take a list of new children.

attach_sibling - same issue with name and possible list of arguments.


Ordered

position_column & parent_column - since they both have to be called
exactly once in a specific order, it might be worth considering
combining them into a single method.

Is the ordering really restricted to a single column rather than some
predicate? Could that be relaxed?

position_column - this method is not listed.

attach_before - $this->attach_before($that) reads as "this attach before
that" but attach_before actually attaches that rather than this so IMHO
a different name would be better. I can't think of one I like -
add_senior_sibling?

attach_after - same issue as attach_before

_grouping_clause - this is deeply worrying. It overrides a private
method of a base class that is marked in that class as "These methods
are used internally. You should never have the need to use them." So
there's something wrong somewhere!


Minor typo stuff:

"add .. to the top of the .. list" => "add .. to the front of the ..
list" or is that a US => UK thing?


General Comments

There're no traversal methods (depth-first or breadth-first, all nodes
at level 5 etc) or classification predicates (is_leaf etc). I guess you
plan to add those?

When you generalize the API for other representations, it would be nice
if it could also handle DAGs.

I must confess to a prejudice. I have a wariness about trees/graphs in
databases. I tend to build the tree in memory and interrogate/manipulate
it there, using the database only as a backing store. The tree structure
itself is usually quite small compared to current memory sizes, even if
it contains 100,000 nodes or so. So something that automatically cached
the tree and knew which nodes needed writing back at a checkpoint would
probably be more use to me.

Cheers, Dave

Its up to you. For example, if you parent column is parent_id then you
could do $obj->parent_id( 0 ); or $obj->parent( 0 ), or if you're
creating a new object you could either specify it in the ->create({
parent_id=>0 }) or in the table definition as in "parent_id INTEGER NOT
NULL DEFAULT 0".

I've added a small comment to this effect under the parent() method.
Good point - I've modified the docs to include this information where I
had missed putting it in.
Return 1 on success and 0 on minor errors, throw exceptions (croak) on
harder errors.
Because Matt asked me to follow the DOM naming conventions, which I think
I have to the best of my ability. Some of the method names I've chosen
are not directly from the DOM methods, but are heavly influenced by them.
That could be. No good name pops right off the top of my head, so I'll
let this one lie - it can be tacked on any time.
It could be relaxed. But I'm not sure exactly how best to handle it.
Its a good idea - I'll keep it in mind.
Its in the Ordered component. Any method that exist in
Tree::AdjacencyList or Ordered components is not shown in
Tree::AdjacencyList::Ordered component. I've added a section listing
the methods that are made available via these other two components. You
would still need to read the related component's POD for detailed docs
on the methods.
The _grouping_clause method was designed specifically for people that
want to subclass Ordered (as Tree::AdjacencyList::Ordered does) and want
to extend how Ordered groups the objects. That being said, I think the
whole idea can be scrapped. Done.
Good catch. Nah, this is a we used to call before/after up/down thing
and there are still some remnants of the up/down concept. Fixed.
That will be implimented with a seperate DBIC::Tree::Visitor set of
components such as how Tree::Simple::Visitor does it.
Yes, I plan to add thos. is_leaf is a good one, which makes me think
is_parent, is_branch, and is_root are good ones as well. Any more?
A DAG is a bit of a different beast than a Tree, but I'll keep it in
mind. Sounds like a deffinate possibility.
Good idea, maybe we'll have a Tree::Cached component one day.

I've commited all of the above changes.
Thanks for all the input Dave!

Aran

Or just turn caching on on the resultsets?

Ah, right, which brings me back to implimenting cacheing on the resultset
when requesting descendants() and ancestors(). TODO.

Aran

I think we're at cross-purposes here. My question was what actually
happens if I call $obj->parent(0)? My reading of the docs says it should
set parent_id to zero; my reading of the code says it does no such thing.
Urgh, IMHO :) What's special about the DOM that it deserves such
respect? And worth breaking internal consistency for? It would be nice
to have a mention in the docs to explain the apparent inconsistency
(ideally to the source of the names, because I haven't been able to find
a fair few with a bit of googling).
I appreciate this dilemma. As the reader in this instance, I can just
point out that this policy makes it more difficult to use the module. If
I were the maintainer, I might well have a different opinion :)
Well, a tree is a special case of a DAG, so an interface that can handle
DAGs can handle trees, but not necessarily vice versa.

Cheers, Dave

Well, I suggested it because I didn't have a better idea - and the DOM is
probably the single best-known tree API. Doesn't mean we can't come up with
something better - anybody want to sketch out a better set of names for the
methods?
Which brings us back to a regular problem with DBIC's lots-of-components
nature. I think what we really need is a magic script to assemble to bits of
POD from other modules into one that uses them in a way that doesn't get in
the way of the maintainer.
From a user's point of view a tree is just a DAG constrained to a single
parent, right?

I've just commited a script that uses Class::C3 to pick out the
inheritance order and digs out the methods in the various modules and
creates a nicely formatted POD of inherited methods. Its in:

http://dev.catalyst.perl.org/repos/bast/branches/DBIx-Class-current/maint/inheritance_pod.pl

I've used it to generate the INHERITED METHODS section in all the
modules in the DBIx-Class-Tree repo (just commited).
Sounds right to me.

Aran

You're a hero! I'll try this on lots of things :)
Pretty much. Each node must have exactly one parent (with a fudge at the
root) and the graph must be connected (i.e. it's not a forest)

Cheers, Dave