Recent PostsRecent Posts Popular TopicsPopular Topics
 Home Search Members Calendar Who's On

 Recursive Queries in SQL:1999 and SQL Server 2005 Rate Topic Display Mode Topic Options
Author
 Message
 Posted Friday, May 16, 2008 6:20 AM
 SSCertifiable Group: General Forum Members Last Login: 2 days ago @ 8:49 AM Points: 7,030, Visits: 14,716
 Excellent article, Frédéric. I have recommended this to people in the past.One thing I don't quite understand about the left and right bounds. Suppose I wanted to add a new item to your hierarchy, let's say "airship". Then the left bound for airship would be 25 and the right bound 26. But 25 is already the right bound for "air" and 26 the right bound for "all". Would I need to renumber, or is the answer to leave gaps in the sequence when doing the initial numbering?ThanksJohn
Post #501968
 Posted Friday, May 16, 2008 7:52 AM
 Hall of Fame Group: General Forum Members Last Login: Friday, September 16, 2016 12:22 PM Points: 3,849, Visits: 72,507
 This is by far one of the best articles I've read on just about any subject.As a former programming student who went network admin and then hybridded into DBA, let me say that I remember the hell of the travelling salesman problem when we did it in C.To see it broken down to about 25 lines of SQL makes me cry tears of joy. :)Bravo! --Mark Tassin MCITP - SQL Server DBAProud member of the Anti-RBAR alliance.For help with Performance click this linkFor tips on how to post your problems
