I have a hierarchical ADT that I want to store in a database.

Nodes have exactly one parent element that is a node as well. Multiple nodes can have the same parent node.

My current approach uses an adjacency list with a table structure similar to the following:

| Field          | Type             | Null | Key | Default | Extra          |
| node_id        | int(10) unsigned | NO   | PRI | NULL    | auto_increment |
| node_name      | varchar(255)     | NO   |     | NULL    |                |
| parent_node_id | int(10) unsigned | YES  | MUL | NULL    |                |
where parent_node_id stores other node_id values and cascades on update and delete.

To display a node's hierarchy, I implemented a loop in my script that queries for the respective parent_node_id, which can result in 5 to 10 database queries for a node. This struck me as incredibly inefficient, but I am at a loss as to how to avoid this. From my limited understanding of the inner workings of relational databases, I have deduced that stored procedures is not necessarily the way to go, since the issue seems to be with my approach to how I am storing my ADT.
I looked at discussions on how to store trees in databases, but couldn't find anything that addressed my specific needs, which are:

  • The integrity of the node hierarchy is important, which to me rules out storing the complete hierarchy in a column (Path Enumeration.)
  • Whenever I retrieve a node, I will also need to query for it's complete hierarchy.

This blog post goes into some detail on the issues you're having. You can do hierarchal queries in MySQL and also do complete chains of hierarchies. You should also be able to maintain the hierarchy from what I can tell.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.