9 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
corresponds to the formula{ {(x,1),(y,2)}, {(x,1),(y,3)}, {(x,2),(y,10)} }((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