アブラムスキーが語る、普通のデータベースで普通に起きる量子的現象

最近、データベースに関する記事「概念的に単純明快合理的なデータベース問い合わせ言語その1」を書きました。それで、データベース関連のキーワードで検索しているうちに、すごく面白いモノを見つけてしまいました。

とりあえず「コレは面白そうだ」と言っておきます。$`
\newcommand{\mbf}[1]{\mathbf{#1}}
`$

内容：

サムソン・アブラムスキー
アブラムスキーがデータベースについて書いていた
文脈性
関係データベース
類似性
文脈性はどこから来るのか？

サムソン・アブラムスキー

サムソン・アブラムスキー〈Samson Abramsky〉は、イギリスの著名な計算科学者です -- 僕は計算科学〈computing science〉の人だと思っていますが、物理も論理も圏論も得意で、ひょっとすると物理学者と認識している人もいるかも知れません。分野を横断した功績を残している人です。

このブログ内でもアブラムスキーへの言及はけっこうあります。

このブログ内での「アブラムスキー」の検索結果

2010年の記事「Webサービスの設計：リンク集＋お絵描きWeb設計」に、アブラムスキーの肖像写真（Wikipediaから）を載せています。

2014年の記事「その後の抽象スカラー、それとダガー圏」にも、セリンジャー〈Peter Selinger〉（過去記事では「セリンガー」と表記していた）、パナンガデン〈Prakash Panangaden〉と一緒の写真を載せています。

[2014年時点において]5,6年前の写真でしょうか、左がアブラムスキー、右がセリンガー（まん中はパナンガデン）です。

圏論勉強会と周辺の人々で、アブラムスキーのテンパリー／リーブ代数の論文を読んでいたこともあります。

[Abr09-]
Title: Temperley-Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics
Author: Samson Abramsky
Submitted: 14 Oct 2009
Pages: 44p
URL: https://arxiv.org/abs/0910.2737

2009年にArXivに投稿される前から ox.ac.uk （オックスフォード大学）ドメイン内で上記論文は公開されていて、以下の過去記事に言及があります。

寝る前に（2007-04-28 ）
圏論勉強会：3点テンパリー／リーブ代数の掛け算九九（2008-06-16）

アブラムスキーがデータベースについて書いていた

以下は13年も前の論文です。

[Abr12-13]
Title: Relational Databases and Bell's Theorem
Author: Samson Abramsky
Submitted: 31 Aug 2012 (v1), 12 Jul 2013 (v2)
Pages: 19p
URL: https://arxiv.org/abs/1208.6416

えっ、「関係データベースとベルの定理」だってぇ、なにそれ？面白そうじゃん！

2012年／2013年頃といえば、僕はスピヴァック〈David I. Spivak〉の関手データモデル〈functorial data model〉に“衝撃”を受けていました。

デイヴィッド・スピヴァックはデータベース界の革命児か -- 関手的データモデル（2013-01-28）
衝撃的なデータベース理論・関手的データモデル入門（2013-02-11）

ほぼ同じ時期にアブラムスキーも、データベースに関するナカナカに衝撃的な理論を発表していたのです。僕は今まで13年間まったく知りませんでした。データベース・コミュニティで話題になったなんてことも、おそらくなかったでしょう。

「関係データベースとベルの定理」に関連する論文として以下もあります。

[ABILM15-17]
Title: Contextuality, Cohomology and Paradox
Authors: Samson Abramsky, Rui Soares Barbosa, Kohei Kishida, Raymond Lal, Shane Mansfield
Submitted: 10 Feb 2015 (v1), 5 Mar 2017 (v2)
Pages: 18p
URL: https://arxiv.org/abs/1502.03097

「文脈性、コホモロジー、そしてパラドックス」 -- まー、なんて魅惑的なタイトルなんでしょう。

文脈性

僕は物理はよく知らない／分からないので、前節の論文を拾い読みしたニワカ仕込みの浅知恵で語ります。「たぶん、こんなことじゃなかろうか？」という程度の話なので眉にツバしながら読んでください。

