Mô hình tập hợp lồng nhau trong cơ sở dữ liệu phân cấp

Mô hình tập hợp lồng nhau

Dữ liệu dạng phân cấp (hierarchical data structure) được sử dụng trong nhiều ứng dụng web như menu, chuyên mục phân cấp có quan hệ cha – con. Việc tổ chức lưu trữ cấu trúc đó trên một cơ sở dữ liệu (CSDL) cũng cần có sự tính toán, xem xét để sử dụng phương pháp nào là tốt nhất cho hệ thống.

Chúng ta cùng tham khảo một cấu trúc như hình bên dưới, cấu trúc này sẽ được sử dụng để làm ví dụ cho toàn bài viết:

Example Model

Theo cách tiếp cận thông thường trong việc thiết kế CSDL, ta sẽ cho mỗi 1 chuyên mục (node) sẽ có 1 thuộc tính là ParentId dùng để lưu trữ id của parent node của nó. Lúc này cấu trúc trong CSDL của chúng ta sẽ có dạng sau đây:

Categories
Id
Name
ParentID

Khi lưu trữ dữ liệu của ví dụ trên ta có:

Id Name ParentId
1 Tin tức null
2 Xã hội 1
3 Đời sống 2
4 Đô thị 2
5 Âm nhạc 1
6 Thời trang 1
7 Giải trí 1
8 Thể thao 1
9 Bóng đá Anh 8
10 Bóng đá TBN 8

Với cách này, ta có thể biết được một node có những node con nào (dưới 1 cấp) và ngược lại, một node sẽ thuộc một node cha (trên 1 cấp) nào đó.

Ưu điểm:

  • Cấu trúc dữ liệu đơn giản
  • Dễ dàng liệt kê tất cả node con (dưới 1 cấp)
  • Thêm, di chuyển một node mới dễ dàng

Nhược điểm:

  • Khó liệt kê được tất cả node cha (trên 1 cấp), node “ông nội” (trên 2 cấp), node “ông tổ”… của một node nào đó. Ở đây không đề cập dùng đệ quy để duyệt vì việc này sẽ tốn chi phí cho hệ thống.

Vì khuyết điểm trên, chúng ta cần tiếp cận với phương pháp khác đáp ứng được việc truy xuất nhanh chóng. Bài viết này xin giới thiệu phương pháp sử dụng kỹ thuật Nested set model.

Nested set model (Mô hình tập hợp lồng nhau)

Giới thiệu

Mô hình tập hợp lồng nhau là kỹ thuật dùng để thể hiện các tập hợp lồng nhau (nested set) trong CSDL. Xét cấu trúc chuyên mục đã nói ở trên khi sử dụng phương pháp tập hợp này sẽ có dạng như sau:

Nested set model

Chúng ta có thể dễ dàng hình dung được cấu trúc dữ liệu ban đầu được biểu diễn theo kiểu tập hợp như trên. Vậy trong CSDL, làm thể nào để biết được mục Đời sống là tập hợp con của Xã hội, cũng là tập hợp con của Tin tức? Chúng ta cũng đến với hình ảnh tiếp theo:

Nested set model with left and right

Lúc này mỗi tập hợp được quy định bởi 2 con số [Left, Right], dựa vào hình trên ta dễ dàng thấy rằng mục Đời sống [3, 4] là con của Xã hội [2, 7] vì tập hợp [3, 4] thuộc tập hợp [2, 7]. Tương tự Đời sống cũng thuộc Tin tức vì [3, 4] thuộc tập hợp [1, 20]. Mục Âm nhạc [8, 9] không thuộc mục Xã hội [2, 7] vì [8, 9] không thuộc [2, 7]. Từ đó, ta có thể thiết kế được cấu trúc bảng trong CSDL như sau:

Categories
Id
Name
Left
Right

Dữ liệu thực tế cho ví dụ trên sẽ là:

Id Name Left Right
1 Tin tức 1 20
2 Xã hội 2 7
3 Đời sống 3 4
4 Đô thị 5 6
5 Âm nhạc 8 9
6 Thời trang 10 11
7 Giải trí 12 13
8 Thể thao 14 19
9 Bóng đá Anh 15 16
10 Bóng đá TBN 17 18

Giả sử ta muốn liệt kê tất cả các node con của mục Xã hội [2, 7] thì SQL query của chúng ta có dạng như sau:

