問題タブ [transitive-closure-table]

次のテーブルがあります:(私はsqliteを使用しています)

i特定の特定の深さへの閉鎖を見つける必要があります。ただし、SQLite では再帰クエリを使用できません。1 つのクエリを作成しようとしましたが、それを効率的に呼び出して目的の結果を得ることができません。

これは、深さ 2 までのすべてのクロージャーをリストします。しかし、私の特定のユースケースでは、深さ 8 までのクロージャーを許可する必要があります。

このタイプのクエリでは、次のことを試すことができます。

これにより、深さ 3 までのクロージャーが返されますが、選択クエリが冗長になります。閉鎖を見つけるためのより良い方法はありますか?

投稿にネストされたコメントが添付されたアプリをセットアップしました。コメントにクロージャ テーブル方式 (スライド 40)を使用することにしました。これは、ハード ディスク容量がいかに安価であるかと比べて、ツリー構造のクエリと管理がいかに簡単に見えるかという理由によるものです。しかし、問題が発生しています。祖先 ID ではなく、投稿 ID に基づいてツリー パスを取得する方法がわかりません (スライド 49)。

私のデータベース構造は次のようになります。

スライドショーのように、事前にparent_idがわかっている場合は、ツリーを簡単に取得できます:

parent_idただし、事前にわかりません。しか知らないpost_id。データベースのセットアップ方法では、投稿に複数のツリーが関連付けられています。

私の最初の解決策は、次のようなクエリでした。

それは正しいデータを返しますが、そのような入れ子になった SELECT は正しくないように感じます。これを行うより良い方法はありますか？

ありがとう！

【前回の質問】

Reddit のようなコメントをアプリに追加しようとしていますが、データベースの編成にはクロージャー テーブル パターンを使用することにしました。私のアプリデータベースは次のようになります。

投稿

コメント

コメントパス

現在、次のクエリを実行しています。

に基づいてコメントのリストを取得しますpost_id。返されるデータは次のとおりです。

これはツリーを表します:

ただし、返されたデータを Python ツリー構造に変換するのに苦労しています。基本的に、私の目標はこの質問と最終出力（HTML）に関するこの質問ですが、すでに情報を持っているので、再帰SQLステートメントに頼りたくありません。これに似た構造になりたいので、ある種の再帰が必要だと思います：

基本的に辞書のネストされたリストなので、Jinja の再帰 loopを使用してそれらをループできます。誰にもアイデアはありますか？

ありがとう！

編集 2013-04-17

いじって、私は「実用的な」解決策を持っていますが、それは多くの反復を行うので、この質問に対する答えとしてマークしたくありません。私が使用した解決策は次のとおりです。

セット内のすべてのレコードが呼び出されるcomment_setたびに繰り返されるため、理想的ではありません。create_tree()しかし、それは私が今持っている最高のものです。誰にも考えはありますか？

SQL Server データベースで使用されている一連の階層データがあります。データは guid を主キーとして格納され、parentGuid はオブジェクトの直接の親を指す外部キーとして格納されます。WebApi プロジェクトの Entity Framework を介して最も頻繁にデータにアクセスします。状況をもう少し複雑にするために、親に適用されるアクセス許可がそのすべての子孫に適用されるように、この階層に基づいてアクセス許可を管理する必要もあります。私の質問はこれです：

私はあちこちを検索しましたが、この状況を処理するのに最適な方法を判断できません。次のオプションがあることを知っています。

1. Recursive CTEs階層データを処理するために、Common Table Expression (別名 RCTE) を作成できます。これは通常のアクセスでは最も単純なアプローチのようですが、子オブジェクトのアクセス許可レベルを決定するために使用すると遅くなる可能性があるのではないかと心配しています。
2. テーブルにデータ型フィールドを作成し、hierarchyIdSQL Server が提供するGetAncestor()、IsDescendantOf()、などの関数を使用できます。これによりクエリがかなり簡単になるようですが、hierarchyId フィールドを正しく維持するには、かなり複雑な挿入/更新トリガーが必要になるようです。インサートとムーブを通して
3. closure tableすべてのリレーションシップをテーブルに格納する を作成できます。私はそれを次のように想像しています：親列と子列、それぞれの親 - >子関係が表されます。(つまり、1->2 2->3 は、データベースでは 1-2、1-3、2-3 として表されます)。欠点は、挿入、更新、および削除のトリガーがかなり単純であるにもかかわらず必要であり、この方法では大量のレコードが生成されることです。

