Pertanyaan Apa sajakah opsi untuk menyimpan data hierarkis dalam basis data relasional?


Ringkasan Baik

Secara umum, Anda membuat keputusan antara waktu baca cepat (misalnya, nested set) atau waktu tulis cepat (daftar adjacency). Biasanya, Anda berakhir dengan kombinasi opsi di bawah ini yang paling sesuai dengan kebutuhan Anda. Berikut ini memberikan beberapa bacaan mendalam:

Pilihan

Yang saya sadari dan fitur umum:

  1. Daftar Adjacency:
    • Kolom: ID, ParentID
    • Mudah diimplementasikan.
    • Cheap node bergerak, menyisipkan, dan menghapus.
    • Mahal untuk menemukan tingkat, leluhur & keturunan, jalan
    • Hindari N + 1 via Ekspresi Tabel Umum dalam basisdata yang mendukungnya
  2. Set Bersarang (a.k.a Modifikasi Preorder Tree Traversal)
    • Kolom: Kiri, Kanan
    • Leluhur yang murah, keturunan
    • Sangat mahal O(n/2) memindahkan, menyisipkan, menghapus karena pengkodean yang mudah menguap
  3. Meja Jembatan (a.k.a. Tabel penutupan / pemicu)
    • Menggunakan tabel gabungan terpisah dengan: leluhur, keturunan, kedalaman (opsional)
    • Leluhur dan keturunan yang murah
    • Menulis biaya O(log n) (ukuran subtree) untuk disisipkan, diperbarui, dihapus
    • Normalized encoding: baik untuk statistik RDBMS & perencana kueri dalam gabungan
    • Membutuhkan banyak baris per node
  4. Lineage Column (a.k.a. Jalan yang Terwujud, Enumerasi Jalur)
    • Kolom: garis keturunan (mis. / Orang tua / anak / cucu / dll ...)
    • Keturunan murah melalui permintaan awalan (mis. LEFT(lineage, #) = '/enumerated/path')
    • Menulis biaya O(log n) (ukuran subtree) untuk disisipkan, diperbarui, dihapus
    • Non-relasional: bergantung pada tipe data Array atau format string serial
  5. Interval Bersarang
    • Seperti nested set, tetapi dengan real / float / decimal sehingga pengkodean tidak mudah berubah (memindahkan / memasukkan / menghapus murah)
    • Memiliki masalah representasi / presisi nyata / hanyut / desimal
    • Varian encoding matriks menambahkan pengkodean leluhur (terwujud jalan) untuk "bebas", tetapi dengan menambahkan trickiness dari aljabar linier.
  6. Meja Datar
    • Daftar Adjacency yang dimodifikasi yang menambahkan kolom Level dan Peringkat (misalnya pemesanan) ke setiap record.
    • Murah untuk iterasi / nomor halaman
    • Pemindahan dan penghapusan yang mahal
    • Penggunaan Baik: diskusi berulir - forum / komentar blog
  7. Beberapa kolom garis keturunan
    • Kolom: satu untuk setiap tingkat garis keturunan, mengacu pada semua orang tua hingga ke akar, tingkat ke bawah dari tingkat item diatur ke NULL
    • Leluhur yang murah, keturunan, tingkat
    • Masukkan, hapus, pindah daun
    • Sisipan mahal, hapus, pindah dari simpul internal
    • Batas keras untuk seberapa dalam hirarki bisa

Catatan Khusus Database

MySQL

Peramal

  • Menggunakan CONNECT BY untuk melintasi Daftar Adjacency

PostgreSQL

SQL Server

  • Ringkasan umum
  • 2008 menawarkan HierarchyId tipe data muncul untuk membantu dengan pendekatan Kolom Baris dan memperluas kedalaman yang dapat diwakili.

1061
2017-10-29 00:34


asal


Jawaban:


Jawaban favorit saya adalah seperti apa kalimat pertama di thread ini yang disarankan. Gunakan Daftar Adjacency untuk mempertahankan hierarki dan gunakan Kumpulan Bersarang untuk menanyakan hierarki.

Masalahnya sampai sekarang adalah bahwa metode coverion dari Daftar Adjacecy ke Nested Sets telah sangat lambat karena kebanyakan orang menggunakan metode RBAR ekstrim yang dikenal sebagai "Push Stack" untuk melakukan konversi dan telah dianggap sebagai cara untuk mahal untuk mencapai Nirvana dari kesederhanaan pemeliharaan oleh Daftar Adjacency dan kinerja mengagumkan dari Kumpulan Bersarang. Akibatnya, kebanyakan orang akhirnya harus puas dengan satu atau yang lain terutama jika ada lebih dari, katakanlah, 100.000 node yang buruk atau lebih. Menggunakan metode push stack dapat menghabiskan waktu seharian untuk melakukan konversi pada apa yang akan dianggap MLM sebagai hierarki kecil juta node.

Saya pikir saya akan memberikan Celko sedikit kompetisi dengan datang dengan metode untuk mengubah Daftar Adjacency ke Nested set dengan kecepatan yang sepertinya tidak mungkin. Berikut performa metode push stack pada laptop i5 saya.

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'

Dan inilah durasi untuk metode baru (dengan metode push stack dalam kurung).

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!!!)

Ya itu benar. 1 juta node dikonversi dalam waktu kurang dari satu menit dan 100.000 node dalam waktu kurang dari 4 detik.

Anda dapat membaca tentang metode baru dan mendapatkan salinan kode di URL berikut. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Saya juga mengembangkan hierarki "pra-agregat" menggunakan metode yang serupa. Para MLM dan orang-orang yang membuat tagihan materi akan tertarik dengan artikel ini. http://www.sqlservercentral.com/articles/T-SQL/94570/

Jika Anda mampir untuk melihat artikel, masuk ke tautan "Bergabunglah dengan diskusi" dan beri tahu saya apa pendapat Anda.


30



Ini adalah jawaban yang sangat parsial untuk pertanyaan Anda, tetapi saya harap masih berguna.

Microsoft SQL Server 2008 mengimplementasikan dua fitur yang sangat berguna untuk mengelola data hierarkis:

Silahkan lihat "Model Hierarki Data Anda Dengan SQL Server 2008" oleh Kent Tegels di MSDN untuk memulai. Lihat juga pertanyaan saya sendiri: Rekursif query tabel-sama di SQL Server 2008


21



Desain ini belum disebutkan:

Beberapa kolom garis keturunan

Meskipun memiliki keterbatasan, jika Anda dapat menanggungnya, itu sangat sederhana dan sangat efisien. Fitur:

  • Kolom: satu untuk setiap tingkat garis keturunan, mengacu pada semua orang tua hingga ke akar, tingkat di bawah tingkat item saat ini diatur ke NULL
  • Batasi seberapa dalam hirarki bisa
  • Leluhur yang murah, keturunan, tingkat
  • Masukkan, hapus, pindah daun
  • Sisipan mahal, hapus, pindah dari simpul internal

Berikut mengikuti contoh - pohon taksonomi burung sehingga hierarki adalah Kelas / Ordo / Keluarga / Genus / Spesies - spesies adalah tingkat terendah, 1 baris = 1 takson (yang sesuai dengan spesies dalam kasus simpul daun):

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 ''
);

