Abstract
In this talk, we consider the problem of counting the solutions to a query. Our first motivating scenario is the use of regular expressions to extract paths from a graph database. More specifically, given a graph database D, a regular expression r and a natural number n, consider the problem of counting the number of paths p in D such that p conforms to r and the length of p is n. This problem is known to be hard, namely #Pcomplete. In this talk, we show that this problem admits a fully polynomialtime randomized approximation scheme (FPRAS). Remarkably, the key idea to prove this result is to show that the fundamental problem #NFA admits an FPRAS, where #NFA is the problem of counting the number of strings of length n accepted by a nondeterministic finite automaton (NFA). While this problem is known to be #Pcomplete and, more precisely, SpanLcomplete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem and obtain as a welcome corollary that every function in SpanL admits an FPRAS.
As a second motivating scenario, we consider the widely used class of conjunctive queries over relational databases. More specifically, for every class C of conjunctive queries with bounded treewidth, we introduce the first FPRAS for counting the answers to a query in C. In fact, our FPRAS is more general, and also applies to conjunctive queries with bounded hypertree width, as well as unions of such queries. As for the case of graph databases, the key ingredient in our proof is the resolution of a fundamental counting problem from automata theory. Specifically, we show that the problem #TA admits an FPRAS, where #TA is the problem of counting the number of trees of size n accepted by a tree automaton (TA).
This talk is based on the results presented in [Marcelo Arenas et al., 2021; Marcelo Arenas et al., 2021].
BibTeX  Entry
@InProceedings{arenas:LIPIcs.ICDT.2022.2,
author = {Arenas, Marcelo},
title = {{Counting the Solutions to a Query}},
booktitle = {25th International Conference on Database Theory (ICDT 2022)},
pages = {2:12:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772235},
ISSN = {18688969},
year = {2022},
volume = {220},
editor = {Olteanu, Dan and Vortmeier, Nils},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15876},
URN = {urn:nbn:de:0030drops158763},
doi = {10.4230/LIPIcs.ICDT.2022.2},
annote = {Keywords: Counting, query answering, fully polynomialtime randomized approximation scheme}
}
Keywords: 

Counting, query answering, fully polynomialtime randomized approximation scheme 
Collection: 

25th International Conference on Database Theory (ICDT 2022) 
Issue Date: 

2022 
Date of publication: 

19.03.2022 
Supplementary Material: 

Audiovisual (Video of the Presentation): https://doi.org/10.5446/58128 