Query-time reasoning in uncertain RDF knowledge bases with soft and hard rules

Recent advances in information extraction have paved the way for the automatic construction and growth of large, semantic knowledge bases from Web sources. However, the very nature of these extraction techniques entails that the resulting RDF knowledge bases may face a significant amount of incorrect, incomplete, or even inconsistent (i.e., uncertain) factual knowledge, which makes efficient query answering over this kind of uncertain RDF data a challenge. Our engine, coined URDF, augments first-order reasoning by a combination of soft rules (Datalog-style implications), which are grounded in a deductive fashion in order to derive new facts from existing ones, and hard rules (mutual-exclusiveness constraints), which enforce additional consistency constraints among both base and derived facts. At the core of our approach is an efficient approximation algorithm for this constrained form of the weighted MaxSAT problem with soft and hard rules, allowing us to dynamically resolve inconsistencies directly at query-time. Experiments on real-world and synthetic data confirm a high robustness and significantly improved runtime of our framework in comparison to state-of-the-art MCMC techniques.