Cách xử lý data phân cấp nhiều cấp lồng nhau với closure tables

Trong quá trình làm việc, chúng ta sẽ thường xuyên gặp phải các kiểu dữ liệu dạng phân cấp, nhiều cấp lồng nhau. Ví dụ category đa cấp, menu đa cấp, bình luận nhiều cấp... Nếu chỉ có 2 cấp thì sẽ rất đơn giản, nhưng khi data có 3 cấp trở lên mọi việc sẽ trở lên phức tạp. Có một số cách tổ chức database để xử lý data loại này:

Bảng phân tích trên chỉ là tương đối, các bạn có thể đọc thêm để rõ hơn.
Trong bài này mình sẽ giới thiệu về phương pháp nhiều ưu điểm nhất, cách triển khai đơn giản và nên sử dụng đó là sử dụng Closure Tables. Phương pháp này thuận lợi cho cả việc insert và select data.

1. Closure Tables là gì?

Closure Tables sử dụng một bảng bổ sung để lưu trữ tất cả các mối quan hệ giữa các nút trong cây phân cấp, không chỉ lưu trữ cha trực tiếp mà còn lưu cả các tổ tiên, con cháu ở mọi cấp độ. Bảng này thường bao gồm các cột chính:

• ancestor: ID của cha (ở cấp cao hơn).
• descendant: ID của con (ở cấp thấp hơn).
• depth: Khoảng cách từ Ancestor đến Descendant.

Điều này giúp bạn có thể dễ dàng tìm kiếm tất cả tổ tiên hoặc con cháu của một nút bằng cách truy vấn bảng Closure.

2. Cấu trúc bảng

• Bảng chính:

CREATE TABLE nodes ( id INT PRIMARY KEY, name VARCHAR(255) NOT NULL
);

INSERT INTO nodes (id, name) VALUES
(1, 'Root'),
(2, 'Child A'),
(3, 'Child B'),
(4, 'Grandchild');

• Bảng Closure Table:

CREATE TABLE closure_table ( ancestor INT NOT NULL, descendant INT NOT NULL, depth INT NOT NULL, PRIMARY KEY (ancestor, descendant), FOREIGN KEY (ancestor) REFERENCES nodes(id), FOREIGN KEY (descendant) REFERENCES nodes(id)
);

• Thêm mối quan hệ vào closure_table
  Giả sử cây: Root -> Child A, Child B -> Grandchild (con của Child B).

-- Thêm mối quan hệ nút với chính nó (depth=0)
INSERT INTO closure_table (ancestor, descendant, depth) VALUES
(1, 1, 0),
(2, 2, 0),
(3, 3, 0),
(4, 4, 0); -- Thêm mối quan hệ phân cấp
INSERT INTO closure_table (ancestor, descendant, depth) VALUES
(1, 2, 1), -- Root -> Child A
(1, 3, 1), -- Root -> Child B
(3, 4, 1), -- Child B -> Grandchild
(1, 4, 2); -- Root -> Grandchild

3. Cách truy vấn data

• Lấy tất cả con cháu của Root (id=1):

SELECT n.id, n.name
FROM nodes n
JOIN closure_table ct ON n.id = ct.descendant
WHERE ct.ancestor = 1 AND ct.depth > 0;

• Lấy tổ tiên của Grandchild (id=4):

SELECT n.id, n.name
FROM nodes n
JOIN closure_table ct ON n.id = ct.ancestor
WHERE ct.descendant = 4 AND ct.depth > 0;

4. Thêm nút mới

• Bước 1: Thêm nút vào bảng nodes

INSERT INTO nodes (id, name) VALUES (5, 'Grandchild A');

• Bước 2: Thêm mối quan hệ vào closure_table

INSERT INTO closure_table (ancestor, descendant, depth) VALUES (5, 5, 0); -- Nút với chính nó
INSERT INTO closure_table (ancestor, descendant, depth)
SELECT ancestor, 5, depth + 1
FROM closure_table
WHERE descendant = 2
UNION
SELECT 2, 5, 1; -- Mối quan hệ trực tiếp cha-con

5. Xóa nút:

• Ví dụ: Xóa Grandchild A, id=5

DELETE FROM closure_table WHERE descendant = 5 OR ancestor = 5;
DELETE FROM nodes WHERE id = 5;

6. Sự quan trọng của depth:

6.1. Xác định mức phân cấp:

• Truy vấn lấy con trực tiếp (depth = 1) của Root (id=1):

SELECT n.id, n.name
FROM nodes n
JOIN closure_table ct ON n.id = ct.descendant
WHERE ct.ancestor = 1 AND ct.depth = 1;

• Kết quả: Chỉ trả về Child A (2), không bao gồm Grandchild A (3) (vì depth = 2). Nếu không có depth, không thể phân biệt con trực tiếp (Child A) với con gián tiếp (Grandchild A).

6.2. Sắp xếp hoặc giới hạn cấp độ:

• Lấy con cháu của Root nhưng chỉ đến cấp 2:

SELECT n.id, n.name, ct.depth
FROM nodes n
JOIN closure_table ct ON n.id = ct.descendant
WHERE ct.ancestor = 1 AND ct.depth <= 2
ORDER BY ct.depth;

• Kết quả: Child A (2, depth=1), Grandchild A (3, depth=2). depth giúp lọc hoặc sắp xếp theo mức độ sâu trong cây.

6.3. Tối ưu hóa truy vấn phức tạp:

• Tìm đường dẫn từ Root đến Grandchild A:

SELECT n.name, ct.depth
FROM nodes n
JOIN closure_table ct ON n.id = ct.descendant
WHERE ct.ancestor = 1 AND ct.descendant = 3;

• Kết quả: Xác định Grandchild A ở depth = 2, cho biết nó cách Root 2 cấp. Nếu không có depth, cần phải truy vấn đệ quy hoặc phức tạp hơn để tính khoảng cách.

7. Conclusion

Sử dụng phương pháp closure tables giúp cho việc xứ lý dữ liệu phân cấp rất dễ dàng và thuận tiện. Việc cập nhật 1 nút cũng không đòi hỏi phải cập nhật toàn bộ cây như các phương pháp khác.
Cảm ơn các bạn đã đọc bài viết! 😄

Nguồn tham khảo:

• https://www.slideshare.net/slideshow/models-for-hierarchical-data/4179181#69
• https://towardsdev.com/modelling-hirearchical-data-using-closure-tables-078cc40a1aa8
• https://medium.com/stackademic/mastering-hierarchies-simplifying-tree-structures-in-sql-and-beyond-part-1-the-closure-table-9db497b2572a