Можем ли мы представить DAG (ориентированный ациклический граф) с помощью ltree PostgreSQL?

Я хочу хранить иерархические данные в базе данных PostgreSQL. Я нашел расширение ltree, но оно используется для хранения древовидных данных, т.е. может быть только один родительский узел. Есть ли способ настроить его для хранения нескольких родительских узлов?


postgresql directed-acyclic-graphs ltree
person semicolon    schedule 02.06.2020    source источник
comment
Таблица с двумя столбцами parent_id, child_id может представлять его, но не предотвратит циклы. Является ли это полезным представлением, зависит от того, насколько велик набор данных и что вам нужно с ним делать.   -  person AdamKG    schedule 02.06.2020
comment
@AdamKG у данных не будет цикла, и могут быть миллионы узлов. Но максимальное количество детей для узла может составлять около 100 тыс.   -  person semicolon    schedule 03.06.2020

Ответы (1)


arrow_upward
2
arrow_downward

Да, это можно сделать с помощью расширения ltree, используя два таблицы: одна для ваших узлов, а другая для ваших путей. У Bustawin есть отличная статья о том, как работать с группами обеспечения доступности баз данных, использующими это расширение с этой стратегией.

Чтобы узел имел несколько родителей, необходимо, чтобы мы определили более одного пути ltree для такого узла, который ведет от каждого родителя. Скажем, у нас есть DAG, который образует ромб между узлами A, B, C и D:

A -> B
B -> D
A -> C
C -> D

Используя расширение, вы должны иметь узел D, связанный с двумя путями, A.B.D и A.C.D. Оба запроса должны возвращать узел D

SELECT * FROM nodes
JOIN paths ON paths.node_id = nodes.id
WHERE paths.ltree_path ~ "A.B.*{1}"

SELECT * FROM nodes
JOIN paths ON paths.node_id = nodes.id
WHERE paths.ltree_path ~ "A.C.*{1}"
person Magmagan    schedule 22.09.2020