dan contoh data:

+---------+---------+---------+----------+---------+-------------------------------+
| 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                   |

Ini bagus karena cara ini Anda mencapai semua operasi yang dibutuhkan dengan cara yang sangat mudah, asalkan kategori internal tidak mengubah levelnya di pohon.


20



Model Adjacency + Nested Sets Model

Saya melakukannya karena saya dapat memasukkan item baru ke pohon dengan mudah (Anda hanya perlu ID cabang untuk memasukkan item baru ke sana) dan juga menanyakannya cukup cepat.

+-------------+----------------------+--------+-----+-----+
| 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 |
+-------------+----------------------+--------+-----+-----+
  • Setiap kali Anda membutuhkan semua anak dari orang tua yang baru saja Anda tanyakan parent kolom.
  • Jika Anda membutuhkan semua keturunan dari orang tua Anda, Anda harus menanyakan barang-barang yang mereka miliki lft antara lft dan rgt orang tua.
  • Jika Anda membutuhkan semua orang tua dari setiap node hingga ke akar pohon, Anda harus meminta item yang memiliki lft lebih rendah dari node lft dan rgt lebih besar dari node rgt dan mengurutkan dengan parent.

Saya perlu membuat akses dan query pohon lebih cepat dari sisipan, itulah mengapa saya memilih ini

