Récursion, récursion, récursion …

une référence récursive est dite RCTE (recursive common table expression).

Vous vous dites peut-être que ce SQL récursif est réservé aux informaticiens haut de gamme et est peu utile pour résoudre des problèmes de gestion. Eh bien, avant de parvenir à cette conclusion, analysez donc votre base de données. Beaucoup de tables de base de données contiennent des lignes qui ont une relation inhérente avec d’autres lignes de la même table, comme des liens hiérarchiques ou des correspondances de vols qui ont naturellement recours à des algorithmes récursifs.

Pour expliquer une RCTE, rien ne vaut les relations hiérarchiques qui constituent l’organigramme d’une entreprise. Le président veut connaîtreles noms de tous les employés qui travaillent sous l’autorité d’un cadre intermédiaire nommé Carfino. Cette liste de collaborateurs doit inclure non seulement les managers qui rendent des comptes à Carfino, mais également les gens qui travaillent pour eux. Si la requête ne portait que sur les subordonnés immédiats de Carfino, une simple requête SQL suffirait. Mais la demande du président oblige à naviguer au travers de tous les niveaux de management dans l’entreprise. On pourrait certes utiliser une approche manuelle itérative : une application lance une requête chargée de trouver les subordonnés immédiats puis stocke cette information avant d’entamer une nouvelle boucle pour trouver les employés qui travaillent pour les subordonnés directs de Carfino, et ainsi de suite. Plus élégamment, c’est l’occasion idéale d’utiliser  SQL récursif. En effet, une RCTE permet de naviguer simplement au travers de tous les niveaux de management, moyennant une seule requête SQL.

Pour un tel scénario, la RCTE comporte trois phases, différenciées dans la figure 10 par trois couleurs. A savoir

• initialiser la requête (en vert)

• naviguer récursivement jusqu’au niveau suivant (en violet)

• abandonner la récursion et revenir au résultat final (en rouge)  

Dans cet exemple de RCTE, la phase d’initialisation permet d’identifier tous les employés qui travaillent sous l’autorité directe de Carfino. Donc la première étape consiste à extraire l’ID employé de Carfino afin que la phase suivante puisse trouver tous les employés qui ont une valeur ID manager qui fait référence à l’ID employé de Carfino : SELECT 1, empid, name FROM emp WHERE name = ‘Carfino’

Une valeur constante de 1 est renvoyée sur cette instruction SELECT germe (seeding) pour montrer dans le rapport final le niveau hiérarchique ou l’échelon d’un employé dans la chaîne hiérarchique de Carfino. L’instruction d’initialisation ne sera exécutée qu’une fois par DB2 UDB et ne sera pas exécutée sur les exécutions récursives de l’expression de table emp_list. DB2 UDB exige que la ou les instructions d’initialisation soient codées au début de la RCTE.

L’instruction SELECT de couleur violette est la portion récursive de la RCTE parce qu’elle contient une référence récursive à l’expression de table emp_list sur la clause FROM : SELECT o.level + 1,Next_layer.empid, next_layer.name FROM emp as next_layer, emp_list o WHERE o.empid = next_layer.mgrid )

A son premier passage dans la phase récursive de la requête, l’instruction SELECT produira une liste des employés dont Carfino est le manager, parce que o.empid contiendra le numéro d’employé de Carfino et cette valeur est jointe et comparée à l’ID manager de tous les employés.

La colonne join sur l’instruction SELECT récursive a toujours besoin de se joindre à la valeur germe produite par l’instruction d’initialisation (c’est-à-dire, la colonne empid). C’est par cette condition join que la RCTE s’auto-alimente avec une liste des employés à analyser lors de la prochaine exécution récursive.

La prochaine exécution de cette instruction récursive produira une liste des employés dont les managers reportent directement à Carfino, et ainsi de suite. Les traversées récursives de la RCTE s’arrêtent dès que l’instruction rencontre des employés non cadres, dont les numéros d’employés n’apparaissent jamais dans la colonne mgrid.

Notez aussi que la colonne level(niveau) est incrémentée pour suivre la profondeur de récursion dans l’organisation, à chaque exécution. L’opération UNION ALL combine les résultats provenant des phases d’initialisation et de récursion.

On l’a vu, l’instruction SELECT d’initialisation n’est pas exécutée sur les exécutions récursives de la RCTE. Pour exécuter réellement la RCTE et produire des résultats, il faut que la dernière instruction SELECT (en rouge) démarre le traitement récursif de la hiérarchie de l’entreprise : SELECT level, name FROM emp_list Cette instruction SELECT fait référence à la CTE emp_list. Cette référence fait que l’instruction SELECT germe est exécutée en premier, puis le relais est transmis à la phase récursive, laquelle construit le jeu de résultats final (figure 11). Dans le jeu de résultats final, on observe que les employés ne sont pas listés sous leurs managers.

Par défaut,DB2 UDB recherche et traite toujours les données « en largeur d’abord ». Par conséquent, DB2 UDB traverse un niveau de l’organisation avant de passer au niveau suivant.

Il existe une recherche « en profondeur d’abord » avec la RCTE de DB2 UDB for iSeries dans la V5R4,parce qu’il est fréquent que des applications veuillent les données dans cet ordre. Dans une recherche en profondeur d’abord, DB2 UDB prend l’un des  subordonnés directs de Carfino et essaie d’abord de traiter tous les employés qui travaillent pour ce manager, avant de traiter un autre des subordonnés directs de Carfino. L’ordre de traitement est spécifié par la clause SEARCH en figure 12 et dans les résultats de la figure 13. La sortie de la figure 13 montre bien que le jeu de résultats est ordonné d’une manière qui reflète naturellement les relations présentes dans un organigramme.

La première chose intéressante dans cet exemple en profondeur d’abord est que la clause SEARCH a besoin d’utiliser la même colonne que celle qui est spécifiée sur la référence résultats de la figure 13. La sortie de la figure 13 montre bien que le jeu de résultats est ordonné d’une manière qui reflète naturellement les relations présentes dans un organigramme.

lignes sur cette requête SQL. Cette colonne de séquencement (SeqCol) spécifiée sur le SET est très importante parce que ce même nom de colonne doit aussi être spécifié sur la clause ORDER BY. En revanche, le nom de la colonne est sans importance et laissé à votre imagination.