私はあちこち検索してみましたが、これら3つの方法の間でアドバイスを与えるものは何も見つかりません.

PS私はまた、この問題に対する代替ソリューションを受け入れます

hereのような複数の垂直メニューを探しています。ドロップメニューは必要ありません。私のmysqlデータベースでは、カテゴリに典型的なクロージャテーブル階層（先祖/子孫/深さ）を使用しており、それらをレンダリングしたいと考えています。データベースからすべての親と子を取得するには、次の方法があります。

プレゼンターには次のものがあります。

また、私は Nette Framework を使用しているため、Latte テンプレート エンジンを使用しています。これは Smarty と非常によく似ています。親と子を持つすべてのカテゴリをレンダリングするには、次のようにします。

私の最大の問題は、3 つ以上のレベルのメニューが必要な場合に css スタイルを作成する方法です。が選択されている場合、あるカテゴリはそのサブカテゴリが表示され、別のカテゴリは非表示になります。が選択されると、いくつかのサブカテゴリが彼のサブカテゴリを表示し、別のサブカテゴリが非表示になります。事前に本当にありがとう、私の英語で申し訳ありません。私が何を意味するか知っていることを願っています。

edgeリレーショナル データベース (Firebird) に 2 つのテーブルとnode(隣接リスト モデル)を持つ DAG があります。それらを再帰的にクエリしたいのですが、再帰クエリは非常に非効率的であることがわかりました。そこで、Dong et.al に続いて推移閉包を維持するためのトリガーを実装しようとしました。論文http://homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf。

SELECTは非常に高速になりましたがDELETE、グラフ全体が 1 回の削除でコピーされるため、非常に低速です。さらに悪いことに、同時更新は不可能に思えます。

これを実装するより良い方法はありますか？

編集

いくつかの実験を行い、TC テーブルへの参照カウンターを導入しました。これにより、削除が高速になります。簡単なテスト ケースをいくつか書きましたが、正しいかどうかはわかりません。これは私がこれまでに持っているものです:

これは私自身の考えですが、他の人はすでに TC を実装していると思います。彼らは同じことをしていますか？

いくつかのテスト ケースがありますが、大きなグラフで矛盾が発生する可能性があるかどうかはわかりません。

並行性についてはどうですか。2 つの同時トランザクションがグラフを更新したい場合、このアプローチは失敗すると思いますよね?

編集

コードにいくつかのバグが見つかりました。修正されたバージョンを共有したいと思います。

すばらしい記事を見つけました: http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o。アプローチの異なる興味深い記事や科学論文はありますか?

Closure Table を使用して階層ユーザー グループを表現したことがある人はいますか? オンラインで見つけたすべての例で、ノードの ID は構造内で常に一意です。

この問題を想像してみてください: 私のソフトウェアの従来のセキュリティ管理では、ユーザーのリストとグループのリストがあり、ユーザーが複数のグループに所属でき、各グループが他のグループを含むことができるようにしたいと考えています。 .

ユーザー テーブル:

ID | ユーザータイプ | 名前

(レコードがユーザーを表す場合、UserType は 0、グループ 1 の場合)

テーブル UserHC Id | 親 ID | レベル

「MyID」がすでに存在する場合（主キーが Id、ParentId であるため）、既に知られている挿入する古典的なコマンドを分析すると、うまくいきません。

INSERT INTO UserHC ( [Id], [ParentId], [Level] ) select {MyID} as [Id], [ParentId], [Level] +1 UserHC from [Id] = {myid} UNION ALL SELECT {MyID} , {myId} , 0

* MyId は新しい Users.Id です

複雑な分析を行う前に、同様の要件をすでに持っている人がいるかどうか、またそれをどのように解決したか疑問に思っていました。

ありがとう

最近、MySQL をブラッシュアップしており、階層データを含むデータベースを作成する必要があります。

ツリー形式で表現する必要があるいくつかの異なるタイプのデータがありますが、それを行う方法がわかりません。

たとえば、私には他の人を雇うことができる、または雇われる人がいるとしましょう。これらの人々はそれぞれ機器をチェックアウトすることができ、各機器には名前、説明、および交換部品のリストが必要であり、各交換部品にはコストなどが必要です。

私が目にするクロージャ テーブルのほとんどの例は、フォーラムやスレッド化されたコメントを処理するのにどれだけ優れているかに焦点を当てています。複数のデータ型を持つクロージャ テーブルを作成するにはどうすればよいですか?