物理で「文脈性〈contextuality〉」という言葉・概念があります。量子力学において登場するケースが多いようですが、量子と無関係な状況でも意味を持つ概念です。

物理的実在物があるとして、それを認識するには観察・測定するしかありません。その物理的実在物を把握するには単一の測定装置では不十分で、複数の測定装置が必要だとします。例えば（あくまで説明のための仮の事例ですが）、A, B, C の3つの測定装置を使うことにします。それぞれの測定装置はどれも、測定結果として実数値を返すとします。

測定には誤差があるので、何度も測定を繰り返します。それらのバラついた測定値達は $`\mbf{R}`$（実数直線）上の（経験的）確率分布になります。2つの測定装置を一緒に使って同時測定をすれば $`\mbf{R}^2`$ （ユークリッド・デカルト平面）上の同時確率分布になります。

さて、何らかの事情で3つの測定装置を全部一度には使えないとして、2つの測定装置のペアを使うことにします。組み合わせ方は幾つかあります。

A と B の同時測定
B と C の同時測定
A と C の同時測定

これらの同時測定を何度も繰り返して、信頼に足る実験的〈経験的〉2次元確率分布達が得られたとします。それらの2次元確率分布が3枚の方眼紙にプロットされたとしましょう。この3枚の確率分布図を見て我々は、当該の物理的実在物を「測定により捕まえた」と確信するでしょう。3枚の図が、物理的実在物の完全な描像ではないにしろ、物理的実在物の存在を疑うことはないでしょう。

しかし、その3枚の確率分布図を発生させる物理的実在物なんて在りゃしない、って、そんな事態が起こり得るそうです。そんなバカな?! と思いますよね。僕も“ちょっと何言ってるかわからない”（© サンドウィッチマン）。

んじゃ、測定結果は何だったんだ？となります。測定結果は幻ではなくて事実です。が、それは2つの測定装置の同時測定により得られた事実です。3つの測定装置を同時に使って測定すると（それが出来たとして*1）何も観測されないのです。

このような不可解な現象や、現象を引き起こす原因を文脈性と呼んでいるようです。

関係データベース

ミクロな量子力学現象なら、文脈性があっても「まー、量子の世界だからな。そんなこともあるかもな。」と思えます。アブラムスキー達が指摘していることは、古典的、つうか要するに普通の（IT関係者ならみんな知っている）関係データベース〈relational database〉の世界にも文脈性が在るということです。

データベースは、データベース全体として何かしら現実世界を写し取っているはずです。話を簡単にするために、データベース全体に3つのカラム A, B, C があるとします。カラム A, B でテーブル AB、カラム B, C でテーブル BC、カラム C, A でテーブル CA を構成しているとします。

これら3つのテーブルに次のようにデータが入っている状況を考えます。

テーブル AB

A	B
0	1
3	4
6	7

テーブル BC

B	C
1	2
4	5
7	8

テーブル CA

C	A
2	3
5	6
8	0

この状況を作るためのSQL文は以下のようです（SQLiteを使用しています）。SQL文を知らないなら、SQLコードは無視してください。話の筋はちゃんと追えますから大丈夫です。

CREATE TABLE AB
(
  A INTEGER,
  B INTEGER
);
CREATE TABLE BC
(
  B INTEGER,
  C INTEGER
);
CREATE TABLE CA
(
  C INTEGER,
  A INTEGER
);

INSERT INTO AB VALUES
  (0, 1),
  (3, 4),
  (6, 7)
;
INSERT INTO BC VALUES
  (1, 2),
  (4, 5),
  (7, 8)
;
INSERT INTO CA VALUES
  (2, 3),
  (5, 6),
  (8, 0)
;

データベース設計では、単一のテーブルに格納可能なデータでもあえて複数のテーブルにバラして格納することがあります。単一テーブルにまとめた結果が欲しいならば、ジョイン〈join〉というテーブル操作をすればいいのです。例えば、テーブル AB とテーブル BC のデータを、A, B, C という3つのカラムにまとめ上げたいなら、以下の問い合わせ（SQL SELECT文）を使います。

