Solved

Recursive SQL

Posted on 2011-09-21
5
316 Views
Last Modified: 2012-05-12
Hi,

I Have a table like below

ProductID          RepProdID
######           ###########
a                         b
a                         c
a                         d
b                         a
b                         e
b                         f
b                         z
c                         a
c                         k


Means, The product a is replaced by b and etc

Now, If I query with product ID "a" then I want the output

B, C, D, E, F, Z, K.

Since product "a" is the source of all this products (please note that b to a is also possible which leads to infinite loop).

I want t-sql query to achieve this without infinite recursive loop.

How can I achieve this? Please help.
0
Comment
Question by:radcaesar
5 Comments
 
LVL 42

Accepted Solution

by:
dqmq earned 500 total points
ID: 36574199
Using a view, substitute your view and table names for T and V


create view V as
select productid, repprodid from T
   where ProductID < RepProdID
      or not exists (select * from T as C where T.productID = c.Repprodid and c.productid = t.repprodid)
group by productid, repprodid

;with cte
as
(
select T.RepProdID from V as T where T.ProductID = 'f'
union all
select T.RepProdID from V as T
inner join cte on cte.RepProdID = T.ProductID
)
select * from cte  
0
 
LVL 21

Expert Comment

by:JestersGrind
ID: 36574282
Typically, infinite loops in a hierarchy means that data has errors, but here is another way to do it.  It actually looks for repeating patterns and then ignores them.

Greg


DECLARE @Anchor VARCHAR(5)

SET @Anchor = 'a'

;WITH RecursiveCTE
AS
(
	SELECT ProductID, RepProdID, 1 AS [Level], 'N' AS Cycle,
		CAST('.' + CAST(ProductID AS VARCHAR(8)) + '.' AS VARCHAR(MAX)) AS CTEPath
	FROM YourTable
	WHERE ProductID = @Anchor
	UNION ALL
	SELECT a.ProductID, a.RepProdID, b.[Level] + 1 AS [Level],
		CASE 
			WHEN b.CTEPath LIKE '%.' + CAST(a.ProductID AS VARCHAR(8)) + '.%' THEN 'Y'
			ELSE 'N'
		END,
		CAST(b.CTEPath + CAST(a.ProductID AS VARCHAR(8)) + '.' AS VARCHAR(MAX))
	FROM YourTable a INNER JOIN 
		RecursiveCTE b ON a.ProductID = b.RepProdID AND b.Cycle = 'N'
)
SELECT  DISTINCT
	RepProdID
FROM   
	RecursiveCTE
WHERE
	RepProdID <> @Anchor
OPTION(Maxrecursion 100)

Open in new window

0
 
LVL 9

Author Comment

by:radcaesar
ID: 36574339
Just a clarification

It will work for values like ML005J, 5XP00M right.

I have this doubt because of the below where condition check.

where ProductID < RepProdID

Please explain this.
0
 
LVL 42

Expert Comment

by:dqmq
ID: 36574869
>It will work for values like ML005J, 5XP00M right.

Well, I think so...< works fine for character values.

The goal is to eliminate the bi-directional parallelism (a replaces b, b replaces a) and infinite recursions (a replaces b, b replaces c, c replaces a).  


BTW, if "a replaces b" is equivalent to "b replaces a", then it may behoove you to add a check constraint for ProductID < RepProdID and eliminate the opposite, but equivalent relationships from your table. That makes clean retrival so much easier.  

If "a replaces b" is NOT equivalent to "b replaces a", then it's not clear what the difference might be.


 "a replaces b" is equivalent to "b replaces a"

Also, I think this view would also work and might be more self-documenting:

create view V as
select productid, repprodid from T where ProductID < RepProdID
union
select repprodid, productid from T where ProductID > RepProdID



0
 
LVL 29

Expert Comment

by:Olaf Doschke
ID: 36580434
The major ingredient will surely be CTE, so if you're not familiar with common table expressions used for recursion, maybe have a read on http://www.simple-talk.com/sql/t-sql-programming/sql-server-cte-basics/

The main question really is, whether the hierarchical data pointing back to a root node really is valid. I think so, because of my interpretation of what replacement of a product means. I may be wrong on the details, but if you think about the development of a product in the normal case older products are  replaced by newer ones only, but there might be cases a new product turns out to be less good than it's predecessor, which I imagine could be the reason a replacement product can be replaced by it's predecessor.

In that case, I'd say you could also add A to the result, as A indirectly is/was it's own replacement product. That aside the easiest yet not most effective way is to use tha maxrecursion option to cut off infinite loops after a recursion level never reached in a normal case, which is the brute force method to avoid infinite recursions. I like both the idea of checking an anchor, but the infinite loop might not go back to the anchor. Only allowing ProductID < RepProdID would not put A into the result, which you also don't want, so that would also be ok, as that only looks for forward replacements, but then there might be a history of replacements as in a->f->b->z, which would miss b and z in that case, but surely it's avoiding recursion.

It might be easier to understand and maintain to not put the recursion into the query, but instead make a query determining only the direct replacement products and use that simpler query in a recursive function starting with a root product, collecting it's direct replacement products and in the next recursion level the replacement products for those products found etc., collecting the intermediate products into a central result list, unless a call yields no further products into that list. In each level of recursion you only need to let that recursive function call itself with products neww to the list, so recursion ends naturally.

Bye, Olaf.
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Introduction SQL Server Integration Services can read XML files, that’s known by every BI developer.  (If you didn’t, don’t worry, I’m aiming this article at newcomers as well.) But how far can you go?  When does the XML Source component become …
The Delta outage: 650 cancelled flights, more than 1200 delayed flights, thousands of frustrated customers, tens of millions of dollars in damages – plus untold reputational damage to one of the world’s most trusted airlines. All due to a catastroph…
Via a live example, show how to extract information from SQL Server on Database, Connection and Server properties
Via a live example, show how to shrink a transaction log file down to a reasonable size.

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now