Storing Hierarchical Data in a Database

Anonymous · Feb 19, 2004 07:58

This article has revolutionized my thinking. As a new person to PHP, this has presented me with a new way of categorizing my data in future projects. A must-read for any programmer.

**jpirkkal** · Feb 25, 2004 01:21

No worries, I managed to solve my problem by myself. It was all about altering the database table so that it contains the parent id-field (I don't need it for anything beside this). Now I just figure out if there is childgroups in group that user has chosen, if not, show products in it. Then just print all other groups with same parentid that the first one in that "tree".

**fbronx** · Feb 25, 2004 03:19

Originally Posted by jpirkkal

That function in the article prints out all groups in tree, I need to show only active tree. I'm doing some kind of webstore and there is no need to show all groups at same time. When user clicks one group, show its childgroups and when user clicks one childgroup, show its childgroups...

Ask if I you think you can help, but didn't get the idea.

Maybe you can use the following trick:

Code:

SELECT COUNT(b.id) AS LEVEL,
          a.* 
     FROM category a, 
          category b
    WHERE a.lft BETWEEN b.lft AND b.rgt
 GROUP BY a.id

The query above will give you the level of the category (1=root, 2=child of root, ...)

When you only want to show the direct children of the root, you can do the following:

Code:

   SELECT COUNT(b.id) AS LEVEL,
          a.* 
     FROM category a, 
          category b
    WHERE a.lft BETWEEN b.lft AND b.rgt
 GROUP BY a.id HAVING COUNT(b.id) = 2

Anonymous · Mar 1, 2004 11:35

really good

Anonymous · Mar 9, 2004 18:12

This is a really valuable resource -- it's provided me with the tools I needed to build much more complex web applications with databases.

It'd be great if this article was followed up with a real-world application, but any programmer with reasonable problem solving skills can take these ideas and run with them (as I have).

9.9 out of 10!

Anonymous · Mar 10, 2004 05:01

this is a great article and very well written. Keep up the good work !!

Anonymous · Mar 10, 2004 08:42

How would we create a nested unordered list (ul) of the tree, rather than an asci text tree with spaces and newline?

**jsmith** · Mar 10, 2004 20:02

I needed to do something like that for a project and came up with this.

Code:

function display_tree($root) {
   // retrieve the left and right value of the $root node
   $result = mysql_query('SELECT L, R FROM tree '.
                          'WHERE Title="' .$root. '";');
   $row = mysql_fetch_array($result);

   // start with an empty $right stack and a $list_depth of 0
   $right = array();
   $list_depth = 0;

   // now, retrieve all descendants of the $root node
   $result = mysql_query('SELECT Title, L, R FROM tree '.
                          'WHERE L BETWEEN '.$row['L'].' AND '.
                          $row['R'].' ORDER BY L ASC;');

   // start the unordered list
   echo "<ul>\n";
 	
   //loop through the table
   while ($row = mysql_fetch_array($result)) {
       
       // only check stack if there is one
       if (count($right)>0) {
           // check if we should remove a node from the stack
           while ($right[count($right)-1]<$row['R']) {
               array_pop($right);
              
           }
       }

   $title = $row['Title'];
   $current_list_depth = count($right);
		
   if ($current_list_depth == $list_depth) {				
      echo "<li>$title</li>\n";
   } elseif ($current_list_depth > $list_depth) {			
      echo str_repeat ("<ul>\n", $current_list_depth - $list_depth);
      echo "<li>$title</li>\n";
   } elseif ($current_list_depth < $list_depth) {			
      echo str_repeat ("</ul>\n", $list_depth - $current_list_depth);
      echo "<li>$title</li>\n";
   }

    // add this node to the stack
   $list_depth = count($right);
   $right[] = $row['R'];
   }

   echo str_repeat ("</ul>\n", $list_depth);			// Close all lists
   echo "</ul>\n";			
}

**indent** · Mar 11, 2004 08:00

Originally Posted by jsmith

I needed to do something like that for a project and came up with this. (snipped)

That's an awesome start, except the output is invalid due to incorrect nesting.

A nested UL needs to appear INSIDE it's containing LI element, not outside it, eg:

HTML Code:

<ul>
  <li>A<ul>
      <li>one</li>
      <li>two</li></ul>
  </li>
  <li>B</li>
  <li>C</li>
  <li>D<ul>
      <li>one</li>
      <li>two</li>
      <li>three</li></ul>
  </li>
</ul>

**jsmith** · Mar 13, 2004 18:35

That's a good point. It makes this a little more difficult because you need to find out if a list item has descendents, and if it does then start a nested <ul>. Here's a slightly reworked solution:

Code:

function display_tree($root) {
	// retrieve the left and right value of the $root node
	$result = mysql_query(	'SELECT L, R FROM tree '.
									'WHERE Title="' .$root. '";');
	$row = mysql_fetch_array($result);

	// start with an empty $right stack and a $list_depth of 0
	$right = array();
	$list_depth = 0;

	// now, retrieve all descendants of the $root node
	$result = mysql_query(	'SELECT Title, L, R FROM tree '.
									'WHERE L BETWEEN '.$row['L'].' AND '.
									$row['R'].' ORDER BY L ASC;');

	// start the unordered list
	echo "<ul>";

	//loop through the table
	while ($row = mysql_fetch_array($result)) {

	// only check stack if there is one
	if (count($right)>0) {
		// check if we should remove a node from the stack
		while ($right[count($right)-1]<$row['R']) {
			array_pop($right);
      }
	}

	$title = $row['Title'];
	$current_list_depth = count($right);
	echo "\n";

	if ($current_list_depth == $list_depth) {				// List depth has not changed
		echo "<li>$title";
		if (($row['R'] - $row['L']) > 1) {					// We're starting a new subtree because $row has descendents
			echo "<ul>";
		} else {
			echo "</li>";											// No descendents, just a entry
		}
	} elseif ($current_list_depth > $list_depth) {		// List depth has increased
		echo "<li>$title";
		if (($row['R'] - $row['L']) > 1) {
			echo "<ul>";
		} else {
			echo "</li>";
		}
	} elseif ($current_list_depth < $list_depth) {		// List depth has decreased, therefore close some unordered lists
		echo str_repeat ("</ul></li>\n", $list_depth - $current_list_depth);
		echo "<li>$title";
		if (($row['R'] - $row['L']) > 1) {
			echo "<ul>";
		} else {
			echo "</li>";
		}
	}

	// add this node to the stack
	$list_depth = count($right);
	$right[] = $row['R'];

	}
	echo str_repeat ("</ul></li>\n", $list_depth);		// Close all lists
	echo "</ul>\n";												// Close the primary list
}

**indent** · Mar 20, 2004 18:58

Originally Posted by jsmith

That's a good point. It makes this a little more difficult because you need to find out if a list item has descendents, and if it does then start a nested <ul>. Here's a slightly reworked solution:

Awesome -- thanks heaps!!

**DarkAngelBGE** · Mar 21, 2004 10:37

@JSSmith: please use the [ php ]BB tag instead of [ code ]. Thanks.

Neat article indeed.

**indent** · Mar 21, 2004 16:29

Ok, I've got one last challenge for this article and it's code. I've converted my tree table so that the primary keys are numeric, not named with title. My fields are now: id, title, parent, type, lft, rgt.

The problem is, I want to be able to call each node directly via it's path, according to it's title:

/path/to/node/is/this/

rather than:

/0/4/14/28/12/

(preferably without heaps of queries)

The gurus here might have a better idea, but the folks on the MySQL list suggested adding another column, with the named path, so that queries on a given path (to get a specific node) are dead simple:

SELECT * FROM tree WHERE path='/path/to/node/is/this/'

Can any suggest how to modify rebuild_tree() to include the path to each node as it walks the tree and rebuilds the table?

**KSA** · Mar 29, 2004 00:23

**GamerZ** · Mar 29, 2004 00:32

Originally Posted by KSA

i am using the parent id method, but instead of recursive queries, I only query once, store the info in an array and recurrsive the array instead. It is easier to understand, at least for me.

**Widow Maker** · Mar 29, 2004 00:34

Second one is a lot quicker for SELECTs, though slower I believe for UPDATEs.

**Amorya** · Apr 10, 2004 08:23

I'm trying to design a threaded message board. I've got most of the theory ok, except I want the threads to be sorted by last post date not first post date. So I added a last post date field to the table, and each time a post is made then it updates the last post field of each parent node to the current time.

Problem is, how on earth do I sort by it? sorting by last post will break the threading. I want it to be as much as possible sorted by last post date, but within the boundaries of threading.

Any ideas?

**eXplosive** · Apr 10, 2004 22:39

Just read this. Nice article.

Anonymous · Apr 19, 2004 17:57

This article was fantastic. I got to work on it immediately. I'm far from an expert, but i think i've got it working pretty well. I will paste the functions i made for add_node and delete_node but I am having trouble making a function for move_node. If anyone has one, please paste it!

Note: I'm basically a novice when it comes to this stuff, so these functions may not be fantastic, but they seem to work for me. If anyone can see a problem with them, please make a post.

function add_node($root,$new_node_name){
$query="SELECT lft, rgt FROM cats WHERE catid='$root'";
$result = pg_query($query);
$row = pg_fetch_array($result);
$updatefrom = $row[rgt]-1;
$newlft=$row[rgt];
$newrgt=$row[rgt]+1;
$sql="UPDATE cats SET rgt=rgt+2 WHERE rgt>'$updatefrom'";
pg_query($sql);
$sql="UPDATE cats SET lft=lft+2 WHERE lft>'$updatefrom'";
pg_query($sql);
$sql="INSERT INTO cats (title,lft,rgt,parent) VALUES ( '$new_node_name', '$newlft', '$newrgt' , '$root' )";
pg_query($sql);
}

function delete_node($node){
$query="SELECT lft, rgt FROM cats WHERE catid='$node'";
$result = pg_query($query);
$row = pg_fetch_array($result);
$width=$row[rgt]-$row[lft]+1;
$sql="DELETE from cats where lft BETWEEN $row[lft] AND $row[rgt]";
pg_query($sql);
$sql="UPDATE cats set lft = lft - $width where lft > $row[rgt]";
pg_query($sql);
$sql="UPDATE cats set rgt = rgt - $width where rgt > $row[rgt]";
pg_query($sql);
}

my table structure is as follows:
title: name of the item
lft: left value
rgt: right value
catid: item id
parent: parent id for adjacency (just in case you need it)

It would be greatly appreciated if someone could post a function to move a node.

Hope this helps someone.

**Pests** · Apr 23, 2004 19:37

How do you get the direct chrildren of any node, not just the root?

Anonymous · May 3, 2004 14:28

Thanks, this great article helped me a lot ! Now i finally understand this method! :-)

Anonymous · May 8, 2004 09:42

I have been playing with the modified preorder trees described here. There are several issues I am still trying to figure out:
1) The delete_node() function described here does not work for nodes that have children. If one deletes a parent node, then all its children should become children of the next node down.

2) How to write a function to move a node, and how to move a node with children so that all children are moved also.

Anonymous · Jun 17, 2004 21:41

This would be interesting if it were combined with graph theory to calculate the affinity of child nodes and build associations based on them.

**Dean C** · Jun 18, 2004 08:27

I'd love to see a class developed for this Modified preorder tree traversal method

**[ArcanE]** · May 9, 2005 15:10

Originally Posted by Dean C

I'd love to see a class developed for this Modified preorder tree traversal method

Allow me to second that, would make my (and alot of other ppl's) life alot easier

Could take up some time to write up all the code though.

User Tag List

Thread: Storing Hierarchical Data in a Database

Thread Tools

Display

Bookmarks

Bookmarks

Posting Permissions