Re: pointers on representing tree in db?

From: Lennart Jonsson <lennart_at_kommunicera.umea.se>
Date: Tue, 17 Apr 2001 20:57:38 +0200
Message-ID: <3adc922a$1_at_news.kommunicera.umea.se>


Quite neet feature. Oracle seems to have a lot of things that DB2 doesnt. I am however more interested in "classical" work using only standard SQL. The solution I came up with is to use two tables

Table Data (id integer not null, parent_id references...) id is p.k Table Ancestor (id, ancestor_id) both id and ancestor_id references id in Data

Both a subtree and a path for a particular node can be easily retrieved from the Ancestor table.

Inserting a node (x,y) to Data -> inserting (x,y) Union (x Cross Ancestors(y) into Ancestor
Deleting a node (x,y) from Data -> deleteing where id in (x Union subtree(x)) from Ancestor
Moving a subtree (x,y) to (x,z) ->

    deleting (x Union subtree(x)) Cross path(x) from Ancestor     inserting (x Union subtree(x)) Cross (z union path(z)) into Ancestor

(Cross denotes the cartesian product between two sets)

The solution also include links between different trees, but that's another story.

This seems to work with reasonable performance, but I'm eager to see how others have solved this type of issue. I'm not very experienced with databases, and I feel that perhaps I'm violating normal forms etc by storing some values tvice (both as id, parent_id and as id, ancestor_id). Any hints or pointers to information would be greatly apreciated.

Thanx in advance
/Lennart

"Todd Gillespie" <toddg_at_linux127.ma.utexas.edu> wrote in message news:9bfr66$mha$2_at_geraldo.cc.utexas.edu...
> Lennart Jonsson <lennart_at_kommunicera.umea.se> wrote:
> : Hi, does any one know of any pointers on how to represent trees in a
> : relational db? I'm sure there must be standard ways of doing this
> : (representing organizations for example). I have implemented a solution
> : which works but is far from perfect, thus eager to see other sides of
 the
> : same coin :-)
>
> Oracle has an extension to SQL syntax to build trees in queries. Use the
> CONNECT BY statement; it's been there since Oracle8.
> A quick tutorial is here:
> http://www.arsdigita.com/books/sql/trees.html
>
> And of course in the documentation at technet.oracle.com is more
> extensive.
Received on Tue Apr 17 2001 - 20:57:38 CEST

Original text of this message