CODEWITHSUNDEEP
sqlsql-servert-sqlsql-server-2000
user366312
user366312

Reputation: 16894

SQL Server - How to manage hierarchical data in a table?

I use SQL Server 2000.

Suppose I have two tables like the following:

Area
----------------------------------
ID| Name   | HierarchyLevel
----------------------------------
1 | World  |     1
2 | America|     2
3 | Europe |     2
4 | Africa |     2
5 | USA    |     3

and 

AreaHierarchy
------------------------
ID | ParentID | ChildID
------------------------
 1 |   1      |    2
 2 |   1      |    3
 3 |   1      |    4
 4 |   2      |    5

where

AreaHierarchy.ParentID and AreaHierarchy.ChildID are FKs of Area.ID

How can I find the nth parent of USA?

Is it possible without looping?

Probably not.

Upvotes: 2

Views: 4149

Answers (6)

Jitender Yadav
Jitender Yadav

Reputation: 365

You can use the nested set model by Joe Celko https://en.wikipedia.org/wiki/Nested_set_model

or even better The closure Table model

Upvotes: 0

Paul Keister
Paul Keister

Reputation: 13077

I understand that you want support back to SQL Server 2000, but I think it should be noted that the SQL Server 2008 Hierarchy ID function GetAncestor() does exactly what you're looking for.

Upvotes: 0

Eric
Eric

Reputation: 95093

In SQL Server 2005+, you'd use a CTE in a function:

create function get_parent(@child as int, @parent_level as int)
returns int
as
begin
    declare @parent int

    ;with parentage as (
         select 
             h.parent_id, 
             h.child_id,
             0 as level
         from 
             areahierarchy h
         where
             h.child_id = @child
         union all
         select
             h.parent_id,
             h.child_id,
             p.level + 1 as level
         from
             areahierarchy h
             inner join parentage p on
                 h.parent_id = p.child_id
         where
             p.level < @parent_level
    )

    select @parent = p.child_id from parentage p 
    where level = (select max(level) from parentage)

    return @parent
end

Upvotes: 1

Robert Koritnik
Robert Koritnik

Reputation: 104999

No loops, no recursion

The best thing is to add additional field in your second table, that would be called ie. Parents and would simply store parent IDs in a string like:

AreaHierarchy
------------------------------------
ID | ParentID | ChildID | Parents
------------------------------------
 1 |    1     |    2    | 1/
 2 |    1     |    3    | 1/
 3 |    1     |    4    | 1/
 4 |    2     |    5    | 1/2/

This way you can easily get to any parent in the branch without recursion or any other complicated procedure. The cost in processing is very small you just copy parent's Parents value and add one more ID. And since you probably need to read more than write/update, this is the best solution to your problem.

And if I were you, I'd just keep one table for the data you have. Join both tables into one. Level could also be computed based on counting slashes in Parents varchar value but I wouldn't recommend doing that.

Additional 'catch' you should be aware of

If your data is mostly reads/writes and much less updates, this structure is really performant. But if your table does a lot more updates than read/writes, you should avoid this technique. Why? Imagine you have a very deep tree with lots of children. Changing a parent of some node high up in near the root would mean you should update Parents of the whole subtree nodes.

Upvotes: 5

MatBailie
MatBailie

Reputation: 86706

You could use recursion. If you have SQL Server 2005 or newer you can use Common Table Expressions. If not you realistically need to use User Defined Functions.


An example of a UDF to do that could be...

CREATE FUNCTION get_nth_parent(area_id AS INT, n as INT)
RETURNS INT
AS

IF (n = 0) RETURN area_id

DECLARE @return INT
SELECT
   @return = dbo.get_nth_parent(AreaHierarchy.ParentID, n-1)
FROM
   AreaHierarchy
WHERE
   ChildID = area_id

RETURN @return


An example using Common Table Experessions could be...

DECLARE @hierarchy TABLE (
   parent_id  INT,
   child_id   INT
)
INSERT INTO @hierarchy SELECT 1,2
INSERT INTO @hierarchy SELECT 1,3
INSERT INTO @hierarchy SELECT 1,4
INSERT INTO @hierarchy SELECT 2,5


;WITH
   relative_distance (
      child_id,
      parent_id,
      distance
   )
AS
(
   SELECT
      child_id,
      parent_id,
      1
   FROM
      @hierarchy

   UNION ALL

   SELECT
      [relative_distance].child_id,
      [hierarchy].parent_id,
      [relative_distance].distance + 1
   FROM
      [relative_distance]
   INNER JOIN
      @hierarchy AS [hierarchy]
         ON [hierarchy].child_id = [relative_distance].parent_id
)

SELECT
   parent_id
FROM
   [relative_distance]
WHERE
   child_id = 5
   AND distance = 2

Upvotes: 1

Lukasz Lysik
Lukasz Lysik

Reputation: 10610

Should work

CREATE PROCEDURE find_nth_parent 
    @id INT,
    @level INT
AS
BEGIN
    SET NOCOUNT ON;

    DECLARE @counter INT
    SET @counter = 1

    DECLARE @currentItem INT
    DECLARE @currentItemNew INT

    SET @currentItem = @id

    WHILE @counter <= @level
    BEGIN
        SET @currentItemNew = NULL
        SELECT @currentItemNew = ParentID FROM AreaHierarchy WHERE ChildId = @currentItem
        IF @currentItemNew IS NULL
        BEGIN
            SELECT NULL
            RETURN 
        END
        SET @currentItem = @currentItemNew
        SET @counter = @counter + 1
    END
    SELECT @currentItem
END

Calling

EXEC find_nth_parent 5,2

returns 1 which means "World" (2nd parent), calling

EXEC find_nth_parent 5,1

return 2, which means "America" (1st parent).

Hope it helps

Upvotes: 1

Related Questions