ぜひ押さえておきたいデータベースの教科書

先日のエントリで少し話したのですが、僕が在学していたときの東大にはデータベースを学ぶためのコースというものがありませんでした（DB関係の授業は年に１つか２つある程度。現在はどうなんだろう？）。そんなときに役だったのは、やはり教科書。読みやすいものから順に紹介していきます。（とはいってもすべて英語の本です。あしからず）

一番のお薦めは、Raghu Ramakrishnan先生 (現在は、Yahoo! Research) の「Database Management Systems (3rd Edition)」。初学者から研究者まで幅広く使えます。データベース管理システム（DBMS）の基本概念から、問い合わせ最適化、トランザクション管理など、これらを実装・評価するために必要な、「DBの世界での常識」が、丁寧な語り口でふんだんに盛り込まれています。この1冊を読んでおけば、DBの世界で議論するための土台が十二分に身に付きます。

2つ目は、StanfordからDB界を引っ張っている3人の先生、Hector Garcia-Molina、Jeffrey D. Ullman（Ullman先生は昨年に引退したのですが、まだラボに顔を出しているようです）、Jennifer D. Widom （世界1周旅行に出かけているらしい…）による「Database Systems: The Complete Book」。これもRaghu本と同じように、DBがどのように作られているかを知るのに良い教科書。問い合わせ最適化などに関しては、こちらの方が詳しいです。Raghu本では、データベースの知識を広く扱い、それぞれに大事な視点を紹介しているのですが、こちらの本ではその定式化、アルゴリズムの詳細にまで踏み込んでいたり、と充実しています。

次はトランザクション管理の本を紹介。データベースにおけるトランザクション管理の実装には、これでもか、というくらい非常に多くの知識を要します。まず、データベース上で多数の検索・更新処理（トランザクション）を並列に実行したときに、安全にデータを保存するとはどういうことか、そして、更新に失敗したときに、どうやってもとの状態にデータベースを復元するか。さらには、並列化しトランザクションのスループット（1秒あたりに処理できるトランザクションの数）を向上させるために重要な、ロック管理（どの部分のデータを保護し、どの部分にアクセスを許すか）についてなど。これらについて把握していなければ安全・かつ高速なDBなどはとても実装できないでしょう。

Gerhard Weikum先生による「Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery」は、トランザクション処理に関する古典的な話題から新しい話題までを理論・実践の両面から初めて整理した画期的な本です。この一冊があれば、過去のトランザクション理論の本は読まなくても良いくらい内容が充実しています。
ここで導入される階層化ロックという概念により、1993年にトランザクション処理の大御所であるJim Gray（一昨年にボートで遭難。いまだ消息不明…）が書いた「Transaction Processing: Concepts and Techniques(こちらは詳細な実装に興味がある人にお薦めです)」にあるような従来のロックの管理方式の正当性が、綺麗な形で裏付けされていくのは圧巻です。Jim Gray本人が「自分が書きたかった本」と称賛するのもうなずける内容。特に関連文献の項が充実していて、この一冊があれば、過去から現在までの研究の流れが非常によくわかり、詳しい情報へのアクセスが容易になります。

ロック理論だけではなく、実装上の問題、障害回復、分散トランザクションと、トランザクションに関する話題は網羅されています。B+-tree以外のindexがなぜトランザクション処理にはうまく使えていないのか、など、トランザクションを極めようとするなら、ぜひ手元に欲しい１冊です。

最後は、データベースの歴史を知る上でとても大切な一冊。PostgreSQLを開発したMITのStonebraker先生らによる「Readings in Database Systems」（通称 red book）です。この本は、過去30年に渡り重要な功績となった論文を集めたものです。30年の間に蓄積された論文の数は膨大で、どこから読み始めればいいかわからないものなのですが、この論文集のおかげで、重要なものから順に読んでいくことができます。論文以外の解説記事も面白く、1979年にCoddがRelational modelを提唱した前後、どのようなデータベースシステムが良いかという議論が活発になされて、結局どのような顛末になったかまで書かれてあります。XMLのような階層型データも当時から話題であったし、データの意味・モデルに基づいたsemanticデータベースや、最近よく話題になるような、プログラムで扱うオブジェクトの保存に特化したオブジェクトデータベースなども昔、一度市場から消滅している過去があるのです。

実装に特化した話も秀逸で、なぜDBMSではトランザクション管理、インデックスなどをモジュール化した実装ができないのか、分散（クラウド）データベースでは、どのようなシステム構成が考えられてきて、落ち着きどころはどこか。さらには、なぜXMLデータベースは成功しないか、など一刀両断していて、長い歴史をみてきたからこそ書ける切り口がとても面白い本です。Stonebraker先生も、5年10年も立てば、昔に熱心に議論されたことが忘れられて、また同じような研究が盛り上がるような現状を危惧してこれをまとめたとか。「歴史は繰り返す」というのは本当ですね。（はてな界隈でもこの「歴史は繰り返す」現象をよく見かけるのですが、大人げないので敢えて突っ込みを入れるようなことはしていません）

