daviestar daviestar -4 years ago 88
SQL Question

Why does no one store an array of child ids on nodes in a relational db tree structure?

I'm working on a hobby project which is a nested todo list app.

I started with the tree view example in the Redux repository (Javascript project), which uses a data structure which stores an array of child ids on each node. At first I found this strange, but having played with the structure for some time, IMO its easy to maintain and reason about.

Now I'm researching the best method to persist my todos using PostgreSQL. I've extensively read through the pros and cons of each solution here (What are the options for storing hierarchical data in a relational database?), and am about to settle on recursive WITH CTE's, as writes and updates take priority over reads in my app, but I thought I should ask.. is there a reason why storing child ids on the parent is not a popular solution for relational DB's?

It's most similar to the Adjacency List method, but with less recursion, and you get ordering (by maintaining order in your

array). It also seems easier to reason about as you don't need to think inversely about parents while asking for a 'top down' tree.

I already have the logic in place to interactively move/update/etc nodes in Javascript using this structure, so it would be a big win if I could use the same logic to persist the data.

Answer Source

is there a reason why storing child ids on the parent is not a popular solution for relational DB's

This idea is very popular, with two caveats, and under certain modeling scenario:

  • Since database fields store a single "thing", so storing so storing a list "on the parent" means storing the list in a separate table related to parent by ID, and
  • Since a single child can belong to multiple parents, enforcing "one parent per child" policy becomes a lot harder.

In effect, DB's model of storing child IDs on the parent side stores IDs on nobody's side, because you can retrieve IDs of parents of a child with the same ease as retrieving children of a parent. That is why this approach is used when you model many-to-many relationship.

Note: Since enforcing one parent per child policy when you store parent ID on the child happens automatically, you can easily model your tree like that, while converting in-memory representation to an adjacency list for the tree.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download