Bài 6: Graph Queries Bằng CTE Đệ Quy

CTE đệ quy ở Bài 5 duyệt 1 cây danh mục — mỗi nút có đúng 1 cha, không có chu trình, đảm bảo tự dừng. Đồ thị (graph) tổng quát hơn hẳn: 1 nút có thể có nhiều cạnh vào/ra, và quan trọng nhất — có thể có chu trình (A dẫn tới B, B dẫn tới A). Bài này dùng 1 mạng lưới chuyến bay thật để giải 3 bài toán đồ thị kinh điển hoàn toàn bằng SQL thuần: tất cả điểm đến có thể tới được (transitive closure), đường đi rẻ nhất, và phát hiện chu trình — cùng với 1 cạm bẫy có thể khiến CTE đệ quy chạy vô hạn nếu không cẩn thận.

1. Mô Hình Đồ Thị Trong Bảng Quan Hệ: Edge List

Cách biểu diễn đồ thị phổ biến nhất trong SQL là edge list (danh sách cạnh): 1 bảng nút (sân bay) và 1 bảng cạnh có hướng, có trọng số (chuyến bay, với giá vé là trọng số):

CREATE TABLE airports (
  airport_code TEXT PRIMARY KEY,
  airport_name TEXT NOT NULL,
  city TEXT NOT NULL
);
CREATE TABLE routes (
  route_id INTEGER PRIMARY KEY,
  origin_code TEXT,   -- cạnh CÓ HƯỚNG: từ origin_code
  dest_code TEXT,     -- tới dest_code
  airline TEXT,
  price REAL,         -- trọng số cạnh
  duration_min INTEGER
);

Bài học tạo bảng này ngay trong phiên làm việc (giống cách category_tree được tạo ở Bài 5) — mạng lưới gồm 9 sân bay, 21 chuyến bay 1 chiều giữa Việt Nam và khu vực (TP.HCM, Hà Nội, Đà Nẵng, Nha Trang, Phú Quốc, Hải Phòng, Bangkok, Singapore, Dubai). Khác biệt cốt lõi so với category_tree: nhiều cặp sân bay có cả 2 chiều (SGN↔HAN, SGN↔DAD...), tạo ra chu trình — bay SGN→DAD→HAN→SGN là quay lại đúng điểm xuất phát. Cây không bao giờ có chuyện này (con không bao giờ dẫn ngược về ông bà); đồ thị thì có, và điều đó thay đổi hoàn toàn cách viết CTE đệ quy an toàn.

2. Transitive Closure: Mọi Điểm Đến Có Thể Tới Được

Transitive closure trả lời: "từ sân bay X, có thể bay tới những sân bay nào — qua bất kỳ số chặng nào?" Đây là bài toán CTE đệ quy tự nhiên: bắt đầu từ các chuyến bay trực tiếp, rồi tiếp tục nối chuyến từ mọi điểm đã tới được.

WITH RECURSIVE reachable(start_code, current_code, path, hops) AS (
  -- Anchor: mọi chuyến bay trực tiếp từ CXR (Nha Trang)
  SELECT origin_code, dest_code, origin_code || '->' || dest_code, 1
  FROM routes WHERE origin_code = 'CXR'

  UNION ALL

  -- Recursive: nối tiếp chuyến bay từ nơi vừa "tới được"
  SELECT re.start_code, r.dest_code, re.path || '->' || r.dest_code, re.hops + 1
  FROM routes r
  INNER JOIN reachable re ON r.origin_code = re.current_code
  WHERE instr(re.path, r.dest_code) = 0  -- xem callout ngay bên dưới — dòng này BẮT BUỘC
)
SELECT current_code, MIN(hops) AS min_hops
FROM reachable
GROUP BY current_code
ORDER BY min_hops;

Kết quả: từ CXR có thể tới 8/8 sân bay còn lại — gần nhất (1 chặng) là SGN, DAD; xa nhất (3 chặng) là HPH (Hải Phòng, phải qua trung chuyển 2 lần). Thử đổi origin_code = 'CXR' thành 'DXB' (Dubai) — kết quả trả về 0 hàng, vì Dubai trong dataset này chỉ có chuyến bay đến (từ SGN), không có chuyến bay đi nào — 1 "nút chìm" (sink node) trong đồ thị có hướng. Đây là điểm khác biệt quan trọng của đồ thị có hướng: "X tới được Y" không có nghĩa "Y tới được X".

