Extending Relational Algebra for Complex Query Optimization

26 concepts17 papers1 proposal

Relational algebra owes its enduring success to a simple property: it is a formal mathematical system. Because operations like selection ($\sigma$), projection ($\pi$), and join ($\bowtie$) possess well-defined algebraic properties like commutativity and associativity, a database optimizer can systematically rearrange a query plan to find the most efficient execution path.

However, modern applications frequently force databases to handle workloads that go far beyond standard tables. Whether dealing with machine learning inference, XML hierarchies, streaming graphs, or messy data cleaning pipelines, developers often resort to external scripts or opaque user-defined functions (UDFs). To a traditional query optimizer, these external steps are black boxes; it cannot see inside them, let alone optimize across them.

The core insight of this research direction is that we can optimize complex, non-relational workloads by formalizing their semantics as first-class algebraic primitives. By integrating domain-specific operations directly into a unified algebraic framework, we can apply formal rewrite rules to systematically eliminate redundancies, push constraints early, and transform slow procedural loops into high-performance bulk operations.

First-Class Primitives and Cross-Domain Optimization

Why does elevating an operation to a first-class algebraic primitive matter? When an operation is treated as an opaque post-processing step, the database engine must materialize and process entire datasets before passing them to the external tool.

Consider data fusion—the process of deduplicating and merging messy records. As Wang-Chiew Tan notes in Letter from the Special Issue Editors, data cleaning is traditionally handled by ad-hoc external scripts. However, Jens Bleiholder et al. demonstrate in Eliminating NULLs with Subsumption and Complementation that formalizing data fusion via algebraic operators like subsumption and complementation allows the query optimizer to reorder operations. Instead of cleaning the entire dataset first, the engine can push standard relational filters and joins below the fusion step, drastically reducing the volume of data that needs to be merged.

This principle of cross-domain optimization becomes even more powerful when applied to machine learning and advanced analytics:

  • Machine Learning Inference: In Extending Relational Query Processing with ML Inference, Konstantinos Karanasos et al. introduce a unified intermediate representation that blends relational and linear algebra. This visibility enables the engine to use standard SQL query predicates to prune branches of an ML decision tree, while zero-weight features in the ML model can trigger the removal of unnecessary database column projections.
  • Hypothetical Analytics: Andrey Balmin et al. show in Hypothetical Queries in an OLAP Environment that embedding arithmetic operations directly into relational algebra allows the optimizer to treat calculations as first-class entities. This enables the system to execute complex "what-if" simulations directly within the standard query pipeline rather than as a separate post-processing phase.
  • Schema Restructuring: In On Efficiently Implementing SchemaSQL on an SQL Database System, Fereidoon Sadri et al. prove that integrating data restructuring operators (like splitting or unfolding) into a formal logical algebra allows standard selections to be pushed inside the restructuring phase, filtering out irrelevant records before expensive structural transformations occur.

Pushing Constraints and Filters Early

The most fundamental optimization in relational databases is pushing selection filters as close to the data source as possible to minimize intermediate data sizes. By formalizing non-relational domains algebraically, this technique can be applied to highly diverse paradigms.

In an early foundational work, Peter M. D. Gray et al. in Manipulating Descriptions of Programs for Database Access used formal rewrite rules to reorder logic programming operations, demonstrating that moving selection filters earlier prevents downstream combinatorial explosions.

Decades later, the same algebraic intuition solves modern streaming and graph challenges. For instance, Anil Pacaci et al. develop a streaming graph algebra in Evaluating Complex Queries on Streaming Graphs, showing that systematic transformation rules like predicate push-down significantly reduce latency and increase throughput when detecting complex patterns in real-time graph streams.

Opaque Pipeline (Unoptimized):
[Data Load] ──> [Complex Operation / Graph Match] ──> [Filter Predicate] (Processes everything)

Algebraic Pipeline (Optimized):
[Data Load] ──> [Filter Predicate] ──> [Complex Operation / Graph Match] (Processes minimal data)

This structural refinement appears across several other domains:

Loop Lifting: Turning Iterations into Bulk Operations

One of the most severe performance bottlenecks in declarative languages (like XQuery or XPath) is the reliance on nested loops or procedural-style iterations to navigate hierarchical data. Naive execution engines evaluate these loops row-by-row or node-by-node, resulting in poor scalability and quadratic or exponential time complexity.

The algebraic solution to this problem is a technique known as loop lifting. Instead of executing individual lookups sequentially, loop lifting transforms nested iterative constructs into bulk-oriented relational operations (such as joins).

Procedural Iteration (Slow):
for $x in doc("users.xml")
  for $y in doc("orders.xml") where $x/id = $y/userId
    return <result>{$x, $y}</result>  -- Evaluated item-by-item

Loop-Lifted Relational Plan (Fast):
UsersTable ⋈_{id=userId} OrdersTable  -- Evaluated as a single bulk join

In Pathfinder: XQuery - The Relational Way, Magdalena Bałazińska et al. demonstrate how XQuery's core iterative constructs, such as FLWOR clauses, can be mapped entirely to relational algebra. By lifting these loops into set-oriented operations, the underlying relational engine can process data in bulk, achieving massive performance gains over traditional XML databases.

The authors extend this concept to multi-dimensional text and linguistic annotations in Representing and Querying Multi-dimensional Markup for Question Answering. Here, Wouter Alink et al. show that loop lifting allows a system to process sets of overlapping document regions simultaneously, maintaining linear computational complexity even across gigabytes of text.

Similarly, Balder ten Cate et al. prove in Axiomatizing the Logical Core of XPath 2.0 that using algebraic axioms to rewrite nested loops into linear path expressions can speed up query execution by up to 1,000 times, leveraging the highly mature optimization strategies that relational engines already possess for path navigation.

Partial Evaluation and Semantic Pre-calculation

Finally, algebraic optimization can happen even before a query plan is fully constructed, by simplifying complex compositional expressions at the semantic level.

In A General Computational Treatment of Comparatives for Natural Language Question Answering, Bruce W. Ballard explores how natural language interfaces handle highly complex, nested comparative phrases (e.g., "at least 20 inches more than twice as long as..."). The author demonstrates that by performing partial evaluation of these algebraic expressions within the semantic parser, nested constants and static mathematical expressions can be pre-calculated and collapsed into simple constants before being compiled into a database query. This pre-execution simplification removes significant computational overhead, ensuring that the backend database engine only receives clean, fully evaluated predicates.

Key Foundational Work

A General Computational Treatment of Comparatives for Natural Language Question Answering (1988) — contributed 2 concept elements to this direction.
Manipulating Descriptions of Programs for Database Access (1983) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_algebraic_query_optimization_f73ba1ca,
  title = {algebraic query optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algebraic-query-optimization/rdr_f73ba1cae5f642278812fb700351655e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_algebraic_query_optimization_f73ba1ca_v1,
  title = {algebraic query optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algebraic-query-optimization/rdr_f73ba1cae5f642278812fb700351655e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake