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

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

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

データベース:: 論理の使い所は

2017年に「奥野幹也『理論から学ぶデータベース実践入門』はどこがダメなのか」という記事を書きました。そこで指摘した内容で、補足・敷衍したい事が幾つもありました(ピンク色になってます)。が、書き記す気力がなかなか湧かない。

ちゃんと書こうと思うと億劫になるので、ふと思い立ったときに、データベースと論理に関するラフなメモ書きを残すことにします。

内容:

データベースのどこに論理を使うか

奥野幹也『理論から学ぶデータベース実践入門』はどこがダメなのか // 消極的提案: 第2章を削除する」より:

僕が感じたこの本の問題点のひとつは「論理をほとんど使ってない」ことです。どうせ使わないのなら、第2章「述語論理とリレーショナルモデル」は不要です。奥野さんは、

  • 論理学に触れない正規化の解説は、でたらめだと言っても過言ではありません。

と思いっきり強調太字で書いてますが、過言です。実際に、第3章以降で、述語論理を実質的・本質的に使っている所はないです。

奥野本に限らず、「RDB集合論をベースにしている」「RDBは論理を使っている」と言うだけで、実際には集合論も論理もロクに使っていない説明をみうけます。

論理を使うのは、形式化のためです。何らかの形式体系〈formal system〉としての論理系〈logical system〉をセットアップして、その論理系の構文論と意味論により対象物や現象を記述・分析することになります。

データベースとその周辺の事物を記述・分析する場合に、どこにどのような論理を使うべきなのでしょうか? 話が発散しないように、

  • 何を論理式で記述すべきなのか?

という問題設定で考えましょう。

データベース関連で論理式〈formula〉で書きたいもの・ことは、大別すれば次のニ種類でしょう。

  1. 個体に対する条件を論理式で書きたい。
  2. 関係に対する制約を論理式で書きたい。

ここでは、二種類の使用場面を区別するために、

  1. 条件記述〈condition description/definition〉の論理式
  2. 制約記述〈constraint description/definition〉の論理式

と呼び分けることにします。

条件記述の論理式の復習

条件記述の論理式はお馴染みのものです。SQL SELECT文のWHERE句のなかに書くような論理式ですね。

これについては特段に述べることもないですが、念のためにザッと復習して、それと共に用語・記法の確認をしておきます。

集合Aに対して、Formula(A) は、Aの要素に関して記述する論理式〈formula〉の集合とします。論理式は、なんらかの言語Lで書かれるので、L-Formula(A) のように書いたほうが正確ですが、論理言語Lは前もって決っているとします。また、Aの要素を表す変数名を固定するなら、Formula(x:A) のように変数名(ここでは'x')も入れますが、変数名は何でもいいので、変数名を特定せずに、その場その場で適当な変数を使います。

例えば、Personが“世界中のあらゆる時点における人”の集合だとして、年齢20歳以上の女性を選び出すには、次のような論理式を書くことになります。

  • age(x) ≧ 20 ∧ gender(x) = FEMALE

この論理式には色々な記号が登場しました。

  • 集合Person上を走る変数記号 'x'
  • 整数値の定数記号 '20' と、性別値の定数記号 'FEMALE'
  • 関数記号 'age', 'gender'
  • 関係記号 '≧' と '='
  • 論理記号 '∧' 意味は「かつ」

これらの記号達は、事前に論理系の構文論の一部として定義され、記号が指す対象〈デノテーション〉も意味論で決めておきます。

構文論と意味論がハッキリしているのなら、{x∈Person | age(x) ≧ 20 ∧ gender(x) = FEMALE} のような集合が、集合Personの部分集合として(原理的に)確定します。もちろん、「Personとは何か?」「genderという関数はどういうアルゴリズムで与えられるか?」とかは、現実には完全決着が付かないのですが、理想化した状況で考えます。

条件記述の論理式は、古典一階述語論理をそのまま使えばいいでしょう。古典一階述語論理は、極めて安定した基盤です。素直に古典一階述語論理を使えば問題はありません。ただし、古典一階述語論理は計算の効率は芳しくないので、その点の考慮や工夫は別途必要です。

関係とは

