Name
Title | ||
|---|---|---|
Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration |
Abstract | ||
|---|---|---|
ABSTRACTWe consider tuple-independent probabilistic databases in a dynamic setting, where tuples can be inserted or deleted. In this context we are interested in efficient data structures for maintaining the query result of Boolean as well as non-Boolean queries. For Boolean queries, we show how the known lifted inference rules can be made dynamic, so that they support single-tuple updates with only a constant number of arithmetic operations. As a consequence, we obtain that the probability of every safe UCQ can be maintained with constant update time. For non-Boolean queries, our task is to enumerate all result tuples ranked by their probability. We develop lifted inference rules for non-Boolean queries, and, based on these rules, provide a dynamic data structure that allows both log-time updates and ranked enumeration with logarithmic delay. As an application, we identify a fragment of non-repeating conjunctive queries that supports log-time updates as well as log-delay ranked enumeration. This characterisation is tight under the OMv-conjecture. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3452021.3458326 | International Conference on Management of Data |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Berkholz | 1 | 49 | 7.03 |
| Maximilian Merz | 2 | 0 | 0.34 |