大容量XML文書のデータ更新が 可能なXML編集ライブラリ

Presentation on theme: "大容量XML文書のデータ更新が 可能なXML編集ライブラリ"— Presentation transcript:

1 大容量XML文書のデータ更新が 可能なXML編集ライブラリ
理学部　情報科学科 指導教官　千葉　滋　助教授 学籍番号　00_01519　石川　零 注目すべき箇所のみを書く そのほかは口で説明する 1枚1分

2 XMLデータの利用例 例：DBLP – 196MBの文献リスト Z氏が書いた論文の題名、学会、年度のデータを集めたい references
<conferences> <year>2003</year> <conference> <conference-name>OOPSLA</conference-name> <paper> <title>HydroJ: object-oriented pattern matching for evolvable distributed systems </title> <author>Keunwoo Lee</author> </paper> ... </conference> <conference-name>AOSD</conference-name> </conferences> </references> conferences ...... conference- name … conference XML文書のある利用例について説明します。 XMLはデータ記述言語として様々な分野で利用されています。 例えばDBLPから196MBの文献リストが配られています。 今回例に挙げるのはこれを簡単にした文献リストですが、このような文献リストから、 Zさんが書いた論文の題名、その論文が発表された学会、発表年度のデータをセットにして 集めて取り出したいとします。 この左の図がその文献リストの一部を表すXMLデータです。 XMLはデータを構造化して扱うことができ、その構造化されたデータは、右図のような形をしています。 データの一番上のノードはreferencesというノードです。その子ノードはconferencesといい、 その学会で発表された論文のリストを年度別に持っています。このconference-name ノードは、 その学会の名前を表しています。 Conferenceは、その学会のある年に行われた論文リストを表しています。子要素である Yearが行われた年を表しています。 その子要素にはpaper要素があります。これは1つの論文を表していて、その子要素に題名を表す Title要素と、著者を表すauthor要素を持っています。 この例では、Z氏の書いた論文の題名と学会、年度のデータを集めるという操作を考えます。 言うべきこと： 　このXMLデータは、住所の情報を元に操作する機会が多く、そのため住所を元に構造化されて並べられている 　必要なのは大容量XMLデータの一部 XMLで様々なデータを扱おうという動きがあり、そのため、大容量のXMLデータを扱う機会も増えている。 大容量のXMLデータでも、必要なのはその一部である。またデータ全体をメモリ上に上げて操作することはできない。 Todo: 図を書く。 この例で、プログラムが必要なデータは（右図）になる。 ・例を示す ・例を変更、階層がより深くて分散しているものが良い ・XML文書が巨大になるという事を説明したいが、このスペースでは難しいので省く ・この時点で、この場合では欲しいノードが散らばっていることについて説明する 例を書き直す 絵を書き直す ...... year paper paper title author title author

