In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote: > > can anyone recommend a good reference source for doing recursive sql on > postgresql? i want to do something similar to a BOM expansion. (i.e. i need > to traverse a self-referencing table that stores a tree structure and answer > a question like "Get me A and all of A's descendents")
Floyd, When building Cascade ( http://summersault.com/software/cascade ), I struggled with a few different models for storing a tree structure in Postgres. Here are some bits of how the system I settled on works. I've been really happy with it, both of in terms of performance, but also in terms of ease of writing queries that make use of it. category_id | integer | not null default nextval('"cas_category_category_id_seq"'::text) parent_id | integer | sort_key | character varying(255) | The 'parent_id' is not strictly needed, but makes some queries easier. The 'sort_key' is real crux of the system. It may be best explained by illustration. Each node in the tree has a two letter code associated with it. For the root node in the tree, this is 'aa'. Each child node forms its "sort_key" value by taking it's parents value and appending it's own. So the first child of the root node would have: aaaa And the second child would have aaab Here's an actual snapshot of my database using this: (from Skatepark.org ) category_id | parent_id | sort_key | name -------------+-----------+----------+--------------------- 0 | | aa | Top 10 | 0 | aaab | Propaganda 43 | 10 | aaabaa | Quotes 12 | 10 | aaabab | Presentations 64 | 10 | aaabac | Public Parks 65 | 10 | aaabad | Private Parks 66 | 10 | aaabae | Essays 67 | 10 | aaabaf | Letters 69 | 10 | aaabah | Surveys 70 | 10 | aaabai | Waivers 4 | 10 | aaabaj | Legislation 54 | 4 | aaabajaa | Youth in Politics 36 | 10 | aaabak | Statistics 3 | 10 | aaabal | Media Coverage 30 | 3 | aaabalaa | Success Stories 19 | 10 | aaabam | Sarcastic Rants 8 | 10 | aaaban | Web Services 37 | 0 | aaag | Fund-raising 46 | 37 | aaagaa | Grants 9 | 0 | aaai | Design and Building ####### Answering a question like "Get me all descendants of the 'Propaganda' category" becomes very easy: SELECT category_id, name from cas_category WHERE sort_key like 'aaab%'; By using "LIKE" above, and checking the length of the sort_key, just about any tree related query becomes easy, especially when you have the parent_id as well. You can look at the Cascade source code for more examples that use this. The one 'drawback' to this system is that it doesn't support trees of infinite size. If I'm doing my math right, I think the design above 'only' supports 676 children per node. I've never run into that limitation. :) Of course, you could always make each piece of the sort_key longer, if you needed to support more children per node. Mark > > Regards, > > Floyd Shackelford > 4 Peaks Technology Group, Inc. > VOICE: 334.735.9428 > FAX: 702.995.6462 > EMAIL: [EMAIL PROTECTED] > ICQ #: 161371538 > PGP Key ID: 0x2E84F2F2 > PGP Fone at private.fwshackelford.com on request > > Shackelford Motto: ACTA NON VERBA - Actions, not words > > Alabama StateMotto: AUDEMUS JURA NOSTRA DEFENDERE - We Dare Defend Our > Rights > > The Philosophy of Liberty: http://www.isil.org/resources/introduction.swf > > "We have allowed our constitutional republic to deteriorate into a virtually > unchecked direct democracy. Today's political process is nothing more than a > street fight between various groups seeking to vote themselves other > people's money. Individual voters tend to support the candidate that > promises them the most federal loot in whatever form, rather than the > candidate who will uphold the rule of law." --Rep. Ron Paul > > > ---------------------------(end of broadcast)--------------------------- > TIP 9: the planner will ignore your desire to choose an index scan if your > joining column's datatypes do not match > -- -- http://mark.stosberg.com/ ---------------------------(end of broadcast)--------------------------- TIP 8: explain analyze is your friend
