Leo's Chronicle: database

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

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日金曜日

2009年1月7日水曜日

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

先日のエントリで少し話したのですが、僕が在学していたときの東大にはデータベースを学ぶためのコースというものがありませんでした（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の知識を持った上でソースコードを読んでみると、素早く全体の構造から実装の詳細までを把握することができます。

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

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

2008年12月15日月曜日

[講演案内] Relational-Style XML Query

講演の案内です。

第3回先端的データベースと Web 技術動向講演会
（ACM SIGMOD日本支部第40回支部大会）
「VLDB2008 国際会議報告および XML DBの最新動向」

2008年12月20日(土)に、「Relational-Style XML Query」の話題で、SIGMOD日本支部大会において講演を行います。申込期限は過ぎておりますが、まだ若干席が残っているようです。

Relational-Style XML Query
XMLのような階層構造を持ったデータに対して、フラットなSQLを用いて問い合わせを行う手法であるRelational-Style XML Query (SIGMOD2008で発表) について紹介します。

この内容を日本(語)で紹介するのは初めてですし、横田先生の案内によると、「どうしたらSIGMODに通るような論文を書けるか」についても期待されているご様子なので、その当たりの話も織り交ぜようかと考えています。乞うご期待。

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ファイル）を作成しました。

Xerial: SQLite JDBC Driver

この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データベースを使うには次の手順で行います：

sqlite-jdbc-(version).jar をここからダウンロードします。2008年10月現在の最新版は3.6.4です。（Maven central repoのミラーからもダウンロードできます。）
下にあるサンプルプログラム(Sample.java)は、JDBCを通してデータベースの作成、検索をする例です。これをコンパイルします。
Javaを実行するときに、上記のJARファイルを以下のようにクラスパスに含めます。
```
java -classpath ".:sqlite-jdbc-(VERSION).jar" Sample
```
これだけで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ではファイルにデータベースを保存せずにメモリーの上でデータベースを構築することもできるので、データベースのテスト用にも最適です。

2008年9月10日水曜日

Google Street Viewが持ちえない情報

Google Street View(ストリートビュー）が、写してはいけないものまで公開していることが多くのサイトで話題になっています。今日、「不適切画像の削除作業は小鳥並の知能で行われる」：高木浩光＠自宅の日記のエントリをみて、根本的な問題がようやく整理できました。

Google Street Viewが検索エンジンのロボットやウェブ上のブログなどと根本的に違うのは、「人のフィルターを通さない情報をネットに晒している」ことに尽きます。

もちろんGoogle Street Viewのデータを収集するには、路上の写真を撮影する実際の作業員がいて、撮るべき場所の最低限の判断はしているのでしょう。（私道に入り込んでいたり、とそれすらも怪しいですが）。写ってしまった人の顔をぼかすなどの処理もしているようです。けれど、ネットに公開すべき情報とそうでない情報の判断を、98%の精度でスパムメールを弾くのと同じ方法で行ってはいけない事例が多々存在します。

例えば、写ってはいけない人が、その場所に写っていた場合。この写真をウェブに公開してもよいかという判断は、写っている場所以外の外部情報を使わないと通常はできません。なぜなら、顔が伏せられていたとしても、背格好、服装や行動範囲などでその人を特定できる情報を持っている人にとっては、ただの写真以上の情報がそこにあります。たとえ洗濯物が映ってしまったという程度のことでも、女性の一人暮らしであることがわかってしまうなど、写された住居に住む人の危険を招くことさえありえます。

「問題のある画像だから、画像を消す」という現在のGoogleの対応では、「消したという事実」によって、消された場所に何があったのか、という好奇心を刺激し、削除依頼主の意にそぐわない事態を招くことが十分考えられます。

インターネットの普及に伴い、ネットの存在意義もプライバシーの問題も議論されてきました。ネットの検索エンジンがけしからん、といういう人が減ってきたのは、利便性の認知とともに「Webに個人情報などを公開しない」という選択肢と、そのための情報の管理方法が存在しうるからです。つまり「人によるフィルター」を介在させる余地がWebに情報を送る前に残されているのです。けれど、ストリートビューにはそれがない。

目に見える情報がすべてではないのです。株のインサイダー取引のように、内部情報を知りうるものだけに利益を与え、他の人の利益を不正に大きく損ねてしまう。

ストリートビューは、今までなかなか見られなかった情報を収集し、目的地や町の雰囲気を容易に知ることができるようなったという点で、その存在意義や利便性は高く評価しています。ただ、それを人や機械の目による判定や、報告だけで安全にできるというGoogleの現在の主張には、非常におこがましいものを感じます。当事者にしかわからない情報というのは常に存在するものです。

今までのウェブ情報の収集とは違って、ストリートビューでは「人によるフィルター」の情報が根本的に抜け落ちています。「ウェブに存在しない・載せていない」という事実だって立派な情報です。フィルターを通したあとの情報を扱ってきたから、Googleには何をしても怖くないという強みがありました。ストリートビューのように、フィルターを通す前のレイヤー（層）の情報を扱いだしてから、急に対応の陳腐さが目立つようになってきたのがとても残念です。

2008年8月20日水曜日

[本郷でお散歩] PFIに行きました

今週休みをとっていたので、この機会に、はてなの関連エントリー機能を実装するなど、いまを時めくPreferred Infrastructure(PFI) さんに遊びに行ってきました。忙しいところ快く応じてくれた社長の西川君、太田君に感謝。

以前、二人が会社を立ち上げたばかりのころに、データベースの話で盛り上がったことがあります。東大全体を見回しても、データベースシステムとその実装にまで興味がある人って意外と少なくて、Jim GrayのTransaction Processingを読んでいるなど、データベース屋さんの僕にとっては、貴重な話相手です。

ACM主催のプログラミングコンテストICPCの東大内予選（と僕が勝手に呼んでいます。本当は国内予選。ただ、各大学から３チームまでしか先に進めない）を勝ち抜けて、世界大会にまで出場するだけでもすごい人達なのですが。

今日は分散トランザクションについて話をしてきました。トランザクション処理は、スループットを上げるための実装はそうとう複雑なのですが、さらにマシンが複数台になると考慮すべき障害が増えてとたんに難しくなります。運用を考えたときのコストとか、商用DBといえど落ちることがある、などの話を聞けてためになりました。僕は研究者の立場なので常に新しいものを開発すればいいのですが、24時間常時動かすというのはやはり相当大変なことなのだと再認識。もしかすると、僕はこういった運用の大変さから逃れるために、研究の道に入ったのかも。

今回は短時間の訪問だったので紹介しきれませんでしたが、本当は最先端の話題でもっといっぱい話したいことがありました。主にMITのStonebraker教授(PostgreSQLを作った先生）のお弟子さんたちの話なのですが、C-Store (列ごとにテーブルを分割して圧縮。性能抜群）, H-Store (トランザクションの意味を考えて、仕事の単位を分割、sequentialに処理して速度を稼ぐもの)など。One-size doesn't fit all (DBMSも用途に応じたものが必要）という時代の流れがあるんですね。現在主流のrow-oriented storage（テーブル行単位でディスクに配置していくもの）で、ロックマネージャーを外し、ログを外し、、、とやっても、トランザクションで100倍の性能を上げるのは難しいんです (OLTP Through the Looking Glass, And What We Found There. SIGMOD2008を参照)。

まだ教科書には載ってないけれど、トランザクションを高速に実現するための現在の主流であるsnapshot isolationを、性能をほとんど落とさずserializableにする話 (Serializable Isolation for Snapshot Databases。著者に実際に会ったときにソースコードくださいと話したらBerkeleyDB上での実装を公開してくれました)など。

XMLのような階層構造のデータもrelational databaseと同じ枠組みで扱える、という僕の研究の話もいつか紹介したいですね。こんな要素をもろもろ含んだ日本発の最先端DBMSを、彼らのように物を作ることに貪欲で、「わくわく」する感覚を持ち続けている人たちと一緒に作れたらいいなぁと夢見ていたりします。

PFIのオフィスは、自宅から徒歩圏内なので、本当はもっと遊びに行きたいのですが、職場まで遠距離通勤＋子育て中なので、もうちょっと落ち着いてからかな。

後編：[本郷でお散歩] UT Cafe にも行きました。

2008年7月1日火曜日

Rails、Hibernate、EJB スキーママッピングあれこれ

久し振りの更新。普段、突発的にものを書きたくなる衝動をブログにぶつけていたのですが、最近はそれがTwitterに吸収されてしまっています。短い単発コメントより、まとまった文章がある方が本当は価値が高いんですけどね。今日はTwitterが重いので、ブログに戻ってきました。

閑話休題。

SIGMOD2008に参加してみて不思議だったのは、Schema Mappingの研究が想像以上に盛んだったこと。これは、データベースのスキーマ（テーブル構造情報）を、他のスキーマへと変換するときに使います。データベースの移行とか、アプリケーションに合わせて形を書き換えるとか。

でも、そもそもマッピングって、足し算が入るだけでも、不可逆変換なんですよね。1+2を合わせて、「3」というデータを作ったとき、この「3」というデータは、1+2の結果か、2+1の結果かわからなくなる。そうすると、マッピングに使える演算の種類は限られてきます。

SIGMOD2007のベストペーパー、Compiling Mappings to Bridge Applications and Databasesにあるように、テーブルデータ　-> オブジェクトというマッピングをし、オブジェクトの更新結果をテーブルデータに正しく反映させるといった、roundtrip制約を入れると、使えるマッピングの種類を限定せざるを得ません。Join演算なんてもってのほかです。

問題を、オブジェクト（Javaのクラスなど）とテーブルデータ(relational database)の構造の違い(impedance mismatch)の吸収に絞ると、すでに世間で実用化されている技術がいくつかあります。Ruby on Rails, EJB3.0 (Enterprise Java Beans), Hibernateなどがその代表でしょう。

それぞれの一長一短(pros and cons)

Rails: テーブルの列名に対応したメソッドを自動追加するので(Person.id, Person.name, ...などでアクセス)、簡単なスキーマ変更（カラムを増やす、など）なら、ソースコードの変更が不要。ただし、実行時に初めてわかるメソッドなので、コンパイラによる静的チェックの恩恵が受けられない。実際に、動かしてみるまでプログラムが正しく動くかどうかわかりません。

EJB3.0: Javaのクラス定義と、テーブルデータをAnnotationなどを駆使して対応させます。テーブル名、カラム名とクラス名、メソッド名が食い違う場合はAnnotationを使って細かい対応付けができるのが売り。Data Access Objectを通して、オブジェクトを更新、テーブルに反映させるという手順。ただし、１つのオブジェクト定義でも、文脈に応じて、別々のテーブルに格納したいことがあります。たとえば、Personクラスを、student, teacherテーブルへ。student（Personクラスに対応）の一部を、alumniテーブルに格納したい、などなど。クラス定義の中に対応するテーブル名やカラム名を含める設計だと、この目的には対応できません。ここはぜひ分離してほしいところ。（Railsも、クラスに対応するテーブル名は決め打ちです。プログラミングはとても簡単な反面、オブジェクトの使いまわしは難しい。一応、オブジェクトに対応するテーブル名は設定可能ですが）

Hibernate：僕はこのtutorialを読むだけでがっかりしました。こちらにも解説書のサンプルがあります。Javaのクラスと、テーブルデータベースの違いを吸収するのに、XMLで書かれたマッピングファイルが必要なんです。EJB3.0も裏でHibernateを使っているようです。なんだ、なんだ？。これだと、クラスを書き換えたら、XMLも書き換える必要がある。そのXMLファイルをクラスファイルから自動生成できるのかもしれないけれど、Javaのリフレクションを使えばXMLをあらかじめ用意する必要なんてないはず。設定ファイルが多い（ある）という点で、Railsほどの簡潔さ、わくわく感はありません。

明示的であれ暗黙的であれ設定項目を把握するまで動作が理解できないスキーママッピングなら、技術としての重要性は低いように思う。Railsのようにマッピングを決め打ちできる状況は多いと感じるし、テーブル型データとオブジェクト間のimpedance mismatchがそれほどあるとも思えません。現に、Object-Relational Databaseというように、Reational databaseは、様々な形のオブジェクトを保存できるように成長しています。

データベースのデータを扱うのが、プログラム言語中であるなら、プログラム中で使うクラス定義（オブジェクト）がスキーマそのものです。オブジェクトをそのまま保存できれば事足ります。テーブル名、カラム名なんてプログラム中で気にする必要はないはず。それに加えて、オブジェクトをどのような位置（コンテキスト）に保存するかが選択できればよい。たとえば、2007年度のデータ、2008年度のデータなど、フォルダでファイルを管理するのと同じように、データを保存する位置を決める。この2点ができれば、データベースの機能としては十分なんじゃないかと思います。

コンテキストを表す能力が高いのはXMLだし、定型データを扱うのはRelational Databaseの得意技。データベースの研究者として、両者の融合をもう少し進めていきたいところです。

2008年5月3日土曜日

研究者インタビューを受けました

SIGMODに論文が採択されたこともあって、インタビューを受ける機会がありました。(電子情報通信学会データ工学研究会のニュースレター)。

インタビューと編集はNTTサイバー研の鬼塚さんがしてくれたのですが、本当にお疲れ様です。普段SIGMOD Recordなどで研究者インタビューを読む分には気楽なのですが、いざ自分が受けてみたり、編集の様子などを見ると、裏では、相当な努力があることがわかりました。

鬼塚さんの努力の甲斐あって、今回が初回のニュースレターは、かなり読み応えのあるものになっています。喜連川先生のアドバイスには、研究者として大事なことがたくさん含まれています。top confereceを目指すことは重要、でも、研究者としてできることは、それだけではない。

小杉さんのＰＣ(Programming Commitee)体験談でも、immediate rejectは本当にあっさりしているんだな、と。また、今回のSIGMODのPC ChairであるDennis Shashaが提示したという査読、採否の方針はとても参考になります：

1. 査読にあたってはそのペーパの良い部分を見つけるように心がけること。rejectする際は、技術的な誤りなどの正当な理由や、killer referencesを示すと共に、some words of encouragement を忘れないこと。
2. innovative ideaを重視し、短期間で修正可能なミスを主原因としてrejectしないこと
3. 既存のアルゴリズムのバリエーションで、ちょっと思いついた、程度のものは、大規模な性能改善がない限りあまり重視しないこと
4. 実験に関しては、
　i) 統計的に意味のある母数で実験がおこなわれていること
　ii) 可能な範囲で標準的なデータセットとクエリを用いていること
　iii) 更新とクエリシナリオがテストされていることが満足されていることを重視すること

それにしても投稿数が去年の3割増しとは。。。PCも大変だ。論文を投稿するときは、読みやすい論文にすることを心がけて、PCの負担を減らしてあげるようにしないといけないですね。また、自分が査読する側に回った際も、良い部分を見つけるようにして、研究コミュニティの良いサイクルを回していくことがとても大切。

2008年3月17日月曜日

大学の若手研究者ができる４つのこと・実践編

情報関連の研究では、日本は欧米を中心としたコミュニティから取り残されています。このことは、ここ数年のTop Conference/Journalでの日本のpresence（存在感）をみるだけでもよくわかります。この状態を危惧して、tatemuraさんが「大学の若手研究者ができること」と題して以下の4つを提言しています。

（１）英語のレジュメを書いてみる（書かせてみる）
（２）日本語論文を書かない（書かせない）
（３）無駄な学会を退会する
（４）官僚との付き合いを減らす

「日本語論文を書かない」という点については、僕自身、既に6年実践しています。そもそも、東京大学の情報科学科というところ（大学院ではComputer Scienceという名称）は、学部の卒業論文から英語で書かせる伝統があって、英語で論文を書くということは、研究をする上でのボトムラインという感覚が染み付いています。この意味では、「英語で書かせる」というのは、教育的にはいい方法だと思います。

東大生と言えど、皆が英語が流暢なわけでも、英文を書き慣れているわけでもないので、最初に出来上がってくる文章はひどいものですが、経験を積んでいくと、だんだんいい文章が書けるようになってくるようです。ここで苦労している時点で既に、英語圏で普通に研究をしている人たちに差をつけられているので、日本語で書く暇があったら、日頃から英語で書く練習をしないと、ますます差がついてしまいます。

tatemuraさんも言っていますが、日本人の頭脳や技術力が必ずしも劣っているとは、僕も思えません。（とある先生に同じ話をしたところ、向こうの研究者はもっと賢いんだよ、と言われましたが（汗））。それはともかく、新しい技術や、自ら開拓した研究分野を、「英語」で「わかりやすく」伝える技術を併せ持った人が、日本にどれだけいるのでしょうか？という話です。SIGMOD, VLDBのようなデータベースのtop conferenceに通すためには、英語のnativeと言えども、数ヶ月を書けて論文を、個々のフレーズに至るまで吟味するそうです。ミーティングで文章を議論して、２時間でようやく1パラグラフ進んだという話も聞きます。僕としても、「日本語で書かない」を実践した、というよりはもっと単純な理由で、「日本語でまで論文を書く余裕がない」というのが本音です。

研究者として、一番面白くないことは、自分の仕事（論文）に対して何も反応がないことだと思っています。ブログを書く動機だったり、絵や音楽などの作品を作る情熱だって、何らかの反応を求めてるから生まれてくるものだと思います。ビジネスだったら、売れる、ということ。だから、たとえ論文が採録されたとしても、Reviewerの反応が素っ気なかったり、後続研究が出なかったら（つまり売れなかったら）がっかりするものです。（ブログに関しては、直接のコメント等がなくても、のちのち、いろいろなキーワードで検索されていることを知ると楽しいものですが）

