Entry

How can I store a hierarchical structure in a database?

How are folder systems stored in a relational database?

Aug 25th, 2000 05:14
Kai Amrhein, Mårten Svantesson, Loren Siebert, Nathan Wallace, Nathan Wallace

This is one of the more interesting problems to solve using a relational
database...<g>

If you can get a hold of "SQL for Smarties" by Joe Celko it has a great
chapter on solving this problem.  The problem with the common solution
of just keeping a pointer to the parent is that you can end up needing
recursive queries.

The solution is once of those very simple but I would never have thought
of it approaches.  Basically you have to think of the folders as sets. 
So, Linux would be a big set that contained smaller sets like Red Hat
and Mandrake.  Each of those sets can also contain smaller sets and so
on down your hierarchy.

You then lay these sets out flat and give each one a left and right
index.

     3--RPM--4 5--GIMP-6

   2------RedHat---------7  8-----------Mandrake----------9

 1---------------------Linux--------------------------------10

Notice how the indexes for linux completely contain all the other
indices.

You can do really cool queries with this structure like show me all
parents for the folder called $id:

    select *
    from   folders as parents, folders as children
    where  parents.leftindex < children.leftindex
    and    parents.rightindex > children.rightindex
    and    children.id = $id

or show me all the leaves of the tree:

    select *
    from   folders
    where  leftindex = rightindex - 1;

and so on...

The inserts get pretty hairy though as you have to update all the
indices...

BTW, databases like Oracle have a heap of SQL extensions to let you do
hierarchical stuff much more easily...

Don't you wish you were using an object database...<g>

**********
I use Oracle 8, and it provides support for hierarchies using the 
CONNECT BY and PRIOR clauses. It's not ANSI SQL, but it's a lot easier 
than the scheme outlined above. -loren
**********

For some applications a suitable solution is to use the PHP function
serialize to make a string of an array holding hierarchial data.
This string could then be stored in a text field.

WARNING: If you in PHP3 unset an element in an array and the serialize 
it the element will still be there when you retrieve the data with 
unserialize. It's value will be the empty string.

Hi there,

I'va seen and used a different approach. Basically, it's using the
following table-layout:

filed1: 	id	int not null 
field2:		number	int not null
field3:		level	int not null
...(and more fields containing your specific information)
And thats it.
Now what is most important is to get the right understanding for the
usage of the number field. Think of your tree completely expanded,
displaying all nodes.
The topmost entry has number one, as well as level one. The second entry
has number two, and either level two (if it's a child-node of entry one)
or level 1 if it's not. And so on. The third entry has number three ...

In order to find an entry's parent, just select all entrys with a
smaller number than your childentry, then start with the last of the
resulting entrys (it's number is number of childentry minus 1) and check
if it has a level of (childentry's-level minus 1). If it does, it's the
parent. If it doesn't, check the next resultiing entry (number =
childentry-number minus 2) and so on...

To find all children of an entry, just reverse the described process.

Upon inserting or deleting entries, you just have to increase/decrease
the number of all following entries (update docs set
number=number-$entryCount);

Hope this helps,
Kai Amrhein