2007年1月25日木曜日

[Research] MonetDB/XQuery

ここ2日で論文をたくさん読みました。 今年に入ってから37本PDFをダウンロードしたようです。さすがに全部は読みこなせないですが、一応目を通して、知りたいことがあれば深く読んで。。と。現代人だからこそできる手法。昔の人はどう研究してたんだろう。不思議で仕方がないです。

内容は、Compressed Index, Data Modeling, MonetDB/XQueryに関して。圧縮索引は、うまくブロック化すれば結構XMLに使えるんじゃないかと思うのです。去年の最新の結果だと、括弧木やその変形構造上でのrank/select操作で、木の探索とか、簡単なpathの探索をやってしまおうというもので、コンパクトで検索も速いし十分実用的。ただ、XMLのデータを表現するときに、0/1で表現された括弧以外の情報(タグ名とか、node id, pre, post order, levelなど)もディスク上の近い位置に保持されていてほしいわけで…。うまく使うのがとっても難しい。下手にそういう情報をまとめてしまうと、今度は圧縮しやすい構造ではなくなってしまうので。

というわけで、圧縮索引はおいておいて、おとなしく、普通にXML DBのsurveryに戻りました。最近やけに話題になっているMonetDB/XQuery。SIGMOD2006で発表を聞いてきたときは、relational algebraにXQueryを落とし込んで、最適化するとスケジュールも小さくなって、速くなりました!と、詳細を省いた発表だったので、インパクトが伝わらなかったのだけれど、論文をみると、過去数年の研究の集大成論文になってたんですね。これ。

面白い点は、
- for loopなど各iterationの状態をtableに押し込んで、relational algebraで表現できるようにした

なるほどねぇ。これは確かに新しい。loopをまたがった最適化も表現しやすくなるし、納得。TAXのようなパターンツリーベースのXML algebraだと、こういうところまでoperationを分解できないような気がします。

- purely relational: このアプローチ、当初は、既存のRDBにXMLエンジンを埋め込みたいというところから始まっていたと思うのだけれど、合理的な部分が見えてきました。ノードとかテキストに特殊な索引をつけてXMLの問い合わせを速くするなんて方法と、algebraを分離できるんですね。特殊なindex structureが使えるなら、それにあわせてalgebraを組みなおすこともできるので、relational algebraの枠組みで全部表現できる。ここはelegantですね。


逆に、主張しているほどすごくなさそうな部分。Stair-case joinは、単に一度触ったページ部分には二度触れないというだけなので、最初の論文からあまりインパクトはなかったと思います。

- updateができる: うーん。たしかにノードの挿入に対処するのにlogical number使いたいのは、みんなわかってるのだけれど、(挿入に強いordpathはラベルが長くなりがちだし)、挿入した位置以降のpage ID -> logical offsetのmapは全部書き換え。このオーバーヘッドって大きいんじゃないのかな。。。 あと、やっぱり木の移動は削除、挿入になってしまうし。。。

- ancestoreの問い合わせ、結局、候補のノードのpost = pre + size - levelを計算するまでancestorだと判定できないから、context nodeの位置によって影響を受けやすいのかも。まぁ、preだけのindexから、順々に親をたどってもさほど遅くはないのですが。



あと思ったのは、問い合わせ方法がnavigationが中心で、pre-orderの順で近くの位置にデータが格納されていることを想定したものになってますね。でも、C-Storeのようにcolumn-orientedで、データを格納したいという需要とは逆行している?XMLだと同じpathに属するノードを近くに置いておくと、データも圧縮しやすくなるし、ディスクI/Oを抑えるのにもつながるから、ツリーを辿らなくてすむならそちらの方がいいのだけれど。XMLの圧縮の論文はほぼ全部この事実に基づいて構築されていますし。row & columnをうまく分解する必要がありそう。まぁ、それだからXMLのindexingの研究が濫立しているのですが。

そもそも、navigation queryというのは、Webが広まって需要がでてきたXMLデータ特有のもの。でも、XQueryのようにnavigationで問い合わせや更新をするのはわりと直感に反することもあります。データの持つ関係(ER-diagramとかUMLであらわされるもの)だけでなく、データの意味とはあまり関係のない木構造のことまで考えなきゃいけないので。データの順番とかは大事なことも多いのですが、木構造の指定を間違えると答えを得られなかったりするなど、階層関係を正確に与えるべきかどうかは疑問が残るところです。

確かに木でデータを表現するのは便利だけれど、木構造を使って問い合わせするのは行き過ぎのような気がして、最近は違ったアプローチを取るようにしています。この研究成果が、うまく形に残るといいけれど。

2 件のコメント:

myui さんのコメント...

基本的にpathfinderが凄いんじゃなくて,ベースとしてるmonetdb/milが良いんだと思ってますが,staircase-joinのpartitioning/skippingは良いと思いましたが。一度触った以上に,結果に必要ないページを飛ばしてますよね。

データの配置は直列化も意識しての事だと思いますよ。一番時間のかかるのそこだから。

Pathfinder関連で学術的に価値があるのは,validationのとこかもっという気がします。他は新規性が高くて凄いアプローチというわけでもないので。

それと,navigational-queryはxmldb以前にoodbでよく利用されてたかと。
MonetDB/XQueryは話題になっているかというと,むしろ直接の比較対象とするのを皆避けてるんじゃないでしょうか^^;

Taro L. Saito (leo) さんのコメント...

> makotoさん

結果に必要ないページを飛ばす過程で、子ノードは触ってしまうんだけれど、子ノードに関しては同じページに配置されていることが多いから負荷が少ないということを言いたかったのです。

直列化。確かに、preorderで格納していくのがindexing時の時間が短いよね。ギガ超えるときはここがかなり効いてきますね。たしかに。

navigationというか、そもそも階層的なデータベースの議論そのものが1970年代から続いている議論w XMLも企業のbig elephantがいいものを開発して決着をつけてしまうのかもしれませんが。

License

Creative Commons LicenseLeo's Chronicle by Taro L. Saito is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 2.1 Japan License.