Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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).

share|improve this question
add comment

migrated from stackoverflow.com May 27 '13 at 17:46

This question came from our site for professional and enthusiast programmers.

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
    
You understood it right, thank you! This is exactly what I was looking for. @branko-dimitrijevic answered it the same way, so I think this really is the best practice ;) –  Trevor May 27 '13 at 10:25
add comment

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:

enter image description here

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.


1 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.

share|improve this answer
    
Thank you! This is basically the same solution as @Szidor wrote, and it looks really neat. But, in my case, there can be more than one "root", since there is not only one top order. So I guess PARENT_ID will point to itself when an order has no parent order. –  Trevor May 27 '13 at 10:25
    
And what is the order or top orders? I think what you refer to as "top order" is the first level of children in my model. –  Branko Dimitrijevic May 27 '13 at 10:48
    
There is no sort order in the first level, since these orders are independent orders from different owners. So there is no need to sort them. –  Trevor May 27 '13 at 13:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.