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.
The recent advent of information extraction techniques has
enabled the automatic construction and growth of large, semantic
knowledge bases from Web sources. Knowledge bases such as
DBpedia [
Research on knowledge base construction has adopted
probabilistic models and statistical learning for cleaning the gathered
pool of raw fact candidates (typically extracted from Wikipedia
and textual or semi-structured Web pages). A powerful instrument
to this end is reasoning with consistency constraints (see, e.g., [
When query answers are empty because critical pieces of knowledge are missing, reasoning over uncertain facts can be helpful to produce—at least—likely or speculative results. To this end, deduction rules are an instrument to infer answers that go beyond the extensionally represented content of the knowledge base. These rules themselves may be uncertain as well. For example, suppose we want to find the doctoral advisor of Alon Y. Halevy. Often (but not always) the senior author on the first few papers of a researcher is the doctoral advisor. Based on such a rule, we could deduce that Yehoshua Sagiv is Halevy’s advisor. Moreover, deduction rules cover a wide range of RDF/S and OWL-based reasoning concepts, such as the owl:TransitiveProperty of predicates (e.g., for the rdfs:subClassOf property or over owl:sameAs links), which lie at the expressive intersection of Datalog-style deductive reasoning and OWL-DL. Additional consistency constraints, on the other hand, cover OWL concepts such as the owl:FunctionalProperty or owl:disjointWith properties of predicates and classes.
In summary, we emphasize the following desiderata for querytime reasoning over uncertain RDF triples: 1) to give answers to complex SPARQL queries over triples with highly varying confidence values; 2) to overcome the incompleteness problem, exploit deduction rules, which may themselves be uncertain, and to infer answers even if some critical triples are missing; 3) to counter amplified noise and keep query-result precision high, take into account consistency constraints in the specific context of a user query; 4) achieve all of the above with high efficiency, so that queries can be answered with interactive response time of a few seconds. Our aim with URDF is to address the above desiderata in an integrated manner. Our implementation is based on top-down, ondemand grounding of rules expressed in first-order logic, together with a constrained form of weighted MaxSAT solving. Considering hard constraints jointly with MaxSAT reasoning over propositional clauses poses additional challenges; to our knowledge, these have not been addressed in prior work for interactive, query-time reasoning.
We are given a set X of Boolean variables, each variable taking either the value true or false. The negation of a variable x 2 X (denoted as x), has the value true if and only if x is assigned false. We shall refer to a variable x and its negation x as a literal. A Horn clause C is a set of literals containing at most one positive literal. Given a truth assignment to variables, we shall say that a Horn clause is satisfied if it contains at least one literal whose value is true (clauses are assumed to be in disjunctive form). Every clause C is associated with a positive weight w(C) 2 R. A Horn formula is defined as a conjunction of Horn clauses (and hence Horn formulas are in conjunctive normal form, CNF). A Horn formula is satisfiable if there is a truth assignment to all literals such that all clauses are satisfied. As we deal with Horn formulas that might not be satisfiable, we seek to find a truth assignment that maximizes the total weight of satisfied clauses. An example of a Horn formula is the following (x1 _ x2) ^ (x2 _ x3) equiv. to (x1 x2) ^ (x3 x2); where denotes logical implication.
Given a set of relation types R and a set E of entities, a fact f is defined as a triplet of the form f = (e1; e2; r), which expresses an instance of a binary relation of type r 2 R for two entities e1; e2 2 E (i.e., we could denote the fact that “John is married to Yoko”, where John and Yoko are both entities). Moreover, facts may be uncertain. Hence every fact f is also associated with a positive weight w(f ) 2 R, expressing the degree of confidence in the fact being correct. Moreover, every fact is also associated with a Boolean variable xf 2 X, whose value indicates whether the corresponding fact is true or false. In the following, we shall simplify the notation and do not distinguish between variables and facts anymore. Hence, assigning the value true to a fact f corresponds to assigning true to the corresponding variable xf .
We define a knowledge base KB as a triplet KB = fF ; C; Sg, where F is a set of facts, C is a set of Horn clauses, and S is a collection of disjoint sets of facts. We shall refer to C and S as soft deduction rules and hard consistency constraints, respectively (or soft and hard rules for short).
We consider weighted Horn clauses with exactly one positive head literal as soft rules. A soft rule could state, for example, that “if Yoko and John are married and John lives in NY, then also Yoko lives in NY”, with a confidence of 0.38 of being correct, which we write as follows: lives(Yoko; NY ) married(Yoko; John) ^ lives(John; NY )[0:38]
To tackle the inherent incompleteness of F , we lift soft rules into first-order rules with universally quantified variables, which serve as input to our knowledge base. Soft rules then have the shape of first-order Horn clauses and can be written as Datalog-style implications. To express the first-order rule that “married couples usually live in the same place”, for example, we use the following compact notation: livesIn(p1 ; loc1 )
marriedTo(p1 ; p2 ) ^ livesIn(p2 ; loc1 )[0:38]
The set of facts F may contain inconsistent information. Hence, we introduce hard consistency constraints that take the shape of a collection of disjoint sets of mutually-exclusive facts S = S1; : : : ; SjSj. We enforce the constraint that for each hard rule Sk, at most one fact f 2 Sk may be assigned the value true. For example, if we observe two or more different birth dates for a person, clearly something went wrong either during extraction or when reasoning with soft rules. We can formally identify such an inconsistency by formulating a consistency constraint as follows: (date1 = date2 )
bornOn(p1; date1) ^ bornOn(p1; date2) Grounding this hard rules could, for example, then yields the following set of mutually exclusive facts fbornOn(John; 1931 ); bornOn(John; 1940 ); bornOn(John; 1957 )g which specifies that John could be born either in 1931, 1940, 1957, or in none of the above years. In contrast to soft rules, hard rules may not be violated by any truth assignment to the corresponding Boolean variables. 2.3
As we deal with Horn formulas that might not be satisfiable, we seek to find a truth assignment that maximizes the total weight of the satisfied clauses. We call this problem weighted MaxSAT with soft and hard rules which we formally define as follows. We are given a set of facts F = ff1; f2; : : : ; fng, a collection C =
of sets S = S1; : : : ; St that partition F (hard rules). Each clause
a truth assignment to each variable f 2 F such that for each set in S at most one fact is assigned the value true, and the sum of the weights of the satisfied clauses is maximized.
Given a knowledge base KB = fF ; C; Sg (in grounded form),
we define an instance of the MaxSAT problem with soft and hard
rules as follows. Every fact fi 2 F is associated with a Boolean
variable. In addition, we introduce a unit clause Ci = ffig, whose
weight is equal to the confidence of the corresponding fact. For
convenience of notation, for each fact fi, we also introduce a unit
hard rule Si = ffig into S. As the MaxSAT problem with hard
and soft rules is a generalization of the classic MaxSAT problem
with Horn clauses, which is NP-Hard [
We remark that instead of hard rules, one could also enforce consistency constraints by introducing soft rules with high weights. However, in combination with an approximation algorithm, this approach may involve non-trivial issues as illustrated by the following example. Consider the following two facts bornOn(John; 1931 ) and bornOn(John; 1940 ), whose weights are 0 and w 0, respectively. In order to enforce the hard rule that John can only have one date of birth, we could introduce the following soft rule (x _ y) where x and y are the Boolean variables associated with facts bornOn(John; 1931 ) and bornOn(John; 1940 ), respectively. However, it is not clear how to determine the weight W of such a soft rule. If W is not large enough, then we could not enforce the hard consistency constraint. On the other hand, if W is too large, then any (1 + ) approximation algorithm (for > 0) might assign true to bornOn(John; 1931 ), as the ratio between such a solution and
W the optimum is W +w .
Our algorithm is inspired by Johnson’s approximation algorithm
for the original weighted MaxSAT [
The first step is to compute a real value pi in [0; 1] for each fact
fi, satisfying the following property: the sum of all pi’s
corresponding to the facts within a same hard rule is at most 1. Each
pi is interpreted as the probability that fi is assigned true and is
computed in such a way that pi is large when the confidence in fact
fi being true is high (i.e., w(fi) is large) and small otherwise. A
simple algorithm for computing the pi’s proceeds as follows: for
each hard rule S, with probability 1=2 assign true to the fact with
largest weight in S and with probability 1=2 assign false to all facts
in S. This gives a 1=2-approximation algorithm, however there
are more sophisticated algorithms which work better in practice,
while maintaining the approximation guarantee (see our technical
report for more details [
Formally, we denote with Wt the value of our potential function at step t. At the beginning of our algorithm all facts are unassigned and the value of our potential function (W0) is defined as W0 = X w(C) P (C is satisfied):
C2C where the probability that a clause is satisfied is a function of the pi’s computed at the beginning of our algorithm.
At step t, let ^ft 1 = f^1; : : : ; f^t 1 be the truth assignment for the facts ft 1 = f1; : : : ; ft 1 and let St be a hard rule considered at step t. We denote with St = f alse the truth assignment that assigns false to all facts in St. For every f in St, we define Wt;f=true =
X w(C) P (C is sat.j^ft 1 = ft 1; f = true) where P(AjB) denotes a conditional probability. When all facts in St are assigned false our potential function is denoted as Wt;St=false =
X w(C) P (C is sat.j^ft 1 = ft 1; St = f alse): C2C
C2C Our algorithm determines the truth assignment that maximizes the current potential function by choosing the largest value among all Wt;f=true’s and Wt;St=false and then assigns the corresponding truth values to the facts in St. At each iteration, all satisfied clauses are removed from the set of clauses.
Our algorithm stops when all facts have been assigned a truth
value. We remark that our algorithm is completely deterministic
(i.e., it always produces the same output given the same input).
Algorithm 1 shows pseudocode for our algorithm, while the
approximation guarantee of our algorithm is stated in Theorem 1.
Algorithm 1 Weighted MaxSAT with Soft and Hard Rules
1: For each hard rule compute a prob. distribution over its facts
so that for each fact fi, pi is proportional to w(fi), see [
If Wt;f=true Wt;St=false then assign true to f , else assign false to all facts in St. 4: Remove all satisfied clauses.
hard rules, let be the minimum number of negated literals in any
approximation algorithm for the MaxSAT problem with soft and hard rules, where p is obtained by solving the equation p = 1 p .
m = Pc2C jcj and n = Ps2S jsj.
tee of 1=2 for general Horn clauses.
Due to space constraints, we defer the proof of Theorem 1 to
[
In the absence of any soft and hard rules, URDF conforms to a standard (conjunctive) SPARQL engine where all facts in F are assumed to be true. Our key observation for query answering in combination with MaxSAT solving is that still often only a small subset of facts in F —often several orders of magnitude less facts than those contained in the entire knowledge base—are relevant for answering a specific query and for finding the corresponding truth assignments to the facts that are related to the query. For this purpose, we define the dependency graph DQ F of a query Q as follows.
DEFINITION 1. Given a knowledge base KB = fF ; C; Sg and a conjunctive query Q, then:
Definition 1 already yields a recursive algorithm to compute the
dependency graph, which is similar to SLD resolution [
SQ (Algorithm 1). 7: return DQ with truth assignments to all facts f 2 DQ
Given a set of first order rules, this form of deductive grounding
has a well-known polynomial runtime for non-recursive Datalog
programs, and for linear, recursive programs, respectively. It
however has an exponential complexity (in the number of facts) already
for Datalog programs with a single, non-linear, recursive rule [
We remark that the above form of dependency graph construction guarantees truth assignments to query answers that are consistent with the truth assigments that would be found by the MaxSAT solver for the entire sets of facts F , clauses C, and constraints S. That is, the truth assignments to facts in the dependency graph DQ F for any query Q after MaxSAT solving are equivalent to the truth assignments that would be obtained for these facts when running the MaxSAT solver over the entire set of facts F in the knowledge base (modulo ties and possible MaxSAT approximation errors).
The following experiments were run on an AMD Opteron QuadCore 2.6 GHz server with 16 GB RAM, using Oracle-11g as storage back-end for the underlying knowledge base. Physical I/O’s were cached (thus aiming to eliminate variances due to disk operations) by running each query once and then taking the average runtime over 5 immediately repeated runs. Memory consumption was generally not a delimiting factor, with up to 501 MB overall memory consumption for our URDF Java implementation (including the high overhead of the Java VM) and less than 10 MB for the Alchemy package (see Subsection 5.2), implemented in C++. 5.1
The semantic graph of YAGO [
Alchemy2 provides a series of algorithms for statistical relational
learning and probabilistic inference based on the Markov Logic
Networks [
The first setting reports running times and result precision for the URDF reasoner compared to MAP inference and MC-SAT over the basic YAGO setting. As for approximation quality, we measure the relative precision of the URDF MaxSAT solver compared to the MAP baseline: if the MaxSAT weight computed by URDF (MAXSAT-W ) is at least as large as the weight achieved by MAP inference (MAP-W ), and none of the hard constraints are violated by either approach, we conclude that we found an equally good or even better solution. Grounding time (SLD) denotes the time needed to ground the query atoms, soft and hard rules, and to expand the dependency graph via a top-down SLD resolution. In the following, #C and #S denote the number of grounded soft and hard rules (including unit clauses), while jCj and jSj denote the number of occurrences of facts in all grounded soft and hard rules, respectively. The overall query response time (in ms) for URDF is the sum of SLD grounding and MaxSAT solving. Table 1 shows that the URDF MaxSAT solver achieves more than two orders of magnitude runtime improvement over MAP and MC-SAT, at 90 percent precision compared to the MAP baseline for queries Q1–Q10. That is, for 9 out of the 10 queries URDF finds the same MaxSAT weight as MAP, while only for query Q7, the weight returned by URDF is marginally worse. We also see that running MC-SAT is generally more expensive than MAP inference. In this basic setting, 2http://alchemy.cs.washington.edu/
SLD grounding clearly dominates query response times for URDF. However, for all queries we achieve interactive response times with an overall runtime of at most 3 seconds per query. 5.2.2
To systematically investigate the asymptotic behavior of our algorithm for large dependency graphs and more complex rules, we employ synthetic expansions over the basic YAGO setting. In the first expansion setting (Figure 1)(a), we expand each grounded soft rule by 10 distinct facts as noise per expansion step, for each of the query results depicted in Table 1. For the noisy facts, we apply uniform weights and weights following Gaussian distributions (with 2=1) around the original weights ( ) of the YAGO facts. We thus simulate very complex CNF formulas with more than 105 occurrences of facts in soft rules. In the following plots, the grounding time also includes the time for expanding the CNF formulas with these noisy facts and thus is not constant for all runs. Figure 1(a) confirms that the runtime of the MaxSAT algorithm is not affected by the weighting schemes and remains equally efficient.
In the second expansion setting (Figure 1)(b), we do not only vary the number of facts per soft rule, but also the number of grounded soft and hard rules by replicating rules with different combinations of noisy facts. That is, for each original grounded fact, we introduce 10 mutually exclusive facts as noise, and, for each soft rule, we expand the CNF by introducing 10 randomly expanded soft rules at each expansion step. Overlap among soft rules is achieved by uniform-randomly drawing the noisy facts from a static pool of 1,000 synthetic facts for all expansions. We keep Gaussian weights for the expanded facts. This setting yields very large CNF formulas with jCj + jSj ranging from 2,312 to 2,321,488. More specifically, we create constraints with up to 21,277 soft rules and 2,311,551 occurrences of facts in all soft rules, over an overall amount of only 9,937 distinct facts for the last expansion step. In this step, each fact on average occurs in more than 232 rules, each with an average rule length of 108 facts. URDF solves the CNF formulas for this expansion in 15.7 seconds, while remaining at a higher precision in computing the MaxSAT weight as MAP. We measure the approximation precision only for the first three expansion steps, yielding MaxSAT weights of 853:74, 975:02, 1; 099:34 for URDF and 854:58, 937:74, 1; 069:70 for MAP, respectively. MAP does not scale to larger CNFs than in these first three expansions, while MC-SAT cannot be run beyond the first expansion step anymore. 5.2.3
The previous experiments were run over the entire YAGO
knowledge base, using 16 handcrafted rules in a fully recursive fashion.
To measure the cost of deduction over such a large knowledge base
with more general rules, we conduct runs over 42 recursive rules
learned inductively by a variant of FOIL [
Reasoning with inconsistency and uncertainty has been gaining
significant attention in the Database, Semantic Web, and Machine
Learning communities lately. In contrast to related works on
uncertain and probabilistic databases, we consider a more dynamic
way of querying and reasoning with deduction rules for intensional
relations. All database approaches for uncertain data we are aware
of— for example Trio [
Statistical Relational Learning (SRL) has been gaining a strong
momentum in both the Database and Machine Learning
communities, with Markov Logic Networks (MLNs) [
In [
We presented a query-time reasoning approach for uncertain RDF data and SPARQL queries over a combination of soft deduction rules and hard consistency constraints. URDF employs a generalized weighted MaxSAT algorithm that guarantees consistent query answers with regard to the hard constraints. Our experiments confirm that our MaxSAT approximation algorithm yields interactive response times over formulas with many thousands of grounded rules and facts, while empirically performing much better than the provided lower bound of 1/2 for the approximation guarantee. We also saw that, in many cases, the grounding time for the Datalogstyle soft deduction rules is the actual delimiting factor for query response times. Our future work will investigate how to further scale up inference by a combination of dynamic grounding over the highly transient parts of the knowledge base with materialized facts for the more static parts, as well as by distributing our grounding and MaxSAT-based inference strategies.