ネストされたセットモデル
ネストされたセット モデルは、リレーショナル データベース内のネストされたセット コレクション(ツリーまたは階層とも呼ばれます)を表す手法です。
これはネストされた間隔に基づいており、「階層の再編成の問題がなく、保存された階層関係にアクセスすることなく、祖先パスの階層クエリにアルゴリズム的に回答できます。」[ 1 ]
モチベーション
標準的な関係代数と関係計算、そしてそれらに基づくSQL操作では、階層構造に対する望ましい操作をすべて直接表現することはできません。ネストされた集合モデルは、この問題に対する解決策です。
別の解決策として、階層を親子関係として表現する方法があります。ジョー・セルコはこれを隣接リストモデルと呼びました。階層が任意の深さを持つ場合、隣接リストモデルでは、2つの要素の階層の内容を比較したり、ある要素が別の要素のサブ階層のどこかにあるかどうかを判断したりするような操作を表現できません。階層の深さが固定または制限されている場合、これらの操作は可能ですが、レベルごとに1つのリレーショナル結合を実行する必要があるため、コストがかかります。これはしばしば部品表問題として知られています。
階層構造は、グラフデータベースに切り替えることで容易に表現できます。また、リレーショナルモデルにはいくつかの解決策があり、一部のリレーショナルデータベース管理システムでは回避策として利用可能です。
- SQL の階層クエリ機能などの専用の階層データ型のサポート。
- ネストされたリレーショナル代数などの階層操作によってリレーショナル言語を拡張します。
- SQL の CONNECT ステートメントなどの推移的閉包を使用してリレーショナル言語を拡張します。これにより親子関係を使用できるようになりますが、実行コストは依然として高くなります。
- クエリは、反復処理をサポートし、リレーショナル演算をラップした言語（PL/SQL、T-SQL 、汎用プログラミング言語など）で表現できます。
これらのソリューションが利用できない、または実行できない場合は、別のアプローチを講じる必要があります。
技術
ネストされた集合モデルは、ツリートラバーサルに従ってノードに番号を付ける。ツリートラバーサルは各ノードを2回訪問し、訪問順に番号を割り当て、両方の訪問で番号を割り当てる。これにより、各ノードに2つの番号が残り、2つの属性として保存される。クエリは低コストになり、これらの番号を比較することで階層のメンバーシップをテストできる。更新には番号の再割り当てが必要となるため、コストがかかる。整数ではなく有理数を使用するリファインメントは番号の再割り当てを回避できるため、更新は高速になるが、はるかに複雑になる。[ 2 ]
例
衣料品店のカタログでは、左側に示す階層に従って衣料品が分類されます。
| ノード | 左 | 右 |
|---|---|---|
| 衣類 | 1 | 22 |
| 男性用 | 2 | 9 |
| 婦人向け | 10 | 21 |
| スーツ | 3 | 8 |
| スラックス | 4 | 5 |
| ジャケット | 6 | 7 |
| ドレス | 11 | 16 |
| スカート | 17 | 18 |
| ブラウス | 19 | 20 |
| イブニングドレス | 12 | 13 |
| サンドレス | 14 | 15 |
階層の最上位に位置する「衣料品」カテゴリは、すべての従属カテゴリを包含しています。そのため、左ドメイン値と右ドメイン値はそれぞれ1と22です。後者の値は、表現されるノードの総数の2倍です。次の階層レベルには「メンズ」と「レディース」が含まれており、どちらもさらに下位レベルを含んでおり、それぞれを考慮する必要があります。各レベルのデータノードには、表データに示されているように、含まれるサブレベルの数に応じて左ドメイン値と右ドメイン値が割り当てられます。
パフォーマンス
ネストされたセットを使用するクエリは、ストアド プロシージャを使用して隣接リストをトラバースするクエリよりも高速になることが期待できるため、 MySQL 5.xなど、ネイティブの再帰クエリ構造を持たないデータベースではより高速なオプションとなります。 [ 3 ]ただし、再帰 SQL クエリは、「直接の子孫を見つける」クエリでは同等のパフォーマンスが期待でき、他の深さの検索クエリでははるかに高速になるため、PostgreSQL、[ 4 ] Oracle、[ 5 ] Microsoft SQL Serverなど、そのようなクエリ構造を提供するデータベースではより高速なオプションとなります。 [ 6 ] MySQL には以前は再帰クエリ構造がありませんでした。しかし、バージョン 8 でそのような機能が追加されました。[ 7 ]
欠点
動的な無限データベースツリー階層の使用例はまれです。ネストセットモデルは、ツリー要素と1つまたは2つの属性のみがデータである場合に適していますが、ツリー内の要素に対してより複雑なリレーショナルデータが存在する場合には適していません。「車両」カテゴリの開始深度が任意で、「車」の子に「メルセデス」の子がある場合、ツリーテーブルがネイティブで非正規化されていない限り、外部キーテーブルの関係を確立する必要があります。新しく作成されたツリー項目の属性は、親、子、さらには兄弟とすべての属性を共有しない可能性があります。「植物」属性のテーブルに外部キーテーブルを確立した場合、「木」とその子「オーク」の子属性データに整合性は付与されません。したがって、ツリーに項目が挿入されるたびに、ごく単純な使用例を除き、その項目の属性の外部キーテーブルを作成する必要があります。
ツリーが頻繁に変更される可能性が低い場合は、システムの初期設計段階で適切に正規化された属性テーブルの階層構造を作成することができます。これにより、よりシンプルで移植性の高いSQL文を作成できます。具体的には、ツリーの変更に任意の数のランタイムテーブル、プログラムによって作成または削除されたテーブルを必要としないSQL文を作成できます。より複雑なシステムでは、暗黙的な数値ツリー構造ではなく、リレーショナルモデルを通じて階層構造を構築できます。アイテムの深さは、DBアーキテクチャ全体の基礎ではなく、単なる別の属性です。SQLアンチパターン[ 8 ]には次のように記載されています。
ネストされた集合は巧妙な解決策ですが、もしかしたら巧妙すぎるかもしれません。また、参照整合性をサポートしていません。ツリーを変更するよりも頻繁にクエリを実行する必要があるような場合に最適です。[ 9 ]
このモデルでは複数の親カテゴリを定義できません。例えば、「オーク」は「樹木タイプ」の子カテゴリになるだけでなく、「木材タイプ」の子カテゴリにもなります。これに対応するには、追加のタグ付けや分類体系を確立する必要があり、単純な固定モデルよりも複雑な設計が必要になります。
ネストされたセットは、挿入後にテーブル内のすべてのレコードの左ドメイン値と右ドメイン値を更新する必要があるため、挿入処理が非常に遅くなります。多くの行が書き換えられ、インデックスが再構築されるため、データベースに大きな負荷がかかります。しかし、単一の大きなツリーではなく、小さなツリーのフォレストをテーブルに格納できれば、更新する必要があるのは1つの小さなツリーだけなので、オーバーヘッドは大幅に削減される可能性があります。
ネストされた区間モデルはこの問題を抱えていませんが、実装がより複雑で、あまり知られていません。それでも、リレーショナル外部キーテーブル問題は依然として存在します。ネストされた区間モデルは、ノードの位置を商（n/d）で表される有理数として保存します。[1]
バリエーション
上述のようにネストされたセットモデルを使用すると、特定のツリー走査操作においてパフォーマンス上の制限が生じます。例えば、親ノードから直下の子ノードを見つけようとする場合、次のSQLコード例のように、サブツリーを特定のレベルまで枝刈りする必要があります。
SELECT Child.Node 、Child.Left 、Child.Right FROM Tree as Parent 、Tree as Child WHERE Child.Left BETWEEN Parent.Left AND Parent.Right AND NOT EXISTS ( --中間ノードがありませんSELECT * FROM Tree as Mid WHERE Mid.Left BETWEEN Parent.Left AND Parent.Right AND Child.Left BETWEEN Mid.Left AND Mid.Right AND Mid.Node NOT IN ( Parent.Node 、Child.Node ) ) AND Parent.Left = 1 --親ノードの左インデックスが指定されていますあるいは、同様に:
SELECT DISTINCT Child.Node , Child.Left , Child.Right FROM Tree as Child , Tree as Parent WHERE Parent.Left < Child.Left AND Parent.Right > Child.Right --子ノードを祖先に関連付けますGROUP BY Child.Node , Child.Left , Child.Right HAVING max ( Parent.Left ) = 1 --指定された親ノードを最も近い祖先として持つノードのサブセットを作成します複数の階層にまたがる子ノードを検索する場合、クエリはより複雑になります。この制限を克服し、ツリーのトラバーサルを簡素化するために、ツリー内のノードの深さを維持するための列がモデルに追加されます。
| ノード | 左 | 右 | 深さ |
|---|---|---|---|
| 衣類 | 1 | 22 | 0 |
| 男性用 | 2 | 9 | 1 |
| 婦人向け | 10 | 21 | 1 |
| スーツ | 3 | 8 | 2 |
| スラックス | 4 | 5 | 3 |
| ジャケット | 6 | 7 | 3 |
| ドレス | 11 | 16 | 2 |
| スカート | 17 | 18 | 2 |
| ブラウス | 19 | 20 | 2 |
| イブニングドレス | 12 | 13 | 3 |
| サンドレス | 14 | 15 | 3 |
このモデルでは、親ノードが与えられた場合、その直下の子ノードを見つけることは、次のSQLコードで実行できます。
SELECT Child.Node , Child.Left , Child.Right FROM Tree as Child , Tree as Parent WHERE Child.Depth = Parent.Depth + 1 AND Child.Left > Parent.Left AND Child.Right < Parent.Right AND Parent.Depth = 1 --親ノードの左インデックスが指定されています参照
参考文献
- ^「SQLにおけるネストされたインターバルツリーエンコーディング」、Vadim Tropashko、Oracle Corp. オリジナルはhttps://web.archive.org/web/20111119165033/http://sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdfです。
- ^ヘイゼル、ダニエル (2008). 「有理数を用いた入れ子集合のキー設定」arXiv : 0806.3115 [ cs.DB ].
- ^ Quassnoi (2009年9月29日)、「隣接リストとネストされたセット：MySQL」、Explain Extended 、2010年12月11日閲覧。
- ^ Quassnoi (2009年9月24日)、「隣接リストとネストされたセット：PostgreSQL」、Explain Extended 、2010年12月11日閲覧。
- ^ Quassnoi (2009年9月28日)、「隣接リストとネストされたセット：Oracle」、Explain Extended 、2010年12月11日閲覧。
- ^ Quassnoi (2009年9月25日)、「隣接リストとネストされたセット: SQL Server」、Explain Extended 、2010年12月11日閲覧。
- ^ 「MySQL :: MySQL 8.0 リファレンスマニュアル :: 13.2.15 WITH (共通テーブル式)」 . dev.mysql.com . 2021年9月1日閲覧。
- ^ Bill, Karwin (2010-06-17). SQLアンチパターン. p. 328.
- ^ Bill, Karwin. SQLアンチパターン. p. 44.
外部リンク
- Troels の RDBMS の階層データへのリンク
- リレーショナルデータベースにおける階層データの管理
- ネストされたセットのための PHP PEAR 実装– Daniel Khan 著
- MySQL ストアド プロシージャを使用して、任意の隣接リストをネストされたセットに変換する
- PHP Doctrine のネストセット用 DBAL 実装– PreviousNext
- R ネストセット– R のネストセットの例
