コッドの定理

コッドの定理は、リレーショナルモデル用の 2 つのよく知られた基礎クエリ言語であるリレーショナル代数とドメインに依存しないリレーショナル計算クエリの表現力は、まったく同等であると述べています。つまり、データベース クエリは、他の言語で表現できる場合にのみ、1 つの言語で作成できます。

この定理は、データベース管理の リレーショナル モデルの父であるEdgar F. Coddにちなんで名付けられました。

ドメインに依存しないリレーショナル計算クエリとは、データベース自体に現れる値以外の値のドメインを選択しても不変であるリレーショナル計算クエリのことです。つまり、異なるドメインに対して異なる結果を返すクエリは除外されます。このような禁止されたクエリの例は、「関係 R に出現するもの以外のすべてのタプルを選択する」というクエリです。ここで、R はデータベース内のリレーションです。異なるドメイン、つまりタプルを構築できるアトミック データ項目のセットを想定すると、このクエリは異なる結果を返すため、明らかにドメインに依存しません。

コッドの定理は、構文的に全く異なる 2 つの言語の同等性を確立する点で注目に値します。リレーショナル代数は変数のない言語ですが、リレーショナル計算は変数と量化を備えた論理言語です。

関係計算は本質的に一階述語論理と同等であり、^[1]実際、コッドの定理は1940年代後半から論理学者に知られていました。^{[2] [3]}

リレーショナル代数と表現力の点で同等なクエリ言語は、コッドによってリレーショナル完全と呼ばれました。コッドの定理によれば、これにはリレーショナル計算も含まれます。リレーショナル完全性は、興味深いデータベースクエリがリレーショナル完全な言語で表現できることを意味するわけではありません。表現できないクエリのよく知られた例としては、単純な集計(タプルを数える、またはタプル内の値の合計など、SQL では表現できるがリレーショナル代数では表現できない操作) や、バイナリエッジ関係によって与えられたグラフの推移閉包の計算などがあります (表現力も参照)。コッドの定理では、 SQL の nullとそれが伴う3 値ロジックも考慮されていません。null の論理的処理は、依然として論争の的となっています。^[4]さらに、SQL には、重複行を許可するマルチセットセマンティクスがあります。それでも、リレーショナル完全性は、クエリ言語の表現力を比較するための重要な基準となります。

• アビテブール、セルジュ、ハル、リチャード B.、ヴィアヌ、ビクター(1995)。データベースの基礎。アディソン・ウェズリー。ISBN 0-201-53771-0。
• Codd, EF (1972)。「データベースサブ言語のリレーショナル完全性」。Rustin, R. (編) 著。データベースシステム。第 6 回 Courant コンピュータサイエンスシンポジウムの議事録 (1971 年 5 月 24 ～ 25 日: ニューヨーク、NY)。Prentice-Hall。pp. 65 ～ 98。ISBN 0-13-196741-X。

• Pichler, Reinhard (2018 年 3 月 20 日)。「データベース理論: 3. コッドの定理」(PDF)。論理計算研究所、DBAI グループ、ウィーン工科大学。2020年 8 月 22 日時点のオリジナル(PDF)からアーカイブ。2019年8 月 8 日閲覧。