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

Logo SQL Server

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 :

Formule de la factorielle

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 :

EmployeeIDEmployeeNameTitleManagerID
1Ken SanchezChief Executive OfficerNULL
273Brian WelckerVice President of Sales1
274Stephen JiangNorth American Sales Manager273
275Michael BlytheSales Representative274
276Linda MitchellSales Representative274
285Syed AbbasPacific Sales Manager273
286Lynn TsofliasSales Representative285
287David BradleyMarketing Manager273
288Mary GibsonMarketing Specialist287

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 :

EmployeeIDEmployeeNameTitleManagerIDHierarchyChain
1Ken SanchezChief Executive OfficerNULL1
273Brian WelckerVice President of Sales11/273
274Stephen JiangNorth American Sales Manager2731/273/274
275Michael BlytheSales Representative2741/273/274/275
276Linda MitchellSales Representative2741/273/274/276
285Syed AbbasPacific Sales Manager2731/273/285
286Lynn TsofliasSales Representative2851/273/285/286
287David BradleyMarketing Manager2731/273/287
288Mary GibsonMarketing Specialist2871/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.

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

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

    […] 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’aime

  2. Avatar de Les requêtes récursives (partie 2/3) « SQL Server dans le détail

    […] 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’aime

  3. Avatar de Pat

    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’aime

  4. Avatar de acksad02

    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’aime

    1. Avatar de acksad02

      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’aime

      1. Avatar de PGeiger

        Bonjour,

        Content que vous ayez trouver la réponse à votre problématique.
        Je vous souhaite une continuation.
        Bien à vous.

        PGeiger

        Aimé par 1 personne

  5. Avatar de Alain Touret

    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’aime

    1. Avatar de PGeiger

      Bonjour,

      Je suis d’accord avec votre remarque.
      Merci pour votre commentaire.
      Bien à vous,
      PGeiger

      J’aime

  6. Avatar de olivier

    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’aime

    1. Avatar de PGeiger

      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’aime

      1. Avatar de olivier

        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’aime

        1. Avatar de PGeiger

          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’aime

          1. Avatar de olivier

            Merci pour votre réponse rapide

            J’aime

  7. Avatar de zac

    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’aime

  8. Avatar de zac

    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’aime

  9. Avatar de zac

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

    J’aime

    1. Avatar de Philippe Geiger

      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’aime

  10. Avatar de zac

    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’aime

    1. Avatar de Philippe Geiger

      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’aime

      1. Avatar de zac

        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’aime

        1. Avatar de Philippe Geiger

          Bonjour,
          Bonne continuation.
          Bien à vous,
          PGeiger

          J’aime

Rechercher

A propos de l’auteur

Spécialiste certifié Microsoft BI (SQL Server et Azure), Philippe Geiger accompagne aussi bien les professionnels en infrastructure que les développeurs BI. Maîtrisant tous les aspects de la plateforme Data de Microsoft, il assure également, en sa qualité de formateur certifié, les formations officielles de Microsoft. Par ailleurs, il est Directeur des Activités Grand-Est chez Metsys, société « Pure Player » Microsoft.

Les derniers tweets

Certifications

Microsoft Certified: Power BI Data Analyst Associate
Microsoft Certified: Azure AI Engineer Associate
Microsoft Certified: Azure Fundamentals
Microsoft Certified: Azure Data Fundamentals
MCSE: Data Management and Analytics — Certified 2018
MCSA: SQL 2016 Database Administration - Certified 2016
MCSA: SQL Server 2012/2014 - Certified 2016
Microsoft Certified: Azure Data Engineer Associate
Microsoft Certified: Azure Database Administrator Associate
Microsoft Certified: Power Platform Fundamentals
Microsoft Certified Trainer 2022-2023
MCSE: Data Management and Analytics — Certified 2016
MCSA: SQL 2016 Database Development - Certified 2016
MTA: Database Fundamentals - Certified 2016
Microsoft Certified: Azure Data Scientist Associate
Microsoft 365 Certified: Fundamentals
Microsoft Certified: Azure AI Fundamentals
Exam 473: Designing and Implementing Cloud Data Platform Solutions
MCSA: SQL 2016 Business Intelligence Development - Certified 2016
MCSA: BI Reporting - Certified 2018

Archives