Bagaimana cara mewakili grafik terarah dengan banyak orang tua?

http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html menyediakan algoritme untuk menyisipkan dan menghapus dari Tabel Penutupan.

Saya ingin memodelkan struktur data yang serupa, kecuali bahwa node mungkin memiliki banyak orang tua.

Diberikan:

Jika kami menghapus [B, C]saya berharap akan berakhir dengan:

dan jika kita menghapus simpul Bsaya berharap berakhir dengan:

Namun, jika Anda menggunakan algoritme penulis untuk menghapus tautan atau simpul, Anda akan melihat bahwa itu menandai [D, C, 1]untuk dihapus, yang tidak diinginkan.

Apa yang saya coba sejauh ini

Saya telah mencoba mengadaptasi struktur data asli dengan menambahkan referenceskolom yang menunjukkan berapa banyak cara untuk melakukan perjalanan antara dua node. Dalam contoh di atas, Anda dapat melakukan perjalanan dari Ake Cbaik melalui Batau melalui D. Idenya adalah ketika Bdihapus, jalur dari Ake Cdisimpan dan jumlah referensi berkurang dari 2 menjadi 1. Itu bagus secara teori, tapi saya tidak tahu bagaimana cara agar implementasi berjalan dan sekarang saya bertanya-tanya apakah itu mungkin (struktur data mungkin tidak mengandung cukup informasi untuk mencari tahu baris mana yang harus dihapus).

Apa yang saya tanyakan

Bagaimana Anda mengadaptasi Tabel Penutupan untuk mendukung banyak orang tua? Struktur data alternatif apa yang akan Anda rekomendasikan? https://stackoverflow.com/q/4048151/14731 berisi daftar exaustive dari struktur data seperti itu, tetapi tidak jelas mana yang mendukung (atau yang terbaik untuk) banyak orang tua.

Biasanya membuat tabel node dan tabel hubungan. Grafik yang diarahkan tidak benar-benar hierarkis dan mereka dapat memiliki loop yang membuat kueri lebih sulit. Tetapi jika Anda menganggap DAG sebagai pohon umum (Yaitu pohon yang memungkinkan banyak orang tua tetapi masih sangat hierarkis) dan grafik terarah sebagai DAG umum (yaitu seperti DAG tetapi tidak sepenuhnya hierarkis) segalanya menjadi lebih mudah.

Jadi untuk solusi PostgreSQL yang sangat sederhana, kami mungkin melakukan sesuatu seperti:

CREATE TABLE node (
    id serial primary key,
    payload jsonb not null
);

CREATE TABLE relationship (
    id serial primary key,
    relationship_type text not null,
    from_node int references node(id) not null,
    to_node int references node(id) not null,
    payload jsonb not null
);

Kemudian Anda dapat menanyakan sesuatu seperti ini:

with recursive dg as (
    select n.id as node_id, null::Int as parent, array[n.id] as path
      from node n
    union all
    select to_node, from_node, path || to_node
      FROM relationship
      JOIN dg on dg.node_id = from_node AND NOT from_node = ANY(path)
)
select * from dg;