Codd's theorem

By Codd's theorem [] there is a direct correspondence between expressions of the relational algebra and (domain independent) expressions of the relational calculus (i.e. formulas).

There are two kinds of relational calculus:

• The tuple calculus, in which the variables range over the tuples in the relations
• The domain calculus, in which the variables range over the attribute types

The domain calculus more closely resembles the predicate calculus of first-order logic []

For example:

• DUM corresponds to the truth constant ⊥ for "false"
• DEE corresponds to the truth constant ⊤ for "true"
• A relation literal corresponds to a formula which is a disjunction of conjunctions. For example the relation

  { {(x,1),(y,2)}, {(x,1),(y,3)}, {(x,2),(y,10)} }

  corresponds to the formula

  ((x=1)∧(y=2)) ∨ ((x=1)∧(y=3)) ∨ ((x=2)∧(y=10))

• The relvar name R corresponds to the atomic formula P(x1,...,xn) where P is the predicate symbol for R and x1,...,xn are variables corresponding to the attributes of R
• Let the algebra expressions R,S be union compatible and have attributes x1,...,xn, and correspond to the predicate expressions P and Q respectively. Then:
  • The algebra expression (R = S) corresponds to the formula ∀x1 ... ∀xn (P ↔ Q)
  • The algebra expression (R ⊆ S) corresponds to the formula ∀x1 ... ∀xn (P → Q)
  • The algebra expression (R JOIN S) corresponds to the formula (P ∧ Q)
  • The algebra expression (R UNION S) corresponds to the formula (P ∨ Q)
  • The algebra expression (R MINUS S) corresponds to the formula (P ∧ ¬Q)
  • The algebra expression PROJECT(R,attrib(R)\{x}) corresponds to the formula ∃x φ

The relational algebra is limited in the following ways:

• it doesn't support aggregations (counting tuples, or summing up values occurring in tuples)
• it doesn't allow for computing the transitive closure of a graph given by its binary edge relation

Nevertheless it is usual for an RDBMS to provide this capability, making it more powerful that Codd's definition of relationally complete