問題タブ [transitive-closure-table]

いくつかの階層データを持つ新しいプロジェクトを開始しており、現在、それをデータベースに保存するためのすべてのオプションを検討しています。

再帰クエリを許可するPostgreSQLを使用しています。また、クロージャーテーブルなどのリレーショナルデータベースのデザインパターンを調べ、neo4jなどのグラフデータベースソリューションを調べました。

私はそれらのオプションの間で決定するのが難しいと感じています。例：私のRDBMSで再帰クエリが許可されている場合でも、クロージャテーブルを使用することは理にかなっていますか？それは、保守性とパフォーマンスの点でグラフデータベースソリューションとどのように比較されますか？

ご意見・ご感想をいただければ幸いです！

MySQLに階層データを格納するシステムを実装しようとしています。スライド番号40から始まるBillKarwinによって説明されているように、ここに実装されているシステムを使用することにしました。テーブルが自動的に維持されるようにデータベースをセットアップしようとしています。EntryPaths

更新：データベースを更新してSQLを作成しました。更新のために1/2が機能していると思います。データベースを実行した後、SQLを作成して次のことを試してください

まず、このエントリがどのように見えるかを確認します

そしてこれはどのように見えるか

表示された最初のエントリには複数の子があり、2番目のエントリには子がありません。次の更新を実行して、「CollegeYears」ノード（およびその子）の親を変更します。John Doe

上記の2つのselectステートメントを再実行すると、アイテムが削除されJane Doeたが、期待どおりに追加されていないことがわかりますJohn Doe。トリガーに問題がありますLibrary_Updateが、修正しようとするアイデアが不足しています。

データベースは、サンプルデータを使用してSQLを作成します。

Closure Table メソッドを使用して階層データを保持する MySQL データベースがあります。簡単なサンプル データベース作成スクリプトが質問の後に続きます。現時点での問題は、データベースからデータを正しい順序で引き出すにはどうすればよいですか? 現在、次の選択ステートメントを使用しています。

正しい情報を引き出しますが、正しい順序ではありません。

サンプル データを使用したサンプル データベース作成スクリプト。

次のDAGがあります

閉鎖表はこちら

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

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

次の問題があります: ソース ノード ( node_s ) からターゲット ノード ( node_t ) へのすべての可能なパスを検出しようとしています。

グラフ エッジを含む元のテーブルの形式は単純です。ノード_x | ノード_y | 強度 | ここで、"node_x" -> "node_y" は、エッジの強度が "重み" である直接エッジです。

パスの探索中の任意の時点で、その子の中のノードがターゲットnode_tを持っていることを発見した場合、このパスを記録し、このノードからのパスの探索を停止します。それ以外の場合は、探索を続行します。

簡単な解決策は、グラフの推移閉包を構築する PostgreSQL の再帰 CTE を使用することでした。

上記のコードは、ソース ノードnode_sから可能なすべてのパスを検出します。推移閉包の構築後にのみ、ソース ノードからターゲット ノードへの必要なパスの行を選択できます (最後の SELECT ステートメントを参照)。

例：

best_path テーブルには次のデータがあります。

クエリ:

ソース ノード = 1 からターゲット ノード = 4 へのパスを見つける

結果：

これは私が必要とするものではありません。ノード 2 からノード 4 (ターゲット) への直接エッジが既にあるため、パス 1.2.5.、1.2.4.8.、1.2.4.9.、1.2.5.10.、1.2.5.11. は必要ありません。ノード 2 の場合、2 から 4 へのパスが検出された時点で停止する必要があります。

要約すると、ノードが既にターゲット ノードへの直接エッジを持っている場合、ノードのパスを発見したくありません。これは、CTE の再帰的な用語で、次のような条件が必要であることを意味します。疑似コードは次のとおりです。

ソース ノード = 1 からターゲット ノード = 4 へのパスを検索するクエリの結果として、次のようにしたいと考えています。

よろしくお願いします。

私はすでに多くの方法を試しました。たとえば、FROM/WHERE 句の条件、CTE を関数に渡そうとしましたが、成功しませんでした。

任意の提案をいただければ幸いです。

私は自分が望むものを達成する独自の再帰関数を持っていますが、膨大な量のデータでは非常に遅くなります。PostgreSQL の CTE は最適化されているようですので、もう少し掘り下げてみたいと思います。

