🔢 mathematics

Completeness of Relational Algebra via Cylindric Algebra

This paper presents an alternative algebraic proof of the completeness of relational algebra with respect to first-order logic formulas, leveraging its embedding into cylindric algebra to derive a new conversion algorithm and lay the groundwork for extending these results to models handling incomplete or vague information.

Original authors: Jan Laštovička

Published 2026-03-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jan Laštovička

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Translating Two Languages

Imagine you are a librarian trying to manage a massive library (a Database). You have two ways to ask for books:

The "Recipe" Language (Relational Algebra): This is like giving a step-by-step cooking recipe. "Take the 'Fiction' shelf, remove the 'Mystery' section, and stack the remaining books on the 'History' table." Computers love this because it's a clear set of instructions they can execute quickly.
The "Desire" Language (First-Order Logic): This is like describing what you want in a sentence. "I want a book that is fiction, but not mystery, and it must be about history." This is great for humans because it's flexible and expressive, but it can be vague or impossible for a computer to execute directly (e.g., "Give me everything that is not a book," which is an infinite list).

The Problem: Sometimes, your "Desire" sentence is too complex or weird for the computer to turn into a "Recipe." The paper tackles a specific group of "Desire" sentences called Allowed Formulas. These are special sentences that can be turned into recipes.

The Goal: The author, Jan Laštovicka, wants to prove two things:

Every "Allowed" sentence can be turned into a computer recipe.
He wants to show how to do it using a new, cleaner method.

The Secret Weapon: The "Shape-Shifting" Algebra

The author doesn't just translate sentence-to-recipe directly. Instead, he uses a middleman called Cylindric Algebra.

The Analogy: The Universal Translator
Imagine you are trying to translate a poem from English to Japanese. It's hard to do directly because the grammar is so different. So, you translate the English poem into a universal "Concept Language" first, and then translate that Concept Language into Japanese.

Relational Algebra (The Recipe) is like Japanese.
First-Order Logic (The Desire) is like English.
Cylindric Algebra is the Concept Language.

The author shows that both the Recipe and the Desire can be perfectly translated into this "Concept Language." Because they both fit into this same mathematical box, he can prove that they are equivalent. It's like proving two different keys open the same lock because they both fit into the same keyhole shape.

Why is this better than the old way?

The paper mentions an older proof (from 1991). The author says his new method is better for two reasons:

Handling Negation (The "Not" Problem):
- Old Way: It was like trying to describe a "non-red" apple by listing every color that isn't red. It was messy.
- New Way: The author treats "Not" as a full, legitimate ingredient. He can say "Not Red" directly without breaking it down into a million other colors. This makes the translation rules much clearer.
Handling Equality (The "Same Thing" Problem):
- Old Way: If you said "The book on shelf A is the same as the book on shelf B," the old method forced you to rewrite the sentence to remove the "same as" part before processing.
- New Way: The new method lets you keep the "same as" part right where it is. It's like letting a chef say "Use the same knife for the onion and the garlic" without forcing them to rename the knife first.

The Algorithm: How to Turn a Sentence into a Recipe

The paper presents a two-step algorithm to turn a complex "Allowed" sentence into a database recipe.

Step 1: Normalization (The "Tidy-Up" Phase)
Imagine you have a messy sentence: "Find me a book that is in the Fiction section, but not in the Mystery section, and it must be the same book as the one on the History shelf."

The algorithm first normalizes this. It rearranges the sentence into a standard, tidy format. It ensures that:

Every variable (like "book") is clearly defined.
The "Not" parts are handled cleanly.
The "Same as" parts are aligned.

Think of this like a chef prepping ingredients before cooking. You chop the onions, peel the carrots, and measure the spices before you turn on the stove. This "prepped" sentence is now guaranteed to be convertible.

Step 2: Translation (The "Cooking" Phase)
Once the sentence is "prepped" (normalized), the translation is straightforward. The algorithm has a simple rulebook:

"And" becomes a Join (combining lists).
"Or" becomes a Union (stacking lists).
"Not" becomes a Difference (subtracting lists).
"Same as" becomes a Selection (filtering the list).

Because the sentence was "prepped" in Step 1, Step 2 is just a mechanical process of swapping words for database commands.

Why Should We Care? (The "Incomplete" Future)

The author mentions a big motivation: Incomplete Information.

Imagine a database where some data is missing or fuzzy. Maybe a book's author is listed as "Unknown" or "Maybe John." Standard logic struggles with this.

The author's method is special because it relies on Cylindric Algebra, which is a very flexible mathematical structure. He argues that if we can prove things work in this algebraic "Concept Language," we can easily adapt the proof to handle messy, incomplete, or vague data in the future.

It's like building a bridge. The old bridge (the 1991 proof) was made of wood and only worked for dry land. This new bridge is made of steel (Cylindric Algebra), so the author believes we can easily extend it to cross swamps (incomplete data) or rivers (vague data) later on.

Summary

The Problem: Computers need clear recipes (Relational Algebra) to run queries, but humans speak in complex sentences (Logic). Not all sentences can be turned into recipes.
The Solution: The author proves that a specific, useful group of sentences ("Allowed Formulas") can always be turned into recipes.
The Method: He uses a mathematical "middleman" (Cylindric Algebra) to prove this connection, which makes the proof cleaner and easier to understand than previous methods.
The Benefit: This new method handles "Not" and "Same As" more naturally and provides a foundation for future databases that deal with missing or fuzzy information.

In short, the paper gives us a better, more robust blueprint for translating human thoughts into computer actions, ensuring that our queries are always executable.

1. Problem Statement

