The dichotomy of probabilistic inference for unions of conjunctive queries

DOI10.1145/2395116.2395119zbMath1281.68095OpenAlexW2079785597MaRDI QIDQ5395698

Dan Suciu, Nilesh N. Dalvi

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2395116.2395119

zbMATH Keywords

Möbius functionMöbius inversion formulaprobabilistic database

Mathematics Subject Classification ID

Database theory (68P15) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Uniform Reliability of Self-Join-Free Conjunctive Queries ⋮ Analyzing real-world SPARQL queries and ontology-based data access in the context of probabilistic data ⋮ Lifted inference with tree axioms ⋮ Range queries on uncertain data ⋮ An epistemic approach to model uncertainty in data-graphs ⋮ A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Unnamed Item ⋮ Open-world probabilistic databases: semantics, algorithms, complexity ⋮ Unnamed Item ⋮ Skyline ranking for uncertain databases ⋮ Estimating latent feature-feature interactions in large feature-rich graphs ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ Query answering over inconsistent knowledge bases: a probabilistic approach ⋮ Unnamed Item