Database
 sql >> Base de données >  >> RDS >> Database

Principes de base des expressions de table, Partie 6 - CTE récursifs

Cet article est la sixième partie d'une série sur les expressions de table. Le mois dernier, dans la partie 5, j'ai couvert le traitement logique des CTE non récursifs. Ce mois-ci, je couvre le traitement logique des CTE récursifs. Je décris la prise en charge par T-SQL des CTE récursifs, ainsi que des éléments standard qui ne sont pas encore pris en charge par T-SQL. Je fournis des solutions de contournement T-SQL logiquement équivalentes pour les éléments non pris en charge.

Exemples de données

Pour les exemples de données, j'utiliserai une table appelée Employés, qui contient une hiérarchie d'employés. La colonne empid représente l'ID d'employé du subordonné (le nœud enfant) et la colonne mgrid représente l'ID d'employé du responsable (le nœud parent). Utilisez le code suivant pour créer et remplir la table Employees dans la base de données tempdb :

SET NOCOUNT ON ; USE tempdb;DROP TABLE IF EXISTS dbo.Employees;GO CREATE TABLE dbo.Employees( empid INT NOT NULL CONSTRAINT PK_Employees PRIMARY KEY, mgrid INT NULL CONSTRAINT FK_Employees_Employees REFERENCES dbo.Employees, empname VARCHAR(25) NOT NULL, salaire MONEY NOT NULL, CHECK (empid <> mgrid) ); INSERT INTO dbo.Employees(empid, mgrid, empname, employee) VALUES(1, NULL, 'David' , $10000.00), (2, 1, 'Eitan' , $7000.00), (3, 1, 'Ina' , $7500.00) , (4, 2, 'Seraph' , 5000.00$), (5, 2, 'Jiru' , 5500.00$), (6, 2, 'Steve' , 4500.00$), (7, 3, 'Aaron' , 5000.00$), ( 8, 5, 'Lilach' , $3500.00), (9, 7, 'Rita' , $3000.00), (10, 5, 'Sean' , $3000.00), (11, 7, 'Gabriel', $3000.00), (12, 9, 'Emilia' , 2000.00$), (13, 9, 'Michael', 2000.00$), (14, 9, 'Didi' , 1500.00$); CRÉER UN INDEX UNIQUE idx_unc_mgrid_empid ON dbo.Employees(mgrid, empid) INCLUDE(empname, salaire);

Observez que la racine de la hiérarchie des employés - le PDG - a un NULL dans la colonne mgrid. Tous les autres employés ont un responsable, donc leur colonne mgrid est définie sur l'ID d'employé de leur responsable.

La figure 1 présente une représentation graphique de la hiérarchie des employés, indiquant le nom de l'employé, son ID et son emplacement dans la hiérarchie.

Figure 1 :Hiérarchie des employés

CTE récursifs

Les CTE récursifs ont de nombreux cas d'utilisation. Une catégorie classique d'utilisations concerne la gestion des structures de graphes, comme notre hiérarchie d'employés. Les tâches impliquant des graphes nécessitent souvent de parcourir des chemins de longueur arbitraire. Par exemple, étant donné l'ID d'employé d'un responsable, renvoyez l'employé d'entrée, ainsi que tous les subordonnés de l'employé d'entrée à tous les niveaux ; c'est-à-dire des subordonnés directs et indirects. Si vous aviez une petite limite connue sur le nombre de niveaux que vous pourriez avoir besoin de suivre (le degré du graphique), vous pourriez utiliser une requête avec une jointure par niveau de subordonnés. Cependant, si le degré du graphe est potentiellement élevé, à un moment donné, il devient impossible d'écrire une requête avec de nombreuses jointures. Une autre option consiste à utiliser du code itératif impératif, mais ces solutions ont tendance à être longues. C'est là que les CTE récursifs brillent vraiment :ils vous permettent d'utiliser des solutions déclaratives, concises et intuitives.

Je vais commencer par les bases des CTE récursifs avant d'aborder les choses les plus intéressantes où je couvre les capacités de recherche et de cycle.

N'oubliez pas que la syntaxe d'une requête sur un CTE est la suivante :

WITH [ ( ) ]
AS
(

)
 ;

Ici, je montre un CTE défini à l'aide de la clause WITH, mais comme vous le savez, vous pouvez définir plusieurs CTE séparés par des virgules.