データベースにおいて主題的に考えるべき論理式は、“関係の性質”や“関係のあいだの関係”を記述する制約記述の論理式です。制約記述の論理式に関しては色々と問題がありますが、最大の問題は、制約記述の論理式に意識が向けられてないことでしょう。ちゃんと考えないとダメだよ。

制約記述の論理式を考える上で困ったことがあります。制約記述の論理式における定数記号や変数記号は“関係”を表すのですが、「関係」という言葉の意味がクリアではないのです。

数学における(標準的な)関係概念はきわめてクリアです。が、RDBの世界の「関係〈リレーション〉」はそれとは別の意味で使われています。ここでは、「関係」は数学の標準的な意味で使い、RDBジャーゴンRDBコミュニティ特有の隠語)としての「関係」は「テーブル」と呼びます。「RDBにおける『関係』は、数学の『関係』と同じだ」といった主張は信じないほうがいいです*1

以上の方針で述べるとして; A, B を集合として、AからBへの関係〈relation from A to B〉とは、直積集合 A×B の部分集合のことです。

  • rがAからBへの関係 :⇔ r⊆A×B

AからBへの関係の全体を Rel(A, B) と書くことにします。

  • r∈Rel(A, B) :⇔ rがAからBへの関係 ⇔ r⊆A×B

集合Xのベキ集合(部分集合全体からなる集合)を Pow(X) と書くことにすると:

  • Rel(A, B) = Pow(A×B)

次の点に注意してください。

  1. A, B に何の制限もない。任意の集合でよい。
  2. r⊆A×B にも何の制限もない。任意の部分集合でよい。
  3. 関係には向きがある。AからBへの関係とBからAへの関係は違う。
  4. ここでいう関係は、二項関係であり、単項関係や三項関係は含まれない。

二項関係しか考えないことが気になる人がいるかも知れませんが、二項関係があれば、任意のn項関係や高階関係(関係のあいだの関係)をシミュレートできるので心配ありません。常に二項関係で考えることが重要です。

rがAからBへの関係(r⊆A×B)のとき、Aをrの〈domain〉、Bをrの余域〈codomain〉と呼びます。また、rがAからBへの関係であることを r:A→B rel と書くことにします。'rel'を付けているのは、関数と誤解されないようにです。

  • r:A→B rel :⇔ rがAからBへの関係 ⇔ r∈Rel(A, B) ⇔ r⊆A×B

次の書き方も使います。

  • dom(r) = A :⇔ rの域はA
  • cod(r) = B :⇔ rの余域はB

制約記述の論理式とは

AとBを集合として、AからBへの関係の全体は Rel(A, B) と書くのでした。Rel(A, B) も集合なので、Rel(A, B) に関する論理式の集合 Formula2(Rel(A, B)) を考えることができます。'Formula'2と'2'を付けたのは、先程の論理式の集合とは別な言語を使うことになるからです。

Formula2の論理式、つまり制約記述の論理式は、二階の論理式と呼ばれたりもしますが、一階、二階と分類するより、互いに関連するが使用目的が違う二つの論理言語/論理式がある状況を理解することが重要です。

例として、A = B = Person = (人の集合) として、r:Person→Person rel を「結婚している」という関係だとします。

  • (x, y)∈r :⇔ x と y は結婚している

rに含まれるペア (x, y) を「夫婦」と呼び、一番目の要素xの役割名を「夫」、二番目の要素yの役割名を「妻」とすると、

  • (x, y)∈r :⇔ (x, y) は夫婦であり、x は夫、y は妻である

rは、戸籍を管理するデータベースの一部であるテーブルとみなせます。rが持っている情報は、世界全体の情報のごく一部でもかまいません。例えば、特定の市町村の夫婦だけを記録しているとか。

制約記述とは、rのような関係が満たすべき条件を明確に書き下すことです。rとして、Person×Person の勝手な部分集合を取っていいわけではありません。

現時点(2019年6月)日本において、結婚が可能な年齢は男女で差があり(改正される予定だが)、同性婚は認められていません。

  1. 夫婦の夫は18歳以上の男性である必要がある。
  2. 夫婦の妻は16歳以上の女性である必要がある。

これは、「結婚している」あるいは「夫婦である」を表す関係 r に課せられる条件です。関係が満たすべき性質とも言えます。条件を課せられる対象が関係なので、制約という言い方で区別しのたのでした。

データベースにおいて、関係(テーブル)が「異常」だとか「矛盾している」とか言いますが、それは制約を満たしてないことです。基準となる制約を明確にしない限り、「異常」「矛盾している」は無意味です。

関係と部分集合

先に進む前に、関係についてもう少し補足しておきます。

Rel(A, B) = Pow(A×B) なので、関係は部分集合の特殊な形と言えます。しかし一方、部分集合を関係の特殊な形とみなすこともできます。この相互の言い換えはとても重要です。

1 = {0} を単元集合〈singleton set〉(要素をひとつだけ持つ集合)とします*2。集合Aのベキ集合 Pow(A) は、次のように書けます。

  • Pow(A) \stackrel{\sim}{=} Pow(1×A) = Rel(1, A)

Pow(A) と Rel(1, A) のあいだの同型(1:1の対応)は、S⊆X ←→ s⊆1×A で与えられますが、要素のレベルで書けば:

  • x∈S ⇔ (0, x)∈s

Pow(A) と Rel(1, A) は完全に同じわけではありませんが、標準的な同型があります。今後は、Pow(A) の代理に Rel(1, A) を使うことがあります。なんなら同一視する(Pow(A) = Rel(1, A) とみなす)こともあります。

さて、関係 r:A→B rel に対して、im(r), coim(r) という集合を定義します。

  • im(r) := {y∈B | (x, y)∈r となる x∈A が存在する}
  • coim(r) := {x∈X | (x, y)∈r となる y∈B が存在する}

im(r) を関係rの〈image〉、coim(r) を関係rの余像〈coimage〉と呼びます*3。定義から、im(r)⊆B, coim(r)⊆A 、つまり、im(r)∈Pow(B), coim(r)∈Pow(A) です。すぐ前に言った事情で、im(r)∈Rel(1, B), coim(r)∈Rel(1, A) ともみなします。

r:A→B rel に対して、その転置〈transpose〉rT:B→A rel を次のように定義します。

  • rT := {(y, x)∈B×A | (x, y)∈r}

転置 rT は、r の向きを逆にしたものです。像・余像は転置で入れ替わります。

  • im(rT) = coim(r)
  • coim(rT) = im(r)

coim(r)⊆dom(r), im(r)⊆cod(r) ですが、域・余域と像・余像は別物です -- 区別しましょう。

制約記述の論理式の実際

制約記述の論理式は、例えば、「結婚している」を表す関係 r:Person→Person rel が、現状の日本の法律と照らし合わせて妥当かどうかを判断する基準を与えます。この例では、法律が制約として記述されますが、学校のデータベースならば、学校の規則が制約として記述されるでしょう。例えば、「データベース基礎」を受講してない学生は「データベース実践演習」を履修登録できない、とかです。また、企業のデータベースならば、ビジネスルールが制約として記述されるでしょう。

個体(例えば人)に対する条件記述と、関係に対する制約記述を、単一の論理言語で済ませることもできるし、それが便利なこともあります。しかし、互いに関連するふたつの論理言語を準備したほうが使い勝手は良さそうです。

制約記述言語で使われる記号は次のようになります。

  • 関係の集合 Rle(A, B) 上を走る変数記号 例: 'r', 's'
  • 特定の関係を表す定数記号 例: 空な関係を表す ∅, 恒等関係を表す 'idA'
  • 関係を受け取り関係を返す演算記号/関数記号 例: '∪', '∩', 'im', 'coim', 'T'
  • 関係の性質や、関係のあいだの関係を表す記号 例: '=', '⊆'
  • 論理記号 これは条件記述言語と共通

定数記号として、条件記述の論理式を使って定義された部分集合が使えます。例えば、{x∈Person | age(x) ≧ 20 ∧ gender(x) = FEMALE} は、Rel(1, Person) に値を取る関係とみなします。前節で述べた「部分集合を関係とみなす」方法を使います。

im, coim も、関係から関係への一引数関数とみなします。集合(を表す記号)A, B に対して、

  • im:Rel(A, B)→Rel(1, B) func
  • coim:Rel(A, B)→Rel(1, A) func

