SQl Server - Hierarchical Data

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.