ABSTRACT
This paper proposes P-TopK, a framework integrating EDB-bounded Datalog with probabilistic query optimization, leveraging size bounds to guide lifted inference for efficient approximation schemes with guaranteed error bounds.
PAPER · PDF
Loading PDF…
Key findings
P-TopK achieves polynomial-time complexity for certain query classes, generalizing the safe query dichotomy to recursive settings.
The Probabilistic Adorned Evaluation (PAE) algorithm enables efficient approximate evaluation with user-specified error guarantees.
Preliminary analysis suggests P-TopK can achieve significant speedups over existing lifted inference methods for recursive queries.
Limitations & open questions
The framework's applicability to real-world knowledge base queries needs further experimental validation.