Dans les CTE réguliers et non récursifs, l'expression de la table interne est basée sur une requête qui n'est évaluée qu'une seule fois. Dans les CTE récursifs, l'expression de la table interne est généralement basée sur deux requêtes appelées membres , bien que vous puissiez en avoir plus de deux pour gérer certains besoins spécifiques. Les membres sont généralement séparés par un opérateur UNION ALL pour indiquer que leurs résultats sont unifiés.

Un membre peut être un membre d'ancrage — ce qui signifie qu'il n'est évalué qu'une seule fois ; ou il peut s'agir d'un membre récursif — ce qui signifie qu'il est évalué à plusieurs reprises, jusqu'à ce qu'il renvoie un jeu de résultats vide. Voici la syntaxe d'une requête sur un CTE récursif basé sur un membre d'ancrage et un membre récursif :

WITH [ ( ) ]
AS
(

UNION ALL

)
 ;

Ce qui rend un membre récursif, c'est d'avoir une référence au nom CTE. Cette référence représente le jeu de résultats de la dernière exécution. Lors de la première exécution du membre récursif, la référence au nom CTE représente le jeu de résultats du membre d'ancrage. Dans la Nième exécution, où N> 1, la référence au nom CTE représente l'ensemble de résultats de l'exécution (N – 1) du membre récursif. Comme mentionné, une fois que le membre récursif renvoie un ensemble vide, il n'est plus exécuté. Une référence au nom CTE dans la requête externe représente les ensembles de résultats unifiés de l'exécution unique du membre d'ancrage et de toutes les exécutions du membre récursif.

Le code suivant implémente la tâche susmentionnée consistant à renvoyer la sous-arborescence des employés pour un gestionnaire d'entrée donné, en transmettant l'ID d'employé 3 comme employé racine dans cet exemple :

DECLARER @root AS INT =3 ; WITH C AS( SELECT empid, mgrid, empname FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M .empid)SELECT empid, mgrid, empnameFROM C;

La requête d'ancrage est exécutée une seule fois, renvoyant la ligne pour l'employé racine d'entrée (employé 3 dans notre cas).

La requête récursive joint l'ensemble des employés du niveau précédent (représenté par la référence au nom CTE, alias M pour les responsables) avec leurs subordonnés directs de la table Employés, alias S pour les subordonnés. Le prédicat de jointure est S.mgrid =M.empid, ce qui signifie que la valeur mgrid du subordonné est égale à la valeur empid du gestionnaire. La requête récursive est exécutée quatre fois comme suit :

  1. Renvoyer les subordonnés de l'employé 3 ; sortie :employé 7
  2. Renvoyer les subordonnés de l'employé 7 ; sortie :employés 9 et 11
  3. Renvoyer les subordonnés des employés 9 et 11 ; sortie :12, 13 et 14
  4. Renvoyer les subordonnés des employés 12, 13 et 14 ; sortie :ensemble vide; la récursivité s'arrête

La référence au nom CTE dans la requête externe représente les résultats unifiés de l'exécution unique de la requête d'ancrage (employé 3) avec les résultats de toutes les exécutions de la requête récursive (employés 7, 9, 11, 12, 13 et 14). Ce code génère la sortie suivante :

empid mgrid empname------ ------ --------3 1 Ina7 3 Aaron9 7 Rita11 7 Gabriel12 9 Emilia13 9 Michael14 9 Didi

Un problème courant dans les solutions de programmation est le code incontrôlable comme les boucles infinies généralement causées par un bogue. Avec les CTE récursifs, un bogue pourrait conduire à une exécution de piste du membre récursif. Par exemple, supposons que dans notre solution pour renvoyer les subordonnés d'un employé d'entrée, vous ayez un bogue dans le prédicat de jointure du membre récursif. Au lieu d'utiliser ON S.mgrid =M.empid, vous avez utilisé ON S.mgrid =S.mgrid, comme ceci :

DECLARER @root AS INT =3 ; WITH C AS( SELECT empid, mgrid, empname FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =S .mgrid)SELECT empid, mgrid, empnameFROM C;

