php - ツリー構造のデータベース スキーマを開発する方法 (有向非巡回グラフ)

Question

以下のツリー構造を使用しており、以下の db スキーマを開発する予定です。

私が今までに開発したものは以下のとおりです。

私が抱えている問題は、Y を検索すると、以下のツリーが生成されることです。

私が使用しているロジックは、Y には 2 つの相互参照 X、Z があり、これらの 2 つのノードはダイアグラム内にあり、親ノードは最初の親ノードまでずっとある必要があります。

上記のように、mysql db テーブルを使用してこのツリーを生成するために PHP を使用しているとします。DB構造を変更できます。同様のツリー構造をグーグルで検索しましたが、助けが見つかりませんでした。

ノート

あなたにコードを書いてほしいと言っているわけではありません。私が求めているのは、これをどのように行うべきかというガイドラインだけです。

以下は役に立ちましたが、それでも私のシナリオとは異なります

フラットテーブルをツリーに解析する最も効率的/エレガントな方法は何ですか?

データベースでツリーのような構造を表現する方法

誰かがツリーを生成するためにどのphpライブラリを使用すべきか、また使用するのに適したdb構造を教えてください。

Answer 1

と の両方に複数の ID があるため、データベース構造は正規化されていませnode_parent_idんcross_refer。この情報を別々の表に分ける必要があります。

したがって、nodesテーブルに加えて、親子関係を説明する 2 つ目のテーブルがあります。このテーブルには、子ノード ID と親ノード ID があります。

相互参照は、2 つのノード ID 列を持つ 3 番目のテーブルにある必要がありますが、相互参照は双方向であるため、これを行うには 2 つの方法があります。1 つの方法は、各相互参照を 1 回だけ保存することです。つまり、テーブルをクエリするときに、両方の可能性をチェックする必要があります (X と Y の間の相互参照は、X を最初の列に、Y を 2 番目の列に保存することができます。またはその逆なので、X を見つけるには、両方の列をチェックする必要があります)。もう 1 つの方法は、各相互参照を 2 回 (方向ごとに 1 回) 格納することです。これによりクエリが簡単になりますが、冗長なデータが保存され、不整合が発生する可能性があります。たとえば、何らかの理由で一方の参照が削除され、もう一方が削除されていない場合などです。

この構造を持つパスを見つけることは、カンマ区切りの文字列を追加で解析する必要がないため、はるかに簡単になります。これは、より複雑で効率的ではありません。

これを使用して参照整合性を確保することもできます。たとえば、データベースに実際には存在しない親 ID がノードに含まれないようにすることができます。

詳細については、「データベースの正規化」を調べてください。（または、その傾向がある場合は、「z」で綴ることもできます;-P）

Answer 2

