Expressive Power of Relational Languages

Every computational formalism has boundaries—problems it cannot solve, questions it cannot answer. Relational algebra and calculus, despite their elegance and power, are no exception. Understanding these limitations is not a sign of weakness in the relational model; rather, it reveals the precise tradeoffs the model makes: what it gains in decidability, optimization, and simplicity, and what it sacrifices in raw expressiveness.

This page explores the fundamental limitations of the relational model. We'll examine specific types of queries that cannot be expressed, understand why these limitations exist, and see how recognizing them informs both database design and the development of extended query languages.

To understand relational limitations, we must first understand what relational algebra and calculus fundamentally are: they are equivalent to first-order logic over finite structures (with equality and a fixed set of relation names).

First-order logic (FOL) is characterized by:

• Variables that range over individual elements (domain values)
• Predicates that test relationships between elements
• Connectives (∧, ∨, ¬, →, ↔)
• Quantifiers (∃, ∀) that range over individuals

What FOL lacks:

• Quantification over predicates themselves (that's second-order logic)
• Quantification over sets of elements (also second-order)
• Fixed-point operators for defining recursive structures
• Any form of counting or arithmetic

Why this matters:

First-order logic is remarkably expressive for many purposes, but it has a fundamental weakness: it cannot express properties that require unbounded iteration or counting. Consider:

• 'Is the graph connected?' — Requires checking paths of arbitrary length
• 'How many employees are there?' — Requires counting
• 'What is the total salary?' — Requires arithmetic aggregation

These queries are not first-order definable over finite structures, and therefore cannot be expressed in relational algebra or calculus.

The mathematical foundation:

The study of what can and cannot be expressed in FOL over finite structures is the domain of finite model theory. Key results include:

• Ehrenfeucht-Fraïssé games — A technique for proving queries are not FOL-definable
• 0-1 laws — Asymptotic results about FOL expressibility
• Descriptive complexity — Connections between logic and computational complexity

While we won't dive deep into these mathematical tools, knowing they exist explains why limitations are precisely characterizable rather than merely observed.

The most famous limitation of relational algebra is its inability to compute transitive closure—the reachability relation in a graph. This limitation has profound practical implications for hierarchical and network data.

Why is transitive closure inexpressible?

Reachability can require arbitrarily many steps:

A → B → C → D → ... → Z

To detect that Z is reachable from A, we need to follow an unbounded chain. Relational algebra expressions have fixed depth—each expression specifies a finite number of operations. No fixed-depth expression can handle arbitrary-length paths.

A concrete example:

Consider the ParentOf(parent, child) relation:

ParentOf(Alice, Bob)
ParentOf(Bob, Carol)
ParentOf(Carol, David)

Query: Find all ancestor-descendant pairs.

'Ancestors' includes grandparents, great-grandparents, etc.—chains of arbitrary length.

We can express fixed-length chains:

-- Parents (1 step)
π_{parent, child}(ParentOf)

-- Grandparents (2 steps)
π_{P1.parent, P2.child}(ParentOf P1 ⋈_{P1.child = P2.parent} ParentOf P2)

-- Great-grandparents (3 steps)
... (more joins)

But for arbitrary depth? Impossible in pure relational algebra.

Practical impact:

• Organizational hierarchies (who reports to whom, transitively)
• Bill of materials (what parts compose a product, recursively)
• Social networks (who can reach whom through connections)
• Transportation networks (which cities are connected)

All these require transitive closure and exceed basic relational expressiveness.

Relational algebra operates on sets of tuples. It can filter, combine, and transform tuples, but it cannot count them, sum their values, or compute any aggregate function over a set.

Why counting is inexpressible:

First-order logic quantifiers (∃, ∀) can express:

• 'There exists an x such that...'
• 'For all x...'

But they cannot express:

• 'There are exactly 5 x's such that...'
• 'There are more x's satisfying φ than ψ'

The mathematical proof:

This is a famous result in finite model theory. Using Ehrenfeucht-Fraïssé games, one can prove that no first-order sentence can distinguish between a set of 100 elements and a set of 101 elements. Therefore, counting is not first-order definable.

Practical queries that fail:

-- These require aggregation (not in basic RA)
SELECT department, COUNT(*) FROM Employee GROUP BY department;
SELECT AVG(salary) FROM Employee;
SELECT MAX(order_total) FROM Orders;
SELECT department, SUM(salary) FROM Employee GROUP BY department;

What CAN we express?

Relational algebra can express:

• 'There exists an employee' — ∃
• 'All employees have salary > 0' — ∀
• 'There are at least k employees' (for fixed k) — ∃x₁∃x₂...∃xₖ (all distinct)
• 'There are at most k employees' (for fixed k) — Negation of 'at least k+1'
• 'There are exactly k employees' (for fixed k) — Combination of above

But k must be known at query compile time, not computed from data.

Pure relational algebra treats domain values as abstract, uninterpreted elements. It can test equality (x = y) and, with extensions, inequality (x < y), but it cannot compute new values through arithmetic operations.

What pure RA cannot express:

-- Compute a derived value
SELECT name, salary * 1.1 AS raised_salary FROM Employee;

-- Arithmetic in conditions (beyond comparisons)
SELECT * FROM Orders WHERE quantity * price > 1000;

-- Date arithmetic
SELECT * FROM Subscriptions WHERE end_date - start_date > 30;

-- String concatenation
SELECT first_name || ' ' || last_name AS full_name FROM Person;

The theoretical reason:

Pure first-order logic doesn't include arithmetic. The domain is just a set of values with equality. While we can add comparison predicates (<, ≤, >, ≥) to the logic, these are interpreted predicates—they test properties but don't compute new values.

The expressibility spectrum:

Practical note:

SQL and all practical query languages include arithmetic. When we speak of 'relational algebra' in implementation, we mean an extended version with:

• Arithmetic expressions in selection conditions
• Computed attributes in projection (extended projection)
• Type-specific operations (date arithmetic, string functions)

Relation algebra operates on sets—unordered collections where tuple position has no meaning. This fundamentally conflicts with ordering and ranking operations.

Why ordering is outside the model:

Relational algebra is defined over relations, which are sets of tuples. In set theory:

• {1, 2, 3} = {3, 1, 2} = {2, 3, 1}
• Sets have no inherent order

Ordering is a property of sequences (lists), not sets. To return a 'top-k' result, we would need:

1. A comparison relation (e.g., salary ordering)
2. A way to limit output size
3. A way to produce an ordered sequence, not a set

RA can do (1) partially via selection, but (2) and (3) are outside its scope.

Related inexpressible queries:

-- Top-k queries
SELECT * FROM Employee ORDER BY salary DESC LIMIT 10;

-- Ranking
SELECT name, RANK() OVER (ORDER BY salary DESC) FROM Employee;

-- Percentiles
SELECT * FROM Employee WHERE salary > PERCENTILE_CONT(0.9) ...;

-- Running aggregates
SELECT date, SUM(sales) OVER (ORDER BY date) FROM DailySales;

Theoretical vs. practical perspective:

In the relational model, ORDER BY is not a relational operator—it produces an ordered list, not a relation. The result of ORDER BY is outside the relational model entirely.

In practice, SQL includes ORDER BY as a presentation operation. The optimizer knows it doesn't affect relational semantics, so it can be applied after all relational operations complete.

While relational algebra can test string equality, it cannot perform string manipulation or pattern matching beyond what's achievable through element-wise comparison.

Inexpressible string operations:

-- Substring matching
SELECT * FROM Products WHERE name LIKE '%laptop%';

-- Regular expression matching
SELECT * FROM LogEntries WHERE message ~ 'error.*fatal';

-- String functions
SELECT UPPER(name), LENGTH(description) FROM Products;

-- Full-text search
SELECT * FROM Documents WHERE body @@ 'database & optimization';

The theoretical reason:

In pure relational algebra:

• String values are atomic, unstructured elements
• We can test if two strings are equal or (with ordering) lexicographically ordered
• We cannot 'see inside' a string to examine substrings, characters, or patterns

The LIKE predicate:

SQL's LIKE operator (with % and _ wildcards) requires an extended predicate not in basic FOL. It's testing a property (pattern matching) that involves examining the internal structure of string values.

Regular expressions:

Even more powerful, regular expressions require finite automata to evaluate. While regular languages and FOL are incomparable in general, pattern matching within strings is definitely outside standard relational operators.

Practical approach:

SQL systems implement string operations as built-in functions:

• These are extensions to the relational model
• They're evaluated during tuple processing
• They enhance expressiveness beyond pure RA

The pure relational model assumes all data is known and present. Null values—representing missing, unknown, or inapplicable information—introduce complexities that the basic model doesn't naturally handle.

The null value complications:

1. Three-valued logic:

   • TRUE, FALSE, UNKNOWN
   • NULL = NULL is UNKNOWN, not TRUE
   • Logical operations: TRUE ∧ UNKNOWN = UNKNOWN

2. Aggregation ambiguity:

   • What is SUM of {10, NULL, 20}? (Most systems: 30, ignoring NULL)
   • What is AVG? (30/2 = 15, or 30/3 = 10?)

3. Join semantics:

   • Should NULL join with NULL? (Usually no)
   • Outer joins introduce NULLs for non-matching tuples

Why this exceeds the pure model:

Pure relational algebra assumes:

• Every tuple has a value for every attribute
• Equality tests have definite outcomes (TRUE or FALSE)
• All operations are total (defined for all inputs)

Nulls violate all three assumptions.

SQL's approach:

SQL incorporates nulls and three-valued logic:

• IS NULL / IS NOT NULL predicates
• COALESCE and NULLIF functions
• Special handling in aggregates
• Outer join operators that can produce nulls

These are extensions beyond the pure relational model, though they're so fundamental to SQL that they feel core to the 'relational' approach.

The limitations we've examined aren't accidents or oversights—they're the result of deliberate (or at least inevitable) design tradeoffs. Understanding these tradeoffs illuminates why the relational model succeeded despite its limitations.

The expressiveness-tractability tradeoff:

In computational logic, a general principle holds:

More expressive logics are harder to evaluate and less amenable to optimization.

Relational algebra (equivalent to FOL) sits at a sweet spot:

• Powerful enough to express most naturally occurring queries
• Weak enough to ensure polynomial-time evaluation
• Structured enough to enable algebraic optimization

Adding transitive closure crosses a complexity boundary. Adding unrestricted recursion makes evaluation undecidable. Adding aggregation and arithmetic changes the complexity characteristics.

Historical vindication:

The success of relational databases over 50 years validates these tradeoffs. Systems that tried to be 'more expressive' (like early object databases) often lost the optimization and simplicity benefits. The relational model's limitations are features as much as bugs—they define a coherent, implementable, optimizable system.

We've explored the fundamental limitations of relational algebra and calculus—the boundaries of what the pure relational model can express.

What's next:

Recognizing limitations naturally leads to the question: How do we extend the relational model to overcome them? Page 5 examines the extensions developed over decades—from SQL's aggregation and grouping to recursive CTEs, window functions, and beyond. We'll see how practical query languages transcend pure relational expressiveness while preserving (as much as possible) the benefits of the relational foundation.