知識テーブルに基づく大規模知識処理のためのXMLデータベースの試作

全文

(1)2006−ICS−145（6） 2006／10／25. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. JAWS2006 知識テーブルに基づく大規模知識処理のための XML データベースの試作驛昌弥† a). 大囿忠親††. 新谷虎松††. An Implementation of an XML Database based on a Knowledge Table for LargeScale Knowledge Processing Masaya EKI†a) , Tadachika OZONO†† , and Toramatsu SHINTANI††. Abstract. XML(eXtensible Markup Language) は，情報表現やインターネット，その他の場所でのデータ交換の標準となってきている．多くのデータソースが XML に転換され，そのコンテンツは XML を用いて表現されるので，XML データの効率的で有効なクエリ処理や最適化が，重要になってきている．XML データベースにおいて，事前にデータ構造のすべてを決定できない不定型なデータを扱うというニーズの場合，データベース作成時にスキーマを用意できない．スキーマレス型の XML データベースを選択しなければならない．既存の XML データベースでは内部構造を知らないと効率良く検索できないという問題もある．本研究では，スキーマの有無に関わらず XML 文書を述語と知識テーブルに変換し，問い合わせに対して検索などの推論を行う．本稿では，XML 文書の知識テーブル及び述語への変換及び検索のアルゴリズムについて述べる． Keywords. データベース，XML，述語，推論，スキーマレス. 1. はじめに. リレーショナルデータベースは，取り扱う XML データが形式の決まっている構造データの場合には検索性. コンテンツの XML 化が急激に進んでおり，コンテ. 能が良い．構造の定義が困難な非構造データでは，検. ンツを扱う多くの IT ソリューションのプラットフォー. 索性能が大幅に低下する．リレーショナルデータベー. ムにおいて，大量の XML データを効率的に蓄積，検. スには，データ構造に変更があった場合，それに合わ. 索，管理する機能の重要度が高くなっている．XML. せて表構造を変更しなければならないという欠点があ. は，データの意味を表すタグを目的に応じて定義でき. る．. る拡張可能なマークアップ言語の国際標準データ記述. XML データベースは，多種多様な階層構造を持つ. 言語である．. XML データを，木構造のままで格納，操作することが. XML の高い記述力から要求される全文検索や階層. できるデータベースである．XML データの格納や取. 構造に関する検索，例えば親子や兄弟などの要素を組. 得にあたって，マッピング処理のようなデータ構造を. み合わせて階層構造を辿ったり，条件を満足する部分. 考慮した処理が存在しないため，ソリューション開発. 階層を抽出したりする検索などは，XML の処理に必. 中やビジネス環境の変化により発生するデータ構造の. 要な検索であるが，高速化が困難である．. 変更にも比較的柔軟に対応できる．XML データベー. XML データの管理には，リレーショナルデータ. スは XML データを木構造のままで格納できるため，. ベースや XML データベースが用いられることが多い．. 非構造データを容易に扱えるが，XML 特有の検索を高速化するためには使用可能なメモリより多くのデー. †. 名古屋工業大学工学部知能情報システム学科，〒 466-8555 名古屋市昭和区御器所町 †† 名古屋工業大学大学院情報工学専攻，〒 466-8555 名古屋市昭和区御器所町 a) E-mail: [email protected]. （注 1）：著作権は (社）情報処理学会にある.. タにアクセスしなくてはならず，スケーラビリティが低く，小規模なデータ量を扱うシステムに用途が限定されてしまっていた．このことが結果的に XML データベースの普及を妨げた最大の要因であると考えられ. −41−.

(2) Proceedings of JAWS2006. る．. DTD が独自構文であるにもかかわらず，スキーマ言語. 近年，XML データを扱うためのシステムとして様々. 習得が最も簡単であるとされている．Schematron の言. なものが提案されている．例えば関係のマッピング. 語仕様は非常に単純で記述性が高いが，XPath を知っ. XML データ [1]，オブジェクトリレーショナルモデル. ていることが前提になる．RELAX は XML Schema. [2]，半構造データベースのような特別な目的を持つ. 並みの記述性を兼ね備えていながら，シンプルな構造. データベース [3]，ネイティブ型のデータベースの開発. の言語である．詳しくは [14] に記されている．. [4] などがある．主な問題点として，どの XML データ. XML データベースは，スキーマの有無に関して，. 管理システムも問い合わせ言語の最適化に直面してい. スキーマ必須，性能を上げるためにはスキーマを使. る．. う，スキーマレスといった 3 種類に分けられる．事. 本研究では一般的な XML 文書，特に事前に仕様が. 前にデータ構造のすべてを決定できない不定型なデー. 決定してない，もしくは仕様の変更が頻繁に起こるよ. タを扱うというニーズの場合，データベース作成時に. うなスキーマレスの XML 文書を述語及び知識テーブ. スキーマを用意できない．仕様変更があるようなデー. ルに変換し，検索や推論を行うことで，XML の柔軟. タ集合を扱う場合にもスキーマレス型の XML データ. 性と高速な検索の実現を目指す．. ベースを選択することが好ましい．. 以降，2 章では，現状の XML データベースについ. 2. 2 問い合わせ言語. て述べる．3 章では，木構造を表す述語を高速に検索. 問い合わせ言語にはいくつか提案されているが，広. するためのデータ構造である知識テーブルについて述. く普及されていて機能性の高いものに XQuery[15] が. べる．4 章では，本システムの構成について述べる．. ある．XQuery は，表現式という単位から構成され，. 最後に，5 章で本稿をまとめる．. 表現式の組み合わせによって複雑な問い合わせを記述. 2. XML データベース XML データベースとは XML 形式の情報をそのま. できる関数型言語である．XQuery 1.0 は XPath 2.0 をサブセットとして含んでいるので，XML の各要素を指定するには XPath を使用する．. ま格納できるデータベースで，NeoCore XMS[5] や. XQuery 問い合わせには，厳格な形式意味論が与え. Xindice[6] がある．XML データベースには，アルゴ. られており，XML 文書に対して様々な問合せを行う. リズムの設計により様々な種類が提案されているが，. ことが出来るが，文法が複雑でユーザにとって扱いに. それらは画一されていない．XML を扱うデータベー. くい言語である．更に，XML データベースの内部構. スの種類として，マッピング型 XML データベース，. 造を知らなければ，XQuery を用いて効率良く検索で. オブジェクトリレーショナルモデル，半構造データを. きない．. 扱うデータベース，ネイティブ型のデータベースなど. これらの XML データベースや問い合わせ言語の問. が提案されている．. 題点を踏まえて，内部構造を知らなくても効率良く検. 2. 1 スキーマ言語. 索が可能であり，複雑な記述を必要としない問い合わ. スキーマ言語とは，XML のような構造化文書を記. せとそれに連動した XML データベースシステムが必. 述するためのマークアップ言語を作成するためのメタ. 要である．. 言語である．文書中でどのようなタグや属性が使われ. 2. 3 XML データベースの問題点. ているかなど，具体的な文書構造を記述するために使. 一般的に問題とされるのは，処理速度が遅い点や. われる言語がスキーマ言語である．. データ量が膨大になる点，大規模なデータに対しての. XML のスキーマ言語の一つとして，DTD[7] が使. 検索が難しい点などである．構造化されたデータの処. われているが，データ型が定義できない点や，文法が. 理スピードは，リレーショナルデータベースに比べて. XML と無関係である点など様々な欠点が指摘されてい. 極めて低速である．. る．W3C では XML Schema[8] と呼ばれる新たな言. 実際に実用レベルで使用する場合に更に致命的な. 語の開発を進めているが，仕様が複雑で標準化は難航. 問題が出てくる．半構造データを扱いスキーマを参考. している．他の主な言語として，XDR[9]，SOX[10]，. にはするが必ずしも必要としないという XML データ. Schematron[11]，DSD[12]，RELAX[13] などがある．. ベースの利点が，XML データベースの内部構造を知. これらのスキーマ言語から，使いやすさの観点では，. らないと効率良く検索できないという問題によって利. −42−.

(3) JAWS2006知識テーブルに基づく大規模知識処理のための XML データベースの試作. 点ではなくなっている．従って，事前にデータ構造の. 1 html( http://www.nitech.ac.jp/ ). 仕様が確定していて仕様の変更が少ないシステムでなければ，XML データベースの内部構造を知らない. 2 html( http://summer.ics.nitech.ac.jp/ ). ユーザは検索できない．XML 文書をテキスト検索する全文検索は，XML データベースの内部構造を知らなくても検索できるが，負荷が大きいので大規模な. 3 http. データに対しては効率が悪い．このことにより，データベースの構造が変更された場合に，データベース作. 4 www. 成者はもとより，不特定多数のユーザによる共有デー. 図2. タベースなどでは仕様変更のたびに新たな仕様書を片. 図 1 の有向グラフ. 手に検索しなくてはならない．１. 2. 3. １. １. 4. 2. 2. 3. 知識テーブルに基づく XML 文書の. 3. 4. １. 検索. 2. 3. 1 知識テーブル知識テーブル [16] は，木構造やネットワークモデルなど有向グラフにおいての知識の関係をテーブルで表現するものである．XML を有向グラフであるとすると，下位ノードからルートへ辿る有向グラフであると考えられる．例えば，図 1 の XML を有向グラフで表現すると図 2 になる．図 2 中の四角はノードを表わし，. 図3. １. 図 1 の知識テーブル. relation(html( http://www.nitech.ac.jp/ ), 0, 0, 0, 0). relation(html( http://summer.ics.nitech.ac.jp/ ), 0, 0, 0, 0). relation(http, 1, 1, 0, 0). relation(www, 2, 2, 1, 0).. 四角中の左の数字はノードの ID である．また，知識テーブルで表現すると図 3 になる．知識テーブルにお. 上記のような保存形式では，一般にタグ n 個に対して. けるテーブル要素に書かれている数字は，縦要素の ID. n2 の数字のメモリが必要なので効率が悪い．ここで. から見て横要素の ID との関係を表している．この数. は以下のように数字をまとめ，int 型の 10 進数表現に. 字は ‘1’,‘2’,‘0’ の 3 種類で表され、それぞれ直接の親. よって省メモリ化をはかっている．. ノード，辿ることのできるノード，無関係なノードという意味である．何も記述されていないテーブル要素には ‘0’ が入っている．例えば，ノード 1 とノード 3 が親子関係であることがわかる．. relation(html('http://www.nitech.ac.jp/'), [0]). relation(html('http://summer.ics.nitech.ac.jp/'), [0]). relation(http, [5]). relation(www, [26]).. <www> <http> <html> http://www.nitech.ac.jp/ </html> <html> http://summer.ics.nitech.ac.jp/ </html> </http> </www>. この場合の [ ] 内の 10 進数は，例えば図 3 の横 4 の列. 図 1 XML 文書の例. 得られるので 10 進数から元のテーブルの関係を求め. において ‘2’,‘2’,‘1’,‘0’ と並んでいるのでこれを 2 進数化して ‘10’,‘10’,‘01’,‘00’ とし，それぞれを左の要素から順に下位に並べていくと ‘00’,‘01’,‘10’,‘10’ となる．これを 10 進数にすると ‘26’ となる．この 10 進数の表記の仕方は，ある 10 進数に対して唯一の 2 進数がることができる．上記の知識テーブルの 10 進数表現は，以下のようなビット列型表現に置き換えることで，. 図 3 の知識テーブルを述語に変換すると以下のように. 大規模データを扱うことができ，リレーショナルデー. なる．以降，述語は，特に断りがない限り論理型言語. タベースのビット演算を行うことで高速な検索も可能. の Prolog に類似した記法で記述する．. になる． 00000000000000000101000010100100. −43−.

(4) Proceedings of JAWS2006. 上記のビット列は，図 3 の知識テーブルのノード間の関係 0000,0000,1100,2210 をそれぞれビット列型表現に 0.32. 変換した 00000000,00000000,01010000,10100100 を. 0.28. 3. 2 知識テーブルの性能図 4 は知識テーブルと 2 分木表現でのメモリ使用量の比較である．ここで，横軸は要素の数，縦軸はメモリ使容量を表わしている．2 分木表現は，単純にノードの数が 2 倍になるとメモリは 2 倍になる．知識テーブルは，ノードが増えると右上がりの緩やかな曲線を描くようにメモリが増加する．. search time(sec))/relatuon. 繋げたものである．. 0.24 0.20 0.16 0.12 0.8 1.0 1.2. 0.08. 0.8 1.0 1.2. 0.8 1.0 1.2. 0.04. 0.8 1.0 1.2. 0.8 1.0 1.2. 0.8 1.0 1.2. 0. 図 5 は知識テーブルと 2 分木表現でのそれぞれノー. 10. 50. 100. 200. 150. 250. numbers of relations. ドの上位，下位の検索時間である．ここで，横軸は要素の数，1 要素あたりの縦軸は検索時間を表わしており，知識テーブルと 2 分木表現について，それぞれ上. 0.8 1.0 1.2. 位タグと下位タグを求める検索時間をグラフで表わし. supers(Binary representation) subs (Binary representation) supers(Knowledge Table) subs(Knowledge Table). 図 5 1 ノードあたりの検索時間. ている．どちらの表現も上位タグを求めることより下位タグを求めるほうが効率が良く，知識テーブルのほうが 2 分木表現よりも検索時間が短い．上位タグを求. ベースに XML の検索や推論を行う．知識テーブルで. めることが下位タグを求めることよりもコストが掛か. 表現可能な XML について議論する．. るのは，本システムの知識テーブルが XML 文書を下. 再帰的なタグ構造，より一般的に言えばある X タグ. 位タグから上位タグを辿る構造であるからである．. の上位タグが選言になるという XML は，知識テーブ. 図 4，図 5 から，知識テーブルと 2 分木表現で，知. ルで表現することができる．図 6 の XML 文書は http. 識テーブルはメモリが大きいが，高速な検索が行える. というタグの中に http タグがあり，http タグに対し. ことがわかる．データベースにおいて，ストレージの. ての上位タグが www か xhtml の選言になっている．. 容量よりスピードが重要視されるので，本システムで. 図 6 を知識テーブルで表すと図 7 になる．. Memory spaces(Kbyte). は XML 文書の検索に知識テーブルを用いた． <www> <http> <xhtml> <http> <html> http://www.nitech.ac.jp/ </html> </http> </xhtml> </http> </www>. 120 100 80. 0.8 1.0 1.2. 60. 0.8 1.0 1.2. Knowledge Table. 40. 図 6 XML 文書の例 2. 0.8 1.0 1.2. 20. Binary representation. 0.8 1.0 1.2. 0.8 1.0. 0. 1.2. 0.8 1.0 1.2. 10. 50. 100. 200. 150. 250. numbers of relations. 図4. メモリ使用量の比較. 例えば，図 8 のようにタグの中に id を持つものや，空タグでタグ内に要素を持つものを表現する際に，毎回識別子の名前が同じではある保証はなく，1 つのタグに 2 つ以上の識別子を持つことがあるので，知識テーブルでの表現ができない場合がある．1 つのタグに対して唯 1 つの識別子を許す場合のみ表現が可能で. 3. 3 XML の種類による知識テーブル. ある．ただし識別子を持つタグが葉であってはいけな. 本システムでは，3.1 節で説明した知識テーブルを. い．もしこの状態を扱う場合，図 8 の Urn タグでは. −44−.

(5) JAWS2006知識テーブルに基づく大規模知識処理のための XML データベースの試作 1 2 3 4 5. html( http://www.nitech.ac.jp/ ) http xhtml http www. １ 2. 3. 4. 5. １. つに分割したが，より深い部分で木を分割すると，部多数に分割することは良いことばかりでなく，ルート. 2 １. 4 2. 2. １. 5 2. 2. 2. 図7. 善することができる．今回の例では部分木 A，B の 2 分木が増え 1 つの知識テーブルの検索効率は良くなる．. 2 １ 3. 木を分割することで，知識テーブルの検索効率を改. から辿る際のハッシュテーブルの増加や知識テーブルを探すコストが掛かること，分割することにより意味１. 図 4 の知識テーブル. 情報の過失など悪いこともあるのでトレードオフである．. 以下のように参照先のアドレスを用いる．. Urn(参照先)，参照先:id=‘1’ value=‘1984’. NewsML. この場合の参照先は知識テーブルではなく通常の記憶領域なので知識テーブルを用いる本システムでは好ま Catalog. しくない．. ・・・. 木. ・・・. ・・・. 図 9 XML. ・・・. Comment. Resource. Resource. ・・・. 図 8 XML 文書の例 3. A. ・・・. <NewsML> <Catalog> <Resource> <Urn id= 1 >1984</Urn> <Url>topicset.iptc-format-nsk.xml</Url> <DefaultVocabularyFor Scheme="IptcFormats"/> </Resource> </Catalog> </NewsML>. NewsItem. 3. 4 大規模データに対する知識テーブル知識テーブルのタグ関係情報はビット列型で保存されているが，大規模データを扱う場合，ビット列が非常に長くなる場合がある．この場合，XML の木構造分割が必要になる．XML 文書は，通常ルートノード. 4. システム実装. から数ノードまで，大分類，小分類などそれより深い. 本システムの構成は図 10 になる．まず XML 文書. 層に書かれている内容の分類分けをしているタグが多. を知識テーブルに変換する．知識テーブルに変換され. い．これらのタグも含めて木構造全体を 1 つの知識. たデータは，ビット列型のタグ関係情報と述語に変換. テーブルにすると，知識テーブルの要素が増える．. され，RDB(リレーショナルデータベース) に格納さ. 図 9 は XML 文書を木で表したものである．この図. れる．. では，全体の XML 木は部分木 A，B，C の集合であると考えられる．A の部分木を探索する時，B の部分木は A に対して独立していて，影響を与えることも受. 4. 1 ストレージの管理 XML をデータベースで扱う上で挙げられるものと. けることもない．このようなノードを複数同一の知識. してストレージがある．例えば XML 文書をリレー. テーブルに入れておくと，検索効率が低下する．C の. ショナルデータベースのような 2 次元の表に置き換え. 部分木は，ルートから比較的浅いノードまでの部分木. るマッピング型や，XML 文書を木構造を保持するか. で，この部分木は情報量が低く，知識テーブルにしな. 最小限の変換で保存するネイティブ型などがある．本. くてもよい．C の部分木はハッシュテーブルに格納す. システムは，知識テーブルに基づき推論を行うので，. る．. 木構造を保持するネイティブ型ではなく，知識テーブ. −45−.

(6) Proceedings of JAWS2006. 知識テーブルに変換. XML 文書. 述語論理表現に変換. 述語論理表現. bit 列型表現に変換. RDB に格納. RDB. 図 10. <NewsML> <Catalog> <Resource> <Urn>topicset.iptc-format-nsk:1</Urn> <Url>topicset.iptc-format-nsk.xml</Url> </Resource> <Resource2> <Urn>topicset.iptc-status-ja:1</Urn> <Url>topicset.iptc-status-ja.xml</Url> </Resource2> </Catalog> <NewsItem> <Comment>併用写真</Comment> </NewsItem> </NewsML>. 知識テーブル. RDB に格納. 図 11 XML 文書の例 5 1 2 3 4 5 6 7 8 9 10. bit 列型表現. システム構成図. ルを既存のリレーショナルデータベースを用いて保存. Urn( topicset.iptc-format-nsk:1 ) Url( topicset.iptc-format-nsk.xml ) Urn( topicset.iptc-status-ja:1 ) Url( topicset.iptc-status-ja.xml ) Comment( 併用写真 ) Resource Resource2 Catalog NewsItem NewsML. 0000000000000000000000000000000000000000 0000000000000000000000000000000000000000 0000000000000000000001010000000000000000 0000010100000000000010101010000101000000 0000000001000000000010101010101010010100. するのでマッピング型のストレージである．具体的には，推論のための述語をリレーショナルデータベースに保存する．知識テーブルのデータは以下のスキーマ構造で保存する．. 図 12. 図 11 のビット列型表現. 知識テーブル : knowledgetable(id, tag, number) ビット列型のタグ関係情報 : ビット relation(data). ここで，知識テーブルの ID が重複することはないこ. 1 : 入力：タグ関係のビット列型データ B 2: 探すノードの ID Number 3 : procedureBitSearch(B, Number) 4 : 出力： 1 つ先のタグ NextTag 5 : begin 6: int : x = 0 //返すタグの数字 7: x := ビット列の N umber に該当する場所から 01 の場所を代入 8 : return x ; 9 : end.. とと，null 値を認めないので knowledge テーブルの. id は primary key 属性を持つ．bitrelation に data はビット列型で保存されている．検索にはリレーショナルデータベースのビット演算を用いるので，ビット数の上限が無く，高速な演算を行うことができる． 3 節の図 1 の XML 文書をリレーショナルデータベースに格納する形式にすると以下のようになる． knowledgetable(1, html( http://www.nitech.ac.jp/ ), 0) knowledgetable(2, html( http://summer.ics.nitech.ac.jp/ ), 0) knowledgetable(3, http, 5) knowledgetable(4, www, 26) bitrelation(00000000000000000101000010100100). 図 13 ビット列型の検索アルゴリズム. が初めて呼ばれる場合は，Query に記述されているタ. 4. 2 知識テーブルの利用図 11 の XML 文書をビット列型で表すと図 12 にな. グ名からリレーショナルデータベースを用いて求めた. る．図 12 の一番左の数字はノードの ID である．ビッ. の呼び出しの戻り値である．3 行目は，この procedure. ト列型の検索アルゴリズムは図 13 になる．尚，アル. の引数である．4 行目は戻り値で，次回この procedure. ゴリズムの左側の数字は行番号である．. が呼び出された時の引数になる．7 行目では，リレー. ここで，図 13 のアルゴリズムについて説明する．. ショナルデータベースのビット演算により ‘01’ の場所. 1 行目は，リレーショナルデータベースから取得した. を求める．8 行目は戻り値である．行き先のない状態. ビット列型データである．2 行目は，この procedure. の場合は，x には 0 が入っている．. ノードの ID であり，2 回目以降は呼ばれた場合は前回. −46−.

(7) JAWS2006知識テーブルに基づく大規模知識処理のための XML データベースの試作. 4. 3 問い合わせ言語本システムにおけるユーザからの問い合わせ言語は，論理型言語の Prolog に類似した記法を用いる．以下. XML 構造の検索. Query. 結果出力. は Prolog の文法とは異なっている主な点である．紙面の都合上，その他の点については省略する．. bit 列型データ述語論理データ. ・変数は (アンダースコア) で始まる．大文字で開始しても変数と見なさない・タグや構造を変数で指定できない・! (カット) を用いることができない・; (選言) を用いることができない・if による条件分岐を行えない. RDB. 図 14. 検索の流れ. 例えば，図 11 の XML 文書で，Urn のタグの要素を求めたいとき，“Urn = X. ” という問い合わせを. 1 : 入力：タグ関係のビット列型データ B 2: ユーザの入力クエリ Query 3 : 出力：検索結果 Result 4 : procedure SearchXML (B, Query) 5 : begin 6 : V ← {}//検索結果 7: repeat 8: int : i = BitSearch(B, Number) 9: V ← V ∪ リレーショナルデータベースの IDi のノード; 10 : until すべてのノードの行き先無し 11 : return V; 12 : end.. 作る．この問い合わせの Urn は求めたいタグの名前で，X は変数である．この問い合わせに対して，以下の結果が返される．解が複数存在する場合，or によって解が接続された結果が返される． X = “topicset.iptc − f ormat − nsk : 100 or “topicset.iptc − status − ja : 100 例えば，図 11 の XML 文書で，上位タグに Resource タグを持つ Urn タグの要素を求めたいとき，“Urn =. X, predessor(Resource, X). ” という問い合わせを作る．“Urn = X” と predessor(Resource, X)” の間の. 図 15 検索アルゴリズム. カンマは，連言 (AND) の意味である．predessor( A,. B) は， A は B より上位タグであるということを表わす述語である．この問い合わせに対して，以下の結. なっている．8 行目では，4.2 節の BitSearch アルゴ. 果が返される．. リズムを用いて現在のタグの先のタグを求める．9 行目では，8 行目の戻り値を用いてリレーショナルデー. X = “topicset.iptc − f ormat − nsk : 100. タベースから対応するタグを取得し，ユーザに返す検索結果に加える．. 4. 4 問い合わせの流れ. 4. 5 その他の問い合わせ. 図 13 は検索の流れである．ユーザから受け取った. その他の問い合わせには，新規タグ追加，値の更新，. Query とリレーショナルデータベースに保存されてい. タグ削除などがある．ここでは新規タグ追加について. る知識テーブルのビット列型タグ関係情報と述語から，. 記述する．値の更新，タグ削除については紙面の都合. 必要な構造を導き出して結果を出力する．図 15 は，検. 上省略する．図 16 は，新規タグ追加アルゴリズムで. 索アルゴリズムである．. ある．. ここで，図 15 のアルゴリズムについて説明する．. ここで，図 16 のアルゴリズムについて説明する．1. 1 行目は，リレーショナルデータベースから取得した. 行目は，リレーショナルデータベースから取得したビッ. ビット列型データである．2 行目は，ユーザが入力し. ト列型データである．2 行目は，新規追加されるノー. たクエリである．3 行目は，ユーザに返す検索結果で. ドのデータで，追加される場所，タグ名，値のデータ. ある．表示するタグ構造が入っている．7∼10 行目は，. を持つ．5 行目では，追加される場所の判定を行い，. 出力するタグ構造を求め終わるまでループするように. −47−.

(8) Proceedings of JAWS2006. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10 : 11 :. 入力：タグ関係のビット列データ B 新規追加するデータ D. 模システムの実装，およびヒューリスティックに XML. procedure InsertXML (D) begin if 追加される場所が葉 int : i := 追加される枝のビット列 i の 01 の項目を 10 に変換 i := i ∪ 追加される場所に 01 B ← B ∪ i; endif end.. ある．. 図 16 新規追加アルゴリズム. 文書を分割した際の実行速度及びメモリの評価実験で. 文 [1]. 献. Bohannon, P., Freire, J., Roy, P., Simeon, J.:From XML schema to relations: A cost-based approach to XML storage. , Proceedings of the 18th International Conference on Data Engineering, page 64, 26 Feburary -1 March 2002.. [2]. Klettke, M., Meyer, H., “XML and object-relational database systems-enchancing structual mappings based on statistic” , WebDB, May 2000.. [3]. McHugh, J., Widom, J., “Query optimization for XML”, VLDB 1999.. 枝の場合のみ処理を続ける．追加される場所が葉の場. [4]. Fiebig, T., Helmer, S., Kanne, C.-C.,Moerkotte, G., Neumann, J., Schiele, R., Westmann, T., “Anatomy. 合，入力されたノードは追加されず，終了する．6 行. of a native XML base management system””, VLDB. 目では，追加される枝のビット列を取得する．7 行目. 2002.. では，6 行目で取得したビット列の ‘01’ の項目を ‘10’. [5]. NeoCore, http://www.neocore.jp/xml/. に変換する．8 行目では，7 行目のビット列に追加さ. [6]. Xindice, http://xml.apache.org/xindice/. れる枝を参照する場所に ‘01’ を追加する．６行目∼8. [7]. T. Bray, J. Paoli, C. M. Sperberg-McQueen (ed.), “Extensible Markup Language (XML) 1.0”, W3C,. 行目で，追加するノードは，追加される枝から辿れるノードをすべて ‘10’ として持ち，追加される枝に対し. February 1998. [8]. D. C. Fallside (ed.), “XML Schema Part 0: Primer”, W3C, April 2000.. て ‘01’ を持つことになる． [9]. Charles Frankston, Henry S. Thompson, “XML Schema. 5. まとめ. Developer’s. Guide”,Internet. Document,. http://www.ltg.ed.ac.uk/~ht/XMLData-Reduced.htm, July 1998.. 本論文では，XML 文書，特に事前に仕様を決定でき. [10]. て，事前にスキーマが用意されている XML 文書と同等の性能で検索することを目的として，XML データ. [11]. //www.brics.dk/DSD/, 1999. [13]. gr.jp/relax/, April 2000. [14]. ment [15]. ることでスキーマレスな XML データベースを実現し. Toramatsu Shintani, “Knowledge Table:. An Ap-. proach to Speeding up the Search for Relational Information in Knowledge Base”, Journal of Informa-. していないのは，タグの中に要素を書き，空タグとす. tion Processing, Vol. 13, No4, 1990. [17]. J. Clark, S. DeRose (ed.) “XML Path Language (XPath) Version 1.0”, W3C, November 1999.. の課題である．本システムの特筆すべき点は，検索において，推論. XQuery 1.0: An XML Query Language, http://www. w3.org/TR/xquery/, June 2006.. [16]. るタグ X の上位タグが選言であるものにである．対応る書き方を含む XML 文書で，これについては，今後. Dongwon Lee, Wesley W. Chu, “Comparative Analysis of Six XML Schema Languages”,Internet Docu-. ナルデータベースに保存し，検索の問い合わせにはリ. ている．本システムで対応している XML 文書は，あ. M. Makoto, “RELAX (REgular LAnguage description for XML), Internet Document, http://www.xml.. 本システムにおいて，知識テーブルのタグと ID の. レーショナルデータベースに保存したデータを利用す. N.Klarlund, A.Moller, M.I.Schwatzbach, “Document Structure Description 1.0”, Internet Document, http:. 成し，知識テーブルをもとに述語に変換し，推論を行. 対応表及び，ビット列型のタグ関係情報をリレーショ. R.Jelliffe, “Schematron”, Internet Document, http: //www.ascc.net/xml/resource/schematron/, May 2000.. [12]. ベースを提案した．XML 文書から知識テーブルを作う．. A.Davidson, M.Fuchs, M.Hedin, et al., “Schema for Object-Oriented XML 2.0”,W3C,July 1999. ず，スキーマを用意できないような XML 文書に対し. [18]. Dunren. Che,. Karl. Aberer,. M.. Tamer. ¨ ozsu,. “Query optimization in XML structured-document. による検索が可能であるという拡張性について重点を. databases”,VLDB 2006.. 置いている点である．今後の課題は，速度向上，大規. −48−.

(9)