3 ユーザが望むデータ構造は、元の構造から変化する
取り出したいデータ構造 データを元の構造と異なる側面から取り出したい 学会別や年度別ではなく著者名 取り出したいデータ構造が、元の構造から変化 部分木ではだめ references conferences paper title author conference references year conference- paper title author conferences ...... 　取り出したいデータについて見てみましょう。 　このXMLデータはこのように、学会別、年度別に構造化されています。 　そのため、例えばある学会の、ある年度のデータを取り出したいときは、このように、データの 部分木という形で指定する事ができます。これはXMLデータが、学会別、年度別に構造化されているからです。 //この赤で囲まれた要素は、取り出したいデータを、どの要素から見ているかを示したものです。 　しかし、この例で必要なのは、authorがZ氏であるようなpaper要素に対して、title要素と、その要素の1つ上に あるyear要素と、さらに1つ上にあるconference-name要素を1つにまとめたものです。 　そのため、必要なデータ構造というのは、このような、paper要素から見て、子要素であるtitle要素とauthor要素と それより上にあるyear要素、conference-name要素を1つにした、このようなデータ構造であると言えます。 　このように、元のデータ構造とは異なる側面からデータを見た場合、取り出したいデータ構造は 元のデータ構造と違ったものであるという事が言えます。 　このとき、データは部分木で表すことができません。 100歳以上の人は全国各地にいるため、必要なデータはこの図のように、 XMLデータの中のあちこちの枝に散らばって存在します。 それぞれのデータは、このようにノードの親子関係や、子孫関係を表す枝によって結びついている。 例えばこの人のデータと、住んでいる地域を表すノードは関連付けて取り出す必要がある。 また、これらのデータは部分木として取り出すことはできない。 このXMLデータは国民のデータを住所を元に管理しているので、ある町に住む人のデータは部分木で表すことが できるが、しかし年齢という観点から見ると、必要なデータはXML文章中に散らばってしまう。 これらの必要なデータは、要素の親子関係、子孫関係を表す枝によって結びついている。 例えば100歳以上の人のデータと、住んでいる地域を表すノードは子孫関係で結びついていて、 これらを関連付けて取り出す必要がある。 言うべきこと： 　このXML文書は、住んでいる地域を元にしてデータを調べるのに都合よく構造化されている。 　そのため、ある地域に住む国民を探すなら、部分木で取り出せる 　しかし、ある年齢に一致する国民を探す場合、欲しいデータはXMLデータ中に散らばってしまう XMLに含まれるデータは、ある1つの観点から構造化されたもので、必ずしも他の目的にあったデータ構造とは限らない。 →別な目的からデータを扱う場合、必要なデータが構造化されておらず、XML文書に散らばってしまう。 Todo:一見構造化されたデータが、別な観点から見るとまとまっていない事を示す。 ・「この例では」欲しいノードが、枝葉に散らばっている事をきちんと説明する ・aspect指向における、関心事がone moduleに固まっているということは、ここでは部分木に対応している。 　one module に固まっていないのと同様に、ノードも固まっていない。部分木にならないという事を しっかりと説明する。 ・横断木を使う場合は、言葉の意味をきちんと説明しなければいけない ・Xealの場合、欲しいノードを木構造に変換するわけではないので、敢えて「木構造として抽出したい」と 述べる必要はない。 なぜ欲しいノード群が散らばってしまうのか → … conference conference- name ...... year paper paper title author title author ある観点から構造化されたXMLデータ ユーザが望むデータ構造は、元の構造から変化する

4 既存技術では困難な処理 DOMやSAXでこの処理を行うのは難しい DOM SAX XMLデータ全体を読み込み操作する
データ構造の操作が面倒 大容量のXMLデータの操作には非効率 探したデータを別な構造へ変換する手間 SAX XMLデータを木構造として扱わない 複雑な構造を取り出すのがDOMよりさらに困難 このような処理は、既存のXML文書を操作するためのAPIである、DOMやSAXでは困難です。 DOMは、XMLデータを全て読み込み、木構造のデータとして操作するAPIです。 DOMでこの例のような事を行う場合、複雑な構造をした欲しい文献のデータを探すのも大変ですが、 探したデータを別の構造のデータに変換するという手間もあります。 また、DOMはXMLデータを全て読み込んで操作するため、大容量のXMLデータの操作には 効率が悪いと言えるでしょう。 一方SAXは、イベント駆動型のAPIです。XMLデータ全体をメモリ上に読み込まないため、 DOMよりメモリを節約して操作ができますが、XMLデータを木構造として扱わないため、 複雑な構造を取り出すのが、DOMよりさらに困難です。 SAXは文書を先頭から順に読み込み、発見した要素や文字列に対して次々と処理を行うAPIで、大容量の文書が扱える。 しかしSAXは、XMLデータをノードの列として扱い、木構造として扱わないため、要素同士が親子関係かどうかを調べる プログラムを自分で書かなければならない。 そのプログラムは煩雑で、しかもノードが散らばっている場合、コーディングがとても大変になる。 枝に沿って探さないと、見つけるのが大変 SAXは要素を処理する順を決められないため、散らばったノードを探すプログラムの記述が大変 ・この例における処理の特徴と、問題点についてもう一回整理する。 ・DOMやSAXという言葉は、説明しながら出す（アニメーション） ・SAXについては、なぜ横断的なノード集合を扱うのが難しいか、述べる必要がある。 　→構造を再構成しなければならないから 　（文書の先頭から順にノードを読み込む→処理を行うノードの順番が決まっている 　　→ノードを処理する順番を決められない 　　→Ex. あるノードの処理を行った後に、その子ノードを処理する事ができない 　　→あるノードと、次にくるノードの階層的な位置関係を知ることができない 　　→読み込まれるノードとノードの関係を、自分で復元して、それが必要なノードかを 判別するプログラムを書く必要がある 　SAXでは、要素を処理する順番が決められている 　→SAXでは、ノード間の特定の関係（親子関係、兄弟関係）を持つ要素順に処理を行うことはできない 　→しかし散らばったノード間の関係は、要素の子孫関係や兄弟関係で表される 　→特定の関係を持つ要素を、探すプログラムを書かなければならない //　→SAXで散らばったノードを扱うためのプログラムを書かなければならない 　→ノードの階層や発見順、名前を 　→散らばったノードを探すプログラムは、複雑で大変

