Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 SQL Server 2005 Forums
 Transact-SQL (2005)
 CTE recursive query hierarchy

Author  Topic 

michael.appleton
Posting Yak Master

160 Posts

Posted - 2008-11-05 : 10:12:00
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:


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 main problem is that some pipelines routes can eventually loop back to the same WaterWorks thus causing an infinte loop. Ideally I would like a way of limiting the answers so that each pipeline id is only used once but I'm not sure how to do this. I've commented out some code I did try but it does not work. Any ideas how to do this?

Thanks very much! Let me know if anything needs explaining a bit better.

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2008-11-05 : 11:37:57
Please provide some sample data


Success is 10% Intelligence, 70% Determination, and 22% Stupidity.
\_/ _/ _/\_/ _/\_/ _/ _/- 881
Go to Top of Page

visakh16
Very Important crosS Applying yaK Herder

52326 Posts

Posted - 2008-11-05 : 11:42:13
add a LEFT JOIN to recursive part onto main table based on reqd id condition and check for non matches (Where maintable.Id is null). If you dont know how to incorporate this to query, show some sample data of your table along with column names and reqd output.
Go to Top of Page

michael.appleton
Posting Yak Master

160 Posts

Posted - 2008-11-06 : 08:03:31
Left joins are not allowed in recursive CTE expressions, as are any outer joins. The issue is I need to check results the CTE has produced a recursion before. Some sample data is:


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:


--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


Go to Top of Page

michael.appleton
Posting Yak Master

160 Posts

Posted - 2008-11-06 : 09:44:46
I've also post this on http://www.dbforums.com/showthread.php?p=6366106#post6366106
Go to Top of Page

visakh16
Very Important crosS Applying yaK Herder

52326 Posts

Posted - 2008-11-06 : 09:48:11
Try method below:-
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=109492
Go to Top of Page
   

- Advertisement -