7 Pertanyaan: Apa saja pilihan untuk menyimpan data hierarkis dalam database relasional?

pertanyaan dibuat di Mon, Apr 22, 2019 12:00 AM

Gambaran Umum yang Baik

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

Yang saya tahu dan fitur-fitur umum:

  1. Daftar Adjacency :
    • Kolom: ID, ParentID
    • Mudah diterapkan.
    • Simpul murah bergerak, menyisipkan, dan menghapus.
    • Mahal untuk menemukan level, keturunan & keturunan, jalur
    • Hindari N + 1 melalui Ekspresi Common Table dalam database yang mendukung mereka
  2. Nested Set (alias Modifikasi Preorder Tree Traversal )
    • Kolom: Kiri, Kanan
    • Nenek moyang murah, keturunan
    • O(n/2) pemindahan, pemasukan, penghapusan yang sangat mahal karena penyandian yang mudah menguap
  3. Bridge Table (alias Tabel Penutupan /pemicu w )
    • Menggunakan tabel gabungan terpisah dengan: leluhur, keturunan, kedalaman (opsional)
    • Nenek moyang dan keturunan yang murah
    • Menulis biaya O(log n) (ukuran subtree) untuk disisipkan, diperbarui, dihapus
    • Pengkodean yang dinormalisasi: baik untuk statistik RDBMS & perencana kueri bergabung
    • Memerlukan beberapa baris per node
  4. Kolom Lineage (alias Path Terwujud , Path Enumeration)
    • Kolom: garis silsilah (mis. /orang tua /anak /cucu /dll ...)
    • Keturunan murah melalui kueri 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
    • Suka kumpulan yang disarangkan, tetapi dengan real /float /desimal sehingga pengkodeannya tidak mudah berubah (langkah /masukkan /hapus yang murah)
    • Mengalami masalah representasi /presisi nyata /float /desimal
    • varian pengkodean matriks menambahkan pengkodean leluhur (jalur material) untuk "gratis", tetapi dengan menambahkan trickiness aljabar linier.
  6. Tabel Rata
    • Daftar Ajudikasi yang dimodifikasi yang menambahkan kolom Level dan Peringkat (mis. pemesanan) ke setiap catatan.
    • Murah untuk digunakan kembali /paginasi lebih dari
    • Pindahkan dan hapus mahal
    • Penggunaan Baik: diskusi beralur - komentar forum /blog
  7. Beberapa kolom garis keturunan
    • Kolom: satu untuk setiap level garis keturunan, merujuk ke semua orang tua hingga ke akar, level turun dari level item diatur ke NULL
    • Nenek moyang, keturunan, level
    • yang murah
    • Sisipan murah, hapus, pindahkan daun
    • Sisipkan mahal, hapus, pindahkan node internal
    • Batas keras hingga seberapa dalam hierarki dapat

Catatan Khusus Basis Data

MySQL

Oracle

PostgreSQL

SQL Server

  • Ringkasan umum
  • 2008 menawarkan HierarchyId tipe data tampaknya membantu dengan pendekatan Lineage Column dan perluas kedalaman yang bisa direpresentasikan.
1226
  1. Menurut slideshare .net /billkarwin /sql-antipatterns-strike-back halaman 77, Closure Tables lebih unggul dari Adjacency List, Path Enumeration dan Nested Sets dalam hal kemudahan penggunaan (dan saya juga menebak-nebak kinerjanya).
    2012-11-01 00: 36: 48Z
  2. Saya kehilangan versi yang sangat sederhana di sini: gumpalan sederhana. Jika hierarki Anda hanya memiliki beberapa item dozend, pohon id serial mungkin merupakan opsi terbaik.
    2015-11-12 16: 22: 16Z
  3. @ Lothar: pertanyaan adalah wiki komunitas jadi jangan ragu untuk mendapatkannya. Pemikiran saya dalam hal ini adalah saya hanya akan melakukannya dengan database yang mendukung semacam penataan gumpalan seperti XML dengan bahasa query yang stabil seperti XPATH. Kalau tidak, saya tidak melihat cara yang baik untuk query selain dari mengambil, deserialize, dan membuat kesalahan dalam kode, bukan SQL. Dan jika Anda benar-benar memiliki masalah di mana Anda memerlukan banyak elemen arbitrer, Anda mungkin lebih baik menggunakan database Node seperti Neo4J, yang telah saya gunakan dan sukai, meskipun tidak pernah digunakan untuk produksi.
    2016-01-23 12: 51: 58Z
  4. 2017-07-26 12: 48: 28Z
  5. Tautan MSDN untuk "Ringkasan Umum" tidak lagi menampilkan artikel. Itu dalam edisi September 2008 Majalah MSDN, yang dapat Anda unduh sebagai file CHM, atau lihat melalui arsip web di: web.archive.org/web/20080913041559/http://msdn.microsoft.com:80/…
    2017-10-18 10: 19: 11Z
