Re: SQL over tree-type database?

There where a thread (pointers on representing tree in db) a couple of days back discussing how to represent trees in a relational db. Two different methods where mentioned (with some variants)

Nested set method by Joe Celko:

http://www.dbmsmag.com/9603d06.html

and keeping track of the transitive closure of the tree (in a separate table). Jan Hidders pointed out a nice article about that:

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.

You can find an electronic version on the page

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

Hope it helps

/Lennart

>In article <9d99lt$aq21_at_imsp212.netvigator.com>, Tuan Nguyen says...
>
>I am actually working on something similar. The problem of the solution
>suggested is that you need to know in advance the depth of the tree in order
>to create the Level A-B-C... table.
>
>What I have come up with is that the database contains simply the table :
>
>PARENT -> CHILD pairs.
>
>The code is done in C++
>
>For the 1st parent, we look at all the childs. For the 1st generation
>childs, we look at their childs, then we do the same for the 2nd generation
>childs etc... until there are no descendants. Each time, we store them in a
>tree which is a list of list in C++.
>
>Ideally, we would have SQL manage the recursivity. As I know nothing about
>SQL, I decided to try and do it in C++.
>
>If anybody has a better solution than that, I would be happy to know about
>it.
>
>
>
>Carlos Bromanski wrote in message
><3af5fe66$0$42879$1dc6e903_at_news.corecomm.net>...
>>Here is a very simple example, but perhaps this is what you're talking
>>about?
>>
>>set of tables that hold trees:
>>CREATE TABLE LevelA (NodeID int, ItemName char(30) )
>>CREATE TABLE LevelB (ParentNodeID int, NodeID int, ItemName char(30) )
>>CREATE TABLE LevelC (ParentNodeID int, NodeID int, ItemName char(30) )
>>
>>data for a couple of trees; also you could insert data from existing
>>unnormalized data like yours:
>>INSERT INTO LevelA (NodeID, ItemName) VALUES (1, "Blue Widget")
>>INSERT INTO LevelA (NodeID, ItemName) VALUES (2, "Red Widget")
>>INSERT INTO LevelB (NodeID, ParentNodeID, ItemName) VALUES (1, 1, "Round
>>Framitz")
>>INSERT INTO LevelB (NodeID, ParentNodeID, ItemName) VALUES (2, 1, "Square
>>Framitz")
>>INSERT INTO LevelB (NodeID, ParentNodeID, ItemName) VALUES (3, 2, "Plasma
>>Framitz")
>>INSERT INTO LevelC (NodeID, ParentNodeID, ItemName) VALUES (1, 2, "Framitz
>>Paint")
>>INSERT INTO LevelC (NodeID, ParentNodeID, ItemName) VALUES (2, 2, "Framitz
>>Decals")
>>INSERT INTO LevelC (NodeID, ParentNodeID, ItemName) VALUES (3, 3, "Framitz
>>Coolant")
>>
>>a SELECT that spits out the entire tree:
>>SELECT LevelA.NodeID, LevelA.ItemName, LevelB.NodeID, LevelB.ItemName,
>>LevelC.NodeID, LevelC.ItemName
>>FROM LevelA, LevelB, LevelC
>>WHERE
>> LevelC.ParentID = LevelB.NodeID AND
>> LevelB.ParentID = LevelA.NodeID AND
>> LevelA.ItemName = "Blue Widget"
>>
>>- cb
>>
>>Guennadi V. Liakhovetski <G.Liakhovetski_at_sheffield.ac.uk> wrote in message
>>news:Pine.GSO.4.21.0105052140420.4335-100000_at_acms23...
>>> Hello
>>>
>>> Sorry, I am not a specialist in databases, so, perhaps, my question is
>>> simple or meaningless... We've got a relational database (PostgreSQL),
>>> which is currently VERY redundant. Ok, I know how to reduce the
 redundancy
>>> by splitting the table into several smaller (2-column in our
>>> case) ones. But, anyway the redundancy would only be decreased, and not
>>> removed completely, and building SQL-queries would become more difficult
>>> (nested selects, etc.), unless you can create something like a view on
 the
>>> top of several tables?... Anyway, the data naturally have tree-structure,
>>> so, ideally it should be kept that way (not sure if RDBMSs can perform
>>> such optimisation / redundancy removal automatically?), but I still want
>>> to be able to use SQL-queries. So, ideally, the data should be stored in
 a
>>> tree, but logically be representable as a table with rows spanning all
>>> tree-levels... Is this possible? and - if yes - how?
>>>
>>> Thanks
>>> Guennadi
>>> ___
>>>
>>> Dr. Guennadi V. Liakhovetski
>>> Department of Applied Mathematics
>>> University of Sheffield, U.K.
>>> email: G.Liakhovetski_at_sheffield.ac.uk
>>>
>>>
>>
>>
>>
>>
>>
>>
>
>
Received on Tue May 08 2001 - 20:27:39 CEST