Re: Processing Tables containing tree-like data

[Richard Broersma Jr <rabroersma(at)yahoo(dot)com>]

--- psql-novice(at)netzach(dot)co(dot)il wrote:

> 
> Hi,
> 
> I have a table which looks like this:
> 
> id	info	parentid
> 0	<God>	0
> 1	Adam	0
> 2	Cain	1
> 3	Abel	1
> 4	Seth	1
> 5	Enosh	4
> ....
> 

This model is known as the Adjacency list tree model. there are two other with different strengths
and weaknesses. They are Path Enumeration tree model, and the nested set tree model.  

Path Enumeration and nested set are better suited for this kind of query than the Adjacently list
model.  The simplest and best preforming queries are probably developed using the nested set
model, but this poor choice if you are frequently adding new people to your table.

The Path enumeration model doesn't have an insertion problem, however, this model looks very
de-normalized.  I would imagine that it queries can be slow since it relies on LIKE predicates to
find all of the descendants of a particular node.

On a side note, I believe that the PostgreSQL developers are working on adding a standard SQL
operation that will handle this for your.  Perhaps we could expect to see it in the next couple of
years. 

path-enumeration
http://www.onlamp.com/pub/a/onlamp/2004/08/05/hierarchical_sql.html

nested-set
http://www.dbmsmag.com/9604d06.html

Regards,
Richard Broersma Jr.