3. Tìm Đường Đi Rẻ Nhất (Cheapest Path)

Thêm cột tích luỹ chi phí vào đúng cấu trúc CTE ở mục 2, rồi sắp xếp theo chi phí là tìm được đường bay rẻ nhất — không cần thuật toán Dijkstra phức tạp, chỉ cần liệt kê mọi đường đi hợp lệ (không lặp lại điểm) trong 1 số chặng giới hạn, rồi ORDER BY:

WITH RECURSIVE route_search(current_code, path, total_price, hops) AS (
  SELECT dest_code, origin_code || ' -> ' || dest_code, price, 1
  FROM routes WHERE origin_code = 'SGN'

  UNION ALL

  SELECT r.dest_code, rs.path || ' -> ' || r.dest_code, rs.total_price + r.price, rs.hops + 1
  FROM routes r
  INNER JOIN route_search rs ON r.origin_code = rs.current_code
  WHERE instr(rs.path, r.dest_code) = 0
    AND rs.hops < 4  -- không ai chấp nhận bay 5+ chặng chỉ để tiết kiệm vài đô
)
SELECT path, total_price, hops
FROM route_search
WHERE current_code = 'SIN'
ORDER BY total_price
LIMIT 5;

Kết quả từ TP.HCM (SGN) tới Singapore (SIN):

Bay thẳng vừa rẻ nhất vừa ít chặng nhất ở đây — nhưng đây không phải quy luật chung: thử đổi đích đến trong sân chơi bên dưới, có những cặp sân bay mà đường nhiều chặng hơn lại rẻ hơn đường ít chặng (do giá vé từng chặng khác nhau theo hãng bay). Đây chính là lý do cần liệt kê và sắp xếp theo giá, thay vì mặc định "ít chặng nhất = rẻ nhất".

4. Phát Hiện Chu Trình (Cycle Detection)

Nghịch lý thú vị: mục 2 và 3 chặn việc quay lại điểm đã ghé qua để tránh vòng lặp vô hạn. Nhưng phát hiện chu trình lại cần điều ngược lại — cho phép quay về đúng điểm xuất phát (chỉ chặn quay lại các điểm khác điểm xuất phát), rồi kiểm tra khi nào current_code trùng lại start_code:

WITH RECURSIVE cycle_search(start_code, current_code, path, hops) AS (
  SELECT origin_code, dest_code, origin_code || '->' || dest_code, 1
  FROM routes

  UNION ALL

  SELECT cs.start_code, r.dest_code, cs.path || '->' || r.dest_code, cs.hops + 1
  FROM routes r
  INNER JOIN cycle_search cs ON r.origin_code = cs.current_code
  WHERE cs.hops < 6 AND cs.current_code != cs.start_code  -- CHỈ chặn quay lại các điểm khác start
)
SELECT DISTINCT start_code, path, hops
FROM cycle_search
WHERE current_code = start_code  -- đã quay đúng về điểm xuất phát = tìm thấy chu trình
ORDER BY hops
LIMIT 10;

Kết quả có cả chu trình 2 chặng (round-trip đơn giản như SGN->HAN->SGN) lẫn chu trình 3 chặng thật sự đi qua 3 sân bay khác nhau, ví dụ DAD->HAN->SGN->DAD (tổng giá 175). Lưu ý điều kiện chặn ở đây (cs.current_code != cs.start_code) khác hẳn mục 2/3 (instr(path, dest_code) = 0) — đây không phải sơ suất, mà là 2 bài toán cần 2 chiến lược chặn khác nhau: transitive closure/đường đi rẻ nhất muốn đường đi đơn giản (không lặp bất kỳ điểm nào), còn phát hiện chu trình cố tình cho phép quay lại đúng 1 điểm — chính điểm xuất phát.

Bảng So Sánh: Duyệt Cây (Bài 5) vs Duyệt Đồ Thị (Bài 6)

Sân chơi tương tác: SQL Workbench Với Mạng Chuyến Bay

Thử đổi sân bay xuất phát/đích đến trong các ví dụ, hoặc tự viết truy vấn transitive closure/tìm đường rẻ nhất cho cặp sân bay khác — toàn bộ 9 sân bay và 21 chuyến bay có sẵn ngay khi trang tải xong.

Đang tải...