Relation Algebra

Origin. De Morgan, Peirce, and Schröder developed algebra of relations (1860s-1890s). Tarski axiomatized relation algebras (1941). Algebraic approach to binary relations. Equivalent to three-variable first-order logic. Foundation for database theory and program semantics.

Models. Algebra of binary relations. Relations: subsets of A × A. Operations: union, intersection, complement, composition, converse. Identity relation and empty relation. Expresses relational databases, programs as relations, graph properties.

Formalism.

Relation algebra: (R, ∪, ∩, ‾, ;, ˘, Id, ∅, U) where:

• (R, ∪, ∩, ‾, ∅, U) is Boolean algebra
• ; : R × R → R (composition)
• ˘ : R → R (converse)
• Id ∈ R (identity relation)

Axioms:

1. Boolean algebra axioms
2. (R ; S) ; T = R ; (S ; T) (composition associative)
3. R ; Id = R = Id ; R (identity)
4. (R ∪ S) ; T = (R ; T) ∪ (S ; T) (right distribution)
5. R˘˘ = R (double converse)
6. (R ; S)˘ = S˘ ; R˘ (converse of composition)
7. R˘ ; (R ; S)‾ ⊆ S‾ (Tarski/De Morgan axiom)

In axiom 7 the complement is taken of the composite R ; S, not of R and S separately. It is equivalent to the cycle law — (R ; S) ∩ T = ∅ iff (R˘ ; T) ∩ S = ∅ iff (T ; S˘) ∩ R = ∅ — which is what makes it the one axiom tying converse, composition and complement together, and hence the axiom the whole theory turns on.

Derived notions:

• Domain: dom(R) = Id ∩ (R ; U)
• Range: ran(R) = Id ∩ (U ; R)
• R is functional: R˘ ; R ⊆ Id
• R is total: Id ⊆ R ; R˘

Example operations:

• R ; S: composition (x relates to z if x R y and y S z)
• R˘: converse (x R˘ y iff y R x)
• R*: reflexive transitive closure (not first-order definable)

Symbols.

Metatheory. The equational theory of relation algebras is undecidable — Tarski's result, since the valid equations code first-order validity. Tarski and Givant, A Formalization of Set Theory Without Variables (1987), made the placement exact: the equational calculus of RA is equipollent with the three-variable fragment L³ of first-order logic with equality, and ZF can be presented as an equational theory over RA, set theory with no variables at all. That placement explains the boundary, since the two-variable fragment is decidable and NEXPTIME-complete (Grädel, Kolaitis, and Vardi, 1997) while the three-variable fragment is undecidable. Not every abstract relation algebra is an algebra of actual binary relations: Lyndon (1950) exhibited a finite non-representable one, and his sequel (1956) gave an infinite schema of conditions axiomatizing the representable class. Tarski (1955) proved RRA is a variety; Monk (1964) proved it is not finitely axiomatizable, and Andréka, Hodkinson, and Németi strengthened this to exclude axiomatization in finitely many variables. Hirsch and Hodkinson (2001) proved that representability of a finite relation algebra is undecidable.

Applies to. Database query languages. Program semantics (relations as specifications). Graph algorithms. Verification. Knowledge representation. Access control.

Limitations. Relation algebra reaches only three variables' worth of first-order logic, and the variable hierarchy is strict, so there are first-order properties of binary structures expressible with four variables and not with three — RA is properly weaker than full first-order logic even on binary relations. Only binary relations are in the signature; higher arities need cylindric or polyadic algebras. Reflexive transitive closure R* is not expressible, since it is not first-order definable at all, so iteration must be handled by Kleene algebra or dynamic logic instead. Nothing is gained computationally: the equational theory is undecidable, and even deciding whether a finite algebra is representable is undecidable. The abstract axioms are incomplete for the intended semantics — Lyndon's algebras satisfy them and represent nothing — and by Monk's theorem no finite equational repair exists.

© 2026 Lingenic LLC