Foundations and Trends® in Databases > Vol 7 > Issue 3-4

Query Processing on Probabilistic Data: A Survey

By Guy Van den Broeck, University of California, Los Angeles, USA, guyvdb@cs.ucla.edu | Dan Suciu, University of Washington, USA, suciu@cs.washington.edu

 
Suggested Citation
Guy Van den Broeck and Dan Suciu (2017), "Query Processing on Probabilistic Data: A Survey", Foundations and TrendsĀ® in Databases: Vol. 7: No. 3-4, pp 197-341. http://dx.doi.org/10.1561/1900000052

Publication Date: 07 Aug 2017
© 2017 G. Van den Broeck and D. Suciu
 
Subjects
Probabilistic Data Management,  Query Processing and Optimization,  Data Models and Query Languages,  Database Theory,  Relational learning
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Probabilistic Data Model
3. Weighted Model Counting
4. Lifted Query Processing
5. Query Compilation
6. Data, Systems, and Applications
7. Conclusions and Open Problems
References

Abstract

Probabilistic data is motivated by the need to model uncertainty in large databases. Over the last twenty years or so, both the Database community and the AI community have studied various aspects of probabilistic relational data. This survey presents the main approaches developed in the literature, reconciling concepts developed in parallel by the two research communities. The survey starts with an extensive discussion of the main probabilistic data models and their relationships, followed by a brief overview of model counting and its relationship to probabilistic data. After that, the survey discusses lifted probabilistic inference, which are a suite of techniques developed in parallel by the Database and AI communities for probabilistic query evaluation. Then, it gives a short summary of query compilation, presenting some theoretical results highlighting limitations of various query evaluation techniques on probabilistic data. The survey ends with a very brief discussion of some popular probabilistic data sets, systems, and applications that build on this technology.

DOI:10.1561/1900000052
ISBN: 978-1-68083-314-0
154 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-68083-315-7
154 pp. $260.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Probabilistic Data Model
3. Weighted Model Counting
4. Lifted Query Processing
5. Query Compilation
6. Data, Systems, and Applications
7. Conclusions and Open Problems
References

Query Processing on Probabilistic Data: A Survey

Probabilistic data is motivated by the need to model uncertainty in large databases. Over the last twenty years or so, both the Database community and the AI community have studied various aspects of probabilistic relational data.

Query Processing on Probabilistic Data: A Survey presents the main approaches developed in the literature, reconciling concepts developed in parallel by the two research communities. It starts with an extensive discussion of the main probabilistic data models and their relationships, followed by a brief overview of model counting and its relationship to probabilistic data. The monograph proceeds to discuss lifted probabilistic inference, a suite of techniques developed in parallel by the Database and AI communities for probabilistic query evaluation. It then provides a summary of query compilation, presenting some theoretical results highlighting limitations of various query evaluation techniques on probabilistic data. It ends with a brief discussion of some popular probabilistic data sets, systems, and applications that build on this technology.

 
DBS-052