5 Javaライブラリ「Xeal」の提案 XMLデータの参照・修正を支援 拡張したXPath を用いて取り出したいデータ構造を指定
データ構造変換器つきのDOMとみなせる 用途に応じた型でユーザに提供 変更を元のXMLデータへ反映 XMLデータ ユーザプログラム 本研究では、このような処理を行うことのできるライブラリとしてXealを提案します。 XealはXMLデータの参照・修正を支援するライブラリです。 Xpathという言語を拡張したものを用いて、XMLデータから取り出したいデータ構造を指定する ことができます。 これは、大雑把に言えばデータ構造変換器のついたDOMのようであると言う事もできます。 またXealは、XMLデータから取り出したデータ構造を用途に応じた型でユーザに渡すことができます。 また、データの変更を元のXMLデータに反映させることができます。 特徴は箇条書きで、単語で説明 横断木->　ノード群 SAXで必要なコーディングの手間を解消 指示 Xeal 探索 取得 例：社員データを取り出すpath /questionnaires//(this[]) result[age/text()=“20”]/ {(int)following::year/text(), answer/text()} SAXでは困難な横断木の取得を簡単に行うことができる

6 取り出したいデータ構造の指定法 拡張したXPathを用いてデータ構造を指定 XPathは本来、経路を用いて要素を指定する言語
Paper要素をフィルタリングする条件 /references //paper [author/text()=“Z”]/ { author /text(), title /text(), (ancestor::conferences) / conference-name /text(), (ancestor::conference) / (int) year /text() } references conferences ...... conference- name … conference Xealでは、拡張したXpathを用いてXMLデータ内のデータ構造を指定します。 Xpathは本来、経路を用いて要素を指定するための言語ですが、本研究では、このXpathを データ構造を指定するための言語として用いました。 先程の例で、取り出したかったデータを指定するPathが、この左下の図です。 このPathについて説明します。 まずreference要素から、その子孫要素にあたるpaperという要素を指定しています。 このpaperをフィルタリングする条件として、author要素の内容がZ氏である、 という条件が用いられています。 以下はZ氏の文献に対して、著者、題名、学会の名前、年度を取り出すための記述です。 最初のauthorとtitleは、それぞれpaperの子要素のauthorとtitleを指定しています。 次の要素ですが、これはpaperの祖先に当たるノードで、conferences というノードを 指定しており、さらにその子要素である、conference-name要素を指定しています。 次のyear要素も同様です。 　なお、赤字は拡張した文法なので、次のスライドで説明します。 ...... year paper paper title author title author その要素から見て祖先にあたる要素を指定 赤字は拡張した文法

