Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««1234»»

Recursive Queries in SQL:1999 and SQL Server 2005 Expand / Collapse
Author
Message
Posted Sunday, November 4, 2007 9:50 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, October 5, 2013 8:27 AM
Points: 15, Visits: 118
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")



Post #418308
Posted Friday, May 16, 2008 2:42 AM


SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Monday, September 22, 2014 9:30 AM
Points: 216, Visits: 1,369
Fantastic article. Many thanks for sharing your work. :)
Post #501838
Posted Friday, May 16, 2008 5:23 AM
SSChasing Mays

SSChasing MaysSSChasing MaysSSChasing MaysSSChasing MaysSSChasing MaysSSChasing MaysSSChasing MaysSSChasing Mays

Group: General Forum Members
Last Login: Wednesday, September 17, 2014 4:02 AM
Points: 648, Visits: 1,874
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!
Post #501918
Posted Friday, May 16, 2008 6:20 AM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Today @ 9:47 AM
Points: 5,386, Visits: 9,962
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
Post #501968
Posted Friday, May 16, 2008 7:52 AM


Hall of Fame

Hall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of FameHall of Fame

Group: General Forum Members
Last Login: Yesterday @ 7:42 AM
Points: 3,688, Visits: 72,435
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 DBA
Proud member of the Anti-RBAR alliance.
For help with Performance click this link
For tips on how to post your problems
Post #502060
Posted Friday, May 16, 2008 4:48 PM
SSC Rookie

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

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, October 5, 2013 8:27 AM
Points: 15, Visits: 118
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

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Saturday, October 5, 2013 8:27 AM
Points: 15, Visits: 118
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 +



Post #502603
Posted Sunday, May 18, 2008 9:52 AM
SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Wednesday, September 10, 2014 3:19 AM
Points: 5,375, Visits: 1,391
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-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 8:40 AM
Points: 35,265, Visits: 31,754
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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #502621
« Prev Topic | Next Topic »

Add to briefcase «««1234»»

Permissions Expand / Collapse