URDF: Efficient Reasoning in Uncertain RDF Knowledge Bases with Soft and Hard Rules
Lists
Only you see this
Abstract
We present URDF, an efficient reasoning framework for graph-based, nonschematic\nRDF knowledge bases and SPARQL-like queries. URDF augments\nfirst-order reasoning by a combination of soft rules, with Datalog-style \nrecursive\nimplications, and hard rules, in the shape of mutually exclusive sets of facts. \nIt incorporates\nthe common possible worlds semantics with independent base facts as\nit is prevalent in most probabilistic database approaches, but also supports \nsemantically\nmore expressive, probabilistic first-order representations such as Markov\nLogic Networks.\nAs knowledge extraction on theWeb often is an iterative (and inherently noisy)\nprocess, URDF explicitly targets the resolution of inconsistencies between the \nunderlying\nRDF base facts and the inference rules. Core of our approach is a novel\nand efficient approximation algorithm for a generalized version of the Weighted\nMAX-SAT problem, allowing us to dynamically resolve such inconsistencies \ndirectly\nat query processing time. Our MAX-SAT algorithm has a worst-case running\ntime of O(jCj jSj), where jCj and jSj denote the number of facts in grounded\nsoft and hard rules, respectively, and it comes with tight approximation \nguarantees\nwith respect to the shape of the rules and the distribution of confidences of \nfacts\nthey contain. Experiments over various benchmark settings confirm a high \nrobustness\nand significantly improved runtime of our reasoning framework in comparison\nto state-of-the-art techniques for MCMC sampling such as MAP inference\nand MC-SAT.\nKeywords
BibTeX
@inproceedings{theobald2010urdf,
author = {Martin Theobald and Mauro Sozio and Fabian M. Suchanek and Ndapa Nakashole},
title = {{URDF: Efficient Reasoning in Uncertain RDF Knowledge Bases with Soft and Hard Rules}},
booktitle = {MPG.PuRe},
year = {2010},
}Loading related content...