On Sun, May 9, 2010 at 8:33 AM, Ovid <curtis_ovid_...@yahoo.com> wrote: > My apologies. This isn't PG-specific, but since this is running on PostgreSQL > 8.4, maybe there are specific features which might help. > > I have a tree structure in a table and it uses materialized paths to allow me > to find children quickly. However, I also need to sort the results > depth-first, as one would expect with threaded forum replies. > > id | parent_id | matpath | created > ----+-----------+---------+---------------------------- > 2 | 1 | 1 | 2010-05-08 15:18:37.987544 > 3 | 1 | 1 | 2010-05-08 17:38:14.125377 > 4 | 1 | 1 | 2010-05-08 17:38:57.26743 > 5 | 1 | 1 | 2010-05-08 17:43:28.211708 > 7 | 1 | 1 | 2010-05-08 18:18:11.849735 > 6 | 2 | 1.2 | 2010-05-08 17:50:43.288759 > 9 | 5 | 1.5 | 2010-05-09 14:02:43.818646 > 8 | 6 | 1.2.6 | 2010-05-09 14:01:17.632695 > > So the final results should actually be sorted like this: > > id | parent_id | matpath | created > ----+-----------+---------+---------------------------- > 2 | 1 | 1 | 2010-05-08 15:18:37.987544 > 6 | 2 | 1.2 | 2010-05-08 17:50:43.288759 > 8 | 6 | 1.2.6 | 2010-05-09 14:01:17.632695 > 3 | 1 | 1 | 2010-05-08 17:38:14.125377 > 4 | 1 | 1 | 2010-05-08 17:38:57.26743 > 5 | 1 | 1 | 2010-05-08 17:43:28.211708 > 9 | 5 | 1.5 | 2010-05-09 14:02:43.818646 > 7 | 1 | 1 | 2010-05-08 18:18:11.849735 > > Rationale: this is for a threaded forum and id 6 is a reply to id 2, so it > needs to show up after that one. Here's the rough structure of what the > output would look like (imagine an HTML forum): > > * id 1 (root post) > * id 2 > * id 6 > * id 8 > * id 3 > * id 4 > * id 5 > * id 9 > * id 7 > > How would I work that out? Can I do that in straight SQL or should additional > information be added to this table? >
This is (once more) a flat query if you use a set / subset tree implementation. Joe Celko's book "Trees and Hierarchies in SQL for Smarties" might be the fastest way to get up to speed on this, but you can also figure it out if you spend a bit of time with Google.... Basically, every node in the tree is a table row with two columns, say left and right. All children are contained within the left and right of the parent. Pre-order tree traversal gives the algorithm for assigning left and right. Once done, your problem is solved by ordering on left. -- Peter Hunsberger -- Sent via pgsql-general mailing list (pgsql-general@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
