neurolang.probabilistic.small_dichotomy_theorem_based_solver module¶
Implentation of probabilistic query resolution for hierarchical queries [^1]. Using this we apply the small dichotomy theorem [^1, ^2]: Let Q be a conjunctive query without self-joins or a non-repeating relational algebra expression. Then: * If Q is hierarchical, then P(Q) is in polynomial time, and can be computed using only the lifted inference rules for join, negation, union, and existential quantifier.
If Q is not hierarchical, then P(Q) is #P-hard in the size of the database.
[^1]: Robert Fink and Dan Olteanu. A dichotomy for non-repeating queries with negation in probabilistic databases. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’14, pages 144–155, New York, NY, USA, 2014. ACM.
[^2]: Nilesh N. Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. VLDB J., 16(4):523–544, 2007.
- neurolang.probabilistic.small_dichotomy_theorem_based_solver.extract_atom_sets_and_detect_self_joins(query)¶
- neurolang.probabilistic.small_dichotomy_theorem_based_solver.is_hierarchical_without_self_joins(query)¶
Let Q be first-order formula. For each variable x denote at(x) the set of atoms that contain the variable x. We say that Q is hierarchical if forall x, y one of the following holds: at(x) ⊆ at(y) or at(x) ⊇ at(y) or at(x) ∩ at(y) = ∅.
- neurolang.probabilistic.small_dichotomy_theorem_based_solver.solve_marg_query(rule, cpl)¶
Solve a MARG query on a CP-Logic program. Parameters ———- query : Implication
Consequent must be of type Condition. MARG query of the form ans(x) :- P(x).
- cpl_programCPLogicProgram
CP-Logic program on which the query should be solved.
Returns¶
- ProvenanceAlgebraSet
Provenance set labelled with probabilities for each tuple in the result set.
- neurolang.probabilistic.small_dichotomy_theorem_based_solver.solve_succ_query(query, cpl_program, run_relational_algebra_solver=True)¶
Solve a SUCC query on a CP-Logic program.
- Parameters:
- queryImplication
SUCC query of the form ans(x) :- P(x).
- cpl_programCPLogicProgram
CP-Logic program on which the query should be solved.
- run_relational_algebra_solver: bool, default True
When true the result’s relation attribute is a NamedRelationalAlgebraFrozenSet, when false the attribute is the relational algebra expression that produces the such set.
- Returns:
- ProvenanceAlgebraSet
Provenance set labelled with probabilities for each tuple in the result set.