More Web Proxy on the site http://driver.im/

research-article

Free access

A compositional framework for complex queries over uncertain data

Authors:

Michaela Götz,

Christoph KochAuthors Info & Claims

ICDT '09: Proceedings of the 12th International Conference on Database Theory

Pages 149 - 161

https://doi.org/10.1145/1514894.1514913

Published: 23 March 2009 Publication History

Abstract

The ability to flexibly compose confidence computation with the operations of relational algebra is an important feature of probabilistic database query languages. Computing confidences is computationally hard, however, and has to be approximated in practice. In a compositional query language, even very small errors caused by approximation can lead to an entirely incorrect result: A selection operation on an approximated probability can incorrectly keep or drop a tuple even if the probability value has been approximated to a very narrow confidence interval.

In this paper, we study the query evaluation problem for compositional query languages for probabilistic databases with particular focus on providing overall result quality guarantees in the face of approximate intermediate results. We present a framework for evaluating compositional queries based on a new representation system that can capture uncertainty about probabilities. More specifically, we consider probability intervals instead of exact probabilities, interpreting tuples obtained by selection on approximate values as unreliable.

We study the complexity of query evaluation over our new model. We present efficient confidence computation algorithms which compute bounds that are close to tight for important classes. For deciding a selection predicate, we show that no efficient randomized algorithm exists unless BPP⊃NP. Still we are able to efficiently guess robust predicates with a good error bound. Putting all these pieces together in our framework, we evaluate queries using a decomposition into a relational algebra plan and an approximation plan. The latter allows to successively improve accuracy and error bounds, while the relational algebra plan only has to be executed once.

References

[1]

Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.

Digital Library

[2]

Periklis Andritsos, Ariel Fuxman, and Renee J. Miller. Clean answers over dirty databases: A probabilistic approach. In Proc. ICDE, 2006.

Digital Library

[3]

Lyublena Antova, Thomas Jansen, Christoph Koch, and Dan Olteanu. "Fast and Simple Relational Processing of Uncertain Data". In Proc. ICDE, 2008.

Digital Library

[4]

Philip Bohannon, Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis. "Conditional Functional Dependencies for Data Cleaning". In Proc. ICDE, 2007.

[5]

Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. "Incorporating Constraints In Probabilistic XML". In Proc. PODS, 2008.

Digital Library

[6]

Nilesh Dalvi and Dan Suciu. "Efficient Query Evaluation on Probabilistic Databases". In Proc. VLDB, 2004.

Digital Library

[7]

Norbert Fuhr and Thomas Rölleke. "A Probabilistic Relational Algebra for the Integration of Information Retrieval and Database Systems". ACM Trans. Inf. Syst., 15(1), 1997.

Digital Library

[8]

Erich Grädel, Yuri Gurevich, and Colin Hirsch. "The Complexity of Query Reliability". In Proc. PODS, 1998.

Digital Library

[9]

Edward Hung, Lise Getoor, and V. S. Subrahmanian. "Probabilistic Interval XML". In Proc. ICDT, 2003.

Digital Library

[10]

T. Imielinski and W. Lipski. "Incomplete Information in Relational Databases". J. ACM, 31(4), 1984.

Digital Library

[11]

Abhay Jha, Vibhor Rastogi, and Dan Suciu. "Query Evaluation with Soft-Key Constraints". In Proc. PODS, 2008.

Digital Library

[12]

David S. Johnson. A catalog of complexity classes. Handbook of theoretical computer science (vol. A): algorithms and complexity, pages 67--161, 1990.

Digital Library

[13]

Richard M. Karp and Michael Luby. "Monte-Carlo Algorithms for Enumeration and Reliability Problems". In Proc. FOCS, 1983.

Digital Library

[14]

Christoph Koch. "Approximating Predicates and Expressive Queries on Probabilistic Data". In Proc. PODS, 2008.

Digital Library

[15]

Christoph Koch and Dan Olteanu. "Conditioning Probabilistic Databases". In Proc. VLDB, 2008.

Digital Library

[16]

Laks V. S. Lakshmanan, Nicola Leone, Robert B. Ross, and V. S. Subrahmanian. Probview: A flexible probabilistic database system. ACM Trans. Database Syst., 22(3):419--469, 1997.

