8

http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html provides an algorithm for inserting and deleting from a Closure Table.

I'd like to model a similar data structure, except that nodes may have multiple parents.

Given:

Graph #1

If we remove [B, C] I expect to end up with:

Graph #2

and if we remove node B I expect to end up with:

Graph #3

However, if you use the author's algorithm for removing links or nodes you will notice that it tags [D, C, 1] for deletion, which is undesirable.

What I've tried so far

I have tried adapting the original data structure by adding a references column that indicates how many ways there are to travel between two nodes. In the above example, you can travel from A to C either through B or through D. The idea would have been that when B gets removed, the path from A to C gets kept and the reference count decreases from 2 to 1. It was nice in theory, but I couldn't figure out how to get the implementation working and now I wonder if it's at all possible (the data structure might not contain enough information to figure out which rows to remove).

What I'm asking

How would you adapt Closure Tables to support multiple parents? What alternative data structures would you recommend? https://stackoverflow.com/q/4048151/14731 contains an exaustive list of such data structures, but it's not clear which ones support (or are best for) multiple parents.

  • So, what have you tried? And what is the references column? – ypercubeᵀᴹ Oct 2 '14 at 18:41
  • I don't believe one would adapt closure tables in your scenario. Closure tables are good for many tree based applications, but this question alludes to a much less restrictive type of DAG (Directed Acyclic Graph). This is a topic which might be suitable for a Masters thesis and like so many things when it comes to databases, an optimal solution will heavily rely on your exact, specific use case. This or this might help you get started. – Avarkx Oct 3 '14 at 14:41
  • Which db software? – Neil McGuigan Oct 3 '14 at 18:20
  • @NeilMcGuigan, H2 and PostgreSQL though obviously I prefer a DB-agnostic solution. – Gili Oct 3 '14 at 18:22
3

Usually create a nodes table and a relationships table. Directed graphs are't really hierarchical and they can have loops which makes querying harder. But if you think of a DAG as being a generalised tree (I.e. a tree that allows multiple parents but is still strictly hierarchical) and a directed graph as being a generalised DAG (i.e. like a DAG but not strictly hierarchical) things get easier.

So for a very simple, PostgreSQL solution we might do something like:

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

Then you can query something like this:

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;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.