Lower Bounds for Conjunctive Query Evaluation CCS: Theory of computation Database theory
Stefan Mengel · 2025
Read Lower Bounds for Conjunctive Query Evaluation CCS: Theory of computation Database theory by Stefan Mengel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-17702.txt.
Introduction
Stefan Mengel gives a 2025 tutorial survey on how hard it is to answer conjunctive queries, a basic kind of database query. The survey gathers known results on the cost of query evaluation across several settings. These range from yes-or-no queries and counting answers to listing answers one by one and reaching answers directly.
A main theme is how recent guesses from complexity theory link to query answering. Under those guesses, many known algorithms for these tasks likely cannot be improved, which tells researchers where the true limits sit. The tutorial is aimed at readers who want a map of what is known, which methods look final, and where the open ground remains in database theory.
Catalog record
| CREATOR | Stefan Mengel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-17702
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lower Bounds for Conjunctive Query Evaluation CCS: Theory of computation Database theory Stefan Mengel Abstract . In this tutorial, we will survey known results on the complexity of conjunctive query evaluation in different settings, ranging from Boolean queries over counting to more complex models like enumeration and direct access. A particular focus will be on showing how different relatively recent hypotheses from complexity theory connect to query answering and allow showing that known algorithms in several cases can likely not be improved. 1. Introduction Understanding the complexity of different forms of query answering is one of the major research areas in database theory. Historically, the complexity of queries has been studied in three ways: in combined complexity, in data complexity ( Vardi82 ) , or in parameterized complexity ( Grohe02 ) . When trying to understand the necessary runtime to answer queries, combined complexity is very pessimistic: since the query and the database are both the inputs, answering first-order queries is PSPACE-hard and even conjunctive queries are NP-hard ( ChandraM77 ) . On the other end of the spectrum, in data complexity all first-order queries are classified as in PTIME and thus easy ( Vardi82 ) , which blurs the different complexities of different queries. So in a sense, both of these classical approaches are not completely satisfying when trying to assess the hardness of concrete queries. A more refined approach is parameterized complexity ( Grohe02 ) : similarly to data complexity, one considers the database as the main input, but instead of neglecting the query completely, one sees its size as a parameter. The runtime dependence on the parameter may be bad, but crucially it should not appear in the exponent of the input size, so roughly, for parameter k and input size n , a runtime of 2^{k}n is good, but n^{k} is bad. Parameterized complexity has led to many interesting results on the complexity of query answering, in particular the characterization of all classes of conjunctive queries that can be solved efficiently from the perspective of parameterized and combined complexity ( GroheSS01 ; Grohe07 ) . However, despite these merits, parameterized complexity has inherent limitations: it is only applicable to classes of queries, and thus we cannot use it to learn something about the complexity of specific, concrete queries. Fine-grained complexity opens up the possibility of attacking this question and determining the exact exponents of optimal query answering algorithms for individual queries. The idea of the area is to develop a complexity theory for problems inside PTIME to determine optimal runtimes for problems that are in classical theory all considered easy. The goal is to complement problems with algorithms that have runtime O(n^{c}) with lower bounds that rule out any algorithm with runtime O(n^{c-\varepsilon}) for all \varepsilon>0 . Of course, with today’s techniques, one cannot expect to show unconditional lower bounds. Also, it turns out that common classical assumptions like P \neq NP or even the Exponential Time Hypothesis, which plays a major role in parameterized complexity, appear to not be sufficient. Instead, fine-grained complexity relies on its own set of different hypotheses. Often these posit that known algorithms for important problems that have, despite considerable efforts, not been improved for a long time, are optimal. So the results of fine-grained complexity theory are generally of the form “If there is no better algorithm for problem X, then there is no better algorithms for problem Y, either.” where X can be one of several different, well-studied problems and Y is the problem that one is interested in. This makes fine-grained complexity a less coherent theory than, say, the theory of NP-completeness, and the confidence in its main hypotheses is certainly lower. However, it still provides techniques to give insights into which runtimes improvements would imply major, surprising algorithmic advances on well-known problems. This paper is not a survey of or introduction to fine-grained complexity itself---there are certainly others better qualified to do so 1 1 1 For example, there will be a keynote by Virginia Vassilevska Williams on this topic at PODS this year. and this type of work already exists, see e.g. ( VassilevskaWilliams2018 ) or the videos from a recent Simons Institute workshop that explain the area to a database theory audience ( Simons23 ) . Instead, this paper will be limited to a single question: how can fine-grained complexity be used to determine the complexity of conjunctive query answering. Here query answering is not restricted to materializing the complete query result or solving Boolean queries, but also covers tasks like counting (as a prototypical aggregation task), enumeration and direct access. A large part of this paper will be on linear time bounds, as this is the case that is by far most studied. As we will see, there is a wealth of results on this. Afterwards, we will turn to super-linear runtimes. Unfortunately, lower bounds for this case are far less developed, but we will give an overview of what is known and which techniques exist. Throughout the whole paper, we will introduce important hypotheses from fine-grained complexity that have been proven useful in database theory and show how they have been applied. Acknowledgements This paper was written to complement a tutorial that the author was invited to give at PODS 2025. The authors thanks the program committee for this opportunity to collect and present the results surveyed in this paper. Florent Capelli and Christoph Berkholz provided thoughtful comments, advice and discussion on an earlier version of this paper. The author is grateful for the time and effort they invested into this, which greatly improved the presentation of this survey. 2. Preliminaries 2.1. Database Queries We assume that the reader is familiar with the basics of database theory, in particular the relational model, see e.g. the first part of ( ArenasBLMP21 ) . In this paper, we will focus only on conjunctive queries , so queries of the form q(X){\,:\!\!-\,}R_{1}(X_{1}),\ldots,R_{\ell}(X_{\ell}) , where X and the X_{i} are sets of variables with X\subseteq\bigcup_{i\in[\ell]}X_{i} . If X=\bigcup_{i\in[\ell]}X_{i} , then we call q a join query . If X=\emptyset , we call q Boolean . If all relation symbols R_{i} in q are different, we say that q is self-join free ; if the same relation symbol repeats, we say that q has self-joins. We assume basic familiarity with the AGM-bound ( AtseriasGM13 ) and worst-case optimal join algorithms ( Ngo18 ) , see also ( ArenasBLMP21 , Chapters 27 and 28) . However, these concepts will not be central, and knowledge of their existence will be enough. As is standard, we assign hypergraphs to queries: for the query q(X){\,:\!\!-\,}R_{1}(X_{1}),\ldots,R_{\ell}(X_{\ell}) , the corresponding hypergraph H=(V,E) has vertices V:=\bigcup_{i\in[\ell]}X_{i} and the edge set \{X_{i}\mid i\in[\ell]\} . A hypergraph H=(V,E) is called acyclic if the following process ends with a hypergraph with no vertices or edges: while possible, delete a vertex that is contained in at most one edge, or delete an edge that is a subset of another edge. A conjunctive query is called acyclic if its hypergraph is acyclic. Acyclic queries are important and well studied because of their good algorithmic properties, see e.g. ( ArenasBLMP21 , Chapters 20 and 21) . For background and many properties