6

次のDAGがあります

A --> B

|     |
v     v

C --> D

閉鎖表はこちら

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

およびも削除せずに、パスB > Dを削除する (したがって を削除する)にはどうすればよいでしょうか。A > B > DA > C > DC > D

現在、次のクエリを使用していますが、すべてのノードに親が 1 つしかない場合にのみ機能します。

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

4 に答える 4

1

自然言語では、「Aの子孫でもあるB以外にDの親がいない場合は、Dに対する祖先-子孫の反発を削除します」となります。あれは正しいですか？

（編集：いいえ、それは正しくありません。Dへの反発を削除する必要があるだけでなく、Dのすべての子孫への反発も削除する必要があります。したがって、その基準は無効です...）

私の暫定SQLは次のようになります。

DELETE a
FROM Closure AS a
    INNER JOIN Closure AS b ON a.Descendant = b.Descendant
WHERE
    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)

（クエリを間違えた場合、または非標準の機能を使用した場合は申し訳ありませんが、実際にはその経験はありません。しかし、私の自然言語の説明は、クエリで実際に何を行う必要があるかについての洞察を与えるはずです）

更新：考え直してみると、私のクエリがすべての場合に機能するとは限りません。このことを考慮：

A --> B --> D --> E --> F
  1. FはDの子孫です（True）
  2. EはFの親です（True）
  3. EはBではありません（True）
  4. AはEの祖先ではありません（False）

したがって、A >> F削除する必要がある場合でも、削除されません。申し訳ありませんが、仕方がありませんでしたが、それは1つのクエリに収まらないほど大きな問題のようです。最初にアルゴリズムソリューションを探してから、それをどのように実装できるかを確認することをお勧めします。

于 2012-03-09T23:31:02.477 に答える
0

深さを追跡し、同時に複数の親を許可することはおそらく可能ですが、特にソリューションに重複ペアが含まれる場合は、コードの匂いがします。トーマスの答えはその問題を概説しています。

複数の親が許可されている場合にノードのリンクを解除することに焦点を当てるために、質問を少し単純化します。これは、それ自体が十分に難しい問題だからです。深度列を完全に破棄し、重複するペアがないと仮定しています。

D の子を考慮に入れる必要があり、すぐに複雑になります。私たちが持っているとしましょう：

A --> B
       
|     |
v     v

C --> D --> E

D を B からリンク解除したいということは、E と B の間のリンクも削除する必要があることを意味します。

A --> B --> C
             
      |     |
      v     v

      D --> E < -- G
      
      |
      V

H --> F

この場合、B > D を切断すると、B と E のリンクを解除したくなくなります。これは、E がまだ C を介して B にリンクされているためです。しかし、B から F を切断したいのです。

その 2 番目の例を使用して、以下のソリューションを説明します。この例では、D には親が 1 つしかないことはわかっていますが、D に複数の親がある場合でも完全に機能します。この方法でいくつかのエッジ ケースをより簡単に示すことができるので、このようにしています。

テーブルは次のようになります。

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

クエリ 1: D を含む D のすべての子孫を取得する

SELECT `Descendant`
FROM `Closure`
WHERE `Ancestor` = @Node

これは以下を返します:D, E, F

クエリ 2: B を含む B のすべての祖先を取得する

SELECT `Ancestor`
FROM `Closure`
WHERE `Descendant` = @ParentNode

これは以下を返します:A, B

クエリ 3a: クエリ 1 または 2 に表示されない、クエリ 1 のアイテムのすべての祖先を取得する

SELECT DISTINCT `Ancestor`
FROM `Closure`
WHERE `Descendant` IN (@Query1)
AND `Ancestor` NOT IN (@Query1)
AND `Ancestor` NOT IN (@Query2)

これは以下を返します:C, G, H

ここでの目標は、E と F のすべての親を取得して、チェーンをさらに上に再接続することです。

クエリ 3b: これはクエリ 3a とまったく同じですが、先祖と子孫の両方が返される点が異なります。

SELECT DISTINCT `Ancestor`, `Descendant`
[ ... ]

これは以下を返します:(C, E), (G, E), (H, F)

これは後で必要になります。

クエリ 4: クエリ 3a の結果をフィルタリングして、チェーンのさらに上に再接続するノードに絞り込む

SELECT `Ancestor`,`Descendant`
FROM `Closure`
WHERE `Descendant` IN (@Query3a)
AND (`Ancestor` IN (@Query2) OR `Ancestor` = `Descendant`))

これは以下を返します:(A, C), (B, C), (C, C)

これで、リンクを解除してはならない C のすべての親への参照ができました。F の親へのリンクがないことに注意してください。これは、F が B および A に接続されていないためです (リンクを解除する) D を介する場合を除きます。

クエリ 5: クエリ 3b の結果をクエリ 1 と 4 の間のブリッジとして使用して、保持する必要があるペアを構築します。

SELECT `Query4`.`ancestor`,`Query3b`.`descendant`
FROM (@Query3b) as `Query3b`
LEFT JOIN (@Query4) as `Query4`
WHERE `Query3b`.`descendant` IN (@Query1)

これは以下を返します:(A, E), (B, E)

クエリ 6: クエリ 5 によって返されたすべてのペアを除外することを除いて、ノードとその子を孤立させるための通常のクエリを実行します。

DELETE FROM `Closure`
WHERE `Descendant` IN (@Query1)
AND `Ancestor` IN (@Query2)
AND (`Ancestor`, `Descendant`) NOT IN (@Query5)

この操作の後、次のリンクを削除します。

| Ancestor | Descendant |
-------------------------
| A        | D          |
| A        | F          |
| B        | D          |
| B        | F          |

D と F の両方が正しくリンク解除され、E は A と B への接続を正しく保持し、次のようになります。

A --> B --> C
             
            |
            v

      D --> E < -- G
      
      |
      V

H --> F

何か見逃したことがあれば教えてください！私は今日この問題を自分で解決しましたが、時間が経つにつれて、より多くのエッジケースに遭遇する可能性があります. 見つけたら、この回答を更新します。

于 2022-02-01T23:42:00.630 に答える