Re: self referencing tables/ nested sets etc... - Mailing list pgsql-general

Rob,

I'm not sure what application you're doing this for, so I don't know how to
advise. However, I implemented my own interpretation of "nested sets"
recently, which I will describe for you.

I was inspired by reading
http://www.yafla.com/papers/sqlhierarchies/sqlhierarchies.htm by Dennis W.
Forbes. But my own approach is to let the unique id of each object serve as
its "key" in the nested set key-chain (which I call its "ancestry"), and
separate the ids with path separator, e.g.:

sah=# select id, parent, ancestry, depth from objects;
id | parent | ancestry | depth

---+--------+----------+------

 2 | 1      | 1/2      | 1

 1 | 1      | 1        | 0

 3 | 1      | 1/3      | 1

 4 | 3      | 1/3/4    | 2

 5 | 4      | 1/3/4/5  | 3



The ancestry attribute (type varchar) shows the "path" to each item. Then I
can do queries like the following:

-- selects all objects where the ancestry attribute has '3' as a complete
word.

select * from objects where ancestry ~ '.*[[:<:]]3[[:>:]].*';

The ancestry and depth are created automatically by trigger. This has been
working fine for me, but I haven't tested it with a tree of any great depth.
It would seem to be perfect for wide, shallow trees. The trick is the
trigger to create ancestry and depth on insert & update to objects. I just
use a "recursive trigger" -- it updates the ancestry and depth for each
direct child of the updated object, which in turn calls the trigger on each
of those children. I'm not aware of any recursion limits on this type of
thing in pgsql -- I'd be interested to know from the list if there are any.

HTH,

Shawn Harrison

----- Original Message -----
From: "Rob Hoopman" <rob@tuna.nl>
To: <pgsql-general@postgresql.org>
Sent: Tuesday, March 23, 2004 3:25 PM
Subject: [GENERAL] self referencing tables/ nested sets etc...


> Hi all,
> I mostly just lurk on the list, but I need to vent. And I could use any
> advice/ experiences you'd be willing to share.
>
> For those of you that don't want to read my rant:
> What solutions are there to storing a wide/shallow self referencing tree
in a
> database?
> Any pointers to previous discussions, articles or other background
information
> is very much apreciated. I seem to be googling in circles, the same
articles
> keep popping up.
> If I learned one thing today it's that I need to educate myself a bit
before
> settling on an approach for this ;-)
>
> Cheers,
> Rob
>
> Pre-P.S. If anyone is interested in my plpgsql version of the approach
from
> the dbazine.com article from my rant, you're welcome to it. I'd be happy
to
> post it to the list or sending it in the mail.
>
>
> <RANT>
> Today I was confronted with the problem of storing self referencing data,
(The
> popular tutorial material seems to be employees with a boss/subordinate
> relationship.) I'm sure many of you have been there.
> So like a good boy I went to trawl the pgsql archives and found some
> references to the Celko 'nested set' model
> [http://www.intelligententerprise.com/001020/celko.shtml]. After some more
> googling around I found http://www.dbazine.com/tropashko4.shtml.
>
> I'm not sure if any of you are familiar with this approach, but it's
similar
> to the 'nested sets' approach and somehow this approach appealed to me
more
> than the Celko 'nested sets'. ( And the 'Real World Performance group at
> Oracle Corp.' sounds like a ringing endorsement )
>
> I don't have any mathematical background, no formal CS education of note
and
> not a lot of experience with plpgsql programming. But... I'm a sucker for
a
> challenge.
> So, equipped with my limited skillset, I have spent today wrestling with
my
> lack of skill, my unfamiliarity with the problem domain, inaccuracies in
the
> article, oracle to postgres translation quirks.
> But I pressed on. Never loosing sight of my goal: the reward and pride of
> overcoming this academic challenge.
>
> It's been a long day, I managed to squeeze in a lunch break, two bathroom
> visits and a few trips to the coffee machine. But my heart was light at
the
> prospect of a job well done.
>
> And now,... at the end of the day I am proud to announce to the world:
> "I have actually done it! Today I have acheived something I have not done
> before. I am a better man tonight than I was this morning."
>
> But,... it's a bittersweet victory because the provided solutions is
> completely useless to me. It appears that when adding more than 48 sub
nodes
> to any node in the tree, craps out because of an INT8 column overflowing.
>
> So after this aticlimax I've set aside my pride and turn to the list for
> guidance.
> </RANT>
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
>                http://www.postgresql.org/docs/faqs/FAQ.html