というプロファイル(関数の域・余域指定)を持ちます。'func'は関数であることを明示する符丁(マーカー)です。

「結婚している」を表す関係が、法的に妥当であることを記述する制約論理式の話に戻りましょう。制約論理式を書く準備に、まずは関係定数を定義します。

  • maleOver18 := {x∈Person | age(x) ≧ 18 ∧ gender(x) = MALE}
  • femaleOver16 := {x∈Person | age(x) ≧ 16 ∧ gender(x) = FEMALE}

これは特定の集合を表しますが、Pow(Person) = Rel(1, Person) とみなせば、maleOver18, femaleOver16∈Rel(1, Person) なので、maleOver18, femaleOver16 は関係定数です。より正確に言えば、'maleOver18', 'femaleOver16' という記号が表す意味〈デノテーション〉が 1→Preson rel というプロファイルを持つ関係です。

関係定数記号 'maleOver18', 'femaleOver16'、関係を受け取り関係を返す関数記号 'im', 'coim'、関係のあいだの関係を表す記号 '⊆'、論理記号 '∧' を使って、関数変数 'r' に関する制約論理式を書けます。

  • coim(r)⊆maleOver18 ∧ im(r)⊆femaleOver16

この論理式は、「結婚している」を表す関係rに対する法的な制約を表します。

データベースのための論理系の枠組み

一階述語論理+集合論とか高階述語論理とか、強力な論理言語/論理系がありますが、データベースの話をするには強力過ぎると思います。値や個体の集合を議論領域〈domain of discourse〉とする一階述語論理、関係の集合を議論領域とする一階述語論理の組み合わせで十分でしょう。前者が条件記述の論理、後者が制約記述の論理です。

条件記述の論理式 p∈Formula(A) は、{x∈A | p} という形で Rel(1, A) の定数(特定の関係)を定義できます。この定数は、制約記述の論理式内で使えます。この意味で、条件記述の論理と制約記述の論理は無関係ではありません。

もし、制約記述の論理式を高階述語論理で解釈したいなら、α∈Formula2(Rel(A, B)) に対応する、集合 A×B 上の2階述語論理式(または集合論の論理式)も構成できます。必要があるなら、強力な論理系に埋め込んで考えてもかまいません。

論理式に出てくる記号(名前)の型(プロファイル)と、定数記号か変数記号かの区別はとても大事です。集合を表す'Person'、関係(部分集合と同一視)を表す'maleOver18', 'femaleOver18' などは定数記号です。それに対して、「結婚している」を表す関係記号'r'(もっとそれらしく'married'とかにしてもよい)は変数記号です。なぜなら、時間の流れに沿って追加・削除されるからです。

変更される関係を指す記号〈名前〉が関係変数記号であり、プログラミングにおけるプログラム変数(破壊的代入を許す変数)に相当します。関係変数記号の値を勝手気ままに換えることが出来ないことを宣言するために、制約記述の論理式が使われるのです。

関係変数rと、rに関する制約論理式α、そして変更操作mがあるとき、次のことが要求されます。

  • 変更操作mの前に、rは制約αを満たしていたならば、変更操作mの後でも、rは制約αを満たしている。

例えば、「25歳の男性と30歳の男性の婚姻届を受理する」と、「coim(r)⊆maleOver18 ∧ im(r)⊆femaleOver16」という制約論理式を満たせなくなります。

制約論理式と変更操作について明確な定式化をしないままで、「異常だ」「矛盾だ」と言ってみても曖昧で雑なことしか言えません。現状のRDBシステム実装や、純粋主義リレーショナル理論は、制約論理式と変更操作について語る枠組みとして相応しくはありません。かといって、新しい枠組みを作る必要もありません(劣化した車輪の再発明をするだけ)。既存の枠組み(論理、集合、圏など)を、歪めたり矮小化しないで、普通に使えばいいのです。

普通に使う方法や例については、次に思い立ったときに。

*1:まったくの間違いではありませんが、断り書きを付けないと正確な主張にはなりません。

*2:単元集合の要素は何でもかまいません。

*3:像を余域、余像を域と呼ぶ人もいますが、そうすると、先に定義した域・余域と区別ができなくなります。それはとても困るので、像・余像を使います。