CTE đệ quy: Cỗ máy duyệt đồ thị ẩn giấu trong SQL

Khi các lập trình viên gặp các bài toán đồ thị, chẳng hạn như làm việc với phân cấp, tìm đường đi giữa các thành phố, hoặc lập bản đồ kết nối mạng xã hội, phản ứng đầu tiên thường là tìm đến một công cụ chuyên dụng. Chúng ta thường nghĩ rằng cần một cơ sở dữ liệu đồ thị như Neo4j hoặc một thư viện Python như NetworkX để xử lý những thách thức này.

Đối với đồ thị khổng lồ hàng tỷ nút, những công cụ đó thực sự cần thiết. Nhưng đối với một phần đáng kể dữ liệu vận hành, ví dụ chuỗi cung ứng vài nghìn nút, sơ đồ tổ chức, hoặc đường dẫn điều hướng, việc đưa thêm một công cụ cơ sở dữ liệu mới có thể là giải pháp thừa thãi về kiến trúc.

Cơ sở dữ liệu quan hệ hiện tại của bạn có thể xử lý hầu hết các bài toán đồ thị một cách hiệu quả. Chìa khóa nằm ở một tính năng có trong chuẩn SQL từ năm 1999 nhưng vẫn chưa được sử dụng rộng rãi: Common Table Expressions (CTE) đệ quy.

Bài viết này hướng dẫn cách thực hiện duyệt đồ thị, tìm đường đi và phát hiện chu trình chỉ bằng SQL chuẩn.

Kiến thức cơ bản về CTE thông thường

Trước khi đi sâu vào CTE đệ quy, hãy xem lại một CTE thông thường (không đệ quy) hoạt động như thế nào.

Một Common Table Expression là một tập kết quả tạm thời được định nghĩa trong một câu lệnh SELECT, INSERT, UPDATE hoặc DELETE. Bạn có thể coi nó như một subquery có tên hoặc một view tạm thời chỉ tồn tại khi truy vấn chạy.

Lý do chính để dùng CTE là làm cho truy vấn dễ đọc hơn. Chúng giúp chia nhỏ logic phức tạp thành các bước rõ ràng, từng phần. Ví dụ, với bảng doanh số bán hàng:

WITH region_totals AS (
    -- Tính tổng doanh số mỗi khu vực
    SELECT region, SUM(amount) as total_sales
    FROM sales
    GROUP BY region
)
SELECT region, total_sales
FROM region_totals
WHERE total_sales > (SELECT AVG(total_sales) FROM region_totals);

Khối WITH region_totals AS (...) định nghĩa CTE. Truy vấn sau đó coi region_totals như một bảng thực. Khi truy vấn kết thúc, CTE biến mất. Một CTE đệ quy đưa khái niệm này đi xa hơn — thay vì chỉ truyền dữ liệu xuống truy vấn chính, nó có thể tham chiếu chính nó để tạo ra các hàng mới dựa trên các hàng trước đó.

Cấu trúc của một CTE đệ quy

Một CTE đệ quy hoạt động như một vòng lặp bên trong truy vấn. Không giống câu lệnh SELECT thông thường chạy một lần, CTE đệ quy tiếp tục chạy cho đến khi không còn dữ liệu. Nó xây dựng tập kết quả từng bước.

Mọi CTE đệ quy có cấu trúc cơ bản:

• Truy vấn khởi tạo (anchor): Bắt đầu tập kết quả.
• Truy vấn đệ quy: Nối với chính nó để thêm các hàng mới.
• Điểm dừng: Khi truy vấn đệ quy không còn trả về hàng nào.

Khi chạy, cơ sở dữ liệu thực hiện tìm kiếm theo chiều rộng (Breadth-First Search - BFS): chạy anchor, thêm kết quả vào bảng làm việc, sau đó dùng các kết quả đó cho bước đệ quy. Quá trình lặp lại cho đến khi bước đệ quy không trả về hàng mới.

WITH RECURSIVE graph_cte AS (
    -- 1. Truy vấn khởi tạo (Anchor)
    SELECT * FROM table WHERE id = 1

    UNION ALL

    -- 2. Truy vấn đệ quy nối với chính nó
    SELECT t.*
    FROM table t
    JOIN graph_cte g ON t.parent_id = g.id
    -- 3. Điểm dừng: đệ quy tự kết thúc khi JOIN không còn tìm thấy kết quả
)
SELECT * FROM graph_cte;

