The dichotomy of probabilistic inference for unions of conjunctive queries

No abstract is available for this paper.

• Publication year

  2012

• Venue

  JACM

• Publication date

  2012-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2395116.2395119
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lattice duality: The origin of probability and entropy

  2013cited by this paper
• Probabilistic databases

  2011cited by this paper
• Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams

  2011cited by this paper
• Unsupervised Ontology Induction from Text

  2010cited by this paper
• Computing query probability with incidence algebras

  2010cited by this paper
• The Exponential Time Complexity of Computing the Probability That a Graph Is Connected

  2010cited by this paper
• Model Counting

  2009cited by this paper
• Markov Logic: An Interface Layer for Artificial Intelligence

  2009cited by this paper
• Wiley Interdisciplinary Reviews

  2009cited by this paper
• Secondary-storage confidence computation for conjunctive queries with inequalities

  2009cited by this paper
• SPROUT: Lazy vs. Eager Query Plans for Tuple-Independent Probabilistic Databases

  2009cited by this paper
• Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases

  2008cited by this paper
• Representing and Querying Correlated Tuples in Probabilistic Databases

  2007cited by this paper
• Short XORs for Model Counting: From Theory to Practice

  2007cited by this paper
• Joint Inference in Information Extraction

  2007cited by this paper
• Management of probabilistic data: foundations and challenges

  2007cited by this paper
• Provenance semirings

  2007cited by this paper
• Introduction

  2006cited by this paper
• The dichotomy of conjunctive queries on probabilistic structures

  2006cited by this paper
• Entity Resolution with Markov Logic

  2006cited by this paper
• Markov logic networks

  2006cited by this paper
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees

  2006cited by this paper
• Lifted First-Order Probabilistic Inference

  2005cited by this paper
• BDDs--design, analysis, complexity, and applications

  2004cited by this paper
• Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series)

  2004cited by this paper
• Elements of Finite Model Theory

  2004cited by this paper
• A Knowledge Compilation Map

  2002cited by this paper
• On the tractable counting of theory models and its application to belief revision and truth maintenance

  2000cited by this paper
• ADVANCED DETERMINANT CALCULUS

  1999cited by this paper
• The complexity of query reliability

  1998cited by this paper
• Complexity of Generalized Satisfiability Counting Problems

  1996cited by this paper
• Foundations of Databases

  1994cited by this paper
• Branching Programs and Binary Deci-sion Diagrams-Theory and Applications

  1987cited by this paper
• The Theory of Probabilistic Databases

  1987cited by this paper
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

  1983cited by this paper
• Equivalences Among Relational Expressions with the Union and Difference Operators

  1980cited by this paper
• Equivalences Among Relational Expressions

  1979cited by this paper
• The Complexity of Enumeration and Reliability Problems

  1979influential reference
• Optimal implementation of conjunctive queries in relational data bases

  1977cited by this paper
• The VLDB Journal manuscript No. (will be inserted by the editor)

  year unknowncited by this paper

• Responsibility Measures for Conjunctive Queries with Negation

  2026influential citation
• A Unifying Algorithm for Hierarchical Queries

  2025cites this paper
• Tuple-Independent Representations of Infinite Probabilistic Databases

  2025cites this paper
• ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data

  2025cites this paper
• Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries

  2025cites this paper
• Database Theory in Action: Making Provenance and Probabilistic Database Theory Work in Practice (Invited Talk)

  2025cites this paper
• Causality-Based Scores Alignment in Explainable Data Management

  2025cites this paper
• FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds

  2025cites this paper
• The Causal-Effect Score in Data Management

  2025cites this paper
• Applications and Computation of the Shapley Value in Databases and Machine Learning

  2024cites this paper
• Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability

  2024cites this paper
• Expected Shapley-Like Scores of Boolean functions: Complexity and Applications to Probabilistic Databases

  2024cites this paper
• Is Complex Query Answering Really Complex?

  2024cites this paper
• A Unifying Framework for Incompleteness, Inconsistency, and Uncertainty in Databases

  2024cites this paper
• Shapley Value Computation in Ontology-Mediated Query Answering

  2024cites this paper
• Tractable Circuits in Database Theory

  2024cites this paper
• The Generalized Causal-Effect Score in Data Management (short paper)

  2024cites this paper
• From Shapley Value to Model Counting and Back

  2023cites this paper
• Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue

  2023cites this paper
• UnRavL: A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs

  2023cites this paper
• How to Turn Your Knowledge Graph Embeddings into Generative Models via Probabilistic Circuits

  2023cites this paper
• When is Shapley Value Computation a Matter of Counting?

  2023cites this paper
• LogicMP: A Neuro-symbolic Approach for Encoding First-order Logic Constraints

  2023cites this paper
• Approximating Queries on Probabilistic Graphs

  2023influential citation
• Towards Heterogeneous Data Integration: The NeuroLang Approach

  2023cites this paper
• Banzhaf Values for Facts in Query Answering

  2023cites this paper
• The Shapley Value in Database Management

  2023influential citation
• Probabilistic Query Evaluation: The Combined FPRAS Landscape

  2023influential citation
• Computing expected multiplicities for bag-TIDBs with bounded multiplicities

  2022cites this paper
• A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations

  2022cites this paper
• Fast Möbius and Zeta Transforms

  2022cites this paper
• Swift Markov Logic for Probabilistic Reasoning on Knowledge Graphs

  2022cites this paper
• Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries

  2022cites this paper
• Query answering over inconsistent knowledge bases: A probabilistic approach

  2022cites this paper
• Guest column: A panorama of counting problems the decision version of which is in P

  2022cites this paper
• Weighted Counting of Matchings in Unbounded-Treewidth Graph Families

  2022cites this paper
• Gamma Probabilistic Databases: Learning from Exchangeable Query-Answers

  2022cites this paper
• Meta-analysis of the functional neuroimaging literature with probabilistic logic programming

  2022cites this paper
• Scalable Query Answering Under Uncertainty to Neuroscientific Ontological Knowledge: The NeuroLang Approach

  2022cites this paper
• Probabilities of the Third Type: Statistical Relational Learning and Reasoning with Relative Frequencies

  2022cites this paper
• Probabilistic Query Evaluation with Bag Semantics

  2022influential citation
• SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning

  2021cites this paper
• An epistemic approach to model uncertainty in data-graphs

  2021cites this paper
• Computing the Shapley Value of Facts in Query Answering

  2021cites this paper
• Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration

  2021cites this paper
• Statistical Relational Artificial Intelligence with Relative Frequencies: A Contribution to Modelling and Transfer Learning across Domain Sizes

  2021cites this paper
• Lifted Inference with Tree Axioms

  2021cites this paper
• Query Games in Databases

  2021cites this paper
• Open-world probabilistic databases: Semantics, algorithms, complexity

  2021influential citation
• 23rd International Conference on Database Theory, ICDT 2020, Copenhagen, Denmark, March 30 - April 2, 2020

  2020cites this paper
• Introduction to Probabilistic Ontologies

  2020cites this paper
• Symbolic Querying of Vector Spaces: Probabilistic Databases Meets Relational Embeddings

  2020cites this paper
• Database Repairing with Soft Functional Dependencies

  2020cites this paper
• Tuple-Independent Representations of Infinite Probabilistic Databases

  2020cites this paper
• Aggregated Deletion Propagation for Counting Conjunctive Query Answers

  2020cites this paper
• A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries

  2020cites this paper
• Probabilistic Databases for All

  2020cites this paper
• Computing the Shapley Value of Tuples in Conjunctive Queries with Negation

  2020cites this paper
• Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

  2020cites this paper
• Complex Coordinate-Based Meta-Analysis with Probabilistic Programming

  2020cites this paper
• The Complexity of Counting Problems over Incomplete Databases

  2020cites this paper
• Independence in Infinite Probabilistic Databases

  2020cites this paper
• Model Counting for Conjunctive Queries Without Self-Joins

  2019cites this paper
• Towards Deterministic Decomposable Circuits for Safe Queries

  2019influential citation
• Scalable Rule Learning in Probabilistic Knowledge Bases

  2019cites this paper
• Generalized Lineage-Aware Temporal Windows: Supporting Outer and Anti Joins in Temporal-Probabilistic Databases

  2019cites this paper
• The Shapley Value of Tuples in Query Answering

  2019cites this paper
• Analyzing Uncertain Tabular Data

  2019cites this paper
• Anytime Approximation in Probabilistic Databases via Scaled Dissociations

  2019cites this paper
• Generalized Deletion Propagation on Counting Conjunctive Query Answers

  2019cites this paper
• Lineage-Aware Temporal Windows: Supporting Set Operations in Temporal-Probabilistic Databases

  2019cites this paper
• A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs

  2019cites this paper
• Counting Problems over Incomplete Databases

  2019cites this paper
• Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases

  2019influential citation
• The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries

  2019cites this paper
• Uniform Reliability of Self-Join-Free Conjunctive Queries

  2019influential citation
• The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs

  2019influential citation
• Combined Complexity of Probabilistic Query Evaluation

  2018influential citation
• Parameterised Queries and Lifted Query Answering

  2018cites this paper
• Recent Advances in Querying Probabilistic Knowledge Bases

  2018cites this paper
• Uncertain Data Lineage

  2018cites this paper
• Dan Suciu Speaks Out on Research, Shyness and Being a Scientist

  2018cites this paper
• Query Answering On Uncertain Big RDF Data Using Apache Spark Framework

  2018cites this paper
• On Constrained Open-World Probabilistic Databases

  2018cites this paper
• Retrieval from Uncertain Data Bases

  2018cites this paper
• Query Processing over Uncertain Data

  2018cites this paper
• Learning From Query-Answers

  2018cites this paper
• SchemaDrill: Interactive Semi-Structured Schema Design

  2018cites this paper
• Supporting Set Operations in Temporal-Probabilistic Databases

  2018cites this paper
• A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases

  2018influential citation
• Datalog Revisited for Reasoning in Linked Data

  2017cites this paper
• Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning

  2017influential citation
• Conjunctive Queries on Probabilistic Graphs: Combined Complexity

  2017influential citation
• Most Probable Explanations for Probabilistic Database Queries

  2017influential citation
• Ontology-Mediated Queries for Probabilistic Databases

  2017influential citation
• Efficient Sensitivity Analysis for Inequality Queries in Probabilistic Databases

  2017cites this paper
• Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151)

  2017cites this paper
• Query Processing on Probabilistic Data: A Survey

  2017cites this paper
• Exact Model Counting of Query Expressions

  2017cites this paper
• Provenance and Probabilities in Relational Databases

  2017cites this paper