Lập kế hoạch du lịch với dữ liệu chuyến bay

Truy vấn phân cấp và đệ quy trong SQL Server

Jasmin Ludolf

Content Developer

Bảng thông tin sân bay

Bảng thông tin ví dụ của một sân bay

Cấu trúc bộ dữ liệu chuyến bay như thế nào?

Departure	Arrival	FlightNumber	Cost	Time
London	Paris	LH3827	90	2
Vienna	New York	MH2370	379	8
New York	Paris	LH9832	489	9
Vienna	Paris	SU2389	200	3
London	Chicago	OP1230	650	10
New York	Chicago	NL5460	150	2

Xây dựng lộ trình bay như thế nào?

Hình minh họa các lộ trình bay có thể trên toàn cầu

Dùng đệ quy để lấy mọi lộ trình bay
Một lộ trình xác định bởi sân bay đi và đến
Giới hạn số lần quá cảnh để có lộ trình thực tế

Xây dựng lộ trình bay - bước 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      |
| ...       | ...           | ...    |
+-----------+---------------+--------+

Xây dựng lộ trình bay - bước 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
)

Thêm route ở phần neo
Theo dõi route ở phần đệ quy
Giới hạn số điểm dừng

Xây dựng lộ trình bay - kết quả

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     |    
| ...       | ...          | ...                                       |
+-----------+--------------+-------------------------------------------+

Truy vấn các chuyến bay khả thi với giới hạn

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 '...' ;

Tìm tất cả sân bay đến có thể, khi:

Sân bay đi cố định
- New York
Số stops giới hạn ở n
Kết quả bị ràng buộc bởi một điều kiện
- giới hạn chi phí
- tuyến rẻ nhất đến một điểm đến

Hãy tìm các lộ trình bay khả thi!

Truy vấn phân cấp và đệ quy trong SQL Server