¿Cómo representar un gráfico dirigido con varios padres?

http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html proporciona un algoritmo para insertar y eliminar de una tabla de cierre.

Me gustaría modelar una estructura de datos similar, excepto que los nodos pueden tener múltiples padres.

Dado:

Si eliminamos [B, C], espero terminar con:

y si eliminamos el nodo B, espero terminar con:

Sin embargo, si utiliza el algoritmo del autor para eliminar enlaces o nodos, notará que se etiqueta [D, C, 1]para su eliminación, lo que no es deseable.

Lo que he probado hasta ahora

Intenté adaptar la estructura de datos original agregando una referencescolumna que indica cuántas formas hay de viajar entre dos nodos. En el ejemplo anterior, puede viajar de Aa Ctravés Bo a través D. La idea habría sido que, cuando Bse elimina, se mantiene el camino de Aa Cy el recuento de referencias disminuye de 2 a 1. Fue agradable en teoría, pero no pude averiguar cómo hacer que la implementación funcione y ahora me pregunto si es posible (la estructura de datos puede no contener suficiente información para determinar qué filas eliminar).

Lo que pregunto

¿Cómo adaptaría las tablas de cierre para apoyar a varios padres? ¿Qué estructuras de datos alternativas recomendarías? https://stackoverflow.com/q/4048151/14731 contiene una lista exhaustiva de tales estructuras de datos, pero no está claro cuáles admiten (o son mejores para) varios padres.

Por lo general, crea una tabla de nodos y una tabla de relaciones. Los gráficos dirigidos no son realmente jerárquicos y pueden tener bucles, lo que dificulta las consultas. Pero si piensa en un DAG como un árbol generalizado (es decir, un árbol que permite múltiples padres pero que sigue siendo estrictamente jerárquico) y un gráfico dirigido como un DAG generalizado (es decir, como un DAG pero no estrictamente jerárquico) las cosas se vuelven más fáciles.

Entonces, para una solución PostgreSQL muy simple, podríamos hacer algo como:

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

Entonces puedes consultar algo como esto:

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;