Expressive Power of Relational Languages

When Edgar F. Codd invented the relational model in 1970, he didn't just propose a new way to organize data—he established a mathematical foundation for data manipulation that would define database systems for the next fifty years and beyond. Central to this achievement was the concept of relational completeness: a rigorous, formal criterion that determines whether a query language possesses sufficient expressive power to be considered a legitimate relational query language.

Relational completeness isn't merely an academic curiosity. It serves as the gold standard benchmark that every database query language—from SQL to modern NoSQL query interfaces—must either meet or explicitly acknowledge falling short of. Understanding relational completeness is understanding the very essence of what it means to query relational data.

Before we can appreciate relational completeness, we must understand the problem it solves. In the early days of database development, each database system offered its own proprietary query language with unique syntax, semantics, and capabilities. This created a chaotic landscape where:

• Portability was impossible — Applications written for one database couldn't work with another
• Comparison was subjective — There was no objective way to determine if one query language was 'better' than another
• Theoretical analysis was blocked — Without a formal foundation, proving properties about query languages was impractical
• Education was fragmented — Every system required learning an entirely new paradigm

Codd recognized that the relational model needed a reference standard—a mathematically precise definition of the minimum capabilities any relational query language must possess. This standard would serve as both a theoretical foundation and a practical benchmark.

Why a minimum standard matters:

A minimum standard is distinct from specifying all possible features. Relational completeness defines the floor, not the ceiling. A language may exceed relational completeness (and most practical languages do, with features like aggregation, sorting, and recursion), but it must not fall below this baseline while claiming to be a relational query language.

This distinction is crucial:

By establishing a clear baseline, Codd enabled:

1. Objective language comparison — Any language can be evaluated against the standard
2. Theoretical analysis — Properties provable for the standard apply to all complete languages
3. Implementation guidance — Database designers know what they must support
4. Query optimization — Equivalent expressions in complete languages can be transformed

With the need established, we can now examine the precise definition. Relational completeness is defined relative to a reference language—specifically, the relational algebra as defined by Codd.

This definition has several important implications:

1. The reference is relational algebra, not calculus

While relational calculus (both TRC and DRC) is equivalent in expressive power to relational algebra (as we'll prove in Page 3), Codd chose algebra as the reference because:

• It provides explicit algorithms for evaluation
• Its operations correspond directly to implementation techniques
• It serves as an intermediate representation for query optimization

2. Equivalence is semantic, not syntactic

Two queries are equivalent if they produce the same result for all possible database instances. The syntax can differ dramatically:

-- Relational Algebra
π_{name}(σ_{salary > 50000}(Employee))

-- SQL (also complete)
SELECT name FROM Employee WHERE salary > 50000

-- TRC (also complete)
{ t.name | ∃t ∈ Employee (t.salary > 50000) }

All three are equivalent despite radically different syntax.

3. The definition is about expressibility, not efficiency

A language is complete if the query can be expressed, regardless of how efficiently it executes. A complete language might have a concise query that runs in exponential time. Completeness says nothing about performance—that's the domain of query optimization and physical design.

These five operations form a minimal complete set—they are sufficient to express any query that relational algebra can express. Other operations like intersection (∩), join (⋈), and division (÷) are convenient but derivable:

-- Intersection is derivable from difference
R ∩ S = R − (R − S)

-- Natural join is derivable from selection and product
R ⋈ S = σ_{join-condition}(R × S)

-- Division is derivable from the others (complex but possible)
R ÷ S = π_{R-S}(R) − π_{R-S}((π_{R-S}(R) × S) − R)

A language must be able to express queries equivalent to any combination of the five core operations to be relationally complete. The derived operations are optional conveniences.

Given the formal definition, how do we actually determine if a query language is relationally complete? There are two principal approaches:

Approach 1: Direct Reduction

Show that each of the five fundamental relational algebra operations can be expressed in the candidate language. If all five are expressible, the language is complete.

Approach 2: Equivalence Proof

Prove that the candidate language is equivalent to a language already known to be complete (like TRC or DRC). This leverages established results rather than re-proving from scratch.

SQL's ability to express all five operations—plus many extensions—makes it unambiguously relationally complete. But completeness testing becomes more interesting for languages that claim to be relational but have unusual syntax or paradigms.

Example: Query-by-Example (QBE)

QBE, developed at IBM in the 1970s, uses a visual, table-based interface rather than textual syntax. To prove QBE's completeness:

1. Show that QBE can express selection (via example elements with conditions)
2. Show that QBE can express projection (via marking columns to output)
3. Show that QBE can express union (via multiple example tables)
4. Show that QBE can express difference (via negation patterns)
5. Show that QBE can express Cartesian product (via linking example tables)

Each mapping must be formally verified to ensure semantic equivalence, not just superficial similarity.

There's an important nuance in the definition of relational completeness that often goes unexplained: completeness is defined only over safe queries.

Recall that relational calculus can express unsafe queries—queries that produce infinite or domain-dependent results. For example:

{ t | ¬(t ∈ Employee) }

This query asks for 'all tuples not in Employee'—an infinite set that depends on what domain values exist. Such queries are:

• Impossible to compute (infinite results)
• Domain-dependent (results change based on unstated assumptions)
• Meaningless in practice (what would you do with all non-employees?)

Relational algebra, by contrast, can only produce finite results (closed over finite relations). This asymmetry affects the completeness definition.

This refinement matters because:

1. It makes the comparison fair

Asking a language to express infinite-result queries would be an impossible standard. By restricting to safe queries, we compare what languages can realistically compute.

2. It explains SQL's design choices

SQL enforces safety structurally. The FROM clause binds variables to finite relations, ensuring that all free variables range over finite domains. This isn't a limitation—it's a deliberate choice to match the algebraic model.

3. It clarifies the equivalence proofs

When proving that TRC equals relational algebra, we prove equivalence for safe TRC queries only. The proof doesn't claim that algebra can express unsafe calculus queries (it can't), but that doesn't affect completeness because unsafe queries are excluded from the standard.

