Les requêtes récursives (partie 3/3)

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.

Philippe Geiger

24 août 2012

SQL Server

Administration, Architecture, CTE, Récursivité, SQL Server

21 réponses à « Les requêtes récursives (partie 3/3) »

Les requêtes récursives (partie 1/3) « SQL Server dans le détail

25 août 2012

[…] 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
Les requêtes récursives (partie 2/3) « SQL Server dans le détail

25 août 2012

[…] 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
Pat

7 juillet 2014

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
acksad02

4 septembre 2014

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
1. acksad02
  
  4 septembre 2014
  
  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
  1. PGeiger
    
    4 septembre 2014
    
    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
Alain Touret

3 mars 2015

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
1. PGeiger
  
  3 mars 2015
  
  Bonjour,
  
  Je suis d’accord avec votre remarque.
  Merci pour votre commentaire.
  Bien à vous,
  PGeiger
  
  J’aimeJ’aime
olivier

2 juin 2015

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
1. PGeiger
  
  2 juin 2015
  
  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
  1. olivier
    
    2 juin 2015
    
    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
  2. PGeiger
    
    2 juin 2015
    
    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
  3. olivier
    
    2 juin 2015
    
    Merci pour votre réponse rapide
    
    J’aimeJ’aime
zac

15 juillet 2019

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
zac

15 juillet 2019

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
zac

15 juillet 2019

peut etre ma version de sql serveur ? = sql server 2008

J’aimeJ’aime
1. Philippe Geiger
  
  15 juillet 2019
  
  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
zac

15 juillet 2019
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
```
UNION ALL

SELECT i + 1
FROM CompteurCTE
WHERE i < 6
)
```
— Appel de la CTE
SELECT *
FROM CompteurCTE;

j’obtiens bien
i
1
2
3
4
5
6

J’aimeJ’aime
1. Philippe Geiger
  
  15 juillet 2019
  
  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
  1. zac
    
    16 juillet 2019
    
    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
  2. Philippe Geiger
    
    16 juillet 2019
    
    Bonjour,
    Bonne continuation.
    Bien à vous,
    PGeiger
    
    J’aimeJ’aime