Câu hỏi Các tùy chọn để lưu trữ dữ liệu phân cấp trong cơ sở dữ liệu quan hệ là gì?


Tổng quan tốt

Nói chung, bạn đang đưa ra quyết định giữa thời gian đọc nhanh (ví dụ, tập lồng nhau) hoặc thời gian ghi nhanh (danh sách kề). Thông thường, bạn kết thúc với một sự kết hợp của các tùy chọn dưới đây phù hợp nhất với nhu cầu của bạn. Sau đây cung cấp một số đọc sâu:

Tùy chọn

Tôi nhận thức được và các tính năng chung:

  1. Danh sách Adjacency:
    • Cột: ID, ParentID
    • Dễ để thực hiện.
    • Di chuyển nút, chèn và xóa giá rẻ.
    • Đắt tiền để tìm mức độ, tổ tiên & con cháu, con đường
    • Tránh N + 1 qua Biểu thức bảng chung trong cơ sở dữ liệu hỗ trợ họ
  2. Tập hợp lồng nhau (a.k.a Đã sửa đổi cây đặt hàng trước)
    • Cột: Trái, Phải
    • Tổ tiên giá rẻ, hậu duệ
    • Rất đắt O(n/2) di chuyển, chèn, xóa do mã hóa dễ bay hơi
  3. Bảng cầu (a.k.a. Đóng cửa bảng / w gây nên)
    • Sử dụng bảng nối riêng biệt với: tổ tiên, hậu duệ, chiều sâu (tùy chọn)
    • Tổ tiên và hậu duệ giá rẻ
    • Ghi chi phí O(log n) (kích thước của cây con) để chèn, cập nhật, xóa
    • Mã hóa được chuẩn hóa: tốt cho các thống kê RDBMS và kế hoạch truy vấn trong các phép nối
    • Yêu cầu nhiều hàng trên mỗi nút
  4. Cột Lineage (a.k.a. Đường dẫn vật chất, Đường dẫn liệt kê)
    • Cột: dòng truyền thừa (ví dụ: / parent / child / grandchild / etc ...)
    • Con cháu giá rẻ thông qua truy vấn tiền tố (ví dụ: LEFT(lineage, #) = '/enumerated/path')
    • Ghi chi phí O(log n) (kích thước của cây con) để chèn, cập nhật, xóa
    • Không quan hệ: dựa trên kiểu dữ liệu Array hoặc định dạng chuỗi được tuần tự hóa
  5. Khoảng thời gian lồng nhau
    • Giống như tập lồng nhau, nhưng với thực / phao / thập phân sao cho mã hóa không dễ bay hơi (di chuyển / chèn / xóa không tốn kém)
    • Có các vấn đề về độ chính xác / thực / số thập phân / số thập phân
    • Biến thể mã hóa ma trận thêm mã hóa tổ tiên (đường dẫn vật chất) cho "miễn phí", nhưng với sự khéo léo thêm của đại số tuyến tính.
  6. Bảng phẳng
    • Danh sách Adjacency được sửa đổi sẽ thêm cột Cấp bậc và Xếp hạng (ví dụ: đặt hàng) vào mỗi bản ghi.
    • Giá rẻ để lặp / phân trang
    • Di chuyển và xóa đắt tiền
    • Sử dụng tốt: thảo luận luồng - diễn đàn / bình luận trên blog
  7. Nhiều dòng chi tiết
    • Cột: một cho mỗi cấp độ dòng, đề cập đến tất cả các bậc cha mẹ lên đến gốc, mức độ xuống từ cấp độ của mặt hàng được thiết lập để NULL
    • Tổ tiên giá rẻ, hậu duệ, cấp độ
    • Giá rẻ chèn, xóa, di chuyển của lá
    • Chèn, xóa, di chuyển các nút nội bộ đắt tiền
    • Giới hạn cứng về mức độ phân cấp có thể

Cơ sở dữ liệu

MySQL

Oracle

PostgreSQL

Máy chủ SQL

  • Tóm tắt chung
  • Ưu đãi 2008 HierarchyId kiểu dữ liệu xuất hiện để trợ giúp với cách tiếp cận Lineage Column và mở rộng độ sâu có thể được biểu diễn.

1063
2017-10-29 00:34


gốc


Vâng. "Duy trì việc đóng cửa các đồ thị trong SQL" bởi Libkin et.al là một bài báo kinh điển về chủ đề này. - Tegiri Nenashi
Theo slideshare.net/billkarwin/sql-antipatterns-strike-back trang 77, Closure Tables vượt trội hơn Adjacency List, Path Enumeration và Nested Sets về mặt dễ sử dụng (và tôi cũng đoán hiệu suất). - Gili
Liên kết MSDN đó cho "Tóm tắt chung" không còn hiển thị bài viết. Trong ấn bản tháng 9 năm 2008 của tạp chí MSDN, bạn có thể tải xuống dưới dạng tệp CHM hoặc xem qua lưu trữ web tại: web.archive.org/web/20080913041559/http://msdn.microsoft.com:80/… - David Kemp
Đóng cử tri những ngày đó chỉ đọc các tiêu đề. Không cố gắng để hiểu phạm vi của câu hỏi và họ không đọc câu trả lời, các bạn thực sự cố gắng sử dụng thêm nút SKIP khi bạn không hiểu về một chủ đề - jean
Câu hỏi này sâu đến nỗi tôi tự hỏi họ có thể đặt một cái gì đó như thế này, chắc chắn nó có thể rộng nhưng xem xét nó là chiều sâu của nó. Không có gì bỏ phiếu để mở lại - Viney


Các câu trả lời:


Câu trả lời yêu thích của tôi là câu đầu tiên trong chuỗi này được đề xuất. Sử dụng Danh sách Adjacency để duy trì cấu trúc phân cấp và sử dụng Nested Sets để truy vấn cấu trúc phân cấp.

Vấn đề cho đến bây giờ là phương pháp bao phủ từ một danh sách Adjacecy đến Nested Sets đã rất chậm vì hầu hết mọi người sử dụng phương pháp RBAR cực đoan được gọi là "Push Stack" để thực hiện chuyển đổi và được coi là đắt tiền để đạt được Nirvana của sự đơn giản của bảo trì bởi Danh sách Adjacency và hiệu suất tuyệt vời của Nested Sets. Kết quả là, hầu hết mọi người cuối cùng phải giải quyết cho một hoặc khác, đặc biệt là nếu có nhiều hơn, nói, một 100.000 nút tệ hại hoặc hơn. Sử dụng phương pháp push stack có thể mất cả ngày để thực hiện chuyển đổi trên những gì MLM'ers coi là một hệ thống phân cấp nút nhỏ.

Tôi nghĩ tôi sẽ cho Celko một chút cạnh tranh bằng cách đưa ra một phương pháp để chuyển đổi một danh sách Adjacency thành Nested với tốc độ mà dường như không thể. Đây là hiệu suất của phương pháp push stack trên máy tính xách tay i5 của tôi.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

Và đây là khoảng thời gian cho phương thức mới (với phương pháp ngăn xếp đẩy trong dấu ngoặc đơn).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Vâng đúng rồi. 1 triệu nút được chuyển đổi trong chưa đầy một phút và 100.000 nút trong chưa đầy 4 giây.

Bạn có thể đọc về phương thức mới và nhận bản sao mã tại URL sau. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Tôi cũng đã phát triển một hệ thống phân cấp "được tổng hợp trước" bằng các phương pháp tương tự. MLM'ers và mọi người lập hóa đơn vật liệu sẽ đặc biệt quan tâm đến bài viết này. http://www.sqlservercentral.com/articles/T-SQL/94570/

Nếu bạn dừng lại để xem một trong hai bài viết, hãy nhảy vào liên kết "Tham gia thảo luận" và cho tôi biết suy nghĩ của bạn.


32





Đây là một câu trả lời rất riêng cho câu hỏi của bạn, nhưng tôi hy vọng vẫn hữu ích.

Microsoft SQL Server 2008 triển khai hai tính năng cực kỳ hữu ích để quản lý dữ liệu phân cấp:

  • các HierarchyId loại dữ liệu.
  • biểu thức bảng chung, sử dụng với từ khóa.

Hãy xem "Lập mô hình phân cấp dữ liệu của bạn với SQL Server 2008" bởi Kent Tegels trên MSDN để bắt đầu. Xem thêm câu hỏi của riêng tôi: Truy vấn đồng bộ bảng đệ quy trong SQL Server 2008


21



Thú vị, HierarchyId, không biết về điều đó: msdn.microsoft.com/en-us/library/bb677290.aspx - orangepips
Thật. Tôi làm việc với rất nhiều dữ liệu phân cấp đệ quy, và tôi thấy các biểu thức bảng chung rất hữu ích. Xem msdn.microsoft.com/en-us/library/ms186243.aspx cho phần giới thiệu. - CesarGon


Thiết kế này chưa được đề cập:

Nhiều dòng chi tiết

Mặc dù nó có những hạn chế, nếu bạn có thể chịu đựng chúng, nó rất đơn giản và rất hiệu quả. Tính năng, đặc điểm:

  • Cột: một cho mỗi cấp độ dòng, đề cập đến tất cả các bậc cha mẹ lên đến gốc, mức độ dưới mức các mục hiện tại được đặt thành NULL
  • Giới hạn mức độ phân cấp có thể
  • Tổ tiên giá rẻ, hậu duệ, cấp độ
  • Giá rẻ chèn, xóa, di chuyển của lá
  • Chèn, xóa, di chuyển các nút nội bộ đắt tiền

Dưới đây là một ví dụ - cây phân loại của các loài chim để phân cấp là lớp / thứ tự / gia đình / chi / loài - loài là mức thấp nhất, 1 hàng = 1 taxon (tương ứng với loài trong trường hợp của các nút lá):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

và ví dụ về dữ liệu:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

Điều này là rất tốt bởi vì cách này bạn hoàn thành tất cả các hoạt động cần thiết một cách rất dễ dàng, miễn là các loại nội bộ không thay đổi cấp độ của chúng trong cây.


20





Mô hình Adjacency + Nested Sets Model

Tôi đã cho nó bởi vì tôi có thể chèn các mục mới vào cây một cách dễ dàng (bạn chỉ cần một id của chi nhánh để chèn một mục mới vào nó) và cũng có thể truy vấn nó khá nhanh.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • Mỗi khi bạn cần tất cả trẻ em của bất kỳ phụ huynh bạn chỉ cần truy vấn parent cột.
  • Nếu bạn cần tất cả các hậu duệ của bất kỳ phụ huynh nào bạn truy vấn các mục có lft giữa lft và rgt của cha mẹ.
  • Nếu bạn cần tất cả các bậc cha mẹ của bất kỳ nút nào đến gốc của cây, bạn truy vấn các mục có lft thấp hơn nút lft và rgt lớn hơn nút rgt và sắp xếp theo parent.

Tôi cần phải truy cập và truy vấn cây nhanh hơn chèn, đó là lý do tại sao tôi chọn

Vấn đề duy nhất là sửa chữa left và right cột khi chèn các mục mới. Tôi cũng tạo ra một thủ tục lưu trữ cho nó và gọi nó mỗi khi tôi chèn một mục mới mà là hiếm trong trường hợp của tôi, nhưng nó thực sự là nhanh. Tôi có ý tưởng từ cuốn sách của Joe Celko, và thủ tục lưu trữ và cách tôi nghĩ ra nó được giải thích ở đây trong DBA SE https://dba.stackexchange.com/q/89051/41481


13



+1 đây là một cách tiếp cận hợp pháp. Từ kinh nghiệm của riêng tôi, chìa khóa sẽ quyết định xem bạn có đồng ý với những lần đọc bẩn khi các hoạt động cập nhật lớn xảy ra. Nếu không, nó sẽ trở thành một vấn đề hoặc ngăn chặn mọi người truy vấn trực tiếp các bảng và luôn đi qua một API - các sprocs DB / hàm hoặc mã. - orangepips
Đây là một giải pháp thú vị; tuy nhiên, tôi không chắc chắn việc truy vấn cột cha thực sự mang lại lợi thế lớn nào khi cố gắng tìm con - đó là lý do tại sao chúng tôi có cột trái và phải, ngay từ đầu. - Thomas
@ Thomas, có sự khác biệt giữa children và descendants. left và right được sử dụng để tìm các hậu duệ. - azerafati


Nếu cơ sở dữ liệu của bạn hỗ trợ các mảng, bạn cũng có thể triển khai một cột dòng hoặc đường dẫn vật hoá dưới dạng một mảng các id cha.

Cụ thể với Postgres, bạn có thể sử dụng các toán tử thiết lập để truy vấn hệ thống phân cấp và nhận được hiệu suất tuyệt vời với các chỉ số GIN. Điều này làm cho việc tìm kiếm cha mẹ, con cái và chiều sâu khá tầm thường trong một truy vấn. Cập nhật là khá dễ quản lý là tốt.

Tôi đã viết đầy đủ về việc sử dụng mảng cho đường dẫn vật chất hóa nếu bạn tò mò.


10





Đây thực sự là một hình vuông, câu hỏi lỗ tròn.

Nếu cơ sở dữ liệu quan hệ và SQL là búa duy nhất bạn có hoặc sẵn sàng sử dụng, thì câu trả lời đã được đăng cho đến nay là đủ. Tuy nhiên, tại sao không sử dụng một công cụ được thiết kế để xử lý dữ liệu phân cấp? Cơ sở dữ liệu đồ thị lý tưởng cho dữ liệu phân cấp phức tạp.

Sự thiếu hiệu quả của mô hình quan hệ cùng với sự phức tạp của bất kỳ giải pháp mã / truy vấn nào để ánh xạ một mô hình đồ thị / phân cấp lên mô hình quan hệ không đáng để so sánh với sự dễ dàng mà giải pháp cơ sở dữ liệu đồ thị có thể giải quyết cùng một vấn đề.

Hãy xem xét một Bill of Materials như một cấu trúc dữ liệu phân cấp chung.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Con đường ngắn nhất giữa hai hội đồng phụ: Thuật toán truyền tải đồ thị đơn giản. Đường dẫn có thể chấp nhận có thể đủ điều kiện dựa trên tiêu chí.

Tương tự: Mức độ tương tự giữa hai hội đồng là gì? Thực hiện một cuộc di chuyển trên cả hai cây con tính toán giao lộ và liên minh của hai cây con. Phần trăm tương tự là giao lộ chia cho công đoàn.

Sự đóng kín: Đi bộ cây con và tổng hợp (các) trường quan tâm, ví dụ: "Có bao nhiêu nhôm trong một hội đồng phụ?"

Có, bạn có thể giải quyết vấn đề với SQL và một cơ sở dữ liệu quan hệ. Tuy nhiên, có nhiều cách tiếp cận tốt hơn nếu bạn sẵn sàng sử dụng đúng công cụ cho công việc.


7



Câu trả lời này sẽ vô cùng hữu ích hơn nếu các trường hợp sử dụng được chứng minh, hoặc tốt hơn là tương phản, làm thế nào để truy vấn một cơ sở dữ liệu đồ thị với SPARQL ví dụ thay vì SQL trong một RDBMS. - orangepips
SPARQL có liên quan đến cơ sở dữ liệu RDF là một lớp con của miền lớn hơn của cơ sở dữ liệu biểu đồ. Tôi làm việc với InfiniteGraph mà không phải là một cơ sở dữ liệu RDF và hiện không hỗ trợ SPARQL. InfiniteGraph hỗ trợ một số cơ chế truy vấn khác nhau: (1) API điều hướng biểu đồ để thiết lập chế độ xem, bộ lọc, vòng loại đường dẫn và trình xử lý kết quả, (2) biểu đồ đường dẫn biểu đồ phức tạp, và (3) Gremlin. - djhallx


Tôi đang sử dụng PostgreSQL với các bảng đóng cho các hệ thống phân cấp của tôi. Tôi có một thủ tục lưu trữ chung cho toàn bộ cơ sở dữ liệu:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Sau đó, đối với mỗi bảng nơi tôi có một hệ thống phân cấp, tôi tạo trình kích hoạt

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Để điền một bảng đóng cửa từ hệ thống phân cấp hiện có, tôi sử dụng thủ tục được lưu trữ này:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

Các bảng đóng được định nghĩa với 3 cột - ANCESTOR_ID, DESCENDANT_ID, DEPTH. Có thể (và tôi thậm chí là lời khuyên) để lưu trữ các bản ghi có cùng giá trị cho ANCESTOR và DESCENDANT, và một giá trị bằng 0 cho DEPTH. Điều này sẽ đơn giản hóa các truy vấn để truy lục hệ thống phân cấp. Và chúng rất đơn giản:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

4