関係論理

関係論理 (かんけいろんり、関係計算、リレーショナル論理、リレーショナル計算、英: relational calculus) は、関係データベースの関係モデル (リレーショナルモデル) において、宣言的な方法で関係 (リレーション、表、テーブル) として表現されたデータを扱う、コンピュータ科学における演算の体系である。 関係論理には、組関係論理 (タプル関係論理) と定義域関係論理とがある。 関係として表現されたデータに対して行う演算体系としては、関係代数とこの項目で説明する関係論理 (関係計算) の2種類が知られている。 関係論理は宣言的にデータを扱う演算体系であり、関係代数が手続き的にデータを扱うのとは対照的である。 組関係論理と定義域関係論理の表現能力は同等である。

関係論理を実装したデータベース言語 (問い合わせ言語) としては、QUEL や SQL、Tutorial D などが挙げられる。 ただし SQL については、関係論理を完全な形で実装していないとして批判する意見がある。

関係モデル

関係モデルの概念

詳細は「関係モデル」を参照

関係論理は関係モデルに基づく関係データベースのデータベース言語 (問い合わせ言語) であるため、最初に関係モデルを簡単に定義する。 関係は、一つの見出しと0以上の同じ型の組の順序づけられていない集合からなるデータ構造である。 値としての関係を、関係値という。 関係値を値としてもつ変数を関係変数 (relvar) という。 関係変数が値としてもつ関係値は、時間とともに変化する。 関係変数はデータ定義言語 (DDL) を使って定義することができる。 見出しは、特定の属性の順序づけられていない集合である。 関係値を構成する組の集合を本体という。 すなわち関係値は、見出しと本体から構成されている。 組 (タプル) は、0以上の属性の集合からなるデータ構造である。 属性は、属性名と定義域の名称のペアである。 定義域は、データ型と同じ意味と考えてよい。 属性は、その定義域に適合するなんらかの属性値をもつ。 属性値は、スカラ値もしくはより複雑な構造をもつ値である。 関係値を構成するおのおのの組は特定の一つ以上の属性の集合で識別される。 この属性集合を候補キーという。 こうした関係モデルの概念は数学的に定義されるが、既存のデータベースの実装はこうした定義に厳密に準拠しているわけではない。 表 (テーブル) は、関係の視覚的表現として受け容れられている。 組は行の概念に似ている。

関係代数との対比と関係完備

例えば関係代数では、書籍データベースから次の手順で、特定の書名の書籍を在庫としてもつ書店の店名と電話番号を問い合わせるであろう。

1. 書籍関係と書店関係を書店IDで結合する。
2. 結合して生成された関係を指定された書名で制限する。
3. 制限して生成された関係を店名と電話番号で射影する。

この例の問い合わせは関係論理では次のような宣言的に定式化できる。

書籍データベースにおいて、書籍関係と書店関係のそれぞれの書店IDが同一であるものとし、指定された書名をもつ店名と電話番号を取得する。

関係代数と関係論理は互いに等価である。 関係代数で表現された式は、等価な関係論理の式で表現することができる。 逆に関係論理で表現された式も、等価な関係代数の式で表現することができる。

関係モデルを考案したエドガー・F・コッドは、関係データベース言語の表現能力について関係完備という用語を定義した。 関係完備とは、コッドが提唱した限定のもとで、一階述語論理に関して完全な言語であることを意味する。 関係論理と関係代数は関係完備である。

組関係論理

組関係論理 (タプル関係論理) はエドガー・F・コッドにより関係モデルの構成要素として考案された。 組関係論理を発想の基としてデータベース言語 (問い合わせ言語) QUELとSQLが設計された。 SQLは、コッドの関係モデルと関係論理に忠実に準拠して設計されていないとして、批判を受けることがある。 しかしSQLは2008年現在ほとんど全ての関係データベース管理システム (RDBMS) のデータベース言語として採用されている。

組関係論理は、{t | φ(t)} の形式で表される。 ここで t は組変数である。 φ はどのように条件づけるかを示す式である。 データベース述語は R(t) もしくは t∈R として記述される。

組関係論理で使われる演算子は次のとおりである。

論理演算子

• ∧ (and)
• ∨ (or)
• ¬ (not)
• ∃ (存在記号)
• ∀ (全称記号)

存在記号と全称記号は変数を束縛することができる。

組関係論理の例

顧客がいる場所:

• {t.場所 | 顧客(t)}

ブレーメン内のすべての顧客:

• {t | 顧客(t) ∧ t.場所="ブレーメン"}

注文した顧客:

• {t | 顧客(t) ∧ ∃s(注文(s) ∧ s.顧客番号=t.顧客番号)}

注文されていない商品:

• {t | 商品(t) ∧ ¬∃s(注文(s) ∧ s.商品番号=t.商品番号)}

組関係論理において、結合の条件は明示的に記述される。

定義域関係論理

定義域関係論理は Michel Lacroix と Alain Pirotte により考案されたといわれる。

定義域関係論理では、問い合わせは次のような形式になる。

${<X1,X2,....,Xn>|p(<X1,X2,....,Xn>)}$

ここでおのおののX_iは定義域変数もしくは定数である。 また p(<X1, X2, ...., Xn>) は関係論理の定式を示している。 問い合わせの結果は X_i から X_n で構成される組の集合であり、この集合は関係論理の定式が真となっている。

定義域関係論理の言語は組関係論理と同じ演算子を使う。

定義域関係論理の例

A、B、C をそれぞれランク、名前、ID とする。 また D、E、F をそれぞれ名前、部署名、ID とする。

恒星船 USS エンタープライズ の全ての船長を問い合わせる:

• {<A, B, C> | <A, B, C> in エンタープライズ ∧ A = "船長" }

この例において、A、B、C は結果集合を示しており、またエンタープライズ関係に含まれる集合を示している。

エンタープライズの船員で星図作成の部署に属する人の名前を問い合わせる:

• {<B> | ∃ A, C ( <A, B, C> in エンタープライズ ∧ ∃ D, E, F(<D, E, F> in 部署 ∧ F = C ∧ E = "星図作成" ))}

この例では名前だけを問い合わせている。 <B>は属性名である。 F = C は要件である。 なぜなら、ここで必要なのはエンタープライズの船員でありかつ星図作成の部署に属する人の名前であるからである。

先の例の別の定義域関係論理式での表現例は次のようになる。

• {<B> | ∃ A, C (<A, B, C> in エンタープライズ ∧ ∃ D (<D, "星図作成", C> in 部署))}

この例では、要求されたF定義域は定式内に直接位置づけられており、C定義域変数は部署の存在を問い合わせる際に再び使用されている。 なぜなら、C定義域変数はすでに船員のIDをもつからである。

参考文献

• 『データベースシステム概論 原著第6版』丸善、東京、1997年。ISBN 4-621-04276-9。 

  Date, Chrisopher J. (2004). An Introduction to Database Systems (8th ed.). Addison Wesley. ISBN 0-321-19784-4 

• 『データベース実践講義—エンジニアのためのリレーショナル理論』オライリー・ジャパン、東京、2006年。ISBN 4-87311-275-3。 

  Database in Depth : Relational Theory for Practitioners. 北京: O'Reilly Media. (2005). ISBN 0596100124 

• Edgar F. Codd: A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 13(6):377–387, 1970.
• Andreas Heuer, Gunter Saake: Datenbanken: Konzepte und Sprachen, MITP Verlag, ISBN 3-8266-0619-1, S. 297 ff.