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

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

ユーザが望むデータ構造は、元の構造から変化する 取り出したいデータ構造 データを元の構造と異なる側面から取り出したい 学会別や年度別ではなく著者名 取り出したいデータ構造が、元の構造から変化 部分木ではだめ 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データ ユーザが望むデータ構造は、元の構造から変化する

既存技術では困難な処理 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で散らばったノードを扱うためのプログラムを書かなければならない 　→ノードの階層や発見順、名前を 　→散らばったノードを探すプログラムは、複雑で大変

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では困難な横断木の取得を簡単に行うことができる

取り出したいデータ構造の指定法 拡張した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 その要素から見て祖先にあたる要素を指定 赤字は拡張した文法

拡張した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() }

データを用途に応じた型で提供する仕組み 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 で提供するための指定も可能

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

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で必要なデータを探索

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