他に、これらの本がお勧めな理由としては、世界中の大学でデータベースの講義用の教科書として使われていて、Googleで検索するだけで講義資料が手に入る、というのも特徴です。さっと内容を調べたいときには、講義資料を検索するとよいでしょう。

研究寄りの話ばかりしてないで、もっと実用的なOracleとかMicrosoft SQLServer、DB2などの商用データベースや、オープンソースのPostgreSQL, MySQL, SQLiteなどを紹介したらどうしたって？ そんなに欲張らなくても大丈夫。最初に紹介したRaghuの本でも読んでおけば、それぞれの製品で、SQLで検索・更新がどのように実行され、indexがどう使われるのかなんて、すぐわかるようになります。他に必要な知識は、SQLの方言や、それぞれのシステムでデータがディスク上にどのように配置されるかという情報くらい。それがわかれば、検索の種類やテーブル設計の違いで、パフォーマンスにどのような影響がでるか、より正確に把握できるようになることでしょう。オープンソースのシステムなら、このようなDBの知識を持った上でソースコードを読んでみると、素早く全体の構造から実装の詳細までを把握することができます。

関連情報

• DBの基本を勉強したい人へオススメする本（日本語の文献が良い人へ）
• Leo's Chronicle: XML時代の終焉 ~ XMLから再びCoddへ (XMLも結局Coddの手のひらの上だった、というお話。歴史は繰り返す)
  
• Database Column: GoogleのMapReduceは時代への大いなる逆行だ (原題 MapReduce: A major step backwards. By David Dewitt and Michael Stonebraker) (歴史は繰り返す、のもう一つの例。コメント欄が熱い）

東大で学んだ「勉強」の意味－「教わる」から「学ぶ」へ

以下の記事を読んで、これは大学としての文化が違うのだなと感じました。

大学ってもっとすごいところだと思っていた。

なんかこう、毎日が発見に溢れていて大学じゃなきゃ知り得ないことがたくさんあって・・・
そんな素晴らしい世界だと思っていたのに・・・。

大学で秘伝を習うたった1つの方法

対価を支払っていないから秘伝を知り得ていないのだ。そこにいる人たちの中で、賢い人たちは全員秘伝を知っているし、その取得方法もわかっている。
とりあえず自分が、秘伝を教えてもらえるのにふさわしい対価を払えるようになろう。さすれば、自然と大学にある知の秘伝があなたのものになる。

どうやら大学には「秘伝」なるものがあって、それは「対価」を払って「教わる」か「引き出す」ものらしいです。「対価」として考えられるのは、学生さんのポテンシャルであったり、議論していてわくわくさせてくれるような「きらりと光る何か」だと思います。そういった教えることへのやりがいを感じれば、教員の方も喜んで「秘伝」を伝授する（とは思います。少なくとも僕自身に関しては）

しかし、いざ「秘伝」とも言うべき知見の集大成である論文や、コンピューター系ならソースコードが目の前に差し出されていても、内容を自分で読もうとしない（あるいは読み切れない）人が多く見受けられるようになりました。

近年、大学院での教育に重点が置かれるようになって、東大の大学院にも、東大の学部を経ずに、他の大学からの学生が多く入ってくるようになっています。もちろん、そこらの東大生より優秀な人もいるので驚かされることもありますが、どちらかというと、カルチャーショックを感じることの方が多いです。それは、彼らに共通して、

勉強は「教わる」ものだ

という意識が非常に強いこと。知人の助教（こちらも東大上がり）と話していても、やはりそう感じるそうです。

実は、東大に伝わる「秘伝」は、この正反対。

勉強は自ら「学ぶ」ものだ

「勉強」は人様から教えてもらうものではなく、自ら学んでいくもの。この意識が染みついてていたから、「勉強ができる＝なにがいい？ (404 Blog Not Found)」などで述べられている人から押し付けられるという「勉強」の定義の仕方には非常に違和感を覚えます。

また、東大で講義を受けていると、

「わからないところは自分で学ぶのが、大学院ですからね」

と言われることが多くあったし、大学時代の研究室の教授に、

「私は私の研究をします。みなさんも、自分で好きな研究をしてくださいね」

と、まったく教授から研究指導を受けなかったにもかかわらず、その研究室にいたメンバーのほとんどが、いまや旧帝大の教授にまでなっている、という実話もあります。

僕が卒業した東京大学理学部 情報科学科なんてところは、C言語の授業がカリキュラム上に全くないにもかかわらず、C言語でプログラミングする課題が出たり、「Javaくらい自分で学んでくださいね」とか言われたり、そういうのが当たり前に要求されるので、学生の方も自分で本を買ってきて1週間で新しい言語を学んで課題を仕上げてくる、というのが日常茶飯事になっています。

それに、僕の専門はデータベースなのですが、それに関連した講義は、在学中にたったの1コマ、さわり程度の授業しかありませんでした。DBのことは本当に論文と教科書だけで学んでいます。データベースの学科があって懇切丁寧なカリキュラムがある大学がうらやましくて仕方がないです。

教えてもらわなくても人が育つのが東大というところ。ただ、先にも述べたように、学生さんの方の意識が「教えてもらう」側に傾いてきているので、最近は、教える側もより丁寧にと力を入れています。従来のように、「残りは自分で勉強してきてね」、と放り出すだけだと、「勉強」しきれずに、試験・レポートで大半がさんざんな成績になってしまったり…。それでも、どんなに難しい試験だったとしても、満点はいつもいて、自ら「学べる」人がちゃんといることがわかります。

東大生が「学歴」を気にしないというのは、それはもちろん少なくとも日本の中ではトップクラスの大学だから引け目を感じなくて済むというのもあるけれど、「自ら学ぶ力を持った人」の強さを知っている、というのも大きい。「学ぶ力」は「学歴」を問わないから。だから、先のエントリで大学に失望している人には、もっと多くを自ら学べるように「頑張れ」とエールを送りたいと思います。

（追記）

誤解のないように断っておきますが、東大の前期教養課程（1～2年時）の必修科目の講義（特に実験など）は教材・教育方法に力を入れていて非常に丁寧です。実験データの整理の仕方など、論文を書くときに必要な力を叩き込んでくれます。だから、グラフには単位までしっかり記入するなどといった基本が身についてない他大学の学生さんをみると、逆に、ちょっとがっかりするものです。。。

（さらに追記）

誤解を招きそうだったので補足。東大の授業が手抜きなわけでは決してありません。ただ要求するレベルが総じて高いものになるため、授業が「手取り足取り」というわけにはいかず、必ず自分で学ばないといけない部分が出てくるのです。プログラミングなら、オブジェクト指向の考え方などはほとんど教わりませんが、オブジェクト指向で組まれたコードを読み書きする必要はあったりします。または、最新のCPUのアーキテクチャについて書かれた論文をぽんと渡されて、それを読んで発表する授業など、習った知識だけではこなせない課題が出されることも往々にしてあります。

（補足：2009年1月18日)

