Logo SQL Server

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] AS 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] AS e
INNER JOIN [DirectReports] AS 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] AS 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] AS e
INNER JOIN [DirectReports] AS 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] AS 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] AS e
INNER JOIN [DirectReports] AS 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

21 réflexions sur “Les requêtes récursives (partie 3/3)

  1. 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

  2. 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

  3. 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. 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. 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

  4. 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

  5. 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

    1. 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

  6. 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. 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. 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

N'hésitez pas à laisser un commentaire. Vous contribuerez à l'amélioration de ce blog :

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s