Combined Approximations for Probabilistic Query Evaluation: An Intensional Approach
summary
Claims a method to get combined FPRASes for probabilistic query evaluation by compiling query+instance into non-deterministic OBDD or structured DNNF and then using an FPRAS for automaton counting. Shows self-join-free, bounded-hypertree-width queries admit a combined FPRAS; one-way path queries on labeled DAGs admit a combined FPRAS (ordering by DAG topological order); gives an FPRAS for directed ST reliability on DAGs. Proves hardness: some tree-on-tree cases have no FPRAS and some provenance DNNFs require exponential size.
AI-written summary · about
chapters (14)
- 0:00Probabilistic DB approximations
- 1:05Probabilistic query evaluation
- 4:41Exact evaluation complexity
- 7:35Motivation for approximations
- 9:23FPRAS requirements
- 11:52Approximation for self-join free
- 14:50Probabilistic graph restrictions
- 17:15Graph query approximability
- 19:02nOBDDs for path queries
- 21:52Network reliability FPRAS
- 23:15Inapproximability lower bounds
- 24:40Provenance circuit limits
- 26:26Future directions
- 28:35Conclusion
related talks
01h 01mBrief Tutorial on Probabilistic Databases
47mApproximate Lifted Inference with Probabilistic Databases
35mApproximating Certain and Possible Answers Beyond Sets
43mA Dichotomy for Queries with Negation in Probabilistic Databases
01h 06mSampling in Query Evaluation 2
01h 06mSampling in Query Evaluation 1
41mOptimizing Relational Programs I
21mProbabilistic Inference for Datalog with Correlated Inputs