Ví dụ 1: Phân cấp tổ chức (Cây)

Bài toán đồ thị phổ biến nhất trong phần mềm doanh nghiệp là cấu trúc cây. Hệ thống tệp, chuỗi bình luận, sơ đồ tổ chức đều mô hình hóa các quan hệ phân cấp.

Giả sử có bảng employees với dữ liệu sơ đồ tổ chức công ty:

CREATE TABLE employees (
    id SERIAL PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INT REFERENCES employees(id),
    role TEXT
);

INSERT INTO employees (id, name, manager_id, role) VALUES
(1, 'Alice', NULL, 'CEO'),
(2, 'Bob', 1, 'VP Engineering'),
(3, 'Charlie', 1, 'VP Sales'),
(4, 'Dave', 2, 'Backend Lead'),
(5, 'Eve', 2, 'Frontend Lead'),
(6, 'Frank', 4, 'Junior Dev');

Bài toán: tạo báo cáo hiển thị mọi nhân viên, đường quản lý (ví dụ “Alice -> Bob -> Dave”) và cấp độ trong hệ thống phân cấp.

Giải pháp SQL:

WITH RECURSIVE org_chart AS (
    -- Anchor: Bắt đầu với sếp (cấp độ 1)
    SELECT
        id, name, manager_id, role,
        1 AS depth,
        name AS path
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- Đệ quy: Tìm nhân viên do lớp trước quản lý
    SELECT
        e.id, e.name, e.manager_id, e.role,
        oc.depth + 1 AS depth,
        oc.path || ' -> ' || e.name AS path
    FROM employees e
    JOIN org_chart oc ON e.manager_id = oc.id
    WHERE oc.depth < 10  -- Giới hạn an toàn
)
SELECT * FROM org_chart ORDER BY depth, id;

Kết quả:

id  name    manager_id  role            depth   path
--  ------- ----------  --------------  -----   --------------------------
1   Alice               CEO             1       Alice
2   Bob     1           VP Engineering  2       Alice -> Bob
3   Charlie 1           VP Sales        2       Alice -> Charlie
4   Dave    2           Backend Lead    3       Alice -> Bob -> Dave
5   Eve     2           Frontend Lead   3       Alice -> Bob -> Eve
6   Frank   4           Junior Dev      4       Alice -> Bob -> Dave -> Frank

Quá trình bắt đầu với anchor chọn Alice. Bước đệ quy nối kết quả hiện tại với bảng employees qua manager_id = id. Vòng đầu tìm Bob và Charlie; vòng sau tìm Dave, Eve, rồi Frank. Khi không còn nhân viên khớp, đệ quy dừng — tạo ra cái nhìn phẳng về phân cấp tổ chức mà không cần vòng lặp trong mã ứng dụng.

Ví dụ 2: Tìm đường đi trong mạng lưới (Đồ thị)

Cây chỉ đi một hướng từ trên xuống. Đồ thị phức tạp hơn vì có thể chứa chu trình và nhiều đường đi. Xét mạng lưới giao thông với trọng số là chi phí:

CREATE TABLE connections (
    origin TEXT,
    destination TEXT,
    cost INT
);

INSERT INTO connections VALUES
('New York', 'London', 500),
('New York', 'Paris', 600),
('London', 'Dubai', 400),
('Paris', 'Dubai', 350),
('Dubai', 'Tokyo', 500),
('Paris', 'Tokyo', 800);

Bài toán: tìm mọi tuyến đường từ New York đến Tokyo và tổng chi phí từng tuyến.

Giải pháp SQL:

WITH RECURSIVE travel_planner AS (
    -- Anchor: Chuyến bay khởi hành từ New York
    SELECT
        origin, destination,
        cost as total_cost,
        origin || ' > ' || destination as route,
        1 as hops
    FROM connections
    WHERE origin = 'New York'

    UNION ALL

    -- Đệ quy: Chuyến bay từ điểm đến trước đó
    SELECT
        c.origin, c.destination,
        tp.total_cost + c.cost,  -- Cộng dồn chi phí
        tp.route || ' > ' || c.destination,  -- Mở rộng tuyến đường
        tp.hops + 1
    FROM connections c
    JOIN travel_planner tp ON c.origin = tp.destination
)
SELECT route, total_cost, hops
FROM travel_planner
WHERE destination = 'Tokyo'
ORDER BY total_cost ASC;