7 Jawaban                              7                         

Jawaban favorit saya adalah seperti yang disarankan kalimat pertama di utas ini. Gunakan Daftar Adjacency untuk mempertahankan hierarki dan gunakan Nested Sets untuk menanyakan hierarki.

Masalahnya sampai sekarang adalah bahwa metode peliputan dari Adjacecy List 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 yang mahal untuk mencapai Nirvana dari kesederhanaan perawatan oleh Daftar Adjacency dan kinerja Nested Sets yang mengagumkan. Akibatnya, kebanyakan orang akhirnya harus puas dengan satu atau yang lain terutama jika ada lebih dari, katakanlah, sekitar 100.000 node yang buruk. Menggunakan metode push stack bisa memakan waktu satu hari penuh untuk melakukan konversi pada apa yang akan dianggap oleh MLM sebagai hierarki jutaan node kecil.

Saya pikir saya akan memberi Celko sedikit kompetisi dengan datang dengan sayaMereka akan mengonversi Daftar Adjacency ke Nested dengan kecepatan yang sepertinya mustahil. Inilah kinerja metode push stack di 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 tanda 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 serupa. MLMer dan orang-orang yang membuat tagihan bahan akan sangat tertarik dengan artikel ini. http://www.sqlservercentral.com/articles/T-SQL/94570/

Jika Anda mampir untuk melihat kedua artikel tersebut, masuklah ke tautan "Bergabung dengan diskusi" dan beri tahu saya pendapat Anda.

    
58
2013-03-04 02: 22: 41Z

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

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

Lihatlah " Model Hierarki Data Anda Dengan SQL Server 2008 " oleh Kent Tegels di MSDN untuk memulai. Lihat juga pertanyaan saya sendiri: Permintaan tabel-sama rekursif dalam SQL Server 2008

    
30
2017-07-26 14: 03: 02Z
  1. Menarik, the HierarchyId, tidak tahu tentang itu: msdn.microsoft.com/en-us/library/bb677290.aspx
    2010-10-29 00: 38: 21Z
  2. Memang. Saya bekerja dengan banyak data hierarkis rekursif, dan saya menemukan ekspresi tabel umum sangat berguna. Lihat msdn.microsoft.com/en-us/library/ms186243.aspx untuk intro.
    2010-10-29 00: 41: 39Z

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 level garis keturunan, merujuk ke semua orang tua hingga ke akar, level di bawah level item saat ini diatur ke NULL
  • Batasi sampai seberapa dalam hierarki bisa
  • Nenek moyang, keturunan, level
  • yang murah
  • Sisipan murah, hapus, pindahkan daun
  • Sisipkan mahal, hapus, pindahkan node internal

Berikut ini contoh - pohon taksonomi burung sehingga hierarki adalah Kelas /Urutan /Keluarga /Genus /Spesies - spesies adalah level 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 datanya:

 
+---------+---------+---------+----------+---------+-------------------------------+
| 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 dengan cara ini Anda menyelesaikan semua operasi yang diperlukan dengan cara yang sangat mudah, asalkan kategori internal tidak mengubah levelnya di pohon.

    
26
2017-05-23 12: 02: 58Z

Model Adjacency + Model Nested Sets

