L’objet de ces trois articles est d’aborder un problème qui ne semble pas possible de réaliser simplement avec une requête SQL, la récursivité. La solution réside dans les CTE (expressions de tables communes).
Dans le premier article, nous posons les bases du problème. Dans le deuxième article, nous expliquons ce que sont les expressions CTE. Enfin, le dernier article montre comment la récursivité est traitée avec les expressions CTE.
Le principe de la récursivité
Voici comment Wikipédia définit la récursivité :
En informatique et en logique, une fonction ou plus généralement un algorithme qui contient un appel à elle-même est dite récursive. Deux fonctions peuvent s’appeler l’une l’autre, on parle alors de récursivité croisée.
Dans un autre article, nous trouvons l’exemple suivant :
Prenons maintenant un exemple issu des mathématiques, celui de la factorielle. Celle-ci se définit intuitivement pour des entiers positifs par la fonction suivante :
L’idée de la récursivité est d’utiliser une définition équivalente, à savoir une suite récurrente :
Le fait d’écrire que n! = n.(n-1)! signifie que la fonction factorielle peut être définie de façon récursive : en d’autres termes, la factorielle de n est la factorielle de n-1 multipliée par n. Donc, pour calculer la factorielle de n, il faut d’abord calculer la factorielle de n-1 jusqu’à ce que nous arrivions à ce que n vaut 1 et dans ce cas la factorielle de 1 vaut 1.
La solution du problème
Ces bases étant posées, voici comment nous écrivons une requête récursive utilisant une expression régulière.
Ce qui ne change pas, c’est de décrire le nom de l’expression CTE ainsi que les colonnes associées :
WITH [DirectReports]([ManagerID],
[EmployeeID],
[FirstName],
[LastName],
[Title])
Ensuite, nous écrivons ce qui s’appelle l’accroche, c’est à dire la condition de départ. Ici, l’accroche est de définir le nom du plus haut responsable, c’est-à-dire celui n’a pas de manager :
SELECT e.[ManagerID],
e.[EmployeeID],
e.[FirstName],
e.[LastName],
e.[Title]
FROM [dbo].[MyEmployees] e
WHERE [ManagerID] IS NULL
La troisième partie correspond à la définition de la récursivité. Pour cela, nous allons utiliser le nom de l’expression CTE dans le corps de l’expression CTE lui-même. Dans notre cas ; l’instruction est de lister les employés qui dépendent du manager renvoyé dans l’expression CTE :
UNION ALL
SELECT e.[ManagerID],
e.[EmployeeID],
e.[FirstName],
e.[LastName],
e.[Title]
FROM [dbo].[MyEmployees] e
INNER JOIN [DirectReports] d
ON e.[ManagerID] = d.[EmployeeID]
Les deux instructions dans le corps de l’expression CTE sont jointes par une clause UNION ALL.
La quatrième et dernière partie est donc la construction de l’instruction principale. Ici, nous ferons simplement la mise en forme du résultat de l’expression CTE. L’instruction principale pourrait être nettement plus complexe avec notamment des jointures avec d’autres tables :
SELECT [EmployeeID],
[FirstName] + ' ' + [LastName] AS [EmployeeName],
[Title],
[ManagerID]
FROM [DirectReports]
ORDER BY [EmployeeID]
L’ultime tâche est donc d’associer toutes les parties pour obtenir la requête finale :
WITH [DirectReports]([ManagerID],
[EmployeeID],
[FirstName],
[LastName],
[Title])
AS(
-- Point de départ
SELECT e.[ManagerID],
e.[EmployeeID],
e.[FirstName],
e.[LastName],
e.[Title]
FROM [dbo].[MyEmployees] e
WHERE [ManagerID] IS NULL
UNION ALL
-- Définition de la récursivité
SELECT e.[ManagerID],
e.[EmployeeID],
e.[FirstName],
e.[LastName],
e.[Title]
FROM [dbo].[MyEmployees] e
INNER JOIN [DirectReports] d
ON e.[ManagerID] = d.[EmployeeID])
-- Table de sortie référençant la table CTE
SELECT [EmployeeID],
[FirstName] + ' ' + [LastName] As [EmployeeName],
[Title],
[ManagerID]
FROM [DirectReports]
ORDER BY [EmployeeID];
Voici le résultat de la requête :
| EmployeeID | EmployeeName | Title | ManagerID |
|---|---|---|---|
| 1 | Ken Sanchez | Chief Executive Officer | NULL |
| 273 | Brian Welcker | Vice President of Sales | 1 |
| 274 | Stephen Jiang | North American Sales Manager | 273 |
| 275 | Michael Blythe | Sales Representative | 274 |
| 276 | Linda Mitchell | Sales Representative | 274 |
| 285 | Syed Abbas | Pacific Sales Manager | 273 |
| 286 | Lynn Tsoflias | Sales Representative | 285 |
| 287 | David Bradley | Marketing Manager | 273 |
| 288 | Mary Gibson | Marketing Specialist | 287 |
Amélioration de la requête
Il est possible d’améliorer la requête que nous avons obtenue au paragraphe. L’idée est d’ajouter une colonne qui détermine le niveau de l’employé dans la hiérarchie (cette colonne nous servira à ajouter une indentation avant le titre de la personne) ainsi qu’une autre colonne pour afficher la liste de la hiérarchie des employés. Voici cette nouvelle requête :
WITH [DirectReports]([ManagerID],
[EmployeeID],
[FirstName],
[LastName],
[Title],
[Level],
[HierarchyChain])
AS(
-- Point de départ
SELECT e.[ManagerID],
e.[EmployeeID],
e.[FirstName],
e.[LastName],
e.[Title],
0 AS [Level],
CAST(e.[EmployeeID] AS NVARCHAR(1000))
FROM [dbo].[MyEmployees] e
WHERE [ManagerID] IS NULL
UNION ALL
-- Définition de la récursivité
SELECT e.[ManagerID],
e.[EmployeeID],
e.[FirstName],
e.[LastName],
e.[Title], [Level] + 1,
CAST(([HierarchyChain] + N'/' +
CAST(e.[EmployeeID] AS NVARCHAR(10)))
AS NVARCHAR(1000))
FROM [dbo].[MyEmployees] e
INNER JOIN [DirectReports] d
ON e.[ManagerID] = d.[EmployeeID])
-- Table de sortie référençant la table CTE
SELECT [EmployeeID],
[FirstName] + ' ' + [LastName] AS [EmployeeName],
SPACE(4 * [Level]) + [Title] AS [Title],
[ManagerID],
[HierarchyChain]
FROM [DirectReports]
ORDER BY [EmployeeID];
Et voici le résultat de cette deuxième requête :
| EmployeeID | EmployeeName | Title | ManagerID | HierarchyChain |
|---|---|---|---|---|
| 1 | Ken Sanchez | Chief Executive Officer | NULL | 1 |
| 273 | Brian Welcker | Vice President of Sales | 1 | 1/273 |
| 274 | Stephen Jiang | North American Sales Manager | 273 | 1/273/274 |
| 275 | Michael Blythe | Sales Representative | 274 | 1/273/274/275 |
| 276 | Linda Mitchell | Sales Representative | 274 | 1/273/274/276 |
| 285 | Syed Abbas | Pacific Sales Manager | 273 | 1/273/285 |
| 286 | Lynn Tsoflias | Sales Representative | 285 | 1/273/285/286 |
| 287 | David Bradley | Marketing Manager | 273 | 1/273/287 |
| 288 | Mary Gibson | Marketing Specialist | 287 | 1/273/287/288 |
Maintenant, intéressons-nous au plan d’exécution de la première des requêtes récursives :
Ce plan d’exécution montre que l’ensemble du traitement de l’instruction avec l’expression CTE est totalement pris en charge par l’optimiseur statistique. Le plan d’exécution de la deuxième requête est strictement identique à celui de la première à une exception près, l’ajout de 4 blocs « Compute Scalar » correspondants aux calculs des colonnes Level et HierarchyChain :
Pour aller plus loin, il existe depuis SQL Server 2008 un nouveau type de données : HierarchyID. Ce type (définit comme un objet SQL-CLR) permet de stocker et de parcourir une arborescence. Il ne permet pas de traiter une récursivité comme nous venons de le voir ici. Pour plus d’information, nous nous reporterons à cet article.
Bien à vous.
De Microsoft, de sa plateforme data et d'autres choses 
21 réponses à « Les requêtes récursives (partie 3/3) »
[…] du problème. Dans le deuxième article, nous expliquons ce que sont les expressions CTE. Enfin, le dernier article montre comment la récursivité est traitée avec les expressions […]
J’aimeJ’aime
[…] du problème. Dans le deuxième article, nous expliquons ce que sont les expressions CTE. Enfin, le dernier article montre comment la récursivité est traitée avec les expressions […]
J’aimeJ’aime
Bonjour et merci Monsieur,
vous venez de m’enlever une épine au pied par l’article « Les requêtes récursives (partie 3/3) »
Patrick
J’aimeJ’aime
Bonjour. Merci pour cet excellent article qui est exactement la réponse à mon problème.
Néanmoins j’ai une question:
Je voudrais que le résultat soit sous la forme de données a format XML afin de l’afficher sur une page web avec de balises et .
Comment procéder?
Merci.
Kader
J’aimeJ’aime
Rebonjour,
Cela fait déjà 3 jours que cherche un moyen pour y parvenir et il a fallu que je pose la question ici pour trouver la réponse une heure plus tard.
Pour ceux qui se retrouveraient dans le même cas que moi, voici le lien.
http://stackoverflow.com/questions/14765937/cte-and-for-xml-to-generate-nested-xml
Cordialement.
Kader
J’aimeJ’aime
Bonjour,
Content que vous ayez trouver la réponse à votre problématique.
Je vous souhaite une continuation.
Bien à vous.
PGeiger
J’aimeAimé par 1 personne
Merci pour cet article très clair.
Les opérateurs lag et lead introduits dans la version 2012 complètent l’arsenal des requêtes récursives. Certains auteurs proposent des équivalents pour les versions précédentes.
J’aimeJ’aime
Bonjour,
Je suis d’accord avec votre remarque.
Merci pour votre commentaire.
Bien à vous,
PGeiger
J’aimeJ’aime
Bonjour j’essaye de construire une fonction recursive depuis plusieurs jours mais je bloque.
j’ai une table avec un id dossier et une date de reception de documents, je voudrais en resultat l’id dossier avec en 2 ème champ l’ensemble des dates à laquelle j’ai reçu des documents …
J’ai donc construis la requete suivante
WITH DOS_PIECE_CTE (id_dossier, date_reception_liste) AS
( — Point de départ
SELECT e.id_dossier,
CAST(e.date_reception AS date )
FROM DOS_PIECE AS e
WHERE id_dossier = ‘336400’ UNION ALL
— Définition de la récursivité
SELECT e.id_dossier,
CAST((date_reception_liste + N’/’ + CAST(e.date_reception AS VARCHAR(10))) AS VARCHAR(1000))
FROM DOS_PIECE AS e
INNER JOIN DOS_PIECE_CTE AS d ON d.id_dossier = e.id_dossier )
— Table de sortie référençant la table CTE
SELECT date_reception_liste
FROM DOS_PIECE_CTE
J’obtiens le message d’erreur suivant :
SQL error #1:ERROR: relation « dos_piece_cte » does not exist
Détail : There is a WITH item named « dos_piece_cte », but it cannot be referenced from this part of the query.
Indice : Use WITH RECURSIVE, or re-order the WITH items to remove forward references.
Position : 389
Pouvez vous m’aider sur le sujet ?
Merci
J’aimeJ’aime
Bonjour,
Deux remarques :
1) Le message d’erreur ne correspond pas au format standard des messages d’erreur de SQL Server. Utiliser-vous des composants qui réécrivent les requêtes comme ODBC. Si c’est le cas, il faudra demander à ces composants de passer la requête directement au serveur sans réécriture de celui-ci.
2) Je suis étonné de votre condition de jointure : « d.id_dossier = e.id_dossier », cela ne ressemble pas à une condition de récursivité. Pour la table nommé « e », la valeur de id_dossier sera forcément ‘336400’. Si tel est le cas, une requête non récursive existe.
Bien à vous,
PGeiger
J’aimeJ’aime
Merci en effet, j’utilise jdbc mais je ne sais pas comment passer la requete sans réécriture,
sinon il me faut en effet, une concaténation des dates de réception sur un seul enregistrement mais mon niveau en SQL et mes recherches ne m’ont pas permis jusqu’a présent de trouver la solution, si vous en avez une ou je suis preneur de votre aide.
Merci
J’aimeJ’aime
Pour JDBC, je ne peux pas vous répondre car je ne connais pas.
Si votre problématique est de transformer une colonne de valeur en une liste horizontal, il y a plusieurs solutions : passer par un faux XML ( http://blogs.msdn.com/b/guruketepalli/archive/2014/01/29/sql-server-concatenate-row-values-using-t-sql.aspx) ou encore les curseurs si le nombre de valeurs n’est pas trop important.
Bien à vous,
PG
J’aimeJ’aime
Merci pour votre réponse rapide
J’aimeJ’aime
bonjour
je bataille sur le sujet
je ne comprends pas pk ma req recusrive ne retourne que les niveaux 0 et 1
WITH PDM_LINKS_VW01CTE
–)
AS
(
select adrnode,ADRFATHER,OBJECTIDENT,0 as i
from PDM_LINKS_VW01
where
ADRLINK=0– and OBJECTTYPE=’OT08′
and OBJECTIDENT=’861v4′
union all
select TOUS.adrnode,TOUS.ADRFATHER,TOUS.OBJECTIDENT,i+1
from PDM_LINKS_VW01 TOUS
— inner join PDM_LINKS_VW01 VWf
— on vwf.adrlink<>0 and VWf.ADRFATHER=VWp.adrnode
–where vwp.OBJECTTYPE=’OT08′
inner join PDM_LINKS_VW01CTE pere
on pere.adrnode =TOUS.ADRFATHER
)
select * from PDM_LINKS_VW01CTE;
2390126 0 861v4 0
2390127 2390126 115v2 1
2390128 2390126 84v1 1
2390129 2390126 496v1 1
2390130 2390126 47v1 1
2390131 2390126 87v1 1
2390132 2390126 64v1 1
2390133 2390126 259v1 1
etc..
J’aimeJ’aime
avec les nom d’entêtes de cols
adrnode ADRFATHER OBJECTIDENT i
2390126 0 861v4 0
2390127 2390126 115v2 1
2390128 2390126 84v1 1
2390129 2390126 496v1 1
2390130 2390126 47v1 1
2390131 2390126 87v1 1
2390132 2390126 64v1 1
2390133 2390126 259v1 1
J’aimeJ’aime
peut etre ma version de sql serveur ? = sql server 2008
J’aimeJ’aime
Bonjour zac,
J’ai vérifié, les CTE récursifs sont disponibles dans SQL Server 2008. J’attire votre attention sur le fait que tous les supports sur SQL Server 2008 et SQL Server 2008 R2 ne sont plus disponibles depuis quelques jours. Ces versions ont plus de 10 ans.
Ensuite, votre script a l’air juste à la lecture.
Avez-vous bien vérfier que les valeurs 2390127, 2390128, etc apparaissent dans le champs ADRFATHER de la table PDM_LINKS_VW01 ?
Bien à vous,
PGeiger
J’aimeJ’aime
bonjour et merci pour votre retour, un vrai casse tète cette histoire
merci nous allons bientôt migrer sur la version 2012 de sql server,
je ne comprends vraiment pas mon pb, si je raisonne sur un exemple plus simple, le pere de haut niveau est 2397v1
2397v1
-2872v1
–179v1
–3038v1
–3039v1
–2480v1
–3040v1
–2482v1
–2481v1
–3041v1
–2267v1
si je joue
WITH PDM_LINKS_VW01CTE
–)
AS
(
select adrview,adrnode,ADRFATHER,OBJECTIDENT,0 as i
from PDM_LINKS_VW01
where
ADRLINK=0– and OBJECTTYPE=’OT08′
and OBJECTIDENT=’2397v1′
union all
select tous.adrview,TOUS.adrnode,TOUS.ADRFATHER,TOUS.OBJECTIDENT,i+1
from PDM_LINKS_VW01 TOUS
— inner join PDM_LINKS_VW01 VWf
— on vwf.adrlink<>0 and VWf.ADRFATHER=VWp.adrnode
–where vwp.OBJECTTYPE=’OT08′
inner join PDM_LINKS_VW01CTE pere
on pere.adrnode =TOUS.ADRFATHER and pere.adrview=tous.adrview
)
select * from PDM_LINKS_VW01CTE;
j’obtiens
adrview adrnode ADRFATHER OBJECTIDENT i
26033 786832 0 2397v1 0
26033 786833 786832 2872v1 1
puis je joue
WITH PDM_LINKS_VW01CTE
–)
AS
(
select adrview,adrnode,ADRFATHER,OBJECTIDENT,0 as i
from PDM_LINKS_VW01
where
ADRLINK=0– and OBJECTTYPE=’OT08′
and OBJECTIDENT=’2872v1′
union all
select tous.adrview,TOUS.adrnode,TOUS.ADRFATHER,TOUS.OBJECTIDENT,i+1
from PDM_LINKS_VW01 TOUS
— inner join PDM_LINKS_VW01 VWf
— on vwf.adrlink<>0 and VWf.ADRFATHER=VWp.adrnode
–where vwp.OBJECTTYPE=’OT08′
inner join PDM_LINKS_VW01CTE pere
on pere.adrnode =TOUS.ADRFATHER and pere.adrview=tous.adrview
)
select * from PDM_LINKS_VW01CTE;
cela me retourne bien
adrview adrnode ADRFATHER OBJECTIDENT i
24602 5101695 0 2872v1 0
24602 5101696 5101695 179v1 1
24602 5101697 5101695 3038v1 1
24602 5101698 5101695 3039v1 1
24602 5101699 5101695 2480v1 1
24602 5101700 5101695 3040v1 1
24602 5101701 5101695 2482v1 1
24602 5101702 5101695 2481v1 1
24602 5101703 5101695 3041v1 1
24602 5101704 5101695 2267v1 1
mais pas de recursivité en une seule fois
pourtant
en jouant simplement
WITH CompteurCTE
AS (
SELECT 1 AS i
— Appel de la CTE
SELECT *
FROM CompteurCTE;
j’obtiens bien
i
1
2
3
4
5
6
J’aimeJ’aime
Bonsoir,
J’aimerai attirer votre attention sur le fait que pour votre objet identifié 2872v1 vous n’avez pas les même valeurs entre les deux requêtes : « 26033 786833 786832 » vs « 24602 5101695 0 ».
Cela explique la rupture de la récursivité : ces deux objets ne respectent pas votre condition de jointure (pere.adrnode =TOUS.ADRFATHER and pere.adrview=tous.adrview).
Vous pourriez vérifier cela ?
Bien à vous,
PGeiger
J’aimeJ’aime
bonjour
je comprends
actuellement l’affichage de l’arborescence est géré via une page web utilisant le langage c#.
la récursivité au niveau de la base de données n’existe pas sur cette seule condition pere.adrnode TOUS.ADRFATHER and pere.adrview=tous.adrview.
je vais tout de même chercher s il existe un autre champs permettant de faire ce lien entre mes 2 reqs
c’est très gentil à vous d’avoir passé du temps sur mon sujet.
J’aimeJ’aime
Bonjour,
Bonne continuation.
Bien à vous,
PGeiger
J’aimeJ’aime