> -----Original Message----- > From: Jason Schauberger [mailto:crossroads0000@xxxxxxxxxxxxxx] > Sent: Tuesday, August 03, 2010 8:02 AM > To: pgsql-general@xxxxxxxxxxxxxx > 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 -- Sent via pgsql-general mailing list (pgsql-general@xxxxxxxxxxxxxx) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