The paper addresses the completeness of Relational Algebra (RA) with respect to First-Order Logic (FOL). Specifically, it seeks to prove that every "allowed" formula in FOL has a semantically equivalent relational expression, and conversely, that every relational expression corresponds to an allowed formula.

Context: While RA is a procedural language for databases, FOL is a declarative language. A fundamental challenge is translating declarative queries (FOL formulas) into executable procedural queries (RA expressions).
Limitation: Not all FOL formulas can be translated into RA. For example, formulas involving unrestricted negation (e.g., $\neg r(x)$ ) or unrestricted universal quantification often lack equivalent RA expressions because RA operates over finite domains and cannot express "everything else" without a bounded active domain.
Target: The paper focuses on allowed formulas (a subset of FOL defined by structural constraints ensuring domain independence) and aims to provide a constructive proof of completeness and an algorithm for translation.
Motivation: The author aims to establish a proof technique that is algebraic and generalizable to relational models handling incomplete or vague information (e.g., null values or similarity-based domains), where standard logical proofs may fail.

2. Methodology

The core methodological innovation is the use of Cylindric Algebras (CA) as an intermediate algebraic structure to bridge FOL and RA.

Cylindric Algebra Embedding: The paper leverages the known embedding of Relational Algebra into Cylindric Algebras (established by Imieliński and Lipski). In this framework:
- RA operations (union, difference, join, projection, selection, renaming) map directly to CA operations (Boolean union/difference, intersection, cylindrification, diagonal elements).
- FOL semantics are interpreted as sets of valuations within a CA structure.
Algebraic Proof Strategy: Instead of relying solely on syntactic transformations of formulas, the proof is conducted within the algebraic structure of the Cylindric Algebra. This allows the author to treat negation as a full logical connective and handle equality naturally without pre-processing elimination.
Normalization Algorithm: The paper introduces a two-step algorithm to convert an allowed formula into a relational expression:
1. Normalization: Transforming an arbitrary allowed formula into a normalized formula.
2. Translation: Converting the normalized formula directly into a relational expression using a set of recursive rules.

3. Key Concepts and Definitions

Allowed Formulas: A syntactic subset of FOL where free variables are "generated" by the formula structure, ensuring that the formula's truth value depends only on the active domain of the database. This ensures domain independence.
Equality and Co-equality ($eq$ and $coeq$): The paper defines equivalence relations on variables for any formula $\phi$ $ϕ$ .
- $eq(\phi)$ : Variables that must be equal for the formula to hold.
- $coeq(\phi)$ : Variables that must be distinct (or related in a specific way) for the formula to hold.
- These are used to track variable dependencies during normalization.
Generators and Cogenerators ($gen$ and $cogen$):
- $gen(\phi)$ : A formula representing the "positive" part of $\phi$ that restricts the active domain.
- $cogen(\phi)$ : A formula representing the "negative" part.
- These mappings are crucial for the normalization process, ensuring that the normalized formula stays within the bounds of the active domain.
Normalized Formulas: A specific syntactic form of formulas defined inductively. They are structured such that they can be directly mapped to RA operations (e.g., conjunctions map to joins, negations map to set differences).

4. Key Contributions

Alternative Proof of Completeness:
The paper provides a new proof that every allowed formula is semantically equivalent to a relational expression. Unlike previous proofs (e.g., VGT91), this proof is carried out entirely within the Cylindric Algebra framework. This algebraic approach is highlighted as more robust for generalization to non-standard database models (e.g., those with incomplete information).
Handling Negation and Equality:
The approach treats negation as a primary connective rather than eliminating it early. It also permits equality ( $\approx$ ) in formulas without requiring prior elimination, simplifying the translation process.
Normalization Algorithm:
The author defines a rigorous algorithm to transform an allowed formula $\phi$ into a normalized formula $norm(\phi, gen(\phi))$ .
- The algorithm recursively processes the formula structure.
- It uses "alignment" to ensure free variables match across sub-formulas.
- It utilizes the $gen$ and $cogen$ mappings to restrict the domain appropriately.
Constructive Translation:
Once a formula is normalized, the paper provides a direct, rule-based translation to a relational expression (e.g., $expr(\phi)$ ). This makes the completeness proof constructive, meaning it yields an executable algorithm.

5. Results

Theorem 6.8 (Completeness): Every allowed formula is semantically equivalent to its normalization.
Theorem 6.9 (Domain Independence): All allowed formulas are domain independent. Consequently, they are semantically equivalent to relational expressions.
Algorithm Correctness: The paper proves that the normalization process preserves the semantic value of the original formula relative to the generator (the active domain constraint).
Example Application: The paper demonstrates the algorithm on Relational Division, a complex query often difficult to express in standard RA. The algorithm successfully derives the standard RA expression for division: $\pi_{x}(s) - \pi_{x}((r \bowtie \pi_{x}(s)) - s)$ .

6. Significance and Future Work

Generalizability: The primary significance of this work is the algebraic nature of the proof. Because Cylindric Algebras can be generalized to accommodate incomplete information (e.g., nulls) or vague information (e.g., similarity relations), this proof technique suggests a pathway to establishing completeness for these advanced relational models.
Practical Utility: The normalization algorithm offers a potential optimization for query compilers. By normalizing formulas first, the translation to RA becomes more systematic and potentially more efficient.
Theoretical Clarity: The paper clarifies the structural conditions required for a formula to be "allowed" and provides a clear algebraic characterization of why these formulas are translatable to RA.

In summary, Laštovicka's work bridges the gap between logical query languages and procedural database execution using the powerful machinery of Cylindric Algebras, offering a robust, generalizable proof of completeness and a concrete algorithm for query translation.