Linde002::PHP

I was working on a small webapp a couple of months ago that would help my girlfriend manage her research data on horses. Amongst her wishes was that she would be able to view the selected horse’s family tree.

Now this is a specific wish that contains two generic problems.

• Retrieving hierarchical data from flat dataset
• Representing hierarchial / genealogical data in a browser

More info after the jump:

Retrieving hierarchical data from flat dataset

To summarize, How do I get from:

ID   Parent    Name
1    3            John
2    3            Jane
3    0            Mike

to:

Mike
   John
   Jane

Well in the Oracle world (as well as in others) they have the Connect by prior option which basically works like this:

SELECT ID, Name, Parent
FROM myTable
CONNECT BY PRIOR ID = Parent;

In MySQL however, we do not have that option. What you can do is either do a left join on itself an X number of times where X is the predermined level of recursion (the adjacency list) or you can use the nested set model. Both of which have major downsides in my opinion.

The adjacency list model doesn’t give you any flexibility when you have a dynamic depth tree, in my case I had horses that contained data of up to 8 generations, and the nested set model needs you to assign the leafs a number, layer by layer, from left to right. Which also isn’t very friendly.

It used to be possible to use recursive stored procedures to emulate connect by prior behavior but as far as I can tell this functionality went away with MySQL version 5 because of the number of bugs associated with it. For now it seems there isn’t a lot of work going into this functionality but, seeing as how MySQL is now owned by Oracle, miracles might happen.

If you want to learn more about these methods because they can help you in your situation take a look at the MySQL website

In my case I simply went for PHP recursion to retrieve each level. This meant I ’solved’ the problem but, I only had to deal with one or two users at a time on a small table that was easily indexable. On any project that is larger I would highly discourage this practice. Database queries don’t come cheap you know.

The second problem, and the actual reason why I’m writing this is:

Representing hierarchial / genealogical data in a browser

Now this is a bit trickier, the summarized problem is:

Displaying a tree that has a undefined number of starting nodes with a unknown number of child nodes in a way that makes sense to the user and does not rely on added media-plugins and/or readers.

Ergo, show this in the browser without showing inline pdf’s, horrible images generated on the fly or other mumbo jumbo:

© codeproject.com

The problem is augmented by the fact that if you don’t know how many childs a node (horse) has you don’t know how much space you want to allocate for the children which in turn makes it hard to place the parent elements on the page.

So today by chance I stumbled upon Graphic Javascript Tree widget that basically did everything I needed. The way it works is that is uses either VML or the HTML5 <canvas> element to ‘paint’ the elements and the connecting lines. It’s pretty good cross-browser wise and easy to set up. Basically you add the included .js & .css to your HTML and paste the following code and voila, you’ve got your first tree.

// myTreeContainer is a tag with id='myTreeContainer'
var myTree = new ECOTree("myTree","myTreeContainer");
// Add the root element
myTree.add(0,-1,"Apex Node");
// Add a child
myTree.add(1,0,"Left Child");
// Add another child
myTree.add(2,0,"Right Child");
// Update it to show the changes
myTree.UpdateTree();

Another cool feauture is that you can specify a node to include a hyperlink which allows it to tie into your existing application by calling other pages, javascript, etc..

The only problem that I have is that if I wanted to see both the parents and the children of a node (horse) I need to show two seperate trees, this because a node can have only one parent. You can represent multiple parents by setting them as the node’s children and then turning the tree upside down but if you do this you can’t add any children. This a challenge for another time.