Digital Library

[17]

Christopher Ré, Julie Letchner, Magdalena Balazinska, and Dan Suciu. "Event Queries on Correlated Probabilistic Streams". In Proc. SIGMOD, 2008.

Digital Library

[18]

Luca Trevisan. A note on approximate counting for k-dnf. In Proc. APPROX-RANDOM, 2004.

[19]

Leslie G. Valiant. "The Complexity of Enumeration and Reliability Problems". SIAM J. Comput., 8(3), 1979.

[20]

Jennifer Widom. "TRIO: A System for Managing Data, Uncertainty, and Lineage". In Charu Agarwal, editor, Managing and Mining Uncertain Data, 2008. To appear.

[21]

Wenzhong Zhao, Alex Dekhtyar, and Judy Goldsmith. Query algebra operations for interval probabilities. In Proc. DEXA, 2003.

[22]

Wenzhong Zhao, Alex Dekhtyar, and Judy Goldsmith. Databases for interval probabilities. Int. J. Intell. Syst., 19(9):789--815, 2004.

Digital Library

Cited By

Kim KKim Y(2018)Causal design knowledgeComputer-Aided Design10.1016/j.cad.2011.05.00543:9(1137-1153)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.cad.2011.05.005
Zhang YWang HYang ZLi J(2014)Relative Accuracy EvaluationPLoS ONE10.1371/journal.pone.01038539:8(e103853)Online publication date: 18-Aug-2014
https://doi.org/10.1371/journal.pone.0103853
Ge TLiu F(2012)Accuracy-Aware Uncertain Stream DatabasesProceedings of the 2012 IEEE 28th International Conference on Data Engineering10.1109/ICDE.2012.96(174-185)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1109/ICDE.2012.96
Show More Cited By

Recommendations

Ranking queries on uncertain data

Uncertain data is inherent in a few important applications. It is far from trivial to extend ranking queries (also known as top-k queries), a popular type of queries on certain data, to uncertain data. In this paper, we cast ranking queries on uncertain ...
Range queries on uncertain data

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...
Top-k dominating queries in uncertain databases
EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology

Due to the existence of uncertain data in a wide spectrum of real applications, uncertain query processing has become increasingly important, which dramatically differs from handling certain data in a traditional database. In this paper, we formulate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDT '09: Proceedings of the 12th International Conference on Database Theory

March 2009

334 pages

ISBN:9781605584232

DOI:10.1145/1514894

Editor:
Ronald Fagin
IBM Research

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

EDBT/ICDT '09

EDBT/ICDT '09: EDBT/ICDT '09 joint conference

March 23 - 25, 2009

St. Petersburg, Russia

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
228
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim KKim Y(2018)Causal design knowledgeComputer-Aided Design10.1016/j.cad.2011.05.00543:9(1137-1153)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.cad.2011.05.005
Zhang YWang HYang ZLi J(2014)Relative Accuracy EvaluationPLoS ONE10.1371/journal.pone.01038539:8(e103853)Online publication date: 18-Aug-2014
https://doi.org/10.1371/journal.pone.0103853
Ge TLiu F(2012)Accuracy-Aware Uncertain Stream DatabasesProceedings of the 2012 IEEE 28th International Conference on Data Engineering10.1109/ICDE.2012.96(174-185)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1109/ICDE.2012.96
Suciu DOlteanu DRé CKoch C(2011)Probabilistic DatabasesSynthesis Lectures on Data Management10.2200/S00362ED1V01Y201105DTM0163:2(1-180)Online publication date: 31-May-2011
https://doi.org/10.2200/S00362ED1V01Y201105DTM016
Deutch DKoch CMilo TParedaens JVan Gucht D(2010)On probabilistic fixpoint and Markov chain query languagesProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807114(215-226)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807085.1807114
Koch C(2009)On Query Algebras for Probabilistic DatabasesACM SIGMOD Record10.1145/1519103.151911637:4(78-85)Online publication date: 20-Mar-2009
https://dl.acm.org/doi/10.1145/1519103.1519116
Antova LKoch COlteanu D(2009)$${10^{(10^{6})}}$$ worlds and beyondThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-009-0149-y18:5(1021-1040)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1007/s00778-009-0149-y

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents