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:

Boolean algebra axioms
(R ; S) ; T = R ; (S ; T) (composition associative)
R ; Id = R = Id ; R (identity)
(R ∪ S) ; T = (R ; T) ∪ (S ; T) (right distribution)
R˘˘ = R (double converse)
(R ; S)˘ = S˘ ; R˘ (converse of composition)
R˘ ; (R̄ ; S̄) ⊆ S̄ (Tarski/De Morgan axiom)

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.

Symbol	Unicode	Name	Meaning
;	—	Composition	Sequential combination
˘	U+02D8	Converse	Reverse relation
∪	U+222A	Union	Either relation
∩	U+2229	Intersection	Both relations
‾	U+0305	Complement	Negation
Id	—	Identity	Diagonal
U	—	Universal	Full relation

Metatheory. Relation algebra equational theory undecidable. Equivalent to 3-variable FOL (L³). Representable relation algebras: concrete relations. Not all abstract RAs are representable (Lyndon). Finite RA satisfiability undecidable.

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

Limitations. Undecidable in general. Transitive closure not definable. Only binary relations. Three-variable limitation for FOL embedding. Less expressive than full FOL.