Re: pointers on representing tree in db?

First of all sorry for replying this way. My mail server wont let me have your postings so I'll have to use deja to read them (where one cant post anymore). Second thanks for all the suggestions.

>> Jan Hidders

Jan, the article you suggested* where precisely the sort of thing I was looking for. Very interesting. Luckily for me I have a simpler structure to keep track of, meaning I can keep things a bit simpler than in the article :-)

• Maintaining the transitive closure of graphs in SQL. Guozhu Dong, Leonid Libkin, Jianwen Su and Limsoon Wong. Int. Journal of Information Technology, 5 (1999), 46-78.

   http://cm.bell-labs.com/who/libkin/publ.html

>> Philip Lijnzaad
 

>Lennart> Table Data (id integer not null, parent_id references...) id is
 p.k
>
>what is Data.parent_id for ?

Each row in the Datatable represent a treenode. parent_id is a reference to another row which acts as a parent for the current one. Example:

(1,1), (2,1), (3,1), (4,2), (5,4),...,

represents a tree with 1 as root. 2 and 3 are children of 1. 4 is a child of 2 and 5 is a child of 4. The ancestor table for this tree would look like

(2,1), (3,1), (4,2), (4,1), (5,4), (5,2), (5,1)

Thus the ancestor table can be asked for the subtree or the path from a node to root

select id from ancestor where ancestorid = x select ancestorid from ancestor where id = x

Maintenence of the ancestor table is performed via triggers which includes the operations posted earlier. Major drawback is that the ancestor table grows quite fast for large trees (but disks are cheap these days :-). A typical tree in the system where I implemented this solution involves prox 100000 nodes.

I havent been able to look at the solution bye Joe Celko yet, so I cant comment on that

Cheers
/Lennart

[...] Received on Thu Apr 19 2001 - 22:06:16 CEST