While tracking depth and allowing multiple parents at the same time is probably possible, I get a code smell from it, especially when the solution involves having duplicates pairs. Thomas' answer outlines that issue.
I'm going to simplify the question a bit to just focus on unlinking a node when multiple parents are allowed, because it's a tricky enough problem on its own. I'm discarding the depth column entirely and assuming there are no duplicate pairs.
You have to take into account children of D, which gets complicated fast. Say we have:
A --> B
| |
v v
C --> D --> E
We want to unlink D from B, which means we also have to remove links between E and B. But what if they're connected like this:
A --> B --> C
| |
v v
D --> E < -- G
|
V
H --> F
In this case if we disconnect B > D, we don't want to unlink B and E anymore, because E is still linked to B through C. But we do want to disconnect F from B.
I'll go through my solution below using that second example. I know that D only has one parent in this example, but it still works perfectly if D has multiple parents; I can more easily demonstrate some of the edge cases this way so that's why I'm doing it like this.
Here's what the table would look like:
| Ancestor | Descendant |
-------------------------
| A | A |
| A | B |
| A | C |
| A | D |
| A | E |
| A | F |
| B | B |
| B | C |
| B | D |
| B | E |
| B | F |
| C | C |
| C | E |
| D | D |
| D | E |
| D | F |
| E | E |
| F | F |
| G | G |
| G | E |
| H | H |
| H | F |
Query 1: Get all descendants of D, including D
SELECT `Descendant`
FROM `Closure`
WHERE `Ancestor` = @Node
This will return: D, E, F
Query 2: Get all ancestors of B, including B
SELECT `Ancestor`
FROM `Closure`
WHERE `Descendant` = @ParentNode
This will return: A, B
Query 3a: Get all ancestors of the items in Query 1 that do not appear in Query 1 or 2
SELECT DISTINCT `Ancestor`
FROM `Closure`
WHERE `Descendant` IN (@Query1)
AND `Ancestor` NOT IN (@Query1)
AND `Ancestor` NOT IN (@Query2)
This will return: C, G, H
The goal here is to get all parents of E and F that may reconnect farther up the chain.
Query 3b: this is exactly the same as Query 3a, except it returns both ancestors and descendants
SELECT DISTINCT `Ancestor`, `Descendant`
[ ... ]
This will return: (C, E), (G, E), (H, F)
We'll need this later.
Query 4: Filter results of Query 3a down to nodes that reconnect farther up the chain
SELECT `Ancestor`,`Descendant`
FROM `Closure`
WHERE `Descendant` IN (@Query3a)
AND (`Ancestor` IN (@Query2) OR `Ancestor` = `Descendant`))
This will return: (A, C), (B, C), (C, C)
We now have references to all parents of C that should not be unlinked. Note that we have no links to parents of F. That's because F is not connected to B and A except through D (which we're unlinking).
Query 5: Construct the pairs that should be kept, using the results of Query 3b as a bridge between Queries 1 and 4
SELECT `Query4`.`ancestor`,`Query3b`.`descendant`
FROM (@Query3b) as `Query3b`
LEFT JOIN (@Query4) as `Query4`
WHERE `Query3b`.`descendant` IN (@Query1)
This will return: (A, E), (B, E)
Query 6: Run the regular query for orphaning a node and its children, except exclude all pairs returned by Query 5
DELETE FROM `Closure`
WHERE `Descendant` IN (@Query1)
AND `Ancestor` IN (@Query2)
AND (`Ancestor`, `Descendant`) NOT IN (@Query5)
After this operation, we will have removed the following links:
| Ancestor | Descendant |
-------------------------
| A | D |
| A | F |
| B | D |
| B | F |
Both D and F are correctly unlinked, and E correctly retains its connections to A and B, leaving:
A --> B --> C
|
v
D --> E < -- G
|
V
H --> F
Let me know if I've missed anything! I just solved this problem myself today and I may run into more edge cases as time goes on. If I find any I'll update this answer.