こう書くと、学生が皆自ら「学ぶ」のなら、大学の存在意義はないと思われるかもしれません。けれど、それだけでは「学ぶ」ことを続けていくには十分ではありません。なぜなら、周りに何もないところで、勉強を続けていくのは至難の業でからです（教育機関が整っていない国や地域のことを想像してみてください）。「学ぶ」ための題材、施設、そして学ぶ意欲を刺激する教師や仲間が集まってくることに、大学の本当の価値があると思います。

湯島天神の初詣

皆様、あけましておめでとうございます。

年末に頑張って論文を書こうとしていたのですが、かなりの熱が出て4日間ばかり寝込んでしまい、結局何もできませんでした。皆が休みの日は休め、ということでしょうか。とほほ。子供が生まれてから、土日に働くのが難しいことをつくづく実感したので、そもそも休みに仕事するような計画ではいけないのでしょう。

大晦日にようやく回復したので、毎年恒例の、東京天神うどんさんの年末限定おそばを食べに行きました。あたたまります。

湯島天神は11時頃には初詣客が押し寄せ、警官も交通整備をしていたりと、もう大混雑なのです。到着に遅れてしまったときは、年末は夜通しで営業しているこのお店でちょっとくつろぐのが一興です。

下の写真で中央奥が湯島天神で、この位置で参拝まで約45分待ち。でも、行列はもっと後方まで続いているので1時間待ちは必至。寒いので防寒用具は忘れずに。

毎年この様子を見ていて思うのですが、実は、ここ以外にも比較的、列が短く、中に入りやすい場所があるのです。写真の天神正面から並んでいる人たちは今回が初めてでそちらの入口を知らないのか、待ち行列なんて苦にしない方々なのか、あるいは伝統を重んじて「年籠り」を路上でしているのか、いつも不思議に思っています。

僕はどうするかというと、元旦を避け４～６日くらい過ぎてからようやくお参りに行っています。もうそれは初詣というべきものではないのかもしれませんが、湯島天神の菅原道真様も、人が少なくなった方がゆっくり話も聞けるでしょう、ということで。

それでは。今年もよろしくお願いいたします。

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のように単一のテーブルだけだと心もとない、けれど構造が入り組みすぎても、扱いきれない。そして、このもどかしさと真正面に向き合うのが、データベース研究の世界なのです。

Gmailのショートカットキーが覚えられないときは

「?」キー（Shift+/)を押しましょう。ショートカットキー操作の一覧が出てきます。

この中で僕がよく使うのは、

• g, i と押して inboxに戻る（再読み込みにも使います）(Go to Inbox と覚えます）
  
• g, l (Go to Label) と押して、ラベルを検索
• /  で検索窓にフォーカスを合わせる
• メールを見ながら、「.」を押して、ラベルを付ける　（ラベルを選ぶときに、頭文字のキーを打ち続けると早く選べます）
  

などです。お試しあれ。