XML (Extensible Markup Language) は、Web アプリケーションにおけるデータ表現とデータ交換の標準となり、特に電子商取引、Web サービス、その他のアプリケーションの普及に伴い、XML タイプのデータが主流になりました。主流のデータ形式。したがって、XML データ管理テクノロジ、特に XML データ クエリテクノロジが現在の研究のホットスポットになっています。
リレーショナル データと比較すると、XML にはさまざまな利点がありますが、最大の欠点はその効率性です。リレーショナル データ ファイルでは、データ フィールド名は 1 回だけ出現する必要があるのに対し、XML データ ファイルでは要素名が繰り返し出現するため、クエリの効率に確実に影響します。 XML のクエリ効率をできるだけ向上させるためには、XML 型に対するインデックス機能を提供する必要があります。
World Wide Web Consortium は、2007 年 1 月 23 日に XPath 2.0 と XQuery 1.0 を推奨標準として特定し、さまざまなクエリ言語が優位性を争う以前の状況に終止符を打ちました。 この標準に基づいて、従来のメーカーに加えて、さまざまな科学研究機関が、さまざまなストレージ モデル、さまざまなクエリ アルゴリズム、および最適化手法を使用した XPath および XQuery (文献には十数以上が記載されています) の実装を提案しています。これに関連して、Dameng Database Company も独自の開発戦略に基づいて独自の XML クエリ エンジン モデルを提案しており、現在、Dameng の XML クエリ エンジンは鋭意開発中であり、XML データに対する効果的なインデックスの確立は XML に影響を与える重要な要素です。データクエリのパフォーマンス。既存のデータベース製品のインデックス技術の詳細な分析に基づいて、Dameng XML クエリ エンジンが最適なパフォーマンスを達成できるように、より合理的なインデックス構造が設計されています。
XML インデックス技術の紹介
現在、XML に関する研究は主に 2 つの側面に分かれています。 1 つは、XML などの半構造化データの保存、クエリ、管理のためのネイティブ データベースです。データとメタデータは完全に XML 構造で表現され、その基礎となるデータ ストレージ形式 (オブジェクト モデル、リレーショナル モデルなど) とは何の関係もありません。 、など）。もう 1 つは、リレーショナル データベースの成熟したテクノロジを使用して XML データを処理する、リレーショナル データベースとの間の相互変換です。後者の方向はより実際的な重要性があるため、XML 研究の焦点となっています。
ストレージ ソリューションに加えて、インデックス テクノロジもデータベース システムを決定する際の最も重要な要素の 1 つです。 XML ドキュメントに対してインデックス構造が構築されていない場合、XML データに対するクエリはドキュメント ツリー全体を走査することになる可能性があり、XML データ セットが増加するにつれて、このオーバーヘッドは許容できなくなります。したがって、XML インデックス技術の研究は理論的かつ実用的価値が高くなります。
従来のインデックス作成テクノロジは長期的な蓄積を経て比較的成熟しましたが、このタイプのインデックス作成テクノロジは、（特定の関係を持つパターンではなく）値に基づいてデータ レコードを検索する機能に主に焦点を当てており、データレコード間の論理関係。XML データクエリの基本的な機能は、パターンの特徴 (正規のパス式の形式で記述された構造的関係) の入力に基づいて、パターンに適合するデータを抽出することです。指標は、パターンマッチングに適した技術を設計することです。
XML インデックスの分類
パスベースの XML インデックス
パスベースのインデックスは、XML ツリー構造内のノードのパス情報に基づいており、特定の縮小方法を採用しているため、縮小されたツリー構造は異なるパス情報のみを維持し、存在しません。同じ道。 提案されているインデックスには、DataGuides インデックス、Index Fabric インデックス、Adaptive Path Index for XML Data (APEX) が含まれます。
Dataguides インデックスは、ルート ノードから始まる洗練されたパスの構造的な概要です。エッジ ラベルを連結して形成される文字列パスは、データガイド内で 1 回だけ記述されます。データガイドは、パス クエリを走査するときに必要なノードの数を減らし、XML ドキュメントをルートから効率的に走査します。ただし、ワイルドカード文字を含むパス クエリや、XPath 標準で定義されている子孫または自己軸を使用したパス クエリでは、複数の接続操作が必要となるため、クエリの効率が低くなり、データの冗長性が生じます。
次に、これら 2 つの大きなフィールドに関する Java オブジェクト ファイル TestLob.java を作成し、CLOB 属性フィールドと BLOB 属性フィールドの型をそれぞれ String 型と byte[] 型として定義します。CLOB は大きなテキスト型であるため、Java の String 型に対応します。 、BLOB は、厳密に定義されておらず、バイナリ ストリームの形式で保存されているいくつかの大きなファイルを処理するため、byte[] 型を使用し、これら 2 つのプロパティの Getter メソッドと Setter メソッドをそれぞれ定義します。コードは次のとおりです。
データガイドのインデックスはルート ノードからのものです。 開始リファインメント パスの構造概要。エッジ ラベルを連結して形成される文字列パスは、データガイド内で 1 回だけ記述されます。データガイドは、パス クエリを走査するときに必要なノードの数を減らし、XML ドキュメントをルートから効率的に走査します。ただし、ワイルドカード文字を含むパス クエリや、XPath 標準で定義されている子孫または自己軸を使用したパス クエリでは、複数の接続操作が必要となるため、クエリの効率が低くなり、データの冗長性が生じます。
Index Fabric は、Patricia Trie ツリー上に開発されたインデックス構造で、各要素ノードへのマークされたパスを文字列でエンコードし、これらのエンコードされた値を Patricia Trie ツリーに挿入します。これにより、XML データのクエリが、文字列のクエリへのパス。クエリを実行するときは、まずクエリ パスを文字列形式にエンコードしてから、インデックス ツリー内で検索します。 Index Fabric インデックスの利点は、XML データの階層構造情報を格納し、スキーマのある XML データとスキーマのない情報の取得を均一に処理し、XML データのクエリと更新に必要な時間が、階層に関係なく済むことです。インデックスキーの長さが関係します。 Index Fabric インデックスの欠点は、テキスト値を持つ要素ノードの情報のみを保持するため、要素ノード間の構造的関係が失われることです。したがって、DataGuide インデックスと同様に、Index Fabric インデックスは、XPath 標準で定義されている子孫または自己軸を使用して部分的に一致するクエリ式を処理するのに効率的ではありません。
この目的のために、APEX [14] は XML データの分散に依存する情報を導入しました
。クエリ: 頻繁に発生する XML クエリ ステートメントに対応するラベル ノードをハッシュ構造に事前保存します。その機能はキャッシュの機能に似ています。新しいクエリの処理が必要な場合、まずハッシュ テーブルを検索して、満足のいくノード セットがあるかどうかを確認します。ただし、要素値または属性値を含むクエリ式の場合は効率が低くなります。
ノードベースのインデックス
ノードベースのインデックスは、基本的に XML データをデータ単位のレコード セットに分解し、同時に XML データ内の単位の位置情報をレコードに保存します。パスベースのインデックスとは異なり、ノードベースのインデックスは、ラベル パスを通じてノードを見つける必要があるという制限を破り、XML データを正規形式のノード レコードに分解します。ノードの位置情報を保存し、成熟したリレーショナル データベース管理システムにうまく統合できるため、現在最も広く使用されているインデックスです。
位置情報のさまざまなエンコード方法に従って、ノードベースのインデックスは一般に次のカテゴリに分類できます:
1. プレフィックスベースのインデックス
. プレフィックスベースのインデックスは、主に Dewey [12] エンコーディングと ORDPATH エンコーディングに基づいて生成されたインデックスです。 [13] 同様の方法が採用されており、ORDPATH を圧縮する方法が示されており、SQL Server 2005 のインデックス構成に適用されています。
プレフィックス コーディングの基本的な考え方は、ノードの親ノードのコーディングをノードのコーディングのプレフィックスとして直接使用することです。プレフィックス コーディングでは、ノード v が別のノード u の子孫であるかどうかを判断するだけで済みます。 u のコーディングが v のコーディングのプレフィックスであるかどうか。プレフィックス コーディング インデックスの重要な特性は、その辞書の順序付けです。ノード r をルートとするサブツリー内の任意のノード u について、そのプレフィックス コーディング c(u) は、その左の兄弟サブツリー (右の兄弟サブツリー) より大きい (小さい) です。内のすべてのノードの。したがって、プレフィックスベースのインデックスは、包含関係の計算を効果的にサポートできるだけでなく、ドキュメントの位置関係の計算も効果的にサポートできます。
2. 区間符号化に基づくインデックス
区間符号化インデックスでは、ツリー T 内の各ノードに区間コード [開始、終了] が割り当てられます。これは、ノードの区間コードがその子孫ノードの区間コードを含むという条件を満たします。つまり、ツリー T のノード u はノード v の祖先であり、
start(u) の最初の間隔符号化スキームがディーツ符号化である場合に限り、ツリー T の各ノードには、前順トラバーサル シーケンス番号が割り当てられ、ポスト順序トラバーサル シーケンス番号タプル。ツリー T の祖先ノード u は、前順序トラバーサル (後順序トラバーサル) でその子孫ノード v の前 (後) に出現する必要があるため、ノード u と v は祖先/子孫関係になります。 、pre(u) の場合のみ
間隔エンコーディング インデックスのもう 1 つの典型的な例は、各ノードに番号のペアを割り当てる XISS インデックスです。ここで、order は拡張プレオーダー エンコーディングであり、size はノード スコープの子孫です。
ドキュメント ツリー内の任意のノード X および Y について、order(x)XISS インデックスが元のクエリ ステートメントを部分式に分解する
場合に限ります
。次に、これらの部分式に対してそれぞれクエリを実装し、最後にこれらの中間結果を結合してクエリ結果セットを取得します。これにより、ワイルドカード文字を含むクエリ ステートメントをより適切にサポートできるようになります。ただし、最終的なクエリ結果は、各中間結果を連結した後に取得されます。このような方法は確かにすべてのワイルドカード問題を解決できますが、そのような中間結果の連結は、特に長いパスを持つ単純な式の場合、非常に時間がかかる可能性があります。
2 つのインデックス作成メカニズムの比較。
パスベースのインデックス作成は、主にノードの等価性やパスの等価性などの手法に基づいており、元のドキュメントよりもはるかに小さいインデックス構造が得られます。したがって、クエリを処理するときは、結果を取得するために基本的にインデックス ツリー全体を走査する必要があります。パスベースのインデックスは、単純なパス式クエリを適切にサポートできますが、正規のパス式の場合はあまり適切に機能しません。
ノードベースのインデックスは、エンコード技術を通じて各ノードにインデックスを付けます。ノード間の構造的な関係は、エンコードを通じて一定時間で判断できます。ただし、特にクエリ生成時に多くの中間結果が存在する場合、長いパス式の場合には、ノードインデックスの結合操作はコストがかかります。
パスベースのインデックス作成とノードベースのインデックス作成にはそれぞれ長所と短所がありますが、相互に補完し合うことができます。現在、実際のアプリケーションでは、ノードベースのインデックス作成がより広く使用されており、研究は比較的成熟しています。そのため、Dameng Company の XML インデックス構造に関する研究は主にノードベースのインデックス作成に焦点を当てており、パスベースのインデックス作成を参照して適切な改善を行っています。 。