Trong các hệ thống thông tin hiện đại, việc xử lý dữ liệu phức tạp như mạng xã hội, cấu trúc tổ chức phân cấp, hay quan hệ đa chiều ngày càng trở nên quan trọng. Để mô hình hóa các loại dữ liệu này, chúng ta thường sử dụng cấu trúc cây (tree) và đồ thị (graph), vốn có nhiều tầng quan hệ và liên kết chặt chẽ, phản ánh chính xác cách dữ liệu được tổ chức trong thực tế.

Các hệ quản trị cơ sở dữ liệu cần “điều hướng” qua các cấu trúc này để truy xuất thông tin một cách hiệu quả. Đây là lúc truy vấn đệ quy (recursive queries) phát huy tác dụng, giúp xử lý và truy vấn dữ liệu phân cấp một cách nhanh chóng, tối ưu hóa hiệu suất và nâng cao khả năng phân tích dữ liệu trong các ứng dụng phức tạp.

Mục lục nội dung

Yêu cầu

Hướng dẫn thực hành này yêu cầu bạn đã có kinh nghiệm thực tế với PostgreSQL. Để thử các ví dụ, giả sử bạn đã cài đặt và chạy PostgreSQL trên một máy chủ độc lập hoặc dưới dạng một instance được quản lý.

Bạn cần hiểu cách hoạt động của Common Table Expressions (CTEs) trong PostgreSQL vì đệ quy dựa trên việc sử dụng CTE. Việc biểu diễn một đồ thị dưới dạng bảng dẫn đến thiết kế cơ sở dữ liệu chuẩn hóa. Do đó, việc hiểu cách hoạt động của các view (khung nhìn) để đơn giản hoá các truy vấn JOIN cũng rất hữu ích. Ngoài ra, bạn cần nắm vững các khái niệm cơ bản về khoa học máy tính như đệ quy và các cấu trúc dữ liệu như đồ thị và cây.

Một số chức năng cho các truy vấn đệ quy, chẳng hạn như từ khóa CYCLE, được giới thiệu từ PostgreSQL 14.0 (phát hành năm 2021). Các mẫu code trong hướng dẫn này được kiểm tra trên PostgreSQL 14.5 và dự kiến tương thích với các phiên bản PostgreSQL từ 14.0 trở lên.

Cơ sở lý thuyết

Phần này cung cấp cái nhìn tổng quan về một số khái niệm cơ bản của cấu trúc dữ liệu cây và đồ thị.

Cây và đồ thị đều bao gồm các nút (node) và các cạnh (edge). Một nút đại diện cho một thực thể cụ thể, như một người, địa điểm hay một thành phần. Một cạnh biểu thị mối quan hệ giữa hai nút, ví dụ như mối quan hệ giữa hai người. Các nút có thể được liên kết trực tiếp qua một cạnh đơn hoặc gián tiếp qua các nút và cạnh khác. Các nút được liên kết trực tiếp được gọi là các nút kề nhau (adjacent nodes) và thường được biểu diễn theo cặp, ví dụ (Node1, Node2). “Đi qua” (traverse) một đồ thị có nghĩa là thăm tất cả hoặc một số các nút liên quan từ một nút khởi đầu.

Trong đồ thị vô hướng, các cạnh không có hướng. Ví dụ, “A là bạn của B” về mặt lập trình là như nhau với “B là bạn của A”. Ngược lại, trong đồ thị có hướng, hướng của cạnh là quan trọng. Một cạnh từ A đến B không giống với một cạnh từ B đến A. Ví dụ, “A theo dõi B” không giống “B theo dõi A”. Trong đồ thị có hướng, cặp nút được sắp xếp: (A, B) khác biệt với (B, A). Khi có một cạnh có hướng từ A đến B, A được coi là tổ tiên (ancestor) và B là hậu duệ (descendant). Một nút lá (leaf node) là nút không có hậu duệ.

