you could get away with using a single table.. the dbt_nav_childx table for instance.. if the parent id is zero, it's the top, 1 secondary..etc..etc. i'd probably make the cont_id the primary as well, assuming it's unique from the other table.. it'll make more sense and provide a better index if you ever query against it. just a few off hand observations.. good luck with it.

Workin on something...

... any minute now...

Building a recursive nested xhtml list from scratch was insanely difficult, if I remember correctly. I might have a solution for you (if I manage to find it), but it tends to lose efficiency if you traverse too deep. Then again, that's recursion for you.

If you recursively build your hierarchy, then again recursively build your list, no problem. I think I was trying to hard to create one elegant function that did both, but again, it's only semi-recursive. This was my first stab at recursion, and yeah, new kind of ball game, but manageable once you figure out the concept

Answer:

Let's assume you have a table called "food". In this table you have title column and a parent column. The title will act as the primary key or 'id' for this example. You have the following members in the table:

title|parent
food|
fruit|food
green|fruit
pear|green
red|fruit
cherry|red
yellow|fruit
banana|yellow
meat|food
beef|meat
pork|meat

So you get the following hierarchy:

food
 fruit
   green
    pear
   red
    cherry
   yellow
    banana
 meat
   beef
   pork

Let's say you want to delete "fruit" and all of it's children. Your logic may be something like this:

target fruit, delete all descendents
delete banana
delete yellow
delete cherry
delete red
delete pear
delete green
delete fruit

Here's the function (actually it's 2 functions)

// The delete_children() function recieves 4 variables
// 1. The id of the parent of all the child nodes you want to delete
// 2. The name of the 'id' column in the table
// 3. The name of the 'parent_id' column in the table
// 4. The name of the table to delete from
function delete_children($parentNode, $idCol, $parentCol, $table)
{
// Query all records, selecting the ID and Parent_id columns in the table
$qSelect = mysql_query("SELECT $idCol, $parentCol FROM $table;");

// Create an empty array and populate it as a 2D array with all the records from your query
$aTree = array();
while( $aRow = mysql_fetch_assoc($qSelect) )
{
$aTree[] = array
(
'id' => $aRow["$idCol"],
'parent' => $aRow["$parentCol"]
);
}

// The get_children() function will find all the children related to the parent variable
// It receives the 2D array created above, and the parent variable received from the parent function
function get_children($array, $parent)
{
// Iterate through and cast each member of the 2D array as a 1D array
foreach($array AS $node)
{
// Check if the parent property of the current node matches the parent variable received by this function
if($node['parent'] == $parent)
{
// If parents match,
// concatinate the title property of the node to a string with a pipeline symbol
// and initiate the function again to check for children of this node
$aDelete .= $node['id'] . "|";
$aDelete .= get_children($array, $node['id']);
}
}
// Return the string with all the node members we will delete from the database table
return $aDelete;
}

// Initiate the recursive function above and cast its output to a string variable
$sChildren = get_children($aTree, $parentNode);

// Attach the parent to the string with a pipeline symbol
$sChildren = $parentNode . "|" . $sChildren;

// Explode the string by the pipeline and cast to an array
$aChildren = explode("|", $sChildren);

// Reverse the array
$aChildren = array_reverse($aChildren);

// Array member $aFood[0] will have an empty value, so shift it (delete)
array_shift($aChildren);

// Loop through each member of our final array and concatinate it to a DELETE query
foreach($aChildren AS $key => $value)
{
$qDelete = mysql_query("DELETE FROM $table WHERE $idCol = '" . $value . "' LIMIT 1;");
}
}

delete_children('fruit', 'title', 'parent', 'food');


For the database example above, youll end up with the following hierarchy if you were to query the remaining members:

food
  meat
   beef
   pork


Not sure if this is absolutely the most efficient way, but it works :)

Huzzah! I think I finally figured this out. You can most definately build an XHTML nested list from a numbered tree in a database, no matter how deep the branches go. And you can do so without using recursive functions. You'll need a couple of loops, though.

This would have been a huge time-saver on a earlier projects, if only I'd had the tenacity to see this through before, since It only took a couple of hours to code from scratch. Most of that time went into figuring out the nested list output in XHTML.

A single database table, from which you can print out everything from menus to breadcrumb paths or sitemaps makes everything so much simpler. It's quite simple to insert or delete branches, also.

I'll have to do some tweaking and testing before I share the code (English variable names and such might be a bit easier to understand than Finnish ones).

In response to kari.patila - off the top of my head it's impossible to create a nested list (to unlimited depth) without recursion. If you were simply using loops without recursion you'd need to physically code a loop for every possible depth/node. You basically need a loop for every node to check whether it has a child node, and then to see if that child node has a child node etc etc. Without recursion this is impossible (although if you knew that there was only going to be 2 depths etc it would be achievable).

I've finally solved this with a lot of help from the guy with an actual Computer Science degree at work. It really only took a few lines of code and didn't require more than one call to the database. And it required only one function. Took us a good hour to hammer out.

I guess the amount of calls to the database really depends more on how your database is structured. In our case, we ended up with an array of objects like:

Array
{
[stdClass Object] =>
[id] => 2
[pid] => 1
}
and then just passed the array and a parent to a function _build_tree($array, $pid = FALSE) and recursively hunted for children (or passed it no $pid and let it figure out the parent on the first go). The initial function call and each recursive call were run through a theming function that built the nested list.

I know it can be done in a third of that code. As far as the Rails thing goes, Rails is a framework for Ruby. PHP is PHP. I'm sure a PHP framework could handle this in a few lines too. So, how many lines of Ruby code does it take for Rails to do this? That's a proper comparison. And then, which one runs faster.

The difficulty level seems to be related to the structure of the database, as the queries can get pretty complex, at least when dealing with a numbered tree. The efficiency of Varland's script seems to be the about the same as mine, when handling the same amount of data, even though the original data is represented differently in the database.