Approximating predicates and expressive queries on probabilistic databases

ABSTRACT

We study complexity and approximation of queries in an expressive query language for probabilistic databases. The language studied supports the compositional use of confidence computation. It allows for a wide range of new use cases, such as the computation of conditional probabilities and of selections based on predicates that involve marginal and conditional probabilities. These features have important applications in areas such as data cleaning and the processing of sensor data. We establish techniques for efficiently computing approximate query results and for estimating the error incurred by queries. The central difficulty is due to selection predicates based on approximated values, which may lead to the unreliable selection of tuples. A database may contain certain singularities at which approximation of predicates cannot be achieved; however, the paper presents an algorithm that provides efficient approximation otherwise.

REFERENCES

• 1: L. Antova, T. Jansen, C. Koch, and D. Olteanu. "Fast and Simple Relational Processing of Uncertain Data". In Proc. ICDE, 2008.
• 2: Lyublena Antova , Christoph Koch , Dan Olteanu, From complete to incomplete information and back, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247559]
• 3: Lyublena Antova , Christoph Koch , Dan Olteanu, Query language support for incomplete information in the MayBMS system, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 4: L. Antova, C. Koch, and D. Olteanu. "World-set Decompositions: Expressiveness and Efficient Algorithms". In Proc. ICDT, 2007.
• 5: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 6: 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]
• 7: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 8: Nilesh Dalvi , Dan Suciu, The dichotomy of conjunctive queries on probabilistic structures, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265571]
• 9: Michel de Rougemont, The reliability of queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.286-291, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212479]
• 10: 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]
• 11: Joseph Y. Halpern, Reasoning about Uncertainty, MIT Press, Cambridge, MA, 2003
• 12: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 13: Christopher Jermaine , Subramanian Arumugam , Abhijit Pol , Alin Dobra, Scalable approximate query processing with the DBO engine, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247560]
• 14: Richard M. Karp , Michael Luby, Monte-Carlo algorithms for enumeration and reliability problems, Proceedings of the 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), p.56-64, November 07-09, 1983 [doi>10.1109/SFCS.1983.35]
• 15: M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.
• 16: C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. ICDE, 2007.
• 17: P. Sen and A. Deshpande. "Representing and Querying Correlated Tuples in Probabilistic Databases". In Proc. ICDE, pages 596--605, 2007.
• 18: Stanford Trio Project. "TriQL -- The Trio Query Language", 2006. http://infolab.stanford.edu/~widom/triql.html.
• 19: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages, Theory

Keywords:
approximation, complexity, probabilistic databases, uncertain data