Database model: doubly linked list

Question

I am not sure if I get this right. I'm designing a database model for use in an application, and I'm stuck at a doubly linked list (model first; there is no code yet).

There's an order. An order has an owner who gives it to someone, an acceptor. The acceptor can decide to divide the order into suborders. He will then become the owner of these suborders and give them to other acceptors. An order can have infinite Suborders, which can also have infinite Suborders and so on. Typical hierarchy. But the (sub-) orders have to be in order (no pun intended), and it would be nice if they could refer to the predecessor and the successor. Predecessor to the first suborder would either be null oder the parent order, successor to the last order either null or the parent order.

What is the best practice in such a case? I feel that the following is a bit... too much clutter (suborders would be a collection).

Answer 1

I'm not sure I understand your question right, but:

If I understand right, this is a tree that has children ordered. Also the creation of children is monotone, that is no children are deleted. In these cases, in relational databases I used to have:

• Id

• parent's Id

• child order (first child is 1, second 2, etc.)

• child count (count of my children, only needed if you want "last child")

• acceptor, ...

Key's are ( Id ) & ( parent's ID ; child order ).

In this case:

1. Previous sibling is ( parent's Id ; child order-1 )
2. Next sibling is ( parent's Id ; child order+1 )
3. First child is ( Id ; 1 )
4. Last child is ( Id ; child count )
5. Parent id ( parent's Id )

I hope I helped.

Answer 2

You have two issues here:

1. Representing hierarchical data.
2. Providing order at each level of hierarchy.

Probably the simplest way to do it is to use the "adjacency list" for representing hierarchy and order field for representing order:

Properties:

• The PARENT_ID is a foreign key that references ITEM_ID, denoted by FK1.
• There is an alternate key on {PARENT_ID, ORDER_IN_PARENT}, denoted by U1.
• Both PARENT_ID and ORDER_IN_PARENT are NULL-able.
• There is only one root where these fields are actually NULL.

So, to traverse the whole "list" in-order, start from the root, select its children in order, select children's children, etc. recursively...

A sibling can be reached simply by getting the item that belongs to the same parent, having the smallest ORDER_IN_PARENT larger than the starting item. If there is no such node, go to one level up and repeat...

Child levels can be added/split/deleted naturally.

Alternatively, you could use "nested sets" model, which in addition to its basic function of representing a hierarchy also naturally orders the items. Bill Karwin has a nice presentation about various ways for representing hierarchies.

---

¹ SELECT * FROM ITEM WHERE PARENT_ID = :parent_id ORDER BY ORDER_IN_PARENT. On a DBMS that supports recursive queries, it might be possible to do that in a single query.