Nilesh Dalvi
Dan Suciu
ABSTRACT
We show that for every conjunctive query, the complexity of evaluating it on a probabilistic database is either PTIME or P-complete, and we give an algorithm for deciding whether a given conjunctive query is PTIME or P-complete. The dichotomy property is a fundamental result on query evaluation on probabilistic databases and it gives a complete classification of the complexity of conjunctive queries.
- Daniel Barbará, Hector Garcia-Molina, and Daryl Porter. The management of probabilistic data. IEEE Trans. Knowl. Data Eng., 4(5):487--502, 1992. Google Scholar
Digital Library
- Jihad Boulos, Nilesh Dalvi, Bhushan Mandhani, Shobhit Mathur, Chris Re, and Dan Suciu. Mystiq: a system for finding more answers by using probabilities. In SIGMOD, pages 891--893, 2005. Google ScholarDigital Library
- Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Inf. Comput., 125(1):1--12, 1996. Google ScholarDigital Library
- Nilesh Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. In VLDB, 2004.Google ScholarDigital Library
- Nilesh Dalvi and Dan Suciu. Management of probabilistic data: Foundations and challenges. In PODS, 2007. Google ScholarDigital Library
- Tomas Feder and Moshe Y. Vardi. Monotone monadic snp and constraint satisfaction. In STOC, pages 612--622, 1993. Google ScholarDigital Library
- Norbert Fuhr and Thomas Rolleke. A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Trans. Inf. Syst., 15(1):32--66, 1997. Google ScholarDigital Library
- Erich Gradel, Yuri Gurevich, and Colin Hirch. The complexity of query reliability. In PODS, pages 227--234, 1998. Google ScholarDigital Library
- Laks V. S. Lakshmanan, Nicola Leone, Robert Ross, and V. S. Subrahmanian. Probview: a flexible probabilistic database system. ACM Trans. Database Syst., 22(3):419--469, 1997. Google ScholarDigital Library
- Christopher Re, Nilesh Dalvi, and Dan Suciu. Query evaluation on probabilistic databases. IEEE Data Engineering Bulletin, 29(1):25--31, 2006.Google Scholar
- Thomas J. Schaefer. The complexity of satisfiability problems. In STOC, pages 216--226, 1978. Google ScholarDigital Library
- L. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8:410--421, 1979.Google ScholarDigital Library
- Jennifer Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, 2005.Google Scholar
Index Terms
- The dichotomy of conjunctive queries on probabilistic structures
Recommendations
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database TheoryThe problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
A dichotomy in the complexity of counting database repairs
An uncertain database db is defined as a database in which distinct tuples of the same relation can agree on their primary key. A repair is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples of the same relation ...
Efficient approximations of conjunctive queries
PODS '12: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database SystemsWhen finding exact answers to a query over a large database is infeasible, it is natural to approximate the query by a more efficient one that comes from a class with good bounds on the complexity of query evaluation. In this paper we study such ...
Comments