関係代数 (関係モデル)
こうした人々による肯定的な評価は、コッドが自分の関係モデルから関係の属性の順序という概念を除外したことが大きな理由である。 このモデルでは組(タプル)は、属性名の集合から属性値の集合を導出する部分関数である。 この項目の説明では、組 t の属性 a を t(a) と記述する。
コッドの関係代数が一階述語論理に関しては実際には完全ではないと留意しておくことは、重要である。 仮に一階述語論理に関して完全であったならば、関係モデルをどのように実装するにせよ、コンピュータ上の克服できない困難に突き当たってしまうであろう。 こうした困難を克服するためにコッドは、関係代数の演算対象を有限の関係のみに限定し、また否定(NOT)と選言 (OR)を限定的にサポートすることを提唱した。 コッドの関係代数は、実際にはホーン節で再帰と否定の無い一階述語論理のサブセットである。 こうした限定に類することは、他の多くの論理に基づくコンピュータ言語においてもみられることである。
コッドは、関係データベース言語の表現能力について関係完備という用語を定義した。 関係完備とは、コッドが提唱した限定のもとで、一階述語論理に関して完全な言語であることを意味する。 実際にコッドが提唱した限定は、コッドの関係代数をデータベースのさまざまな目的に適用することにおいて、不都合は無かった。 関係代数は関係完備である。 関係代数と同等もしくは同等以上の表現能力を持つ関係データベース言語は関係完備であるといえる。
R { A, B }
関係 R と S に共通の属性名が無いこと。
σ A ( R ) = σ A σ A ( R ) {\displaystyle \sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)}
σ A σ B ( R ) = σ B σ A ( R ) {\displaystyle \sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)}
関係論理(関係計算)は、関係代数と同等の表現能力を持つため、関係完備である。 なお関係論理には定義域関係論理と組関係論理がある。
どのような代数であれ、一定の数の演算子は基本的 (プリミティブ) であり、それ以外の演算子は、基本的な演算子のみをもって定義できるため、基本的ではない。 関係代数における基本的な演算子の選択が、論理学における基本的な演算子の選択と似ているならば、利便である。 AND、OR および NOT の論理における基本的な演算子の選択は恣意的であることはよく知られているが、コッドは自分の関係代数において恣意的な選択をした。 コッドは関係代数において次の6つの基本的な演算子を定めた。
制限(選択)
射影
直積(直積集合)
和(和集合)
差(差集合)
属性名変更
(実際にはコッドは属性名変更を基本的な演算子群から除去した。しかし属性名変更を含めた例として後の#歴史の節で述べる ISBL が存在する) この6つの演算子は、表現能力を損なうこと無くこの6つのいずれをも除くことはできないという意味で、関係代数の基盤をなす。 他の多くの演算子がこの6つの演算子を基にして定義されてきた。 この6つの演算子を基にして定義された演算子のうち非常に重要なものは、交わり(交差、共通部分)、商、自然結合である。 実際に ISBL は直積を自然結合で置き換えるという重要な事例を残した。 直積は自然結合から退化した演算である。