Étant donné qu'au moins un employé avec un ID de responsable non nul est présent dans la table, l'exécution du membre récursif continuera à renvoyer un résultat non vide. N'oubliez pas que la condition de terminaison implicite pour le membre récursif est lorsque son exécution renvoie un jeu de résultats vide. S'il renvoie un jeu de résultats non vide, SQL Server l'exécute à nouveau. Vous vous rendez compte que si SQL Server n'avait pas de mécanisme pour limiter les exécutions récursives, il continuerait à exécuter le membre récursif à plusieurs reprises pour toujours. Par mesure de sécurité, T-SQL prend en charge une option de requête MAXRECURSION qui limite le nombre maximal autorisé d'exécutions du membre récursif. Par défaut, cette limite est définie sur 100, mais vous pouvez la remplacer par n'importe quelle valeur SMALLINT non négative, 0 représentant aucune limite. Définir la limite de récursivité maximale sur une valeur positive N signifie que la N + 1 tentative d'exécution du membre récursif est abandonnée avec une erreur. Par exemple, exécuter le code bogué ci-dessus tel quel signifie que vous comptez sur la limite de récursivité maximale par défaut de 100, de sorte que l'exécution 101 du membre récursif échoue :

empid mgrid empname------ ------ --------3 1 Ina2 1 Eitan3 1 Ina...
Msg 530, Niveau 16, État 1, Ligne 121
L'instruction s'est terminée. La récursivité maximale 100 a été épuisée avant la fin de l'instruction.

Dites que dans votre organisation, il est prudent de supposer que la hiérarchie des employés ne dépassera pas 6 niveaux de gestion. Vous pouvez réduire la limite de récursivité maximale de 100 à un nombre beaucoup plus petit, comme 10 pour être du bon côté, comme ceci :

DECLARER @root AS INT =3 ; WITH C AS( SELECT empid, mgrid, empname FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =S .mgrid)SELECT empid, mgrid, empnameFROM COPTION (MAXRECURSION 10);

Désormais, s'il y a un bogue entraînant une exécution intempestive du membre récursif, il sera découvert lors de la 11 tentative d'exécution du membre récursif au lieu de la 101 exécution :

empid mgrid empname------ ------ --------3 1 Ina2 1 Eitan3 1 Ina...
Msg 530, Niveau 16, État 1, Ligne 149
L'instruction s'est terminée. La récursivité maximale 10 a été épuisée avant la fin de l'instruction.

Il est important de noter que la limite de récursivité maximale doit être utilisée principalement comme mesure de sécurité pour interrompre l'exécution du code emballement bogué. N'oubliez pas que lorsque la limite est dépassée, l'exécution du code est interrompue avec une erreur. Vous ne devez pas utiliser cette option pour limiter le nombre de niveaux à visiter à des fins de filtrage. Vous ne voulez pas qu'une erreur soit générée lorsqu'il n'y a pas de problème avec le code.

À des fins de filtrage, vous pouvez limiter le nombre de niveaux à visiter par programmation. Vous définissez une colonne appelée lvl qui suit le numéro de niveau de l'employé actuel par rapport à l'employé racine d'entrée. Dans la requête d'ancrage, vous définissez la colonne lvl sur la constante 0. Dans la requête récursive, vous la définissez sur la valeur lvl du responsable plus 1. Pour filtrer autant de niveaux sous la racine d'entrée que @maxlevel, ajoutez le prédicat M.lvl <@ maxlevel à la clause ON de la requête récursive. Par exemple, le code suivant renvoie l'employé 3 et deux niveaux de subordonnés de l'employé 3 :

DECLARE @root AS INT =3, @maxlevel AS INT =2 ; WITH C AS( SELECT empid, mgrid, empname, 0 AS lvl FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, M.lvl + 1 AS lvl FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid AND M.lvl <@maxlevel)SELECT empid, mgrid, empname, lvlFROM C;

Cette requête génère la sortie suivante :

empid mgrid empname lvl------ ------ -------- ----3 1 Ina 07 3 Aaron 19 7 Rita 211 7 Gabriel 2

Clauses standards SEARCH et CYCLE

La norme ISO/IEC SQL définit deux options très puissantes pour les CTE récursifs. L'une est une clause appelée SEARCH qui contrôle l'ordre de recherche récursif, et une autre est une clause appelée CYCLE qui identifie les cycles dans les chemins parcourus. Voici la syntaxe standard pour les deux clauses :

7.18

Fonction

Spécifiez la génération d'informations de tri et de détection de cycle dans le résultat des expressions de requête récursives.

Formater

::=
[ ]
AS

[ ]
::=
| |
::=
SEARCH SET
::=
DEPTH FIRST BY | BREADTH FIRST BY
::=
::=
CYCLE SET TO
DEFAULT USING
::= [ { }… ]
::=
::=
::=
::=
::=

