conference paper
On Probabilistic Fixpoint and Markov Chain Query Languages.
2010
PODS '10: Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
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.
Type
conference paper
Author(s)
Date Issued
2010
Published in
PODS '10: Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
Start page
215
End page
226
Editorial or Peer reviewed
REVIEWED
Written at
OTHER
EPFL units
| Event name | Event place | Event date |
Indianapolis, Indiana, USA | June 6-11,2010 | |
Available on Infoscience
May 23, 2011
Use this identifier to reference this record