• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability.
Antoine Amarilli, Timothy van Bremen and Kuldeep S. Meel.
In Proceedings of the International Conference on Database Theory (ICDT), March 2024.
Query evaluation over probabilistic databases is a notoriously intractable problem - not only in combined complexity, but for many natural queries in data complexity as well [Antoine Amarilli et al., 2017; Nilesh N. Dalvi and Dan Suciu, 2012]. This motivates the study of probabilistic query evaluation through the lens of approximation algorithms, and particularly of combined FPRASes, whose runtime is polynomial in both the query and instance size. In this paper, we focus on tuple-independent probabilistic databases over binary signatures, which can be equivalently viewed as probabilistic graphs. We study in which cases we can devise combined FPRASes for probabilistic query evaluation in this setting. We settle the complexity of this problem for a variety of query and instance classes, by proving both approximability and (conditional) inapproximability results. This allows us to deduce many corollaries of possible independent interest. For example, we show how the results of [ACJR21] on counting fixed-length strings accepted by an NFA imply the existence of an FPRAS for the two-terminal network reliability problem on directed acyclic graphs: this was an open problem until now [Rico Zenklusen and Marco Laumanns, 2011]. We also show that one cannot extend a recent result [Timothy van Bremen and Kuldeep S. Meel, 2023] that gives a combined FPRAS for self-join-free conjunctive queries of bounded hypertree width on probabilistic databases: neither the bounded-hypertree-width condition nor the self-join-freeness hypothesis can be relaxed. Finally, we complement all our inapproximability results with unconditional lower bounds, showing that DNNF provenance circuits must have at least moderately exponential size in combined complexity.
@inproceedings{ABM24,
author={ Amarilli, Antoine and Bremen, Timothy van and Meel, Kuldeep S.},
title={Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability},
abstract={Query evaluation over probabilistic databases is a notoriously intractable problem -
not only in combined complexity, but for many natural queries in data complexity as well [Antoine Amarilli et al., 2017; Nilesh N. Dalvi and Dan Suciu, 2012].
This motivates the study of probabilistic query evaluation through the lens of approximation algorithms, and particularly of
combined FPRASes, whose runtime is polynomial in both the query and instance size. In this
paper, we focus on tuple-independent probabilistic databases over binary signatures, which
can be equivalently viewed as probabilistic graphs. We study in which cases we can devise
combined FPRASes for probabilistic query evaluation in this setting. We settle the complexity
of this problem for a variety of query and instance classes, by proving both approximability and
(conditional) inapproximability results. This allows us to deduce many corollaries of possible independent interest.
For example, we show how the results of [ACJR21]
on counting fixed-length strings accepted by an NFA imply the existence of an FPRAS for the
two-terminal network reliability problem on directed acyclic graphs: this was an open problem
until now [Rico Zenklusen and Marco Laumanns, 2011]. We also show that one cannot extend
a recent result [Timothy van Bremen and Kuldeep S. Meel, 2023] that gives a combined FPRAS
for self-join-free conjunctive queries of bounded hypertree width on probabilistic databases:
neither the bounded-hypertree-width condition nor the self-join-freeness hypothesis can be
relaxed. Finally, we complement all our inapproximability results with unconditional lower bounds,
showing that DNNF provenance circuits must have at least moderately exponential size in combined complexity.
},
month=mar,
year={2024},
booktitle=ICDT,
bib2html_pubtype={Refereed Conference},
bib2html_rescat={Data Streams},
bib2html_dl_pdf={https://doi.org/10.4230/LIPIcs.ICDT.2024.15},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51