Kết quả:

route                           total_cost  hops
------------------------------  ----------  ----
New York > Paris > Tokyo        1400        2
New York > London > Dubai > Tokyo  1400     3
New York > Paris > Dubai > Tokyo  1450      3

Truy vấn đệ quy khám phá đồ thị từng bước: đầu tiên là các nước láng giềng của New York, sau đó là láng giềng của họ, cho đến khi tìm thấy Tokyo. Cơ sở dữ liệu giữ trạng thái chi phí tích lũy và chuỗi đường đi — về cơ bản viết một thuật toán tìm đường chỉ bằng SQL.

Ví dụ 3: Phát hiện chu trình (Bẫy vòng lặp vô hạn)

Ví dụ trước giả định đồ thị có hướng và không chu trình (DAG). Nhưng đồ thị thực tế có thể có vòng lặp — nếu London kết nối với Dubai và Dubai kết nối ngược lại London, truy vấn có thể mắc kẹt trong vòng lặp vô hạn.

Thêm chu trình vào dữ liệu:

INSERT INTO connections VALUES ('Dubai', 'New York', 900);  -- Vòng lặp!

Nếu chạy truy vấn cũ, nó sẽ treo hoặc crash. Cần vá bằng phát hiện chu trình:

WITH RECURSIVE travel_safe AS (
    -- Anchor
    SELECT
        origin, destination,
        cost AS total_cost,
        origin || '->' || destination AS path_history,
        0 AS is_cycle,
        1 AS depth
    FROM connections
    WHERE origin = 'New York'

    UNION ALL

    -- Đệ quy có kiểm tra chu trình
    SELECT
        c.origin, c.destination,
        ts.total_cost + c.cost AS total_cost,
        ts.path_history || '->' || c.destination AS path_history,
        CASE
            WHEN instr(ts.path_history, c.destination) > 0 THEN 1
            ELSE 0
        END AS is_cycle,
        ts.depth + 1 AS depth
    FROM connections c
    JOIN travel_safe ts ON c.origin = ts.destination
    WHERE ts.is_cycle = 0  -- Không mở rộng đường đi có chu trình
      AND ts.depth < 10    -- Giới hạn độ sâu an toàn
)
SELECT route, total_cost, is_cycle, depth
FROM travel_safe
WHERE destination = 'Tokyo';

Truy vấn theo dõi lịch sử đường đi dưới dạng chuỗi văn bản. Trước khi mở rộng một tuyến, kiểm tra xem điểm đến tiếp theo đã có trong chuỗi chưa — nếu có, đánh dấu là chu trình và không mở rộng. Giới hạn độ sâu cứng đảm bảo đệ quy không chạy mãi ngay cả với dữ liệu bất thường.

Ví dụ 4: Sáu độ tách biệt (Đường đi ngắn nhất)

Trong mạng xã hội, khái niệm “sáu độ tách biệt” nói rằng mọi người đều kết nối với nhau qua tối đa sáu người trung gian. Bài toán: với hai người, tìm chuỗi bạn bè ngắn nhất nối họ.

Vì CTE đệ quy hoạt động theo chiều rộng, lần đầu tiên đệ quy tìm thấy người mục tiêu, đó chính là đường đi ngắn nhất trong đồ thị không trọng số.

Tạo dữ liệu mối quan hệ bạn bè:

CREATE TABLE friendships (
    user_name   TEXT NOT NULL,
    friend_name TEXT NOT NULL
);

-- Mối quan hệ bạn bè của Alice
INSERT INTO friendships VALUES
('Alice', 'Bob'), ('Bob', 'Alice'),
('Alice', 'Carol'), ('Carol', 'Alice'),
('Bob', 'Dan'), ('Dan', 'Bob'),
('Dan', 'Erin'), ('Erin', 'Dan'),
('Erin', 'Frank'), ('Frank', 'Erin'),
('Frank', 'Grace'), ('Grace', 'Frank'),
('Grace', 'Kevin'), ('Kevin', 'Grace'),
('Carol', 'Kevin'), ('Kevin', 'Carol');

Tìm số độ tách biệt giữa Kevin và mọi người khác:

