Is there some documented "best way" of doing this? The way I thought to do it would be to say that the object has_many of itself in the model, and then simply have foo_id (assuming the table itself is named "foo"), referencing the "id" field in the "foo" table (eg, foo_id is a foreign key referencing the "id" field in the same table). A null value would mean it''s the top level and doesn''t belong to any others, but an int would indicate the id of it''s parent. Does anybody see any problem with this kind of setup? Is there a smarter way to do it that I haven''t thought of? Thanks. -- One Guy With A Camera http://rbpark.ath.cx
Michael Glaesemann
2005-Mar-20 09:09 UTC
Re: storing a heirarchical structure in a relational db
Heya Rob, On Mar 20, 2005, at 17:58, Rob Park wrote:> Is there some documented "best way" of doing this? > > The way I thought to do it would be to say that the object has_many of > itself in the model, and then simply have foo_id (assuming the table > itself is named "foo"), referencing the "id" field in the "foo" table > (eg, foo_id is a foreign key referencing the "id" field in the same > table). A null value would mean it''s the top level and doesn''t belong > to any others, but an int would indicate the id of it''s parent. > > Does anybody see any problem with this kind of setup? Is there a > smarter way to do it that I haven''t thought of?The two most common ways are the adjacency list model (which you''re describing) and the nested set model. They serve different needs and have varying update and querying speeds (depending on the type of query). A little googling on SQL, adjacency list model, nested set model, and Joe Celko will probably bring up enough information to get you going. Good luck! Michael Glaesemann grzm myrealbox com
Caleb Buxton
2005-Mar-20 09:49 UTC
Re: storing a heirarchical structure in a relational db
acts_as_tree http://rails.rubyonrails.com/classes/ActiveRecord/Acts/Tree/ClassMethods.html#M000277 is how you could do it in rails. however, i think it ultimately breaks down to a has_many IIRC caleb On Sun, 20 Mar 2005 18:09:12 +0900, Michael Glaesemann <grzm-YSGFQ8SKJZVDPfheJLI6IQ@public.gmane.org> wrote:> Heya Rob, > > On Mar 20, 2005, at 17:58, Rob Park wrote: > > > Is there some documented "best way" of doing this? > > > > The way I thought to do it would be to say that the object has_many of > > itself in the model, and then simply have foo_id (assuming the table > > itself is named "foo"), referencing the "id" field in the "foo" table > > (eg, foo_id is a foreign key referencing the "id" field in the same > > table). A null value would mean it''s the top level and doesn''t belong > > to any others, but an int would indicate the id of it''s parent. > > > > Does anybody see any problem with this kind of setup? Is there a > > smarter way to do it that I haven''t thought of? > > The two most common ways are the adjacency list model (which you''re > describing) and the nested set model. They serve different needs and > have varying update and querying speeds (depending on the type of > query). A little googling on SQL, adjacency list model, nested set > model, and Joe Celko will probably bring up enough information to get > you going. > > Good luck! > > Michael Glaesemann > grzm myrealbox com > > _______________________________________________ > Rails mailing list > Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org > http://lists.rubyonrails.org/mailman/listinfo/rails >
Charles Comstock
2005-Mar-20 20:56 UTC
Re: storing a heirarchical structure in a relational db
There should be two versions of acts_as_tree, one that provides adjacency list and the existing one that provides nested set model. That way if people knew they were dealing with a data set complex enough to require adjacency list they could choose to use it. Charles Comstock On Sun, 20 Mar 2005 01:49:57 -0800, Caleb Buxton <adbust-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:> acts_as_tree > > http://rails.rubyonrails.com/classes/ActiveRecord/Acts/Tree/ClassMethods.html#M000277 > > is how you could do it in rails. > > however, i think it ultimately breaks down to a has_many IIRC > > caleb > > On Sun, 20 Mar 2005 18:09:12 +0900, Michael Glaesemann > <grzm-YSGFQ8SKJZVDPfheJLI6IQ@public.gmane.org> wrote: > > Heya Rob, > > > > On Mar 20, 2005, at 17:58, Rob Park wrote: > > > > > Is there some documented "best way" of doing this? > > > > > > The way I thought to do it would be to say that the object has_many of > > > itself in the model, and then simply have foo_id (assuming the table > > > itself is named "foo"), referencing the "id" field in the "foo" table > > > (eg, foo_id is a foreign key referencing the "id" field in the same > > > table). A null value would mean it''s the top level and doesn''t belong > > > to any others, but an int would indicate the id of it''s parent. > > > > > > Does anybody see any problem with this kind of setup? Is there a > > > smarter way to do it that I haven''t thought of? > > > > The two most common ways are the adjacency list model (which you''re > > describing) and the nested set model. They serve different needs and > > have varying update and querying speeds (depending on the type of > > query). A little googling on SQL, adjacency list model, nested set > > model, and Joe Celko will probably bring up enough information to get > > you going. > > > > Good luck! > > > > Michael Glaesemann > > grzm myrealbox com > > > > _______________________________________________ > > Rails mailing list > > Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org > > http://lists.rubyonrails.org/mailman/listinfo/rails > > > _______________________________________________ > Rails mailing list > Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org > http://lists.rubyonrails.org/mailman/listinfo/rails >
Jarkko Laine
2005-Mar-20 21:24 UTC
Re: storing a heirarchical structure in a relational db
On 20.3.2005, at 22:56, Charles Comstock wrote:> There should be two versions of acts_as_tree, one that provides > adjacency list and the existing one that provides nested set model. > That way if people knew they were dealing with a data set complex > enough to require adjacency list they could choose to use it.I think you mixed up the two. The current implementation uses parent_id, and thus the adjacency list approach. See http://groups-beta.google.com/group/comp.databases.postgresql.sql/msg/ f3087f3019690890?q=CELKO+group: comp.databases.postgresql.sql&hl=en&rnum=8 for explanation. //jarkko> > Charles Comstock > > > On Sun, 20 Mar 2005 01:49:57 -0800, Caleb Buxton <adbust-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> > wrote: >> acts_as_tree >> >> http://rails.rubyonrails.com/classes/ActiveRecord/Acts/Tree/ >> ClassMethods.html#M000277 >> >> is how you could do it in rails. >> >> however, i think it ultimately breaks down to a has_many IIRC >> >> caleb >> >> On Sun, 20 Mar 2005 18:09:12 +0900, Michael Glaesemann >> <grzm-YSGFQ8SKJZVDPfheJLI6IQ@public.gmane.org> wrote: >>> Heya Rob, >>> >>> On Mar 20, 2005, at 17:58, Rob Park wrote: >>> >>>> Is there some documented "best way" of doing this? >>>> >>>> The way I thought to do it would be to say that the object has_many >>>> of >>>> itself in the model, and then simply have foo_id (assuming the table >>>> itself is named "foo"), referencing the "id" field in the "foo" >>>> table >>>> (eg, foo_id is a foreign key referencing the "id" field in the same >>>> table). A null value would mean it''s the top level and doesn''t >>>> belong >>>> to any others, but an int would indicate the id of it''s parent. >>>> >>>> Does anybody see any problem with this kind of setup? Is there a >>>> smarter way to do it that I haven''t thought of? >>> >>> The two most common ways are the adjacency list model (which you''re >>> describing) and the nested set model. They serve different needs and >>> have varying update and querying speeds (depending on the type of >>> query). A little googling on SQL, adjacency list model, nested set >>> model, and Joe Celko will probably bring up enough information to get >>> you going. >>> >>> Good luck! >>> >>> Michael Glaesemann >>> grzm myrealbox com >>> >>> _______________________________________________ >>> Rails mailing list >>> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org >>> http://lists.rubyonrails.org/mailman/listinfo/rails >>> >> _______________________________________________ >> Rails mailing list >> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org >> http://lists.rubyonrails.org/mailman/listinfo/rails >> > _______________________________________________ > Rails mailing list > Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org > http://lists.rubyonrails.org/mailman/listinfo/rails >-- Jarkko Laine http://jlaine.net http://odesign.fi _______________________________________________ Rails mailing list Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org http://lists.rubyonrails.org/mailman/listinfo/rails
Jarkko Laine
2005-Mar-21 14:28 UTC
Re: storing a heirarchical structure in a relational db
On 21.3.2005, at 03:27, Charles Comstock wrote:> Whatever the actual name, the parent_id approach is the naive > implementation as it requires far more queries to show the tree. > Whatever the name is for the approach where you store a left and right > range and ensure ordering through that is it is superior for large > sets of data, particularly if one needs to display the whole tree. I > was actually kind of suprised that the parent_id appraoch was that > which was initially implemented. The left and right approach is a > little trickier to implement but other then needing two extra columns > it allows all the same actions to be performed on the tree. At least > as far as I am aware of. Once it would be in the framework though > no one would need to re-implement it, and I was under the impression > that really the main reason to use the parent_id approach was for ease > of development. Since acts_as_tree removes the re-development time it > would seem it would make more sense to use the more efficient > algorithm.Agreed. Just wanted to to put the terms straight ;-) //jarkko> Charles Comstock > > On Sun, 20 Mar 2005 23:24:22 +0200, Jarkko Laine <jarkko-k1O+Gnc6WpmsTnJN9+BGXg@public.gmane.org> > wrote: >> On 20.3.2005, at 22:56, Charles Comstock wrote: >> >>> There should be two versions of acts_as_tree, one that provides >>> adjacency list and the existing one that provides nested set model. >>> That way if people knew they were dealing with a data set complex >>> enough to require adjacency list they could choose to use it. >> >> I think you mixed up the two. The current implementation uses >> parent_id, and thus the adjacency list approach. See >> http://groups-beta.google.com/group/comp.databases.postgresql.sql/msg/ >> f3087f3019690890?q=CELKO+group: >> comp.databases.postgresql.sql&hl=en&rnum=8 for explanation. >> >> //jarkko >> >>> >>> Charles Comstock >>> >>> >>> On Sun, 20 Mar 2005 01:49:57 -0800, Caleb Buxton <adbust-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> >>> wrote: >>>> acts_as_tree >>>> >>>> http://rails.rubyonrails.com/classes/ActiveRecord/Acts/Tree/ >>>> ClassMethods.html#M000277 >>>> >>>> is how you could do it in rails. >>>> >>>> however, i think it ultimately breaks down to a has_many IIRC >>>> >>>> caleb >>>> >>>> On Sun, 20 Mar 2005 18:09:12 +0900, Michael Glaesemann >>>> <grzm-YSGFQ8SKJZVDPfheJLI6IQ@public.gmane.org> wrote: >>>>> Heya Rob, >>>>> >>>>> On Mar 20, 2005, at 17:58, Rob Park wrote: >>>>> >>>>>> Is there some documented "best way" of doing this? >>>>>> >>>>>> The way I thought to do it would be to say that the object >>>>>> has_many >>>>>> of >>>>>> itself in the model, and then simply have foo_id (assuming the >>>>>> table >>>>>> itself is named "foo"), referencing the "id" field in the "foo" >>>>>> table >>>>>> (eg, foo_id is a foreign key referencing the "id" field in the >>>>>> same >>>>>> table). A null value would mean it''s the top level and doesn''t >>>>>> belong >>>>>> to any others, but an int would indicate the id of it''s parent. >>>>>> >>>>>> Does anybody see any problem with this kind of setup? Is there a >>>>>> smarter way to do it that I haven''t thought of? >>>>> >>>>> The two most common ways are the adjacency list model (which you''re >>>>> describing) and the nested set model. They serve different needs >>>>> and >>>>> have varying update and querying speeds (depending on the type of >>>>> query). A little googling on SQL, adjacency list model, nested set >>>>> model, and Joe Celko will probably bring up enough information to >>>>> get >>>>> you going. >>>>> >>>>> Good luck! >>>>> >>>>> Michael Glaesemann >>>>> grzm myrealbox com >>>>> >>>>> _______________________________________________ >>>>> Rails mailing list >>>>> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org >>>>> http://lists.rubyonrails.org/mailman/listinfo/rails >>>>> >>>> _______________________________________________ >>>> Rails mailing list >>>> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org >>>> http://lists.rubyonrails.org/mailman/listinfo/rails >>>> >>> _______________________________________________ >>> Rails mailing list >>> Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org >>> http://lists.rubyonrails.org/mailman/listinfo/rails >>> >> -- >> Jarkko Laine >> http://jlaine.net >> http://odesign.fi >> >> >> >>-- Jarkko Laine http://jlaine.net http://odesign.fi _______________________________________________ Rails mailing list Rails-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org http://lists.rubyonrails.org/mailman/listinfo/rails
> > Whatever the actual name, the parent_id approach is the naive > > implementation as it requires far more queries to show the tree. > > Whatever the name is for the approach where you store a left and right > > range and ensure ordering through that is it is superior for large > > sets of data, particularly if one needs to display the whole tree. I > > was actually kind of suprised that the parent_id appraoch was that > > which was initially implemented. The left and right approach is a > > little trickier to implement but other then needing two extra columns > > it allows all the same actions to be performed on the tree. At least > > as far as I am aware of. Once it would be in the framework though > > no one would need to re-implement it, and I was under the impression > > that really the main reason to use the parent_id approach was for ease > > of development. Since acts_as_tree removes the re-development time it > > would seem it would make more sense to use the more efficient > > algorithm.I think the reason is that the adjacency list model was much simpler to implement. Looking at the code for act_as_tree (http://dev.rubyonrails.com/file/trunk/activerecord/lib/active_record/acts/tree.rb), it just sets up belongs_to and has_many associations. I''m not sure how this would work with the other tree model. You''d need to override the save method to calculate the left/right values, for instance. I was planning on taking a stab at this when the need arose in one of my projects. It hasn''t yet. -- rick http://techno-weenie.net
> I think the reason is that the adjacency list model was much simpler > to implement. Looking at the code for act_as_tree > (http://dev.rubyonrails.com/file/trunk/activerecord/lib/active_record/acts/tree.rb), > it just sets up belongs_to and has_many associations. I''m not sure > how this would work with the other tree model. You''d need to override > the save method to calculate the left/right values, for instance. > > I was planning on taking a stab at this when the need arose in one of > my projects. It hasn''t yet.Sorry for the double post, but the acts_as_list method (http://dev.rubyonrails.com/file/trunk/activerecord/lib/active_record/acts/list.rb) is a better example of a good act. It shows how to add class and instance methods to a model. I''m sure now that implementing the other tree model (nested list? I get the terms all mixed up) won''t be a problem. -- rick http://techno-weenie.net