グラフを操作するために私が見つけた唯一の PHP ライブラリは、PEAR “Structures_Graph” パッケージ ( http://pear.php.net/manual/en/package.structures.structures-graph.php ) です。現在はメンテナンスされておらず、重要な機能 (ノードの削除など) が実装されておらず、深刻なバグ (Windows 7 でインストールできないなど) が未解決のままです。そのパッケージは、現在の形では役に立たないようです。

グラフを操作するために必要な基本的な操作は、グラフを変更する操作 (変更) とグラフをクエリする操作 (非変更) に分けることができます。

突然変異操作

• CreateNode($nodeName) は、$nodeID を返します – ノードが作成されると、ノードをグラフ内の他のノードに接続するエッジがないことに注意してください。
• DeleteNode($nodeID) – 参照整合性を強制するには、ノードに接続しているすべてのエッジが以前に削除されている場合にのみ許可され、それ以外の場合は例外がスローされます。
• UpdateNodeName($nodeID, $newNodeName) – 既存のノードの名前の変更が許可されている場合。
• CreateHorizo​​ntalEdge($souceNodeID, $destinationNodeID) – これは有向エッジです。エッジが既に存在する場合、またはエッジの傷を追加してサイクルが作成された場合は、例外をスローします。
• DeleteHorizo​​ntalEdge($sourceNodeID, $destinationNodeID)
• CreateVerticalEdge($firstNodeID, $secondNodeID) – これは双方向エッジです。最初と 2 番目のノード ID を切り替えることができ、グラフへの影響は同じになります。エッジが既に存在する場合、または 2 つのノードが同じ水平方向の親を持っていない場合は、例外をスローします。
• DeleteVerticalEdge($firstNodeID, $secondNodeID) – エッジは無向であるため、引数の作成順序が逆であってもエッジを削除します。

例: 「B」で始まるノード名を持つグラフのセクションを手動で作成するには、コードは次のようになります。

$nodeID_B = CreateNode(“B”);
$nodeID_B1 = CreateNode(“B1”);
$nodeID_B2 = CreateNode(“B2”);
$nodeID_B3 = CreateNode(“B3”);
CreateHorizontalEdge($nodeID_B, $nodeID_B1);
CreateHorizontalEdge($nodeID_B, $nodeID_B2);
CreateHorizontalEdge($nodeID_B, $nodeID_B3);
CreateVerticalEdge($nodeID_B1, $nodeID_B2);
CreateVerticalEdge($nodeID_B2, $nodeID_B3);

「B3」という名前のノードを手動で削除するコード:

// Must remove all edges that connect to node first
DeleteVerticalEdge($nodeID_B2, $nodeID_B3);
DeleteHorizontalEdge($nodeID_B, $nodeID_B3);
// Now no edges connect to the node, so it can be safely deleted
DeleteNode($nodeID_B3);

非変更操作

• NodeExists($nodeID) – true/false を返します
• GetNodeIDByName($nodeName) – $nodeID を返します
• GetNodeName($ノードID)
• Horizo​​ntalEdgeExists($sourceNodeID, $destinationNodeID) – true/false を返します
• VerticalEdgeExists($firstNodeID, $secondNodeID) – true/false を返し、引数の順序に関係なく同じ結果を返します。
• Horizo​​ntalConnectionExists($startNodeID, $endNodeID) – true/false を返します – 水平方向の矢印に従って、開始ノードから終了ノードまでのパスはありますか? $nodeID1 から $nodeID2 への新しい水平エッジを作成するとサイクルが作成されるかどうかをテストするには、Horizo​​ntalConnectionExists($nodeID2, $nodeID1) を呼び出します。
• GetHorizo​​ntalAncestorNodes($nodeID) – 引数ノードへの水平パスを持つすべてのノードの配列を返します。
• GetHorizo​​ntalDescendentNodes($nodeID) – 引数ノードから引数ノードへの水平パスを持つすべてのノードの配列を返します。
• GetVerticalSiblingNodes($nodeID) – 引数ノードへの垂直接続を持つすべてのノードの配列を返します。（私の明確な質問に対するあなたの答えによると）、垂直関係は推移的ではないため、関数 VerticalEdgeExists （上記）は垂直関係を照会するために必要な唯一のものです。

例: 質問で説明したサブツリーに含まれるノードのリストを取得するには、GetHorizo​​ntalAncestorNodes($nodeID) と GetVerticalSiblingNodes($nodeID) の結果を組み合わせます。

データ構造

nodeID と nodeName を保持する「Nodes」テーブルが常に必要です。このテーブルは、ノードに関連付けられた他の情報を保持するように拡張できます。

垂直エッジは推移的ではないため、それらに関する情報は、列 vEdgeID、firstNodeID、secondNodeID を持つ「VerticalEdges」テーブルに簡単に入れることができます。

水平エッジ情報を格納する方法には、いくつかのオプションがあります。一方では、データ構造と変更操作は単純にすることができますが、一部のクエリ操作が遅くなり、より複雑になるという代償があります。一方、データ構造は少し複雑になる可能性がありますが、非常に大きくなる可能性があり (最悪の場合、ノード数に応じて指数関数的に増加します)、変更操作がより複雑になりますが、クエリはより単純で高速になります。どの実装が最適かは、グラフのサイズと、グラフがクエリされる回数と比較してどのくらいの頻度で変化するかによって決まります。

単純なものから複雑なものまで、グラフを表す 3 つの可能なデータ構造について説明します。データ構造の最後のセットについてのみ、上記の操作のアルゴリズムについて詳しく説明します。クエリと変更の比率が高い小さなグラフには、一連の構造が最適だと思います。

すべてのデータ構造には、上で説明した「Nodes」テーブルと「VerticalEdges」テーブルがあることに注意してください。

最小限のデータ構造

最初のデータ構造には、列 hEdgeID、sourceNodeID、destinationNodeID を持つ「Horizo​​ntalEdges」テーブルがあります。変更関数は単純で、ほとんどのコードは例外をスローするエラー チェック コードです。変化しない関数 Horizo​​ntalConnectionExists、GetHorizo​​ntalAncestorNodes、および GetHorizo​​ntalDecendentNodes は複雑で、遅くなる可能性があります。呼び出されるたびに、Horizo​​ntalEdges テーブルを再帰的に走査し、nodeID を収集します。これらのコレクションは、後の 2 つの関数に対して直接返されますが、開始ノードの子孫を検索しているときに終了ノードが見つかった場合、Horizo​​ntalConnectionExists は終了して true を返すことができます。終了ノードが見つからずに検索が終了した場合は、false が返されます。

推移閉鎖表

2 番目のデータ構造にも、上記のものと同じ Horizo​​ntalEdges テーブルがありますが、列 hTCID、startNodeID、および endNodeID を持つ 2 番目のテーブル「Horizo​​ntalTransitiveClosures」もあります。このテーブルには、開始ノードと終了ノードの各ペアに対して行があり、水平方向のエッジを使用するパスを開始ノードから終了ノードまでたどることができます。

例: 問題のグラフの場合、ノード A を含むこの表の行は次のとおりです (表記を簡単にするために、整数のノード ID ではなく名前を使用してノードを識別し、hTCID 列を省略します)。

A, A2
A, A2B1
A, A2B1B2
A, X
A, Y
A, Z

ノード A2B1 を含む行 (最初の行も上記のセットにあります) は次のとおりです。

A, A2B1
A2, A2B1
B, A2B1
B1, A2B1
A2B1, A2B1B2
A2B1, X
A2B1, Y
A2B1, Z

最悪のシナリオでは、このテーブルはノード数の 2 乗に比例します。

このデータ構造を使用すると、Horizo​​ntalConnectionExists、GetHorizo​​ntalAncestorNodes、および GetHorizo​​ntalDescendentNodes を Horizo​​ntalTransitiveClosures テーブルの単純な検索として実装できます。複雑さは、CreateHorizo​​ntalEdge および DeleteHorizo​​ntalEdge 関数に移されます。DeleteHorizo​​ntalEdge は特に複雑で、アルゴリズムが機能する理由についてかなりの説明が必要です。

パスによる推移閉鎖

ここで説明する最終的なデータ構造は、水平方向のエッジ情報を 2 つのテーブルに格納します。最初の「Horizo​​ntalTransitiveClosurePaths」には、列 hTCPathID、startNodeID、endNodeID、pathLength があります。2 番目のテーブル「PathLinks」には、PathLinkID、hTCPathID、sourceNodeID、destinationNodeID の列があります。

Horizo​​ntalTransitiveClosurePaths テーブルは、上記のデータ構造の Horizo​​ntalTransitiveClosures テーブルに似ていますが、推移閉包ごとに 1 行ではなく、推移閉包を達成できる可能性のあるパスごとに 1 つの行があります。たとえば、質問に示されているグラフでは、Horizo​​ ntalTransitiveClosures テーブルには、B で始まり A2B1B2 で終わるクロージャに対して 1 つの行 (B, A2B1B2) (上記の簡略表記) があります。B から A2B1B2 に到達するには 2 つの方法があるため、Horizo​​ntalTransitiveClosurePaths テーブルには (10, B, A2B1B2, 3) と (11, B, A2B1B2, 2) の 2 つの行があります。PathLinks テーブルは、パスを構成するエッジごとに 1 つの行でこれらのパスのそれぞれを記述します。B から A2B1B2 への 2 つのパスの場合、行は次のようになります。

101, 10, B, B1
102, 10, B1, A2B1
103, 10, A2B1, A2B1B2
104, 11, B, B2
105, 11, B2, A2B1B2

Horizo​​ntalTransitiveClosurePaths テーブルで長さ 1 の行を選択することでエッジを見つけることができるため、Horizo​​nalEdges テーブルは必要ありません。

クエリ関数は、上記の Transitive Closure データ構造と同じ方法で実装されます。クロージャーには複数のパスが存在する可能性があるため、GROUP BY 演算子を使用する必要があります。たとえば、ID :nodeid のノードの祖先であるすべてのノードを返す SQL クエリは次のとおりです。 SELECT startNodeID from Horizo​​ntalTransitiveClosurePaths WHERE endNodeID = :nodeid GROUP BY startNodeID

DeleteHorizo​​ntalEdge を実装するには、エッジを含むすべてのパスの hTCPathID の PathLinks を検索します。次に、これらのパスを Horizo​​ntalTransitiveClosurePaths テーブルから削除し、パスに関連付けられているすべてのエッジを PathLinks テーブルから削除します。

CreateHorizo​​ntalEdge($souceNodeID, $destinationNodeID) を実装するには、まず Horizo​​ntalTransitiveClosurePaths テーブルで $souceNodeID で終わるパスを検索します。これが「祖先パス セット」です。DestinationNodeID で始まるパスを Horizo​​ntalTransitiveClosurePaths で検索します。これが「子孫パス セット」です。次に、次の 4 つのグループ (一部は空の場合があります) から新しいパスを Horizo​​ntalTransitiveClosurePaths テーブルに挿入し、それらのパスのリンクを PathLinks テーブルに挿入します。

1. $souceNodeID から $destinationNodeID までの長さ 1 のパス
2. 祖先パス セット内の各パスに対して、$souceNodeID から $destinationNodeID への 1 つの追加リンクによってパスの末尾を拡張する新しいパス
3. 子孫パス セット内のパスごとに、$souceNodeID から $destinationNodeID への 1 つの追加リンクによってパスの開始を拡張する新しいパス
4. 祖先パス セットからの 1 つのパスと子孫パス セットからの 1 つのパスの組み合わせごとに、祖先パスをスライスして作成されたパス、$souceNodeID から $destinationNodeID へのリンク、子孫パスへのパス。

例: グラフは、A1、A2、B、C、D1、D2 の 6 つのノードで構成されます。(A1, B)、(A2, B)、(C, D1)、(C, D2) の 4 つのエッジがあります。Horizo​​ntalTransitiveClosurePaths テーブル (番号ではなくノード名を使用) は次のとおりです。

1, A1, B, 1
2, A2, B, 1
3, C, D1, 1
4, C, D2, 1

PathLinks テーブルは次のとおりです。

1, 1, A1, B
2, 2, A2, B
3, 3, C, D1
4, 4, C, D2

ここで、B から C にエッジを追加します。祖先パス セットは (1, 2) で、子孫パス セットは (3, 4) です。4 つのグループのそれぞれに追加されるパスは次のとおりです。

1. 新しいエッジ自体: Horizo​​ntalTransitiveClosurePaths: (5, B, C, 1); パスリンク (5、5、B、C)
2. 最後に各祖先パスを 1 つのリンクで拡張します。

   Horizo​​ntalTransitiveClosurePaths:
       6、A1、C、2
       7、A2、C、2
   
   パスリンク:
       6、6、A1、B
       7、6、B、C
       8、7、A2、B
       9、7、B、C
   

3. 各子孫パスを最初に 1 つのリンクで拡張します。

   Horizo​​ntalTransitiveClosurePaths:
       8、B、D1、2
       9、B、D2、2
   
   パスリンク:
       10、8、B、C
       11、8、C、D1
       12、9、B、C
       13、9、C、D2
   

4. 1 つの祖先パスと 1 つの子孫パスを含むすべての組み合わせを結合します。

   Horizo​​ntalTransitiveClosurePaths:
       10、A1、D1、3
       11、A1、D2、3
       12、A2、D1、3
       13、A2、D2、3
   
   パスリンク:
       14、10、A1、B
       15、10、B、C
       16、10、C、D1
       17、11、A1、B
       18、11、B、C  
       19、11、C、D2
       20、12、A2、B
       21、12、B、C
       22、12、C、D1
       23、13、A2、B
       24、13、B、C
       25、13、C、D2
   

回答の一部で追加の説明が必要な場合はお知らせください。

Answer 3

私の理解が正しければ、古典的な多対多の自己参照論理テーブル構造を持っていることになります。これは、3 つのテーブルを作成することで簡単に処理できます。1 つは「ノード」を表し、もう 1 つはノード間の親子の「関連付け」を表し、もう 1 つは兄弟関係を表します。兄弟関係は親子関係から推測できるため、兄弟関係を直接表す必要があるとは思いません。ただし、すべての兄弟に対して「緑色」の関係線をレンダリングしていないため、これは何らかの「特別な」関係であると想定します。テーブル/列は次のようにモデル化できます。

ノード

• node_id (pk)
• . . .

Node_Map

• parent_id (node.node_id への fk)
• child_id (node.node_id への fk)

node_sibling_map

• node_id (node.node_id への fk)
• sibling_id (node.node_id への fk)

このモデルで説明したテーブルにデータを入力するには、次を発行する必要があります。（引用は省略）。

• ノード (node_id) 値 (A) に挿入します。
• ノード (node_id) 値 (B) に挿入します。
• ノード (node_id) 値 (C) に挿入します。
• ノード (node_id) 値 (A1) に挿入します。
• ノード (node_id) 値 (A2) に挿入します。
• ノード (node_id) 値 (B1) に挿入します。
• ノード (node_id) 値 (B2) に挿入します。
• ノード (node_id) 値 (B3) に挿入します。
• ノード (node_id) 値 (A2B1) に挿入します。
• ノード (node_id) 値 (CB3) に挿入します。
• ノード (node_id) 値 (A2B1B2) に挿入します。
• ノード (node_id) 値 (X) に挿入します。
• ノード (node_id) 値 (Y) に挿入します。
• ノード (node_id) 値 (Z) に挿入します。
• node_map (parent_id、child_id) 値 (A、A1) に挿入します。
• node_map (parent_id、child_id) 値 (A、A2) に挿入します。
• node_map (parent_id, child_id) 値 (B,B1) に挿入します。
• node_map (parent_id、child_id) 値 (B、B2) に挿入します。
• node_map (parent_id、child_id) 値 (B、B3) に挿入します。
• node_map (parent_id、child_id) 値 (C、CB3) に挿入します。
• node_map (parent_id、child_id) 値 (A2、A2B1) に挿入します。
• node_map (parent_id、child_id) 値 (B1、A2B1) に挿入します。
• node_map (parent_id、child_id) 値 (B2、A2B1B2) に挿入します。
• node_map (parent_id、child_id) 値 (B3、CB3) に挿入します。
• node_map (parent_id、child_id) 値 (C、CB3) に挿入します。
• node_map (parent_id, child_id) 値 (A2B1B2,X) に挿入します。
• node_map (parent_id, child_id) 値 (A2B1B2,Y) に挿入します。
• node_map (parent_id, child_id) 値 (A2B1B2,Z) に挿入します。
• node_sibling_map（node_id、sibling_id）values（b1、b2）に挿入します。
• node_sibling_map (node_id, sibling_id) 値 (B2,B3) に挿入します。
• node_sibling_map (node_id, sibling_id) 値 (X,Y) に挿入します。
• node_sibling_map (node_id, sibling_id) 値 (Y,Z) に挿入します。