Safety and Completeness Summary:

We've established that relational completeness is defined relative to relational algebra. But why did Codd choose algebra rather than, say, first-order logic or Turing machines? The choice was deliberate and reflects deep insights about database systems.

Contrast with alternatives:

Why not first-order logic (FOL)? FOL is a natural fit for expressing queries (it's essentially what TRC/DRC are), but:

• FOL allows unsafe queries with infinite results
• FOL's procedural interpretation is less direct
• FOL validity and satisfiability are undecidable in general

By using algebra rather than raw logic, Codd sidestepped these issues while preserving all the useful expressiveness.

Why not Turing machines? Turing machines can compute anything computable, but:

• Most Turing-computable queries are irrelevant for databases
• There's no guaranteed termination
• The model doesn't exploit the structure of relational data

Turing completeness is far too powerful—it would make languages incomparable (all would be 'complete') and optimization impossible.

The algebraic benchmark is a design masterstroke: powerful enough to express all natural relational queries, weak enough to guarantee computability and enable optimization.

Relational completeness isn't merely a theoretical property—it has profound practical implications for database users, application developers, and system designers.

Case Study: ORM Query Builders

Modern object-relational mappers (ORMs) like Hibernate, Entity Framework, and Django ORM expose query building interfaces in programming languages. These interfaces must be evaluated for completeness:

• Hibernate Criteria API: Relationally complete—supports all five operations via its fluent interface
• LINQ (Language Integrated Query): Relationally complete—directly maps to relational operations
• Django ORM QuerySet: Relationally complete for single-database queries—supports filter, exclude, union, difference

When an ORM is not complete, developers hit walls:

'I can't express this anti-join in the ORM; I have to drop to raw SQL.'

This is the practical impact of missing relational completeness—the language forces workarounds.

Case Study: GraphQL

GraphQL is not relationally complete by design:

• No equivalent to set difference (no 'NOT IN' or anti-joins at the query level)
• No arbitrary Cartesian products
• Limited to following schema-defined edges

This isn't a bug—GraphQL trades completeness for a simpler, more predictable query model. But it means some relational queries simply cannot be expressed in GraphQL without server-side resolvers implementing the logic.

Several misconceptions about relational completeness persist even among database professionals. Addressing these clarifies the concept and its proper use.

We've established a comprehensive understanding of relational completeness—the foundational concept that defines the expressive power of relational query languages.

What's next:

With relational completeness understood, we turn to one of the most elegant results in database theory: Codd's Theorem. This theorem proves that relational algebra and relational calculus—despite their radically different paradigms (procedural vs. declarative)—are expressively equivalent. The theorem is both intellectually beautiful and practically essential, as it underlies the translation from SQL (calculus-like) to execution plans (algebra-like) that every modern database performs.