リレーショナルデータベースエンジンをベースとした「XML」インデックス技術

XML (Extensible Markup Language) は、インターネットの急速な発展、特に電子商取引、Web サービス、その他のアプリケーションの普及に伴い、XML タイプのデータが Web アプリケーションでのデータ表現とデータ交換の標準になりました。現在主流のデータ形式。したがって、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インデックス

パスベースのインデックスは、XMLツリー構造内のノードのパス情報に基づいており、特定の削減方法を採用しているため、削減されたツリー構造は異なるパス情報のみを維持します。同じパスを持つ 2 つのノードがある。 提案されているインデックスには、DataGuides インデックス、Index Fabric インデックス、Adaptive Path Index for XML Data (APEX) が含まれます。

Dataguides インデックスは、ルート ノードの構造概要から始まる洗練されたパスの一種です。エッジ ラベルの連結によって形成される文字列パスは、データガイド内で 1 回だけ記述されます。データガイドは、パス クエリを走査するときに必要なノードの数を減らし、XML ドキュメントをルートから効率的に走査します。ただし、ワイルドカード文字を含むパス クエリや、XPath 標準で定義されている子孫または自己軸を使用したパス クエリでは、複数の接続操作が必要となるため、クエリの効率が低くなり、データの冗長性が生じます。

次に、これら 2 つの大きなフィールドに関する Java オブジェクト ファイル TestLob.java を作成し、CLOB 属性フィールドと BLOB 属性フィールドをそれぞれ String 型と byte[] 型として定義します。CLOB は大きなテキスト型であるため、Java に対応します。タイプの場合、BLOB はバイナリ ストリームの形式で厳密に定義されていない大きなファイルを処理するために使用されるため、byte[] タイプを使用して、これら 2 つのプロパティの Getter メソッドと Setter メソッドをそれぞれ定義します。関連するコードは次のとおりです。

Dataguides インデックスは、ルート ノードから始まる洗練されたパスの構造的な概要です。エッジ ラベルの連結によって形成される文字列パスは、データガイド内で 1 回だけ記述されます。データガイドは、パス クエリを走査するときに必要なノードの数を減らし、XML ドキュメントをルートから効率的に走査します。ただし、ワイルドカード文字を含むパス クエリや、XPath 標準で定義されている子孫または自己軸を使用したパス クエリでは、複数の接続操作が必要となるため、クエリの効率が低くなり、データの冗長性が生じます。

Index Fabric は、Patricia Trie ツリー上に開発されたインデックス構造であり、各要素ノードへのマークされたパスを文字列でエンコードし、これらのエンコードされた値を Patricia Trie ツリーに挿入します。パスは文字列のクエリに変換されます。クエリを実行するときは、まずクエリ パスを文字列形式にエンコードしてから、インデックス ツリー内で検索します。 Index Fabric インデックスの利点は、XML データの階層構造情報を格納し、スキーマのある XML データとスキーマのない情報の取得を均一に処理し、XML データのクエリと更新に必要な時間が、階層に関係なく済むことです。インデックスキーの長さが関係します。 Index Fabric インデックスの欠点は、テキスト値を持つ要素ノードの情報のみを保持するため、要素ノード間の構造的関係が失われることです。したがって、DataGuides インデックスと同様に、Index Fabric インデックスは、情報: ハッシュ構造内で頻繁に発生する XML クエリ ステートメントに対応する事前保存ラベル ノードで定義された子孫または自己軸を使用した部分一致クエリ式の処理には効率的ではありません。その機能はキャッシュの機能に似ています。新しいクエリの処理が必要な場合、まずハッシュ テーブルを検索して、満足のいくノード セットがあるかどうかを確認します。ただし、要素値または属性値を含むクエリ式の場合は効率が低くなります。

ノードベースのインデックス

ノードベースのインデックスは、基本的に XML データをデータユニットのレコードセットに分解し、同時に XML データ内のユニットの位置情報をレコードに保存します。パスベースのインデックスとは異なり、ノードベースのインデックスは、ラベル パスを通じてノードを見つける必要があるという制限を破り、XML データを正規形式のノード レコードに分解します。ノードの位置情報を保存し、成熟したリレーショナル データベース管理システムにうまく統合できるため、現在最も広く使用されているインデックスです。