Một vòng lặp (cycle) trong đồ thị xảy ra khi tồn tại đường đi trực tiếp hoặc gián tiếp từ một nút quay lại chính nó. Ví dụ, trong đồ thị có hướng, một vòng lặp xuất hiện khi có đường đi từ một nút hậu duệ quay lại một nút tổ tiên. Hãy xem xét một đồ thị có hướng với các nút A, B và C. A là tổ tiên của B, B là tổ tiên của C. Một vòng lặp xuất hiện khi C được kết nối lại với A – nghĩa là C trở thành tổ tiên của A. Lưu ý rằng, một kết nối từ A đến C không tạo thành vòng lặp.

Cây là một dạng đặc biệt của đồ thị có hướng vô chu trình (directed acyclic graph – DAG). Cây có một nút “gốc” duy nhất và là cấu trúc dữ liệu phân cấp – hữu ích để biểu diễn những thứ như cấu trúc báo cáo của một tổ chức dưới dạng sơ đồ tổ chức (orgchart). Trong cây, mỗi tổ tiên có thể có nhiều hậu duệ, nhưng mỗi hậu duệ chỉ có một tổ tiên duy nhất. Độ sâu (depth) của một nút được xác định bởi số cạnh từ nút đó đến nút gốc.

Động lực

Hãy xem xét hai ví dụ:

Cho một sơ đồ tổ chức (orgchart) được biểu diễn dưới dạng cây, bạn muốn tìm tất cả những người nằm trong chuỗi báo cáo của một quản lý cụ thể. Để làm được điều này, bạn cần lấy tất cả các nút là hậu duệ trực tiếp hoặc gián tiếp của nút đó.
Với một mạng xã hội được biểu diễn dưới dạng đồ thị, bạn muốn tìm tất cả bạn bè và bạn của bạn bè của một người. Điều này được biểu diễn bởi tất cả các nút nằm trong phạm vi 2 bậc phân cách từ nút cho trước.

Để trích xuất thông tin dạng này bằng các truy vấn SQL thông thường, trước tiên bạn cần tìm tất cả các nút kề của nút cho trước, sau đó tìm các nút kề của các nút đó, và tiếp tục lặp đi lặp lại cho đến khi:

đạt đến các nút lá, hoặc
đi qua độ sâu mong muốn.

Với một đồ thị nhỏ, có thể (mặc dù rất tốn công) viết nhiều truy vấn con để thực hiện việc này một cách tuần tự. Tuy nhiên, trong thực tế, các đồ thị có kích thước lớn và liên kết phức tạp với nhiều lớp giữa nút gốc và nút lá. Trong nhiều trường hợp, độ sâu không được xác định trước. Do đó, phương pháp lặp bán thủ công như trên không khả thi. Các truy vấn đệ quy giải quyết triệt để vấn đề này.

Cách hoạt động của đệ quy trong PostgreSQL

Trong các ngôn ngữ lập trình thông thường, một hàm đệ quy sẽ tự gọi lại chính nó cho đến khi điều kiện dừng được thỏa mãn. Kết quả của mỗi lần lặp sẽ là đầu vào cho lần lặp tiếp theo. Giá trị ban đầu được đưa vào hàm, gọi là giá trị hạt giống (seed value).

Trong SQL, một truy vấn đệ quy bao gồm hai phần (hai truy vấn con). Phần truy vấn con đầu tiên là truy vấn không đệ quy, có kết quả tương tự như giá trị hạt giống. Phần truy vấn con thứ hai (đệ quy) sẽ gọi lại truy vấn chính. Trong mỗi lần lặp, nó kết hợp kết quả với các kết quả từ các lần lặp trước đó của truy vấn.

Nhờ cấu trúc này, CTE (Common Table Expression) trở nên lý tưởng để triển khai đệ quy. CTE được sử dụng để tổ chức các truy vấn phức tạp thành các truy vấn con, tạo thành các khối xây dựng logic của truy vấn chính.

Một CTE đệ quy được nhận diện bằng từ khóa RECURSIVE đứng trước tên của CTE.

Ràng buộc

