Moving in a Closing Table with Multiple Parents

I have the following DAG

A --> B

|     |
v     v

C --> D


Here is the closure table

| Ancestor | Descendant | Depth |
| A        | A          | 0     |
| A        | B          | 1     |
| A        | C          | 1     |
| A        | D          | 2     |
| A        | D          | 2     |
| B        | B          | 0     |
| B        | D          | 1     |
| C        | C          | 0     |
| C        | D          | 1     |
| D        | D          | 0     |


How can I delete the path B > D

(by deleting that way A > B > D

) without deleting also A > C > D

and C > D


I am currently using the following query, but it only works when each node only has 1 parent.

WHERE `Descendant` IN (SELECT `Descendant` FROM `Closure` WHERE `Ancestor`=@Node)
AND `Ancestor` NOT IN (SELECT `Descendant` FROM `Closure` WHERE `Ancestor`=@Node);



source to share

2 answers

First, I believe there is a duplicate entry in your table. (A,D)

appears twice. Secondly, after removing the edge (B,D)

, the following paths should remain:

  • The self-maps the Node: (A,A)

    , (B,B)

    , (C,C)


  • (A,B)

  • (A,C)

  • (A,D)

    (via C)

Thus, to remove an edge (B,D)

in this example, all it takes is to remove one line:

Delete MyTable 
Where Ancestor = 'B'
    And Descendant = 'D'


The snapping table still reflects only the relationship between the two nodes. The peculiarity is that it displays all indirect relationships effectively as a direct relationship. Edge (B,D)

just says you can get from B

to D

. Only this line says nothing about how you got to B

, and it says nothing about how many nodes it took to get from B

to D

; it just says you can get from B

to D

. Thus, for A > B > D

there is no edge. Chances are all that was captured is what you can get from A

to B

and from A

to D

, which is still correct even if the rib is (B,D)




In natural language this would be: "Remove child-child attachment to D if there is no parent of D other than B, which is also a child of A." It is right?

(Edit: no, this is not correct, it is necessary to remove not only the relashionships in D, but also relashionships for each descendant of D. So these criteria are not valid ...)

My preliminary SQL would then be:

FROM Closure AS a
    INNER JOIN Closure AS b ON a.Descendant = b.Descendant
    a.Descendant IN (SELECT Descendant FROM Closure WHERE Ancestor = {Child}) AND
    b.Depth = 1 AND
    b.Ancestor != {Parent} AND
    a.Ancestor NOT IN (SELECT Ancestor FROM Closure WHERE Descendant = b.Ancestor)


(Sorry if I made a mistake in the request or used non-standard features - I am not really experiencing this. But my natural language description should give an idea of ​​what actually needs to be done on request)

Update: Second, I don't believe my query will work for all cases. Consider this:

A --> B --> D --> E --> F


  • F is a descendant of D (True)
  • E is the parent of F (True)
  • E not B (True)
  • A is not an ancestor of E (False)

Thus, A >> F

it will not be deleted, even if necessary. Sorry I couldn't help but the problem seems too big to fit into a single request. I would like to find an algorithmic solution first and then see how this can be implemented in your case.



All Articles