WITH RECURSIVE paths(person, degree, path) AS (
    -- Anchor: Bắt đầu từ Kevin
    SELECT
        'Kevin' AS person,
        0 AS degree,
        '|Kevin|' AS path

    UNION ALL

    -- Đệ quy: Mở rộng một bước, tránh lặp lại nút đã đi qua
    SELECT
        f.friend_name AS person,
        p.degree + 1 AS degree,
        p.path || f.friend_name || '|' AS path
    FROM friendships f
    JOIN paths p ON f.user_name = p.person
    WHERE p.degree < 6  -- Giới hạn "sáu độ"
      AND instr(p.path, '|' || f.friend_name || '|') = 0
),
ranked AS (
    SELECT
        person, degree, path,
        ROW_NUMBER() OVER (PARTITION BY person ORDER BY degree) AS rn
    FROM paths
    WHERE person <> 'Kevin'
)
SELECT
    person,
    degree,
    replace(trim(path, '|'), '|', ' -> ') AS shortest_path
FROM ranked
WHERE rn = 1
ORDER BY degree, person;

Kết quả:

person  degree  shortest_path
------  ------  ---------------------------------------
Carol   1       Kevin -> Carol
Grace   1       Kevin -> Grace
Alice   2       Kevin -> Carol -> Alice
Frank   2       Kevin -> Grace -> Frank
Bob     3       Kevin -> Carol -> Alice -> Bob
Erin    3       Kevin -> Grace -> Frank -> Erin
Dan     4       Kevin -> Grace -> Frank -> Erin -> Dan
Helen   4       Kevin -> Carol -> Alice -> Bob -> Helen

Truy vấn mở rộng đường đi, theo dõi danh sách người đã ghé thăm trong mỗi đường để tránh vòng lặp. CTE thứ hai dùng hàm cửa sổ ROW_NUMBER() để chọn đường đi ngắn nhất cho mỗi người, loại bỏ các đường dài hơn.

Giới hạn và tối ưu hiệu suất

CTE đệ quy mạnh mẽ nhưng không phải sự thay thế hoàn chỉnh cho công cụ đồ thị chuyên dụng. Chúng hoạt động tốt trong phạm vi nhất định, nhưng hiệu suất giảm nhanh khi vượt giới hạn.

Chỉ mục là yếu tố then chốt. Trong đệ quy, cơ sở dữ liệu liên tục nối tập làm việc với bảng gốc. Nếu các cột nối không được lập chỉ mục, mỗi bước biến thành quét toàn bộ bảng. Luôn lập chỉ mục cho các cột dùng trong bước nối đệ quy.

Kích thước bảng làm việc. CTE đệ quy lưu kết quả trung gian. Trong đồ thị rộng — nơi một nút có hàng nghìn láng giềng — các tập này phình to nhanh và tràn ra đĩa, làm suy giảm hiệu suất. Vì vậy, không nên dùng cho đồ thị rộng, kết nối dày đặc.

Luôn thêm biện pháp an toàn. Dữ liệu thực tế thường lộn xộn và chu trình có thể xuất hiện không báo trước. Thêm giới hạn độ sâu vào mệnh đề WHERE đệ quy là phanh an toàn đáng tin cậy.

Tổng kết

SQL thường bị coi là ngôn ngữ cho báo cáo đơn giản và các thao tác CRUD. Nhưng nó thực sự là một ngôn ngữ lập trình logic khai báo. Bài viết này cho thấy SQL chuẩn, dùng CTE đệ quy, có thể giải quyết nhiều bài toán đồ thị thực tế mà không cần cơ sở dữ liệu đồ thị chuyên dụng.

Với các ví dụ thực tế như sơ đồ tổ chức, lập kế hoạch tuyến đường, duyệt an toàn có kiểm tra chu trình và tính độ tách biệt xã hội, chúng ta thấy cả cách CTE đệ quy hoạt động lẫn giới hạn của chúng.

Điểm chính: CTE đệ quy không thay thế được công cụ đồ thị lớn, nhưng là công cụ mạnh mẽ và ít được khai thác để xử lý đồ thị nhỏ và vừa trong cơ sở dữ liệu quan hệ hiện có — miễn là bạn biết giới hạn hiệu suất và dùng kiểm tra an toàn.

Bạn không phải lúc nào cũng cần cài đặt Neo4j hay viết script Python để duyệt cây hay tìm đường. Đôi khi, tất cả những gì cần là SQL và một cách tư duy mới.