Để đơn giản hóa các ví dụ SQL, hướng dẫn này chỉ xem xét các đồ thị có hướng trong toàn bộ bài. Các ví dụ ban đầu chỉ giới hạn trong DAG (cây là một dạng con của DAG). Các ví dụ sau sẽ cho thấy các tính năng của CTE trong PostgreSQL khi xử lý đồ thị có chu trình (cyclic graphs).

Mô hình dữ liệu ví dụ

Để minh họa các khái niệm, hướng dẫn này sử dụng một mô hình dữ liệu chuẩn hóa bao gồm các nút (nodes) và cạnh (edges).

Bảng node có trường ID. Trường node_name là thuộc tính của nút.
Bảng edge lưu trữ ID của hai nút được kết nối trực tiếp với nhau.

Trong ứng dụng thực tế, bạn cũng có thể thêm các cột bổ sung mô tả thuộc tính của các nút và cạnh. Ví dụ, một cạnh biểu thị “là bạn của” có thể có thuộc tính “friends since”. Một cạnh giữa hai thành phố có thể chứa thông tin về khoảng cách và thời gian di chuyển giữa các thành phố.

Tạo các bảng

Tạo bảng node với 2 cột – node_id và node_name:

CREATE TABLE node (
    node_id INTEGER PRIMARY KEY,
    node_name VARCHAR NOT NULL
);

Tạo bảng edge với 2 cột – node1 và node2, cả hai đều là khóa ngoại tham chiếu đến bảng node:

CREATE TABLE edge (
    node1 INTEGER REFERENCES node (node_id),
    node2 INTEGER REFERENCES node (node_id),
    PRIMARY KEY (node1, node2)
);

Thêm dữ liệu thử nghiệm

Chèn dữ liệu thử nghiệm vào từng bảng. Tạo một số nút (biểu diễn cho con người):

INSERT INTO node (node_id, node_name) 
VALUES (1, 'Tom'), (2, 'Dick'), (3, 'Harry'), (4, 'Jane'), 
    (5, 'Susan'), (6, 'Mary'), (7, 'Sam'), (8, 'Sally'), (9, 'Jack') ;

Tạo các cạnh xác định các mối quan hệ giả định giữa các nút:

INSERT INTO edge (node1, node2) 
VALUES (1, 2), (1, 8), (2, 3), (2, 4), (4, 5), (4, 6), (4, 7), (8, 9) ;

Giải thích:

Tom là tổ tiên của Dick và Sally;
Dick là tổ tiên của Harry và Jane;
Jane là tổ tiên của Susan, Mary, và Sam;
Sally là tổ tiên của Jack.

Khuyến nghị: Vẽ sơ đồ quan hệ trên giấy sử dụng cả ID và tên để dễ hình dung cấu trúc.

Định nghĩa một View chi tiết

Sử dụng một CTE thông thường (không đệ quy) để định nghĩa một view nodes_n_edges chứa tên và ID của các cặp nút kề nhau:

CREATE VIEW nodes_n_edges AS
    WITH cte1 AS (
        SELECT n.node_id, n.node_name, e.node2
        FROM node n
        JOIN edge e 
        ON n.node_id = e.node1
    )
    SELECT 
        cte1.node_id AS node1_id, 
        cte1.node_name AS node1_name, 
        node.node_name AS node2_name,
        node.node_id AS node2_id
    FROM cte1 
    JOIN node 
    ON cte1.node2 = node.node_id;

View này được sử dụng ở các phần sau để truy vấn cấu trúc dữ liệu một cách thuận tiện mà không phải JOIN lặp đi lặp lại giữa các bảng node và edge.

SELECT * FROM nodes_n_edges;

Duyệt cây sử dụng CTE đệ quy

Tạo một CTE đệ quy

Giả sử bạn cần lấy tên của tất cả các người thuộc nhánh có nút gốc là Dick – tương tự như duyệt sơ đồ tổ chức để tìm tất cả những người trong chuỗi báo cáo của Dick.

Sử dụng từ khóa RECURSIVE để tạo một CTE đệ quy có tên rcte:

