How to store an 1:N tree (Hierarchy)

peterchen

What would be the best way to store a strict hierarchy (like a "Help Contents" tree) in a database? Is there a "standard solution"? I'm more looking for alternatives, but here's what seems most natural to me: Storing just the parent in the same table as the items id PKey, nchar name, id PKeyOfParent e.g. 0, "Root", 0 (predefined ID) 1, "Child1", 0 2, "Child2", 0 3, "A GrandChild", 1 4, "Another GrandChild", 2 to get all immediate childs of MyID is simply WHERE PKeyOfParent=MyID Advantage: No redundant data, orphaned items (parent does not exist are easily found. Disadvantages: orphaned "cycles" are possible. can SQL Server can be forced to keep integrity itself (e.g. recursively deleting all descendants?). "IsDescendant" probably cannot be written as a single select (stored procedure maybe?) The application I'm thinking of introduces a "secondary" M:N mapping anyway, but from my judgement, a more restrictive hierarchy would help the user a lot. Also, for the amount of data I imagine it would be no problem to read the entire index, then build the tree in the client, but that sounds just wrong.

We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
Linkify! || Fold With Us! || sighist

Colin Angus Mackay

I'm currently writing an application that has heirarchical data. We have a similar solution, the table contains an Id to its parent (null at the top of the heirarchy). The IsDecendant problem is one we also have, however we store a second, denormalised, table for that. The denormalised table has just two columns ID and decendantID. Using your example data the denormalised table will look like this:

ID decendentID Comments

0 0 -- [Root + Decendents]
0 1
0 2
0 3
0 4
1 1 -- [Child1 + Decendents]
1 3
2 2 -- [Child2 + Decendents]
2 4
3 3 -- [A GrandChild + Decedents]
4 4 -- [Another GrandChild + Decendents]

Then it is easy to query to see if something is a decendent of another thing:

SELECT *
FROM DenormalisedHeirarchy
WHERE decendentID = @decendentID
AND ID = @somethingID

The trick is keeping the denormalised set up to date. In our case we don't have too many inserts/updates so we can afford to have a trigger regenerate part of the denormalised table when changes occur. Does this help?

Upcoming Scottish Developers events: * UK Security Evangelists On Tour (2nd November, Edinburgh) * Developer Day Scotland: are you interested in speaking or attending? My: Website | Blog

Damodar Periwal

The following approach may be simpler. Model your object with a parent and a list of children relationship. Then use an Object Relational Mapping product like NJDX to easily retrieve any objects along with all their children without writing a single line of SQL in your application. For example, You may define a (C#) class MyEntity as follows: public class MyEntity { int id; int pid; // id of the parent entity ArrayList children; // list of children String name; // other fields } Then declaratively define the object relational mapping as follows: CLASS MyEntity TABLE MYENTITY PRIMARY_KEY id RELATIONSHIP children REFERENCES ChildrenCollection WITH id ; COLLECTION_CLASS ChildrenCollection COLLECTION_TYPE ARRAYLIST ELEMENT_TYPE MyEntity PRIMARY_KEY pid ; Now, in your application, you can do a query like: String predicate = ....; // WHERE clause for the top-level objects ArrayList entities = njdx.query("MyEntity", predicate, ...); NJDX will get the top-level MyEntity objects along with its children, each child will be fetched with its own children, each grandchild will be fetched with its own children and so on ... all of this with just one query call to NJDX. The nice thing about such an approach is that it is much easier to deal with object-oriented data in your application. Further, you don't have to write the invariably complicated SLQ/ADO.NET code to fetch and properly associate all the children objects in a long hierarchy. You can also use NJDX to easily insert, update, and delete objects. Even cascading deletes can be done by specifying the mapping appropriately.

-- Damodar Periwal Software Tree, Inc. Simplify Data Integration

Eric Dahlvang

IMHO the self referencing table structure you have chosen is well suited for a "Help Contents" tree. As for orphaned cycles, you could write a trigger to delete all descentants, or just write a function that returns a table of all descendants: Given the following: TableName=SelfRefTable Fields=PKey [int] Name [varchar (50)] PKeyOfParent [int]

PKey    Name                                    PKeyOfParent
------------------------------------------------------------
0       Root                                    NULL 
1       Child1                                  0
2       Child2                                  0
3       A GrandChild                            1
4       Another GrandChild                      2
5	A Great GrandChild                      3
6	A Great Great GrandChild                5
7 	One More GrandChild                     3

You can delete Node 3 and all of its descendants with a function call: delete from SelfRefTable where PKey in(select PID from GetDescendants(3)) This will delete PKey 3,5,6,7 in the above data.

CREATE FUNCTION GetDescendants (@nID int)
RETURNS @tDescReturn table (PID int)
AS
begin
DECLARE @RowsAdded int
declare @tDesc TABLE (PKey int,PKeyOfParent int, processed tinyint default 0)

INSERT @tDesc
SELECT PKey,PKeyOfParent,0
FROM SelfRefTable
WHERE PKey = @nID

SET @RowsAdded = @@rowcount

WHILE @RowsAdded > 0
BEGIN
UPDATE @tDesc
SET processed = 1
WHERE processed = 0

INSERT @tDesc
      SELECT e.PKey, e.PKeyOfParent,0
      FROM SelfRefTable e, @tDesc r
      WHERE e.PKeyOfParent =r.PKey and r.processed = 1

  UPDATE @tDesc
      SET processed = 2
      WHERE processed = 1

  SET @RowsAdded = @@rowcount

END

INSERT @tDescReturn
SELECT PKey
FROM @tDesc
return
end

Also, if you want all ancestors:

CREATE FUNCTION GetAncestors (@nID int)
RETURNS @tAscReturn table (PID int)
AS
begin
DECLARE @RowsAdded int
declare @tAsc TABLE (PKey int,PKeyOfParent int, processed tinyint default 0)

INSERT @tAsc
SELECT PKey,PKeyOfParent,0
FROM SelfRefTable
WHERE PKey = @nID

SET @RowsAdded = @@rowcount

WHILE @RowsAdded > 0
BEGIN
UPDATE @tAsc
SET processed = 1
WHERE processed = 0

INSERT @tAsc
      SELECT e.PKey, e.PKeyOfParent,0
      FROM SelfRefTable e, @tAsc r
      WHERE e.PKey