Bridging the Expressivity Gap in Database Queries

95 concepts92 papers3 proposals

In database theory, the Conjunctive Query (CQ)—essentially the "Select-Project-Join" block of SQL—has long been the gold standard for balancing utility and efficiency. Because CQs are well-behaved, we can often determine if a solution exists or rewrite them into simpler forms with relative ease. However, real-world data analysis rarely stays within these boundaries. Modern applications demand negation, disjunction, recursion, and complex arithmetic, yet these features often break the theoretical guarantees we rely on for performance and correctness.

Recent research focuses on bridging this "expressivity gap," identifying exactly how much logical complexity we can add to a query language before the underlying problems of estimation, optimization, and answering become intractable.

The Limits of Conjunctive Reasoning

The primary challenge is that many foundational database tasks are optimized specifically for CQs. For instance, Nutt et al. and Razniewski demonstrate in Completeness of Queries over Incomplete Databases that reasoning about whether a query result is "complete" (exhaustive) can be reduced to query containment—but only for CQs. Once negation or union is introduced, the framework struggles to provide the same guarantees.

Similarly, in the realm of learned database components, Molina et al. show that while Relational Sum-Product Networks (RSPNs) excel at cardinality estimation for standard joins, they face significant hurdles when handling non-standard arithmetic or complex string matching (DeepDB: Learn from Data, not from Queries!). This pattern repeats across the field: as Dutt et al. note, learned models often fail to generalize to user-defined functions or spatial predicates (Efficiently Approximating Selectivity Functions using Low Overhead Regression Models).

Mapping the Complexity Landscape

To move beyond CQs, researchers are mapping the "complexity landscape" of more expressive languages. This often involves finding a trichotomy or tetrachotomy—a complete classification of every possible query into specific difficulty buckets (e.g., AC⁰, NL, P, or coNP).

For example, Lutz et al. and Sabellek established a trichotomy for queries in the $\mathcal{EL}$ description logic, proving that the ability to rewrite a query into "linear Datalog" (the logic behind recursive SQL) is the deciding factor for its efficiency (Ontology-Mediated Querying with EL: Trichotomy and Linear Datalog Rewritability).

In more complex scenarios involving "covering axioms" (e.g., "every employee is either a manager or a staff member"), Gerasimova et al. identified a tetrachotomy, showing that the syntactic shape of the query—such as whether it forms a simple path or a more complex tree—determines if it can be answered efficiently (A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom).

Structural Tractability and Rewriting

If a query is theoretically hard, can we still make it fast by exploiting its structure? The authors of Structural Tractability of Counting of Solutions to Conjunctive Queries identify quantified star size as a critical property. While traditional measures like treewidth help us know if a solution exists, quantified star size is what makes counting those solutions tractable.

Another powerful strategy is Datalog rewriting. By translating complex, non-Horn ontologies (which allow for "OR" logic) into plain Datalog programs, Kaminski et al. enable standard rule-based engines to handle queries that were previously considered too difficult for scalable systems (Datalog Rewriting Techniques for Non-Horn Ontologies).

The Path to Practical Expressivity

The ultimate goal of this research is to expand the "sweet spot" where high expressivity meets computational feasibility. As Lenzerini and Schaerf argued in their foundational work, it is often possible to use a simple language to build a knowledge base while employing a much richer language for queries, provided the interaction between the two is carefully managed (Concept Languages as Query Languages).

Current efforts continue to push these boundaries, seeking to support:

By formalizing the limits of these operators, the field is moving toward a future where database systems can handle the full complexity of human questions without sacrificing the speed of simple lookups.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_query_language_expressivity_4d6b2cc6,
  title = {query language expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/query-language-expressivity/rdr_4d6b2cc687fd41728044ea475b6d250c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_query_language_expressivity_4d6b2cc6_v1,
  title = {query language expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/query-language-expressivity/rdr_4d6b2cc687fd41728044ea475b6d250c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake