Enumeration Theory through the Lens of Database Challenges

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 data-base 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.