Au moment de la rédaction de cet article, T-SQL ne prend pas en charge ces options, mais dans les liens suivants, vous pouvez trouver des demandes d'amélioration de fonctionnalités demandant leur inclusion dans T-SQL à l'avenir, et voter pour elles :

  • Ajouter la prise en charge de la clause ISO/IEC SQL SEARCH aux CTE récursifs dans T-SQL
  • Ajouter la prise en charge de la clause ISO/IEC SQL CYCLE aux CTE récursifs dans T-SQL

Dans les sections suivantes, je décrirai les deux options standard et fournirai également des solutions alternatives logiquement équivalentes qui sont actuellement disponibles dans T-SQL.

Clause RECHERCHE

La clause SEARCH standard définit l'ordre de recherche récursif comme BREADTH FIRST ou DEPTH FIRST par une ou plusieurs colonnes de classement spécifiées et crée une nouvelle colonne de séquence avec les positions ordinales des nœuds visités. Vous spécifiez BREADTH FIRST pour rechercher d'abord à travers chaque niveau (largeur) puis vers le bas des niveaux (profondeur). Vous spécifiez DEPTH FIRST pour rechercher d'abord vers le bas (profondeur) puis à travers (largeur).

Vous spécifiez la clause SEARCH juste avant la requête externe.

Je vais commencer par un exemple pour la largeur du premier ordre de recherche récursive. N'oubliez pas que cette fonctionnalité n'est pas disponible dans T-SQL, vous ne pourrez donc pas exécuter les exemples qui utilisent les clauses standard dans SQL Server ou Azure SQL Database. Le code suivant renvoie le sous-arbre de l'employé 1, en demandant un premier ordre de recherche en largeur par empid, en créant une colonne de séquence appelée seqbreadth avec les positions ordinales des nœuds visités :

DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M .empid) RECHERCHER LA LARGE D'ABORD PAR empid SET seqbreadth---------------------------------------- ---- SELECT empid, mgrid, empname, seqbreadthFROM CORDER BY seqbreadth;

Voici la sortie souhaitée de ce code :

empid mgrid empname seqbreadth------ ------ -------- -----------1 NULL David 12 1 Eitan 23 1 Ina 34 2 Seraph 45 2 Jiru 56 2 Steve 67 3 Aaron 78 5 Lilach 89 7 Rita 910 5 Sean 1011 7 Gabriel 1112 9 Emilia 1213 9 Michael 1314 9 Didi 14

Ne soyez pas confus par le fait que les valeurs seqbreadth semblent être identiques aux valeurs empid. C'est juste par hasard en raison de la façon dont j'ai attribué manuellement les valeurs empid dans les exemples de données que j'ai créés.

La figure 2 présente une représentation graphique de la hiérarchie des employés, avec une ligne en pointillé indiquant la largeur du premier ordre dans lequel les nœuds ont été recherchés. Les valeurs empid apparaissent juste en dessous des noms des employés et les valeurs seqbreadth attribuées apparaissent dans le coin inférieur gauche de chaque case.

Figure 2 :Étendue de la recherche en premier

Ce qui est intéressant à noter ici, c'est qu'au sein de chaque niveau, les nœuds sont recherchés en fonction de l'ordre de colonne spécifié (empid dans notre cas) indépendamment de l'association parent du nœud. Par exemple, notez qu'au quatrième niveau, Lilach est accessible en premier, Rita en second, Sean en troisième et Gabriel en dernier. C'est parce que parmi tous les employés du quatrième niveau, c'est leur ordre basé sur leurs valeurs empid. Ce n'est pas comme si Lilach et Sean étaient censés être fouillés consécutivement parce qu'ils sont des subordonnés directs du même manager, Jiru.

Il est assez simple de trouver une solution T-SQL qui fournit l'équivalent logique de l'option standard SAERCH DEPTH FIRST. Vous créez une colonne appelée lvl comme je l'ai montré plus tôt pour suivre le niveau du nœud par rapport à la racine (0 pour le premier niveau, 1 pour le second, etc.). Ensuite, vous calculez la colonne de séquence de résultats souhaitée dans la requête externe à l'aide d'une fonction ROW_NUMBER. En tant que fenêtre de commande, vous spécifiez d'abord lvl, puis la colonne de commande souhaitée (empid dans notre cas). Voici le code complet de la solution :

DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname, 0 AS lvl FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, M.lvl + 1 AS lvl FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid)SELECT empid, mgrid, empname, ROW_NUMBER() OVER(ORDER BY lvl, empid) AS seqbreadthFROM CORDER BY seqbreadth;

Examinons ensuite l'ordre de recherche DEPTH FIRST. Selon la norme, le code suivant devrait renvoyer le sous-arbre de l'employé 1, en demandant un premier ordre de recherche en profondeur par empid, en créant une colonne de séquence appelée seqdepth avec les positions ordinales des nœuds recherchés :

DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M .empid) PROFONDEUR DE RECHERCHE D'ABORD PAR empid SET seqdepth---------------------------------------- SELECT empid, mgrid, empname, seqdepthFROM CORDER BY seqdepth;

Voici la sortie souhaitée de ce code :

empid mgrid empname seqdepth------ ------ -------- ---------1 NULL David 12 1 Eitan 24 2 Seraph 35 2 Jiru 48 5 Lilach 510 5 Sean 66 2 Steve 73 1 Ina 87 3 Aaron 99 7 Rita 1012 9 Emilia 1113 9 Michael 1214 9 Didi 1311 7 Gabriel 14

En regardant la sortie de requête souhaitée, il est probablement difficile de comprendre pourquoi les valeurs de séquence ont été affectées telles qu'elles l'étaient. La figure 3 devrait vous aider. Il présente une représentation graphique de la hiérarchie des employés, avec une ligne pointillée reflétant le premier ordre de recherche en profondeur, avec les valeurs de séquence attribuées dans le coin inférieur gauche de chaque case.

Figure 3 :profondeur de recherche en premier

Trouver une solution T-SQL qui fournit l'équivalent logique de l'option standard SEARCH DEPTH FIRST est un peu délicat, mais faisable. Je vais décrire la solution en deux étapes.

À l'étape 1, pour chaque nœud, vous calculez un chemin de tri binaire constitué d'un segment par ancêtre du nœud, chaque segment reflétant la position de tri de l'ancêtre parmi ses frères et sœurs. Vous construisez ce chemin de la même manière que vous calculez la colonne lvl. Autrement dit, commencez par une chaîne binaire vide pour le nœud racine dans la requête d'ancrage. Ensuite, dans la requête récursive, vous concaténez le chemin du parent avec la position de tri du nœud parmi les frères après l'avoir converti en un segment binaire. Vous utilisez la fonction ROW_NUMBER pour calculer la position, partitionnée par le parent (mgrid dans notre cas) et ordonnée par la colonne de classement pertinente (empid dans notre cas). Vous convertissez le numéro de ligne en une valeur binaire d'une taille suffisante en fonction du nombre maximum d'enfants directs qu'un parent peut avoir dans votre graphique. BINARY(1) prend en charge jusqu'à 255 enfants par parent, BINARY(2) prend en charge 65 535, BINARY(3) :16 777 215, BINARY(4) :4 294 967 295. Dans un CTE récursif, les colonnes correspondantes dans les requêtes d'ancrage et récursives doivent être du même type et taille , assurez-vous donc de convertir le chemin de tri en une valeur binaire de la même taille dans les deux.

Voici le code implémentant l'étape 1 dans notre solution (en supposant que BINARY(1) est suffisant par segment, ce qui signifie que vous n'avez pas plus de 255 subordonnés directs par responsable) :

DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname, CAST(0x AS VARBINARY(900)) AS sortpath FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, CAST(M. sortpath + CAST(ROW_NUMBER() OVER(PARTITION BY S.mgrid ORDER BY S.empid) AS BINARY(1)) AS VARBINARY(900)) AS sortpath FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid)SELECT empid, mgrid, empname, sortpathFROM C;

Ce code génère la sortie suivante :

empid mgrid empname sortpath------ ------ -------- -----------1 NULL David 0x2 1 Eitan 0x013 1 Ina 0x027 3 Aaron 0x02019 7 Rita 0x02010111 7 Gabriel 0x02010212 9 Emilia 0x0201010113 9 Michael 0x0201010214 9 Didi 0x020101034 2 SERAP 

 Notez que j'ai utilisé une chaîne binaire vide comme chemin de tri pour le nœud racine du sous-arbre unique que nous interrogeons ici. Si le membre d'ancrage peut potentiellement renvoyer plusieurs racines de sous-arbre, commencez simplement par un segment basé sur un calcul ROW_NUMBER dans la requête d'ancrage, de la même manière que vous le calculez dans la requête récursive. Dans ce cas, votre chemin de tri sera plus long d'un segment.
 

 Ce qu'il reste à faire à l'étape 2, c'est de créer la colonne seqdepth du résultat souhaité en calculant les numéros de ligne classés par chemin de tri dans la requête externe, comme ceci
 
DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname, CAST(0x AS VARBINARY(900)) AS sortpath FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, CAST(M. sortpath + CAST(ROW_NUMBER() OVER(PARTITION BY S.mgrid ORDER BY S.empid) AS BINARY(1)) AS VARBINARY(900)) AS sortpath FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid)SELECT empid, mgrid, empname, ROW_NUMBER() OVER(ORDER BY sortpath) AS seqdepthFROM CORDER BY seqdepth;
 

 Cette solution est l'équivalent logique de l'utilisation de l'option standard SEARCH DEPTH FIRST présentée précédemment avec la sortie souhaitée.
 

 Une fois que vous avez une colonne de séquence reflétant la profondeur du premier ordre de recherche (seqdepth dans notre cas), avec juste un peu plus d'effort, vous pouvez générer une très belle représentation visuelle de la hiérarchie. Vous aurez également besoin de la colonne lvl susmentionnée. Vous commandez la requête externe par la colonne de séquence. Vous renvoyez un attribut que vous souhaitez utiliser pour représenter le nœud (par exemple, empname dans notre cas), préfixé par une chaîne (par exemple ' | ') répliqué lvl fois. Voici le code complet pour obtenir une telle représentation visuelle :
 
DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, empname, 0 AS lvl, CAST(0x AS VARBINARY(900)) AS sortpath FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.empname, M.lvl + 1 AS lvl, CAST(M.sortpath + CAST(ROW_NUMBER() OVER(PARTITION BY S.mgrid ORDER BY S.empid) AS BINARY(1)) AS VARBINARY(900)) AS sortpath FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid)SELECT empid, ROW_NUMBER() OVER(ORDER BY sortpath) AS seqdepth, REPLICATE(' | ', lvl) + empname AS empFROM CORDER BY seqdepth;
 

 Ce code génère la sortie suivante :
 
empid seqdepth emp------ --------- --------------------1 1 David2 2 | Eitan4 3 | | Séraphin5 4 | | Jiru8 5 | | | Lilaque10 6 | | | Sean6 7 | | Steve3 8 | Ina7 9 | | Aaron9 10 | | | Rita12 11 | | | | Émilie13 12 | | | | Michel14 13 | | | | Didi11 14 | | | Gabriel
 

 C'est plutôt cool !
 
Clause CYCLE
 

 Les structures de graphe peuvent avoir des cycles. Ces cycles peuvent être valides ou invalides. Un exemple de cycles valides est un graphique représentant les autoroutes et les routes reliant les villes et les villages. C'est ce qu'on appelle un graphe cyclique . A l'inverse, un graphe représentant une hiérarchie d'employés comme dans notre cas n'est pas censé avoir de cycles. C'est ce qu'on appelle un acyclique graphique. Cependant, supposons qu'en raison d'une mise à jour erronée, vous vous retrouviez avec un cycle involontairement. Par exemple, supposons que vous mettez à jour par erreur l'ID de responsable du PDG (employé 1) en employé 14 en exécutant le code suivant :
 
UPDATE Employés SET mgrid =14WHERE empid =1 ;
 

 Vous avez maintenant un cycle invalide dans la hiérarchie des employés.
 

 Que les cycles soient valides ou invalides, lorsque vous parcourez la structure du graphe, vous ne voulez certainement pas continuer à suivre un chemin cyclique à plusieurs reprises. Dans les deux cas, vous voulez arrêter de poursuivre un chemin une fois qu'une occurrence non première du même nœud est trouvée, et marquer un tel chemin comme cyclique.
 

 Alors, que se passe-t-il lorsque vous interrogez un graphique qui a des cycles à l'aide d'une requête récursive, sans mécanisme en place pour les détecter ? Cela dépend de la mise en œuvre. Dans SQL Server, à un moment donné, vous atteindrez la limite de récursivité maximale et votre requête sera abandonnée. Par exemple, en supposant que vous avez exécuté la mise à jour ci-dessus qui a introduit le cycle, essayez d'exécuter la requête récursive suivante pour identifier la sous-arborescence de l'employé 1 :
 
DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M .empid)SELECT empid, mgrid, empnameFROM C;
 

 Étant donné que ce code ne définit pas de limite de récursivité maximale explicite, la limite par défaut de 100 est supposée. SQL Server interrompt l'exécution de ce code avant la fin et génère une erreur :
 
empid mgrid empname------ ------ --------1 14 David2 1 Eitan3 1 Ina7 3 Aaron9 7 Rita11 7 Gabriel12 9 Emilia13 9 Michael14 9 Didi1 14 David2 1 Eitan3 1 Ina7 3 Aaron...
 Msg 530, Niveau 16, État 1, Ligne 432
L'instruction s'est terminée. La récursivité maximale 100 a été épuisée avant la fin de l'instruction. 

 Le standard SQL définit une clause appelée CYCLE pour les CTE récursifs, vous permettant de gérer les cycles dans votre graphe. Vous spécifiez cette clause juste avant la requête externe. Si une clause SEARCH est également présente, vous la spécifiez d'abord, puis la clause CYCLE. Voici la syntaxe de la clause CYCLE :
 CYCLE 
 SET  TO  DEFAULT 
 USING  

 La détection d'un cycle est basée sur la liste de colonnes de cycle spécifiée . Par exemple, dans notre hiérarchie d'employés, vous voudrez probablement utiliser la colonne empid à cette fin. Lorsque la même valeur empid apparaît pour la deuxième fois, un cycle est détecté et la requête ne poursuit pas un tel chemin plus loin. Vous spécifiez une nouvelle colonne de marque de cycle qui indiquera si un cycle a été trouvé ou non, et vos propres valeurs comme marque de cycle et marque non-cycle valeurs. Par exemple, ceux-ci peuvent être 1 et 0 ou "Oui" et "Non", ou toute autre valeur de votre choix. Dans la clause USING, vous spécifiez un nouveau nom de colonne de tableau qui contiendra le chemin des nœuds trouvés jusqu'à présent.
 

 Voici comment vous traiteriez une demande de subordonnés d'un employé racine d'entrée, avec la possibilité de détecter des cycles basés sur la colonne empid, en indiquant 1 dans la colonne de marque de cycle lorsqu'un cycle est détecté, et 0 sinon :
 
DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M .empid) CYCLE empid SET cycle TO 1 DEFAULT 0---------------------------------------- SELECT empid, mgrid, empnameFROM C;
 

 Voici la sortie souhaitée de ce code :
 
