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.
Best Answer
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.