MCDB: a monte carlo approach to managing uncertain data

ABSTRACT

To deal with data uncertainty, existing probabilistic database systems augment tuples with attribute-level or tuple-level probability values, which are loaded into the database along with the data itself. This approach can severely limit the system's ability to gracefully handle complex or unforeseen types of uncertainty, and does not permit the uncertainty model to be dynamically parameterized according to the current state of the database. We introduce MCDB, a system for managing uncertain data that is based on a Monte Carlo approach. MCDB represents uncertainty via "VG functions," which are used to pseudorandomly generate realized values for uncertain attributes. VG functions can be parameterized on the results of SQL queries over "parameter tables" that are stored in the database, facilitating what-if analyses. By storing parameters, and not probabilities, and by estimating, rather than exactly computing, the probability distribution over possible query answers, MCDB avoids many of the limitations of prior systems. For example, MCDB can easily handle arbitrary joint probability distributions over discrete or continuous attributes, arbitrarily complex SQL queries, and arbitrary functionals of the query-result distribution such as means, variances, and quantiles. To achieve good performance, MCDB uses novel query processing techniques, executing a query plan exactly once, but over "tuple bundles" instead of ordinary tuples. Experiments indicate that our enhanced functionality can be obtained with acceptable overheads relative to traditional systems.

REFERENCES

• 1: Parag Agrawal , Omar Benjelloun , Anish Das Sarma , Chris Hayworth , Shubha Nabar , Tomoe Sugihara , Jennifer Widom, Trio: a system for data, uncertainty, and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 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, C. Koch, and D. Olteanu. 10¹⁰⁶ worlds and beyond: Efficient representation and processing of incomplete information. In ICDE, pages 606--615, 2007.
• 4: L. Antova, C. Koch, and D. Olteanu. MayBMS: Managing incomplete information with probabilistic world-set decompositions. In ICDE, pages 1479--1480, 2007.
• 5: Bahar Biller , Barry L. Nelson, Modeling and generating multivariate time-series input processes using a vector autoregressive technique, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.3, p.211-237, July 2003 [doi>10.1145/937332.937333]
• 6: Doug Burdick , AnHai Doan , Raghu Ramakrishnan , Shivakumar Vaithyanathan, OLAP over imprecise data with domain constraints, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 7: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluation of probabilistic queries over imprecise data in constantly-evolving environments, Information Systems, v.32 n.1, p.104-130, March, 2007 [doi>10.1016/j.is.2005.06.002]
• 8: Reynold Cheng , Sarvjeet Singh , Sunil Prabhakar, U-DBMS: a database system for managing constantly-evolving data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 9: Reynold Cheng , Sarvjeet Singh , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter , Yuni Xia, Efficient join processing over uncertain data, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183719]
• 10: David Chu , Amol Deshpande , Joseph M. Hellerstein , Wei Hong, Approximate Data Collection in Sensor Networks using Probabilistic Models, Proceedings of the 22nd International Conference on Data Engineering, p.48, April 03-07, 2006 [doi>10.1109/ICDE.2006.21]
• 11: 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]
• 12: Amol Deshpande , Samuel Madden, MauveDB: supporting model-based user views in database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142483]
• 13: L. Devroye. Non-Uniform Random Variate Generation. Springer, 1986.
• 14: L. Devroye and G. Lugosi. Combinatorial Methods in Density Estimation. Springer, 2001.
• 15: G. Fishman. Monte Carlo: Concepts, Algorithms, and Applications. Springer, 1996.
• 16: 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]
• 17: J. E. Gentle. Random Number Generation and Monte Carlo Methods. Springer, second edition, 2003.
• 18: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 19: Rahul Gupta , Sunita Sarawagi, Creating probabilistic databases from information extraction models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 20: 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
• 21: S. G. Henderson and B. L. Nelson, editors. Simulation. North-Holland, 2006.
• 22: 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]
• 23: Benny Kimelfeld , Yehoshua Sagiv, Matching twigs in probabilistic XML, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 24: Benny Kimelfeld , Yehoshua Sagiv, Maximally joining probabilistic data, 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.1265572]
• 25: R. Murthy and J. Widom. Making aggregation work in uncertain and probabilistic databases. In Proc. 1st Int. VLDB Work. Mgmt. Uncertain Data (MUD), pages 76--90, 2007.
• 26: A. Nadas. An extension of a theorem by Chow and Robbins on sequential confidence intervals for the mean. Ann. Math. Statist., 40(2):667--671, 1969.
• 27: Roger B. Nelsen, An Introduction to Copulas (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 28: A. O'Hagan and J. J. Forster. Bayesian Inference. Volume 2B of Kendall's Advanced Theory of Statistics. Arnold, second edition, 2004.
• 29: Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 30: C. Re, N. N. Dalvi, and D. Suciu. Query evaluation on probabilistic databases. IEEE Data Eng. Bull., 29(1):25--31, 2006.
• 31: C. Re, N. N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In ICDE, pages 886--895, 2007.
• 32: Christopher Ré , Dan Suciu, Materialized views in probabilistic databases: for information exchange and query optimization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 33: P. Sen and A. Deshpande. Representing and querying correlated tuples in probabilistic databases. In ICDE, pages 596--605, 2007.
• 34: R. J. Serfling. Approximation Theorems of Mathematical Statistics. Wiley, 1980.
• 35: S. Singh, C. Mayfield, S. Prabhakar, R. Shah, and S. E. Hambrusch. Indexing uncertain categorical data. In ICDE, pages 616--625, 2007.
• 36: J. Xie, J. Yang, Y. Chen, H. Wang, and P. Yu. A sampling-based approach to information recovery. In ICDE, 2008. To appear.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
mcdb, monte carlo, uncertainty