ラベル Database Column の投稿を表示しています。 すべての投稿を表示
ラベル Database Column の投稿を表示しています。 すべての投稿を表示

2009年9月11日金曜日

世界のトップ研究者がデータベースの未来を語る - Claremont Report on Database Research

5年に一度、データベースのトップ研究者が一か所に集まって、データベースの未来について語るThe Clearemont Report on Database Research 2008の記事がCACMに紹介されていました。

The Claremont Report on Database Research
(各研究者のプレゼンテーションスライドはこちらから)

大規模データ処理、RDBMSエンジンの見直しの必要性、クラウド、MapReduce、開発者にとってのデータベースの使いやすさ、新しい言語は?、Uncertain data, プライバシーの管理などなど、DBの将来を見据えた意見が盛りだくさんです。

どの研究者がどの方向性を打ち出しているのかを記事から読み取れれば、もう立派なデータベース通。そして、錚々たるメンバーのなかになぜかTim O'Reillyが混じっている。。。

とにもかくにも、彼らがこうだというと、間違いなくデータベース研究の世界はこの方向に動いていくので要注目です。

2009年8月19日水曜日

SSD投入でDBMSのココが変わる! - WEB+DB PRESS vol. 52

SSDを使うとDBMSはどう変わる?徹底検証した記事を書きました!

WEB+DB PRESS Vol.52Image 予約受付中です。

実際に最新最速のSSD、Intel X25-Eを使ってDBMSのパフォーマンスを計測するなど、わくわくしながら記事を書くことができました。SSDの実力に驚きつつも、使い方を間違えるとHDDより遅くなる? など新しい発見もあり。

そして、SSDとHDDの違いがどのようにデータベースの性能に影響するのか?ディスク上のデータ構造(ヒープ、B+-treeなど)からバッファ管理など、データベースシステムの中身を解剖してわかりやすく解説しています。読みやすくなったのは丁寧に添削してくださった担当様のおかげです。感謝。

ディスクを活用したデータのソーティング(External merge sortなど)に加え、2009年6月にEdgar F. Codd Innovation Awardを受賞した喜連川先生のHash joinのアルゴリズムにもこれ以上ないタイミングで言及。MapReduceなんて、20年以上も前にDB屋さんがとっくに発明していて偉いんだ(?)などと、内容も盛りだくさんです。(最初8ページくらいの予定が、19ページ分にもなりました。。。)

SSDについてだけでなく、DBMSのチューニングを極めるなら、ぜひおさえておきたい知識が満載です。SSD時代になっても、B+-treeなどのDB技術は色褪せることなくまだまだ輝きつづけます。

乞うご期待。

関連記事


2009年5月11日月曜日

データベースシステム入門:「データベースは体育会系図書館?」

(データベースシステムとその研究の世界を一般の人にわかりやすく伝えるため、「図書館」をモデルにした話を書いてみました。試験に出そうな(?)部分は太字で強調してあります。)

データベースシステムは図書館
Image
データベース」という言葉は、データの集まりという意味です。データベースシステムの研究では、例えて言うなら「欲しい本がすぐに見つかる図書館」をいかに作るかという問題を考えます。ここで「データ」は図書館の「本」に相当し、「ハードディスク」は「本棚」がたくさん収められている図書館の建物だと考えてください。

「欲しい本がすぐに見つかる」とはどういうことでしょうか?例えば、図書目録を調べて目的の本棚の番号がわかったとしても、本棚までの距離が遠ければがっかりしてしまいますよね?(高すぎて手が届かない、とか泣けてきます)

「キャッシュ」は新刊コーナー
歩く距離を減らす工夫として、新刊書籍のように人気があるものは「新刊コーナー」にまとめて置いておくと便利です。この「新刊コーナー(あるいは人気の図書コーナー)」がいわゆる「キャッシュ」です。キャッシュはハードディスクより速くアクセスできる「メモリ」上に用意するのが普通で、図書館でいうと「受付カウンターの近く」というわけです。

重力・空間を無視して本棚を並び替えよう (B-tree)
しかし「新刊コーナー」の棚も大きさには限界があるので、入りきらない本のための本棚の方がどうしても多くなります。そこで、その本棚まで歩く距離(ディスクI/Oの回数)を減らすためにどうしたらいいかを考えます。現代社会に生きる私たちは、どうしても書店のように本棚を縦横に綺麗に並べたくなってしまいますが、そこはさすが1970年代の研究者。発想が違います。彼らは本棚を縦横ではなく、ピラミッド状に並べることを考えました。本棚を一つ設置したら、次は、1m空けて10個の本棚を並べる。そしてその10個の本棚それぞれにつき、また1mずつあけて本棚を10個並べる、といった具合です。

1m間隔で10,000個の本棚を一列に並べたら10,000mにもなってしまってとても大変です。この大変さを表すために、nを本棚の数として、O(n)(オーダー n)と書きます。これはn=10,000のとき、10,000m歩かなくてはいけない本棚の並び方、ということを意味します。一方、ピラミッド方式だと、どの本棚にでも4m歩くだけで到達できます(4m = log 10,000、1mおきに10個の本棚があるので、10を4回かけて10 x 10 x 10 x 10 = 10,000個の本棚になる)。これをO(log n) (オーダー ログn)と表します。ログオーダーのピラミッド方式では、本棚の数が10倍になっても、1mしか歩く距離が増えません(log 100,000 = 5。もしかしたら空中に浮かぶ本棚までジャンプする必要があるかもしれないですが…)。この本棚の配置はB-treeと呼ばれ現在最もよく使われています。

本はきちんと元の場所に整理して戻しましょう(インデックスとプロトコル)
ピラミッド型配置で本棚までの距離は短くなりましたが、これだけではまだ欲しい本が次の10個の本棚のうちどこにあるかまではわかりません。そこで、各本棚に、五十音やジャンル(小説、歴史など)のラベルを張っておきます。そして、本棚を、左から右の方向にジャンルごとに、しかも、五十音順に並べる、という索引(インデックス)を作るのです。抜き取った本を元の場所に戻さない悪い人がいると、当然この索引は役立たずになってしまいますので、ルールを守るように監視するのがデータベースシステムの仕事でもあります。このルールは「プロトコル(約束・手順)」と呼ばれます。

図書館は仲良く使いましょう (トランザクション管理、同時アクセス制御)
図書館の人が本棚に本を戻しつつ、たくさんの利用者が本を借りにくると、どうしても本棚までの通路が混雑して渋滞が起こってしまいます。この渋滞を解消するために、「今まとめて本を棚にもどすから、ここは通行止め(ロック)ね」とか、「こっちの棚は空いているからどうぞ」などと誘導して移動をスムーズにする(スループットを上げる)のが、「トランザクション管理」です。ロックなどを用いて複数の人の流れをコントロールすることを「同時アクセス制御(concurrency control)」と言います。

手狭になったらもう一つ増やそう (分散データベース)
そして、一か所の図書館で蔵書や利用者の数をさばけなくなると「分館」を作ります。これがいわゆる「分散データベース」で、離れた図書館にしかない本が欲しい場合は、やむなく「取り寄せ(ネットワーク通信)」をするのですが、取り寄せはコストがかかるので、1つの本はあらかじめ3か所の図書館で読めるように3冊購入(といいつつ実はコピー)しておいたり(複製・レプリケーション)、近くの図書館同士なら取り寄せも簡単なので、敢えて離れた図書館に3冊目を置いておいて移動コストを減らす(分散配置・アロケーション)などの工夫もできます。

Image
ハードディスクは体育会系?
そして図書館を形作る「ハードディスク」は、力持ちで大雑把なことは得意ですが、細かい仕事は苦手な体育会系なので、扱いがとても難しいです。「一列に並んだ本棚を100個まとめて持ってきて(シーケンシャルスキャン)」というと片手でひょいっと持ち上げるような頼もしいやつなのに、「こっちと、あれと、あそこと、あの本棚合わせて10個を持ってきて(ランダムアクセス)」というと、本棚100個を移動するより時間がかかってしまったりします。実際、上のハードディスクの写真を見てもらうとわかりますが、ハードディスクというのは要するに回転するレコードに針を当ててデータを読む構造なので、針を細かく動かす仕事は苦手です。そんな彼のために、「とりあえず100個をここ(バッファ)に持ってきて。あとはこっちで探すから」という指示を出すのもデータベースシステムの仕事です。最近流行りのフラッシュメモリー(SSD)も仕事は速いけれどどうやら体育会系脳はそのままのようで。

ここに挙げた項目はそれぞれ奥が深く、今でも熱心に研究されています。そして、ハードディスクのような体育会系脳をいかに賢くするか、というのがデータベース研究の醍醐味でもあります。それに関連する話はまた次の機会に。

(体育会系の人がアホだとか言っているわけではありません。あしからず)

関連:

2009年4月16日木曜日

Flash-Based DBMSの最前線

フラッシュメモリーを使ったSolid State Drive (SSD)の容量が160GBに到達し、市場価格も下がってきたことにより、ハードディスクの代替品としてSSDを使う用途がいよいよ現実味を帯びてきました。低容量のものなら既にiPodやデジカメ用のメディアなど身の回りにも普及しており、市場ではすでに「破壊的イノベーション(「イノベーションのジレンマ―技術革新が巨大企業を滅ぼすとき」より)」が起こっているといえます。(HDD搭載のWalkmanとか既に滅んでいる例もあるし。。。)

Image
では、SSDの登場によってデータベースシステム(DBMS)の実装はどう変わるのか?2009年4月現在の最新論文リストPFIの太田君が紹介してくれたの
で、データベース国際会議の最高峰であるSIGMOD, VLDB, ICDEや、DaMoNワークショップ(新しいハードウェアに特化したDBの研究会)の論文を中心に紹介します。こういうのは速さが勝負なので、まとめて午前中に読んでみました。

まず前提知識として、SSDの特徴は、Sequential Read(連続したブロックを読む)、Random Read(ランダムな位置のブロックを読む)の性能が従来のハードディスク(HDD)に比べて2~10倍以上、製品によっては100倍以上速いこと。

ちなみに、IntelのX25M(80GB/160GB)では、それぞれの操作で最大:
Sequential Read: 250MB/s,   Sequential Write: 70MB/s
Random Read:  35000 IO/s,  Random Write: 3300 IO/s 
一方、Seagateの7,200RPMのHDDでは、
Sequential Read: 120MB/s,  Sequential Write: 120MB/s
Random Read:  100 IO/s,  Random Write: 110 IO/s

このデータだけみると、Sequential Wite以外すべての面においてSSDがHDDを上回っていますが(Intel X25Eにおいては、Sequential Writeが170MB/sになって完全にHDD上回っています)、これはハイエンド製品のデータで、巷に出回っている1~2万円台の低価格SSDはRandom WriteがHDDより遅いのが普通です。(とある32GB SSDでは、Random Read: 3100 IO/sに対し、Random Write: 25 IO/s だとか。HDDよりrandom writeが遅いです)。

SSDの特徴をまとめると
  • read/writeのパフォーマンスが全体的に向上 (1)
  • random read/random writeのパフォーマンスに差があること (2)
  • random writeがHDDより遅いことがある (3)
このうち(1), (2)はHDDより性能が上がるだけなら、既存のDBMSがそのまま速くなって嬉しい。これは、kazuhookuさんのエントリ「 SSD がコモディティになっても状況はかわらない」にあるとおり。ただし、2008年前半は、Random WriteがHDDより速いIntel X25シリーズが出ていなかったので、(3)が深刻な問題でした。そして、実は、今出ている論文というのはこの製品が出る前の研究であるので、(3)の問題を真面目に扱っています。(国際学会の論文というのは、最先端から半年~1年遅れで出てくるものだということは踏まえておいてください。研究の最前線は常に研究者の頭の中です。)

それゆえ残念なことに、今普及している低価格のSSDには効果がありそうだけれど、今後は不要になりそうなアプローチの論文というのもあります:
  • S. W. Lee, and B. Moon. Design of Flash-Based DBMS: An In-Page Logging Approach. SIGMOD 2007. [pdf] (SSDのrandom writeが遅いので、データページ内にログも配置するとDBMSが速くなるという研究)
  • Y. Li, B. He, Q. Luo and K. Yi. Tree Indexing on Flash Disks. ICDE 2009. [pdf]  (Random writeが遅いSSD対策として、B+-treeに独自のページレイアウトをmergeして、insertionの性能を上げた研究。Random Writeが遅いSSDで実験しているから速い結果がでているけれど、IntelのX25シリーズを使ったり、key値だけでなくclustered-indexを使った場合や、ロック処理までちゃんと実装したら、実際のinsertion, throughputの性能差はほとんどないと思われる。)
これらのアプローチはもはや時代遅れに思えてきます。一方、(3)が問題だった製品を使っているにも関わらず、SSDのDBMSにおけるメリットを適格に示している論文は、Samsungのチームが関わっている以下の研究:
  • B. Moon, C. Park, S. W. Lee. A Case for Flash Memory SSD in Enterprise Database Applications. SIGMOD 2008. [pdf]  (SSDを使うと、更新の時系列に沿ってバージョン番号が付けられたrecord chainの探索(MVCCで使う)が速くなり、大規模データの問い合わせに必要な、external merge sort, hash joinの性能(ともにrandom readが多発)が高速化されることを検証した論文)
上の論文の実験でも同じシステム構成を用いているのですが、HDDとSSDを組み合わせて使うアプローチを提示しているのがこれ:
  • I. Koltsidas, and S. D. Viglas. Flashing Up the Storage Layer. VLDB 2008. [pdf] (これもまだ(3)が問題だった当時の話なのですが、状況によってディスクページの保存先をSSD, HDDと切り替えるアルゴリズムを提案しています)
SSDの価格が十分に下がるまでは、このように、random readを速くしたいときはSSD、大きなデータをとりあえず置いておきたいときや、sequential writeでもいいという場合はHDDという素直なアプローチも悪くないと思います。

「5分間ルール」から20年

1987年にJim Gray(Jim Grayに関してはこちらのエントリの最後で紹介しています)が、「5分間ルール」と称して、性能やそれに応じたストレージ価格コストを考えると「5分以内にアクセスされるデータ(4KB程度)はメモリに置いておくべきだ」という提案をしました。その10年後は、HDDのアクセススピード向上は比較的緩やかだったのに対し、ディスクの容量がメモリに比べて急激に上昇し価格は下がる、という状況が相まって、「5分間ルール(10年後)」は維持されていました。

