On Query Algebras for Probabilistic Databases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Query Algebras for Probabilistic Databases

Full text

Pdf (419 KB)

Source

ACM SIGMOD Record archive
Volume 37 , Issue 4 (December 2008) table of contents

COLUMN: Database principles table of contents

Pages 78-85

Year of Publication: 2009

ISSN:0163-5808

Author

Christoph Koch

Cornell University, Ithaca, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 62, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1519103.1519116 What is a DOI?

ABSTRACT

This article proposes a core query algebra for probabilistic databases. In essence, this core is part of the query languages of most probabilistic database systems proposed so far, but is sometimes hidden in complex language definitions. We give a formal definition of the algebra and illustrate it by examples. We then survey the current state of knowledge regarding the expressive power and complexity of this core.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	2	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
	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 and C. Koch. "On APIs for Probabilistic Databases". In Proc. 2nd International Workshop on Management of Uncertain Data, Auckland, New Zealand, 2008.
	5	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]
	6	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
	7	P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. "Conditional Functional Dependencies for Data Cleaning". In Proc. ICDE, 2007.
	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	Michaela Götz , Christoph Koch, A compositional framework for complex queries over uncertain data, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia [doi>10.1145/1514894.1514913]
	11	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]
	12	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]
	13	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]
	14	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]
	15	C. Koch. "MayBMS: A system for managing large uncertain and probabilistic databases". In C. Aggarwal, editor, Managing and Mining Uncertain Data, chapter 6. Springer-Verlag, 2008. To appear.
	16	Christoph Koch, A compositional query algebra for second-order logic and uncertain databases, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia [doi>10.1145/1514894.1514911]
	17	Christoph Koch , Dan Olteanu, Conditioning probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453894]
	18	C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. ICDE, pages 886--895, 2007.
	19	C. Rß and D. Suciu. "Efficient Evaluation of HAVING Queries on a Probabilistic Database". In Proc. DBPL, pages 186--200, 2007.
	20	Sarvjeet Singh , Chris Mayfield , Sagar Mittal , Sunil Prabhakar , Susanne Hambrusch , Rahul Shah, Orion 2.0: native support for uncertain data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376744]
	21	J. Widom. "Trio: a system for data, uncertainty, and lineage". In C. Aggarwal, editor, Managing and Mining Uncertain Data. Springer-Verlag, 2008. To appear.