SQL Parent/Child query

AJKBOC
AJKBOC used Ask the Experts™
on
Hi all

I have a table named "Nodes" with the following columns: "companyID", "parentID"

In this table a "Parent/Child" relationship is kept, in order to know which companies belong to who.

There can be many levels while creating the compnay structure based on the data of the table.

Think of the following scenario:

The top level company id = 1 (has no parent)

1 has 3 children with the following IDs: 10, 50, 80

50 has 2 children with the following IDs: 200, 400

200 has 1 child with the following ID: 5000

So, what i need is an efficient query to return as fast as possible, all the parents and children (whole structure) of a given company ID.

For example, given the ID:200 query should return the following results (two columns: companyID AND its parentID):

column A    column B
   50           1
   400          50
   5000         200
   10           1
   80           1
companyStructure.bmp
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Two questions:
1) Why the result does not contain 200 - 50 combination?
2) Do you have SQL Server 2005? If yes then it is simple usage of CTE - you have to find the top most company for given child and then to select the whole tree for this company.

Author

Commented:
1) The result should contain 200 - 50 combination also. My mistake.
2) YES i have SQL Server 2005. However am not sure what happens with your proposed solution, when a child has more than one parents.

Commented:
The result should be 1, 50 , 200 , 5000  becasue you are extracting parent child hierarchy of 200 compnay
i am sending you solution for this .
DECLARE @tbl TABLE ( ID INT , PID INT )
INSERT  INTO @tbl
        SELECT  1
              , NULL
        UNION ALL
        SELECT  10
              , 1
        UNION ALL
        SELECT  50
              , 1
        UNION ALL
        SELECT  80
              , 1
        UNION ALL
        SELECT  200
              , 50
        UNION ALL
        SELECT  400
              , 50
        UNION ALL
        SELECT  5000
              , 200 ; 
 
WITH    Childcte
          AS ( SELECT   *
               FROM     @tbl
               WHERE    id = 200
               UNION ALL
               SELECT   p.*
               FROM     @tbl p
               INNER JOIN Childcte c
               ON       c.id = p.pid
             ) ,
        parentcte
          AS ( SELECT   *
               FROM     @tbl
               WHERE    id = 200
               UNION ALL
               SELECT   p.*
               FROM     @tbl p
               INNER JOIN parentcte c
               ON       c.pid = p.id
             )
    SELECT  *
    FROM    Childcte
    UNION
    SELECT  *
    FROM    parentcte 

Open in new window

Ensure you’re charging the right price for your IT

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden using our free interactive tool and use it to determine the right price for your IT services. Start calculating Now!

Hmm, you didn't mention two parents possibility in the original question... You also didn't mention cyclic relation possibility (company 5000 can be a parent of company 1). What other possibilities exist?

Author

Commented:
Dear mazher, thanks for your query. However these are not the desired results. I need to get the whole structure,  i need every company related.

Dear pcelba, yes you are right i havent mention it earlier. It is possible that cyclic relation may exists, as you have stated.
Including this possibility, i think am covered.
So, if you have the cyclic relation possibility then you may forgot about "efficient query" because you have to go through your structure in a loop and test each node if it was investigated already or not. You'll need stored procedure to do this work.

Author

Commented:
I thought of that.. Can you give me some pseudocode on this?
The code which retrieves the whole company spider from one given point is in the following SP. It supports multiple parents and cyclic ownership. The code is just the first working saample and it can be optimized for sure.
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
 
-- =====================================================================
-- Author:      Pavel Celba
-- Create date: 2009-10-22
-- Description: Retrieve the whole company structure from given member
-- =====================================================================
CREATE PROCEDURE dbo.sp_GetCompanySpider 
	@CompanyID int
