> It all came to a head when I naively asked an experienced SQL developer how to represent a tree in SQL and learned one way to do it was to have CHILD nodes with FK references to PARENT nodes. So any time you want to get all the CHILDREN of a PARENT you have to query all children to see if they have a FK to the appropriate PARENT.
One far-less-painful solution: use what's called a "closure table" to track the ancestor-descendant relationships not just at the parent-child level, but also grandparent-grandchild, greatgrandparent-greatgrandchild, etc.
For example (assuming Postgres, and eliding some NOT NULL constraints for readability):
CREATE TABLE node (
id INTEGER PRIMARY KEY,
parent_id INTEGER REFERENCES node
name TEXT
);
CREATE TABLE node_closure (
ancestor_id INTEGER REFERENCES node,
descendant_id INTEGER REFERENCES node,
depth INTEGER,
PRIMARY KEY (ancestor_id, descendant_id)
);
Then, whenever inserting a new node (assuming that Postgres allows specifying integer primary key values on insert, which I don't recall if it restricts by default):
-- First node
INSERT INTO node VALUES (0, NULL, "foo");
INSERT INTO node_closure VALUES
(0, 0, 0); -- self
-- Second node (child of first node)
INSERT INTO node VALUES (1, 0, "foobar");
INSERT INTO node_closure VALUES
(1, 1, 0), -- self
(1, 0, 1); -- parent
-- Third node (child of first node; sibling of second node)
INSERT INTO node VALUES (2, 0, "foobaz");
INSERT INTO node_closure VALUES
(2, 2, 0), -- self
(2, 0, 1); -- parent
-- Fourth node (child of second node, grandchild of first node)
INSERT INTO node VALUES (3, 1, "foobarbaz");
INSERT INTO node_closure VALUES
(3, 3, 0), -- self
(3, 1, 1), -- parent
(3, 0, 2); -- grandparent
The upside is that it's now trivial to query for a node and
all its descendants:
SELECT descendant.name
FROM node AS descendant
JOIN node_closure ON descendant.id = node_closure.descendant_id
JOIN node AS ancestor ON ancestor.id = node_closure.ancestor_id
WHERE ancestor.name = 'foo';
Or more succinctly (if you already know the ID):
SELECT name FROM node JOIN node_closure ON node.id = node_closure.descendant_id
WHERE node_closure.ancestor_id = 0;
Either of which gives you:
----
name
----
foo
foobar
foobaz
foobarbaz
As part of this upside, since you're not having to loop through every level of ancestry, reads for deeply-nested descendants are much faster.
The downside is that you have to do extra inserts to an extra table. The inserts themselves can be automated by adding a trigger on node which automatically creates/updates/deletes node_closure rows as necessary (which is why you'd still want the parent_id in the main table: so that the trigger can grab that and build the closure rows, and so that if the closure table gets out-of-sync you can fall back on that and rebuild it), but that still leaves a performance impact on writes (pretty negligible for shallow descendants, but it gets worse for deeper ones).
Personally, I'd opt for a closure table if I know that reads are going to be more common than writes. If writes are more common than reads, then sure, some sort of crazy recursive query might be preferable.