What does it mean to call a query language 'relationally complete', and which queries still fall outside that bar?

## The bar Codd set When Codd proposed the relational model he needed an objective way to judge query languages. His answer was **relational completeness**: a language qualifies if every query expressible in relational algebra can be expressed in it. Because algebra and safe tuple calculus are provably equivalent, the same benchmark can be stated in either formalism, and that equivalence is what is usually called Codd's theorem. The benchmark did real work historically. It gave a yes-or-no criterion for whether a language was a genuine relational query language rather than a record-at-a-time navigation interface, and it separated the user-facing declarative notation from the internal operator algebra that engines actually evaluate. ## Completeness is a floor The subtlety worth carrying into architecture discussions is that relational completeness is a *minimum*. It says a language reaches first-order expressive power over relations. It does not say a language can express everything a business wants to ask, and first-order power has hard, proven limits over finite structures. **No counting or aggregation.** First-order logic cannot express "how many" or "the sum of". Formulas can assert existence and can, with enough variables, distinguish specific small cardinalities, but there is no fixed formula for "the departments with more employees than the average". Aggregate functions and grouping are an extension bolted onto the relational core precisely because the core cannot do this. **No transitive closure.** This is the deepest limit. Given a relation of direct edges, no algebra or calculus expression returns all pairs connected by a path of *arbitrary* length. Each join adds exactly one hop, so an expression with a fixed number of joins answers only a fixed-depth question. Organisational ancestry, component explosion in a bill of materials, dependency graphs and social reachability are all outside first-order power. The impossibility is a genuine theorem about the expressive limits of first-order logic on finite structures, not a statement about anyone's implementation. **No ordering as data.** The relational model treats a relation as an unordered set, so notions like "the third row" or "the previous value in sequence" are not first-order relational concepts; they are added by explicit ordering and windowing extensions. ## What practical languages add, and what it costs Standard query languages went beyond relational completeness on purpose: aggregation with grouping, ordering, and recursive constructs that compute a fixpoint by iterating a query until nothing new is produced, which is exactly the mechanism that supplies transitive closure. Each extension buys expressiveness and gives up something the first-order core enjoyed: - **Rewriting freedom.** The optimiser's strongest identities, pushing selections down, reordering joins, eliminating redundant projections, live in the first-order core. Around aggregation and recursion, rewrites become conditional and fewer, so plan quality is more sensitive to how the query was written. - **Cost estimation.** Cardinality estimation for a fixpoint depends on how many iterations run and how fast the intermediate set grows, which the optimiser cannot know in advance. Recursive query plans are therefore the ones most likely to be badly costed. - **Termination and resource behaviour.** A first-order query over finite data always terminates with a bounded result. A recursive computation over cyclic data may not converge without explicit cycle handling, turning a modelling detail into an availability risk. ## Why this framing matters in design decisions The practical payoff is knowing when a requirement is outside the comfortable core, before it becomes a performance incident. If a feature asks for arbitrary-depth ancestry, permission inheritance through nested groups, or reachability over a relationship graph, then no amount of ordinary query tuning will make a fixed-join formulation correct: the query is not merely slow, it is answering a shallower question than was asked. The design choices at that point are the honest ones, to use a recursive construct with a depth bound and cycle protection, to maintain a materialised closure or a precomputed path encoding, or to move that specific workload onto an engine designed for traversal. Equally, knowing that aggregation sits outside the first-order core explains why heavy aggregate workloads are the ones that most often justify a different physical design, since the operators involved are not the ones the classic relational rewrite rules were built to reorganise. ## Answering well State the theorem, name completeness as a floor rather than a ceiling, give the two canonical gaps of aggregation and transitive closure with a concrete example each, then draw the architectural consequence: extensions are where optimiser guarantees weaken, so recursive and aggregate-heavy workloads deserve explicit design attention rather than being treated as ordinary queries.