Re: Nodes and trees...

> -----Original Message-----
> From: Jason Schauberger [mailto:crossroads0000@googlemail.com]
> Sent: Tuesday, August 03, 2010 8:02 AM
> To: pgsql-general@postgresql.org
> Subject: Nodes and trees...
>
> Dear fellow Postgres users, :-)
>
> please consider this table:
>
> CREATE TABLE nodes (
>
> id      int     PRIMARY KEY,
>
> parent     int     REFERENCES nodes(id)
>
> );
>
> 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.
>
> I could iterate through the complete tree in question
> starting from the root node and going all the way through to
> the terminal/leaf nodes (those without a child), but that
> could take quite long depending on how large the tree is.
>
> So, what I could do is this:
>
> CREATE TABLE nodes (
>
> id      int     PRIMARY KEY,
>
> parent     int     REFERENCES nodes(id),
>
> root    int     NOT NULL        REFERENCES nodes(id)
>
> );
>
> and fill out the root column every time I insert a node. But
> then there is the problem of anomalies, where the root column
> could have an incorrect value (that is, the id of a node
> which is actually NOT the root of the same tree). I guess I
> could check for correctness using triggers.
>
> I also thought that using views might make adding a root
> column to the table completely unnecessary and at the same
> time allow for quickly finding nodes which have the same root.
>
> So, what's the best method to do this? It must be fast, it
> must prevent anomalies, and must also be either SQL standard
> or if it is not, at least it must be easily portable across
> the most popular SQL databases.  I also explicitly don't want
> to create an extra tree ID or something like that, because it
> only mitigates the problem of anomalies, but does not solve it.
>
> Thanks in advance,
>
> Jason.
>

Look up connectby() in tablefuncs contrib module.

Regards,
Igor Neyman