Results 1 to 7 of 7
  1. #1
    Join Date
    May 2008
    Posts
    33

    Unanswered: CTE recursive query hierarchy

    Hello,

    I have been trying to use a recursive query in SQL to solve the following problem. In the database I am using there is a table for pipelines and also that for waterworks. In the real world, pipelines connect from water works to other pipelines, houses and other infrastructure. This is represented in the pipelines table by the columns "ToId" and "FromId".

    I would like to have "WaterWorksSourceId" for every pipeline to see exactly where the water is coming from, and so thought the use or a CTE recursive query would be ideal. This problem is very similar to the usual example of the hierarchal structure of employees in a company and wanting to find out who each employee's top boss is.

    The query I tried was:

    Code:
    WITH PipelineWaterWorkInheritance AS( 
       
       -- Anchor member is defined. 
       SELECT 
          Pipe.Id,
          WaterWorkId=W.Id
       FROM
          Pipelines Pipe
             JOIN
                WaterWorks W ON 
                   Pipe.FromId=W.Id
    
       UNION ALL
       
       -- Recursive member is defined referencing cte_name. 
       SELECT 
          Pipe.Id,
          WaterWorkId
       FROM
          PipelineWaterWorkInheritance PWh
             JOIN
                Pipelines PipeFrom ON
                   PWh.Id=PipeFrom.Id
             JOIN
                Pipelines Pipe ON
                   Pipe.FromId=PipeFrom.Id   --Pipelines that connect directly to each other
                   OR
                   Pipe.FromId=PipeFrom.ToId   --Pipelines that connect to the same infrastructure
    
       --WHERE Pipe.Id Not In (SELECT * Id FROM PipelineWaterWorkInheritance)   --This is not allowed
    ) 
    
    -- Statement using the CTE 
    
    SELECT * 
    FROM PipelineWaterWorkInheritance
    OPTION (MAXRECURSION 1000)
    The issue is I need to check results the CTE has produced a recursion before. Some sample data is:

    Code:
    WaterWorks:
    Id:		Label:
    1		WaterWorks A
    5		WaterWorks B
    7		WaterWorks C
    
    
    Pipelines:
    Id:		ToId:		FromId:		ParentId (to calculate):
    2		3		1			1			(A) Connects from waterworks 1 to pipeline 3
    3		8		3			1			(A) Connects from pipeline 3 to some other infrastructure 8 (house etc)
    4		8		5			5			(B) Connects from water works 5 to other infrastructure 8 (house etc)
    6		10		7			7			(C) Connects from water works 7 to other infrastructure 10 (house etc)
    9		11		7			7			(D) Connects from water works 7 to other pipeline 11
    11		12		9			7			(D) Connects from pipeline 9 to other pipeline 12
    12		13		11			7			(D) Connects from pipeline 11 to other pipeline 13
    13		7		12			7			(D) Connects from pipeline 12 to other water works 7
    14		15		5			5			(E) Connects from water works 5 to pipeline 15
    15		1		14			5			(E) Connects from pipeline 14 to water works 1
    16		20		1			1			(F) Connects from water works 1 to other infrastructure 20
    17		21		16			1			(F) Connects from pipeline 16 to other infrastructure 21
    18		22		16			1			(F) Connects from pipeline 16 to other infrastructure 22
    19		23		16			1			(F) Connects from pipeline 16 to other infrastructure 23
    As a note all objects that are connectable, including pipelines themselves are of a supertype "WaterInfrastructure", and this is a table where all the unique ids are generated and stored.

    Group (A) is quite straightfoward, a simpline waterworks to pipeline to infrastructure
    Group (B) is even more straighfoward, waterworks to infrastructure
    Group (C) is the same as (B)
    Group (D) loops back to the same waterworks, and so the recursive query could run forever, and is why I need to check results a recursion before
    Group (E) connects up two water works, and is also why I'd need to check previous results
    Group (F) shows pipelines that split off from a main pipeline.

    Hope this makes sense. I have actually managed an iterative solution, but I thought a recursive CTE might be quicker and should be possible:

    Code:
    --Gets the initial parent Ids for pipelines connected directly to a parent
    SELECT 
    	Pipe.Id,
    	ParentId=Parent.Id,
    	Pipe.FromId,
    	Pipe.ToId,
    	Cnt=0
    INTO #P
    FROM
    	Pipelines Pipe
    		LEFT JOIN
    			WaterWorks ON
    				Parent.Id=Pipe.FromId
    
    --Counts how far each pipeline is from a pipeline connected directly to parent
    DECLARE @Cnt int
    SET @Cnt=1
    
    
    --Populates pipelines that do not have a parent to pipeline that do and uses their parent id 
    WHILE @@ROWCOUNT>0 AND @Cnt<20
    BEGIN
    	UPDATE P2
    	SET 
    		ParentId=P1.ParentId,
    		Cnt=@Cnt
    	FROM
    		#P P2
    			JOIN 
    				#P P1 ON
    					(
    						P2.FromId=P1.Id		--For pipelines that connect directly
    						OR
    						P2.FromId=P1.ToId	--For pipelines that connect through some infrastructure
    					)
    	WHERE 
    		P2.ParentId Is Null 
    		AND 
    		P1.Cnt=@Cnt-1
    
    	SET @Cnt=@cnt+1
    END
    
    
    SELECT * FROM #p

    I have also posted about this on SQLteam forum

  2. #2
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Your data doesn't make sense to me? I can't picture the heirachy!
    Any chance you could doodle down a diagram?
    George
    Home | Blog

  3. #3
    Join Date
    May 2008
    Posts
    33
    Here's a diagram of the sample data. I've tried to show quite a lot of the strangest connections as this is where most of the problems will happen.
    Attached Thumbnails Attached Thumbnails SampleData.jpg  

  4. #4
    Join Date
    Jan 2007
    Location
    UK
    Posts
    11,434
    Provided Answers: 10
    Just a quick thought; the relationship between waterworks 1 and 5 is fully recursive; meaning it may break a full recursive CTE (i.e. traverse the nodes until we find the greatest parent/child).

    I'll try take a ponder at this next week when I have the tools available
    George
    Home | Blog

  5. #5
    Join Date
    Jan 2011
    Posts
    1

    hi,I am www.dbforums.com member now,Grate !

    Hello.
    The interesting name of a site - dBforums - Database Support Community, interesting this here is very good.
    I spent 2 hours searching in the network, until find your forum!

  6. #6
    Join Date
    Nov 2004
    Posts
    1,427
    Provided Answers: 4
    This is a post of nearly 3 years ago.
    With kind regards . . . . . SQL Server 2000/2005/2012
    Wim

    Grabel's Law: 2 is not equal to 3 -- not even for very large values of 2.
    Pat Phelan's Law: 2 very definitely CAN equal 3 -- in at least two programming languages

  7. #7
    Join Date
    Aug 2004
    Location
    Dallas, Texas
    Posts
    831
    Might be some folks are slow to introduce themselves?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •