การวางแผนเดินทางด้วยข้อมูลเที่ยวบิน

Hierarchical and Recursive Queries in SQL Server

Jasmin Ludolf

Content Developer

กระดานแสดงข้อมูลสนามบิน

ตัวอย่างกระดานแสดงข้อมูลสนามบิน

ชุดข้อมูลเที่ยวบินมีโครงสร้างอย่างไร?

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

สร้างเส้นทางเที่ยวบินอย่างไร?

ภาพแสดงเส้นทางเที่ยวบินที่เป็นไปได้ทั่วโลก

ใช้ recursion เพื่อหาเส้นทางเที่ยวบินที่เป็นไปได้ทั้งหมด
เส้นทางกำหนดโดยสนามบินต้นทางและสนามบินปลายทาง
จำกัดจำนวน layover เพื่อให้ได้เส้นทางที่สมจริง

สร้างเส้นทางเที่ยวบิน - ขั้นตอนที่ 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      |
| ...       | ...           | ...    |
+-----------+---------------+--------+

สร้างเส้นทางเที่ยวบิน - ขั้นตอนที่ 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
)

เพิ่ม route ใน anchor member
ติดตาม route ใน recursive member
จำกัดจำนวน stops

สร้างเส้นทางเที่ยวบิน - ผลลัพธ์

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

การคิวรีเที่ยวบินที่เป็นไปได้พร้อมเงื่อนไข

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

ค้นหาสนามบินปลายทางที่เป็นไปได้ทั้งหมด โดยที่:

สนามบินต้นทางกำหนดไว้แล้ว
- New York
จำกัดจำนวน stops ไว้ที่ n
จำกัดผลลัพธ์ด้วยเงื่อนไข
- จำกัดค่าใช้จ่าย
- เส้นทางถูกที่สุดไปยังปลายทาง

มาฝึกกันเถอะ!

Hierarchical and Recursive Queries in SQL Server