The dichotomy of conjunctive queries on probabilistic structures

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.

REFERENCES

• 1: D. Barbará , H. Garcia-Molina , D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.487-502, October 1992 [doi>10.1109/69.166990]
• 2: Jihad Boulos , Nilesh Dalvi , Bhushan Mandhani , Shobhit Mathur , Chris Re , Dan Suciu, MYSTIQ: a system for finding more answers by using probabilities, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066277]
• 3: Nadia Creignou , Miki Hermann, Complexity of generalized satisfiability counting problems, Information and Computation, v.125 n.1, p.1-12, Feb. 25, 1996 [doi>10.1006/inco.1996.0016]
• 4: Nilesh Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. In VLDB, 2004.
• 5: Nilesh Dalvi , Dan Suciu, Management of probabilistic data: foundations and challenges, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-12, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265531]
• 6: Tomás Feder , Moshe Y. Vardi, Monotone monadic SNP and constraint satisfaction, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.612-622, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167245]
• 7: Norbert Fuhr , Thomas Rölleke, A probabilistic relational algebra for the integration of information retrieval and database systems, ACM Transactions on Information Systems (TOIS), v.15 n.1, p.32-66, Jan. 1997 [doi>10.1145/239041.239045]
• 8: Erich Grädel , Yuri Gurevich , Colin Hirsch, The complexity of query reliability, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-234, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.295124]
• 9: Laks V. S. Lakshmanan , Nicola Leone , Robert Ross , V. S. Subrahmanian, ProbView: a flexible probabilistic database system, ACM Transactions on Database Systems (TODS), v.22 n.3, p.419-469, Sept. 1997 [doi>10.1145/261124.261131]
• 10: Christopher Re, Nilesh Dalvi, and Dan Suciu. Query evaluation on probabilistic databases. IEEE Data Engineering Bulletin, 29(1):25--31, 2006.
• 11: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 12: L. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8:410--421, 1979.
• 13: Jennifer Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

General Terms:
Algorithms, Theory

Keywords:
conjunctive queries, dichotomy, probabilistic databases