Post #502060
 Posted Friday, May 16, 2008 4:48 PM
 SSC Rookie Group: General Forum Members Last Login: Friday, September 19, 2008 2:59 PM Points: 41, Visits: 41
 Thank you for a very interesting article. I did not know that SQL could be recursive; however I DID wonder if it were possible to call stored procedures recursively and was considering trying it out in my current project.One thing that I didn't see is that it is possible for a recursive procedure to trap itself in a loop if a branch points back to a parent branch in the same chain. I've worked places where I was supervisor on one project of someone who was my supervisor on another project. A prime candidate for an infinite recursion.So is there a standardized way of stopping a recursion when it loops back on itself or is that something you have to deal with on a per case basis?(Example: -Jane Smith, Role Pitcher: Subordinates None Role: Supervisor: Subordinates Fred Jones, Role project Leader: Subordinates Nigel Doe: Role Coder: Subordinates None Role Softball Coach: Subordinates Jane Smith (Causes infinite loop) Fred Jones (Causes infinite loop)etc...This is a fairly extreme example but almost any recursive process has the potential to go this way even if it's only caused by a typo.
Post #502405
 Posted Sunday, May 18, 2008 4:53 AM
 Grasshopper Group: General Forum Members Last Login: Saturday, September 19, 2015 7:50 AM Points: 15, Visits: 127
 There is no way to call recursively a SP using a simple CTE query. But you can construct an answer temp table and after call the SP by using an ordered cursor...A +
Post #502602
 Posted Sunday, May 18, 2008 5:14 AM
 Grasshopper Group: General Forum Members Last Login: Saturday, September 19, 2015 7:50 AM Points: 15, Visits: 127
 Some more tricks using CTE and recursivity...1) How to split a string into words ?-- here is the table :CREATE TABLE TRolePers( idPers int, Role varchar(50))-- containing:INSERT INTO TRolePers VALUES (1, 'RespX, RespY')INSERT INTO TRolePers VALUES (2, 'Admin')INSERT INTO TRolePers VALUES (3, 'RespX, RespZ, RespY')/*Find the query that can split the sentence into the columns, every words been delimited par the comma.How to obtain such a result ?idPers Role----------- --------------------------------------------------1 RespX1 RespY2 Admin3 RespX3 respY3 RespZ*/-- solution :WITH T AS(SELECT idPers, CASE WHEN CHARINDEX(',', Role) > 0 THEN LTRIM(SUBSTRING(Role, 1, CHARINDEX(',', Role) - 1)) ELSE Role END AS UnRole, LTRIM(SUBSTRING(Role, CHARINDEX(',', Role) + 1, LEN(Role) - CHARINDEX(',', Role))) AS LesAutresRolesFROM TRolePersUNION ALLSELECT RP.idPers, CASE WHEN CHARINDEX(',', LesAutresRoles) > 0 THEN LTRIM(SUBSTRING(LesAutresRoles, 1, CHARINDEX(',', LesAutresRoles) - 1)) ELSE LesAutresRoles END, CASE WHEN CHARINDEX(',', LesAutresRoles) > 0 THEN LTRIM(SUBSTRING(LesAutresRoles, CHARINDEX(',', LesAutresRoles) + 1, LEN(LesAutresRoles) - CHARINDEX(',', LesAutresRoles))) ELSE NULL ENDFROM TRolePers RP INNER JOIN T ON T.idPers = RP.idPersWHERE LesAutresRoles IS NOT NULL)SELECT DISTINCT idPers, UnRole As RoleFROM TORDER BY 1, 2/*idPers Role----------- --------------------------------------------------1 RespX1 RespY2 Admin3 RespX3 respY3 RespZ(6 ligne(s) affectée(s))*/2) how to concatenate words to obtain sentences-- Here is a table :CREATE TABLE T_PHRASE_PHR(PHR_ID INTEGER NOT NULL, PHR_MOT_POSITION INTEGER NOT NULL, PHR_MOT VARCHAR(32) NOT NULL, CONSTRAINT PK_PHR PRIMARY KEY (PHR_ID, PHR_MOT_POSITION));-- containing :INSERT INTO T_PHRASE_PHR VALUES (1, 1, 'Le')INSERT INTO T_PHRASE_PHR VALUES (1, 2, 'petit')INSERT INTO T_PHRASE_PHR VALUES (1, 3, 'chat')INSERT INTO T_PHRASE_PHR VALUES (1, 4, 'est')INSERT INTO T_PHRASE_PHR VALUES (1, 5, 'mort')INSERT INTO T_PHRASE_PHR VALUES (2, 1, 'Les')INSERT INTO T_PHRASE_PHR VALUES (2, 2, 'sanglots')INSERT INTO T_PHRASE_PHR VALUES (2, 3, 'longs')INSERT INTO T_PHRASE_PHR VALUES (2, 4, 'des')INSERT INTO T_PHRASE_PHR VALUES (2, 5, 'violons')INSERT INTO T_PHRASE_PHR VALUES (2, 6, 'de')INSERT INTO T_PHRASE_PHR VALUES (2, 7, 'l''')INSERT INTO T_PHRASE_PHR VALUES (2, 8, 'automne')INSERT INTO T_PHRASE_PHR VALUES (2, 9, 'blessent')INSERT INTO T_PHRASE_PHR VALUES (2, 10, 'mon')INSERT INTO T_PHRASE_PHR VALUES (2, 11, 'coeur')INSERT INTO T_PHRASE_PHR VALUES (2, 12, 'd''')INSERT INTO T_PHRASE_PHR VALUES (2, 13, 'une')INSERT INTO T_PHRASE_PHR VALUES (2, 14, 'langueur')INSERT INTO T_PHRASE_PHR VALUES (2, 15, 'monotone')/*Find a query that can retrieve the sentence by compounding the words in the column PHR_MOT_POSITION order.How to obtain such a result ?id PHRASE----------- ------------------------------------------------------------------------------------------1 Le petit chat est mort.2 Les sanglots longs des violons de l'automne blessent mon coeur d'une langueur monotone.*/-- solutionWITH phrases (phrase, id, position)AS(SELECT CAST(PHR_MOT AS VARCHAR(max)) + CASE WHEN SUBSTRING(PHR_MOT, LEN(PHR_MOT), 1) = '''' THEN '' ELSE ' ' END, PHR_ID, PHR_MOT_POSITION FROM T_PHRASE_PHRWHERE PHR_MOT_POSITION = 1UNION ALLSELECT phrase + CAST(PHR_MOT AS VARCHAR(max)) + CASE WHEN SUBSTRING(PHR_MOT, LEN(PHR_MOT), 1) = '''' THEN '' ELSE ' ' END AS PHRASE, PHR_ID, PHR_MOT_POSITION FROM T_PHRASE_PHR AS suiv INNER JOIN phrases ON suiv.PHR_ID = phrases.id AND suiv.PHR_MOT_POSITION = phrases.position + 1),maxphraseAS(SELECT id, MAX(position) AS maxpositionFROM phrasesGROUP BY id)SELECT P.id, phrase + '.' AS PHRASEFROM phrases AS P INNER JOIN maxphrase AS M ON P.id = M.id AND P.position = M.maxpositionORDER BY id/*id PHRASE----------- ------------------------------------------------------------------------------------------1 Le petit chat est mort.2 Les sanglots longs des violons de l'automne blessent mon coeur d'une langueur monotone.(2 ligne(s) affectée(s))*/A +
Post #502603
 Posted Sunday, May 18, 2008 9:52 AM
 SSCertifiable Group: General Forum Members Last Login: Wednesday, April 20, 2016 3:23 AM Points: 6,049, Visits: 1,407
 Excellent article. Really really awesome one. You have taken sooooooooooo much time to write this one. Excellent, Brilliant!!!!!!
Post #502615
 Posted Sunday, May 18, 2008 10:17 AM
 SSC-Forever Group: General Forum Members Last Login: Yesterday @ 9:09 PM Points: 42,046, Visits: 39,429
 Nicely done… Recursion is fine for ad hoc hierarchical lookups, but, if I may suggest, using recursion to "step through" things, like that which occurs in a "split", is a bit slow because recursion is a form of "hidden RBAR". The use of a "Tally" or "Numbers" table is better suited for such counting efforts as "splits".` SELECT rp.IDPers, SUBSTRING(','+rp.Role+',',N+1,CHARINDEX(',',','+rp.Role+',',N+1)-N-1) AS Value FROM dbo.Tally t CROSS JOIN dbo.tRolePers rp WHERE N < LEN(','+rp.Role+',') AND SUBSTRING(','+rp.Role+',',N,1) = ',' `Here're the results of the two split methods on a 10,000 row example...=================================================================================== Recursive CTE Method =====(100000 row(s) affected)Table 'Worktable'. Scan count 2, logical reads 582741, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Table 'TRolePers'. Scan count 1, logical reads 200109, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.SQL Server Execution Times: CPU time = 7750 ms, elapsed time = 11879 ms.=================================================================================== Tally Table Method =====(100000 row(s) affected)Table 'Tally'. Scan count 10000, logical reads 30000, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Table 'TRolePers'. Scan count 1, logical reads 109, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.SQL Server Execution Times: CPU time = 782 ms, elapsed time = 3545 ms.Just in case someone adopts the recursive method, please be aware that the recursive method posted does not produce the correct output if some of the embedded elements or the last element had nothing in it (the missing elements are not returned as a position in the output).`--===== A table is not properly formed unless a Primary Key has been assigned ALTER TABLE dbo.TRolePers ADD CONSTRAINT PK_TRolePers_IDPers PRIMARY KEY CLUSTERED (IDPers)GO-- here is the table :CREATE TABLE TRolePers( idPers int, Role varchar(50))-- containing:INSERT INTO TRolePers VALUES (1, 'RespX,RespY')INSERT INTO TRolePers VALUES (2, 'Admin')INSERT INTO TRolePers VALUES (3, 'RespX,RespZ,RespY')INSERT INTO TRolePers VALUES (3, 'Resp01,,Resp03,Resp04,')`For more information on the "Tally" or "Numbers" table, please see the following...http://www.sqlservercentral.com/articles/TSQL/62867/ --Jeff Moden"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".First step towards the paradigm shift of writing Set Based code: Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column." Helpful Links:How to post code problemsHow to post performance problems
Post #502621
 Posted Sunday, May 18, 2008 10:29 AM
 SSCertifiable Group: General Forum Members Last Login: Wednesday, April 20, 2016 3:23 AM Points: 6,049, Visits: 1,407
 OK Jeff, Good one. A very helpful analysis...........
Post #502625
 Posted Sunday, May 18, 2008 11:50 AM
 SSCrazy Eights Group: General Forum Members Last Login: Tuesday, October 25, 2016 7:17 AM Points: 9,298, Visits: 9,517
 Great Article! -- RBarryYoung, (302)375-0451 blog: MovingSQL.com, Twitter: @RBarryYoungProactive Performance Solutions, Inc. "Performance is our middle name."
Post #502636
 Posted Thursday, August 7, 2008 6:17 AM
 Forum Newbie Group: General Forum Members Last Login: Saturday, August 9, 2008 6:39 AM Points: 3, Visits: 10
 Hi all,I've got a problem to solve and I don't seem to be able to get the grip on it I need. The problem is as follows. We have a table called RelationContactContact like so:`SET ANSI_NULLS ONGOSET QUOTED_IDENTIFIER ONGOCREATE TABLE [dbo].[tRelationContactContact]( [RelationContactContactID] [int] IDENTITY(1,1) NOT NULL, [SourceContactID] [int] NULL, [DestinationContactID] [int] NULL CONSTRAINT [PK_PK_PersonInstitutionRelations] PRIMARY KEY CLUSTERED ( [RelationContactContactID] ASC)`I've removed all the Fields that aren't interesting for the problem.What it represents is a self-referencing table via the Fields SourceContactID and DestinationContactID. In fact any Contact (in a separate Contact Table) can have a relation to any other Contact. In fact this is not a Tree structure but a Cloud of relations. Circular Connections are possible (A has a relation to B, B has a relation to C, C has a relation to A). This is also where the problem begins.I've tried to write a Query that resolves all the Connections 1 Contact can have (i.e. A -> B -> C). Here's what I've tried so far. It works but it is way to slow, when the test on the Hops allows values over 2, and has a cartesian product which in the end is filtered out by the SELECT DISTINCT.`WITH MyResult(RelationContactContactID, SourceContactID, DestinationContactID, Hops)AS( -- First itteration SELECT RelationContactContactID, SourceContactID, DestinationContactID, 1 Hops FROM tRelationContactContact rcc UNION ALL -- Second itteration SELECT rcc.RelationContactContactID, rcc.SourceContactID, rcc.DestinationContactID, Hops + 1 Hops FROM tRelationContactContact rcc, MyResult myr WHERE ( myr.SourceContactID = rcc.SourceContactID OR myr.DestinationContactID = rcc.DestinationContactID OR myr.SourceContactID = rcc.DestinationContactID OR myr.DestinationContactID = rcc.SourceContactID ) AND myr.RelationContactContactID <> rcc.RelationContactContactID AND Hops < 2)SELECT DISTINCT RelationContactContactID, SourceContactID, DestinationContactIDFROM MyResultWHERE SourceContactID = 543OR DestinationContactID = 543ORDER BY RelationContactContactID, SourceContactID, DestinationContactID`What I need to do is of course filter out the result of the first (anchor) query in the Select of the second (recursive) query. But I also need to match the field Destination- and SourceContactID with the previous result. T-SQL doen't allow CTE's to use the intermediate result twice. So I'm a bit stuck here. Any ideas?Cheers,Paul.
Post #548218

 Permissions