位置情報のさまざまなエンコーディング方法に従って、ノードベースのインデックスは一般に次のカテゴリに分類できます:

1. プレフィックスベースのインデックス

プレフィックスベースのインデックスは、主に Dewey[12] エンコーディングに基づいて生成されるインデックスです。文献 [13] では、ORDPATH エンコードに同様の方法を使用し、SQL Server 2005 のインデックス構成に適用された ORDPATH を圧縮する方法を提供しています。

プレフィックス エンコーディングの基本的な考え方は、ノードの親ノードのエンコーディングをノード エンコーディングのプレフィックスとして直接使用することです。プレフィックス エンコーディングでは、ノード v が別のノード u の子孫であるかどうかを判断するだけです。 u のエンコーディングが v のエンコーディングであるかどうかを判断する必要があります。エンコーディング プレフィックス。プレフィックス コーディング インデックスの重要な特性は、その辞書の順序付けです。ノード r をルートとするサブツリー内の任意のノード u について、そのプレフィックス コーディング c(u) は、その左の兄弟サブツリー (右の兄弟サブツリー) より大きい (小さい) です。内のすべてのノードの。したがって、プレフィックスベースのインデックスは、包含関係の計算を効果的にサポートできるだけでなく、ドキュメントの位置関係の計算も効果的にサポートできます。

2. 間隔コーディングに基づくインデックス

間隔コーディングインデックスの場合、ツリー T 内の各ノードには間隔コード [開始、終了] が割り当てられます。これは次の条件を満たします: ノードの間隔コードにはその子孫ノードの間隔コードが含まれる言い換えれば、区間符号化は、start(u) の場合にのみ、ツリー T のノード u がノード v の祖先になります

最初の区間符号化スキームはディーツ符号化であり、ツリー T の各ノードには次の A タプルが割り当てられます。前順トラバーサル シーケンス番号と後順トラバーサル シーケンス番号ノード u と v は、PRe(u) の場合にのみ祖先/子孫の関係になります

間隔でエンコードされたインデックスのもう 1 つの典型的な例は、各ノードに番号のペアを割り当てる XISS インデックスです。ここで、order は拡張された事前順序です。 エンコーディング、サイズノードの子孫の範囲です。ドキュメント ツリー内の任意のノード X および Y について、order(x)

XISS インデックスが元のクエリ ステートメントを部分式に分解する場合に限ります。次に、これらの部分式に対してそれぞれクエリを実装し、最後にこれらの中間結果を結合してクエリ結果セットを取得します。これにより、ワイルドカード文字を含むクエリ ステートメントをより適切にサポートできるようになります。ただし、最終的なクエリ結果は、各中間結果を連結した後に取得されます。このような方法は確かにすべてのワイルドカード問題を解決できますが、そのような中間結果の連結は、特に長いパスを持つ単純な式の場合、非常に時間がかかる可能性があります。

2 つのインデックス作成メカニズムの比較

パスベースのインデックス作成は、主にノード結合戦略に基づいており、ノード等価性やパス等価性などの手法を通じて、元のドキュメントよりもはるかに小さいインデックス構造が取得され、その構造は次のようになります。依然としてツリーであるため、クエリを処理するときは、基本的に結果を取得するためにインデックス ツリー全体を走査する必要があります。パスベースのインデックスは、単純なパス式クエリを適切にサポートできますが、正規のパス式の場合はあまり適切に機能しません。

ノードベースのインデックスは、エンコード技術を通じて各ノードにインデックスを付けます。ノード間の構造的関係は、エンコードを通じて一定時間で決定できますが、特に多くの中間結果が生成される場合には、長いパス式をサポートします。クエリによるノード インデックスの結合操作はコストがかかります。

パスベースのインデックス作成とノードベースのインデックス作成にはそれぞれ長所と短所がありますが、相互に補完し合うことができます。現在、実際のアプリケーションでは、ノードベースのインデックス作成がより広く使用されており、研究は比較的成熟しています。そのため、Dameng Company の XML インデックス構造に関する研究は主にノードベースのインデックス作成に焦点を当てており、パスベースのインデックス作成を参照して適切な改善を行っています。 。

上記は、リレーショナル データベース エンジンに基づいた「XML」インデックス技術の内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) をご覧ください。