Re: recursive sql (using the sort_key method) - Mailing list pgsql-sql

In article <NDBBKEGJICMIMJHJEBCOKEEOGOAA.floyds@4peakstech.com>, <floyds@4peakstech.com> 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            |
charactervarying(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
inPolitics         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: FloydS@4PeaksTech.com
> 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/