20年後、SSDが登場して、「5分間ルール」はどうなったのか?というのが次の論文:
  • G. Graefe. The Five-Minute Rule Twenty Years Later, and How Flash Memory Changes the Rules. DaMoN 2007. [pdf
結論を言うと、「5分間ルール」はSSDに関してはそのまま。ただし、HDDに関しては256KBまでページサイズ(B+-treeのリーフなど)を増やした方が検索性能が良くなっている。SSDだと、従来通り2KB~4KBくらい小さなページサイズが速い。従って、HDDとSSDを共に使う場合、それぞれで最適なページサイズの不均衡があるので、先の'Flashing Up The Storage Layer'のような工夫が必要になるよ、という話。SSDを、メモリバッファの拡張としてとらえるか、HDDの拡張として使うかで、アプリケーションや、最適なアルゴリズムも変わることが示唆されており、SSDの利用価値がどこにありそうかを検討するブレインストーミング用の論文として便利だと思います。ちなみに、2種類のページサイズを使い分けるB-Treeは、すでに考案されている(SB-Treeというらしい)ので、こういうったものを実装してみるのも手。

ただ、「B木 - naoyaのはてなダイアリー」で触れられているようなSSDがB+-Treeを駆逐するイノベーションというのはどうも感じられていません。そもそも、B+-treeの構造と、バッファ管理、ログ、ロックやスナップショットなどのトランザクション管理は今でも十分切り離せてなくて、B+-tree以外の索引構造もいままでいろいろ研究されてきましたが(R-treeとか)、検索専用には使われても、更新用途にはどれも生き残っていません。(トランザクション管理の難しさについては、こちらを参照してください:Leo's Chronicle: Top 5 Database Research Topics in 2008

率直なDB研究者としての意見は、
DB研究者って、どうもSSDにはまだ悲観的な気がしているのだけれど、ここで、破壊的イノベーションが起こってあたふたしたりするのだろうか 
http://twitter.com/taroleo/status/1506861323
という消極的なものですが、本当は、あたふたするような事態があった方が、研究テーマが増えて面白くなるので、非常に期待はしています。破壊的イノベーション(適用分野、マーケットががらりと変わってしまうような発明)は、アプリケーションの変化に起因するものだとも思います。SSDの真の価値は、既存のDBMSが進化していく方向にではなく、まったく新しい用途のDBMSを作り得る点と考えると、今後SSDの動向を追うのが楽しくなるのではないでしょうか。

関連

2009年4月2日木曜日

学生を成功に導くアドバイス - Ullman先生からのアドバイス

(この文章は、Ullman先生に許可をいただいて翻訳し掲載しているものです。記事の掲載を快く承諾してくださったUllman先生に感謝)

学生を成功に導くアドバイス
~学生にアドバイスをする教師へのアドバイス(そして、教師が学生から学べること)

Jeffrey D. Ullman



博士課程には、二人として同じ学生はいない。そして、教師がすべきことも個々の学生に応じて変わる。自分のキャリアを振り返ってみて、うまくいったいくつかの方法と、よく使われているけれど実際には学生のためにならないやり方というのがよくわかるようになった。まず初めに述べておくと、教師のゴールとはどうやったら学生が自分自身の力で考え、新しいアイデアを組み立て、問題を解ける人になれるかを教えることだ。

Image
2003年のJeff Ullmanの退官式にて。参加した学生と同僚たち。
(訳者注: 中央左がUllman先生。左端にはJim Gray、中央右にSergey Brinなども)

教師であるあなたは、十代を終えたばかりの学生を受け持って、その分野で最も経験のある誰もができなかった何かをできることを、学生に実感させなければならない。そして、それがただの一回だけでなく、プロとしてそれを生涯続けられるようにしないとだめだ。率直に言って、私が学位を取ろうとしていたときには、博士論文に何を書いていいかわからなかったし、もしわかっていたら、大学院には行っていなかったに違いない。

やってはいけないこと

私は学生で、その後、大学の教員になった。私がいた電気工学科では、学位論文を書く方法は、たくさんの論文を読むことだという考えが定着していた。「論文の最後の章を見ろ。そこには常にopen problem (未解決問題)のリストがある。その中から1つを選んで研究し、ほんの少し発展させられるまで続けるんだ。そしてその小さな成果について論文を書き、最後に必ずopen problemの章を入れるのを忘れるな。そこに、君ができなかったことを全部書くんだ」という具合にだ。

不幸にも、この論文の書き方は今でもあちこちで行われており、凡庸な研究を助長している。そして、研究というものが他の誰かの仕事に小さな成果を付け加えることだという幻想を生んでしまっている。さらに悪いことに、そうしているうちに研究が「解くべき問題」ではなく、「解ける問題」によって左右されるようになる。論文を書き、論文を採録するのも、そのような小さな成果を付け加えるような論文を書く人たちになるが、それでは論文が物書きの世界を超えて世の中に与える影響というのは大したものにはならない。

初期の形態:理論中心の学位論文

コンピュータ科学がまだアカデミックの世界に出はじめの数年は、多くの論文が「理論的」であった。それというのも、論文による貢献がほとんど「紙と鉛筆」によるものだったからだ。定理やアルゴリズムとかそういうもので、ソフトウェアではなかった。そのような研究は、机上の空論に終わるかもしれないという弱みがあったが、理論的な論文が実際に役に立つことは十分ありえる。例を挙げると、私がプリンストン大に入る前、ベル研でRavi Sethiのもとで夏のインターンをしていた時のことだ。Ken ThmpsonとDennis RitchesがMultics(GE635計算機のためのOS)のプロジェクトに参加していた。この猛獣のような計算機は、初めて1つ以上計算に使えるレジスタを持ったもので、Raviと私に与えられた課題は、コードをコンパイルし、レジスタを最大限活用する技術の開発だった。Raviの論文は、数値演算の式をコンパイルし、与えられた数のレジスタを使って最小限のステップで計算するアルゴリズムについてだった。これは実際に数年後、PDP-11用のC言語のコンパイラに組み込まれた。

Raviの論文は「理論的」であり、私も彼も一切コードを書かなかったが、この経験は、私にどんな学位論文でも実際に開発すべきものなのだと確信させる経緯を物語っている。私たちの研究は、どこかの論文に書かれたopen problemに基づいたものではなかったし、むしろ「いくつかのレジスタを使って式をコンパイルする」という要求に応えたものだった。私たちの大きなアドバンテージは、分野を開拓してく力強さを持った環境に身を置いていたことだった。もし、ベル研にいなかったら、この問題に取り組む価値があると気付くことができたかどうかも疑わしい。我々が用いたノードへの順序づけの方法を先に論文にしていたAndrey Ershovでさえ、その研究を1レジスタのマシンでコンパイルする手法としてしか見ていなかったし、論文中で複数レジスタを持つマシンでの可能性などは示唆していなかった。

理想的なPh.D.の学生

一番理想的なシナリオは、学生が私にどんな論文を書きたいかを話して自分自身で研究を行い、かつ、学生がその論文のテーマを選んだ理由が、実際の「顧客」のニーズに基づいている場合だ。Sergey Brin (訳注:後にLarry PageとともにGoogleを起業した)は、この理想に最も近かった。というのも、BrinとLarry Pageの2人は私の助けを一切借りずとも、良い検索エンジンの必要性を認識していたし、その目標にどうやって到達できるかもスタンフォード在学中に見据えていた。ただ1つ欠けていたのは、彼らの2人とも博士の学位をとらなかったことだ。とはいえ、のちにより大きなものを手にするのだが。

さらに似たような例として、George Luekerがいる。彼はある日、私のもとに論文のテーマが何かないかと尋ねに来た。Georgeは、その時は私の学生ではなかったが、プリンストン大で応用数学のプログラムに所属していた。私はその日の朝、chordalグラフについて読んでいて、chordalityを検出するアルゴリズムはどうかと彼に提案した。1年後、彼は再びやってきて、pd-treeについて書いた彼の論文を見せてくれた。そのデータ構造は、chordalityの検査の他に、今でもいくつかの重要なアプリケーションがあるものである。他にも何人もの学生が、渋る私をけしかけて、新しい分野を学ぶ方向に引きずりこんでいった。その後、逆に私が彼らの論文テーマ選びに関わることもあったのだが…。Matt Hechtは、私にデータフロー解析について学ばさせてくれたし、Allen Van Gelderのおかげで、ロジックプログラミングを学ぶことになった。

なぜ「誰が」論文のテーマを提案するかが重要なのか? 私たち教師は、若い科学者が、自分自身の力で取り組む価値があるものを見つけられるように導こうとしている。その過程では、いくつかの判断が必要だ。何がやる価値があるのか?何が実現可能か?そして、どうやってそれをやるか?だ。教師はこれらの判断を助けてあげることもできるが、自分の力で自然にこの域に到達する学生に出会うのは楽しいものだ。それに、年をとるにつれ私が忘れないように心掛けていることは、若い人は、すでに自身の流儀に落ち着いてしまった我々にはできないようなものの見方ができる、ということだ。若い人の技術的な判断を信用するのも悪い戦略ではない。

学生は何を必要としているか

「学生を成功に導くには、多くのサービスを与える準備ができている必要がある。」

「『顧客』を見つけてあげること」。この記事の初めでも述べたが、分野の最先端の問題に触れる必要があり、その問題が実際の「顧客」に必要とされていることが大事だ。ときには産業のなかで「顧客」を見つけることもできる。私とRavi Sethiがベル研でそうであったように。そのために夏のインターンシップはとてもよい機会になりうる。しかし、教師は学生に強い研究グループでインターンをするように薦めるべきだ。強い、というのは、そこでの研究のゴールが、既存の手法に単にひねりを加える以上のことをしている、という意味でだ。

論文が理論的であれ実装による解決であれ、研究がうまくいったときに、学生がその研究の成果を実際に誰が使うことになるのか理解できるようにする必要がある。そしてその答えが、「誰かが僕の書いた論文を読んで、論文中のopen problemを使って自分の学位論文を仕上げるさ」となるようではいけない。特に理論的な論文に関わる場合は、研究が活きる連鎖が生まれるまでの道のりは長いかもしれない。アイデアがアイデアを生んで、研究成果が行きわたる状態に至るまでは。もし、学生にそんな連鎖や研究成果が生かされる道が本当にあるかどうかを無視させてしまうようでは、教師は学生へのサービスを損ねていると言える。

「走り出す前に歩み出すこと」。問題に触れさせるだけでは十分ではない。部分的に、完全にではなくてもよいが、Ph.D.の学生が、自分自身でオリジナルなことをできると自信を持つ必要がある。以下に、実際にうまくいったアイデアをいくつか紹介する。
  • 研究を始めたばかりの学生に、研究の在り方を掴む練習をしてもらうには、あなた自身が小さな問題を通して考え、博士課程の学生にその問題に取り組むように指示するとよい。あなたの頭の中で既に道筋が付けられているので、学生をあるべき方向に誘導するような質問をぶつけるのは簡単で、学生が自ら解法に至るまでそれを続けさせることができる。このような小さな体験だけでも、たいてい、学生が自分で研究に取り組めるようなるのには十分だ。
  • 学生がなるべく早く、論文を読んでいるだけの状態から抜け出し、自分自身のアイデアを生み出せるようにすること。確かに、たくさん論文を読まないと分野の知識を得ることはできないのだが、ある時点から先は、読めば読むほど、考え方がその分野の大勢一般の考え方に近づいてしまい、「枠を超えた」思考というのが難しくなってしまう。もし、学生が見込みのあるアイデアを生み出したなら、もちろん、注意深く既存の文献を探さなければならない。十分な例を通して見た経験から、学生のアイデアが既存の研究の枠内に完全に納まってしまうのは稀であると信じている。(悲しいことに、そういう場合もあるにはあるのだが)。
  • 同僚のHector Garcia-Molinaはよく学生に、理論的に最適な解法を探すことから始めるのではなく、単純で、簡単に実装できる解法で90%のゴールになるものを探すようにと指導している。最適性はあとで研究して、学位論文の重要な部分を形作ることができるからだ。
  • もう一人の同僚のJohn Mitchellは、学生が自分で新しいことができると信じる、というハードルを乗り越えたあとでさえ、学位論文の規模の大きさには委縮してしまうことを指摘してくれた。彼は、とりあえず学生に論文を1つ書くことに集中させている(より良いのは、論文誌ではなく、人に会う機会が生まれる学会のための論文を書くことだ)。学生がいくつかの論文を書いた後、それを元に学位論文を書けば、怖さが軽減する。

「アイデアを表現すること」。教師は、学生が明瞭な文章を書けるように指導しなくてはならない。良いアイデアを学生がうまく伝えることができていなければ、細かい点まで指導する。アドバイザーは論文をかなり丁寧に読見込んで、一文ずつチェックするのが、学生が最初に論文を書くときには大事だ。よくあることだが、早いうちに見つけなくてはいけないのは、簡単な部分については細かいところまで書きこんでいるが、難しい部分になると、たとえば、核となる定理の証明や複雑なアルゴリズムの細部で、非常にあいまいな記述になったり、おおざっぱすぎになったりする場合だ。教師は、難しい部分を判断し、難しい部分がしっかりと書かれるようにしないといけない。(*)

(*) 最初のうちは細かいことのように聞こえるだろうが、論文を非常にわかりやすくする方法は、何も指していない"this"という言葉を学生の論文から探すことだ。多くの学生が(学生以外の人も)"this"を一つの名詞ではなく、ある概念全体を指すのに使ってしまう。例えば、「If you turn the sproggle left, it will jam, and the glorp will not be able to move. This is why we foo the bar.(sproggleを左にまわすと詰まって、glorpが動けなくなる。だからfooしてbarなんだ)」 という文。ここで、書き手の方は、sproggleとglorpが何かわかっているので、"This is why(だから)」で示される「fooしてbar」と言える理由が、glorpは動かないからとか、sproggleが詰まっているからなどと理解できる。けれど、まだglorpやsproggleがどう動くかまだよくわからない読者の立場になって、パラグラフを注意深く書くことが大切だ。今では何も指していない”this”を見つけるのはそう難しいことではない。このようなthisはほとんど文頭にあるので、grep(訳注: 文字列検索プログラム)を使って"This"を検索すればよいだけだ。

「怖がる要因」。もう一つ教師に共通する仕事は、学生が、充実感を持ったまま、何も恥じることなく失敗できるようにすることだ。すべての学生が失敗することへの打たれ強さを持っているわけではないし、多くの学生が、まだうまくいくかよくわからないことを試すのが悪いことだと思ってしまっている。大抵の場合、学生の考える「問題」のモデルは、「宿題」から来ている。つまり、答えがわかっているものだ。そして「今週は何もできませんでした」と報告することを恥じている。たとえそれが、努力不足によるものではなかっとしてもだ。教師であるあなたも、学生が多くの時間をプログラムを書くこと、しかも、人の書いたプログラムを入力として受け取り、その中に含まれるすべてのバグを取り除くようなことに費やしてほしくはないだろう。(実際、私の同僚の学生は、一度師匠にそんなことをやれと言われていたが)。でも、学生に挑戦的でリスクもあるような仕事を薦めるのは大丈夫だ。例えば、他の誰よりもバグをたくさん見つけなさい、というような。その場合、教師の極めて大事な役割は、学生に費やす時間と努力、つまりリスクを承知の上で研究させ、何も良い成果が出なかったときのケアをすることだ。

「集団療法」。よく使われる方法で、学生を励ましつつ研究に邁進させるのに良いのは、フリーのランチだ。Ph.D.の学生のためだけでなく、学部生を研究の輪の中に引きつけるのにも使える。過去15年間、幸いにも私は、スタンフォード大の「データベースグループ(現在のInfolab)」の中にいることができた。メンバーには、Gio Wiederhold、Hector Garcia-Molina、Jennifer Widom、学生、スタッフ、そして外から来ている研究者もいた。金曜日に開かれる定期的なランチでは、学生は自分の研究についてインフォーマルな話をし、良い感じの議論がフロアでなされるのが通常だった。学生が次の学会の発表練習をしても良いし、同僚の学生から細かい点まで指摘を受けることもできる。ランチのもう一つの重要な役割が、つながりにある。グループ行事を行う社会的な集まりのなかでつながりが強くなり、定期的にある出張レポートが、外の世界について学ぶ原動力になる。

新しい形態:プロジェクトに基づいた学位論文

この段階に至るまでは長い年月がかかったが、今やたくさんのソフトウェアプロジェクトが、アカデミックの世界で日常的に行われるようになっている。それでも、純粋に「紙と鉛筆」で書かれた学位論文というのも常にあるものだが、もっと生産的な方法が、Ph.D.コースに入りたての学生をソフトウェアプロジェクトに参加させることだ。たいてい、学生は「何かをしながら学ぶ」経験ができ、ソフトウェア開発に貢献し、それと同時にプロジェクトで研究された新しい概念を学んでいく。年輩の学生は、後輩の学生を助けたり、教える経験を積む機会にも恵まれる。

この研究の形体を効率的に使った一番良い例は、同僚のJennifer Widomによるものだ。たくさんのイノベーションを生んだプロジェクト(半構造データ、ストリームデータベース、そして今は、不確実データのデータベース)の中で、Jenniferは次に挙げるルーチンを完璧にこなした:

1. 研究の大まかなゴールを定め、一緒に取り組む博士課程の学生のチームを作る

2. 相当の期間の時間(6~12か月くらい)を、問題に潜む基礎的な理論やモデルの構築に費やす。(Jenniferが言うには、学生を研究計画とモデルづくりの段階で巻きこむのが、彼女のやり方の際立った特徴だとか)

3. それから実装のためのプロジェクトを始める。細かい点を学生に取り組んでもらう。個々の開発プロジェクトのゴールは、ちゃんと動いて配布してもいいようなプロトタイプを作ることで、商用化できるくらい完璧なものを作ることではない。

4. 学生に、幅広い問題分野から集中して取り組むべき難しい問題を、自分なりに切り出させる。学生は自分のアイデアを組み立てていき、それが学位論文の核となり、さらに、大きなシステムの一部として自分のアイデアを組み込むことで、そのアイデアをの価値を検証できるようになる。

悲しいことに、多くの研究ファンド(たとえばDARPAなど)が、最近かなり「ミッション重視」になってきている。プロジェクトの実装の一部でPh.D.の学生をサポートできるかもしれないが、それではプロジェクトの枠を超えて自分独自の仕事をする余地がない。例えば、私はそれぞれ別の情報源から同じことを聞いたのだが、EUは「研究」を広くサポートするが、その対象はプロジェクトの派生物になるものに厳密に縛られ、プロジェクト内で上のStep 4と同じことはできない。国から博士課程の学生の予算が出るような場合あまり障害はないが、プロジェクト予算からのサポートに学生が依存してしまうような国では、第一線で活躍できる研究者を育てるのは難しくなる。

学生と起業

一風変わった決断がいるのは、教師が、博士課程の間に起業を志す学生とどうやって向き合うかだ。私の意見に賛成する人はあまりいないが、私は少なくとも、起業のアイデアがとんでもないものでなければ、学生は思い切って起業すべきだと考えている。私の考えでは、Ph.D.を取ることや、研究の世界に入ることには確かに価値があるが、しかし、それは考え得る最大の価値ではない。起業は学位論文よりより大きなインパクトを我々の生活に及ぼし得る。それに、起業してビジネスを成功させる機会をここで逃してしまえば、より多くの機会を逃してしまうことになる。もし起業がうまくいかなくても(たいていの場合そうだが)、学生にとっては数年を失うだけで、やろうと思えば博士課程を再開することもできる。

Sergey Brinは私にPh.D.プログラムをやめるかどうか相談することなくGoogleを立ち上げたが、もし聞かれていたとしたら、起業するように言っていただろう。別の学生、Anand Rajaramanは起業に関して私にアドバイスを求めてきた。彼は、あと半年で卒業というところだったが、私は、大学を出てJungleeの創始者になるように彼に言った。そのベンチャーは大成功し、数年後、彼はスタンフォードに戻ってきて、まったく新しい論文のテーマに取りかかった。それは、彼がJungleeで学んだことの一部を集約したものであり、そして彼はDr. Rajaramanとなった。

起業について考えるのにシリコンバレーにいる必要はない。良いアイデアはどこでも生み出すことができるし、良い先生なら、必要に応じて、学生の研究がベンチャー企業の土台になるかも、という選択肢を提示してくれるだろう。私は、別の大学のとある学生から来たメールをよく覚えている。「学位論文になってかつ役に立つ研究というのはあり得ますか?」と。私が肯定的に返事をしたところ、「うちの先生にそのことを説明してくれませんか」と頼まれたのだ。その先生は結局、学生に良いサービスを提供できていなかったと言える。その指導方針がごく一般的なものであったにも関わらずだ。この文章を手直ししている最中でさえ、私は、技術的な研究が、たとえ商用化できなかったとしても、やる価値があると認められるべきだという考えに行きついた。

後記

私のキャリアでの様々な仕事のうち、私が最も誇りに思うのは、53人のPh.D.コースの学生と、それに続く弟子たちだ。(http://infolab.stanford.edu/~ullman/pub/jdutree.txt と、この記事の最初の写真を参照。) その多くが、私には絶対にできなかったようなことを、驚くぐらいよくやってくれた。そして、それぞれが独自の才能を分野で発揮し、眺めているだけでもよい勉強になった。彼らの成功に私が貢献したと思いたいものだが、私がしてあげたと言えるたった1つのことは、彼らが自らの力で才能を開花できる道を遮らないようにした、ということだけだ。

著者
Jeffrey D. Ullman ([email protected]) is the Stanford W. Ascherman Professor of Computer Science (Emeritus) at Stanford University.


2009年3月11日水曜日

SIGMOD2009 Accepted Papers

SIGMOD2009採録論文が発表されました。そのうちのいくつかについて、タイトルだけから内容を推測。
  • Yahoo! Researchの"Generating Example Data for Dataflow Programs"は恐らくPig Latinのデバッグ用のサンプルデータ生成の話。Hadoopなどの上で、複雑なデータ構造を動的に組み立てていくプログラム書きながら、横に実行結果の例を「適切に」示したサンプルが表示されると、わかりやすいよね、という話。
  • ”Towards a simpler XML Schema: effortless handling of nondeterministic regular expressions”はついに来たか、という感じ。Relational styleの考えが入っていて、スキーマ(relation)から考えられるいろいろな木構造をNFAを使って同時に検証する、という流れだったら嬉しい。
  • "DDE: From Dewey to a Fully Dynamic XML Labeling" 。XMLの索引づけはもう食傷気味なのですが。。。「Fully」といいつつ挿入・削除以外の更新操作(木の移動とか)をサポートしていないと、がっくりきそう。
  • その他、multi-core CPU(Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs)とか、SSD(Query Processing Techniques for Solid State Drives)の話もちらほら。
  • 圧巻は、64番 ”A Comparison of Approaches to Large Scale Data Analysis”。Brown, MIT, UW Madison, Yale、そしてMicrosoftって、どんだけコネクションが広いんだ、あなたたちw。日本がDBコミュニティで存在感が出せないのは、こういった人脈がないことに尽きると思います。
  • それにしても、"Why Not?"ってなんだろう?DBMSがこう検索したらどう?とでも聞いてくるのかな?"Schema-Free XQuery"のときといい、Jagadishたちのグループは、論文のネーミングが秀逸です。
全体としての印象は、シリコンバレーに集まっているラボが強い。Microsoft, Yahoo! Research, HPなどなど。もともとはMITやStanford出身だったりするのですが。Stanfordもシリコンバレーの大学。

今回のSIGMODでは、僕は勝負すらできなかったので、投稿して落とされるよりたちが悪い。大負けです。悔しい。
  • 23 
    Entity Resolution with Iterative Blocking
    Steven Whang*, Stanford University
    David Menestrina, Stanford University
    Georgia Koutrika, Stanford University
    Martin Theobald, Stanford University
    Hector Garcia-Molina, Stanford University
  • 25
    Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs
    Wook-Shin Han*, Kyungpook National University
    Jinsoo Lee, 
  • 38
    Minimizing the Communication Cost for Continuous Skyline Maintenance
    Zhenjie Zhang*, National University of Singapo
    Reynold Cheng, 
    Dimitris Papadias, HKUST
    Anthony K. H. Tung, National University of Singapore
  • 47
    FlexRecs: Expressing and Combining Flexible Recommendations
    Georgia Koutrika*, Stanford University
    Benjamin Bercovitz, Stanford University
    Hector Garcia-Molina, Stanford University
  • 64
    A Comparison of Approaches to Large Scale Data Analysis
    Andrew Pavlo*, Brown University
    Samuel Madden, Massachusetts Institute of Technology
    David DeWitt, Microsoft
    Michael Stonebraker, Massachusetts Institute of Technology
    Alexander Rasin, Brown University
    Erik Paulson, University of Wisconsin-Madison
    Lakshmikant Shrinivas, UW-Madison
    Daniel Abadi, Yale University
  • 69
    GAMPS: Compressing Multi Sensor Data by Grouping and Amplitude Scaling
    Sorabh Gandhi, University of California, Santa Barbara
    Suman Nath*, Microsoft Research
    Subhash Suri, UCSB
    Jie Liu, 
  • 94
    Authenticated Join Processing in Outsourced Databases
    Yin Yang, HKUST
    Dimitris Papadias*, HKUST
    Stavros Papadopoulos, HKUST
    Panos Kalnis, NUS
  • 115
    Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis
    Frank McSherry*, Microsoft
  • 118
    Query Simplification: Graceful Degradation for Join-Order Optimization
    Thomas Neumann*, Max-Planck-Institut Informatik
  • 119
    Scalable Join Processing on Very Large RDF Graphs
    Thomas Neumann*, Max-Planck-Institut Informatik
    Gerhard Weikum, Max-Planck-Institut Informatik
  • 120
    Combining Keyword Search and Forms for Ad Hoc Querying of Databases
    Eric Chu*, University of Wisconsin-Madiso
    Akanksha Baid, University of Wisconsin-Madison
    Xiaoyong Chai, University of Wisconsin-Madison
    AnHai Doan, Univ of Wisconsin
    Jeff Naughton, University of Wisconsin
  • 121
    Attacks on Privacy and deFinetti's Theorem
    Daniel Kifer*, Penn State University
  • 122
    Optimizing Complex Extraction Programs over Evolving Text Data
    Fei Chen*, UW-Madison
    AnHai Doan, Univ of Wisconsin
    Jun Yang, Duke University
    Raghu Ramakrishnan, 
    Byron Gao, 
  • 142
    DDE: From Dewey to a Fully Dynamic XML Labeling
    Liang Xu*, NUS
    Tok Wang Ling, NUS
    Huayu Wu, NUS
    Zhifeng Bao, NUS
  • 143
    Self-organizing Tuple Reconstruction in Column-stores
    Stratos Idreos*, CWI
    Martin Kersten, CWI
    Stefan Manegold, CWI
  • 151
    Ranking Queries on Distributed Probabilistic Data
    Feifei Li*, Florida State University
    Ke Yi, Department of Computer Science and Engineering, HKUST
    Jeffrey Jestes, Computer Science Department, FSU
  • 161
    Generating Example Data for Dataflow Programs
    Christopher Olston*, Yahoo! Research
    Shubham Chopra, Yahoo! Research
    Utkarsh Srivastava, Yahoo! Research
  • 165
    Secure Outsourced Aggregation via One-way Chains
    Suman Nath*, Microsoft Research
    Haifeng Yu, 
  • 166
    ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events
    Yuan Mei*, MIT
    Samuel Madden, Massachusetts Institute of Technology
  • 190
    Serial and Parallel Methods for I/O Efficient Suffix Tree Construction
    Amol Ghoting*, IBM Research
    Konstantin Makarychev, IBM Research
  • 191
    Asynchronous View Maintenance for VLSD Databases
    Parag Agrawal, Stanford University
    Adam Silberstein, Yahoo! Research
    Brian Cooper*, Yahoo! Research
    Utkarsh Srivastava, Yahoo! Research
    Raghu Ramakrishnan, 
  • 195
    Kernel-Based Skyline Cardinality Estimation
    Zhenjie Zhang*, National University of Singapo
    Yin Yang, HKUST
    Ruichu Cai, School of Computer Science and Engineering, South China University of Technology
    Dimitris Papadias, HKUST
    Anthony K. H. Tung, National University of Singapore
  • 207
    Quality and Efficiency in High Dimensional Nearest Neighbor Search
    Yufei Tao*, CUHK
    Ke Yi, Department of Computer Science and Engineering, HKUST
    Cheng Sheng, The Chinese University of Hong Kong
    Panos Kalnis, National University of Singapore
  • 224
    Continuous Obstructed Nearest Neighbor Queries in Spatial Databases
    Yunjun Gao*, Singapore Management Univ.
    Baihua Zheng, Singapore Management Univ.
  • 235
    Keyword Search in Databases: The Power of RDBMS
    Lu Qin*, CUHK
    Jeffrey Xu Yu, The Chinese Univ. of Hong Kong
    Lijun Chang, 
  • 242
    Why Not?
    Adriane Chapman*, MITRE Corporation
    H.V. Jagadish, Univ. Michigan
  • 244
    Dictionary-based Order-preserving String Compression for Main Memory Column Stores
    Carsten Binnig*, ETH Zurich
    Stefan Hildenbrand, ETH Zurich
    Franz Frber, 
  • 245
    ROX: Run-time Optimization of XQueries
    Riham Abdel Kader*, University of Twente
    Peter Boncz, CWI
    Stefan Manegold, CWI
    Maurice Van Keulen, University of Twente
  • 253
    An Architecture for Recycling Intermediates in a Column-store
    Milena Ivanova*, CWI
    Martin Kersten, CWI
    Niels Nes, CWI
    Romulo Goncalves, CWI
  • 266
    Scalable Skyline Computation Using Object-based Space Partitioning
    ZHANG Shiming, HKU
    Nikos Mamoulis*, University of Hong Kong
    David Cheung, University of Hong Kong
  • 269
    FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance
    Shimin Chen*, Intel Research Pittsburgh
  • 292
    Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval 
    Jong wook Kim*, ASU
    K. Selcuk Candan, 
  • 293
    Robust XPath Expressions for Web Extraction
    Philip Bohannon, Yahoo! Research
    Nilesh Dalvi*, Yahoo! Research
    Fei Sha, University of Southern California
  • 301
    Incremental Maintenance of Length Normalized Indexes for Approximate String Matching
    Marios Hadjieleftheriou*, AT&T Labs - Research
    Nick Koudas, University of Toronto
    Divesh Srivastava, AT&T Labs-Research
  • 308
    Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers
    Tingjian Ge*, Brown University
    Stanley Zdonik, Brown University
    Samuel Madden, Massachusetts Institute of Technology
  • 316
    Top-K Generation of Integrated Schemas Based on Directed and Weighted Correspondences
    Ahmed Radwan, University of Miami
    Lucian Popa*, IBM Almaden
    Ioana Stanoi, IBM Almaden
    Akmal Younis, University of Miami
  • 319
    E = MC3: Managing Uncertain Enterprise Data
    Peter Haas, IBM
    Fei Xu, University of Florida
    Vuk Ercegovac*, IBM
    Eugene Shekita, IBM
  • 335
    Estimating the Confidence of Conditional Functional Dependencies
    Graham Cormode, AT&T Labs - Research
    Lukasz Golab*, AT&T Research
    Flip Korn, AT&T Labs - Research
    Andrew McGregor, Microsoft Research
    Divesh Srivastava, AT&T Labs-Research
    Xi Zhang, SUNY Buffalo
  • 343
    Monitoring Path Nearest Neighbor in Road Networks
    Zaiben Chen, The University of Queensland
    Heng Tao Shen*, The University of Queensland
    Xiaofang Zhou, University of Queensland
    Jeffrey Xu Yu, The Chinese Univ. of Hong Kong
  • 347
    Uncertainty Management in Rule-based Information Extraction Systems
    Eirinaios Michelakis*, UC Berkeley
    Peter Haas, IBM
    Rajasekar Krishnamurthy, IBM
    Shivakumar Vaithyanathan, IBM
  • 359
    Approximate Entity Extraction with Edit Constraints
    Wei Wang, University of New South Wales
    Chuan Xiao*, UNSW
    Xuemin Lin, 
    Chengqi Zhang, UTS, Australia
  • 361
    Secure k-NN Computation on Encrypted Databases
    Wai Kit Wong*, The University of Hong Kong
    David Cheung, University of Hong Kong
    Ben Kao, The University of Hong Kong
    Nikos Mamoulis, University of Hong Kong
  • 364
    Query Processing Techniques for Solid State Drives
    Dimitris Tsirogiannis*, University of Toronto
    Stavros Harizopoulos, HP Labs
    Mehul Shah, HP Labs
    Janet Wiener, Hewlett-Packard Laboratories
    Goetz Graefe, HP Labs
  • 385
    Query by Output
    Quoc Trung Tran*, NUS
    Chee-Yong Chan, 
    Srinivasan Parthasarathy, Ohio State University
  • 387
    Exploiting Context Analysis for Combining Multiple Entity Resolution Systems
    Zhaoqi Chen*, UCI
  • 395
    Towards a simpler XML Schema: effortless handling of nondeterministic regular expressions
    Geert Jan Bex, Hasselt University
    Wouter Gelade*, Hasselt University
    Wim Martens, University of Dortmund
    Frank Neven, Hasselt University
  • 399
    Cost Based optimization and plan selection for XPath
    Haris Georgiadis*, AUEB
    Minas Charalambidis, AUEB
    Vasilis Vassalos, AUEB
  • 400
    Core Schema Mappings
    Giansalvatore Mecca*, Università della Basilicata
    Paolo Papotti, Università di Roma Tre
    Salvatore Raunich, Unversità della Basilicata
  • 403
    A Gauss Funtion based Approach for Unbalanced Ontology Matching
    Qian Zhong, Tsinghua University
    Hanyu Li*, IBM CRL
    Juanzi Li, 
    Guo tong Xie, ibm
    Jie Tang, 
    Lizhu Zhou, Tsinghua University
  • 407
    Efficient Type-Ahead Search on Relational Data: a TASTIER Approach
    Guoliang Li*, Tsinghua University
    Shengyue Ji, UC Irvine
    Chen Li, Univeristy of California, Irvine
    Jianhua Feng, Tsinghua University
  • 493
    A Revised R*-tree in Comparison with Related Index Structures
    Norbert Beckmann, University of Marburg
    Bernhard Seeger*, University of Marburg
  • 495
    Indexing Correlated Probabilistic databases
    Bhargav Kanagal*, University of Maryland
    Amol Deshpande, University of Maryland, college Park
  • 505
    Efficient Incorporation of User Feedback into Information Extraction and Integration Programs
    Xiaoyong Chai*, University of Wisconsin-Madison
    Ba-Quy Vuong, Univ. of Wisconsin at Madison
    AnHai Doan, Univ of Wisconsin
    Jeff Naughton, University of Wisconsin
  • 513
    Extending Autocompletion to Tolerate Errors
    Surajit Chaudhuri, Microsoft Research
    Raghav Kaushik*, Microsoft Research
  • 526
    Privacy Preservation of Aggregates in Hidden Databases: Why and How?
    Arjun Dasgupta*, University of Texas Arlington
    Nan Zhang, George Washington University
    Gautam Das, Univ of Texas at Arlington
    Surajit Chaudhuri, Microsoft Research
  • 534
    A Declarative Data Representation Framework
    Arvind Arasu*, Microsoft Research
    Raghav Kaushik, Microsoft Research
  • 553
    Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities
    Jiewen Huang, Oxford University
    Dan Olteanu*, Oxford University
  • 562
    3-HOP: A High-Compression Indexing Scheme for Reachability Query
    Ruoming Jin*, Kent State University
    Yang Xiang, Kent State University
    Ning Ruan, Kent State University
    Dave Fuhry, Kent State University
  • 565
    A Framework for Testing Query Transformation Rules
    Hicham Elmongui, Purdue University
    Vivek Narasayya*, Microsoft Research
    Ravi Ramamurthy, Microsoft Research
  • 568
    Robust and Efficient Algorithms for Rank Join Evaluation
    Jonathan Finger, University of California Santa Cruz
    Alkis Polyzotis*, UC Santa Cruz
  • 569
    Cross-tier, Label-based Security Enforcement for Web Applications
    Brian Corcoran*, University of Maryland
    Michael Hicks, University of Maryland
    Nikhil Swamy, Microsoft Research
  • 583
    Optimizing I/O-Intensive Transactions in Highly Interactive Applications
    Mohamed Sharaf*, Univ. of Toronto
    Cristiana Amza, UofT
    Panos Chrysanthis, University of Pittsburgh
    Alexandros Labrinidis, University of Pittsburgh
  • 585
    Detecting and Resolving Unsound Workflow Views for Provenance Preservation
    Peng Sun, Arizona State University
    Ziyang Liu*, Arizona State University
    Susan Davidson, University of Pennsylvania
    Yi Chen, Arizona State University

2009年3月3日火曜日

PODS 2009: Accepted Papers

今日発表されました。

今年のPODS2009は面白そうです。XML関連の研究もまだまだ盛ん。研究の世界ではやりの、Uncertain dataは多くなってきていますが、それだけでなく、heavy-hitterとか、secondary indexingとか、DBのcore技術寄りの論文もあるみたいで、論文が出てくるのが楽しみです。

採録された中には、日本人(面識はないのですが天野さんという方)も一人。Libkinのラボにいるのですね。おめでとうございます。こうやって日本からデータベースコミュニティの中で活躍していけるようになる人が増えるとうれしいですね。


29 Dynamic Indexability: The Query-Update Tradeoff for One-Dimensional Range Queries
(Ke Yi)

31 Satisfiability of the downward fragment of XPath with data equality tests
(Diego Figueira)

37 Satisfiability and relevance for queries over active documents
(Serge Abiteboul, Pierre Bourhis and Bogdan Marinoiu)

38 Equivalence of SQL Queries In Presence of Embedded Dependencies
(Rada Chirkova and Michael Genesereth)

58 Distributed XML Design
(Serge Abiteboul, Georg Gottlob and Marco Manna)

59 Relationship Privacy: Output Perturbation for Queries with Joins
(Vibhor Rastogi, Michael Hay, Gerome Miklau and Dan Suciu)

63 Size and Treewidth Bounds for Conjunctive Queries
(Georg Gottlob, Stephanie Lee and Gregory Valiant)

65 A General Datalog-Based Framework for Tractable Query Answering over Ontologies
(Andrea Cali, Georg Gottlob and Thomas Lukasiewicz)

67 Optimal Tracking of Distributed Heavy Hitters and Quantiles
(Ke Yi and Qin Zhang)

69 Indexing Uncertain Data
(Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao and Ke Yi)

71 Equivalence of Nested Queries with Mixed Semantics
(David DeHaan)

76 Running Tree Automata on Probabilistic XML
(Sara Cohen, Benny Kimelfeld and Yehoshua Sagiv)

78 XML with Incomplete Information: Models, Properties, and Query Answering
(Pablo Barcelo, Leonid Libkin, Antonella Poggi and Cristina Sirangelo)

79 XML Schema Mappings
(Shunichi Amano, Leonid Libkin and Filip Murlak)

82 XPath Evaluation in Linear Time with Polynomial Combined Complexity
(Pawel Parys)

89 Relative Information Completeness
(Wenfei Fan and Floris Geerts)

94 An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets
(Adam Kirsch, Michael Mitzenmacher, Andrea Pietracaprina, Geppino Pucci, Eli Upfal and Fabio Vandin)

98 Generalized Schema-Mappings, From Termination To Tractability
(Bruno Marnette)

103 Similarity Caching
(Flavio Chierichetti, Ravi Kumar and Sergei Vassilvitskii)

105 Optimal Sampling from Sliding Windows
(Vladimir Braverman, Rafail Ostrovsky and Carlo Zaniolo)

111 Exceeding Expectations and Clustering Uncertain Data
(Sudipto Guha and Kamesh Munagala)

116 Consensus Answers for Queries over Probabilistic Databases
(Jian Li and Amol Deshpande)

118 Computing All Skyline Probabilities for Uncertain Data
(Mikhail Atallah and Yinian Qi)

119 Reverse data exchange: coping with nulls
(Ronald Fagin, Phokion Kolaitis, Lucian Popa and Wang-Chiew Tan)

134 Space-optimal Heavy Hitters with Strong Error Bounds
(Radu Berinde, Graham Cormode, Piotr Indyk and Martin Strauss)

143 Secondary Indexing in One Dimension: Beyond Btrees and Bitmap Indexes
(Rasmus Pagh and S. Srinivasa Rao)

2009年1月16日金曜日

Top 5 Database Research Topics in 2008

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

  • 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にできるか、という証明部分。こちらも面白い)


もう一つもトランザクション関連。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研究を見直していくことができ、木構造に捕らわれていては難しかったもの(例えば、木構造を保持した索引で、サイズが小さくかつ、更新しやすいものは、未だに作られていません)でも、木構造を捨てることで様々な最適化が期待できるようになりました。


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

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

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

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

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

関連エントリー

2009年1月7日水曜日

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

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

一番のお薦めは、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 TechniquesImage(こちらは詳細な実装に興味がある人にお薦めです)」にあるような従来のロックの管理方式の正当性が、綺麗な形で裏付けされていくのは圧巻です。Jim Gray本人が「自分が書きたかった本」と称賛するのもうなずける内容。特に関連文献の項が充実していて、この一冊があれば、過去から現在までの研究の流れが非常によくわかり、詳しい情報へのアクセスが容易になります。

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


最後は、データベースの歴史を知る上でとても大切な一冊。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の知識を持った上でソースコードを読んでみると、素早く全体の構造から実装の詳細までを把握することができます。


関連情報

2008年12月22日月曜日

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のようなテーブル形式のデータ)の組み合わせと考えることができ、そのテーブル構造の情報(スキーマ)を使うと、検索が非常に簡単に書けるという点です。

この応用例は広く、僕が日常的に構造を持ったデータを扱うプログラムを書くときに欠かせないツールになっています。例えば、
  • 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のように単一のテーブルだけだと心もとない、けれど構造が入り組みすぎても、扱いきれない。そして、このもどかしさと真正面に向き合うのが、データベース研究の世界なのです。

2008年10月21日火曜日

[SQLite JDBC] Javaで始めるSQLiteデータベース入門

SQLiteデータベースは、Cで書かれた軽量データベースです。「軽量」というのは2つの意味があって、全体のコード数が10万行程度という点(PostgreSQLは100万行に近づいています)と、データベースを保存するファイルが1つに納まっているのがSQLiteの特徴です。他のシステムだと、複数のデータベース用のファイルがあって管理が面倒なのですが、SQLiteのデータベースはファイル1つで、しかもOS互換フォーマットで保存されているので、簡単にOSをまたがったデータベースのコピーを作成することができます。

そもそもリレーショナルデータベース(日本語では関係データベースと訳すことが多いです)って何?という方は、初心者向けに用意した以下の講義資料を参考にしてください。
Javaでデータベースアプリケーションを作成するには、JDBC (Java Database Connection)というAPIを使います。ただし、データベースを使うには、まずシステム側にデータベースシステムをインストールする必要があり、ここが慣れた人でもデータベースシステム(英語では、Database Management System: DBMSと言います)の設定でつまづいたり、面倒なことが多いのが難点でした。

このような問題を解決するために、SQLiteの軽量さを生かしたJava用のライブラリ(jarファイル)を作成しました。
このSQLite JDBC Driverでは、Mac OS X, Windows, Linux (i386, amd64)などよく使われるOSでSQLiteをインストールなしで動作させるために、それぞれのOSでコンパイルしたSQLiteのバイナリをjarファイルの中に埋め込んであります。これは、SQLiteが軽量だからなせる技です。プログラムの実行時に、自動的にjarファイルの中から、OSに応じたSQLiteのバイナリを取り出し、Java側でロードして使えるようにしています。

もし、少々特殊なOSや、CPUを使っていても安心です。SQLiteのCのコードを完全にJavaで動作するように置き換えたpure java版のSQLiteもライブラリに含めているので、上記以外のOSでもきちんと動作します(CをJavaコードに書き換えるのに少々無理があるので、動作は遅くなりますが)

JavaでSQLiteデータベースを使うには次の手順で行います:
  1. sqlite-jdbc-(version).jar をここからダウンロードします。2008年10月現在の最新版は3.6.4です。(Maven central repoのミラーからもダウンロードできます。)
  2. 下にあるサンプルプログラム(Sample.java)は、JDBCを通してデータベースの作成、検索をする例です。これをコンパイルします。
  3. Javaを実行するときに、上記のJARファイルを以下のようにクラスパスに含めます。
    java -classpath ".:sqlite-jdbc-(VERSION).jar" Sample
  4. これだけでJavaでDBMSが使えるようになります。お手軽!
Sample.java

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;


public class Sample
{
public static void main(String[] args) throws ClassNotFoundException
{
// load the sqlite-JDBC driver using the current class loader
Class.forName("org.sqlite.JDBC");

Connection connection = null;
try
{
// create a database connection
connection = DriverManager.getConnection("jdbc:sqlite:sample.db");
Statement statement = connection.createStatement();
statement.setQueryTimeout(30); // set timeout to 30 sec.

statement.executeUpdate("drop table if exists person");
statement.executeUpdate("create table person (id integer, name string)");
statement.executeUpdate("insert into person values(1, 'leo')");
statement.executeUpdate("insert into person values(2, 'yui')");
ResultSet rs = statement.executeQuery("select * from person");
while(rs.next())
{
// read the result set
System.out.println("name = " + rs.getString("name"));
System.out.println("id = " + rs.getInt("id"));
}
}
catch(SQLException e)
{
// if the error message is "out of memory",
// it probably means no database file is found
System.err.println(e.getMessage());
}
finally
{
try
{
if(connection != null)
connection.close();
}
catch(SQLException e)
{
// connection close failed.
System.err.println(e);
}
}
}
}

やや高度な内容ですが、MavenをJavaの開発に使っている人は、mavenのcentral repositoryにsyncされているこのSQLite JDBCライブラリを使うことができます。pom.xmlファイルに以下のような記述をするだけで自動的にダウンロードされます。
<dependencies>
<dependency>
<groupid>org.xerial</groupid>
<artifactid>sqlite-jdbc</artifactid>
<version>3.6.4</version>
</dependency>
</dependencies>

SQLiteではファイルにデータベースを保存せずにメモリーの上でデータベースを構築することもできるので、データベースのテスト用にも最適です。

License

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