TL;DR
This paper tackles the problem of evaluating queries over probabilistic databases, specifically focusing on "homomorphism-closed" queries. The core contribution is a complete dichotomy: these queries are either efficiently solvable or fundamentally hard (#P-hard), providing a clear complexity landscape for a broad class of queries on uncertain data.
What Problem Does This Paper Address?
Managing uncertain data is crucial in many applications, from integrating diverse sources to modeling sensor readings. Probabilistic databases, particularly Tuple-Independent Databases (TIDs), represent this uncertainty by assigning probabilities to individual facts. A key challenge is then Probabilistic Query Evaluation (PQE): computing the probability that a given query holds true over such a database.
While a dichotomy for simpler queries (unions of conjunctive queries, UCQs) was established, a significant gap remained for more expressive query languages, especially those involving recursion. This paper addresses this gap by focusing on "homomorphism-closed" queries (denoted UCQ∞), which are equivalent to infinite unions of conjunctive queries. This class includes important languages like Datalog (without negation) and regular path queries. The authors aim to provide a complete complexity classification for PQE on these more expressive queries over probabilistic graphs (databases with binary relations).
Methods
The paper establishes its dichotomy by proving that all unbounded UCQ∞ queries on arity-two signatures are #P-hard. This is achieved through two main proof strategies, reducing from known #P-hard problems:
- #PP2DNF Reduction: For queries that have a specific type of model (with a "non-iterable edge"), the authors reduce the problem of counting valuations of positive partitioned 2-DNF formulas (#PP2DNF) to PQE. This technique is analogous to hardness proofs for simpler unsafe UCQs.
- #U-ST-CON Reduction: For queries that lack such non-iterable edges, a more involved reduction from the undirected source-to-target connectivity problem (#U-ST-CON) is employed. This reduction relies on the concepts of "tight patterns" and "minimal tight patterns," which are novel contributions.
Key novel concepts introduced include:
- Non-iterable edges: Edges in a model that, when "iterated" (copied to create longer paths), can make a query false.
- Tight patterns: A model of a query with a non-leaf edge that, when "dissociated" (modified to break the edge), makes the query false.
- Minimal tight patterns: Tight patterns that are minimal with respect to edge weight and side weight, serving as a crucial tool for the #U-ST-CON reduction.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity and does not introduce or evaluate on specific datasets.
Key Insights and Ideas
- Expressiveness vs. Tractability: The paper demonstrates a sharp boundary: while bounded UCQ∞ queries (equivalent to UCQs) have a known dichotomy (either tractable or #P-hard), all unbounded UCQ∞ queries on arity-two signatures are #P-hard. This means that even a slight increase in expressiveness beyond UCQs, while remaining homomorphism-closed, can push the problem into the #P-hard complexity class.
- The Power of Homomorphism Closure: The property of being homomorphism-closed is key. It allows for the connection between query satisfaction and the structure of models, enabling the use of techniques like iteration and dissociation.
- Novel Structural Properties of Models: The introduction of "non-iterable" and "tight" edges reveals crucial structural properties of query models that dictate the complexity of PQE. These concepts are central to bridging the gap from known #P-hard problems to the queries under consideration.
- Completing the Dichotomy: By proving #P-hardness for all unbounded UCQ∞ queries, the paper effectively completes the dichotomy for this broad class of queries, building upon prior work for UCQs.
Key Results
The main result is a dichotomy for probabilistic query evaluation (PQE) on homomorphism-closed queries (UCQ∞) over arity-two signatures:
- Theorem 3.2: For any UCQ∞ query Q on an arity-two signature, PQE(Q) is either in FP (tractable) if Q is equivalent to a safe UCQ, or #P-hard otherwise.
- Theorem 3.3: Specifically, any unbounded UCQ∞ query on an arity-two signature is #P-hard for PQE.
This implies that the complexity of PQE for UCQ∞ queries is fully characterized: they are either efficiently computable (if equivalent to a safe UCQ) or #P-hard.
Limitations and Future Work
- Arity Restriction: The current results are limited to arity-two signatures. The authors conjecture that the #P-hardness result for unbounded UCQ∞ queries holds for arbitrary arity signatures as well, but extending the proof techniques (especially dissociation and iteration) to higher arities is a significant open challenge.
- Effectiveness of Dichotomy: The paper does not address whether the dichotomy is "effective," meaning whether it's decidable in polynomial time whether a given query is safe or unsafe. For some restricted query languages (like monadic Datalog), this is decidable, but for general Datalog, it's not.
- Queries with Negation/Disequalities: The current dichotomy applies to homomorphism-closed queries, which are inherently monotone. Extending the results to queries with negation or disequalities is a natural next step but requires different techniques.
- Model Counting: The paper's hardness results are for probabilistic query evaluation. Extending these to the related problem of model counting (where all facts have probability 0.5) is an open question for many query classes.
Summary updated