問題タブ [nested-sets]

ネストされたセット モデルとは、ここで説明されていることを意味します。

ユーザー定義の階層に「カテゴリ」を格納するための新しいシステムを構築する必要があります (より適切な言葉は思いつきません)。ネストされたセット モデルは、書き込みではなく読み取り用に最適化されているため、それを使用することにしました。残念ながら、ネストされたセットの調査とテスト中に、ソートされたノードを持つ階層ツリーをどのように表示するかという問題に遭遇しました。たとえば、階層がある場合:

次のように表示されるように並べ替えます。

捏造が研究の前に現れることに注意してください。

とにかく、長い検索の結果、「ツリーを多次元配列に格納してソートする」、「ツリーを再ソートし、ネストされたセットモデルにシリアル化する」などの回答が表示されました(言い換えています...)。いずれにせよ、最初の解決策は RAM と CPU の恐ろしい浪費であり、どちらも非常に有限のリソースです。2 番目の解決策は、多くの面倒なコードのように見えます。

とにかく、（ネストされたセットモデルを使用して）方法を理解することができました：

1. SQL で新しいツリーを開始する
2. ツリー内の別のノードの子としてノードを挿入します
3. ツリー内の兄弟ノードの後に​​ノードを挿入します
4. SQL から階層構造を持つツリー全体をプルする
5. 深さの制限の有無にかかわらず、階層内の特定のノード (ルートを含む) からサブツリーをプルします
6. ツリー内の任意のノードの親を見つける

したがって、#5 と #6 を使用して、必要な並べ替えを行うことができ、並べ替えられた順序でツリーを再構築するためにも使用できると考えました。

しかし、私が学んだことをすべて見てきたので、#3、#5、および #6 を一緒に使用して、ソートされた挿入を実行できることがわかりました。ソートされた挿入を行った場合、常にソートされます。ただし、並べ替え基準を変更したり、別の並べ替え順序が必要な場合は、振り出しに戻ります。

これは、ネストされたセット モデルの制限でしょうか? その使用は、出力のクエリソートを阻害しますか?

必要なすべての関数を備えた PHP (MYSQL を使用) のネストされたセット クラスを探しています。例えば：

createLeftNode、createRightNode、createRootNode、createSubNode、deleteNode、およびmoveTree。左に 1 つ、右に 1 つ、上に 1 つ、下に 1 つだけでなく、別の木の中の木の一部。

ありがとう！

ネストされたセットを使用してツリーを DB に格納しています。テーブルのフィールドは、id、lft、rgt、および name です。

ノード ID を指定すると、それ自体がリーフ ノードである直接の子 (孫ではない) をすべて見つける必要があります。

階層内にアイテムのリストがあり、このリストを解析してオブジェクトの実際の階層にしようとしています。このリストを保存/反復するために、変更された事前注文ツリー トラバーサルを使用しているため、すべての子を含むツリーのサブセットが「左」の値で並べられています。

たとえば、次のツリーがあるとします。

• アイテムA
  • アイテムA.1
  • アイテムA.2
    • アイテムA.2.2
• アイテムB
  • 項目 B.1
• アイテムC

リストを取得します：

• アイテムA、アイテムA.1、アイテムA.2、アイテムA.2.2、アイテムB、アイテムB.1、アイテムC

(これは、変更された予約注文ツリーの設定の「左」の値の順です)。

私がやりたいことは、これをツリーの実際の構造を含むオブジェクトに解析することです。

フラット リストは TreeObjects のリストとして返され、各 TreeObject には ID、ParentID、Left、Right のプロパティがあります。私が探しているのは関数です：

フラットリストを受け取り、ネストされたリストを返します。

言い換えると：

私はこれを行う方法に途方に暮れています-親を追跡し、より大きなジャンプに対処できるようにします（たとえば、アイテムA.2.2->アイテムB）。

編集:ここでは、ブルートフォース以外のソリューションを探しています(たとえば、トップレベルの親だけが残るまで、アイテムを子ノードに移動したり、数回ループしたりしません)。一度ループして、必要に応じてアイテムを配置できるエレガントな方法があると思います。

覚えておいてください、それらは常に階層的な順序になっているため (私は MPTT を使用しているため)、特定のアイテムは常に前のアイテムの子または兄弟になるか、少なくとも前のアイテムと親を共有します。ツリーの他の場所に来ることは決してありません。

Joe Celko のネストされたセット (変更された事前注文トラバーサル) の既知の制限の中には、ツリーが大きなサイズに成長するにつれてパフォーマンスが著しく低下するというものがあります。

Vadim Tropashko はネストされた間隔を提案し、この論文で例と理論の説明を提供します: http://arxiv.org/html/cs.DB/0401014

これは実行可能なソリューションですか?ネイティブ DB レイヤーから抽象化された (任意の言語での) 実行可能な例はありますか?

私のウェブサイト用にスレッド化されたコメントシステムを構築していて、問題に遭遇しました...

ID フィールドと親 ID フィールドを持つリスト PULLED FROM A DATABASE があります。親 ID フィールドは null にすることができますが、ID フィールドが null になることはありません。

