How to represent a data tree in SQL?

Question

I'm writing a data tree structure that is combined from a Tree and a TreeNode. Tree will contain the root and the top level actions on the data. I'm using a UI library to present the tree in a windows form where I can bind the tree to the TreeView.

I will need to save this tree and nodes in the DB. What will be the best way to save the tree and to get the following features:

1. Intuitive implementation.
2. Easy binding. Will be easy to move from the tree to the DB structure and back (if any)

I had 2 ideas. The first is to serialize the data into a one liner in a table. The second is to save in tables but then, when moving to data entities I will loose the row states on the table on changed nodes.

Any ideas?

Thanks Avi

Answer 1

It depends on how you will be querying and updating the data. If you store all the data in one row, it's basically a single unit that you can't query into or partially update without rewriting all the data.

If you want to store each element as a row, you should first read this article (MySQL specific, but the advice holds for many other databases too).

If you're only ever accessing an entire tree, the adjacency list model makes it difficult to retrieve all nodes under the root without using a recursive query. If you add an extra column that links back to the head then you can do SELECT * WHERE head_id = @id and get the whole tree in one non-recursive query, but it denormalizes the database.

Some databases have custom extensions that make storing and retrieving heirarchical data easier, for example Oracle has CONNECT BY.

Answer 2

The easiest implementation is adjacency list structure:

id  parent_id  data

However, some databases, particularly MySQL, have some issues in handling this model, because it requires an ability to run recursive queries which MySQL lacks.

Another model is nested sets:

id lft rgt data

, where lft and rgt are arbitrary values that define the hierarchy (any child's lft, rgt should be within any parent's lft, rgt)

This does not require recursive queries, but it slower and harder to mainain.

However, in MySQL this can be improved using SPATIAL abitilies.

See these articles in my blog:

• Adjacency list vs. nested sets: PostgreSQL
• Adjacency list vs. nested sets: SQL Server
• Adjacency list vs. nested sets: Oracle
• Adjacency list vs. nested sets: MySQL

for more detailed explanations.

Answer 3

Something like table "nodes" where each node row contains parent id (in addition to the ordinary node data). For root, the parent is NULL.

Of course, this makes finding children a bit more time consuming, but this way the actual database will be quite simple.

Answer 4

Thanks for the comments. I' working with SQL 2005/8 I'm aware of the adjacency structure. the problem I have is not just how to represent it in the DB also to be able to easily bind it later to my actual structure. If I have a tree and I delete a node from it, how to I "translate" it to the DB representation without doing it manually? (EntityFramework? ) DataTable keeps row states but when I translate the DB to an entity I loose that ability.