[Research] MonetDB/XQuery

ここ２日で論文をたくさん読みました。 今年に入ってから３７本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であらわされるもの)だけでなく、データの意味とはあまり関係のない木構造のことまで考えなきゃいけないので。データの順番とかは大事なことも多いのですが、木構造の指定を間違えると答えを得られなかったりするなど、階層関係を正確に与えるべきかどうかは疑問が残るところです。

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