7 拡張したXPathの文法について 複数のノードを指定：｛｝ データを受け取る時のクラス、型を指定：（type）
//paper /{author /text(), title /text()} データを受け取る時のクラス、型を指定：（type） /paper /(int) year /text() 探索のみに利用するノードを指定：（） /paper /(ancestor::conference) /year /text() 拡張したXpathの文法について説明します。 まず、複数のノードを指定するための波カッコ記号があります。 これは、paper要素に関連付けて複数の要素を指定するために用いています。 次に、データを受け取る時のクラス、型を指定するキャスト記号があります。 この例では、年度を表すyear要素を、数として扱うためint型と指定しています。 指定した型でどのようにしてデータを受け取るかは、後で説明をします。 また、丸カッコ記号は、探索のみにノードを利用する記号です。 この例で、ancestor::conferenceは、conference-nameを探すための、単なる 位置情報として用いているため、これに対応するノードはユーザにとって 必要ありません。 そのため、この記号を用いています。 /reference //paper [author/text()=“abc”]/ { author /text(), title /text(), (ancestor::conference) /conference-name /text(), (ancestor::conferences) /(int)year /text() }

8 データを用途に応じた型で提供する仕組み Pathを元にデータを扱うためのクラスを生成し、データをそのクラスのオブジェクトとして提供
DOMのように生の木構造で渡されても、ユーザは不便 pubilc class Paper { String _author; String _title; int _year; String _conference_name; } Path クラス生成器 データを用途に応じた型でユーザへ提供する仕組みについて説明します。 XealはPathを元に、データ構造を扱うためのクラスを生成します。 データはそのクラスのオブジェクトとして、ユーザに提供されます。 例に挙がっていたPathを元に生成されたクラスは、この右の図のように なります。 Author、titleといった、必要なデータをクラスのフィールドとして持つ Paperクラスです。 取り出したデータ構造を、DOMのような木構造で渡されるよりは、 このようなクラスのオブジェクトとして渡された方が、ユーザにとつても 便利でしょう。 またPaperオブジェクトを、VectorやLinkedListの形で提供するための 指定も、Pathに記述することができます。 ノード群を用途に応じた構造、型でユーザへ Pathを元に、用途に応じた構造、型をしたクラスを生成し、 抽出したデータをそのクラスのインスタンスとしてユーザへ渡す →ノード群を、用途に応じたクラスのインスタンスとしてユーザへ →用途に応じたクラスはPathを元に生成され、ノード群を、そのクラスの インスタンスとしてユーザへ 簡潔にして表す。 Xealは、Pathを元にXML文書中から得られた横断木を扱うためのクラスを 生成します。 例えばこのようなPathを元に、探索した横断木を格納するためのクラスとして このようなクラスが生成されます Pathの中に格納する型や構造に関する記述を行うことができ、 横断木はPathで構造を指定したオブジェクトとしてユーザに渡されます。 Paper オブジェクト を Vector や LinkedList で提供するための指定も可能

9 XSLTとの比較 XSLT：XMLデータからXMLデータへの変換規則を定める言語 変換が非効率的 データの変更が困難
変換したデータを、DOMなどで再度オブジェクトにする手間 データの変更が困難 XSLTで変換したXMLデータに修正を加えても、元のXMLデータへ反映させる事が困難

10 Xealは高速に処理が可能 XSLTで変換したデータをDOMで操作する場合とXealで、データ構造の取り出しにかかる時間を比較
実験マシン： (UltraSPARC III　750MHz　× 2, 1024MB , Solaris 8) 「何を比較した実験か」を明確に説明する 結果 　一番速かった 　大容量の文書を検索できた 実行時VMメモリ： 64MB 探索に用いたPath： /site//closed_auction/price/text() XSLTは、この容量のデータまでしか処理できなかった 比較対象として選んだ既存技術の組み合わせ XSLTで抽出したデータをDOMで操作 DOMでデータを読み込んだ後にXPath Engineで必要なデータを探索

11 まとめと今後の課題 XML文書の参照・修正を支援するJavaライブラリの作成 今後の課題 拡張XPathを用いてデータ構造を指定
用途に応じた型でユーザへ渡す 今後の課題 探索速度の向上 探索の条件を動的に与える事ができないか