7 - Second exemple : un réseau complexe (et des requêtes plus sexy !)

Peut être ne voyagez-vous pas assez souvent en France. En tout cas ce que je peux vous dire, c'est qu'à Paris il y a des jolies filles et à Toulouse un délicieux plat appelé cassoulet et un petit constructeur d'avion de nom francisé "bus de l'air"... Plus sérieusement, notre problème

consiste à nous rendre de paris à Toulouse en utilisant le réseau autoroutier :

— creation de la table :
CREATE TABLE T_JOURNEY
(JNY_FROM_TOWN VARCHAR(32),
JNY_TO_TOWN VARCHAR(32),
JNY_MILES INTEGER)

— population :
INSERT INTO T_JOURNEY VALUES (‘PARIS’, ‘NANTES’, 385)
INSERT INTO T_JOURNEY VALUES (‘PARIS’, ‘CLERMONT-FERRAND’, 420)
INSERT INTO T_JOURNEY VALUES (‘PARIS’, ‘LYON’, 470)
INSERT INTO T_JOURNEY VALUES (‘CLERMONT-FERRAND’, ‘MONTPELLIER’, 335)
INSERT INTO T_JOURNEY VALUES (‘CLERMONT-FERRAND’, ‘TOULOUSE’, 375)
INSERT INTO T_JOURNEY VALUES (‘LYON’, ‘MONTPELLIER’, 305)
INSERT INTO T_JOURNEY VALUES (‘LYON’, ‘MARSEILLE’, 320)
INSERT INTO T_JOURNEY VALUES (‘MONTPELLIER’, ‘TOULOUSE’, 240)
INSERT INTO T_JOURNEY VALUES (‘MARSEILLE’, ‘NICE’, 205)

