Re: recursive sql (using the sort_key method)

In article <NDBBKEGJICMIMJHJEBCOKEEOGOAA(dot)floyds(at)4peakstech(dot)com>, <floyds(at)4peakstech(dot)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 | 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: FloydS(at)4PeaksTech(dot)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/