Relational algebra — the formal foundation of SQL and database query languages — is the algebra of tables: selection, projection, join, union, difference. Proving that a set of axioms is complete for relational algebra (every valid equation is derivable) has been a persistent challenge because the algebra combines set-theoretic operations with variable-binding operations in a way that resists standard algebraic methods.
The cylindric algebra approach provides an elegant proof technique. Cylindric algebras, developed by Tarski and collaborators, axiomatize the algebra of first-order logic including quantifier operations. Relational algebra is a fragment of cylindric algebra — every relational operation can be expressed using cylindric operations, and every cylindric operation on finite-dimensional structures can be expressed relationally.
Note (2026-11-09): I checked the abstract of Lastovicka's paper. The completeness it proves is that of relational algebra with respect to allowed formulas of first-order logic (every allowed formula has an equivalent relational expression), by an alternative proof through the embedding into cylindric algebra, together with an alternative algorithm that produces the relational expression. The essay describes a different notion, completeness of an axiomatization (every valid equation is derivable), and a proof that transfers Tarski's completeness theorem; the abstract says neither. Its stated motivation is generalisation to models handling incomplete or vague information, not the extensions to aggregation or recursion that the essay mentions.
The completeness proof works by embedding the relational algebra completeness question into cylindric algebra, where the completeness theorem is already established by Tarski's theory. The embedding preserves the equational structure: a relational algebra equation is valid if and only if its cylindric translation is valid, and the cylindric axioms derive the translation if and only if the relational axioms derive the original.
The technique has generalization potential. Any algebraic system that can be embedded into cylindric algebra inherits its completeness properties. This includes extensions of relational algebra with aggregation, recursion, or other database operations, provided the extensions preserve the cylindric structure.
Completeness for a fundamental algebraic system, proved by recognizing it as a fragment of a system where completeness was already known. The proof is a map, not a construction.