また関係代数の演算子の正確な集合は、名前付けを行わない関係モデル(数学的な関係を採用している)を使うか、それとも名前付けを行う関係モデル(数学的な関係の名前付けによる一般化を採用している)を使うか、ということにも依存している。この項目の説明では、名前付けを行う関係モデルを使うことにする。名前付けを行う関係モデルは、コッドが提唱したものであり、一定の人々によりコッドの最も重要な革新的業績と考えられている。こうした人々による肯定的な評価は、コッドが自分の関係モデルから関係の属性の順序という概念を除外したことが大きな理由である。このモデルでは組(タプル)は、属性名の集合から属性値の集合を導出する部分関数である。コッドの関係代数が一階述語論理に関しては実際には完全ではないと留意しておくことは、重要である。仮に一階述語論理に関して完全であったならば、関係モデルをどのように実装するにせよ、コンピュータ上の克服できない困難に突き当たってしまうであろう。こうした困難を克服するためにコッドは、関係代数の演算対象を有限の関係のみに限定し、また否定(NOT)と選言(OR)を限定的にサポートすることを提唱した。コッドの関係代数は、実際にはホーン節で再帰と否定の無い一階述語論理のサブセットである。こうした限定に類することは、他の多くの論理に基づくコンピュータ言語においてもみられることである。コッドは、関係データベース言語の表現能力について関係完備という用語を定義した。関係完備とは、コッドが提唱した限定のもとで、一階述語論理に関して完全な言語であることを意味する。実際にコッドが提唱した限定は、コッドの関係代数をデータベースのさまざまな目的に適用することにおいて、不都合は無かった。関係代数は関係完備である。関係代数と同等もしくは同等以上の表現能力を持つ関係データベース言語は関係完備であるといえる。関係論理(関係計算)は、関係代数と同等の表現能力を持つため、関係完備である。なお関係論理には定義域関係論理と組関係論理がある。どのような代数であれ、一定の数の演算子は基本的(プリミティブ)であり、それ以外の演算子は、基本的な演算子のみをもって定義できるため、基本的ではない。