Pontificia Universidad Católica de Chile Pontificia Universidad Católica de Chile
Arenas M., Croquevielle L., Jayaram R., Riveros C. (2022)

Counting the Answers to a Query

Revista : SIGMOD Record
Volumen : 51
Número : 3
Páginas : 6-17
Tipo de publicación : ISI Ir a publicación


Counting the answers to a query is a fundamental problem in databases, with several applications in the evaluation, optimization, and visualization of queries. Unfortunately, counting query answers is a #P-hard problem in most cases, so it is unlikely to be solvable in polynomial time. Recently, new results on approximate counting have been developed, specifically by showing that some problems in automata theory admit fully polynomial-time randomized approximation schemes. These results have several implications for the problem of counting the answers to a query; in particular, for graph and conjunctive queries. In this work, we present the main ideas of these approximation results, by using labeled DAGs instead of automata to simplify the presentation. In addition, we review how to apply these results to count query answers in different areas of databases.