Re: Nodes and trees...

On Tue, Aug 03, 2010 at 02:01:58PM +0200, Jason Schauberger wrote:
> Dear fellow Postgres users, :-)
>
> please consider this table:
>
> CREATE TABLE nodes (
>
> id int PRIMARY KEY,
>
> parent int REFERENCES nodes(id)
>
> );

Generally, you'll want to separate the nodes table from the edges
table, as in:

CREATE TABLE nodes (id INTEGER PRIMARY KEY);

CREATE TABLE edges (
tail INTEGER NOT NULL REFERENCES nodes(id),
head INTEGER NOT NULL REFERENCES nodes(id),
PRIMARY KEY(tail, head),
CHECK (tail <> head)
);

Then you might want to prevent other kinds of issues (more uniqueness,
"must be forest," etc.) with other constraints, but let's not go there
for now.

> In this table, each node *can* have a parent node. You can picture
> the whole set of rows of this table as one or more trees with nodes
> and the root of the tree is the node which has no parent node (that
> is, parent is NULL).
>
> Now here's my objective: I want to *quickly* find all nodes that
> have the same root node.

Given a "root" node, i.e. one which appears only as a tail in the
edges table, you'd do something like this:

WITH descendants AS (
SELECT head FROM edges WHERE tail=1 /* the root node */
UNION
SELECT e.head FROM edges e JOIN descendants d ON (e.tail = d.head)
)
SELECT * FROM descendants;

You might want to index edges.tail and edges.head.

Cheers,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate