このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

デイヴィッド・スピヴァックはデータベース界の革命児か -- 関手的データモデル

最近、「おおおー、これは凄い、すんばらしい!」と思ったことがあるので、それについて書きます。

最初に言葉についてのお断り; "categorical"の訳語をどうしようか? と。片仮名で「カテゴリカル」が無難ですが、漢字で書きたい。「圏論的」が落ち着きがいいようですが、必ずしも「論」の意味を含まないときもあります。そこで、以下、「圏的」を使います。

[追記 date="2013-02-12"]入門的解説を書きました。→「衝撃的なデータベース理論・関手的データモデル 入門[/追記]

スピヴァックと関手的データモデル

デイヴィッド・スピヴァック(David I. Spivak, http://math.mit.edu/~dspivak/)は、MITの研究者です。

彼は圏的情報学(categorical informatics)を提唱しています*1。圏的情報学の中心的な概念が関手的データモデル(functorial data model)です。

スピヴァックは、2007年にカリフォルニア大学バークレー校(UC Berkeley)で学位を得てますが、学位論文のタイトルは"Derived Smooth Manifolds"で、幾何学をやっていたようです。タイトルから想像するに、ルーリーなどが開発した代数幾何の道具を使ってなめらかな多様体をゴニョゴニョする話かしらね。2005, 6年あたりには高エネルギー物理学の論文も書いています。

2009年あたりから圏的情報学の論文を発表し出したようです。僕が読んで(ザッと眺めて)みたのは次の2つです。

スピヴァックが提案している枠組みは、非常な一般性を持ちますが、とりあえずは関係データモデルの圏論的な定式化となっています。今までも、データベース理論に圏論を使うという話はありましたが、なんだかしちめんどくさい感じで興味を引かれませんでした。スピヴァックの方法はと言うと、驚くほどに単純で直接的な定式化です。

データベースの概念と圏論の概念をマッピングするためにナニヤラ準備をして、なーんてことは一切しません。なんの準備もなしにいきなり定義、むしろ解釈をするのです。データベースの概念と圏論的な概念の極めて直接的な対応関係を提示します。その一部を対応表にすると:

データベースの概念 圏論の概念
データベースのスキーマ
データベースのテーブル 圏の対象
テーブルのカラム 圏の射
データベースの状態/インスタンス 関手
データ操作 自然変換

スピヴァックは、このような対応に補足事項や制約が不要な証拠を示しています。例えば、妥当と思える方法でデータベーススキーマの圏Schを定義して、圏Schが“小さい圏”の圏Catと圏同値なことを証明しています。彼は次のような文やフレーズをしばしば使っています。

  • Databases are Categories
  • The connection between databases and categories is simple and strong.
  • Schemas are categories, categories are schemas.
  • Categories and database schemas are the same thing.
  • Schema=Category, Data=Functor
  • Database schemas as categories, Database instances as functors

しばしスピヴァックの言うことに耳を傾ければ、「あーナルホドね」なのですが、この単純(過ぎる)解釈を見いだすのは容易なことではないでしょう。その意味で、スピヴァックの解釈は大発見です。

しかし、まったく前例がないかと言うとそうではなくて、データベース・インスタンススキーマ上の関手と考えることは、ローヴェル(Lawvere)の圏論的な代数理論(algebraic theory)とまったく同じ発想です。例えば、ローヴェル流の解釈では、圏C内のモノイドは、単体圏Δからの関手 M:Δ→C とみなせます。同様に、スピヴァック流の解釈では、圏C内のデータベース・インスタンスは、スキーマである圏Sからの関手 D:SC です*2

データベーススキーマは、代数の指標と同じものですが、単一の指標ではなくて、“すべての指標”を同時に考えます。すべての指標(=データベーススキーマ)からなる圏がSchであり、これは圏の圏Catまたはその部分圏と圏同値になります。圏Schは、インスティチューションにおける指標圏と同じものです。インスティチューションのモデル圏にあたるものが、インスタンスの圏 S-InstC := [S, C](関手圏)です。

このように、データベースの諸概念を直接(straightforward)に圏論でモデル化する手法が関手的データモデルです。枠組みはローヴェルやゴグエン(Goguen)のものと同じと言えますが、代数理論やインスティチューションが、データベース/データモデルの議論にこれほど直接的に適用可能であると想像した人は少ないでしょう。(ローヴェルもゴグエンも想像できなかったのでは?)

圏的情報学/関手的データモデルは何がうれしいのか

スピヴァックは次のように書いています*3

the first goal of this paper is to present a straightforward model of databases under which every theorem about small categories becomes a theorem about databases.


この論文の最初の目的は、小さい圏に関するすべての定理がそのままデータベースに関する定理となるような、直接的なデータモデルを提供することです。

圏論と直接対応する関手的データモデルでは、今まで蓄積された圏論の知識や手法がそのまま全部適用できることになります。それらの知識/手法には、随伴、モナド、クライスリ拡張、インデックス付き圏/ファイブレーション、グロタンディーク構成、前層/層、トポス、インスティチューションなどが含まれます。実際スピヴァックは、これらの道具を縦横無尽に使って実際的な結果を出しつつあります。

そして:

Moreover, one may hope to leverage existing mathematical theory to their own database issues through this connection.


さらには、あなた自身のデータベースに関する問題を、この対応関係を通じて、既存の数学理論の力を借りて解きたいと望むかもしれませんね。(そしてそれは可能でしょう。)

スピヴァックが提示した道具と指針のなかで特に印象的なのは、スキーマ変換(schema translation)に伴うデータマイグレーションです。

データベーススキーマは圏なので、2つのスキーマSTのあいだの変換は関手 F:ST となります。このスキーマ変換に対して、T上のデータをS上に、あるいはS上のデータをT上に合理的に移動するにはどうしたらいいでしょうか? この問題は今までも多く取り上げられてきたし、実用上も大変に重要です。しかし、決定的な結果はなかったように思います。

関手Fによる引き戻しを使うと [T, Set]→[S, Set] は簡単(ほぼ自明)に定義できます。この引き戻し関手(pullback functor)を ΔF:[T, Set]→[S, Set] と書きます。難しいのは [S, Set]→[T, Set] 方向のデータ移動です。これに対してスピヴァックは、右前送り関手(right pushforward functor)ΠFと左前送り関手(left pushforward functor)ΣFを次のように定義します。

  • 右前送り関手ΠFは、ΔFの右随伴である。
  • 左前送り関手ΣFは、ΔFの左随伴である。

ΔF、ΠF、ΣF はそれぞれ、Fによって誘導される射影、ジョイン、ユニオンだと言ってもいいでしょう。

これらのデータマイグレーション関手をベースにしてスピヴァックは、スキーマ変換のラウンドトリップ性や、外部キーで結ばれた複数のビュー(実テーブルではない)の更新方法などを議論しています。論旨は明快であり、定式化と推論は厳密です。

関手的データモデルは、関係データベースにだけ適用可能なものではありません。スピヴァック自身、半構造的データベースの例としてRDF(Resource Description Framework)をしばしば引き合いに出しています。XMLJSONベースのデータベース、古典的な網型、階層型のデータベースなども守備範囲に入ります。

Kleisli Database Instances という論文では、ちょっと悪乗り気味に、離散力学系、有向グラフ、チューリングマシン、群の線形表現なども“データベース”の例だと主張してます(やり過ぎだろ)。

他にもまだ面白い話題が山盛りですが、今日はここまでにしておきます。スピヴァックの圏的情報学/関手的データモデルの具体的な内容については、またの機会に紹介したいと思います。

*1:スピヴァック以前にも、categorical informatics という言葉を使っていた人はいると思いますが。

*2:データベース・インスタンスをδのようなギリシャ文字小文字で表すこともあります。

*3:[追記]この文は、Functorial Data Migration からの引用です。ちなみに、the second goal は、データマイグレーション関手の定義です。[/追記]