Saya melakukannya karena saya bisa memasukkan new item ke pohon dengan mudah (Anda hanya perlu id cabang untuk memasukkan item baru ke dalamnya) dan juga menanyakannya dengan 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 apa pun, Anda cukup menanyakan kolom parent.
  • Jika Anda membutuhkan semua keturunan orang tua mana pun, Anda mencari item yang memiliki lft antara lft dan rgt induk.
  • Jika Anda membutuhkan semua orang tua dari simpul mana pun hingga ke akar pohon, Anda meminta item memiliki lft lebih rendah dari lft simpul dan rgt lebih besar dari simpul rgt dan mengurutkannya dengan parent.

Saya perlu membuat mengakses dan menanyakan pohon lebih cepat daripada memasukkan, itu sebabnya saya memilih ini

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

    
18
2017-04-13 12: 42: 40Z
  1. +1 ini adalah pendekatan yang sah. Dari pengalaman saya sendiri kuncinya adalah memutuskan apakah Anda OK dengan membaca kotor ketika operasi pembaruan besar terjadi. Jika tidak, itu menjadi masalah atau mencegah orang untuk menanyakan tabel secara langsung dan selalu melalui API - DB sprocs /fungsi atau kode.
    2016-01-23 12: 54: 29Z
  2. Ini adalah solusi yang menarik; namun, saya tidak yakin menanyakan kolom induk benar-benar menawarkan keuntungan besar ketika berusaha menemukan anak-anak - itulah sebabnya kami memiliki kolom kiri dan kanan, di tempat pertama.
    2016-03-16 17: 44: 40Z
  3. @ Thomas, ada perbedaan antara children dan descendants. left dan right digunakan untuk menemukan keturunan.
    2016-03-17 06: 25: 33Z

Jika basis data Anda mendukung array, Anda juga dapat menerapkan kolom garis silsilah atau jalur terwujud sebagai array id induk.

Khususnya dengan Postgres Anda kemudian dapat menggunakan operator yang disetel untuk menanyakan 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 juga cukup mudah dikelola.

Saya memiliki penulisan lengkap untuk menggunakan array untuk jalur terwujud jika Anda penasaran.

    
13
2013-05-15 04: 35: 10Z

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 cukup. Namun, mengapa tidak menggunakan alat yang dirancang untuk menangani data hierarkis? Database grafik ideal untuk data hierarkis yang kompleks.

Ketidakefisienan model relasional bersama dengan kompleksitas setiap solusi kode /kueri untuk memetakan grafik /model hierarkis ke model relasional tidak sepadan dengan usaha bila dibandingkan dengan kemudahan yang dapat digunakan oleh solusi database grafik masalah yang sama.

Pertimbangkan Bill of Material sebagai struktur data hierarkis yang 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 : Algoritma traversal grafik sederhana. Jalur yang dapat diterima dapat dikualifikasikan berdasarkan kriteria.

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

Penutupan Transitif : Jelajahi sub-pohon dan jumlahkan bidang yang diminati, mis. "Berapa banyak aluminium dalam sub-assembly? "

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

    
9
2014-09-30 13: 45: 17Z
  1. Jawaban ini akan sangat berguna jika use case diperlihatkan, atau lebih baik lagi dibandingkan, bagaimana cara query database grafik dengan SPARQL misalnya, bukan SQL dalam RDBMS.
    2015-01-06 13: 58: 08Z
  2. SPARQL relevan dengan basis data RDF yang merupakan subkelas dari domain yang lebih besar dari basis data grafik. Saya bekerja dengan InfiniteGraph yang bukan merupakan basis data RDF dan saat ini tidak mendukung SPARQL. InfiniteGraph mendukung beberapa mekanisme kueri yang berbeda: (1) API navigasi grafik untuk mengatur tampilan, filter, kualifikasi jalur dan penangan hasil, (2) bahasa pencocokan pola jalur grafik yang kompleks, dan (3) GREMLIN.
    2015-01-07 16: 05: 57Z

Saya menggunakan PostgreSQL dengan tabel penutupan untuk hierarki saya. Saya punya satu prosedur tersimpan universal untuk seluruh basis data:

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

Lalu untuk setiap tabel tempat 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, DEPTH. Dimungkinkan (dan saya bahkan memberi saran) untuk menyimpan catatan dengan nilai yang sama untuk ANCESTOR dan DESCENDANT, dan nilai nol untuk DEPTH. Ini akan menyederhanakan kueri 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;
    
5
2016-08-01 14: 33: 42Z
sumber ditempatkan sini