SELECT AB.A, AB.B, BC.C FROM AB
NATURAL INNER JOIN BC
;

この問い合わせの意味は：

ABテーブルとBCテーブルのデータを使って、
ABテーブルのカラム A と、ABテーブルのカラム B と、BCテーブルのカラム C を表示する。
このとき、ABテーブルのタプル（横1行分のデータ）と、BCテーブルのタプルで、カラム B の値が等しいものだけを選んで新しい3カラムのタプルを作る。

このような、特定のカラム値が一致するタプルをまとめて1つのタプルを作る操作がジョインです。SQL SELECT文に出てくる NATURAL, INNER などは、今の話には非本質的なので気にしなくていいです。

問い合わせの結果は次のようになります。

A	B	C
0	1	2
3	4	5
6	7	8

元になるテーブル AB（左）とテーブル BC（右）を再掲すると：

A	B	B	C
0	1	1	2
3	4	4	5
6	7	7	8

“テーブル BC とテーブル AC のジョイン”、“テーブル AC とテーブル BC のジョイン”でも同様にジョインされたデータを表示できます。

ところが、以下のSELECT文により3つのテーブルを1つにまとめ上げると、結果は空なテーブルになります。

SELECT AB.A, AB.B, BC.C FROM AB
NATURAL INNER JOIN BC
NATURAL INNER JOIN CA
;

データベース全体（3つのテーブル達）には、全体として表現している現実世界の対応物がなかったことになります。

類似性

前々節の物理系の観測・測定の話と前節の関係データベースの話は類似性があります。

2つの観測装置による同時測定の結果は平面 $`\mbf{R}^2`$ の一点としてプロットできます。2つのカラムを持つタプルは格子平面 $`\mbf{Z}^2`$ の一点としてプロットできます。たくさんの同時測定結果達は確率分布を形成しますが、たくさんのタプル達はテーブルデータを形成します。

同時測定値達の2次元確率分布は、3次元の確率分布の周辺分布〈marginal distribution〉と想定されます。物理系の観測・測定では、3つの2次元周辺分布達の合成が3次元の確率分布の近似を与えると考えます。その近似は、物理的実在物の“測定結果による（やや不正確かも知れない）描像”です。

関係データベースの2カラム・テーブルデータは、3カラムのテーブルデータの射影像〈projection image〉と想定されます。現実世界の関係データベースによる記述では、3つの2カラム・テーブルデータ達のジョイン〈結合〉が3カラム・テーブルデータの近似（望みとしては正確な表現）を与えると考えます。その近似は、現実世界の“コンピューターで扱えるデータによる描像”です。

文脈性は、「“観測・測定の対象物である物理的実在物”、あるいは“データとしてモデル化すべき現実世界の対象物・事態”が存在しない」という現象を引き起こします。物理系の観測・測定と、関係データベースによる現実世界モデリングには明らかに類似性があります。

しかし、この類似性は単に「偶然になんだか似ていた」だけかも知れません。見かけ上の偶発的類似性ならば、そこに共通の構造はありません。

アブラムスキー達が言うには、この類似性は偶発的類似性ではないのです。共通の構造があります。

文脈性はどこから来るのか？

共通の構造が、ミクロな世界にしか通用しない原理であるはずはありません。だって、データベースはミクロな世界にあるモノじゃないですからね。ミクロ・マクロに無関係な構造がニ種類の文脈性を引き起こしているのです。

アブラムスキー達の分析によれば、文脈性を引き起こしている共通構造は、幾何的〈geometric〉なものです。ファイバーバンドル〈fiber bundle〉という幾何的構造があります。ファイバーバンドルのねじれが文脈性の淵源えんげんなのです。

以下の絵は、先に引用したアブラムスキー達の論文 [ABILM15-17] にあった絵です。

これは、ポペスク／ローリッヒ箱〈the Popescu–Rohrlich box〉と呼ばれる物理系モデルを量子情報学的に簡略化した絵らしいです（正確なところは僕はよく分かりません）。見てすぐ分かることは、メビウスの帯の有限離散化になっていることです。

もともとの（連続的な）メビウスの帯の絵を、教科書から拝借すると次のようです。

$`F`$ と名付けられた区間（縦棒）が、単一測定装置の測定値やひとつのカラムのデータ型（データベース用語では「カラムのドメイン」）に相当します。円周の一部である $`U`$ が、複数の測定装置の組み合わせや複数のカラムの組み合わせに相当します。網がかかっている $`\pi^{-1}(U)`$ は、同時測定値のグラフやタプルデータがプロットされる領域です。

対象物の確実な全体像を得るには、円周のすべての点（の有限離散近似である有限個の点）での測定値が必要です。メビウスの帯上に描かれたグラフ断片や部分的タプルデータを繋ぎ合わせて、円周のすべての点で定義された大域的データ〈global data〉が欲しいのです。

が、メビウスの帯はねじれているので、大域的データ*3を作ることはできません。大域的データがひとつもないということは、たくさんの大域的データ達（あるいは1つの大域的データの統計的ゆらぎ達）の周辺分布／射映像だと思っていた確率分布／テーブルデータには、対応する大域的データなんてものは無かったことになります。

局所的なデータならいくらでも作れるのだけど、複数の局所的データ達を整合的に繋ぎ合わせた大域的データは作れない、という状況ですね。

驚くべきことに、関係データベースにおける局所・大域問題は、1970年代から1980年代にかけてフェイギン〈Ronald Fagin〉達により詳しく研究されていて、文脈性が生じるかどうかの条件とその判定アルゴリズムが完成しています。

ウルマン〈Jeffrey D. Ullman〉*4が、その経緯を回顧録的にスライドにまとめています。この記事の関係データベースの事例はウルマンのスライドからです。

Ron Fagin and Acyclic Hypergraphs

データベース分野では、局所データ達が整合的に大域的データを定義できるかどうかを、無サイクル・ジョイン従属性〈acyclic join dependency〉という概念で記述しています（例えば、以下の論文参照）。

Acyclic join dependency and data base projections (by Richard Hull, December 1983)

無サイクル・ジョイン従属性は、幾何的な言葉に翻訳すると、ファイバーバンドルの1次のコホモロジーが消えることです。ゼロでない1次コホモロジー類が、局所データ（断片）達から大域的データを作るときの障害〈obstruction〉になっています。

つまり、物理系の測定や関係データベースにおける局所・大域問題は、ファイバーバンドルとそのコホモロジーにより定式化・記述できる、ということです。コホモロジーの具体的な計算には、ファイバーバンドルから層〈sheaf〉を作り、被覆族〈covering family〉のチェック・コホモロジー〈Čech cohomology〉を使います*5。

アブラムスキー達は、実際に関係データベースを離散空間上の層の言葉で定式化・記述しています。これまた驚くべき（僕は驚いた！）ことなんですが、底空間（比喩的には、下側の円周）の被覆族がデータベースにおけるスキーマ〈schema〉になっています。チェックの手法〈Čech methods〉に登場する諸々の概念の対応物が、データベース側にキッチリと揃っているのです。フェイギン達が使っていた無サイクル性〈acyclicity | 非輪状性〉って言葉、コホモロジーでも出てきますよね -- そうとは知らずにデータベース用語として使っていたのでしょうが。

“物理系の測定”と“関係データベース”に現れる文脈性、一見まったく無関係な偶然の類似性に思えますが、その背後にファイバーバンドルという幾何的構造があり、層のコホモロジーの非消滅（ゼロではないこと）が、ある種のパラドックスの原因だったのです。面白くないですか？コレ。

*1:原理的に出来ないことがあるようです。

*2:Fundamentals of Advanced Mathematics V3

*3:ファイバーバンドルまたは層の大域セクション

*4:「ホップクロフト／ウルマンのウルマン」と言えば分かる人もいるでしょう。

*5:被覆族の細分による極限を取らないで、特定の被覆族により計算した結果が重要な意味を持つようです。