Secondary-storage confidence computation for conjunctive queries with inequalities

ABSTRACT

This paper investigates the problem of efficiently computing the confidences of distinct tuples in the answers to conjunctive queries with inequalities (<) on tuple-independent probabilistic databases. This problem is fundamental to probabilistic databases and was recently stated open.

Our contributions are of both theoretical and practical importance. We define a class of tractable queries with inequalities, and generalize existing results on #P-hardness of query evaluation, now in the presence of inequalities.

For the tractable queries, we introduce a confidence computation technique based on efficient compilation of the lineage of the query answer into Ordered Binary Decision Diagrams (OBDDs), whose sizes are linear in the number of variables of the lineage.

We implemented a secondary-storage variant of our technique in PostgreSQL. This variant does not need to materialize the OBDD, but computes, in one scan over the lineage, the probabilities of OBDD fragments and combines them on the fly. Experiments with probabilistic TPC-H data show up to two orders of magnitude improvements when compared with state-of-the-art approaches.

REFERENCES

• 1: E. Adar and C. Re. "Managing Uncertainty in Social Networks". IEEE Data Eng. Bull. 30(2), 2007.
• 2: L. Antova, C. Koch, and D. Olteanu. "10¹⁰6 Worlds and Beyond: Efficient Representation and Processing of Incomplete Information". In Proc. ICDE 2007.
• 3: 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
• 4: 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]
• 5: 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]
• 6: 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]
• 7: 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]
• 8: A. Darwiche and P. Marquis. "A knowlege compilation map". Journal of AI Research 17: 229--264, 2002.
• 9: Jiewen Huang , Lyublena Antova , Christoph Koch , Dan Olteanu, MayBMS: a probabilistic database management system, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA [doi>10.1145/1559845.1559984]
• 10: Ravi Jampani , Fei Xu , Mingxi Wu , Luis Leopoldo Perez , Christopher Jermaine , Peter J. Haas, MCDB: a monte carlo approach to managing uncertain data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376686]
• 11: Richard M. Karp , Michael Luby, Monte-Carlo algorithms for enumeration and reliability problems, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, p.56-64, November 07-09, 1983 [doi>10.1109/SFCS.1983.35]
• 12: Christoph Koch , Dan Olteanu, Conditioning probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453894]
• 13: Christoph Meinel , Thorsten Theobald, Algorithms and Data Structures in VLSI Design, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 14: Dan Olteanu , Jiewen Huang, Using OBDDs for Efficient Query Evaluation on Probabilistic Databases, Proceedings of the 2nd international conference on Scalable Uncertainty Management, p.326-340, October 01-03, 2008, Naples, Italy [doi>10.1007/978-3-540-87993-0_26]
• 15: Dan Olteanu , Jiewen Huang , Christoph Koch, SPROUT: Lazy vs. Eager Query Plans for Tuple-Independent Probabilistic Databases, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.640-651, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.123]
• 16: C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. ICDE 2007.

INDEX TERMS

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

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

General Terms:
Algorithms, Languages, Management, Performance

Keywords:
decision diagrams, probabilistic databases, query processing