Les algorithmes de traversée de graphes ont traditionnellement été le domaine de langages d'application comme Python ou Java, utilisant des bibliothèques comme NetworkX ou JGraphT. Cependant, avec l'avènement des expressions de table commune récursives (CTE) dans la norme SQL:1999, SQL a acquis des capacités Turing-complètes pour des requêtes hiérarchiques et récursives. Cette évolution a transformé ANSI SQL d'un simple langage de récupération de données en une plateforme capable de résoudre des problèmes complexes de géométrie computationnelle et de théorie des graphes directement dans la couche de base de données, minimisant les mouvements de données et tirant parti de l'optimisation basée sur les ensembles.
Déterminer le chemin le plus court dans un graphique non pondéré nécessite de trouver le nombre minimum d'arêtes entre un nœud source et un nœud cible. Contrairement aux structures d'arbres, les graphes contiennent des cycles, ce qui nécessite la détection de cycles pour éviter la récursion infinie. Le défi réside dans l'implémentation de la logique de recherche en largeur (BFS) — typiquement procédurale et basée sur une file d'attente — dans un paradigme déclaratif, basé sur les ensembles, sans constructions de boucles explicites ou variables mutables, tout en respectant strictement la syntaxe ANSI SQL qui interdit les extensions propriétaires telles que CONNECT BY d'Oracle ou les options procédurales de SQL Server.
La solution utilise un CTE récursif pour simuler l'exploration niveau par niveau de BFS. Le membre d'ancrage initialise la recherche à partir du nœud source. Le membre récursif se joint à la table d'arêtes pour découvrir des nœuds adjacents, incrémentant un compteur de longueur de chemin. De manière cruciale, une chaîne de suivi de chemin visité est maintenue pour détecter les cycles et éviter de revisiter des nœuds. La récursion se termine lorsque la cible est atteinte ou qu'aucun nouveau nœud n'est découvert. La norme ANSI SQL prend en charge la détection explicite des cycles à l'aide de la clause CYCLE ou d'un suivi manuel dans le CTE.
WITH RECURSIVE path_finder ( current_node, path_length, visited_path ) AS ( -- Ancre : commencer par la source SELECT source_node, 0, CAST(source_node AS VARCHAR(1000)) FROM edges WHERE source_node = 'A' UNION ALL -- Récursif : explorer les voisins SELECT e.target_node, pf.path_length + 1, CAST(pf.visited_path || '->' || e.target_node AS VARCHAR(1000)) FROM path_finder pf JOIN edges e ON pf.current_node = e.source_node WHERE POSITION(e.target_node IN pf.visited_path) = 0 AND pf.path_length < 100 -- Limite de sécurité ) SELECT path_length, visited_path FROM path_finder WHERE current_node = 'Z' ORDER BY path_length FETCH FIRST 1 ROW ONLY;
Une entreprise de logistique gérait son système de navigation de robot d'entrepôt à travers une base de données relationnelle suivant les itinéraires permis entre les baies de stockage sous forme d'arêtes dirigées. L'équipe des opérations avait besoin d'une requête en temps réel pour déterminer l'itinéraire optimal (le plus court) pour les robots entre deux baies afin de minimiser la consommation de batterie. La contrainte était stricte : la solution devait s'exécuter sur leur cluster PostgreSQL existant en utilisant strictement ANSI SQL sans déployer de microservices externes ou de bases de données graphiques comme Neo4j, en raison des exigences de latence et des mandats de simplicité architecturale.
Solution 1 : BFS en couche d'application avec Python
L'équipe a envisagé d'exporter les données d'arêtes vers un service Python utilisant NetworkX pour calculer les chemins les plus courts. Bien que cela offre de riches bibliothèques algorithmiques et une implémentation simple, cela a entraîné une latence réseau significative entre la base de données et le serveur d'application. Cela a également violé le principe de la source unique de vérité en nécessitant une réplication des données et a créé un point de défaillance potentiel pendant les partitions réseau.
Solution 2 : Procédure stockée avec SQL procédural
Ils ont évalué la possibilité d'écrire une procédure stockée utilisant PL/pgSQL (le langage procédural de PostgreSQL) pour mettre en œuvre un BFS basé sur une file d'attente avec des variables mutables et des boucles. Cela a éliminé la latence réseau mais a sacrifié la portabilité et violé l'exigence de standard ANSI SQL, les enfermant dans une syntaxe spécifique à PostgreSQL. Cette approche nécessitait également une gestion complexe des exceptions pour les cas limites dans la traversée des graphes.
Solution 3 : CTE récursive pure ANSI SQL
L'approche choisie a utilisé un CTE récursif implémentant un BFS limité en niveaux avec suivi de chemin. Cela s'est exécuté entièrement au sein du moteur SQL, tirant parti de la capacité de l'optimiseur de requêtes à paralléliser les jointures. Cette approche garantissait une conformité stricte à ANSI pour la portabilité de la base de données, éliminait les surcoûts réseau et utilisait des optimisations de performance basées sur les ensembles.
L'équipe a sélectionné la solution 3 parce qu'elle répondait aux strictes contraintes architecturales d'opération au sein du cluster de base de données existant tout en maintenant l'indépendance vis-à-vis des fournisseurs. L'approche ANSI SQL a éliminé le besoin d'infrastructures supplémentaires et a permis d'obtenir des performances de requêtes sous-millisecondes sur des graphes avec plus de 10 000 arêtes. La solution a permis à la requête d'être intégrée directement dans les appels JDBC de l'API de dispatching des robots sans couches intermédiaires.
L'implémentation a réussi à calculer des chemins les plus courts pour plus de 500 demandes concurrentes de robots par seconde avec des temps de réponse moyens de moins de 5 ms. L'entreprise de logistique a ensuite migré sa base de données de PostgreSQL vers EnterpriseDB sans modifier la logique de la requête, validant les avantages de portabilité. La solution est devenue un modèle pour d'autres requêtes basées sur des graphes au sein de l'organisation, y compris la détection de dépendances circulaires dans les réseaux de chaîne d'approvisionnement.
Comment empêchez-vous la récursion infinie dans un graphe cyclique lorsque la version de la norme SQL ne prend pas en charge la clause CYCLE ?
Les candidats oublient souvent que les anciennes implémentations ANSI SQL peuvent manquer des clauses SEARCH et CYCLE. La solution implique une détection manuelle des cycles en maintenant une chaîne délimitée ou un tableau de nœuds visités au sein du CTE récursif. Avant d'ajouter un nouveau nœud, la requête doit vérifier que le nœud potentiel n'existe pas déjà dans la chaîne de chemin accumulée en utilisant des fonctions de chaîne comme POSITION. Cela nécessite une manipulation soigneuse des caractères délimiteurs pour éviter les faux positifs, comme le nœud '11' étant détecté dans '111' sans séparateurs appropriés. De plus, les candidats oublient souvent d'inclure un limiteur de profondeur comme mesure de protection contre la récursion incontrôlée dans des graphes profondément connectés.
Pourquoi l'approche CTE récursive pour le chemin le plus court peut-elle renvoyer des résultats sous-optimaux si elle est écrite comme une simple jointure récursive sans ordonnancement de niveau ?
De nombreux candidats implémentent l'étape récursive comme une simple jointure sans comprendre que les CTE récursifs ANSI SQL effectuent une recherche en profondeur (DFS) par défaut à moins que cela ne soit contraint autrement, et non une recherche en largeur (BFS). Dans les problèmes de chemin le plus court pour des graphes non pondérés, BFS garantit que la première solution trouvée est optimale, tandis que DFS peut trouver un chemin plus long en premier. Le détail critique négligé est que sans limiter la profondeur de récursion ou utiliser un compteur de niveau pour s'arrêter à la première correspondance, la requête pourrait explorer des chemins exponentiellement croissants inutilement.
Comment gérez-vous la dégradation des performances lorsque le même nœud est accessible via plusieurs chemins de longueur égale dans un CTE récursif ?
Les candidats oublient fréquemment le concept d'élimination des chemins redondants au sein de SQL. Sans traitement approprié, le CTE récursif génère des lignes distinctes pour chaque chemin possible vers des nœuds intermédiaires, provoquant une croissance exponentielle des ensembles de résultats. La solution exige l'utilisation d'une fonction fenêtre comme ROW_NUMBER() partitionnée par nœud ordonnée par longueur de chemin pour ne conserver que le chemin le plus court vers chaque nœud intermédiaire à chaque itération. Cette optimisation empêche l'ensemble de résultats intermédiaires de gonfler en jetant immédiatement les chemins plus longs vers des nœuds déjà visités plutôt qu'à l'étape de sélection finale.