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.