empid mgrid empname cycle------ ------ -------- ------1 14 David 02 1 Eitan 03 1 Ina 07 3 Aaron 09 7 Rita 011 7 Gabriel 012 9 Emilia 013 9 Michael 014 9 Didi 01 14 David 14 2 Seraph 05 2 Jiru 06 2 Steve 08 5 Lilach 010 5 Sean 0
 

 T-SQL ne prend actuellement pas en charge la clause CYCLE, mais il existe une solution de contournement qui fournit un équivalent logique. Il comporte trois étapes. Rappelez-vous que vous avez créé précédemment un chemin de tri binaire pour gérer l'ordre de recherche récursif. De la même manière, comme première étape de la solution, vous construisez un chemin d'ancêtres basé sur une chaîne de caractères composé des ID de nœud (ID d'employé dans notre cas) des ancêtres menant au nœud actuel, y compris le nœud actuel. Vous voulez des séparateurs entre les ID de nœud, dont un au début et un à la fin.
 

 Voici le code pour construire un tel chemin d'ancêtre :
 
DECLARER @root AS INT =1 ; WITH C AS( SELECT empid, mgrid, empname, CAST('.' + CAST(empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, CAST(M.ancpath + CAST(S.empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid)SELECT empid, mgrid, empname, ancpathFROM C;
 

 Ce code génère la sortie suivante, poursuivant toujours des chemins cycliques, et donc abandonnant avant la fin une fois la limite de récursivité maximale dépassée :
 
empid mgrid empname ancpath------ ------ -------- -------------------1 14 David . 1.2 1 Eitan .1.2.3 1 Ina .1.3.7 3 Aaron .1.3.7.9 7 Rita .1.3.7.9.11 7 Gabriel .1.3.7.11.12 9 Emilia .1.3.7.9.12.13 9 Michael .1.3.7.9. 13.14 9 Didi .1.3.7.9.14.1 14 David .1.3.7.9.14.1.2 1 Eitan .1.3.7.9.14.1.2.3 1 Ina .1.3.7.9.14.1.3.7 3 Aaron .1.3.7.9.14.1.3.7. ...
 Msg 530, Niveau 16, État 1, Ligne 492
L'instruction s'est terminée. La récursivité maximale 100 a été épuisée avant la fin de l'instruction. 

 Eyeballing the output, you can identify a cyclic path when the current node appears in the path for the nonfirst time, such as in the path '.1.3.7.9.14.1.' . 
 

 In the second step of the solution you produce the cycle mark column. In the anchor query you simply set it to 0 since clearly a cycle cannot be found in the first node. In the recursive member you use a CASE expression that checks with a LIKE-based predicate whether the current node ID already appears in the parent’s path, in which case it returns the value 1, or not, in which case it returns the value 0. 
 

 Here’s the code implementing Step 2:
 
DECLARE @root AS INT =1; WITH C AS( SELECT empid, mgrid, empname, CAST('.' + CAST(empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, 0 AS cycle FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, CAST(M.ancpath + CAST(S.empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, CASE WHEN M.ancpath LIKE '%.' + CAST(S.empid AS VARCHAR(4)) + '.%' THEN 1 ELSE 0 END AS cycle FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid)SELECT empid, mgrid, empname, ancpath, cycleFROM C;
 

 This code generates the following output, again, still pursuing cyclic paths and failing once the max recursion limit is reached:
 
empid mgrid empname ancpath cycle------ ------ -------- ------------------- ------1 14 David .1. 02 1 Eitan .1.2. 03 1 Ina .1.3. 07 3 Aaron .1.3.7. 09 7 Rita .1.3.7.9. 011 7 Gabriel .1.3.7.11. 012 9 Emilia .1.3.7.9.12. 013 9 Michael .1.3.7.9.13. 014 9 Didi .1.3.7.9.14. 01 14 David .1.3.7.9.14.1. 12 1 Eitan .1.3.7.9.14.1.2. 03 1 Ina .1.3.7.9.14.1.3. 17 3 Aaron .1.3.7.9.14.1.3.7. 1...
 Msg 530, Level 16, State 1, Line 532
The statement terminated. The maximum recursion 100 has been exhausted before statement completion. 

 The third and last step is to add a predicate to the ON clause of the recursive member that pursues a path only if a cycle was not detected in the parent’s path.
 

 Here’s the code implementing Step 3, which is also the complete solution:
 
DECLARE @root AS INT =1; WITH C AS( SELECT empid, mgrid, empname, CAST('.' + CAST(empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, 0 AS cycle FROM dbo.Employees WHERE empid =@root UNION ALL SELECT S.empid, S.mgrid, S.empname, CAST(M.ancpath + CAST(S.empid AS VARCHAR(4)) + '.' AS VARCHAR(900)) AS ancpath, CASE WHEN M.ancpath LIKE '%.' + CAST(S.empid AS VARCHAR(4)) + '.%' THEN 1 ELSE 0 END AS cycle FROM C AS M INNER JOIN dbo.Employees AS S ON S.mgrid =M.empid AND M.cycle =0)SELECT empid, mgrid, empname, cycleFROM C;
 

 This code runs to completion, and generates the following output:
 
empid mgrid empname cycle------ ------ -------- -----------1 14 David 02 1 Eitan 03 1 Ina 07 3 Aaron 09 7 Rita 011 7 Gabriel 012 9 Emilia 013 9 Michael 014 9 Didi 01 14 David 14 2 Seraph 05 2 Jiru 06 2 Steve 08 5 Lilach 010 5 Sean 0
 

 You identify the erroneous data easily here, and fix the problem by setting the manager ID of the CEO to NULL, like so:
 
UPDATE Employees SET mgrid =NULLWHERE empid =1;
 

 Run the recursive query and you will find that there are no cycles present.
 
Conclusion
 

 Recursive CTEs enable you to write concise declarative solutions for purposes such as traversing graph structures. A recursive CTE has at least one anchor member, which gets executed once, and at least one recursive member, which gets executed repeatedly until it returns an empty result set. Using a query option called MAXRECURSION you can control the maximum number of allowed executions of the recursive member as a safety measure. To limit the executions of the recursive member programmatically for filtering purposes you can maintain a column that tracks the level of the current node with respect to the root node.
 

 The SQL standard supports two very powerful options for recursive CTEs that are currently not available in T-SQL. One is a clause called SEARCH that controls the recursive search order, and another is a clause called CYCLE that detects cycles in the traversed paths. I provided logically equivalent solutions that are currently available in T-SQL. If you find that the unavailable standard features could be important future additions to T-SQL, make sure to vote for them here:
 
     
  • Add support for ISO/IEC SQL SEARCH clause to recursive CTEs in T-SQL 
  • Add support for ISO/IEC SQL CYCLE clause to recursive CTEs in T-SQL

 

 This article concludes the coverage of the logical aspects of CTEs. Next month I’ll turn my attention to physical/performance considerations of CTEs.