sql - dbエントリ間のサイクルを見つける方法は？

Question

次のようなデータベーステーブルがあります。

列1| 2列目

x | Y

y | z

z | バツ

つまり、基本的にx-> y->z->xです。

次に、DBでそのようなエントリを検出する必要があります。1つの解決策は、これらのエントリを取得してメモリ内にグラフを作成し、サイクル検出アルゴリズムを使用してサイクルを検出することです。可能であれば、SQLクエリを使用して実行したいと思います。

Answer 1

SQLiteは再帰クエリをサポートしていないため、自己結合を使用して固定長のサイクルを検出するのが最善の方法です。任意の長さのサイクルを検出することはできません。

これは、質問で示した例のように、長さ2のサイクルを見つける結合の例です。

SELECT ...
FROM t AS t0
JOIN t AS t1 ON t0.column2 = t1.column1
JOIN t AS t2 ON t1.column2 = t2.column1
WHERE t2.column2 = t0.column1

---

コメントを再確認してください。

任意の長さのサイクルを検出する必要がある場合、私が提案できるのは、直接リンク以上のものを格納する必要があるということだけです。また、推移閉包、つまりグラフのすべてのパスを保存する必要があります。これが、この検索を効率的にするための最良の方法です。もちろん、これを行うにはさらに多くのストレージスペースが必要ですが、トレードオフがあります。そして、それはあなたが思っているよりも少ない余分なスペースを取ります。

木の推移閉包設計を行いましたが、非巡回グラフは行いませんでした。フラットテーブルをツリーに解析するための最も効率的でエレガントな方法は何ですか？に対する私の答えを参照してください。または、 SQLを使用した階層データのプレゼンテーションモデル。