• 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.
Selected as one of the 7 best papers from the conference to be invited for a special issue of the journal Logical Methods in Computer Science.
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,
note={
Selected as one of the 7 best papers from the conference to be invited for a
special issue of the journal Logical Methods in Computer Science.
},
bib2html_pubtype={Refereed Conference,Award Winner},
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 Tue Apr 28, 2026 01:27:21