AS
BEGIN
	SET NOCOUNT ON;
	
	-- Return nulls for no parameters or company which does not exist
	IF @CompanyID IS NULL OR NOT EXISTS (SELECT CompanyID FROM Nodes WHERE CompanyID = @CompanyID)
	BEGIN
	  SELECT null AS CompanyID, null AS ParentID
	  RETURN
	END
	
	-- Temporary results table
	CREATE TABLE #AllParents (CompanyID int, ParentID int, IsCyclic bit, IsProcessed bit)
	
	-- Look for all parents
	INSERT INTO #AllParents
	SELECT CompanyID, ParentID, 0, 
	       CASE WHEN ParentID IS NULL THEN 1 ELSE 0 END
	  FROM Nodes
	 WHERE CompanyID = @CompanyID
	
	DECLARE @cID int, @pID int, @ccID int, @ppID int
	
    WHILE EXISTS (SELECT 1 FROM #AllParents WHERE isProcessed = 0)
    BEGIN
      
      SELECT TOP 1 @pID = ParentID, @cID = CompanyID
        FROM #AllParents 
       WHERE isProcessed = 0
      
      UPDATE #AllParents SET isProcessed = 1
       WHERE ParentID = @pID AND CompanyID = @cID
      
      DECLARE par CURSOR FOR
      SELECT CompanyID, ParentID 
	    FROM Nodes
	   WHERE CompanyID = @pID
	  
	  OPEN par
	  FETCH NEXT FROM par INTO @ccID, @ppID
	  
	  WHILE @@FETCH_STATUS = 0
	  BEGIN
	    
	    UPDATE #AllParents SET IsCyclic = 1
         WHERE CompanyID = @ccID AND (ParentID = @ppID  OR (@ppID is NULL AND ParentID is null))
	    IF @@RowCount = 0
	      INSERT INTO #AllParents 
	        VALUES (@ccID, @ppID, 0, CASE WHEN @ppID IS NULL THEN 1 ELSE 0 END)
	    
	    FETCH NEXT FROM par INTO @ccID, @ppID
	  END
	  
	  CLOSE par
	  DEALLOCATE par
      
    END
    
    -- Now we have all parents so we may look for children
	-- Mark top-most parents and cyclic parents as not processed to process them again
	UPDATE #Allparents SET IsProcessed = 0 WHERE ParentID IS NULL OR IsCyclic = 1
	
	CREATE TABLE #Rslt (CompanyID int, ParentID int)
	
    WHILE EXISTS (SELECT 1 FROM #AllParents WHERE isProcessed = 0)
    BEGIN
      
      SELECT TOP 1 @cID = CompanyID, @pID = ParentID
        FROM #AllParents 
       WHERE isProcessed = 0
      
      UPDATE #AllParents SET isProcessed = 1
       WHERE CompanyID = @cID AND (ParentID = @pID OR (@pID is NULL AND ParentID is null))
      
      DECLARE chld CURSOR FOR
      SELECT CompanyID, ParentID 
	    FROM Nodes
	   WHERE ParentID = @cID
	  
	  OPEN chld
	  FETCH NEXT FROM chld INTO @ccID, @ppID
	  
	  WHILE @@FETCH_STATUS = 0
	  BEGIN
	    
	    IF NOT EXISTS (SELECT CompanyID FROM #Rslt WHERE CompanyID = @ccID AND ParentID = @ppID)
	    BEGIN
	      INSERT INTO #Rslt VALUES (@ccID, @ppID)
	      INSERT INTO #AllParents VALUES (@ccID, @ppID, 0, 0)
	    END
	    
	    FETCH NEXT FROM chld INTO @ccID, @ppID
	  END
	  
	  CLOSE chld
	  DEALLOCATE chld
      
    END
    
	--SELECT * FROM #Allparents
	SELECT * FROM #Rslt
	
END
GO

Open in new window

Commented:
This is final and tested source with your requirements.and this code also show with two parent too.

for two parent of 200 Replace derived table with this
INSERT  INTO @tbl
        SELECT  1
              , NULL
        UNION ALL
        SELECT  10
              , 1
        UNION ALL
        SELECT  50
              , 1
        UNION ALL
        SELECT  80
              , 1
        UNION ALL
        SELECT  200
              , 50
        UNION ALL
        SELECT  400
              , 50
        UNION ALL
        SELECT  5000
              , 200
        UNION ALL
        SELECT  200
              , 20
        UNION ALL
        SELECT  20
              , 70
        UNION ALL
        SELECT  70
              , NULL

here 200 hase second parent 20
200-> 20 -> 70
and 70 have more one child 100
70->100
DECLARE @tbl TABLE ( ID INT , PID INT )
DECLARE @CurrentNodeID INT 
INSERT  INTO @tbl
        SELECT  1
              , NULL
        UNION ALL
        SELECT  10
              , 1
        UNION ALL
        SELECT  50
              , 1
        UNION ALL
        SELECT  80
              , 1
        UNION ALL
        SELECT  200
              , 50
        UNION ALL
        SELECT  400
              , 50
        UNION ALL
        SELECT  5000
              , 200 
SET @CurrentNodeID = 200 ; 
 
WITH    ChildToParentCte
          AS ( SELECT   id
                      , pid
               FROM     @tbl
               WHERE    id = @CurrentNodeID  
               --WHERE id IN (1,50,200)
               UNION ALL
               SELECT   tb.id
                      , tb.pid
               FROM     @tbl tb
               INNER JOIN ChildToParentcte ctp
               ON       ctp.pid = tb.id
             ) ,
        ParentToChildCte
          AS ( SELECT   id
                      , pid
               FROM     ChildToParentCte
               UNION ALL
               SELECT   tb.id
                      , tb.pid
               FROM     ParentToChildCte ptc
               INNER JOIN @tbl tb
               ON       ptc.id = tb.pid
             )
    --Distinctly show those records which is not have any parent and current node.
SELECT DISTINCT
        *
FROM    [ParentToChildCte]
WHERE   NOT pid IS NULL
        AND NOT id = @CurrentNodeID 

Open in new window

mazher, "cyclic ownership" (standard possibility in a real life) was one of the requirements also. Did you test it?

Commented:
How many cyclic ownership are there in your problem 1 or many

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial