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

Publicités

13 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

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 )

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 )

Photo Google+

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

Connexion à %s