日本語でわかりやすく研究を伝えるのも大事な仕事ですが、それはどう頑張っても日本の閉じたコミュニティでしか売れないことを覚悟しないといけません。読む側の立場から見ても、SIGMOD, VLDBの文献を追うだけでもかなりの労力を要するので、英語論文に決して引用できない日本語文献は、必然的に読まなくなっていきます。国際的に影響力のある人が、日本語で発表できているなら、世界の風が日本にも流れてきて良いのだと思いますが、現在のようにそのルートが閉ざされてくると、コミュニティは国内に閉じる一方なんだと思います。

ただ、研究者を目指す人にとって、日本における博士課程までの学生生活というのは必ずしも、経済的に恵まれたものではありません。比較的、財政的に豊かな東京大学ですら、博士課程の学生の授業料を全員免除するには至っていませんし、アルバイトをしながら、PhDや、職を得るために、通しやすい日本語で論文を書いている、という事情もあると思います。学生という理由だけで、保育園へ子供を入れる優先順位が他の人より下げられてしまうなど、社会全体として、世界最先端の研究者を育てる風潮がないのも確かだと思います。高校生までの教育問題は報道等で好き勝手に論じても、大学以降の、特に情報系の現在のようなpresenceの低い状態や、学生の待遇については、世間で議論されている様子はちっとも伺えません。

「無駄な学会を退会する」は、まだ学会のPCを依頼されるような、一人前の研究者にはなっていないので、そういう身分になってから考えます。ただ、Fellowならまだしも、ただの学会の会員というのには、どんな価値があるのかよくわからない、というのがあるので、メーリングリストを読む以上の会員にはなっていません。

「官僚との付き合いを減らす」というのも、まだ、どうコメントしていいかよくわからないところです。日本の劣勢を覆す土台となる学生の研究生活の改善のためには、社会的地位の低い学生として博士を取得する苦労を知っている人が、官僚となって働いている方が都合が良いと思うことが多々あるからです。むしろ、現状を鑑みる限り、もっと学者が参政しないといけないと感じています。

最後に、「英語のレジュメを書いてみる」という点。これが実践できていないことが、ここのところ心残りだったので、今日、自分のCurriculum Vitae (CV：履歴書)を書いてみました。海外の若手研究者と比べると寂しい限りですが（tatemuraさんの記事は、この寂しさを認識させたいという意図でしょう）、このCVを充実させ、常に世界に向けて情報を発信していくことを念頭に努力していきたいと思います。

2008年3月14日金曜日

SIGMOD 2008 Repeatability Assessment

今年のSIGMOD 2008から始まったRepeatability Assessment。論文中にある実験結果が第三者によって再現できるかどうかを確認する趣旨のものです。

実行可能なバイナリやソースコードを送り、実験結果を相手方のマシンで検証してもらいます。並列分散計算とか、マシン環境がないと再現しにくいものもあると思いますが、scalabilityとか、result sizeなどなら、傾向として一致することは確認してもらえます。

論文誌と同時に公開されるであろうコードを使って、比較実験がしやすくなるだろう、という期待はあります。他人のアルゴリズムを実装するのは常に大変なので。ただ、コードが入手しやすくなると言っても、フェアな比較になるように気をつけて（実装言語、applicationの違いとか）、かつ性能差の定性的な原因を明らかにしないと、研究としては面白くならないと思います。

ちなみに今回の評価は簡単なものでした。以下、抜粋。
-----
Overall repeatability : Strong Accept

Summary: Figures 16,17 and 19 were successfully repeated.

