On Probabilistic Fixpoint and Markov Chain Query Languages.

We study highly expressive query languages such as datalog, fixpoint, and while-languages on probabilistic databases. We generalize these languages such that computation steps (e.g. datalog rules) can fire probabilistically. We define two possible semantics for such query languages, namely inflationary semantics where the results of each computation step are added to the current database and non-inflationary queries that induce a random walk in-between database instances. We then study the complexity of exact and approximate query evaluation under these semantics.


Published in:
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA
Presented at:
Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, Indianapolis, Indiana, USA, June 6-11,2010
Year:
2010
Laboratories:




 Record created 2011-05-23, last modified 2018-01-28

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)