Planifier des voyages avec des données de vol

Requêtes hiérarchiques et récursives dans SQL Server

Jasmin Ludolf

Content Developer

Tableau d'affichage d'un aéroport

Exemple de tableau d'affichage d'un aéroport

Comment est structuré un ensemble de données de vols ?

Départ	Arrivée	NuméroDeVol	Coût	Durée
Londres	Paris	LH3827	90	2
Vienne	New York	MH2370	379	8
New York	Paris	LH9832	489	9
Vienne	Paris	SU2389	200	3
Londres	Chicago	OP1230	650	10
New York	Chicago	NL5460	150	2

Comment construire une route de vol ?

Carte des routes aériennes possibles dans le monde

Utiliser la récursivité pour obtenir toutes les routes de vol
Une route est définie par l'aéroport de départ et l'aéroport de destination
Limiter le nombre d'escales pour des itinéraires réalistes

Construire une route de vol — étape 1

WITH flightRoute (Departure, Arrival, stops) AS(
  -- Anchor query
  SELECT f.Departure,f.Arrival, 0
      FROM flightPlan f
      WHERE Departure = 'Vienna'
  -- Recursive query
  UNION ALL
      SELECT p.Departure, f.Arrival, p.stops + 1
      FROM flightPlan f, flightRoute p
      WHERE p.Arrival = f.Departure AND 
        p.stops < 5 
)

SELECT Departure, Arrival, stops
    FROM flightRoute

+-----------+---------------+--------+
| Departure | Arrival       | stops  |
|-----------|---------------|--------|
| Vienna    | Paris         | 2      |
| Vienna    | San Francisco | 3      |
| Vienna    | Vienna        | 3      |
| Vienna    | Frankfurt     | 3      |
| ...       | ...           | ...    |
+-----------+---------------+--------+

Construire une route de vol — étape 2

WITH flightRoute (Departure, Arrival, stops, route) AS(
  SELECT f.Departure, f.Arrival, 0, 
  CAST(Departure + '->' + Arrival AS VARCHAR(MAX))
      FROM flightPlan f
      WHERE Departure = 'Vienna'

  UNION ALL
  SELECT p.Departure, f.Arrival, p.stops + 1, 
  p.totalCost + f.Cost, 
  CAST(p.route + '->' + f.Arrival AS VARCHAR(MAX))
      FROM flightPlan f, flightRoute p

      WHERE p.Arrival = f.Departure AND p.stops < 5
)

Introduire route dans le membre d'ancrage
Suivre les routes dans le membre récursif
Limiter le nombre d'escales

Construire une route de vol — résultat

SELECT Departure, Arrival, Route
    FROM flightRoute

+-----------+--------------+-------------------------------------------+
| Departure | Arrival      | route                                     |
|-----------|--------------|-------------------------------------------+
| London    | New York     | London -> Vienna -> Chicago -> New York   |
| Vienna    | Chicago      | Vienna -> London -> Chicago               |        
| Paris     | Los Angeles  | Paris -> Toronto -> Los Angeles           |
| Chicago   | New York     | Chicago -> New York                       |
| Rome      | New York     | Rome -> London -> Chicago -> New York     |    
| ...       | ...          | ...                                       |
+-----------+--------------+-------------------------------------------+

Requêter des vols possibles avec des limites

WITH flightRoute (Departure, Arrival, stops, totalCost, route) AS(
  SELECT f.Departure, f.Arrival, 0, Cost,
    CAST(Departure + '->' + Arrival AS NVARCHAR(MAX))
      FROM flightPlan f
      WHERE Departure = 'New York'
  UNION ALL
  SELECT  p.Departure, f.Arrival, p.stops+1, 
  p.totalCost + f.Cost, p.route + '->' + f.Arrival
      FROM flightPlan f, flightRoute p
      WHERE p.Arrival = f.Departure AND p.stops < '...' 
)

SELECT '...'    
    FROM flightRoute
    WHERE '...' ;

Trouvez tous les aéroports de destination possibles où :

L'aéroport de départ est fixé
- New York
Le nombre d'stops est limité à n
La sortie est restreinte par une condition
- limite de coût
- itinéraire le moins cher vers une destination

Trouvons des routes de vol possibles !

Requêtes hiérarchiques et récursives dans SQL Server