Enumeration Theory through the Lens of Database Challenges
Open Access
- 30 May 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 20-35
Abstract
Computational tasks that require producing many solutions arise throughout data management systems: database query engines return all qualifying tuples; search engines retrieve all relevant documents, albeit ranked; graph databases are tasked with producing all paths connecting two nodes; query optimizers routinely explore a vast space of candidate plans; and so on. Abstractly, these tasks are formalized as enumeration problems, solved by enumeration algorithms, and studied through the lens of enumeration complexity. This talk reflects on the evolution of enumeration in database research. It will begin with a brief survey of classic complexity-theoretic notions and algorithmic techniques that play a central role in enumeration across many domains. It will then review past results on enumeration problems arising in various areas of database systems. After that, it will delve deeper into the evolution of ideas and results on relational queries, with a special focus on join queries. It will conclude with challenges for future directions.Keywords
This publication has 48 references indexed in Scilit:
- Keyword Search on Large Graphs: A SurveyData Science and Engineering, 2021
- Enumeration Complexity of Conjunctive Queries with Functional DependenciesTheory of Computing Systems, 2019
- A survey of community search over big graphsThe VLDB Journal, 2019
- Paradigms for Parameterized EnumerationTheory of Computing Systems, 2016
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- On the Complexity of Dualization of Monotone Disjunctive Normal FormsJournal of Algorithms, 1996
- Network flow and 2-satisfiabilityAlgorithmica, 1994
- On generating all maximal independent setsInformation Processing Letters, 1988
- Candidate keys for relationsJournal of Computer and System Sciences, 1978
- How good is the information theory bound in sorting?Theoretical Computer Science, 1976