• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Probabilistic Query Evaluation: the Combined FPRAS Landscape.
Timothy van Bremen, and Kuldeep S. Meel.
In Proceedings of ACM Symposium on Principles of Database Systems (PODS), June 2023.
We consider the problem of computing the probability of a query over a tuple-independent probabilistic database, known as the probabilistic query evaluation (PQE) problem. The problem is well-known to be #P-hard in data complexity for conjunctive queries in general, as well as for several subclasses of conjunctive queries. Existing approximation approaches for dealing with hard queries have centred on computing the lineage of the query over the database, which can be intractable for all but the smallest of queries due to the exponential dependence of the lineage size on the query length. In this paper, we take a first step towards bridging this gap, by showing how to construct a fully polynomial-time randomized approximation scheme (FPRAS) for the PQE problem for any class of self-join-free conjunctive queries of bounded hypertree width, that runs in time polynomial in both the query length and database instance size. An interesting consequence of our result is the existence of classes of queries that are #P-hard in data complexity to evaluate exactly, yet easy to approximate both in terms of query length and database size.
@inproceedings{BM23,
title={Probabilistic Query Evaluation: the Combined FPRAS Landscape},
author={van Bremen, Timothy and Meel, Kuldeep S.},
abstract={We consider the problem of computing the probability of a query over a tuple-independent probabilistic database, known as the probabilistic query evaluation (PQE) problem. The problem is well-known to be #P-hard in data complexity for conjunctive queries in general, as well as for several subclasses of conjunctive queries. Existing approximation approaches for dealing with hard queries have centred on computing the lineage of the query over the database, which can be intractable for all but the smallest of queries due to the exponential dependence of the lineage size on the query length.
In this paper, we take a first step towards bridging this gap, by showing how to construct a fully polynomial-time randomized approximation scheme (FPRAS) for the PQE problem for any class of self-join-free conjunctive queries of bounded hypertree width, that runs in time polynomial in both the query length and database instance size. An interesting consequence of our result is the existence of classes of queries that are #P-hard in data complexity to evaluate exactly, yet easy to approximate both in terms of query length and database size.},
publication_type={conference},
booktitle=PODS,
year={2023},
url={../Papers/pods23.pdf},
month=jun,
bib2html_rescat={Counting,Data Streams},
bib2html_pubtype={Refereed Conference},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51