Top 5 Database Research Topics in 2008

岡野原君が自然言語処理関連で2008年に読んだ論文のベスト5を紹介しています。それに倣って、僕も個人的にインパクトのあった2008年のデータベース研究のベスト５を集めてみました。

• Michael J. Cahill, Uwe Röhm and Alan D. Fekete. Serializable Isolation for Snapshot Databases. SIGMOD 2008. (ACM DOI)

真っ先に思い浮かんできたのがこの論文。SIGMOD2008のベストペーパーでもあります。僕自身、トランザクション処理を長く研究していた経験から、Serializability（ディスクのread/writeの順番をあるプロトコルに従って入れ替えても、データベースの検索・更新結果に影響を与えない）を保障しつつ、一秒間あたりに処理できるトランザクションの数（つまりスループット）を上げるのは、ものすごく難しいことを実感していました。ロックの粒度、デッドロックの回避、インデックスのconcurrency(同時読み書き）管理などなど、同時に考えないといけない要素が多すぎるのです。

では、現在の商用DBMSではどう高速化しているかというと、snapshot isolationと言って、データベースのある時点での状態(これをsnapshotと呼ぶ）を保持し、readerはsnapshotを参照し、writerは新しいsnapshotを作るようにして、読み書きが衝突しないようにしています。これは確かに性能が出るのですが、特定のread-writeパターンで、serializabilityが崩れてしまい、トランザクションをやり直す（rollbackする) か、あるいは、rollbackが起こらないように検索・更新のworkloadを設計するのが大変でした。

この論文は、そんなsnapshot isolationを、性能をほとんど落とさずserializableにする話で、実装も簡単にできるという素晴らしさ。著者に会ったときにソースコードが欲しいと話したらBerkeleyDB上での実装を公開してくれました。（この話は「PFIに行きました」のエントリでも言及しています)。First AuthorのCahillさんは、Sleepycat (BerkeleyDBの開発元、現在はOracleに買収）で七年働いていたBerkeleyDBの開発者で、こんな改良を施すのもお手のものだとか。どうりでこんな研究ができるわけだと納得。

今後、トランザクションの教科書に一節が追加されるような非常にインパクトのある研究です。各種DBベンダーもこの方式を実装し始めているのではないかな、と思っています。（複雑なトランザクションの処理で新たなボトルネックが出てくる可能性はありますが）

参考文献：Alan Fekete , Dimitrios Liarokapis , Elizabeth O'Neil , Patrick O'Neil , Dennis Shasha, Making snapshot isolation serializable. ACM Transactions on Database Systems (TODS), June 2005　(なぜsnapshot isolationをserializableにできるか、という証明部分。こちらも面白い）

• S Harizopoulos, DJ Abadi, S Madden and M. Stonebraker. OLTP Through the Looking Glass, And What We Found There. SIGMOD 2008.
  

もう一つもトランザクション関連。MITのStonebraker教授(PostgreSQLを作った先生）のお弟子さんたちの研究ですが、現在主流のrow-oriented storage（テーブル行単位でディスクに配置していくもの）で、ロックマネージャーを外し、ログを外し、、、とやっても、トランザクションで100倍の性能を上げるのは難しい、ということを示した論文。近年、彼らの研究は面白くて、C-Store (列ごとにテーブルを分割して圧縮。性能抜群）や、 H-Store(トランザクションの意味を考えて、仕事の単位を分割、sequentialに処理して速度を稼ぐもの)など、One-size doesn't fit all (DBMSも用途に応じたものが必要）という時代の流れをリードしていく存在で、要注目です。

• Taro L. Saito and Shinichi Morishita. Relational-Style XML Query. SIGMOD 2008.　(ACM DOI)

手前味噌で申し訳ないのですが、XMLで表現されるデータ構造を「そのまま保持することに価値がある」と錯覚していた時代に区切りをつけるために、どうしてもこの研究が必要でした。ポイントは、XMLの構造そのものが重要なのではなく、XMLが含んでいるデータモデル(スキーマ）の方が大事で、「XMLの木構造はそのデータモデルの一表現にすぎない」、と示したことです。（参考：「Leo's Chronicle: XML時代の終焉 ~ XMLから再びCoddへ」）木をそのまま維持しなくてもよいようになると、XPath, XQueryなどの問い合わせ言語、インデックス、ストレージなど、従来のXML研究を見直していくことができ、木構造に捕らわれていては難しかったもの（例えば、木構造を保持した索引で、サイズが小さくかつ、更新しやすいものは、未だに作られていません）でも、木構造を捨てることで様々な最適化が期待できるようになりました。

• C. Olston, B. Reed, U. Srivastava, R. Kumar and A. Tomkins. Pig Latin: A Not-So-Foreign Language for Data Processing SIGMOD 2008.
  

Yahoo!のグループによる、分散計算と、構造化データを意識した新しい問い合わせ言語の設計、実装です。GoogleのMap-Reduceでは、分散計算を手軽に書けるのが特徴ですが、key, valueのペアでデータを出力するという枠組みは低レベルすぎで、構造を持ったデータをどんどん組み立てて処理を続けていくプログラムを書くには大変でした。

Yahoo!のPig Latinでは、データをグループ化したり、ネストさせたりする処理を導入して、プログラマの負担を軽減することを狙っています。似たような例として、フラットなSQLでは書きにくいのだけれど、XQueryだと階層をたどってデータを出力するプログラムが書きやすいという話があります。言語の能力的にはどちらが上ということもないのですが、「書きやすさ」は歴然と違う。SQLやkey->valueだけでは不便だったことを改善していく試みは、Relational-Style XML Query(XQueryでも不便だった階層を持ったデータの扱いを簡単にする）にも通じるところがあって、非常に関心を持ってウォッチしています。

• Remembering Jim Gray. Communications of the ACM 2008, Vol 51. No. 11.
  

最後は論文ではなく、雑誌記事の紹介です。1998年にTuring Award（コンピュータ系での言わばノーベル賞）を受賞し、 2007年にボートに乗って遭難してしまったJim Gray。トランザクション処理で大きな功績を残した、そんな彼に寄せられた記事を集めた特集号です。一人の研究者にこれほどのtributeが集まるのはすごいことです。Jim Grayは、ロックの粒度（テーブル単位、レコード単位のロックなど）を織り交ぜて使う手法を開発するなど、今なおその技術はDBMSの実装に使われています。トランザクション処理は非常に身近な存在です。銀行しかり、駅の改札もしかり。現代社会でJim Grayの恩恵を受けていない人はいないと断言しても良いです。

僕自身、Jim Grayとは巨大な生物データの扱いについてメールで議論したこともあり（駆け出しの研究者の僕にも、丁寧に返事をしてくれるような優しい人でした）、そんな彼が遭難したと聞いたときは、心にぽっかり穴があいたような、そんな気持ちになりました。僕だけでなく、やはり、これだけ多くの研究者に慕われているこの人の話題は外せない、ということで。2008年は彼の功績を振り返ってみるよい機会になった年でした。

以上、僕個人としてのトップ５研究でした。データベースは領域が広いので、興味が違えば、まったく別のランキングになるとは思います。SIGMOD, VLDB, ICDEなど国際会議もいくつかあるのですが、実際に会議に参加して雰囲気を肌で感じることができたのはSIGMODだけなので、とても偏ってますね。他の研究者による別の切り口での紹介も欲しいな、と思います。

関連エントリー

• Leo's Chronicle: ぜひ押さえておきたいデータベースの教科書 トランザクション処理やデータベースの基礎、 Jim Grayの書いた「Transaction Processing」など、データベースに関連する様々な教科書を紹介しています。
• 論文ファイブ   稲葉君によるプログラミング言語関連の論文紹介。これを見ると、データベース屋とプログラミング言語屋さんはとても似た問題を扱っていると感じる
• 昨年の論文を振り返る　岡野原君による自然言語・圧縮関連の論文紹介。

XML時代の終焉 ~ XMLから再びCoddへ

先日、ACM SIGMODの日本支部大会に招いていただいて、「Relational-Style XML Query (ACM Portal http://doi.acm.org/10.1145/1376616.1376650)」について講演をしてきました。Relational-Style XML Queryは、XMLという複雑な構造をもったデータに対して、SQLのようなテーブルデータへの検索に使われる言語で問い合わせする手法です。

この研究の肝は、木構造データといわれるXMLでも、実はそのほとんどがリレーション(Microsoft Excelのようなテーブル形式のデータ）の組み合わせと考えることができ、そのテーブル構造の情報（スキーマ）を使うと、検索が非常に簡単に書けるという点です。

Relational-Style XML Query @ SIGMOD-J 2008 Dec.

View SlideShare presentation or Upload your own. (tags: xml amoeba)

この応用例は広く、僕が日常的に構造を持ったデータを扱うプログラムを書くときに欠かせないツールになっています。例えば、

• XMLデータからObject へのマッピング (O-X Mapping) 。この際に、DTD, XML Schemaなどは必要ありません。Objectのクラス定義が、そのまま自動的にXMLクエリ(スライド中のrelation + FD) に対応するからです。
• RDBのようなテーブルデータも木構造データのサブセットなので、検索のアルゴリズムは同一のまま、直接O-R Mappingにも使っています
• 他にも、コンパイラを自作したときにでてくる構文木を、オブジェクトに手軽にmappingするときにも使います。これも、O-X Mappingの一部。
• JSON, YAML, CSV, Tab-separated dataなども、木構造データとしてXMLと同一に扱えます。これらのフォーマットへの対応はadapterを1つ書くだけで済んでしまいます

これらの技術は、日常的にデータベースの扱いが欠かせないバイオインフォマティクスの分野で活用しています。他にも現在研究中で、ここに紹介できるほどまとまってはいないのですが、それでも十分有用な応用というのも多数あります。今後、それらのC++/Javaなどによる実装は xerial.org （エクセリアルのサイト）を通して、追々公開してきたいと思います。僕自身、このおかげでSAX/DOMなどのプログラミングから解放されています。

XML・DB研究者の間では、XMLについて巷で言われているような「XMLがすべてを解決する」的な、XMLの利用価値についてはとても懐疑的です（ある日のTwitterでのTimelineより)。実際、XMLはXPath, XQuery, XSLT, DTD, XML Schemaなど関連技術の仕様が膨大で、学ぶのに非常に時間がかかるものでした。Relational-Style XML Queryが示す世界は、XMLをテーブル構造の組み合わせと考えることで、複雑そうに見えていたXMLが、実はとても簡単に扱えようになるというもの。

必要なのはちょっとした発想の転換です。XMLというデータありき、ではなく、最終的に扱いたいデータが、オブジェクトの形や、テーブル形式であるなら、それはもう巷で言われるようななんでも屋さんのXMLではなく、1970年代にCoddが提唱したrelational modelと同じ世界です。 そこでのXMLにはportableで便利なテキストフォーマットとしての価値しかありません（データを表現するための共通テキストフォーマットが確立したという意義は非常に大きいですが）。

1997年にXMLが登場して早10年。皆こぞって、Coddが提唱したrelational modelからXMLへの転換を試みてきました。けれど、そのようにもてはやされたXMLも再びCoddに帰って行くのです。

参考：A Web Odyssey:  from Codd to XML. Victor Vianu (PODS 2001)

XML、relational modelのどちらが技術的に優位か、という話ではありません。大事なのは、そのデータを扱うのは「人間」という視点です。その「人間」にとって結局、どちらが扱いやすいデータ構造なのか？ 僕自身は、この境目は非常に微妙なところだと考えています。Excelのように単一のテーブルだけだと心もとない、けれど構造が入り組みすぎても、扱いきれない。そして、このもどかしさと真正面に向き合うのが、データベース研究の世界なのです。

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

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

XML Databaseは使ってはいけない

XMLデータベースの研究しているのになんですが、僕個人としては
XML形式でデータを管理することはお勧めしません。

XMLデータを手で記述するなんていう作業はもってのほかです。
XMLは一部を間違って操作するだけで、全体がよくわからないデータになります。

Gmailで動的データ通信に使われているAJAXという技術もあって、この最後のXはXMLのことなのですが、データのやりとりはXMLでいいけれど、データの操作はXMLでないほうがいいとさえ思っています。

けれど、これをお勧めできるようにする技術の研究をしています。

企業の方などで、XMLデータベースを導入しようとしている考えている方は、
それよりも、まずrelational databaseのことを学んでください。今のrelational databaseにできなくて、XMLにできることは、そう多くはありません。逆にXMLにできないことの方が多いくらいです。

けれどこれはSQLを学べということではないのです。データベースを操作する言語なんて、データを取り出せて、安全に更新できれば、なんでもいいのです。それと同じように、XMLを操作する言語も乱立していますが、どれを使おうとどうでもいいことなのです。

XMLを使っているけれど、XMLを操作している印象を持たせないようにすることが、僕の当面の目標です。