Satu-satunya masalah adalah memperbaiki left dan right kolom saat memasukkan item baru. Saya membuat prosedur yang tersimpan untuk itu dan memanggilnya setiap kali saya memasukkan item baru yang langka dalam kasus saya tetapi sangat cepat. Saya mendapat ide dari buku Joe Celko, dan prosedur tersimpan dan bagaimana saya memunculkannya dijelaskan di sini di DBA SE https://dba.stackexchange.com/q/89051/41481


13



Jika database Anda mendukung array, Anda juga dapat mengimplementasikan kolom garis keturunan atau jalur terwujud sebagai larik id induk.

Khusus dengan Postgres, Anda kemudian dapat menggunakan operator yang ditetapkan untuk melakukan kueri hierarki, dan mendapatkan kinerja yang sangat baik dengan indeks GIN. Ini membuat menemukan orang tua, anak-anak, dan kedalaman cukup sepele dalam satu permintaan. Pembaruan sangat mudah dikelola juga.

Saya memiliki penulisan lengkap menggunakan larik untuk jalur yang terwujud jika kamu penasaran.


10



Ini benar-benar pasak persegi, pertanyaan lubang bundar.

Jika database relasional dan SQL adalah satu-satunya palu yang Anda miliki atau mau gunakan, maka jawaban yang telah diposting sejauh ini memadai. Namun, mengapa tidak menggunakan alat yang dirancang untuk menangani data hierarkis? Database grafik ideal untuk data hirarkis yang rumit.

Inefisiensi model relasional bersama dengan kompleksitas solusi kode / query untuk memetakan grafik / model hierarkis ke model relasional tidak sebanding dengan usaha bila dibandingkan dengan kemudahan solusi database grafik dapat memecahkan masalah yang sama.

Pertimbangkan Bill of Materials sebagai struktur data hirarkis umum.

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Jalur terpendek antara dua sub-rakitan: Algoritme grafik sederhana traversal. Jalur yang dapat diterima dapat dikualifikasikan berdasarkan kriteria.

Kesamaan: Apa tingkat kesamaan antara dua majelis? Lakukan traversal pada kedua sub-pohon menghitung persimpangan dan penyatuan dua sub-pohon. Persen yang serupa adalah perpotongan dibagi dengan serikat pekerja.

Penutupan Transitif: Jalani sub-pohon dan jumlah bidang minat, mis. "Berapa banyak aluminium dalam sub-rakitan?"

Ya, Anda dapat memecahkan masalah dengan SQL dan database relasional. Namun, ada pendekatan yang jauh lebih baik jika Anda bersedia menggunakan alat yang tepat untuk pekerjaan itu.


7



Saya menggunakan PostgreSQL dengan tabel penutupan untuk hierarki saya. Saya memiliki satu prosedur penyimpanan universal untuk seluruh database:

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;
$_$;

Kemudian untuk setiap tabel di mana saya memiliki hierarki, saya membuat pemicu

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');

Untuk mengisi tabel penutupan dari hierarki yang ada, saya menggunakan prosedur tersimpan ini:

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;
$$;

Tabel penutupan didefinisikan dengan 3 kolom - ANCESTOR_ID, DESCENDANT_ID, KEDALAMAN. Adalah mungkin (dan saya bahkan menyarankan) untuk menyimpan catatan dengan nilai yang sama untuk ANCESTOR dan DESCENDANT, dan nilai nol untuk KEDALAMAN. Ini akan menyederhanakan pertanyaan untuk pengambilan hierarki. Dan mereka memang sangat sederhana:

-- 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