問題タブ [hierarchical-data]

答えはノーだと思いますが、SQL（MySQL）でツリー構造を任意の深さまでクロールする方法について誰かが洞察を持っていることを望んでいますが、単一のクエリで

より具体的には、ツリー構造のテーブル (id、data、data、parent_id)、およびテーブル内の 1 つの行が与えられた場合、すべての子孫 (子/孫/など)、またはすべての祖先 (親/祖父母)を取得することは可能ですか? /etc) 単一のクエリを使用して、どこまで下がるか上がるかを知らずに?

または、新しい結果がなくなるまで、より深いクエリを続ける、ある種の再帰が必要ですか?

具体的には、私は Ruby と Rails を使用していますが、それはあまり関連性がないと推測しています。

順序付けられたツリー階層を格納するフラット テーブルがあるとします。

ここに がある図があります[id] Name。ルート ノード 0 は架空のものです。

それを正しい順序で正しくインデントされたツリーとして HTML (またはテキスト) に出力するには、どのような最小限のアプローチを使用しますか?

さらに、基本的なデータ構造 (配列とハッシュマップ) しかなく、親/子の参照を持つ派手なオブジェクトはなく、ORM もフレームワークもなく、両手だけしかないと仮定します。テーブルは結果セットとして表され、ランダムにアクセスできます。

疑似コードまたは平易な英語で問題ありません。これは純粋に概念上の問題です。

おまけの質問: このようなツリー構造を RDBMS に格納する根本的に優れた方法はありますか?

編集と追加

あるコメント投稿者 ( Mark Besseyさん) の質問に答えるには: ルート ノードは必要ありません。とにかく表示されることはないからです。ParentId = 0 は、「これらがトップ レベルであること」を表すための規則です。Order 列は、同じ親を持つノードがどのようにソートされるかを定義します。

私が話した「結果セット」は、ハッシュマップの配列として描くことができます (その用語にとどまります)。私の例では、すでにそこにあるはずでした。いくつかの答えは、さらに一歩進んで最初に構築しますが、それは問題ありません。

ツリーの深さは任意です。各ノードは N 個の子を持つことができます。ただし、「何百万ものエントリ」ツリーを念頭に置いているわけではありません。

私が選んだノード名 ('Node 1.1.1') を信頼できるものと間違えないでください。ノードは、'Frank' または 'Bob' と同じように呼ぶことができます。命名構造は暗示されていません。これは単に読みやすくするためです。

独自のソリューションを投稿したので、皆さんはそれをバラバラにすることができます。

私は親子関係を持つdbテーブルを次のように持っています:

ここで、parentId = 0 は、ルート レベルのノードであることを意味します。ここで、親カテゴリのすべてのレベルで子を返す SQL クエリを書きたいと思います。

たとえば、nodeId = 1 の場合、3、4、5、6 を返す必要があります。

MS SQL Server 2005 を使用しています

現在、SQL Server SQL ステートメントを同等の ANSI 汎用ステートメントに変換していますが、WITH ステートメントを使用した再帰ステートメントに悩まされています。

この問題に集中するために、次のように問題を単純化します。

テーブルが 2 つある場合

1. 報告単位

   • col1: キー
   • col2: ParentReportingUnitKey

2. 施設

   • col1: キー
   • col2: ParentReportingUnitKey

この構造は、施設までのレポーティング ユニットの階層を記述しています。レポーティング ユニットは、0 .. 1 の直接の親レポーティング ユニットと 0 .. n の子レポーティング ユニットを持つことができます。

施設は、レポーティング ユニットにリンクする「リーフ」レコードです。

ANSI 92 の有効な SQL ステートメント (または、最悪の場合、Oracle、DB2、および SQL Server で動作するもの) を作成する必要があります。これは、階層の任意の場所にある特定のレポート ユニットに関連するすべての機能を返します。

例えば

• ReportingUnit R1 には ReportingUnit の子 R1.1 と R1.2 があります
• ReportingUnit R1.1 には子 R1.1.1、R1.1.2 があります

• ReportingUnit R1.2 には子 R1.2.1、R1.2.2 があります

• 施設 F1 には、親報告単位 R1.1.1 があります。

• 施設 F2 には、親報告単位 R1.1.2 があります。
• 施設 F3 には、親報告単位 R1.2.1 があります。
• 施設 F4 には、親報告単位 R1.2.2 があります。

ReportingUnit テーブルには 0 ～ n レベルの再帰がある可能性があることを念頭に置いて、パラメーター ReportingUnit=R1 を指定して SQL ステートメントから 4 つの機能すべてを返すにはどうすればよいでしょうか?

最善の方法は次のとおりです。

1. 単一のクエリを使用してデータベースからデータを取得する
2. ネストされた順序付けられていないリストなど、結果の構築をループします

私のテーブルにはid、nameおよびparent_id列があります。

これが私の最後の回答の更新です。各 ul にネストされた「レベル」クラスを与えるカウンターといくつかのコメントがあります。

ネストせずにテーブル行を使用するようにこれを適応させる方法を誰かが提案できますか?

スレッド化されたメッセージ ボードを作成していますが、シンプルにしようとしています。メッセージ テーブルがあり、次に返信テーブルがあります。このテーブルには、トップ レベルの応答を示すために null にすることも、スレッド化された応答を示す値にすることもできる「reply_id」フィールドがあります。

このタイプのテーブルで SELECT 呼び出しを行う方法について少し混乱していますか?

これは、特にパフォーマンスに関して複雑な問題になる可能性があることはわかっていますが、これに対する最も基本的な解決策を探しているだけです。

ありがとう...

平らな構造のオブジェクトがたくさんあります。これらのオブジェクトにはIDとParentIDプロパティがあるため、ツリーに配置できます。それらは特定の順序ではありません。各ParentIDプロパティは、必ずしもID構造内のと一致するとは限りません。したがって、それらはこれらのオブジェクトから出現するいくつかの木である可能性があります。

これらのオブジェクトをどのように処理して、結果のツリーを作成しますか？

私は解決策からそれほど遠くはありませんが、それは最適とはほど遠いことを確信しています...

これらのツリーを作成して、データを適切な順序でデータベースに挿入する必要があります。

循環参照はありません。ParentID == nullの場合、またはParentIDが他のオブジェクトで見つからない場合、ノードはRootNodeです。

隣接リストとネストされたツリーの2つのアプローチがあることを知っています。多数のクエリが原因で、トラバーサルでの隣接リストの使用が遅くなる可能性があると言われています。しかし、私はこれについての現実的な数字を知りません。私が作っているサイトは 200 ページ程度です。(たとえば) サイトマップを生成するためのトラバーサルには、約 0.3 秒以上かかりますか?

LAMP スタックを使用して MySQL (innoDB) で実行します。

より単純な設計のため、可能であれば隣接関係を実装したいと思います。

ありがとう。