Creating a navigation tree from SQL data

smcelhinney

Ok, so I have this table called categories

+-----------+------------------+------+-----+---------+----------------+
| Field     | Type             | Null | Key | Default | Extra          |
+-----------+------------------+------+-----+---------+----------------+
| id        | int(10) unsigned | NO   | PRI | NULL    | auto_increment |
| name      | varchar(45)      | NO   |     |         |                |
| parent_id | int(10) unsigned | YES  |     | NULL    |                |
+-----------+------------------+------+-----+---------+----------------+

each row having a parent_id, which refers to another row in the current table. Assuming that parent level items have a NULL default value, what is the best way to translate this data into a traversable XML tree? So for example, the following data:

+----+--------------+-----------+
| id | name         | parent_id |
+----+--------------+-----------+
|  1 | Home         |      NULL |
|  2 | About        |      NULL |
|  3 | Services     |      NULL |
|  4 | Products     |      NULL |
|  5 | Store        |      NULL |
|  6 | Product 1    |         4 |
|  7 | Service 1    |         3 |
|  8 | Great Offers |         5 |
|  9 | Installation |         6 |
+----+--------------+-----------+

would be displayed in XML as

<root-element>
<item id="1" name="Home" />
<item id="2" name="About" />
...
<item id="4" name="Products">
<item id="6" name="Product 1">
<item id="9" name="Installation" />
</item>
</item>
...
</root-element>

using SQL, given that there is an unknown number of levels?

Many thanks
Stephen

bonkey

It depends on what RDBMS you're using.

MSSQL introduced Recursive queries in SQL Server 2005 which can be used to handle this fairly neatly.

Oracle has CONNECT BY PRIOR which will also do the trick.

For most other popular systems (as far as I'm aware of), you need to hack it somehow.

Googling for "mysql CONNECT BY PRIOR" (or as appropriate for whatever your SQL implementation is) should give you some ideas on how best to tackle it.

democrates

A recursive function (one that calls itself) is often used to traverse a tree from that source structure. Sort it by parent id and name, or parent_id, sib_seq, name where the sibling sequence field allows sibling order to be specified rather than just sorted by name.

For simplicity say the table has one tree, and the root node has a parent id of 0. Call the findchild function supplying the root node, it looks for anything with that root as the parent id, as soon as it finds one it calls itself looking for a child of that, and so on. Starting with root you push each node onto your output. Google for examples in the language/db you're using.

Don't forget to use a counter to protect against infinite loops, and cater for the possibility through some error of orphans (parent id deleted) and loops within the tree, eg parent id set to one of the nodes own descendants. The application should never allow updates like that, but never assume.

If your dataset is small you can read the whole id/pid set into an array and work off that as db connections are 'expensive', this of course depends on usage metrics.

If tree reads far outnumber tree updates, you can gain by taking that serialised output and storing it in the database after updates. That allows a very fast read of the structured tree without the need to serialise each time, but updates will be slower.