(57)【要約】【課題】パーティションすることによりデータベース・アクセスを効率化する、情報処理装置、データベース・システム、情報処理方法およびプログラムを提供すること。【解決手段】パーティション化する対象データを含む単位部分木を、対象データに応答して分離して登録する値パーティションと、単位部分木を固有に識別するためのインデックスを含むベース・パーティションとを生成するパーティション生成部２２２と、構造化文書の属性値を定義する開始タグの位置および終了タグの位置を識別して、属性値の階層構造に対応する分割位置リストを作成し記憶領域に登録するXMLパーザ２２４と、分割するべき単位部分木の開始タグ位置および終了タグ位置を識別し、単位部分木およびインデックスを、構造化文書から分離するXML分割部２２６と、単位部分木とインデックスとを異なるパーティションに登録する分割XML登録部とを含んでいる。【選択図】図２
2010129001.tif 000002
【特許請求の範囲】
【請求項１】
階層構造を有する構造化文書を管理するデータベースを含む情報処理装置であって、前記情報処理装置は、
前記構造化文書のパーティション化する対象データを含む単位部分木を、前記対象データの値に応答して分離して登録する値パーティションと、前記単位部分木以外の部分木および前記単位部分木を固有に識別するためのインデックスを含むベース・パーティションとを生成するパーティション生成部と、
前記構造化文書の属性を定義する開始タグの位置および終了タグの位置を識別して、属性値の階層構造に対応する分割位置リストを作成し記憶領域に登録するパーザ部と、
前記分割位置リストを参照し、前記対象データを含む分割するべき前記単位部分木の前記開始タグ位置および前記終了タグ位置を識別して前記単位部分木および前記単位部分木を参照するためのインデックスを、前記構造化文書から分離する分割部と、
前記分割部により分離した前記単位部分木と前記単位部分木を識別するインデックスとを異なるパーティションに登録する登録部と
を含む情報処理装置。
【請求項２】
前記単位部分木は、複数の前記開始タグを含み、前記インデックスは、前記単位部分木の最初の前記開始タグから生成される、請求項１に記載の情報処理装置。
【請求項３】
前記登録部は、前記単位部分木と、前記単位部分木を固有に識別するための前記インデックスとに対し、相互参照を可能とするポインタをそれぞれ追加して前記異なるパーティションに登録する、請求項２に記載の情報処理装置。
【請求項４】
前記分割部は、前記分割位置リストを参照し、前記異なるパーティションに登録するための前記単位部分木を分離するため、前記構造化文書が含む前記単位部分木の開始位置および終了位置とを対応付ける、領域ペアおよび当該単位部分木の前記構造化文書内での記述順を登録する出現カウンタを含む部分木データ・リストを作成し、記憶領域に登録する、請求項３に記載の情報処理装置。
【請求項５】
前記情報処理装置は、前記値パーティションに登録された前記単位部分木を前記対象データを使用して検索するためのSQL処理部と、前記SQL処理部による検索結果を生成する検索結果生成部を含む、前記請求項４に記載の情報処理装置。
【請求項６】
前記構造化文書は、XMLで記述され、前記データベースは、XMLを格納・検索することを可能にするXMLDBである、請求項４に記載の情報処理装置。
【請求項７】
階層構造を有する構造化文書を登録するデータベースを含むデータベース・システムであって、前記データベース・システムは、
前記構造化文書のパーティション化する対象データを含む単位部分木を、前記対象データの値に応答して分離して登録する値パーティションと、前記単位部分木以外の部分木および前記単位部分木を固有に識別するためのインデックスを含むベース・パーティションとを生成して管理するデータ管理部と、
前記データベースに登録された前記構造化文書を、当該構造化文書の前記階層構造を指定した検索要求を処理するSQL処理部と、
前記SQL処理部による前記値パーティションについての個別検索結果から前記検索要求に対する検索結果を作成する検索結果作成部と
を含み、前記データ管理部は、
前記パーティションを生成するパーティション生成部と、
前記構造化文書の属性を定義する開始タグの位置および終了タグの位置を識別して、属性値の階層構造に対応する分割位置リストを作成し記憶領域に登録するパーザ部と、
前記分割位置リストを参照し、前記対象データを含む分割するべき前記単位部分木の前記開始タグ位置および前記終了タグ位置を識別して前記単位部分木および前記単位部分木を参照するためのインデックスを、前記構造化文書から分離する分割部と、
前記分割部により分離した前記単位部分木と前記単位部分木を識別するインデックスとを異なるパーティションに登録する登録部と
を含む、データベース・システム。
【請求項８】
前記単位部分木は、複数の前記開始タグを含み、前記インデックスは、前記単位部分木の最初の前記開始タグから生成される、請求項７に記載のデータベース・システム。
【請求項９】
前記登録部は、前記単位部分木と、前記単位部分木を固有に識別するための前記インデックスとに対し、相互参照を可能とするポインタをそれぞれ追加して前記異なるパーティションに登録する、請求項８に記載のデータベース・システム。
【請求項１０】
前記分割部は、前記分割位置リストを参照し、前記異なるパーティションに登録するための前記単位部分木を分離するため、前記構造化文書が含む前記単位部分木の開始位置および終了位置とを対応付ける、領域ペアおよび当該単位部分木の前記構造化文書内での記述順を登録する出現カウンタを含む部分木データ・リストを作成し、記憶領域に登録する、請求項９に記載のデータベース・システム。
【請求項１１】
前記構造化文書は、XMLで記述され、前記データベースは、XMLを格納・検索することを可能にするXMLDBシステムである、請求項１０に記載のデータベース・システム。
【請求項１２】
階層構造を有する構造化文書を登録するデータベースに対する情報処理方法であって、前記情報処理方法は、情報処理装置が、
前記構造化文書のパーティション化する対象データを含む単位部分木を、前記対象データの値に応答して分離して登録する値パーティションと、前記単位部分木以外の部分木および前記単位部分木を固有に識別するためのインデックスを含むベース・パーティションとを生成するステップと、
前記構造化文書の属性を定義する開始タグの位置および終了タグの位置を識別して、属性値の階層構造に対応する分割位置リストを作成し記憶領域に登録するステップと、
前記分割位置リストを参照し、前記対象データを含む分割するべき前記単位部分木の前記開始タグ位置および前記終了タグ位置を識別して前記単位部分木および前記単位部分木を参照するためのインデックスを、前記構造化文書から分離するステップと
前記分離するステップで分離された前記単位部分木と前記単位部分木を識別するインデックスとを異なるパーティションに登録するステップと
を実行する、情報処理方法。
【請求項１３】
前記単位部分木は、複数の前記開始タグを含み、前記生成するステップは、前記インデックスを、前記単位部分木の最初の前記開始タグを識別して生成するステップを含む、請求項１２に記載の情報処理方法。
【請求項１４】
前記分離するステップは、前記分割位置リストを参照し、前記異なるパーティションに登録するための前記単位部分木を分離するため、前記構造化文書が含む前記単位部分木の開始位置および終了位置とを対応付ける、領域ペアおよび当該単位部分木の前記構造化文書内での記述順を登録する出現カウンタを含む部分木データ・リストを作成し、記憶領域に登録するステップを含む、請求項１３に記載の情報処理方法。
【請求項１５】
前記登録するステップは、前記単位部分木と、前記単位部分木を固有に識別するための前記インデックスとに対し、相互参照を可能とするポインタをそれぞれ追加して前記異なるパーティションに登録するステップを含む、請求項１４に記載の情報処理方法。
【請求項１６】
さらに、
前記値パーティションに登録された前記単位部分木を前記対象データを使用して検索するステップと、
前記検索するステップによる前記値パーティションについての個別検索結果を統合して検索結果を生成するステップと
を含む、請求項１５に記載の情報処理方法。
【請求項１７】
階層構造を有する構造化文書を登録するデータベースに対する情報処理方法を情報処理装置が実行するためのコンピュータ実行可能なプログラムであって、前記プログラムは、情報処理装置が、
前記構造化文書のパーティション化する対象データを含む単位部分木を、前記対象データの値に応答して分離して登録する値パーティションと、前記単位部分木以外の部分木および前記単位部分木を固有に識別するためのインデックスを含むベース・パーティションとを生成するステップと、
前記構造化文書の属性を定義する開始タグの位置および終了タグの位置を識別して、属性値の階層構造に対応する分割位置リストを作成し記憶領域に登録するステップと、
前記分割位置リストを参照し、前記対象データを含む分割するべき前記単位部分木の前記開始タグ位置および前記終了タグ位置を識別して前記単位部分木および前記単位部分木を参照するためのインデックスを、前記構造化文書から分離するステップと
前記分離するステップで分離された前記単位部分木と前記単位部分木を識別するインデックスとを異なるパーティションに登録するステップと、
を実行するための、コンピュータ実行可能なプログラム。
【請求項１８】
前記単位部分木は、複数の前記開始タグを含み、前記生成するステップは、前記インデックスを、前記単位部分木の最初の前記開始タグを識別して生成するステップを含む、請求項１７に記載のプログラム。
【請求項１９】
前記分離するステップは、前記分割位置リストを参照し、前記異なるパーティションに登録するための前記単位部分木を分離するため、前記構造化文書が含む前記単位部分木の開始位置および終了位置とを対応付ける、領域ペアおよび当該単位部分木の前記構造化文書内での記述順を登録する出現カウンタを含む部分木データ・リストを作成し、記憶領域に登録するステップを含む、請求項１８に記載のプログラム。
【請求項２０】
階層構造を有する構造化文書を管理するデータベースを含む情報処理装置であって、前記情報処理装置は、
前記構造化文書のパーティション化する対象データを含む単位部分木を、前記対象データの値に応答して分離して登録する値パーティションと、前記単位部分木以外の部分木および前記単位部分木を固有に識別するためのインデックスを含むベース・パーティションとを生成するパーティション生成部と、
前記構造化文書の属性を定義する開始タグの位置および終了タグの位置を識別して、属性値の階層構造に対応する分割位置リストを作成し記憶領域に登録するパーザ部と、
前記分割位置リストを参照し、前記対象データを含む分割するべき前記単位部分木の前記開始タグ位置および前記終了タグ位置を識別して前記単位部分木および前記単位部分木を参照するためのインデックスを、前記構造化文書から分離する分割部と、
前記分割部により分離した前記単位部分木と前記単位部分木を識別するインデックスとを異なるパーティションに登録する登録部と
を含み、
前記単位部分木は、複数の前記開始タグを含み、前記インデックスは、前記単位部分木の最初の前記開始タグから生成され、
前記登録部は、前記単位部分木と、前記単位部分木を固有に識別するための前記インデックスとに対し、相互参照を可能とするポインタをそれぞれ追加して前記異なるパーティションに登録し、
前記分割部は、さらに前記分割位置リストを参照し、前記異なるパーティションに登録するための前記単位部分木を分離するため、前記構造化文書が含む前記単位部分木の開始位置および終了位置とを対応付ける、領域ペアおよび当該単位部分木の前記構造化文書内での記述順を登録する出現カウンタを含む部分木データ・リストを作成し、記憶領域に登録しており、前記構造化文書は、XMLで記述され、前記データベースは、XMLを格納・検索することを可能にするXMLDBである、情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースを対象とする情報処理技術に関し、より詳細には、データベースのデータ領域をパーティションすることによりデータベース・アクセスを効率化する、情報処理装置、データベース・システム、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
インターネットといったネットワーク基盤の普及および情報処理装置やアプリケーション・プログラムの進歩により、情報処理装置が処理可能なコンテンツの種類および量が飛躍的に増大している。このような膨大な量のコンテンツにアクセスするために、リレーショナル・データベースや、オブジェクト指向データベースといったデータベースが利用され、クライアント・コンピュータ（以下、単にクライアントとして参照する。）によるコンテンツの検索を可能とさせている。
【０００３】
データベースは、コンテンツを、マスタ・キーなどにより固有に識別して管理し、従来では、コンテンツが含むキーワードなどから生成した索引を使用して検索を実行し、検索結果としてヒットしたコンテンツまたはコンテンツ・リストをクライアントに返すことによって、クライアントのユーザに対し、コンテンツの提供を可能とする。データベースが管理するコンテンツの量が膨大でなければ、データベースが管理する全文書についてキーワード検索などの検索を実行させても、検索効率には大きな影響はないということができる。
【０００４】
一方、データベースが検索しなければならないコンテンツの量が膨大になり、また、近年では検索対象とするべき索引も全文索引などが使用されるようになってきている。このため、検索効率の効率化を目的としてデータベースのコンテンツに対して区画（以下、パーティションとして参照する。）を割当て、データベースの全体を検索するのではなく、特定のパーティション内での検索の検索空間を削減することで、検索効率を向上させる試みも行われている。
【０００５】
パーティション化は、例えば、１つのテーブルを年月など、区分するべき対象
項目の範囲を区切って項目範囲ごとに同一のパーティションに格納し、パーティションの単位でコンテンツやデータの追加・削除・検索を行うことで、全期間にわたって登録されたコンテンツやデータなどを検索する場合に比較して、高速処理が可能となることが知られている。
【０００６】
また、近年では、リレーショナル・データベースの登録コンテンツやデータをXMLなどの構造化文書として登録する技術も知られている。リレーショナル・データベースに各種のデータを登録する際にXMLといった構造化文書を導入することにより、従来の索引検索技術の他、DOM(Document Object Model)やSAX(Simple
API for XML)などのXMLパーザを併用した検索も可能となり、いわゆるXMLデータベース（以下、XMLDBとして参照する。）も提案され、より効率的なコンテンツ検索が可能とされている。さらに、XMLDBを使用することで、リレーショナル・データベースのスキーマを修正することなく、コンテンツやデータの登録要素を修正でき、スキーマ変更に対して柔軟性を付与することができるという利点も知られている。
【０００７】
図１７は、リレーショナル・データベース(以下、RDBとして参照する。)においてXMLを管理する場合のレコードまたはカラム構造の従来例を示す。RDBによるXMLサポートは、主に、XMLデータをRDBのカラムにマッピングして格納するタイプおよびXMLデータをテキスト・データとして一つのカラムに格納して管理される場合が多い。
【０００８】
図１７に示した従来例では、リレーショナル・データベース１７１０は、所定のレコードを識別するために識別値（ＩＤ）を登録するカラムと、その他の属性値を登録する１つまたは複数のカラムと、XML文書のテキストを登録するカラム１７２０とを含んで構成されている、XML文書のサイズが小さい場合には、カラム１７２０にXMLを登録するだけでも充分に対応することができる。しかしながら、現在、１つのカテゴリのデータを記述するXML文書にサイズは、ますます大きくなる傾向にあり、数Ｇバイトとなる例も知られている。このような場合にXML全体を対象として検索を行うことは、XMLパーザなどの処理を考慮しても効率的なものと言うことにはならない。
【０００９】
サイズの大きなXML文書を効率的に検索するための既存技術がいくつか存在する。例えばリレーショナル・データベース製品のDB2（登録商標）（DB2は、インターナショナル・ビジネス・マシーンズ・コーポレーションの登録商標である。）では、XML文書格納および検索のため、XDA(XML
Data Area)オブジェクト１７４０を生成する。XDAオブジェクト１７４０は、複数の領域１７５０、１７６０に分割し、XML文書に対して特定の領域を索引付ける索引オブジェクト１７３０を構成し、大サイズのXML文書の分割領域にアクセスさせる方法が採用されている。また、XML文書は、全体またはその部分木がそれぞれノード・テーブルとして展開され、ノード・テーブルは、例えば、索引オブジェクトなどとしても使用することができる。
【００１０】
これまで、データベースに対してパーティションを導入する技術が種々知られている。例えば、特開平７−３１９９２３号公報（特許文献１）では、データサーバは、システムにおいて異なるプロセッサを実行し、それらの各SQLステートメントを実行し、同時にかつ並行にそれらのデータベース・パーティションにアクセスし、クライアント・アプリケーションから与えられた要求全体のアクセスタイムを低減させる、方法および装置が記載されている。
【００１１】
また、特開２００１−１４２７５２号公報（特許文献２）では、データベースの格納領域としてｍ個のデータベース格納領域が与えられた場合、データベースの一つ又は複数のデータ項目をパーティショニング・キーとし、データベースを前記パーティショニング・キーに対してハッシュ関数を適用し、ｎ（ｍ≦ｎ）個の論理的な単位であるバケットに分割し、当該与えられたデータベース格納領域数に応じて各バケットを管理するデータベース格納領域の対応を決定するハッシュマップ表と、分配されたバケットを各データベース格納領域内の格納単位であるセグメントとマッピングさせるためのセグメントハッシュマップ表によってデータベースを管理する、データベース管理方法が記載されている。
【００１２】
また、XMLなど、タグを使用する構造化文書を使用するデータベースについては、例えば、特開２００８−１９７８１５号公報（特許文献３）に記載されている。特許文献３では、データベースに登録されるべき文書に対応する元の文書が当該データベースに既に登録されている場合、登録されるべき文書のうち元の文書に対して変更が発生した箇所のデータを差分データとして抽出し、索引処理部は、変更が発生した箇所のみの索引を更新することで、索引作成コストを削減するシステムが記載されている。
【特許文献１】特開平７−３１９９２３号公報
【特許文献２】特開２００１−１４２７５２号公報
【特許文献３】特開２００８−１９７８１５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上述したように、これまで、データベースに蓄積されるコンテンツやデータの検索効率を向上させる目的からデータベースにパーティションを割当てる技術が提案され、また、データベースの管理を効率化する目的で、データベースに階層構造を記述した構造化文書を登録する技術が提案されている。
【００１４】
また、RDBによりXML文書を管理する場合、図１７に示したように木構造に対応付けて領域分割を行う他にも、例えば日付、勤務地、明細項目など、特定の値範囲ごとに全体のデータを分類、いわゆるパーティショニングすることも可能である。XML文書を、特定の属性値によってパーティション化することによって、特定の属性値を含むデータの検索空間を縮小でき、効率的な検索処理が可能となるものと考えられる。
【００１５】
しかしながら、従来のデータベースに対してパーティションを割当てて検索空間を削減する手法を、そのままXMLDBに適用する場合、必ずしも効率的なパーティション方法と言うことはできなかった。すなわち、XML文書は、それ自体でデータの階層構造を有することができる。このため、XML文書に対してパーティションの対象とされる対象データを有する部分木が追加されることも充分に想定することができる。また、XMLDBが管理するデータの同一の属性値で指定される、例えば＜支社ｎａｍｅ＝“”＞などで指定される部分木には、パーティションの対象とされるべき対象データであって、異なるパーティションに分離されるべき部分木が追加される可能性が高い。
【００１６】
したがって、XMLDBでパーティションを行うためには、パーティションの対象とする日付、品名、顧客、勤務先その他の対象データを含む部分木を特定し、特定した部分木についてのみ対象データをパーティション範囲と比較する必要がある。
【００１７】
また、単にパーティション分割しただけでは、XML文書の階層構造が失われてしまい、階層構造を有効利用した検索ができなくなることで、新たな索引データを作成しなければならないという問題点も想定される。
【００１８】
すなわち、これまで、データベースに対するパーティション化の有効性およびXMLを使用するデータ構成の変更の柔軟性の両方を損ねることなく、データベースの検索性を向上させ、ため柔軟なデータ構造の変化に対応することができる技術が必要とされていた。
【課題を解決するための手段】
【００１９】
本発明では、上記従来技術の課題を解決するために、情報処理装置は、構造化文書のパーティション化する対象データを含む単位部分木を、構造化文書内で、識別し、単位部分木を規定する開始タグと、終了タグとを対応付けた領域ペアとして識別する。同時に情報処理装置は、構造化文書中の単位部分木の記述順を示す出現カウンタを生成し、部分木の構造化文書中での位置を識別させる。なお、以降の説明は、対象データを格納するデータベースとしてリレーショナル・データベースを使用するXMLDBを用いて行うが、本発明の実施形態はリレーショナル・データベースを使用するXMLDBに限定されない。
【００２０】
単位部分木は、パーティションを行うための特定の意味を有するテキストを含む階層構造体であり、特定の意味の属性を記述するタグ単位で規定される。単位部分木は、データベース管理者やデータベースにアクセスするユーザが、XPathなどを使用して規定することができる。情報処理装置は、パーティションを行う場合、単位部分木を登録するための値パーティションと、当該単位部分木を参照するインデックスを登録するためのベース・パーティションとを作成する。
【００２１】
その後、情報処理装置は、パーザ部を起動し、属性値を定義する開始タグの位置および終了タグの位置を識別して、属性値の階層構造に対応する分割位置リストを作成し記憶領域に登録する。さらに情報処理装置は、作成した分割位置リストを検索して、構造化文書の単位部分木を認識すると、その単位部分木が開始する、構造化文書中での行位置と、当該単位部分木が終了する行位置とを対応付けて領域ペアを生成する。この領域ペアには、出現カウンタにより、構造化文書中での出現位置が対応付けられて、部分木データ・リストが作成される。
【００２２】
部分木データ・リストが作成されると、情報処理装置は、分割位置リストを参照し、パーティションの対象となる対象データを含む分割するべき単位部分木の前記開始タグ位置および前記終了タグ位置を識別し、単位部分木および単位部分木を参照するためのインデックスを、前記構造化文書から分離して識別し、分離した単位部分木と前記単位部分木を識別するインデックスとを異なるパーティションに登録することにより、パーティション分割を行う。
【００２３】
単位部分木は、複数の開始タグを含み、インデックスは、対応する単位部分木の最初の開始タグから生成され、また、パーティションへの登録に際して、単位部分木および単位部分木を固有に識別するためのインデックスに対し、相互参照を可能とするポインタを追加して登録する。
【００２４】
さらに本発明の情報処理装置は、値パーティションに登録された単位部分木を対象データを使用して検索するためのSQL処理部と、SQL処理部による検索結果を生成する検索結果生成部を含んで構成することができる。本発明では、構造化文書は、XMLで記述することができ、データベースは、リレーショナル・データベースを使用するXMLDBとすることができる。
【００２５】
本発明はまた、上記情報処理装置を含むデータベース・システム、情報処理方法、およびプログラムを提供することができる。
【００２６】
本発明によれば、構造化文書の階層構造による検索効率を損なうことなく、パーティション化による検索空間の削減を可能な、情報処理装置を含むデータベース・システム、情報処理方法、およびプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２７】
以下、本発明を実施形態を以て悦明するが、本発明は後述する実施形態に限定されるものではない。図１は、本実施形態のデータベース・システム１００を示す。本実施形態のデータベース・システム１００は、ネットワーク１２０と、ネットワーク１２０に接続され、ユーザにより操作されて、ネットワーク１２０を介してサーバ１３０にアクセスする複数のクライアント１１０、１１２、１１４、１１８とを含んで構成されている。
【００２８】
サーバ１３０は、本実施形態で、データをXMLなどの構造化文書を使用してパーティショニングを実行し、格納するデータベース・アプリケーションを実装する情報処理装置として機能する。サーバ１３０は、特に限定されるものではないが、データベース・サーバの他、ウェブ・サーバ、ＳＮＳサーバ、メール・サーバなどの機能を併せて実装することができる。本実施形態では、ネットワーク１２０は、インターネットなどのネットワークを含むことが好ましいが、インターネット以外にも、WAN(Wide
Area Network)、LAN(Local Area Network)などを含んで構成されていてもよい。
【００２９】
サーバ１３０は、PENTIUM（登録商標）、PENTIUM（登録商標）互換チップなど、CISCアーキテクチャのマイクロプロセッサ、または、POWER  PC（登録商標）などのRISCアーキテクチャのマイクロプロセッサを、シングルコアまたはマルチコアの形態で実装することができる。また、サーバ１３０は、WINDOWS（登録商標）200X、UNIX（登録商標）、LINUX（登録商標）などのオペレーティング・システムにより制御することができる。さらに、サーバ１３０は、C、C++、JAVA（登録商標）、JAVA（登録商標）BEANS、PERL、RUBYなどのプログラミング言語を使用して実装される、CGI、サーブレット、APACHEなどのサーバ・プログラムを実行し、クライアント１１０〜１１８から送付される、データ登録要求や検索要求などの各種の要求を処理する。
【００３０】
クライアント１１０〜１１８は、パーソナル・コンピュータまたはワークステーションなどを使用して実装でき、また、そのマイクロプロセッサ（MPU）は、これまで知られたいかなるシングルコア・プロセッサまたはマルチ・プロセッサを含んでいてもよい。また、クライアント１０８、１１２、１１４は、WINDOWS（登録商標）、UNIX（登録商標）、LINUX（登録商標）、MAC  OSなど、いかなるオペレーティング・システムにより制御されてもよい。また、クライアント１１０〜１１８は、サーバ１３０にアクセスするため、Internet
Explorer（登録商標）、Mozilla（登録商標）、Opera（登録商標）、Netscape Navigator（登録商標）などのブラウザ・ソフトウェアを実装することができる。
【００３１】
クライアント１１０〜１１８と、サーバ１３０との間は、TCP／IPなどのトランザクション・プロトコルに基づき、HTTPプロトコルなどのファイル転送プロトコルを使用するトランザクションを使用したネットワークで接続されている。また、クライアント１１０〜１１８は、サーバ１３０のデータベース・アプリケーションにアクセスするために、JDBC(Java（登録商標）Database
Connectivity)を実装し、JDBCで定められるアプリケーションレベル・プロトコルで、サーバ１３０に接続してもよい。
【００３２】
サーバ１３０は、クライアント１１０〜１１８が送付した要求に対応して、サーバ１３０が管理するデータベースに対して要求に対応した処理、例えば受領したデータを、データベース１４０に格納し、さらにデータを特定の属性値に対応してパーティショニングを実行して、登録する処理を実行する。また、クライアント１１０〜１１８から受領した要求が、検索要求である場合、サーバ１３０は、データベース１４０に対してSQL(Structured Query Language)を発行し、本実施形態では、パーティショニングに関連する属性を検索要求が含む場合には、パーティション単位で、XMLなどの構造化文書で登録されたデータ検索処理を実行する。
【００３３】
また、パーティショニングに関連する属性を含まない検索要求の場合には、従来と同様のSQL文を使用した検索処理を実行する。なお、構造化文書としてXMLを本実施形態では例示的に説明するが、SGML、XHTML、拡張XML(Enhanced XML)など特にXMLに限定されるものではない。
【００３４】
データベース・アプリケーションとしては、例えば、DB2（登録商標。）（DB2は、インターナショナル・ビジネス・マシーンズ・コーポレーションの登録商標である。）、ORACLE（登録商標）、MySQL、ACCESS（登録商標）などのいわゆるリレーショナル・データベース(RDB)を採用することができる。本実施形態のデータベース・システム１００のデータベース・アプリケーションは、データベースに、パーティショニング処理を実行するためのパーティション・モジュールを拡張機能として追加実装する。
【００３５】
図２は、本実施形態のサーバ装置１３０の機能ブロック２００を示す。図２に示した各機能ブロックは、サーバ１３０のプロセッサが各機能部を実装させるためのプログラムをＲＡＭなどの実行空間に読出して、プロセッサがプログラムを実行することにより、情報処理装置の機能手段として機能させることにより情報処理装置上に実現させている。サーバ１３０は、ネットワーク１２０を介してクライアント１１０〜１１８からの要求を受領する。要求は、ネットワーク・アダプタ２０２により受領され、ＯＳＩ参照モデルにおける、物理層、データリンク層、トランスポート層、ネットワーク層を介してより上位プロトコルのアプリケーションに渡され、アプリケーション層を介してデータベース・アプリケーションへと要求およびデータが渡される。
【００３６】
サーバ１３０は、本実施形態の処理を実行するため、SQL処理部２１０と、検索結果作成部２１６と、データ管理部２２０とを含んで構成されている。SQL処理部２１０は、XML文書の階層構造を指定した検索を可能とするSQLコマンドを処理し、検索結果を生成する。図２に示す実施形態では、SQL処理部２１０は、SQLパーザ２１２と、XMLパーサ２１４とを含んでいる。SQLパーザ２１２は、受領した検索要求に対応するSQLコマンドを解析し、SAXなどを含んで実装されるXMLパーザ２１４による検索を可能とする。
【００３７】
検索結果作成部２１４は、データベース１４０からXMLパーザ２１４が抽出した結果を取得して、値パーティション検索結果として表示するためのフォーマットを、例えば、XML文書またはテーブルなどの適切なフォーマットで作成し、ネットワーク・アダプタ２０２を介してクライアントに返却する処理を実行する。
【００３８】
さらにサーバ１３０は、データ管理部２２０を備えている。データ管理部２２０は、本実施形態に従い、データベース・アプリケーションの機能拡張モジュールとして実装でき、パーティション生成部２２２と、XMLパーザ２２４と、XML分割部２２６と、分割XML登録部２２８とを含んで実装することができる。パーティション生成部２２２は、データベース１４０の管理上、データベース管理者がパーティションを設定する対象データ、例えば、日付、顧客名、商品名、勤務地、所属などの値について設定される範囲を使用してパーティションを生成する処理を実行する。
【００３９】
また、データベース１４０が、例えばMySQL、ACCESSなど、プライベートレベルでデータの作成などでアクセスが許可される場合では、ユーザが自己の管理するべきデータの対象データに対応するパーティションを作成するため、例えば、「パーティション作成」要求を発行し、サーバ１３０が、当該要求を受領して、要求されたパーティションを作成することもできる。
【００４０】
なお、データベース管理者やユーザが発行するパーティション作成要求には、パーティション分割するXML文書の部分木を、パーティション分割の粒度を規定するために記述することができる。以下、パーティション分割する粒度となる部分木を、単位部分木＝Pとして参照する。単位部分木は、例えばP＝*／a／b／c...として規定することができる。なお、「*」は、ワイルドカードであり、a、b、cは、単位部分木内で属性および属性値が定義されたタグを意味する。
【００４１】
また、XMLパーザ２２４は、本実施形態では、パーティションの対象とする構造化文書の構造解析を実行するパーザ部として機能し、処理対象とするXML文書をクライアント１１０〜１１８またはデータベース１４０から取得し、パーティションごとにXML文書の単位部分木を分割するためのプリプロセッサとして機能する。XMLパーザ２２４は、この目的のため、XML文書中で、ノードの属性を規定するタグを含む行位置を識別して分割位置リストを生成し、ＲＡＭなどの適切な記憶領域に格納する。なお、XMLパーザ２２４についても、DOMまたはSAXを含んで実装することができ、その機能が異なるためにXMLパーザ２１４と別の機能部として説明するが、ソフトウェア上の構成としては単独のXMLパーザを利用して機能させることができる。
【００４２】
さらにデータ管理部２２０は、XML分割部２２６と、分割XML登録部２２８とを含んで構成されている。XML分割部２２６は、XMLパーザ２２４が取得した、処理対象のXML文書の分割位置リストを使用して、処理対象のXML文書を、単位部分木を粒度としてパーティションに分割して行く。また、XML分割部２２６は、XML文書のパーティションに分割された単位部分木の元のXML文書における階層構造を指定する情報を登録するため、単位部分木を識別するためのインデックスを生成し、XML文書および単位部分木から分離する処理を実行する。
【００４３】
以下、日付など対象データごとに分類されたパーティションを、値パーティションとして参照し、値パーティションに分類登録された単位部分木の元のXML文書に紐付けするインデックスを登録するパーティションを、ベース・パーティションとして参照する。なお、ベース・パーティションには、XML文書がパーティション対象となる部分木を含む場合、当該パーティション対象外の部分木も登録される。また、単位部分木およびインデックスを該当するパーティションに登録する際に、
【００４４】
分割XML登録部２２８は、XML分割部２２６が分割した結果を使用して単位部分木およびインデックスなどを対応するパーティションに登録する。分割XML登録部２２８は、元のXML文書における階層レベルと、パーティション分割された単位部分木との間の階層構造を相互参照することを可能とするため、固有の相互参照識別値をそれぞれベース・パーティションに登録するべきインデックスおよびパーティション分割するべき単位部分木に対してそれぞれ追加する。相互参照識別値についてはより詳細に後述する。
【００４５】
図３は、本実施形態のサーバ１３０が処理対象とするXML文書３００の実施形態を示す。図３に示したXML文書３００は、所定の企業の受注データであり、支社ごとに、支社情報と、受注識別値と、顧客情報と、受注内容を記述する明細とが、各タグによって識別される階層構造を有するXML文書として記述されている。XML文書３００の＜支社name＝“A”＞で指定される親ノードには、複数の、＜受注伝票＞タグで指定される子ノードが含まれており、図３に示す例示的な実施形態では、＜支社name“Ａ”＞の属性が宣言された親ノードには、子ノード３１０と、子ノード３２０とが含まれているのが示されている。
【００４６】
なお、図３に示した実施形態は例示的なものであり、親ノード＜支社name＝“A”＞については、さらに多くの子ノードが記述されていてもよく、対象とするXML文書は、数万行からなるデータを含んでいてもよい。図３に示されるように、各子ノードは、＜日付＞タグが含まれている。これらの対象データを記述するタグはデータタグであり、属性を定義するタグを、属性定義タグとして参照する。説明する本実施形態では、パーティションの対象データは、日付であり、例えば日付に対して会計年度などの範囲を割当て、値パーティションに分類するものとして説明する。また、属性定義タグは、＜支社name＝“Ａ”＞、＜受注伝票  番号＝“０００１”＞、＜明細  行＝“１”＞などを意味する。なお、パーティションを生成する範囲は、会計年や、出版年の他、アメリカ、日本、中国などの地理的範囲でもよいし、「a−d」、「e−f」などの文字範囲でもよい。
【００４７】
図４は、本実施形態のXML文書３００を、木構造４００として示した図である。図４に示すように階層構造４００は、「支社A」を親ノード４１０とし、「受注伝票０００１」ノード４２０および「受注伝票０００２」ノード４３０が、それぞれ支社Aノード４１０の子ノード４２０、４３０として含まれている。図３に示すように、日付データをパーティションの対象とする場合、子ノード４２０と、子ノード４３０とが異なる会計年度のパーティション４７０、４８０に分割されることになる。
【００４８】
図４に示すように、パーティション対象の対象データを含む複数の子ノードが存在する場合、通常では、子ノードごとに対象データの値が異なる。したがって、パーティション対象の子ノードを階層構造の中から分割し、分割単位で、値パーティションに登録する処理を実行することが必要となる。このため、従来のリレーショナル・データベースで行われているように、単位部分木の単に対象データを検出し、パーティションに分類する処理では、元のXML文書の階層構造が失われ、XMLDBの有効性が損なわれてしまうことになる。このため、値パーティション４７０、４８０に含まれる子ノードの、XML文書３００内でのXPathを指定することが必要となる。
【００４９】
本実施形態では、XML文書３００から値パーティション４７０、４８０にパーティション分割された子ノードを記述する部分木に対し、元のXML文書の階層構造を指定するペース・パーティション４６０を生成させ、パーティション化による検索効率の向上を、XMLDBの有効性を損なわずに可能とする。ペース・パーティション４６０は、元のXML文書での子ノードの階層構造におけるレベルを維持させ、かつ、特定の子ノードに対応する単位部分木の参照を可能とする。
【００５０】
図５は、本実施形態のサーバ１３０が実行するXMLDBに対する処理の概略的なフローチャートを示す。図５の処理は、ステップＳ５００から開始し、データベース管理者またはクライアント１１０〜１１８からのパーティション要求指令を受領して開始する。ステップＳ５０１で、サーバ１３０は、指定されたデータの範囲に対応する値パーティションを作成する。ステップＳ５０１のパーティションの作成は、リレーショナル・データベースのDDL(Data
Definition Language)を、XMLに対応可能に処理できるように拡張したSQLスクリプトを使用して作成することができる。
【００５１】
ステップＳ５０２では、処理対象とするXML文書を読出して構文解析を実行し、XML文書から単位部分木を分割後、パーティションする単位部分木をその出現順に対応付けた部分木データ・リストを作成する。その後、ステップＳ５０３では、リストした単位部分木についてポインタを埋込んでパーティションに登録する。なお、ポインタの埋込みは、単位部分木の開始タグに、例えば隠し属性として埋め込むことができる。また、他の実施形態では、索引などに使用されるノード・テーブルの当該部分木に対応する値を格納するレコードに追加することができる。ポインタおよびポインタの埋込み処理については、より詳細に後述する。
【００５２】
本実施形態のXMLのパーティション分割の処理は、ステップＳ５０４で終了する。なお、ステップＳ５０２〜Ｓ５０４の処理は、リレーショナル・データベースにすでに格納されているXMLを対象とすることもできるし、サーバ１３０に対して新たな登録を要求して送付されたXML文書に対しても適用することができる。
【００５３】
図５のステップＳ５０４からは、XMLDBに対する検索処理であり、ステップＳ５０４で、サーバ１３０がクライアント１１０〜１１８から、検索要求を受領する。ステップＳ５０５で、検索要求にパーティションを生成した対象データが含まれているか否かを判断し、パーティションを行った対象データが含まれると判断した場合（Ｙｅｓ）、ステップＳ５０７で、検索要求で指定される対象データを分類したパーティションのみを検索し、ステップＳ５０８で、検索結果を検索要求を発行したクライアントに返し、ステップＳ５０９で処理を終了する。
【００５４】
一方、ステップＳ５０５で、パーティションした属性値を含まない検索要求であると判断した場合（Ｎｏ）、ステップＳ５０６でパーティションにわたって検索を実行し、ステップＳ５０８でパーティションにまたがった結果をマージして検索結果を作成し、検索要求の発行元のクライアントに返し、ステップＳ５０９で処理を終了する。なお、ステップＳ５０６で、値パーティションの個別検索の他、ベース・パーティションの検索も必要な場合、ステップＳ５０８で、値パーティションの検索結果と、ベース・パーティションの検索結果とを個別にマージして検索結果を生成することもできる。
【００５５】
なお、パーティション後の検索結果のマージは、従来のリレーショナル・データベースのパーティション分割されたデータの検索結果のマージ処理を実行する処理を使用して実装することができる。
【００５６】
図６は、本実施形態において、サーバ１３０が、図５のステップＳ５０１でパーティションを生成する処理を実行するためのDDL文６００の実施形態を示す。DDL文６００は、「CREATE TABLE」により支社受注管理のテーブルを作成することを指令し、当該支社受注管理のテーブルを固有に識別するIDを指定し、対象とするXMLの属性を指定した後、「PARTITION
BY RANGE」によりパーティショニングを指令する。図６に示したDDL文６００では、「PARTITION BY RANGE」コマンドの項目引数として、XMLのXPathを指定することか可能とされており、図示する実施形態では、読み込んだXML文書のXPathのパーティション分割するための必要なXPath深度が指定される。DDL文６００は、読込んだXML文書を、XML文書に登録された＜受注伝票＞から開始する子ノードのうち、最古のデータから、２００６／１２／３１までの値パーティションと、２００７／０１／０１から２００７／１２／３１までの値パーティションと、２００８／０１／０１から開始し、２００８／１２／３１で終了する値パーティションの３つの値パーティションを生成する。
【００５７】
図６に示したDDL文６００には、ベース・パーティションを作成する明示的なコマンドは記述されていない。ベース・パーティション作成は、XML文書のレンジ分割のXPathが、図６中、(INFOXML／支社／受注伝票／日付)で設定されると、ベース・パーティションに格納するべきXMLの部分木の断片、すなわち、どの日付パーティションにも入らない部分木およびパーティション分割した単位部分木のインデックスが、分割アルゴリズムによって決定される。レンジ分割サーバ１３０は、PARTITION BY RANGE (INFOXML／…）の引数設定を識別した段階で、ベース・パーティションを登録するために、XMLDB中のデータ保管構造を定義しておくだけでよい。
【００５８】
なお、PARTITION
BY RANGEおよびパーティション分割の処理は、例示的な目的で、データベース１４０としてDB2を使用する場合について説明するものであり、他のリレーショナル・データベースで採用される各種の適合形式に対して適宜変更することができることはいうまでもないことであるし、特定のリレーショナル・データベースの実装形式またはXML分割処理の実装上の都合に応じて、ベース・パーティションを生成する明示的なコマンドを採用することもできる。
【００５９】
なお、タグのうちのどのタグの階層までをパーティション設定に利用するかについては、値パーティションの定義と直接関連し、本実施形態では、DDL文６００の引数として設定された、（INFOXML／支社／受注伝票／日付）の深度に対応するタグ、具体的には、＜日付＞タグをパーティション設定に指定することができる。なお、DDL文で規定するXPathの深度は、値タグを明示的に記述する他、「＊」などのワイルドカードを使用して暗示的に指定することもでき、深度およびXPathの階層構造に一致している限り特に限定されない。
【００６０】
図７は、本実施形態のXML分割を実行する、図５のステップＳ５０２のより詳細なフローチャートを示す。図７の処理は、ステップＳ７００で、図５のステップＳ５０１から制御を渡されて開始し、ステップＳ７０１で、XML分割位置の算出を、XMLパーザを呼び出して実行する。ステップＳ７０１の処理は、より詳細には後述するが、XMLパーザ２２４がXML文書を読み込んで、パーティションするための子ノードを識別するための分割位置を計算し、当該分割位置を指定する分割位置リストを生成する処理である。生成された分割位置リスト７１０は、ＲＡＭなどの適切な記憶領域に格納され、パーティション分割処理が終了するまで、サーバ１３０が保持する。
【００６１】
ステップＳ７０２では、分割位置リスト７１０を参照して、XML文書を構成する子ノードのうち、パーティションに分類する対象データを有する単位部分木に分割して、当該単位部分木を識別するための領域ペアおよび出現カウントを生成し、部分木データ・リストの生成および単位部分木の分割、インデックス生成処理を実行する。その後、ステップＳ７０３では、生成された単位部分木のパーティション対象の値を含むタグおよびベース・パーティションに登録するべきインデックスに対して埋め込むためのポインタを、それぞれ生成する。なお、生成するポインタは、データベース１４０内でインデックスおよび単位部分木を固有に紐付けるための値することができる。
【００６２】
この目的で、ポインタとして例えば、単位部分木に対し、インデックスを固有に識別するインデックス・ポインタを埋込み、インデックスには、単位部分木を固有に識別する子ノード・ポインタを埋込むことができる。なお、インデックス・ポインタは、ベース・パーティションにおけるインデックスの登録番号、格納アドレスなどを使用することができる。また、単位部分木についても、当該値パーティション内での登録番号や格納アドレスなどを使用することができる。
【００６３】
ステップ７０３のポインタの埋込みを実行する場合には、ステップＳ７０２のXML分割処理によってインデックスおよび単位部分木が生成されるごとに登録番号や、格納予定アドレスなどを割当てておき、各ポインタを対応付けたポインタ対応付けテーブル７２０を生成し、ベース・パーティションおよび値パーティションへの登録の際、ポインタ対応付けテーブル７２０を参照しながら並列的に登録する処理を使用することができる。
【００６４】
また、ポインタ対応付けテーブル７２０は、値パーティションに登録するべき単位部分木が特定できた段階で、インデックスおよび単位部分木に登録するべき最新のポインタを対応付けたリストとして構成することもできる。ポインタ対応付けテーブル７２０は、ポインタ埋込み処理が終了した時点でメモリから削除することもできるが、検索処理のための索引データとして使用する目的で、「CREATE TABLE」で作成したテーブルの索引として、図６のIDに紐付けして、処理期間中、キャッシュしておくことができる。
【００６５】
図７の処理は、ポインタ生成・埋め込み処理を終了して、ステップＳ７０４に到達すると、図５のステップＳ５０３に制御を渡し、処理を終了する。
【００６６】
図８は、ステップＳ７０３の処理XML分割位置算出処理の詳細なフローチャートである。図８の処理は、図７の処理が呼出されることにより起動され、ステップＳ８００から開始し、ステップＳ８０１で、i＝0、
Path＝／、 Start＝／(0)、 End＝-1、Count＝φ、CutRangeSet＝φ、isPrevEnd＝falseを初期化する。なお、上記各変数は、下記表１の通り定義する。
【００６７】
【表１】
2010129001.tif 000003
【００６８】
ステップＳ８０１で、各変数の値を初期化した後、ステップＳ８０２で、処理対象のXML文書にまだ読み込むべき開始タグまたは終了タグが存在しているか否かを判断し、読み込むべきタグが残されていない場合（Ｎｏ）、XML文書の最後まで処理を進めたものとして、ステップＳ８０７で処理を終了する。
【００６９】
一方、ステップＳ８０２で、処理対象のXML文書Ｄにまだ読み込むべきタグが存在していると判断した場合（Ｙｅｓ）、ステップＳ８０３で、タグ名を変数Tagに読み込み、Path＝Path+“／”+Tagを計算し、タグの位置番号を１インクリメントする。ステップＳ８０３の処理で、特定の開始タグから、終了タグまでの間のXPathが生成されて行く。ステップＳ８０４で、変数Tagの値が、開始タグか否かを判断し、開始タグである場合（Ｙｅｓ）、ステップＳ８０６で開始タグ処理を実行する。また、ステップＳ８０４で、変数Tagの値が開始タグではない場合（Ｎｏ）、ステップＳ８０５で、終了タグ処理を実行し、ステップＳ８０５およびＳ８０６の各タグ処理が終了すると、処理をステップＳ８０２に戻して、XML文書Ｄの全タグについて処理を終了するまで、処理を反復させる。
【００７０】
図９は、図８のステップＳ８０５およびステップＳ８０６の開始タグ処理および終了タグ処理の詳細なフローチャートを示す。ステップＳ９００からステップＳ９０８までが開始タグ処理であり、ステップＳ９１０〜ステップＳ９１７までが終了タグ処理である。まず、ステップＳ９００〜Ｓ９０８の開始タグ処理から説明する。
【００７１】
開始タグ処理は、ステップＳ９００でステップＳ８０４から制御を渡されて開始し、ステップＳ９０１で、Count＝Count+(0)でcountスタックに０を登録する。ステップＳ９０２で、Path＝Ｐか否かを判断し、現在読んでいるＤのタグのXPathが、値パーティションに分割する単位であることをPath＝Pか否かにより判断し、Path＝Pでない場合（Ｎｏ）、処理をステップＳ９０４に分岐させ、ステップＳ９０４で、現在保持する分割位置候補を出力すべきかどうかを、「Count
の先頭要素が１以上で、かつEnd≧0」か否かの判断を使用して実行する。ステップＳ９０４で、Count の先頭要素が0かまたはEnd≧0ではない場合（Ｎｏ）、ステップＳ９０６に処理を分岐し、変数End＝−１、すなわち終了タグが終了候補であるか否かを判断する。End＝−１である場合（Ｙｅｓ）、ステップＳ９０７でStart＝Path+(i)として、Start位置番号を進め、ステップＳ９０８で、制御を図８のステップＳ８０２に渡し、処理を終了する。
【００７２】
一方、ステップＳ９０２の判断で、Path＝Pである場合（Ｙｅｓ）、ステップＳ９０３で、Countのすべての要素に１を加え、ステップＳ９０４で、「Count
の先頭要素が1以上で、かつEnd≧0」か否かを判断する。この場合には、ステップＳ９０４の判断は肯定的な値を返す（Ｙｅｓ）ので、ステップＳ９０５で変数CutRangeSetに（Start位置番号、End位置番号）を追加し、End＝−１に設定する。ステップＳ９０６では、End＝−1か否かを判断する。この条件下では、ステップＳ９０６の判断は、肯定的な結果を返すので（Ｙｅｓ）、ステップＳ９０８で、Start位置番号を進め、ステップＳ９０８で、制御を図８のステップＳ８０２に返し、処理を終了する。
【００７３】
一方、図８の終了タグ処理は、ステップＳ９１０で、ステップＳ８０４の判断で、変数Tag内の値が、開始タグではないと判断されたことに対応して呼び出されるステップＳ９１０から開始し、ステップＳ９１１で、Countの先頭の値が１以上であるか否かを判断し、Countの先頭の値が、１以上である場合（ｙｅｓ）、ステップＳ９１２で、次の開始タグの検出に対応するためにEnd＝iに設定し、ステップＳ９１３でStartの上位要素を取り除き、ステップＳ９１４で、Countの上位要素を取り除く。なお、Startの上位要素を取り除く処理およびCountの上位要素を取り除く処理については、図１０を使用してより詳細に後述する。
【００７４】
ステップＳ９１５で、Countの先頭要素が、２以上である場合、現在判断しているTagの値は、その親タグの下に既に出現済みであることを示すので、ステップＳ９１６でCutRangeSetに(Start位置番号およびその時点で判断している変数Tagの位置番号をEndとして領域ペアとして対応付けて追加する。その後、処理は、ステップＳ９１７から図８のステップＳ８０２に制御を渡し、終了する。
【００７５】
図１０は、図９のステップＳ９１３で実行するスタックStartに対する上位要素を取り除く処理の説明図である。スタックStartは、XPath＝Pが含むタグのうち、分割するべき子ノードを識別するために必要なタグに対応して、積み重ねられて行き、分割するべき子ノードの終了タグを検出することにより、子ノードの先頭を識別する機能を有する。スタックStartは、XMLパーサ２２２のファーストランで、対象とするXML文書のタグを解析し、XML中の特定の行番号がどのタグを含むかを識別して、分割位置リスト７１０の形式で、適切な記憶領域に登録する。
【００７６】
XML分割部２２６は、XMLパーザ２２２が生成した分割位置リスト７１０を読み込んで、Startに追加する。その処理のため、XML分割部２２４は、XMLパーザ２２２を再度起動してセカンドランを実行させ、まず、最初のrootタグを発見した段階で、rootタグおよびその位置番号をスタックに登録する。さらにその後、タグを検出するごとに、スタックに当該タグおよび位置番号を登録する。例えば、行番号＝５まで処理すると、タグ＝＜ｃ／＞が検出される。XML分割部２２４は、分割単位とするXPath＝P＝*／ｂ／ｃを識別して、タグ＜ｃ＞を検出するまで、スタックにタグおよび位置番号を追加して行く。この結果行番号＝４にまで処理が進行した時、スタックStartは、値スタック１０２０を登録する。なお、分割単位は、単位部分木を与える属性定義タグを記述するものとする。また、分割単位は、説明する実施形態の通り、ワイルドカードを使用して記述することもできるし、rootから最初の単位部分木の最終の属性定義タグまでを記述して規定することもできる・
【００７７】
なお、＜ｃ＞が検出された場合、タグ＜ｃ＞が検出された位置番号を、最上位スタックに追加する。タグ＜ｃ＞に対応する終了タグ＜／ｃ＞が検出され、説明する実施形態では、その後タグ＜／ｂ＞を検出した時点で、分割対象とする単位部分木を検出したものとして、スタックStartの上位２カラム１０４０を取り去り、対応する直前の開始タグ＜ｂ＞の位置番号を最上位スタック１０５０として追加し、値スタック１０３０を生成する。この時、変数Tagには、位置番号＝６が登録されている。単位部分木は、スタックの最上位に登録された位置番号からその時点で変数Tagに登録されている値までの間の区間として設定される。説明する実施形態では、第１の領域ペア＝（３、６）として取得される。
【００７８】
その後、値スタック１０３０には、検出された、タグ＜ｂ＞およびその位置番号で、同一のタグを登録するカラムの値が更新され、位置番号＝８で、タグ＜ｃ＞が検出されると、値すタック１０６０が値すタック１０２０と同様にして作成される。さらに処理が進行し、＜／ｂ＞タグが検出されると、上述した値スタック１０２０に対して実行したと同様の処理を実行し、上位２カラム１０７０を取り去り、対応する直前の開始タグ＜ｂ＞の位置番号を最上位スタック１０９０として追加し、値スタック１０８０を生成する。
【００７９】
この処理が実行された時点で、第２の領域ペア＝（７、１０）が決定される。以上の処理を、処理対象のタグがなくなるまで、または＜／root＞タグが検出されるまで実行し、処理対象のXML文書を、単位部分木に分割して行く。分割した結果は、部分木データ・リストとして、サーバ１３０の適切な記憶空間に格納される。
【００８０】
図１１は、図９の処理による本実施形態で実装するスタックCountの更新処理の概略図および生成される値スタックの値遷移１１００の実施形態を示す。図１１に示すスタックに登録される値は、XPathに依存して値スタックが更新されて行き、分割対象とするXPathの最後の開始タグは、処理対象のXML文書が含む分割対象のXPathのパス・カウンタとして機能する。説明する実施形態では、XPath＝P＝*／b／cである。サーバ１３０のXML分割部２２６は、XMLパーザ２２４のセカンドランの時点で、図１０に示すStartを生成するのと並列的に、Countを生成して行く。
【００８１】
XMLパーザ２２４のセカンドランで、XPathに含まれるrootタグを検出することで値スタックの登録を開始し、後続するXPathの開始タグを検出するごとに、新たなスタックを追加し、値＝0を登録して行く。処理を進め、XPathの最後の要素の開始タグを検出すると全スタックの値にカウント＝１を加える。この段階で値スタック１１１２が生成される。
【００８２】
その後、さらにXMLパーザ２２４のセカンドランで、次の開始タグが検出されるまで、上位のスタックの値を削除して行き、XPathを構成する開始タグが検出された時点で、最下位のスタックの値として0を登録して行く。そしてXMLパーザ２２４の処理の進行にしたがってXPathを構成する最後の構成タグが検出された時点で再度、スタックの値に１を加算することで、値スタック１１１４が生成され、最下位スタックの値が、処理中のXML文書内で検出された単位部分木の数を与えることが分かる。その後同様の処理を繰り返し、行番号１１番目まで達すると再度値＝0のスタックが積み重ねられて行き、行番号１４のタグ＜ｃ＞の検出で、カウント＝１が全スタックに加算され、第３の領域ペア（１３、１６）が出力され、最終的に行番号１８の＜／root＞が検出されると、値スタックは全部が削除され、処理の終了が検出される。図１１に示すXML文書には、単位部分木が３つ存在することが判断される。
【００８３】
図１２は、図９〜図１１の処理で生成された、XML分割を行うための部分木データ・リストの実施形態を示す。図１２に示した実施形態では、XML文書の対応する行との対応関係を明確にするべく、分割位置リスト７１０に対応付けて部分木データ・リスト１３００のデータ構造を示す。図１２に示されるように、XML分割部２２６の処理によって、分割対象のXML文書が含む子ノードを識別するための集合変数CutRangeSetには、XML文書の構造にしたがって、順次（３、６）、（７、１０）、（１３、１６）として単位部分木の範囲が登録されて行く。
【００８４】
部分木データ・リストには、開始タグ処理および終了タグ処理で生成された、StartスタックのデータおよびCountスタックの値、Endの値などが登録されていて、以後の単位部分木のXML文書内での階層構造を含めてパーティション分割する場合のデータを提供する。
【００８５】
本実施形態のサーバ１３０は、図１２のCutRangeSetに登録された行番号を使用して、ベース・パーティションに登録するべきXML文書の部分木を識別して行き、XML分割部２２６によるベース・パーティションおよび値パーティションにパーティションするべき部分木の分割を終了する。
【００８６】
図１３は、ベース・パーティションに分割する部分木を生成する処理のフローチャートを示す。図１３の処置は、単位部分木の特定が終了し、図１２のデータ構造が構築された後に呼出されてステップＳ１３００から開始し、ステップＳ１３０１で、i、j、T、Baseの各値を初期化する。i、jは、単位部分木をカウントするカウンタであり、ｉは、行番号を意味し、ｋは、単位部分木の番号、すなわち、Countの先頭の値に対応する。また、Tは、単位部分木を登録するスタックであり、Baseは、ベース・パーティションに登録するXML文書の部分木を登録するスタックである。
【００８７】
ステップＳ１３０２では、XMLパーザ２２４を呼び出して、分割位置リスト７１０を処理し、Ｄにまだ読み込むべきタグがあるか否かを判断し、処理するべきタグがない場合（Ｎｏ）、処理対象のXML文書に対する処理が終了したので、ステップＳ１３１３でその時点までに生成されたベース・パーティションに登録するべき部分木および値パーティションに登録するべき単位部分木にそれぞれポインタを追加して、各パーティションに登録する。
【００８８】
一方、ステップＳ１３０２でまだ読み込むべきタグがある場合（Ｙｅｓ）ステップＳ１３０３で、処理中のタグを変数Tagに読込み、カウンタiを１だけインクリメントする。ステップＳ１３０４では、j＞kまたはi＜bjであるか否かを判断する。この処理は、単位部分木の範囲を効率的に処理するために採用される。ステップＳ１３０４の判断で、j＞kまたはi＜bjの場合(Ｎｏ）、ステップＳ１３０５で、i＜ejであるかを判断し、i＜ejである場合（Ｙｅｓ）、処理中の行位置は、特定の子ノードの範囲に含まれているのでステップＳ１３０６で、T＝T∪TagとしてスタックTに追加する。
【００８９】
また、ステップＳ１３０４でj＞kまたはi＜bjの場合(Ｙｅｓ）、処理中の行位置は、単位部分木に含まれないので、処理鵜をステップＳ１３０８に分岐させ、Base＝Base∪Tagとして追加する。一方、i＜ejでない場合（Ｎｏ）には、現在処理中の行位置が特定の子ノードの範囲外となっているので、ステップＳ１３０９で、j＝j+1としてカウンタjをインクリメントし、Base＝Base∪Tagとする。この段階で、スタックBaseには、処理中の行番号のタグが登録される。その後、T＝φに再初期化する。
【００９０】
ステップＳ１３０９の処理後、ステップＳ１３０６で、T＝T∪Tagに設定する。この処理の場合、ステップＳ１３０９を経たTは、T＝φに初期化されているので、Ｔには、単位部分木に対応する部分木が蓄積されて行く。ステップＳ１３０６の処理後。ステップＳ１３０７では、i＝bjか否かを判断し、i＝bjの場合（Ｙｅｓ）、現在処理中の行位置が、単位部分木の先頭行に対応する位置なので、なお、ステップＳ１３０９で、i＝bjまたはi＝ejの場合、当該タグ情報を、インデックスとしてベース・パーティションの登録候補としてステップＳ１３０８で、Base＝Base∪Tagとして登録し、処理を再度ステップＳ１３０２に戻し、Ｄの残余タグがなくなるまで処理を繰り返す。
【００９１】
一方、ステップＳ１３０７でi＝bjではない場合（Ｎｏ）、ベース・パーティションに登録するべき行ではないので、処理をステップＳ１３０２に直接戻し、Ｄ中に処理するべきタグがなくなるまで処理を反復させる。以上の処理を処理対象のXML文書の、ベース・パーティションに登録するべき部分木および単位部分木として登録するべき部分木を分離することができる。
【００９２】
XML文書の分割が終了した時点で、XML登録部２２８が呼出され、ポインタの追加および各パーティションへの単位部分木の登録が行われる。図１４は、本実施形態のパーティション分割の実施形態を示す。本実施形態の処理によって、図３に示したXML文書３００は、ペース・パーティション１４１０と、各値パーティション１４２０、１４３０にパーティショニングされる。本実施形態では、ベース・パーティションと、値パーティションとにXML文書を分離する際にも、本来のXML文書の階層構造を維持させるために、パーティション分割された単位部分木とインデックスとを相互参照させるため、ポインタを生成し、インデックスおよびインデックスに対応する単位部分木の行位置にそれぞれポインタを生成し、登録する。
【００９３】
ポインタは、各パーティションごとに固有の値が設定され、ペース・パーティションのインデックスには、対応する単位部分木に割当てられたポインタが登録され、単位部分木には、ベース・パーティションのインデックスに対して割当てたポインタを登録する。ポインタを生成する処理は、種々の実施形態が採用できる。例えば、ベース・パーティションおよび値パーティションを生成する際に、各パーティションに追加された部分木の行番号などをカウントするカウンタを設けておく方法を用いることができる。
【００９４】
この実施形態では、ベース・パーティションにインデックスを追加する場合にカウンタの値Cb(Count_base)を取得し、対応する単位部分木については、登録するべき値パーティションにおけるインデックスに対応するカウンタの値Cv(Count_value)を取得し、インデックスには、ポインタCvを追加し、インデックスに対応する単位部分木には、ポインタCbを追加する処理を実行することができる。
【００９５】
また、ポインタとしては、上述したようにパーティションごとに関連付けられた値を生成して追加する実施形態の他、インデックスおよび当該インデックスにより参照される単位部分木の登録処理を行う場合に、それぞれランダムにポインタRb(Random_base)およびRv(Random_value)を生成し、それぞれ対となる行に追加してもよい。ポインタの埋込についても種々の形式を採用することができる。例えば、ポインタ埋込み処理の第１実施形態では、インデックスまたはインデックスに対応する単位部分木のXMLタグの隠し属性として、インデックスおよび単位部分木の対応するXMLタグにポインタの値を埋込むことができる。
【００９６】
例えば、図１４では、ベース・パーティション１４１０の＜受注伝票＞タグ１４５０に、ptr＝“2006:467”を、＜受注伝票＞タグ１４６０に、ptr＝“2007:8152”を隠し属性値として追加する実施形態である。これに対応して、ベース・パーティションのインデックスのポインタであるb:344は、単位部分木の対応する＜受注伝票＞タグ１４７０の隠し属性値に、parent_ptr＝“b:344”として追加されている。本実施形態では、既存のXMLDBの実装に依存することなく、また検索処理のため、追加のアプリケーションを必要とすることなく、低コストで、既存のXMLDBへの実装が可能となる。
【００９７】
また、ポインタを埋込む第２の実施形態では、既存のXMLDBの実装構成を修正する、XMLDBのために作成するノード・テーブルのレコードに、該当するポインタの値を追加して埋込む実施形態である。この実施形態では、複数のパーティションがポインタを追加したタグを含むことを排除できるので、ハードウェア・リソースの消費という観点では負担が少ない方法である。しかしながら、既存のXMLDBのノード・テーブル登録処理についても修正を加えることが必要とされるので、XMLDBの実装構成の修正も伴うため、XMLDBの実装段階からパーティショニングを行う場合には好ましく使用することができる。
【００９８】
図１５は、本実施形態にしたがってパーティション分割されるXML文書と、パーティション分割されたベース・パーティションおよび単位部分木の各値パーティションにおける登録処理の実施形態を示す。パーティション対象のXML文書１５１０は、ルート・ノードである＜支社  name＝“A”＞以下、パーティション属性である日付の異なる＜受注伝票  番号＝“０００１”＞から開始する単位部分木１５１２と、＜受注伝票  番号＝“０００２”＞から開始する単位部分木１５１４とを含んでいる。
【００９９】
各単位部分木１５１２のうち、先頭タグ＜受注伝票．．．＞は、インデックスとしてベース・パーティション１５３０に追加される。なお、ルート・ノードのタグは、図１３の処理により、分類対象のXPath＝P＝*／b／cに含まれないのでベース・パーティション１５３０に分類されている。また、値パーティション１５３２、１５３４には、パーティション対象の属性値を有するタグを含む単位部分木が登録されている。ベース・パーティション１５３０と、値パーティション１５３２、１５３４との間は、ポインタにより相互参照が可能とされている。
【０１００】
クライアント１１０〜１１８がサーバ１３０に対して検索要求を発行した場合、サーバ１３０は、検索要求が含むキーワードを使用して検索を実行し、検索結果作成部２１６が階層構造を反映した検索結果を作成する。作成した検索結果は、ネットワーク・アダプタ２０２を介してクライアント１１０〜１１８に送付される。
【０１０１】
本実施形態では、XMLDBの検索を実行するため、例えば、SQL関数“XMLQUERY”および“XMLEXISTS”を定義する。コマンド“XMLQUERY”は、SQLのコンテキストの中からXQuery式を実行できるようにするSQLスカラ関数である。“XMLQUERY”は、変数を、XMLQUERY
で指定された XQuery 式に渡すことができる。また、“XMLQUERY”は、XMLシーケンスであるXML値を戻す。
【０１０２】
ここで、“XMLEXISTS”の引数は、XQuery式が１つ以上の項目のシーケンスを戻すかどうかを判別し、引数に指定された XQuery式が空のシーケンスを戻す場合、“XMLEXISTS”は、falseを戻し、その他の場合には、trueを戻す。例えば、“bookstore”テーブルのinfoxmlの列に格納されているXML文書で、／支社／受注伝票／日付の値が、2006／12／01である／支社／受注伝票の一覧を返すSQL文は、以下の洋に記述することができる。
【０１０３】
【数１】
2010129001.tif 000004
（より詳細な定式化については、例えば、http:／／publib.boulder.ibm.com／infocenter／db2luw／v9／topic／com.ibm.db2.udb.apdv.embed.doc／doc／c0023899.htmおよびhttp:／／publib.boulder.ibm.com／infocenter／db2luw／v9／topic／com.ibm.db2.udb.apdv.embed.doc／doc／c0023906.htmを参照されたい。）
【０１０４】
また、検索実行の際、値パーティション内の各日付タグを参照する場合に、日付タグにポインタが付与されていなければ、その親要素（＝受注伝票）は、ベース・パーティションではなく、同一のパーティションに存在することが識別できる。一方、日付タグにポインタが付与されていれば、パーティションされており、この結果、受注伝票の親ノードが、ベース・パーティションに登録されていることが識別でき、パーティションされていないXMLDBおよびパーティション分割されたXMLDBについて、既存のSQLコマンドを使用することができる。
【０１０５】
さらに、パーティショニングに使用したXPath以外のパスに対して検索条件が指定された場合は、すべてのパーティションおよび検索の必要に応じてベース・パーティションを参照し、結果をマージすることにより、従来のRDBパーティション表と同じ処理を使用して検索要求に対応することができる。
【０１０６】
図１６は、本実施形態によりパーティションすることができるXML文書の実施形態を示す。図１６に示した実施形態は、MEDLINEデータベースに登録されたXML文書の実施形態である。MEDLINEデータベースは、医療文献照会用の公共データベースであり、1600万件の文献を所蔵し、ダウンロード可能なデータはXMLファイルとされ、１XMLファイルに、通常３万件の文献が記述されている。
【０１０７】
図１６に示した実施形態のXMLについて、例えば、本実施形態にしたがい論文誌の出版年を値パーティションの対象データとしてパーティション分割することにより、例えば過去５年分の論文だけを調べるクエリーにおいて検索対象とされる検索空間を著しく削減でき、検索速度を著しく向上させることができる。また、パーティション分割を行っても、元のXMLDBに登録された時点での階層構造が、ポインタおよびインデックスの生成により保持できるので、XMLDBの検索性を大きく損なうことなく、パーティション分割を効率的に実行できる。
【０１０８】
また、図１６に示した実施形態では、値パーティション内には、文献を単位とする部分木（MedlineCitation)でパーティションに登録されるので、文献を取得する検索においても、当該パーティションのみにアクセスすれば良く、検索効率は、著しく改善することができる。以上のように、本実施形態は、RDBのレコードをタグの単位とし、それらをまとめて単一のXMLファイルにした形式のデータであって、パーティション対象の属性を含むデータに対して検索効率を向上させることができる。
【０１０９】
本実施形態の上記機能は、Ｃ＋＋、Ｊａｖａ（登録商標）、Ｊａｖａ（登録商標）Ｂｅａｎｓ、Ｊａｖａ（登録商標）Ａｐｐｌｅｔ、Ｊａｖａ（登録商標）Ｓｃｒｉｐｔ、Ｐｅｒｌ、Ｒｕｂｙなどのオブジェクト指向プログラミング言語などで記述された装置実行可能なプログラムにより実現でき、当該プログラムは、ハードディスク装置、ＣＤ−ＲＯＭ、ＭＯ、フレキシブルディスク、ＥＥＰＲＯＭ、ＥＰＲＯＭなどの装置可読な記録媒体に格納して頒布することができ、また他装置が可能な形式でネットワークを介して伝送することができる。
【０１１０】
これまで本実施形態につき説明してきたが、本発明は、上述した実施形態に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【図面の簡単な説明】
【０１１１】
【図１】本実施形態のデータベース・システム１００を示した図。
【図２】本実施形態のサーバ装置１３０の機能ブロック２００を示した図。
【図３】本実施形態のサーバ１３０が処理対象とするXML文書３００の実施形態を示した図。
【図４】本実施形態のXML文書３００を、木構造４００として示した図。
【図５】本実施形態のサーバ１３０が実行するXMLDBに対する処理の概略的なフローチャート。
【図６】本実施形態において、サーバ１３０が、図５のステップＳ５０１でパーティションを生成する処理を実行するためのDDL文６００の実施形態を示した図。
【図７】本実施形態のXML分割を実行する、図５のステップＳ５０２のより詳細なフローチャート。
【図８】、ステップＳ７０３の処理XML分割位置算出処理の詳細なフローチャートである。
【図９】図８のステップＳ８０５およびステップＳ８０６の開始タグ処理および終了タグ処理の詳細なフローチャート。
【図１０】図９のステップＳ９１３で実行するスタックStartに対する上位要素を取り除く処理の説明図。
【図１１】図９の処理による本実施形態で実装するスタックCountの更新処理の概略図および生成される値スタックの値遷移１１００の実施形態を示した図。
【図１２】図９〜図１１の処理で生成された、XML分割を行うための部分木データ・リストの実施形態を示した図。
【図１３】ベース・パーティションに分割する部分木を生成する処理のフローチャートを示した図。
【図１４】ペース・パーティション１４１０の＜受注伝票＞タグ１４５０に、ptr＝“2006:467”を、＜受注伝票＞タグ１４６０に、ptr＝“2007:8152”を隠し属性値として追加する実施形態を示した図。
【図１５】本実施形態にしたがってパーティション分割されるXML文書と、パーティション分割されたベース・パーティションおよび単位部分木の各値パーティションにおける登録処理の実施形態を示した図。
【図１６】本実施形態によりパーティションすることができるXML文書の実施形態を示す。
【図１７】従来のXMLDBのデータ格納構造を示した図。
【符号の説明】
【０１１２】
１００…データベース・システム、１１０〜１１８…クライアント、１２０…ネットワーク、１３０…サーバ、１４０…データベース、２００…サーバ（機能ブロック）、２０２…ネットワーク・アダプタ、２１０…SQL処理部、２１２…SQLパーザ、２１４…XMLパーザ、２１６…検索結果作成部、２２０…データ管理部、２２２…パーティション生成部、２２４…XMLパーザ、２２６…XML分割部、２２８…分割XML登録部、３００…XML文書、３１０、３１２…単位部分木
【図１】
2010129001.tif 000005
【図２】
2010129001.tif 000006
【図３】
2010129001.tif 000007
【図４】
2010129001.tif 000008
【図５】
2010129001.tif 000009
【図６】
2010129001.tif 000010
【図７】
2010129001.tif 000011
【図８】
2010129001.tif 000012
【図９】
2010129001.tif 000013
【図１０】
2010129001.tif 000014
【図１１】
2010129001.tif 000015
【図１２】
2010129001.tif 000016
【図１３】
2010129001.tif 000017
【図１４】
2010129001.tif 000018
【図１５】
2010129001.tif 000019
【図１６】
2010129001.tif 000020
【図１７】
2010129001.tif 000021