http://d.hatena.ne.jp/m-hiyama/20130128#c1359767497 :
データベース技術者が「これを知らないのは不幸」と思えるので、(可能な範囲で)紹介はしようかな、と。
「これ」とはもちろんスピヴァックの関手的データモデルです。「データベース技術者」つうより、データベースに多少とも関わるすべての人にとって関手的データモデルは福音となる可能性があると思っています。RDBに限らず、現存するほとんどすべてのデータベース的システムに対して、極めて単純で統一的な記述を与えてくれます。データマイグレーションのように、これまでは途方に暮れていたような現実的な問題を鮮やかに解いてくれます。
「これ」を紹介する/説明する価値は十分にあります。僕自身が、すぐにでも実務的に使いたいと思っています。しかし、スピヴァックの論文群を要約したら関手的データモデルの説明になるかというと、そうとは言えません。分かりやすく説明するには、それなりの工夫が必要でしょう。どうしたもんか?
以下、説明の仕方の考察であって、関手的データモデル自体の説明ではありませんのであしからず ^^;。(独学したい人の参考に少しはなるかな?)
内容:
- 圏論をどこまで使うか
- 圏論の困難はむしろ先入観
- アンビエント圏は部分写像の圏がよいだろう
- あまりにも単純な!
- カルチャーギャップ、カルチャーショック、対策
- 有限性とか
- 新しい適用分野、新しい動機、新しいユーザー
圏論をどこまで使うか
スピヴァックは、"On The Relational Foundations Of Functorial Data Migration" において、「圏論の知識なんて要らないよ」("An understanding of category theory is not required for understanding the key ideas of this paper.")と書いています。確かに、圏論を直接は使わないように注意しているようですが、チョロチョロと圏的概念が漏出しています。
そもそも、「圏論を表に出さない」のが学習効率上いいのか? は疑問です。そこで頑張っても、無駄に回り道をする/させるだけのような気がします。関手的データモデルの基本を説明/理解するのに、いったいどれ程の圏論が必要なのでしょうか?
"Handbook of Categorical Algebra"という3巻・合計1372ページ(364 + 464 + 544)からなる教科書があるのですが、その第1章37ページを読めば十分過ぎます。第1章に書いてあることで、関手的データモデル入門では使わないことがイッパイあります*1。
「Cが圏である」という文を自然に受け入れられて何かしらのイメージを持てれば大丈夫*2だと思います。そのために、次の言葉は知っている必要があるでしょう。
対応する記号/記法は次のようです。
- Aが圏Cの対象 : A∈Ob(C)、または A∈|C|
- fが圏Cの射 : f∈Mor(C)、または f∈C(記号の乱用)
- 射fの域がA、余域がB : dom(f) = A, cod(f) = B
- 射hは、射fと射gの結合 : h = f;g(図式順記法)、または h = g・f(反図式順記法)
- 射iは対象Aの恒等射 : i = idA
- 結合法則 : (f;g);h = f;(g;h)
- 単位法則 : idA;f = f, f;idB = f
これ以外に、可換図式と関手については知っておいたほうがいいでしょう。自然変換は、データベースインスタンスのデータ操作(manipulation)が出てきた段階で「これは、自然変換と呼ばれるモノの例です」と言えばそれでいいような。なお、言葉や記法には様々な“方言”があることには注意してください(「なんでズボラでその場限りになるのか」の冒頭を参照)。
データマイグレーション関手の構成には随伴を使いますが、それは入門を超えた応用と位置づければ、入門段階で随伴もモナドも不要です。極限/余極限も知っているに越したことはないですが、集合圏における具体的な構成(直積集合とか)が出来れば間に合うでしょう。
圏論の困難はむしろ先入観
上記で述べた程度の圏論の基本概念が理解困難かというと、それはないと思います。事例と一緒に学べば納得できるものでしょう。僕の経験では、問題となるのは特定の事例により刷り込まれてしまう先入観です。
特にタチが悪いのは集合圏です。集合と写像からなる圏=集合圏は、とても重要な例です。しかし、集合圏ではない圏も集合圏のように考えてしまったり*4、集合圏でしか成立しない性質を暗黙に仮定してしまったり。弊害も多いですね。
僕が以前に書いた「はじめての圏論」では、意図的に集合圏を出さないようにしています。最初の例はしりとりの圏です。
それと、よく引き合いに出すのは行列の圏:
単なる集合(離散圏)、モノイド(対象が1個の圏)、順序集合(やせた圏)も圏の仲間です。
アミダクジとそのつなぎ合わせを考えると圏になります。
アミダの発展形にブレイド(組み紐)の圏があります。
さらに変わりモノとして、単純平面タングルの圏なんてのを紹介しこともあります。
要するに、集合圏ではない圏がいくらでもあるよ、と言いたいわけです。次の記事も、集合圏の呪縛から抜け出すのに役に立つかもしれません。
ここで注意しておくと、集合圏はもちろん重要だし、めちゃくちゃよく使います。ただし、「対象は集合、射は写像」のような思い込みはとてもマズイのです。
アンビエント圏は部分写像の圏がよいだろう
スピヴァックの定義によれば、データベーススキーマは圏Sで、データベースインスタンスは関手 D:S→Set です。後の論文(Kleisli Database Instances)では、Setの代わりに色々な圏を使っています。データベースインスタンスを実現するための圏(関手の値となる圏)に特に名前が付いてないようなので、ここではアンビエント圏と呼ぶことにします。
アンビエント圏は用途に応じて取り替えればいいのです。スピヴァックの最初の定義ではアンビエント圏=Setとしていますが、Setが一番使いやすいか? と言うと、どうもそうは思えません。集合と部分写像の圏Partialがいいと僕は思います。そう考えるには、少なくとも4つの理由があります。
- 主キー/外部キーという概念を定式化するには、写像より部分写像のほうが適切である。
- データ操作(manipulation, レコードの削除・追加など)の定義が、はるかに単純になる。
- ホムセットに順序構造を入れることができる。
- 計算可能写像との相性がよい。
アンビエント圏は何を使ってもいいし、色々と変えることによって面白くなるんですが、標準的なアンビエント圏としてはSetよりPartialを採用するのが都合がいいと思えるのです。
あまりにも単純な!
関手的データモデルが人を驚かせ、場合によって拒否反応を引き起こすと思われる所は、その単純さです。
例えば、関係データモデルの用語法では、原子的な値の集合をドメインと呼ぶようですが、スピヴァックはテーブルとドメインを区別してません(プログラミング言語との統合モデルではドメイン=型と考えますが)。カラムの集合(複合カラム)と単一のカラムの区別もありません。従属性とビジネスルールの差はありません。もちろん、実テーブルと仮想テーブルなんて概念もありません。
データモデルを構成する基本概念は3つだけ: テーブル、カラム、制約*5 です。それぞれが圏の対象、圏の射、可換図式に対応します。
レコードという概念は出てきますが、別になくてもかまいません(アンビエント圏によってはレコードを定義できないことがあります)。スピヴァックは、主キー/外部キーの定式化として圏的正規形(categorial normal form)というものを定義はしてますが、それに拘っている様子はなく、「使いたければ使えばぁ」というスタンスでしょう。
そんなに単純化して、従来のデータベース理論が再現できるか? と疑問になります。僕は従来のデータベース理論に精通してないので、確信を持っては言えませんが; まー大丈夫そうです。反感を買うのを承知で正直な感想を述べれば、関係データモデルの理論とかは、無駄に晦渋な議論だったように思えます。ほんとに少数(3つです)な基本概念の対応関係を確立すれば、あとは圏論の初等的な枠内で従来の概念はたいてい再構成できます(たぶん)。
その再構成の過程で、難解そうだった概念のかなりの部分は自明またはドーデモイイ話になってしまいます。NULLがどうだの、第N正規形がどうたら、みたいな話も割とドーデモイイことになります(問題が相対化されてしまいます)。実際、スピヴァックは正規化についてはほとんど無関心なようです*6。既存の概念の言い換えより、データマイグレーション、スキーマ発展(schema evolution)、連合データベース、ホモトピー的手法の適用など、新しく重要なトピックがいくらでもあるからでしょう。
カルチャーギャップ、カルチャーショック、対策
前節で述べたように、極端に単純化された基本概念の上に、抽象度の高い機械仕掛け(machinery)を使って結果を出していくのが圏論っぽいやり方です*7。機械仕掛けの強力さを知らないと、単純化された基本概念がプアで無意味なものに見えるかもしれません。ここらへんは、文化的(あるいは方法論的)ギャップになりそうだな、と感じます。首尾よく「単純化しても大丈夫」なことを納得したら、難解な(ように見えた)従来の定式化に対して「ありゃ何だったんだ!?」と徒労感/虚脱感に襲われるかも知れないですしね。
そういうカルチャーギャップ/カルチャーショックをやわらげるには、従来の概念(の一部)は圏的定式化にも持ち込んだほうがいいと思います。
まず、テーブルとドメインを区別するほうが心が安らぐのではないか、と。この区別は、スキーマの“形状”から厳密に定義することができます。また、ドメインの意味(関手の値)は前もって固定するのが普通です。
テーブルは、基本テーブルとその他のテーブルに分けたほうが議論がしやすいでしょう。これは、実テーブル/仮想テーブルの区別と似たようなもので、ユーザーがメンテナンスしたいと意図しているテーブルが基本テーブルです。「意図している」なんて表現が入るので厳密な定義は無理です -- 天下りに与えるしかありません。Sがスキーマのとき、任意に B⊆|S| を与えた構造 (S, B) が基本テーブル付きのスキーマです。
主キーという概念もないと困る人/不安になる人は多いでしょうから、スキーマSの射の部分集合P(P⊆Mor(S))を主キーとして指定します。主キーの集合Pには次の条件があります。
- p, q∈P、dom(p) = dom(q) ならば、p = q
これは、1つのテーブルは高々1つの主キーしか持てないことです。また、データベースインスタンスの関手Dにも次の制限が入ります。
- p∈P ならば、D(p) は全域的単射である。
基本テーブルの集合B、主キーの集合Pを伴ったスキーマは、(S, B, P) という3つ組になります。
ジョイン、ユニオン、問い合わせ結果などは、アンビエント圏のなかでの対象の構成(主にpullback, pushout図式)だと思えば違和感が少ないように思えます。
有限性とか
コンピュータで扱うデータは、どんなに膨大でも所詮は有限です。スピヴァックのモデルでは、有限性の仮定も入っていません。無限個のテーブルを持つスキーマ、無限個のカラムを持つテーブル、無限個のレコードからなるテーブル状態も認めます。
これらを有限個に制限すると簡単になるわけではありません。むしろ、議論がスムーズに進行しなかったり、せっかくの仕掛けが使えなくなったりします。必要に応じて、適宜、有限性の条件を課すのがいいでしょう。仕様の記述やテストの実行は人間やコンピュータが行うので、有限性が必須となる状況はもちろんあります。
スキーマの有限性には、有限表示可能(finitely presentable)という、うまい条件があります*8。群やモノイドにおける「生成元と関係」の圏論版において、有限生成/有限関係で定義できることです。これはまた、有限個の等式的公理で定義される“有限次元”の代数と同じものです。
新しい適用分野、新しい動機、新しいユーザー
「デイヴィッド・スピヴァックはデータベース界の革命児か -- 関手的データモデル」で述べたように、データベースの分野に圏論がストレートに適用できることは、僕にとって意外であり新鮮でした。少し大げさに言えば衝撃的でしたね。
圏論の新しい適用分野が生まれたことは、圏論を学び活用する新しい動機となるでしょうし、圏論の新しいユーザーも増えることでしょう。従来からの圏論ユーザーであったプログラミング言語界隈の人にとっても、データベースへの適用は面白い話だし、プログラム意味論とデータ意味論の統合が極めて容易になることはとても魅力的に思えます。
… って、関手的データモデルの説明の仕方より、関手的データモデルへ勧誘しているようですね。まー、勧誘が僕の本音だからいいんだけどさ。
*1:例えば、米田の補題はなんと11ページに出てきちゃうんですよね。まー、これは教科書としてイカガナモノカという気もしますが。
*2:後述するように、特定事例の固定的なイメージだとマズイのですが。
*3:「合成」のほうがよく使われていますが、僕は「結合」を使っています。
*4:一般の圏を、集合圏で“表現する”ことは重要ですが、それはまた別な話。
*5:[追記]スピヴァックの用語法では、パス同値関係(path equivalence relation)です。[/追記]
*6:[追記]スピヴァックが興味を持ってないから無意味なのか? と言うと、そんなことはなくて、我々にとっては、正規形/正規化を関手的データモデルのなかで再現することは重要で有意義なことだと思います。[/追記]
*7:体力勝負の泥臭い計算もけっこうありますけどね ^^;
*8:「圏がpresentable」には、別な意味もあります。ここでは有限生成かつ有限関係のことです。