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.

Answer 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.

Answer 2

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?

Answer 3

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