これは私が使用しているクラスです：https ：//gist.github.com/2174233

2つのテーブルがあります。1つのテーブルにはユーザーが含まれ、もう1つのテーブルにはクロージャが含まれます。

メソッドを使用get_children()すると（たとえば、ルートまたは別の親から）、階層の最初のレベルのみが表示されます。どの値をlvl 列に保存する必要がありますか？

これは私が持っているクロージャーテーブルの定義です：

クロージャテーブルに保存するデータの例を次に示します。

最後はlvl列ですが、どの値がそこにあるのかわかりません。使い方を教えてください。

私が保存しなければならない構造には3つのレベルがあります：ルート->20ノード->26ノードですが、それは私に20ノードである最初のレベルの子だけを与えます。

MySQL でクロージャ テーブルを使用して階層をモデル化するときに、兄弟ノードの名前に一意の制約を適用する方法を考えています。

これは私のスキーマです:

このスキーマでは、spacesテーブルに一意の制約を使用して、同じ名前の兄弟がないことを確認しています。

このアプローチの欠点は、space_pathsテーブルにカプセル化された階層メタデータが非正規化されることです。parentつまり、テーブル内のフィールドとspacesテーブル内のパスの一貫性を手動で管理する必要があるということですspace_paths。

非正規化することなく、データベースが兄弟間で一意の名前の制約を適用するようにスキーマを再設計する方法はありますか?

階層データのクエリについてサポートが必要です。これは単一の単純なテーブルであり、ルートエントリの場合はnullになる可能性がありますparent_id。id

テーブル内の各レコードについて、最大IDを持つ最も深い子を見つける必要があります。レコードに子がない場合は、独自のIDを返す必要があります。私は自分で試しましたがSTART WITH A.id = B.id、AとBがサブクエリである場合は使用できませんでした。これは、Oracleがそのような結合を許可していないようです。

サンプルデータは次のとおりです。

およびサンプル結果

私はしばらくの間、このクロージャ テーブルを使ってぐるぐる回っています。私が抱えている問題は、子孫の2番目の出現にあります。複数の親カテゴリに表示されるサブカテゴリのインスタンスがあります。簡単にするために、この例に戻りました。

次のクエリを使用して、目的の結果を得ることができます。

結果：

しかし、別の子、たとえば既に存在する子を追加する場合、leafnodes を roottree -> lastbranch -> lastleaf の子にしたい

2 つの新しいレコード (6-5) と (7-5) をクロージャー テーブルに挿入します。

その後、すべての地獄が解き放たれます。考えられることはすべて試しましたが、どこにも行きません。

これが、クロージャーテーブルメソッドをテストして作成したテーブルです。

PHPを使用してこの単純なツリーを作成しようとしています。テーブルを作成するのに十分なデータがないようです。たとえば、純粋にparentId = 6を見ると、次のようになります。

パート8とパート10はパート7または9の下に存在することはわかっていますが、どちらも存在しません。パート10は3ノードと4ノードの両方の深さに存在することがわかっていますが、どこにありますか？

表内の他のデータを見ると、次のようになっているはずです。

クロージャテーブルの利点の1つは、再帰クエリの必要がないことだと思いましたか？私が間違っていることを説明するのを手伝ってもらえますか？

編集：明確にするために、これはマッピングテーブルです。「parts」と呼ばれる別のテーブルがあり、「closure」テーブルのparentId列とchildId列の両方に相関するpart_idという列があります。上記の表の「id」列（閉鎖）は、主キーを維持するためだけのものです。本当に必要ではありません。このクロージャテーブルを作成するために使用した方法については、次の記事で説明しています。http: //dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html

EDIT2：2つと3つのホップを持つことができます。アイテムに名前を付けることで簡単に説明します。

ナットはボルトの一部です。ボルトとナットのコンボは、自転車内と自転車の一部であるギア内に直接存在します。

使用する方法に関連して、隣接、エッジ、列挙型パス、クロージャー、DAGS（ネットワーク）、および入れ子集合モデルを調べました。私はまだ何が何であるかを解明しようとしていますが、これは非常に複雑なコンポーネントデータベースであり、複数の親があり、サブツリーへの変更は他のツリーを介して伝播する必要があります。さらに重要なのは、データベーススペースと入力中のクエリ時間を犠牲にしても、一般的な使用中の再帰を避けたい挿入、削除、およびツリービューがあることです。