Details: Output (truncated because of the conference tool editing limits):
synth.tab
query fanout scale mode trial time
q5 2 1 0 1 0.125
q5 2 1 0 2 0.125
...

Were you able to install the software? : Yes
Were you able to run experiments? : Yes, all of them
Were you able to repeat experimental results? : Yes, all
Was the submission well-formed (valid and meaningful XML file etc.)? : Yes
----

実は、このfeedbackを得る前に、「プログラムが動かないよ」、という返事が来て、原因を調査したら、送ったコードに、Visual Studio C++ 2005 (SP1)の配布用DLLが含まれていなかったようです。慌てて返信したところ、無事プログラムが動いたようです。Visual Studioが入っていてもだめみたいで、SP1のDLLが必要だったところが盲点。今度から、仮想マシンで実験しておかないとだめですね。Javaだとこの類いの問題が少ないので楽なのですが。

実験を再現するためのMakefileやら、スクリプトを書くのは割と面倒だったのですが、意外なことにその努力の結果は自分に返ってきました。追加実験をするときに同じスクリプトが使えました。自分のプログラムの使い方の備忘録にもなっているし、後々になってわかる良いところが多数。

今度から、実験結果はSQLiteのDBにでも入れて、平均や標準偏差を取ったり、グラフを書く作業もgnuplotを使って、自動化できるようにしておきたいなと思いました。（今回は楽をしてExcelで書きましたが、自動化してなかったので書き直すのはやはり手間だった）

2008年2月18日月曜日

SIGMOD 2008に通りました！

今朝から興奮しっぱなしです。

2月16日が結果発表だったはずなのですが、アメリカ時間で17日になっても返事がこないまま、今日、朝一で見たメールがこれ。

Congratulations! Your paper:

Paper#: 7 Title: Relational-Style XML Query

has been accepted for SIGMOD 2008.
Altogether there were 435 papers submitted and only
78 accepted.

Author Feedback時のReviewerのコメントが良い感じだったので、このまま行くかな、と思っていたのですが本当に通ってくれて一安心です。

435 papersという数字。最近のSIGMOD, VLDBなどのデータベースのtop conferenceは通常600本近くの投稿があるのですが、今回のSIGMODからソースコード（or バイナリ）の添付が求められたので、これで、数が減ったのかもしれません。僕は実装好きなので、運も味方したのかな？Registration時の登録番号も７だったし縁起が良かったです。

SIGMODは学部時代、研究室に入ったときからの目標だったので、実に6年越しの夢がかないました。日本人グループで、SIGMODに通るのっていつ以来なんだろう？櫻井さんという方が海外のチームと共同で2005年に採択されているみたいですが、本当に日本人のみのグループを探してみたところ、1998年の喜連川先生のチーム以来みたいです（間違っていたらごめんなさい）。

これで、日本でも頑張れるんだ！って日本のDB業界が発奮してくれるといいなと思います。僕自身も、DBもXMLもまだまだ使いやすくなっていないので、研究者としての仕事はたくさん残っています。ようやくスタート地点に立てたような気分でもあります。

僕を支えてくれた妻と子供、そして家族に感謝。
論文のパラグラフごとに、細かい表現の修正につきあっていただいた先生に感謝。
博士論文の審査で貴重な意見をくださった先生方に感謝。
この研究につながる強い動機をくれた研究室の同僚に感謝。

今日、研究を続けるモチベーションという、とてもいい栄養をもらうことができました。
ゴールはここではありません。今後も、DBの発展のために貢献していきたいと思います。

2007年2月4日日曜日

Jim Grayが行方不明

Silicon Valley’s High-Tech Hunt for Colleague - New York Times

大変。1月30日にJim Gray博士が行方不明になったそうです。GoogleやAmazonも協力しての捜索が続けられているとか。無事発見されることを祈ります。

僕は、データベースやトランザクション管理についてはJim Grayの本や論文から多くを学びました。いまでは、皆、Web経由でデータベースを当たり前のように使っていますが、mixiのようなデータを管理するサービスも、彼の貢献がなかったらまだ実現できていなかったかもしれません。

Jim Grayとは何度かデータベースについてメールのやりとりさせていただいたことがあります。まだ研究者として駆け出しの僕にも丁寧に答えてくれるような人だったので、本当に衝撃を受けています。

2007年1月25日木曜日

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

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

登録: 投稿 (Atom)

Leo's Chronicle