2022/04/06 by Su Feng, Boris Glavic, Feng, Su +7
Computer Science · #Advanced Database Systems and Queries #Computational Complexity (cs.CC) #Databases (cs.DB) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2204.02758
openalex publication_date 2022/04/06 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
In this work, we study the problem of computing a tuple's expected multiplicity over probabilistic databases with bag semantics (where each tuple is associated with a multiplicity) exactly and approximately. We consider bag-TIDBs where we have a bound c on the maximum multiplicity of each tuple and tuples are independent probabilistic events (we refer to such databases as c-TIDBs. We are specifically interested in the fine-grained complexity of computing expected multiplicities and how it compares to the complexity of deterministic query evaluation algorithms -- if these complexities are comparable, it opens the door to practical deployment of probabilistic databases. Unfortunately, our results imply that computing expected multiplicities for c-TIDBs based on the results produced by such query evaluation algorithms introduces super-linear overhead (under parameterized complexity hardness assumptions/conjectures). We proceed to study approximation of expected result tuple multiplicities for positive relational algebra queries (RA+) over c-TIDBs and for a non-trivial subclass of block-independent databases (BIDBs). We develop a sampling algorithm that computes a 1±ε approximation of the expected multiplicity of an output tuple in time linear in the runtime of the corresponding deterministic query for any RA+ query.