Determine the hierarchy of records in a SQL database

Question

I've got a problem I was wondering if there's an elegant solution to. It is a real business problem and not a class assignment!

I have a table with thousands of records, some of which are groups related to each other.

The database is SQL 2005.

ID is the primary key. If the record replaced an earlier record, the ID of that record is in the REP_ID column.

ID   REP_ID    

E     D
D     B
C     B
B     A
A     NULL

So in this example, A was the original row, B replaced A, C replaced B unsuccessfully, D replaced B successfully and finally E replaced D.

I'd like to be able to display all the records in this table in a grid. Then, I'd like for the user to be able to right click any record in any group, and for the system to locate all the related records and display them in a some sort of tree.

Now I can obviously brute force a solution to this but I'd like to ask the community if they can see a more elegant answer.

Perhaps you should wait until someone (me in this case) offers a SQL solution to recurse the hierarchy. — gbn, Oct 16 '09 at 15:12

score 2 · Answer 1 · answered Oct 16 '09 at 15:07

It's a recursive CTE you need, something like (untested)

;WITH myCTE AS
(
    SELECT
       ID
    FROM
       myTable
    WHERE
       REP_ID IS NULL
    UNION ALL
    SELECT
       ID
    FROM
       myTable T
       JOIN
       myCTE C ON T.REP_ID = C.ID
)
SELECT
    *
FROM
    myCTE

However, the links C->B and D->B

So you want the C->B or both?
Do you want a ranking?
etc?

score 0 · Accepted Answer · answered Oct 16 '09 at 15:14

Use a CTE to build your hierarchy. Something like

CREATE TABLE #test(ID CHAR(1), REP_ID CHAR(1) NULL)

INSERT INTO #test VALUES('E','D')
INSERT INTO #test VALUES('D','B')
INSERT INTO #test VALUES('C','B')
INSERT INTO #test VALUES('B','A')
INSERT INTO #test VALUES('A',NULL)


WITH tree(  ID, 
        REP_ID,
        Depth
        )
AS
(
    SELECT 
    ID,
    REP_ID,         
    1 AS [Depth]                   
    FROM
    #test
    WHERE
    REP_ID IS NULL

    UNION ALL

    SELECT 
    [test].ID,
    [test].REP_ID,          
    tree.[Depth] + 1 AS [Depth]                   
    FROM
    #test [test]
    INNER JOIN
    tree
    ON
    [test].REP_ID = tree.ID
)

SELECT * FROM tree

that is superb. I've not seen CTE expressions before. Thank you! — user69374, Oct 16 '09 at 16:29

score -1 · Answer 3 · answered Oct 16 '09 at 14:56

-1

You probably already considered it but have you looked into simply adding a row to store the "original_id"? That'd make your queries lightning fast compared to building a tree of who inherited from whom.

Barring that, just google for "SQL tree DFS".

Just make sure you have an optimization for your DFS as follows: if you know most records only have <=3 revisions, you can start with a 3-way joint to find A, B and C right away.

answered Oct 16 '09 at 14:56

DVK

126,886
32
213
327

Adding an 'original_id' isn't really an option. I found this page based on your recommendation http://vyaskn.tripod.com/hierarchies_in_sql_server_databases.htm There is a ton of links on there The interesting thing will be determining the hierarchy from any point in the hierarchy - that initial example starts at the root I think – user69374 Oct 16 '09 at 15:07
I guesss it's going to be a case of (1) find the root and (2) show hierarchy. Thanks! – user69374 Oct 16 '09 at 15:08

Determine the hierarchy of records in a SQL database

3 Answers3

Linked