-- incomplete code - do not copy this directly
WITH RECURSIVE rcte AS (

2. Viết truy vấn con không đệ quy để tạo giá trị hạt giống (seed). Đây là các nút kề của Dick (những người trực tiếp báo cáo cho Dick):

 -- incomplete code - do not copy this directly
 SELECT node1_id, node1_name, node2_name, node2_id
 FROM nodes_n_edges
 WHERE node1_name = 'Dick'

3. Viết truy vấn con đệ quy để JOIN kết quả từ rcte với view nodes_n_edges:

 -- incomplete code - do not copy this directly
 SELECT ne.node1_id, ne.node1_name, ne.node2_name, ne.node2_id
 FROM rcte
 JOIN nodes_n_edges ne
 ON rcte.node2_id = ne.node1_id

4. Gom lại bằng UNION trong một CTE đệ quy:

WITH recursive rcte as (
    SELECT node1_id, node1_name, node2_name, node2_id
    FROM nodes_n_edges
    WHERE node1_name = 'Dick'

    UNION 

    SELECT ne.node1_id, ne.node1_name, ne.node2_name, ne.node2_id
    FROM rcte
    JOIN nodes_n_edges ne
    ON rcte.node2_id = ne.node1_id
)
SELECT node1_name, node2_name 
FROM rcte ;

Kết quả của CTE trên sẽ liệt kê các cặp nút thuộc cây con có gốc là Dick.

Hiển Thị Đường Đi Duyệt

Để hiển thị đường đi kết nối giữa hai nút không liên kết trực tiếp, bạn có thể lưu trữ chuỗi đường đi khi duyệt qua từng nút. Bắt đầu với truy vấn đệ quy ở phần trước, khởi tạo một mảng trong truy vấn con không đệ quy. Mỗi lần lặp, truy vấn đệ quy sẽ thêm phần tiếp theo của đường đi vào mảng đó.

WITH RECURSIVE rcte AS (
    SELECT node1_id, node1_name, node2_name, node2_id,
    -- initialize the array
    ARRAY [node1_name, (select('-')), node2_name] AS traversal_path
    FROM nodes_n_edges
    WHERE node1_name = 'Dick'

    UNION 

    SELECT ne.node1_id, ne.node1_name, ne.node2_name, ne.node2_id,
    -- append the path to the array
    rcte.traversal_path||(select(' ; '))||ne.node1_name||(select('-'))||ne.node2_name
    FROM rcte
    JOIN nodes_n_edges ne
    ON rcte.node2_id = ne.node1_id
)
SELECT node1_name, node2_name,
    -- select and prettify the text of the path
    REPLACE(REPLACE(traversal_path::text, '"', ''), ',','') AS traversal_path
FROM rcte ;

Tính toán (và giới Hạn) Độ Sâu Duyệt

Việc gán một độ sâu cho mỗi mối quan hệ giúp bạn hiểu độ sâu của đồ thị con và giới hạn truy vấn đến một độ sâu cụ thể. Ví dụ, bạn có thể tìm các nút cách một nút cho trước N bậc phân cách, tương tự như tìm bạn bè và bạn của bạn bè trong mạng xã hội.

Để theo dõi độ sâu tìm kiếm, bắt đầu với truy vấn từ phần trước. Khởi tạo biến độ sâu bằng 1 trong truy vấn không đệ quy, và truy vấn đệ quy sẽ tăng biến này lên trong mỗi lần lặp.

Khởi tạo truy vấn không đệ quy bắt đầu từ nút Tom để duyệt toàn bộ đồ thị (cây). Tạo một view cho truy vấn duyệt đồ thị này. View này cũng sẽ được sử dụng ở các phần sau.

CREATE VIEW graph_structure AS
    WITH RECURSIVE rcte AS (
        SELECT node1_id, node1_name, node2_name, node2_id,
        -- initialize a depth variable
        1 AS depth,
        ARRAY [node1_name, (select('-')), node2_name] AS traversal_path
        FROM nodes_n_edges
        WHERE node1_name = 'Tom'

        UNION 

        SELECT ne.node1_id, ne.node1_name, ne.node2_name, ne.node2_id,
        -- increment the depth variable
        rcte.depth + 1,
        rcte.traversal_path||(select(' ; '))||ne.node1_name||(select('-'))||ne.node2_name
        FROM rcte, nodes_n_edges ne
        WHERE rcte.node2_id = ne.node1_id
    )
    SELECT node1_name, node2_name,
        REPLACE(REPLACE(traversal_path::text, '"', ''), ',','') AS traversal_path,
        depth
    FROM rcte ;

Kiểm tra đường đi duyệt và độ sâu:

SELECT * FROM graph_structure ;

Để giới hạn độ sâu duyệt, thêm mệnh đề WHERE cho biến độ sâu:

WITH RECURSIVE rcte AS (
    SELECT node1_id, node1_name, node2_name, node2_id,
    1 AS depth,
    ARRAY [node1_name, (select('-')), node2_name] AS traversal_path
    FROM nodes_n_edges
    WHERE node1_name = 'Tom'

    UNION 

    SELECT ne.node1_id, ne.node1_name, ne.node2_name, ne.node2_id,
    rcte.depth + 1,
    rcte.traversal_path||(select(' ; '))||ne.node1_name||(select('-'))||ne.node2_name
    FROM rcte, nodes_n_edges ne
    WHERE rcte.node2_id = ne.node1_id
)
SELECT node1_name, node2_name,
    REPLACE(REPLACE(traversal_path::text, '"', ''), ',','') AS traversal_path,
    depth
FROM rcte 
-- limit the traversal depth
WHERE depth < 3 ;

Duyệt đồ thị vô chu trình

Phần trước đã trình bày truy vấn đệ quy trên cây. Cây là một trường hợp đặc biệt của đồ thị vô chu trình (acyclic graphs). Trong cây, mỗi hậu duệ chỉ có một tổ tiên. Trong đồ thị, một hậu duệ có thể có nhiều tổ tiên.

Trong dữ liệu hiện có, Sam có một tổ tiên duy nhất – Jane. Hãy chuyển đổi mô hình dữ liệu ví dụ từ cây sang đồ thị bằng cách thêm một cạnh từ Tom đến Sam. Như vậy, Sam sẽ có hai tổ tiên – Jane và Tom.

WITH tom AS (
    SELECT node_id 
    FROM node
    WHERE node_name = 'Tom'
)
,sam AS (
    SELECT node_id 
    FROM node
    WHERE node_name = 'Sam'
)
INSERT INTO edge (node1, node2)
VALUES
    ((SELECT node_id FROM tom), (SELECT node_id FROM sam)) ;

Kiểm tra lại view graph_structure:

SELECT * FROM graph_structure ;

Cạnh từ Tom đến Sam giờ đã là một phần của cây.

Trúc trúc truy vấn cho cây sử dụng ở phần trước hoạt động tốt với đồ thị vô chu trình nhưng không áp dụng cho đồ thị có chu trình. Lưu ý thứ tự các nút được chèn – (Tom, Sam). Nếu thứ tự này bị đảo ngược, sẽ tạo ra một vòng lặp.

Duyệt đồ thị có chu trình

Trong mô hình dữ liệu cho đến nay, chưa có vòng lặp. Hãy xét đường đi từ Tom đến Jane: Tom là tổ tiên của Dick và Dick là tổ tiên của Jane. Thêm một vòng lặp vào dữ liệu bằng cách nối Jane quay lại với Tom:

WITH jane AS (
    SELECT node_id 
    FROM node
    WHERE node_name = 'Jane'
)
,tom AS (
    SELECT node_id 
    FROM node
    WHERE node_name = 'Tom'
)
INSERT INTO edge (node1, node2)
VALUES
    ((SELECT node_id FROM jane), (SELECT node_id FROM tom)) ;

Kiểm tra lại đường đi duyệt sử dụng view graph_structure đã tạo:

SELECT * FROM graph_structure ;

Truy vấn này sẽ treo (hang) vì nó rơi vào vòng lặp vô hạn. Nếu bạn đang sử dụng terminal, hãy dừng thủ công bằng cách nhấn CTRL+C.

Vòng lặp vô hạn xảy ra vì mỗi khi tìm đến Jane, đường đi lại quay trở lại Tom, và chu trình này tiếp diễn mãi mãi.

Để tránh vòng lặp, hãy sử dụng mệnh đề CYCLE được giới thiệu trong PostgreSQL 14.0. Mệnh đề CYCLE được thêm vào cuối CTE trước phần SELECT, định nghĩa các cột được kiểm tra để nhận diện vòng lặp. Trong trường hợp này, vòng lặp được nhận diện dựa trên các cột node1 và node2 của bảng edge (được gọi là node1_id và node2_id trong view nodes_n_edges).

Bắt đầu từ truy vấn view graph_structure ở phần “Calculate (and Limit) Traversal Depth”, thêm từ khóa CYCLE sau các truy vấn con của CTE:

WITH RECURSIVE rcte AS (
    SELECT node1_id, node1_name, node2_name, node2_id,
    1 AS depth,
    ARRAY [node1_name, (SELECT('-')), node2_name] AS traversal_path
    FROM nodes_n_edges
    WHERE node1_name = 'Tom'

    UNION 

    SELECT ne.node1_id, ne.node1_name, ne.node2_name, ne.node2_id,
        rcte.depth + 1,
        rcte.traversal_path||(SELECT(' ; '))||ne.node1_name||(SELECT('-'))||ne.node2_name
    FROM rcte
    JOIN nodes_n_edges ne
    ON rcte.node2_id = ne.node1_id
)
-- cycle detection clause
CYCLE node1_id, node2_id SET is_cycle USING path
SELECT 
    node1_name, node2_name,
    REPLACE(REPLACE(traversal_path::text, '"', ''), ',','') AS traversal_path,
    depth
FROM rcte ;

Lưu ý rằng sau khi đường đi quay lại Tom từ Jane, truy vấn (lại) đi qua các nút liên kết với Tom nhưng dừng lại trước khi đến Jane lần thứ hai, do đó tránh được vòng lặp vô hạn.

Kết luận

Truy vấn đệ quy (recursive queries) là công cụ mạnh mẽ giúp bạn mô hình hóa, lưu trữ và phân tích cấu trúc dữ liệu đồ thị trên cơ sở dữ liệu quan hệ. Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách sử dụng truy vấn đệ quy cơ bản trong PostgreSQL, đặc biệt trong đồ thị có hướng (directed graph) – một mô hình dữ liệu quan trọng trong nhiều ứng dụng thực tế.

Các ứng dụng của đồ thị có hướng bao gồm mô hình hóa mạng xã hội (quan hệ “follower”), tính toán chi phí và khoảng cách di chuyển để tìm tuyến đường tối ưu giữa các thành phố, v.v. Để duyệt qua đồ thị, chúng ta có hai phương pháp chính: Duyệt theo chiều rộng (BFS – Breadth-First Search) và Duyệt theo chiều sâu (DFS – Depth-First Search).

Bắt đầu từ PostgreSQL 14.0, bạn có thể sử dụng từ khóa SEARCH trong truy vấn đệ quy với Common Table Expressions (recursive CTEs) để thực hiện duyệt đồ thị hiệu quả hơn. Ngoài ra, tài liệu chính thức của PostgreSQL cũng giải thích chi tiết cách truy vấn đệ quy hoạt động nội bộ, cách phát hiện và tránh vòng lặp mà không cần sử dụng từ khóa CYCLE, giúp tối ưu hóa hiệu suất truy vấn trên dữ liệu đồ thị phức tạp.

Tham khảo thêm: PostgreSQL: Queries with Recursive CTEs

Tài liệu, Hướng dẫn sử dụng Linux, LAMP, LEMP, Webserver...

Hướng dẫn sử dụng truy vấn đệ quy (WITH RECURSIVE) trong PostgreSQL