Lúc này ta thấy có mục Đời sống và Đô thị thỏa điều kiện, suy ra 2 mục này là con của mục Xã hội.

Giả sử muốn liệt kê tất cả các node con của mục Tin tức [1, 20], bao gồm luôn mục Tin tức thì SQL query chúng ta sẽ sửa lại:

Lúc này sẽ có 10 node thỏa điều kiện trên. Thế nhưng các node này (trừ Tin tức) sẽ chỉ biết nó có 1 mục cha duy nhất, đó là Tin tức. Trong khi, cha gần nhất của Bóng đá Anh là Thể thao, cha gần nhất của Đời sống là Xã hội. Vậy bước tiếp theo chúng ta cần là đánh dấu lại node cha gần nhất bằng cách thêm cột ParentId như cách tiếp cận ban đầu. Lúc này cấu trúc bảng dữ liệu chúng ta có:

Id Name Left Right ParentID
1 Tin tức 1 20 null
2 Xã hội 2 7 1
3 Đời sống 3 4 2
4 Đô thị 5 6 2
5 Âm nhạc 8 9 1
6 Thời trang 10 11 1
7 Giải trí 12 13 1
8 Thể thao 14 19 1
9 Bóng đá Anh 15 16 8
10 Bóng đá TBN 17 18 8

Lúc này chúng ta có thể thấy ưu điểm tuyệt vời khi sử dụng Nested set model để truy xuất dữ liệu rồi đúng không? Thế nhưng đây cũng chưa phải là kỹ thuật hoàn hảo tuyệt đối vì nó tốn chi phí trong việc chỉnh sửa dữ liệu như: thêm, xóa node. Để biết nguyên nhân vì sao, chúng ta hãy cùng đến với cách thêm, xóa node trong Nested set model.

Thêm node mới

Giả sử cần thêm mục Nhạc nước ngoài thuộc mục Âm nhạc ta sẽ phải cập nhật lại dữ liệu như hình bên dưới.

Nested set model - adding node

Tổng quát, ta cần làm 2 thao tác:

  1. Tạo ra vùng trống mới trong node Âm nhạc tăng từ [8, 9] => [8, 11]
  2. Thêm node Nước ngoài [9, 10] vào node Âm nhạc

Thao tác 1 sẽ tốn nhiều chi phí vì chúng ta tăng giá trị Left, Right phía sau lên 2 đơn vị (chính là vùng trống dành cho node mới) bằng điều kiện:

Thao tác tiếp theo nhẹ nhàng hơn là chỉ việc thêm node Nước ngoài có giá trị Left, Right = 9, 10 vào CSDL nữa là xong.

Xóa node

Giả sử muốn xóa mục Âm nhạc, ta cần thực hiện cập nhật dữ liệu như hình bên dưới:

Nested set model - removing node

Tổng quát ta sẽ làm hai thao tác:

  1. Xóa node và những node con của nó (mục Âm nhạc + mục Nước ngoài)
  2. Cập nhật lại Left, Right. Thực chất việc này chỉ làm cho dữ liệu được chuẩn hóa Left, Right mà thôi. Cho dù không cập nhật lại Left, Right đi chăng nữa thì việc truy xuất dữ liệu vẫn đúng.

Thao tác 1 không tốn nhiều chi phí, chỉ cần xóa node đó và tất cả node con thuộc nó (truy vấn tất cả node con đã liệt kê ở phần ở trên).

Thao tác 2 tốn nhiều chi phí vì phải giảm N * 2 đơn vị cho Left, Right (N là số node bị xóa, trong ví dụ là N = 2). Trong ví dụ xóa mục Âm nhạc trên ta có SQL query như sau:

Như vậy, chúng ta đã có thể thao tác được với dữ liệu phân cấp với kỹ thuật của mô hình tập hợp lồng nhau. Với những ưu, nhược điểm đã nêu, chúng ta hãy lựa chọn phương pháp phù hợp cho mình trong việc tổ chức các loại danh mục phân cấp cho ứng dụng của mình.

Nếu bạn có mô hình khác tốt hơn thì comment ngay bên dưới nhé!

SSS Full-stack Engineer

Love Silicon Straits and want to know more about our company culture, working environment or job vacancies?
Find out more at careers.siliconstraits.vn.

Silicon Straits
Be Challenged. Be Inspired. Be Different.




Posted by

on November 3, 2015

in , ,

Comments

Follow us for more later

or subscribe with