Conditioning probabilistic databases

ABSTRACT

Past research on probabilistic databases has studied the problem of answering queries on a static database. Application scenarios of probabilistic databases however often involve the conditioning of a database using additional information in the form of new evidence. The conditioning problem is thus to transform a probabilistic database of priors into a posterior probabilistic database which is materialized for subsequent query processing or further refinement. It turns out that the conditioning problem is closely related to the problem of computing exact tuple confidence values.

It is known that exact confidence computation is an NP-hard problem. This has led researchers to consider approximation techniques for confidence computation. However, neither conditioning nor exact confidence computation can be solved using such techniques. In this paper we present efficient techniques for both problems. We study several problem decomposition methods and heuristics that are based on the most successful search techniques from constraint satisfaction, such as the Davis-Putnam algorithm. We complement this with a thorough experimental evaluation of the algorithms proposed. Our experiments show that our exact algorithms scale well to realistic database sizes and can in some scenarios compete with the most efficient previous approximation algorithms.

REFERENCES

• 1: Serge Abiteboul , Paris Kanellakis , Gösta Grahne, On the representation and querying of sets of possible worlds, Theoretical Computer Science, v.78 n.1, p.159-187, Jan. 21, 1991
• 2: Periklis Andritsos , Ariel Fuxman , Renee J. Miller, Clean Answers over Dirty Databases: A Probabilistic Approach, Proceedings of the 22nd International Conference on Data Engineering, p.30, April 03-07, 2006 [doi>10.1109/ICDE.2006.35]
• 3: L. Antova, T. Jansen, C. Koch, and D. Olteanu. "Fast and Simple Relational Processing of Uncertain Data". In Proc. ICDE, 2008.
• 4: L. Antova, C. Koch, and D. Olteanu. "10¹⁰⁶ Worlds and Beyond: Efficient Representation and Processing of Incomplete Information". In Proc. ICDE, 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: E. Birnbaum and E. Lozinskii. "The Good Old Davis-Putnam Procedure Helps Counting Models". Journal of AI Research, 10(6):457--477, 1999.
• 7: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 8: Paul Dagum , Richard Karp , Michael Luby , Sheldon Ross, An Optimal Algorithm for Monte Carlo Estimation, SIAM Journal on Computing, v.29 n.5, p.1484-1496, March 2000 [doi>10.1137/S0097539797315306]
• 9: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.523-544, October 2007 [doi>10.1007/s00778-006-0004-3]
• 10: 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]
• 11: A. Darwiche and P. Marquis. "A knowlege compilation map". Journal of AI Research, 17:229--264, 2002.
• 12: Martin Davis , Hilary Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM (JACM), v.7 n.3, p.201-215, July 1960 [doi>10.1145/321033.321034]
• 13: 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]
• 14: 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]
• 15: J. Huang and D. Olteanu. Conjunctive queries with inequalities on probabilistic databases. Technical report, University of Oxford, 2008.
• 16: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 17: 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]
• 18: R. M. Kapp , M. Luby , N. Madras, Monte-Carlo approximation algorithms for enumeration problems, Journal of Algorithms, v.10 n.3, p.429-448, September 1989 [doi>10.1016/0196-6774(89)90038-2]
• 19: Christoph Koch, Approximating predicates and expressive queries on probabilistic databases, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376932]
• 20: Christoph Meinel , Thorsten Theobald, Algorithms and Data Structures in VLSI Design, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 21: C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. ICDE, pages 886--895, 2007.
• 22: A. D. Sarma, M. Theobald, and J. Widom. "Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases". In Proc. ICDE, 2008.
• 23: P. Sen and A. Deshpande. "Representing and Querying Correlated Tuples in Probabilistic Databases". In Proc. ICDE, pages 596--605, 2007.
• 24: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 25: Michael Wachter , Rolf Haenni, Multi-state Directed Acyclic Graphs, Proceedings of the 20th conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence, May 28-30, 2007, Montreal, Quebec, Canada [doi>10.1007/978-3-540-72665-4_40]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.m Miscellaneous
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance