> Subject: RE: Recursion > Date: Wed, 12 Feb 2003 09:36:11 -0000 > From: "Andy Eastham" <[EMAIL PROTECTED]> > To: "Mysql@Lists. Mysql. Com" <[EMAIL PROTECTED]> > > Rob, > > This is a common problem in document management, where I have a reasonable > amount of experience. > > Unfortunately, the short answer is, that to be completely generic, efficient > and elegant, it's a bit of an impossible problem. > > What we have always done in this situation is to maintain an additional > denormalised column called "FullPath" so, expanding your sample data a bit: > > ID | Name | ParentID | FullPath > -------------------- > 1 | Bob | 0 | 1 > 2 | John | 1 | 1/2 > 3 | Elm | 1 | 3/1 > 4 | Sue | 2 | 1/2/4 > 5 | Dave | 4 | 1/2/4/5 > 6 | Fred | 5 | 1/2/4/5/6 > etc. > > This initially seems like a horrible solution, raddled with problems. > However it's actually quite efficient. > > The application has to manage the Full Path on updates (although it's easy > to rebuild it and check integrity if you screw it up). > > It's also easy to find anything at any level under an object using string > comparisons. > > If you move a folder (parent) to [new path], you have to do an update such > as > > UPDATE table set FullPath = [new path] + substring(oldpath, [new Path > Length]) > WHERE fullpath like '[old path]%' > > Again this is indexed and pretty efficient. > > If you like, you can remove the objects own id from the fullpath and make it > effectively "parent path" > > Hope this helps. > > All the best, > > Andy > > > > -----Original Message----- > > From: Rob [mailto:[EMAIL PROTECTED]] > > Sent: 12 February 2003 07:18 > > To: [EMAIL PROTECTED] > > Subject: Recursion > > > > > > > > Hi all, > > > > I need some help with recursion in mySql. I have the following table: > > > > ID | Name | ParentID > > -------------------- > > 1 | Bob | 0 > > 2 | John | 1 > > 3 | Elm | 1 > > > > etc. > > > > For a given ID, I need to recurse up the tree and get all the > > parents. I've > > already read > > about Joe Celko's nested set approach, but it's not a good solution as > > apparently updates are > > a real pain and this table will be modified heavily. Does anyone have any > > good suggestions?? > > Maybe store procs (although, by all accounts store proc functionality > > doesn't come standard with > > mySql)?? > > > > Thanks > > > > > > --- > > Rob > > > > ************************** > > Rob Cherry > > mailto:[EMAIL PROTECTED] > > +27 21 447 7440 > > Jam Warehouse RSA > > Smart Business Innovation > > http://www.jamwarehouse.com > > **************************
Yes, excellent idea. It's the classic 'linked list' from my old Pascal days. While playing with it I realized that you only have to save the ID, Name and the FullPath (parents) data. For example, using Andy's data: ID | Name | FullPath -------------------- 1 | Bob | 0 2 | John | 0/1 3 | Elm | 0/1 4 | Sue | 0/1/2 5 | Dave | 0/1/2/4 6 | Fred | 0/1/2/4/5 The FullPath doesn't need the the 'leaf' or bottom node - it can be derived (it's the ID). Using a 'split' function on the FullPath data you can pull out the individual parents. -- /* All outgoing email scanned by Norton Antivirus 2002 */ Amer Neely, Softouch Information Services W: www.softouch.on.ca E: [EMAIL PROTECTED] V: 519.438.5887 Perl | PHP | MySQL | CGI programming for all data entry forms. "We make web sites work!" --------------------------------------------------------------------- Before posting, please check: http://www.mysql.com/manual.php (the manual) http://lists.mysql.com/ (the list archive) To request this thread, e-mail <[EMAIL PROTECTED]> To unsubscribe, e-mail <[EMAIL PROTECTED]> Trouble unsubscribing? Try: http://lists.mysql.com/php/unsubscribe.php
