-
ユーザはデータベースを効率的に使おうとするならば関係の意味を知っていなければならない。例えば、基底関係Sの意味は以下のようなものになる。
特定の納入業者番号（S#）をもつ納入業者は特定の名前（SNAME）と特定の状態値（STATUS）をもっており、特定の都市（CITY）に所在地がある。さらに、二つ以上の納入業者が同じ納入業者番号をもつことはない。
この説明はあまり正確ではないが、本章の目的のためには役に立つ。形式的には上記の説明は述語（predicate）または真理値関数――この特殊な例では四つの引数を持つ関数――と呼ばれるものの例である。 引数に値を代入することはその関数を呼び出し（あるいは述語）を具体化し）、真か偽になる命題（proposition）とよばれる式を生み出すことと等価である。
C.J.デイト[1]
はじめに
SQLには「述語(predicate)」という名前を持つ予約語が多く登場します。代表的な述語をリストアップしてみましょう。
- 比較述語(=, <>, > <)
- IN述語
- EXISTS述語
- 限定述語(ALL述語, ANY述語)
- LIKE述語
- BETWEEN述語
- IS NULL述語
- 述語（predicate）は真理値をとる関数である。つまり、それは、ある適当な引数が与えられれば、真か偽を返す関数である。例えば”＞”は述語である。”＞（ｘ，ｙ）”という式 ―― 普通の書き方をすれば”ｘ ＞ ｙ” ―― はもし ｘ の値が ｙ の値より大きければ真を、そうでなければ偽を返す[4]。
この文章は、SQL に応用されている述語論理の初歩を解説するものです。SQL を日常使っているけど、述語論理は知らないという人を読者に想定しています。
普通、論理学の教科書を読むと述語論理の前に命題論理（propositional logic）についての解説があって、確かに、先に命題論理を知っていた方が述語論理を理解しやすいのですが、ここでは命題論理は飛ばして、いきなり述語論理の話をします。その理由は、SQL を使っていれば意識せずに基本的な命題論理を使っているので、説明しなくてもすんなり述語論理に入れるからです。
述語論理入門 その1：述語と変項
コッドは、関係モデルの基礎に述語論理を用いました。彼が述語論理を関係モデル用に書き換えたものを関係論理（relational logic）と呼びます。細かく言うと、関係論理にも２種類あって、コッドが考えたものをタプル関係論理、後にラクロアとピロッテによって提案されたものをドメイン関係論理と言います。しかし、どちらも同じ記述力を持つので、あまり違いを気にする必要はありません。
述語論理という体系自体は、コッドの発明になるものではありません。創始者はドイツの哲学者 G.フレーゲです。彼の処女作『概念記法』(1879)において史上初めて（一階）述語論理が提唱されました。これは、論理学と哲学に革命をもたらした発明だったのですが、そちらの話はこの文章ではしません。興味ある方は私が作っているフレーゲのサイトを覗いてみてください。
では述語論理の基礎知識の導入です。第１段階として導入するのが、「命題(proposition)」という用語です。命題とは要するに記述文のことです。たとえば「クジラは魚である」とか、「昨日は晴れだった」などの文は命題です。真偽判定の対象になる文と言うこともできます。従って、命令文「100万円くれ」や疑問文「今ヒマ？」や勧誘文「僕と一緒に電車に乗ろう」は命題ではありません。真偽の問いようがありませんから。
ある命題の持つ真偽を真理値（truth value）と言います。真理値には、2値論理なら true と false の2種類、3値論理ならそれに加えて、例えば unknown があります。一つの命題はただ一つの真理値を持ちます。「真かつ偽」というような命題は存在しません。
ところで、「神は存在する」とか「クジラ + 猿 = クエン酸」とか「2050年には人類は滅亡している」のような、記述文ではあるが真偽判定ができない文の真理値をどう定めるか、あるいはそもそもこれを命題と認めるかどうかは、難しい問題です。これは論理学にも込み入った問題をもたらします。フレーゲは真理値として true と false の二つしか認めず、全ての命題の真理値は必ず真か偽に決まると考えました（2値原理）。これはその後のほとんどの数学者や論理学者もそうです。私たちが学校で習った数学や論理学もこの原則を守っています。ですが、関係モデルが拠って立つ3値論理では、記述文の真偽が判定できない場合もあることを認めます。「その命題の真偽は判定できない」という意味の第三の真理値 unknown を導入することで、この問題に簡単に決着をつけたのです。もっとも、その代償として、3値論理の演算は2値論理に比べてかなり複雑で、人間の直観に反するものになってしまいました。何もかもうまくいく、とはいかないものです。（3値論理については、こちらの解説を参照のほど。）
では命題の導入を済ませたら、次へ進みます。第２段階は、命題を述語と変項に分解することです。例として、「ポチは犬である」という命題を取りましょう。どうやるかというと、固有名「ポチ」のところを空欄で置き換えます。すると、
「□は犬である」
という文ができます。この不完全な文が「述語（predicate）」です。空欄の部分が「変項（variable）」と呼ばれます。普通、x, y, z …… などの小文字のアルファベットで表して「x は犬である」のように書きます。当たり前ですが、「x は犬である」という文は、これだけでは真偽を判定できません。命題ですらありません。変項 x に「ポチ」や「パトラッシュ」のような個体名を代入することで初めて真偽判定可能な命題となります。それゆえ、この「x は犬である」という述語は、対象から真偽への関数として見なすことが可能です。「x は犬である」という関数は「ポチ」という対象に対して true という真理値を、「タマ」という対象に対しては false を出力するのです。ここは重要なポイントなのでよく理解してください。「命題を述語と変項に分解する」というフレーゲのアイデアが革命的だった点は、文の構造に関数論的アプローチを持ち込んだことだったのです。まだイメージが湧かないという方のために、「x は犬である」という関数を、もっと数学らしい記述で表現してみましょう。
dog(x)
あら不思議、こう書くと、多少は関数のような気がしてきます。変項 x にペットの名前を代入して、命題を作ってみてください。
dog(ポチ) = true
dog(パトラッシュ) = true
dog(タマ) = false
dog(マイケル) = false
ここまでくれば、変項とは、数学の関数における「変数」に対応する用語だということも理解されるでしょう。変数には数しか代入できませんが、変項には数以外の要素も代入できるので、変"数"ではなく変"項"という言葉が使われています。さらに、この dog 関数を、論理学の一般的な表記方法で書いてみます。数学の表記とあまり変わりませんが、「Dx」と書きます。関数名はアルファベットの大文字１字、括弧は省略されます。
では、第３段階へ進みましょう。「x は犬である」という関数では、変項は x の１個だけでした。ですが、変項の数はいくら増やしてもかまいません。例えば2変項の関数として「x は y を愛する」とか「a は b の親である」といったものを挙げられます。数学的表記なら、love(x, y)、parent(x, y)、論理学的表記なら Lxy、Pxy という具合です。1変項関数の述語は1項述語と呼ばれ、2変項ならば2項述語、一般に n変項なら n項述語と呼ばれます[5]。
述語論理入門 その2：量化子
実際に、SQL の色々な述語を述語論理の立場から調べましょう。まず表記の仕方を書き換えてみると
| SQLの表記 | 数学の表記 | 論理学の表記 | 変項の数 |
| x = y | identfy(x, y) | Ixy | 2 |
| x > y | greater(x, y) | Gxy | 2 |
| x LIKE y | like(x, y) | Lxy | 2 |
| x BETWEEN y AND z | between(x, y, z) | Bxyz | 3 |
| x IS NULL | isnull(x) | Nx | 1 |
いい感じです。ここまでなら、単純な関数だけで SQL の述語を表現できます。でも、お気づきでしょう。そう、EXISTS 述語と IN 述語がありません。
実は、この二つの述語を表現するためには、前章で紹介した関数の一般形式では能力不足なのです。具体例を使って説明しましょう。 次のクエリは、社員テーブルから、有名人と同じ誕生日の社員の名前を全て選択します。
社員テーブル ：Personnel
有名人テーブル ：Celebrities
--1.EXISTS述語を使った場合
SELECT P1.name
FROM Personnel AS P
WHERE EXISTS ( SELECT *
FROM Celebrities AS C
WHERE P.birthday = C.birthday);
--2.IN述語を使った場合
SELECT P1.name
FROM Personnel
WHERE birthday IN ( SELECT birthday
FROM Celebrities);
この EXISTS や IN によって表現されている意味は「社員 x と同じ誕生日の有名人が、少なくとも一人存在する」です。「x と y の誕生日が一致する」という2項述語では、この意味を表現できません。素朴に考えると
Pxy
とでも表したくなりますが、これは間違いです。Pxy は「x と y の誕生日が一致する」という意味にしかなりません。「少なくとも一人」という数量の含意が表現されていないのです。どうすればよいのでしょう？ 心配には及びません。述語論理にはこういう表現を作るための道具立てもちゃんと用意されています。それが「量化子」です。（限量子、数量詞という呼び名もあります。）
量化子には2種類あります。「すべての x について～」を表す∀という記号と、「～を満たす x が存在する」を表す∃という記号です。量化子は次のように書きます。
| 「あらゆる x について～」 | ∀x | 普遍量化子、または全称量化子(universal quantifier) |
| 「～を満たす x が存在する」 | ∃x | 存在量化子(existential universal) |
妙な形をした記号だと思うかもしれませんが、全称量化子はアルファベットの「A」を上下逆にした形、存在量化子は「E」を左右逆にした形です。「あらゆる x について～」を英語で書くと「for All x, ～」、「～を満たす x が存在する」は「there Exists x that ～」と書くのでこういう記号が採用されました。また存在量化子の「～を満たす x が存在する」は、「～を満たす x が少なくとも一つ存在する」と読みかえてもかまいません。
すると、先に述べたように、SQL の EXISTS述語は、存在量化子を使って以下のように書けます。
- ∃yPxy ・・・ 「x と誕生日が等しくなるような y が(少なくとも一人)存在する」
これでフレーゲも満足するに違いありません。ところで、ここで注意してほしい重要なポイントがあります。「∃yPxy」という命題関数はいくつの変項を含むでしょうか？ 多くの人が「x と y の二つを含む」と思うのではないでしょうか。しかし、それは間違いです。この命題関数は x のみを変項として持つ、1変項関数です。量化子によって量化されている y は、もはや変項ではないのです。こういう量化された変項を「束縛変項」、そうでない変項を「自由変項」と呼びます。束縛変項は名前だけの変項で、実質的には変項ではありません。
従って、Fx は命題関数ですが、∀xFx は命題関数ではなく、命題です。Fx は、x に代入される個体名に応じて真理値が決まりますが、∀xFx はこの式だけで真理値がちゃんと決まります。「x は泳げる」という命題関数の真理値は、x が直子だったり緑だったりシンジだったりによって異なりますが、「全ての x は泳げる」という命題の真理値は、x に代入される名前の範囲が人間であればfalse に決まります（カナヅチがこの世に居る限りこの命題はfalse ですから）。つまり、∀xFx の束縛変項 x には、いわば全ての固有名が代入済みの形になっているのです[6]。
ではまとめとして、練習をやってください。
問題：「x は y を愛する」(=「y は x に愛される」)を Fxy と表す。次の命題関数を量化子の記号を用いて表せ。ただし x と y は人間とする。
- x は全ての人を愛する
- x には愛する人がいる
- すべての人は y を愛
- y を愛する人がいる
- 全ての人から愛される人がいる(アイドルの存在)
- 全ての人を愛する人がいる(博愛主義者の存在)
- 誰にでも愛する人がいる(冷血漢なんていない)
- 誰でも誰かから愛されている(モテない男への福音)
解答
- ∀yFxy
- ∃yFxy
- ∀xFxy
- ∃xFxy
- ∃y∀xFxy
- ∃x∀yFxy
- ∀x∃yFxy
- ∀y∃xFxy
述語論理入門 その3：WHERE句を述語論理の視点から見る
前章までで、述語論理の基礎を簡単に解説しました。繰り返すと、
- 命題を述語と変項に分解する
- 「全ての x について～」「～を満たす x が存在する」を意味する量化子を導入する
SELECT P.name
FROM Personnel AS P
WHERE sex = 'male'
AND emp_id > 5000
AND birth_year BETWEEN 1970 AND 1980
AND EXISTS ( SELECT *
FROM Celebrities AS C
WHERE P.birthday = C.birthday);
を考えます。この SQL の意味を日本語で表現すると、
名前を従業員テーブルから選択せよ。その条件は
性別が男性である
かつ 従業員 ID が5000より大きい
かつ 生年が1970から1980の間である
かつ 有名人の少なくとも一人と誕生日が一致する。
となります。それではこの SQL を述語論理的に表現してみましょう。分かりやすいように関数は数学的表記を使います。
SELECT P.name
FROM Personnel AS P
WHERE identify(sex, 'male')
AND greater(emp_id, 5000)
AND between(birth_year, 1970, 1980)
AND ∃C.birthday(identfy(P.birthday, C.birthday));
このように書くと分かるように、WHERE句は、述語に値を代入することで作られた命題を、AND、OR、NOT の三つの結合子によって結合することによって構成されています。後はテーブルを一行づつ見ていって、各行の性別や誕生日の値を当てはめてやれば、完全に命題を連結した条件句のできあがりです。どうでしょう。SQL を述語論理的に（＝関数的に）眺められるようになったでしょうか。
「SQLの中の述語論理」はこれで終わりです[7]。述語論理についてもっと詳しく知りたいと思った方は、「データベースについての参考書籍」の述語論理の欄を参考にしてください。より面白く、高度な世界が広がるはずです。
注
[1] C.J.デイト『データベースシステム概論 第6版』(丸善 1997) p.108
[2] 述語は、演算子という名称でも呼ばれます。「=, <, > , <>」は比較演算子（コッドはシータ演算子と呼びました）という呼び方のほうが、むしろ一般的かもしれません。また、IN 関数、LIKE 関数などのように、そのままずばり「関数」と呼ばれることもあります。もちろん、間違った呼び名ではないのですが、これでは真理値を出力するという特性が不明確になるので、私は「述語」という呼び方が明確で気に入っています。
[3] unknown という真理値は、関係モデルが NULL の存在を許したことで3値論理を採用せざるをえなかったために持ち込まれた第三の値です。だから、2値論理に基づく古典的な論理学においては unknown は存在せず、真理値は true と false の二つのみです。
[4] デイト、p.857
[5] 一項述語は別名、非関係述語、多項述語は関係述語とも呼ばれます。多項述語が、個体間の関係を表現する述語であることからきた呼び名です。英語の他動詞は関係述語に、自動詞は非関係述語に、それぞれ含まれます。また、n項述語は n-アリティ(arity)述語とも呼ばれます。アリティとは、その述語がいくつの変項を取りうるかを表す用語です。
[6] 実際のところ、代入される対象の数が有限の場合は、どれだけ長くなろうと、∀xFx は「Fa ∧ Fb ∧ Fc ∧ ･･････」、∃xFx は「Fa ∨ Fb ∨ Fc ∨ ･･････」という、命題論理の連言、選言の論理式と同値です。そしてデータベースのテーブルは有限の行数しか持たないのだから、その意味ではリレーショナル・データベースの論理は命題論理の範囲内に収まると言うことができます。量化子が不可欠になるのは、対象の領域が無限集合になる場合、または多重量化文を表現する場合です。もっとも、量化子を使った表現が簡潔で便利なのは間違いないので、データベースの議論でも一般的に使われます。
[7] 全称量化子の解説はないの？、と思う方もいるでしょうが、実は全称量化子と存在量化子は、片方さえ定義すればもう一方を論理的に導くことができます。そのため、どちらか一方だけ定義すれば十分です。このことは、どんな論理学の教科書にも必ず載っているので、自分で確認してみてください。
Copyright (C) ミック
作成日：2002/12/01
最終更新日：2017/06/22
Tweet