これはスレッド化されたコメント システムなので、ID が一番上になるようにリストを整理しますが、親 ID が存在する場合は ID の下に挿入されます。そして、これも無限に続くことができます。そのため、2 番目のレベルにも ID があり、その ID の親 ID を持つアイテムをその下に挿入したいと考えています。

例えば：

---1. 何とか

--------2. 何とか何とか-> ParentID=1

----------3. 何とか何とか->親ID = 2

-------------- 4. 何とか何とか ->parentID=3

----------- 3.何とか何とか -> 親 ID=2

--------2. 何とか何とか->親ID = 1

私はあなたがポイントを得ると思います。

だからここに私がこれまで持っているものがあります...

途中でソートされているように見えますが、実際にはそうではありません... ThreadID はもちろん、どれだけ右に植えられるかです。

階層内に一連のオブジェクトがあります。最上位の「ルート」ノードがあり、子ノードがあり、子ノードなどがあります。ネストされたセットモデルを使用して、この構造をDBに保存しようとしています。各ノードの各「側」は定義するために番号が付けられていますMySQL での階層データの管理のように、階層:

_{(ソース: mysql.com )}

私の問題は、左右の値を計算することです。私は通常、RecursiveIteratorIterator を使用して階層を反復処理しますが、参照によってインデックス変数を解析する再帰関数に頼らずに数値を計算する方法を見つけることはできません。

何か案は？

おそらく役に立たないでしょうが、これは私が現在持っている（間違った）コードです：

ご覧のとおり、次のようになります。

次の左右の値:

それらがいつあるべきか：

Managing Hierarchical Data in MySQLを見てきましたが、実際にはネストされたセット モデルのノードの追加と削除のみを扱います。

子ノードの有無にかかわらずノードを移動できる必要があります。

どうすればいいですか？

今後のプロジェクトの 1 つでこの概念を使用することを検討しています。

詳細: MySQL での階層データの管理。

良い経験も悪い経験も、例を挙げて教えてください。

より広くするために、さらに情報を追加しています。

複数の親を持つことができる子項目があります (例: ユーザーは都市に属し、UserDefinedRegion というグループにも属することができます)。これは、隣接リストであろうとネストされたセットであろうと、典型的な階層モデルではサポートされていません。

明確にするために、ここにユースケースを貼り付けています。

背景: 現在、システムには、都道府県 -> 郡 -> 市区町村 -> ユーザーという固定の階層があります。

1. Sales Manager はシステムにログインし、City または County と同じレベルの新しいグループを作成します。

2. Sales Manager はシステムにログインし、州と郡または郡と市の間にある新しいグループを作成します。

3. 営業マネージャーがグループを作成すると、翌日にはダッシュボードにまとめられた必要なすべてのレポートを表示できるようになります。

ご覧のとおり、2 番目のポイントは入れ子になったセットによって簡単に実現できますが、同じ子ノードに新しい親ノードを導入する最初のポイントはそうではありません。

これまでに、stackOverflow ユーザーによって次のソリューションが提案されました。

1. ネットワーク データベースがサポートするネットワーク ノード構造。
2. 有向非巡回グラフ。

私は間違いなく RDBMS ソリューションを探しています。実際の階層データ モデルで複数の親ノードに遭遇した人はあまりいないようです。

グループのリストを保存するために、ネストされたセット (別名、変更されたプレオーダー ツリー トラバーサル) を使用しています。すべてのグループのブレッドクラムを (テーブルではなく文字列として) 一度に生成する簡単な方法を見つけようとしています。私のデータも、隣接リスト モデルを使用して保存されます (2 つの同期を維持するためのトリガーがあります)。

たとえば、次のようになります。

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

• ノード A
  • ノード B
    • ノード C
  • ノード D
    • ノード E
    • ノード F

テーブルを返すユーザー定義関数を使用できるようにしたいと思います。

これをもう少し複雑にするために (質問の範囲外ですが)、尊重する必要があるユーザー制限もあります。たとえば、id=3 にしかアクセスできない場合、クエリを実行すると次のようになります。

ユーザーIDをパラメーターとして受け取り、有効なすべてのグループのIDを含むテーブルを返すユーザー定義関数があります。クエリのどこかに限り

それが動作します。

これを実行できる既存のスカラー関数がありますが、妥当な数のグループでは機能しません (2000 グループで 10 秒以上かかります)。グループ ID とユーザー ID をパラメーターとして取り、nvarchar を返します。指定されたグループの親を検索し (左/右の値を取得するための 1 つのクエリ、親を検索するための別のクエリ)、ユーザーがアクセスできるグループにリストを制限します (上記と同じ WHERE 句を使用するため、さらに別のクエリを使用します)。次に、カーソルを使用して各グループを調べ、それを文字列に追加してから、最終的にその値を返します。

これを行うには、その場ですばやく (たとえば、<= 1 秒) 実行されるメソッドが必要です。

これは SQL Server 2005 上にあります。