Click here to monitor SSC
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Recursive Queries in SQL:1999 and SQL Server 2005


Recursive Queries in SQL:1999 and SQL Server 2005

Author
Message
Frédéric BROUARD
Frédéric BROUARD
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
Points: 15 Visits: 127
Answering to meg evans...

I think the good way to do this is :

With tree (id, name)
AS
(Select parent_id, name
from clients
where parent_id = 1
Union all
Select parent_id, name
from clients c
INNER JOIN tree t
ON c.id = t.id
)
Select *
from tree


A + (wich means in french "see u later")



humbleDBA
humbleDBA
SSC Veteran
SSC Veteran (220 reputation)SSC Veteran (220 reputation)SSC Veteran (220 reputation)SSC Veteran (220 reputation)SSC Veteran (220 reputation)SSC Veteran (220 reputation)SSC Veteran (220 reputation)SSC Veteran (220 reputation)

Group: General Forum Members
Points: 220 Visits: 1498
Fantastic article. Many thanks for sharing your work. Smile
David McKinney
David McKinney
Right there with Babe
Right there with Babe (769 reputation)Right there with Babe (769 reputation)Right there with Babe (769 reputation)Right there with Babe (769 reputation)Right there with Babe (769 reputation)Right there with Babe (769 reputation)Right there with Babe (769 reputation)Right there with Babe (769 reputation)

Group: General Forum Members
Points: 769 Visits: 2090
Bonjour Frédéric,

Ca pourrait etre tres interessant comme projet - de traduire ton (tes) livre(s). Je sais pas si j'aurais le temps, par contre! Mais envoie-moi une message si l'idee t'interesse.

En tout cas, c'est un article vraiment exceptionnel!

Bravo!
John Mitchell-245523
John Mitchell-245523
SSCertifiable
SSCertifiable (7.4K reputation)SSCertifiable (7.4K reputation)SSCertifiable (7.4K reputation)SSCertifiable (7.4K reputation)SSCertifiable (7.4K reputation)SSCertifiable (7.4K reputation)SSCertifiable (7.4K reputation)SSCertifiable (7.4K reputation)

Group: General Forum Members
Points: 7420 Visits: 15114
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?

Thanks
John
mtassin
mtassin
SSCarpal Tunnel
SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)SSCarpal Tunnel (4.1K reputation)

Group: General Forum Members
Points: 4101 Visits: 72512
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. Smile

Bravo!



--Mark Tassin
MCITP - SQL Server DBA
Proud member of the Anti-RBAR alliance.
For help with Performance click this link
For tips on how to post your problems
ntaylor-739763
ntaylor-739763
SSC Rookie
SSC Rookie (41 reputation)SSC Rookie (41 reputation)SSC Rookie (41 reputation)SSC Rookie (41 reputation)SSC Rookie (41 reputation)SSC Rookie (41 reputation)SSC Rookie (41 reputation)SSC Rookie (41 reputation)

Group: General Forum Members
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.
Frédéric BROUARD
Frédéric BROUARD
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
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 +



Frédéric BROUARD
Frédéric BROUARD
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
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 RespX
1 RespY
2 Admin
3 RespX
3 respY
3 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 LesAutresRoles

FROM TRolePers
UNION ALL
SELECT 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
END
FROM TRolePers RP
INNER JOIN T
ON T.idPers = RP.idPers
WHERE LesAutresRoles IS NOT NULL
)
SELECT DISTINCT idPers, UnRole As Role
FROM T
ORDER BY 1, 2

/*
idPers Role
----------- --------------------------------------------------
1 RespX
1 RespY
2 Admin
3 RespX
3 respY
3 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.

*/

-- solution
WITH
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_PHR
WHERE PHR_MOT_POSITION = 1
UNION ALL
SELECT 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
),
maxphrase
AS
(
SELECT id, MAX(position) AS maxposition
FROM phrases
GROUP BY id
)
SELECT P.id, phrase + '.' AS PHRASE
FROM phrases AS P
INNER JOIN maxphrase AS M
ON P.id = M.id
AND P.position = M.maxposition
ORDER 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 +



Anipaul
Anipaul
SSCertifiable
SSCertifiable (6.3K reputation)SSCertifiable (6.3K reputation)SSCertifiable (6.3K reputation)SSCertifiable (6.3K reputation)SSCertifiable (6.3K reputation)SSCertifiable (6.3K reputation)SSCertifiable (6.3K reputation)SSCertifiable (6.3K reputation)

Group: General Forum Members
Points: 6275 Visits: 1407
Excellent article. Really really awesome one. You have taken sooooooooooo much time to write this one. Excellent, Brilliant!!!!!!



Jeff Moden
Jeff Moden
SSC-Forever
SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)SSC-Forever (45K reputation)

Group: General Forum Members
Points: 45022 Visits: 39887
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.
Although they tell us that they want it real bad, our primary goal is to ensure that we dont actually give it to them that way.
Although change is inevitable, change for the better is not.
Just because you can do something in PowerShell, doesnt mean you should. Wink

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search