2

I have to store a hierarchical tree into a SQL database. After a search here on the site I found a couple solutions, but I still need some help.

In short, I have “inputs” that must be routed to outputs, based on the type of input signal, the place in the tree and the time.

To make it a bit more complex I have the requirement that it should be work with MSSQL server 2005, MySQL and SQL lite. Maybe I can drop the SQL lite requirement at some time, but for now I have to deal with it.

Most common action taken on the tree is that I have to search from bottom up to the root node for a node with some information attached to it.

The easiest way to implement this seems to me to create a table with references to the parent and selecting first the bottom node, check if the information is attached to it; if not select the parent and repeat.

While simple and not require any special database functionality it require many queries. Up to 6 levels of node nesting will be common, at most 14 levels are expected.

The information that is attached to a node contain some time (period of day/week) depended link between a type of input and the output that I have to find. Below an example; when input 1 on “Node 4” is activated I want to find that the output should be “4”, if input 8 is activated on the same node the output should be “0”. **image link**

where I have to look for more background information about this kind of structures or does anyone have an idea how to design the database structure for this problem?

Edit:

In response to the answer from Young Bob I will do a test. But if someone has an idea for me to do a select (...) if not exist repeat for parent, and so on in one query I'm very interested.

Community
  • 1
  • 1
Lukas
  • 21
  • 3

1 Answers1

0

I'd recommend you read Joe Celko's work on nested sets. See SQL - How to store and navigate hierarchies? for discussion and useful links

Community
  • 1
  • 1
Young Bob
  • 733
  • 3
  • 9
  • Thank you. I already found that post before. But there are many options, links and suggestions on that post. A bit to many for me to oversee which direction to go. Do you have a specific solution in mind? – Lukas Mar 20 '13 at 20:42
  • Best explained here http://en.wikipedia.org/wiki/Nested_set_model. Basically as well as every node having a parent it also a "Left" and "Right" field. These values are initially assigned in sequence by traversing the tree leftmost and downmost in order so that root.Left is 1, node1.Left is 2, etc. and you end up with root.Right = (no. of nodes) * 2. A node is an ancestor (parent, grand-parent, etc.) of our child node if the child node's Left value lies between the (ancestor) node's Left and Right value. The nearest ancestor has largest Left value - so no multiple joins or iterations involved. – Young Bob Mar 21 '13 at 10:32
  • I should add...this approach gives very fast lookups the downside is having to update the Left and Right values in the whole tree whenever the hierarchy changes which could be an issue if the tree is very large and frequently changed. – Young Bob Mar 21 '13 at 10:36
  • Thank you, I will do a test. The principle is clear to me now. The test must show me if the update will be fast enough. Updating 1M records is not done frequently, but seems to be a very slow operation. – Lukas Mar 21 '13 at 19:07