February 13, 2007 at 10:40 am
This is a great article, but I am running into issues with trying to apply this to my own querey.
if anyone is following this string, could you look at the following and tell me if anything jumps out at you for where i am going wrong?
With tree (id, name) AS
(
Select id, name
from
clients
where
parent_id=1
Union
all (
Select
id, name
from
clients
INNER
JOIN tree t
ON
t.parent_id = t.id)
Select * from tree)
many thanks from one who is just working on this part of the database.
September 17, 2007 at 5:48 pm
Frédéric BROUARD,
Your article is awesome. It provides solutions to all my boggling SQL dilemmas.
Thanks for sharing your wisdom.
Jimi J
November 4, 2007 at 9:50 am
Answering to meg evans...
I think the good way to do this is :
[font="Courier New"]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[/font]
A + (wich means in french "see u later")
May 16, 2008 at 2:42 am
Fantastic article. Many thanks for sharing your work. 🙂
May 16, 2008 at 5:23 am
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!
May 16, 2008 at 6:20 am
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
May 16, 2008 at 7:52 am
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!
May 16, 2008 at 4:48 pm
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.
May 18, 2008 at 4:53 am
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 +
May 18, 2008 at 5:14 am
Some more tricks using CTE and recursivity...
1) How to split a string into words ?
[font="Courier New"]-- 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))
*/[/font]
2) how to concatenate words to obtain sentences
[font="Courier New"]-- 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))
*/[/font]
A +
May 18, 2008 at 9:52 am
Excellent article. Really really awesome one. You have taken sooooooooooo much time to write this one. Excellent, Brilliant!!!!!!
May 18, 2008 at 10:17 am
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...
[font="Courier New"]==============================================================================
===== 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.[/font]
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
Change is inevitable... Change for the better is not.
May 18, 2008 at 10:29 am
OK Jeff, Good one. A very helpful analysis...........
May 18, 2008 at 11:50 am
Great Article!
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]
August 7, 2008 at 6:17 am
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 ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE 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.
WITHMyResult(RelationContactContactID, SourceContactID, DestinationContactID, Hops)
AS
(
-- First itteration
SELECTRelationContactContactID,
SourceContactID,
DestinationContactID,
1 Hops
FROMtRelationContactContact rcc
UNIONALL
-- Second itteration
SELECTrcc.RelationContactContactID,
rcc.SourceContactID,
rcc.DestinationContactID,
Hops + 1 Hops
FROMtRelationContactContact rcc,
MyResultmyr
WHERE(myr.SourceContactID= rcc.SourceContactID
ORmyr.DestinationContactID= rcc.DestinationContactID
ORmyr.SourceContactID= rcc.DestinationContactID
ORmyr.DestinationContactID= rcc.SourceContactID
)
ANDmyr.RelationContactContactID<> rcc.RelationContactContactID
ANDHops < 2
)
SELECTDISTINCT RelationContactContactID, SourceContactID, DestinationContactID
FROMMyResult
WHERESourceContactID= 543
ORDestinationContactID= 543
ORDERBY
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.
Viewing 15 posts - 16 through 30 (of 34 total)
You must be logged in to reply to this topic. Login to reply