SQL To Get Parent From Self Referencing Table

Question

I have a table like this:

Item
{
   int ItemID
   int ParentID 
   string Name
}

Item is actually a subset of a larger table Object:

Object
{
    int ObjectID
    string Color
}

So ItemID is an FK to ObjectID. Within Item, ParentID can either refer to another Item or to the parent Object.

What I'd like to do is be able to iterate from a leaf in the Item relationship all the way up through its parents until I finally can determine what ObjectID a given Item leaf descends from.

I'd like to do this in SQL. I'm using SQL Server 2008.

Here's what I'm thinking. I can just iterate up through the the Item ParentID until I can no longer join ParentID with another Item. This ParentID is the ObjectID I want to return.

I've been trying to get this to work using inner joins, but no luck. I'm using C# so if this can be done in linq, which i don't suspect it can without being horribly inefficient, that would be fine too.

Answer I went With:

WITH ObjectH (ParentID, ItemID, Level) AS
(
   -- Base case
   SELECT
      ParentID,
      ItemID,
      1 as Level 
   FROM Item
   WHERE ItemID = @param 

   UNION ALL

   -- Recursive step
   SELECT
      i.ParentID,
      i.ItemID,
      oh.Level + 1 AS Level
   FROM Item i
      INNER JOIN ObjectH oh ON
         c.ItemID = oh.ParentID           
)

SELECT TOP 1 ParentID
FROM ObjectH
ORDER BY Level DESC

This works.

Answer 1

My attempt at trying to do this with a Recursive SQL Server CTE.

Logically, this is how CTE works and this should but I have never used it with a schema exactly like yours.

Usually a tree structure in SQL doesnt have the additional parent "Object" table. (Seems like you are mimicking your objects design exactly 1:1 in the db as well?. I would relook that pattern if i were you )

Try it and let me know if it works.

EDIT: Changed the base query condition a bit

EDIT2: Changed the query to make it specific for one item

WITH ObjectHierarchy (ItemID, Name, ParentID, Level) AS
(
   SELECT 
      ItemID, 
      Name, 
      ParentID, 
      1 as Level 
   FROM Item it, Object ob
   WHERE it.ParentID = ob.ObjectID
   AND ob.ItemID = @itemIdToBeSearched

   UNION ALL

   SELECT
      i.ItemID,
      i.Name,
      i.ParentID,
      oh.Level + 1 AS Level
   FROM Item i
   INNER JOIN ObjectHierarchy oh ON
      i.ParentID = oh.ItemID
   AND oh.ItemID = @itemIdToBeSearched

)

SELECT parentID
FROM ObjectHierarchy 
WHERE LEVEL = 1

Answer 2

Just create a scalar function in SQL that iterates for you, and include it in a view that mimics your table but adds the result of the function as a column. Then you base your LINQ object on the view and you have the ParentID in code.

Answer 3

First of all, it is horrible design to allow the ParentID column to reference two different tables as a "foreign key." You're probably already aware of this due to the difficulties you're experiencing writing this query.

Having said that, and assuming you're at a point where you can't redesign your schema, I'd approach solving this problem by creating a view that represents Item as it "should" be, then using the traditional recursive CTE method on that view to walk the hierarchy.

create view vwItem 
as
select i.ItemID, 
       case when o.ObjectID is null then i.ParentID else null end as ParentID, 
       o.ObjectID, Name
    from Item i
        left join Object o
            on i.ParentID = o.ObjectID
go

;with cteItemList as (
    select i.ItemID, i.ParentID, i.ObjectID, i.Name, 1 as Level
        from vwItem i
        where i.ParentID is null
    union all
    select i.ItemID, i.ParentID, i.ObjectID, i.Name, il.Level+1 as Level
        from vwItem i
            inner join cteItemList il
                on i.ParentID = il.ItemID
)
select *
    from cteItemList
    order by Level, ItemID