4 ms·
I have been perpetually annoyed at the SQL/RDBMS/relational calculus model. It always feels like a huge context shift from imperative programming. after many
by dekhn 7y ago
I have been perpetually annoyed at the SQL/RDBMS/relational calculus model. It always feels like a huge context shift from imperative programming. after many years of writing SQL, I noticed that many other people end up writing SQL statements that look more or less like computer programs (CASE statements, subselects, etc).
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.
This always seemed strange and backwards to me and when I did a deeper dive I learned that tree representations in SQL are a rabbit hole of insanity all arranged around referential integrity.
- topmonk 7y ago> 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. It's just an index lookup, so what? You'd rather mash all the data into a single parent field, is that it?
- dekhn 7y agoi will admit that once I saw postgres has arrays and composite types, it seemed more natural to model this as NODE with array of CHILDREN. I think it's more about the expressivity of pointers and arrays compared to the "backwardness-feeling" of index lookups.
- topmonk 7y agoSo now you have just created a many-to-many relationship. Due to a bug in software, a child could now be linked to multiple parents, or even no parents. Part of good database design is preventing corruption of these sorts of relationships. > I think it's more about the expressivity of pointers and arrays compared to the "backwardness-feeling" of index lookups. Greater expressivity in ways to store bad data is never a good thing.
- papln 7y agoHuh? If you have a tree with parent pointing to children, how do you get a child's parent? You need an index. Same as with a DB.
- josteink 7y ago> I did a deeper dive I learned that tree representations in SQL are a rabbit hole of insanity all arranged around referential integrity. It’s not crazy, just impractical. Trees are mostly represented the same way in memory, except you don’t have to access them in table-format, which admittedly for tree-data is very, very cumbersome.
- dekhn 7y agoI'm not sure what data structure/language environment you mean, but in programming languages, trees are normally represented using pointers (typically from the parent to the child and back). All of this literally goes back to hierarchical databases which were mostly replaces by relational databases for what appear to be mainly performance and implementation reasons.
- camnora 7y agoAn alternative is using a nested set https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model
- dekhn 7y ago"Updating requires renumbering and is therefore expensive".
- cryptonector 7y agoNo. Just use an RDBMS that doesn't suck -- one that supports WITH RECURSIVE CTEs.
- cryptonector 7y agoAll you need to know is WITH RECURSIVE CTEs.
- yellowapple 7y ago> 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.