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.
If we remove
[B, C] I expect to end up with:
and if we remove node
B I expect to end up with:
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
C either through
B or through
D. The idea would have been that when
B gets removed, the path from
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.