Essayons maintenant une simple requête donnant tous les trajets entre deux villes :
WITH journey (TO_TOWN)
AS (SELECT DISTINCT JNY_FROM_TOWN
FROM T_JOURNEY
UNION ALL
SELECT JNY_TO_TOWN
FROM T_JOURNEY AS arrival
INNER JOIN journey AS departure
ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT * FROM journey

TO_TOWN
——————————–
CLERMONT-FERRAND
LYON
MARSEILLE
MONTPELLIER
PARIS
NANTES
CLERMONT-FERRAND
LYON
MONTPELLIER
MARSEILLE
NICE
TOULOUSE
MONTPELLIER
TOULOUSE
TOULOUSE
TOULOUSE
NICE
MONTPELLIER
MARSEILLE
NICE
TOULOUSE
MONTPELLIER
TOULOUSE
TOULOUSE

Constatez avec moi que ce n’est pas très intéressant car nous ne savons pas d’où nous venons. Seul la destination figure dans la réponse et il est probable que plusieurs trajets figurent pour un même voyage.. Pouvons nous avoir plus d’informations ?

Premièrement, considérons que nous devons partir de Paris :

WITH journey (TO_TOWN)
AS (SELECT DISTINCT JNY_FROM_TOWN
FROM T_JOURNEY WHERE JNY_FROM_TOWN = ‘PARIS’
UNION ALL
SELECT JNY_TO_TOWN FROM T_JOURNEY AS arrival
INNER JOIN journey AS departure ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT * FROM journey

TO_TOWN
——————————–
PARIS
NANTES
CLERMONT-FERRAND
LYON
MONTPELLIER
MARSEILLE
NICE
TOULOUSE
MONTPELLIER
TOULOUSE
TOULOUSE

Nous avons probablement trois trajets différents pour aller à Toulouse. Pouvons nous filtrer la destination ? Bien sûr :

WITH journey (TO_TOWN) AS
(SELECT DISTINCT JNY_FROM_TOWN
FROM T_JOURNEY WHERE JNY_FROM_TOWN = ‘PARIS’
UNION ALL SELECT JNY_TO_TOWN FROM T_JOURNEY
AS arrival INNER JOIN journey AS departure
ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT * FROM journey WHERE TO_TOWN = ‘TOULOUSE’

TO_TOWN
——————————–
TOULOUSE
TOULOUSE
TOULOUSE

Nous pouvons affiner cette requête afin qu’elle nous donne le nombre d’étapes des différents trajets, entre l’origine et la destination :

WITH journey (TO_TOWN, STEPS)
AS (SELECT DISTINCT JNY_FROM_TOWN, 0
FROM T_JOURNEY WHERE JNY_FROM_TOWN = ‘PARIS’
UNION ALL SELECT JNY_TO_TOWN, departure.STEPS + 1
FROM T_JOURNEY AS arrival
INNER JOIN journey AS departure ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT * FROM journey WHERE TO_TOWN = ‘TOULOUSE’

TO_TOWN                                         STEPS
——————————–                  ———–
TOULOUSE                                         3
TOULOUSE                                         2
TOULOUSE                                         3

La cerise sur le gâteau serait de connaître la distance des différents trajets. Cela s’exprime comme ceci :

WITH journey (TO_TOWN, STEPS, DISTANCE) AS
(SELECT DISTINCT JNY_FROM_TOWN, 0, 0
FROM T_JOURNEY WHERE JNY_FROM_TOWN = ‘PARIS’
UNION ALL SELECT JNY_TO_TOWN, departure.STEPS + 1 , departure.DISTANCE + arrival.JNY_MILES
FROM T_JOURNEY AS arrival
INNER JOIN journey AS departure ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT * FROM journey WHERE TO_TOWN = ‘TOULOUSE’

TO_TOWN                     STEPS                     DISTANCE
———————–         ———–                     ———–
TOULOUSE                     3                                 1015
TOULOUSE                     2                                 795
TOULOUSE                     3                                 995

La fille qui surgit du gâteau consisterait à afficher les différentes étapes intermédiaires de chaque trajet :

WITH journey (TO_TOWN, STEPS, DISTANCE, WAY)
AS (SELECT DISTINCT JNY_FROM_TOWN, 0, 0, CAST(‘PARIS’ AS VARCHAR(MAX))
FROM T_JOURNEY WHERE JNY_FROM_TOWN = ‘PARIS’
UNION ALL SELECT JNY_TO_TOWN, departure.STEPS + 1 , departure.DISTANCE + arrival.JNY_MILES , departure.WAY + ‘, ‘ + arrival.JNY_TO_TOWN FROM T_JOURNEY AS arrival
INNER JOIN journey AS departure ON departure.TO_TOWN = arrival.JNY_FROM_TOWN) SELECT * FROM journey WHERE TO_TOWN = ‘TOULOUSE’

TO_TOWN                 STEPS             DISTANCE             WAY
———-                         ——-                 ———                     ———————————————-
TOULOUSE     3     1015     PARIS, LYON, MONTPELLIER, TOULOUSE
TOULOUSE     2     795     PARIS, CLERMONT-FERRAND, TOULOUSE
TOULOUSE     3     995     PARIS, CLERMONT-FERRAND, MONTPELLIER, TOULOUSE

Et maintenant, mesdames et messieurs, la technique de la CTE alliée à la puissance de la récursivité SQL sont fiers de vous présenter la solution à un problème de grande complexité, le problème du voyageur de commerce, un des casses têtes de la recherche opérationnelle sur lequel le mathématicien Edsger Wybe Dijkstra trouva un algorithme et lui valu le prix Turing en 1972… :

WITH journey (TO_TOWN, STEPS, DISTANCE, WAY)
AS (SELECT DISTINCT JNY_FROM_TOWN, 0, 0, CAST(‘PARIS’ AS VARCHAR(MAX))
FROM T_JOURNEY WHERE JNY_FROM_TOWN = ‘PARIS’
UNION ALL SELECT JNY_TO_TOWN, departure.STEPS + 1, departure.DISTANCE + arrival.JNY_MILES, departure.WAY + ‘, ‘ + arrival.JNY_TO_TOWN FROM T_JOURNEY
AS arrival INNER JOIN journey AS departure
ON departure.TO_TOWN = arrival.JNY_FROM_TOWN)
SELECT TOP 1 * FROM journey WHERE TO_TOWN = ‘TOULOUSE’
ORDER BY DISTANCE

TO_TOWN STEPS DISTANCE WAY
———- ——- ——— ———————————————-
TOULOUSE 2 795 PARIS, CLERMONT-FERRAND, TOULOUSE

Au fait, TOP n ne fait pas partie de la norme SQL… haïssez- le et bénissez la CTE :

WITH journey (TO_TOWN, STEPS, DISTANCE, WAY) AS (SELECT DISTINCT JNY_FROM_TOWN, 0, 0, CAST(‘PARIS’ AS VARCHAR(MAX)) FROM T_JOURNEY WHERE JNY_FROM_TOWN = ‘PARIS’ UNION ALL SELECT JNY_TO_TOWN, departure.STEPS + 1, departure.DISTANCE + arrival.JNY_MILES, departure.WAY + ‘, ‘ + arrival.JNY_TO_TOWN FROM T_JOURNEY AS arrival INNER JOIN journey AS departure ON departure.TO_TOWN = arrival.JNY_FROM_TOWN), short (DISTANCE) AS (SELECT MIN(DISTANCE) FROM journey WHERE TO_TOWN = ‘TOULOUSE’) SELECT * FROM journey j INNER JOIN short s ON j.DISTANCE = s.DISTANCE WHERE TO_TOWN = ‘TOULOUSE’