Query answering over inconsistent knowledge bases is a problem that has attracted a great deal of interest over the years. Diferent inconsistency-tolerant semantics have been proposed, most of which are based on the notion of repair, that is, a “maximal” consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. We provide generalizations of popular inconsistency-tolerant semantics taking preferences into account and study the data and combined complexity of diferent relevant problems.
stating that beef is a meat dish and o is an order; furthermore, order o has beef for the main course, cheese as side dish, red wine and beer as drinks, and cake and pie as desserts. The ontology Σ contains the following dependencies: 1 : main(, ), meat( ) → hasMeat( ), 2 : drink(, red) → hasWine( ), 3 : drink(, beer) → hasBeer( ), 4 : drink(, ) → hasDrink( ), 5 : main(, ) → ∃ side(, ), 1 : hasBeer( ), hasWine( ) 2 : hasBeer( ), dessert(, ) 3 : hasBeer( ), side(, cheese) 4 : hasWine( ), dessert(, cake), dessert(, pie) → ⊥, → ⊥, → ⊥, → ⊥.
The existential rules 1– 4 specify when an order includes a meat dish, wine, beer, and a drink, respectively. Then, 5 says that a main course always comes with a side dish. The negative constraints 1– 3 say that beer cannot be included in an order together with wine, or a dessert, or cheese. Finally, 4 says that an order cannot include wine, cake, and pie all together.
The knowledge base is clearly inconsistent and admits the following four repairs: 1 = ∖ {drink(o, beer), dessert(o, cake)}, 2 = ∖ {drink(o, beer), dessert(o, pie)}, 3 = ∖ {side(o, cheese), drink(o, red), dessert(o, pie), dessert(o, cake)}, and 4 = ∖ {drink(o, red), drink(o, beer)}. The query = ∃, dessert(, ), asking if some dessert has been ordered, is not entailed under the AR semantics, as repair 3 does not include any dessert. Thus, is not entailed also under the IAR and ICR semantics. □
The AR, IAR, and ICR semantics have been extensively studied for both description logics (DLs) and existential rule languages. In each semantics, all repairs are equally important, and there is no way to prefer one over another. However, in many applications it is natural and desirable to express preferences, e.g., when one data source is more reliable than another, or when information is time-stamped and more recent facts are preferred over earlier ones.
To deal with the scenarios discussed above, we propose a framework for querying inconsistent knowledge bases under user preferences. We enrich knowledge bases with preference rules, so as to narrow down the set of repairs to a set of preferred ones. We then define preferred counterparts of the AR, IAR, and ICR semantics by looking only at preferred repairs.1 Example 2. Consider again the scenario of Example 1. Suppose we would like to express preferences among repairs in such a way that the presence of some items in an order determines what other items are preferred. In our framework, one could specify this kind of preferences by means of the following set Π of preference rules: 1 : hasWine( ) ≻ hasBeer( ) ← hasMeat( ), 2 : dessert(, cake) ≻ dessert(, cherries) ← main(, ), 3 : dessert(, pie) ≻ dessert(, cake) ← ∃ hasDrink( ), side(, ).
1An extended version of this paper has been accepted to KR 2020 [
The first preference rule says that when an order includes meat, wine is preferred over beer. The second preference rule states that when an order includes a main course, cake is preferred over cherries. The third preference rule says that when an order includes a drink and some side dish, pie is preferred over cake.
We will see later that 1 and 4 (cf. Example 1) are the repairs that best satisfy the above preference rules, and thus they are preferred. Only preferred repairs are considered in the definition of preferred inconsistency-tolerant semantics. Thus, for instance, query of Example 1 is entailed under our preferred AR, IAR, and ICR semantics. □
We briefly recall some basics on existential rules from the Datalog ± family [
General. We assume a set C of constants, a set N of labeled nulls, and a set V of variables. A
term is a constant, null, or variable. We also assume a set of predicates, each associated with an
arity, i.e., a non-negative integer. An atom has the form (t), where is an -ary predicate, and
t is a tuple of terms. An atom containing only constants is also called a fact. Conjunctions
of atoms are often identified with the sets of their atoms. An instance is a (possibly infinite)
set of atoms (t), with t a tuple of constants and nulls. A database is a finite instance with
only constants. A homomorphism is a substitution ℎ from terms to terms that is the identity
on C and maps N to C ∪ N. With abuse of notation, homomorphisms are applied also to
(sets/conjunctions of) atoms. A (Boolean) conjunctive query (BCQ) has the form ∃X (X),
where X is a tuple of variables, and (X) is a conjunction of atoms over the variables in X
without nulls. An instance satisfies , denoted |= , if there is a homomorphism ℎ with
ℎ( (X)) ⊆ .2
Dependencies. A tuple-generating dependency (TGD) is a first-order formula of the form
∀X∀Y (X, Y) → ∃Z (X, Z), where X, Y, and Z are pairwise disjoint tuples of variables,
(X, Y) is a conjunction of atoms over X, Y, and (X, Z) is an atom, all without nulls;
(X, Y) is the body of , denoted body ( ), while (X, Z) is the head of , denoted head ( ).
For clarity, we consider single-atom-head TGDs; however, our results extend to TGDs with a
conjunction of atoms in the head. An instance satisfies , written |= , if the following
holds: whenever there exists a homomorphism ℎ such that ℎ( (X, Y)) ⊆ , then there exists
ℎ′ ⊇ ℎ|X, where ℎ|X is the restriction of ℎ on X, such that ℎ′((X, Z)) ∈ . A negative
constraint (NC) is a first-order formula ∀X (X) → ⊥, with X a tuple of variables, (X)
is a conjunction of atoms over X, without nulls, called the body of and denoted body ( ),
and ⊥ denotes the truth constant false. An instance satisfies , written |= , if does not
satisfy the BCQ ∃X (X). Negative constraints that are not satisfied can be represented via
hypergraphs [
Given a set Σ of TGDs and NCs, satisfies Σ , written |= Σ , if satisfies each TGD and NC of Σ . For brevity, we omit the universal quantifiers in front of TGDs and NCs, and use the comma for conjoining atoms. Given a class of TGDs ℒ, we denote by ℒ⊥ the formalism obtained 2We focus on Boolean queries for clarity, but all our results immediately extend to non-Boolean conjunctive queries. by combining ℒ with arbitrary NCs. Finite sets of TGDs and NCs are also called programs, and TGDs are also called existential rules.
Knowledge Bases. A knowledge base is a pair (, Σ) , where is a database and Σ is a program. The set of models of KB = (, Σ) , denoted mods(KB ), is the set of instances { | ⊇ ∧ |= Σ }. We say that KB is consistent if mods(KB ) ̸= ∅, otherwise KB is inconsistent. We say that KB entails a BCQ , denoted KB |= , if |= , for each ∈ mods(KB ). The data complexity considers only the database as part of the input, while the combined complexity considers everything as part of the input.
The Datalog± languages that we consider to guarantee decidability are among the most
frequently analysed in the literature, namely, linear (L) [
Inconsistency-Tolerant Semantics. We now recall the AR, IAR, and ICR semantics.
Let KB = (, Σ) be a knowledge base. A repair of KB is an inclusion-maximal subset of such that (, Σ) is consistent. We use Rep(KB ) to denote the set of all repairs of KB . The closure Cn(KB ) of KB is the set of all facts (thus containing constants only) entailed by and the TGDs of Σ . KB entails a BCQ under the • AR semantics if (, Σ) |= , for each ∈ Rep(KB ). • IAR semantics if ( , Σ) |= , where = ⋂︀{ | ∈ Rep(KB )}.
• ICR semantics if ( , Σ) |= , where = ⋂︀{Cn((, Σ)) | ∈ Rep(KB )}.
We refer to [
In this section, we introduce the syntax and semantics of preference rules, which allow users to express preferences among repairs. The aim is to use such rules to identify a set of preferred repairs among all possible ones, and use only the preferred repairs for AR, IAR, and ICR entailment.
Syntax. The syntax of preference rules is as follows.
A preference rule is an expression of the form (X) ≻ (Y) ← ∃
Z (Z, W), where X, Y, Z, and W are tuples of variables such that X ∩ Z = Y ∩ Z = ∅, (X) and (Y) are atoms over the variables X and Y, respectively, and (Z, W) is a (possibly empty) conjunction of atoms over the variables Z ∪ W, all without nulls. □
In the previous definition, the right-hand (resp., left-hand) side of ← is called the body (resp., head) of and is denoted as body ( ) (resp., head ( )). Intuitively, the head expresses a preference among two atoms, while the body expresses a precondition for such a preference to be applied. A preference rule is ground if all its variables are existentially quantified, that is, it has the form (a) ≻ (b) ← ∃ Z (Z, c), with a, b, c tuples of constants and Z a tuple of variables. A preference program is a finite set of preference rules. A prioritized knowledge base combines a knowledge base with a preference program.
Definition 4. A prioritized knowledge base is a triple (, Σ , Π) , where is a database, Σ is a program, and Π is a preference program. □
We say that is consistent (resp., inconsistent) if the knowledge base (, Σ) is consistent (resp., inconsistent). The set of all repairs of , denoted Rep(), is the set of all repairs of (, Σ) . An example of prioritized knowledge base = (, Σ , Π) is the one presented in Examples 1–2.
Semantics. Consider a prioritized knowledge base = (, Σ , Π) . We use C to denote the set of all constants appearing in (that is, appearing in , Σ , or Π ). A ground instance of a preference rule ∈ Π is a ground preference rule derived from by replacing every non-existential variable with a constant in C, with multiple occurrences of the same variable being replaced with the same constant. We use grnd ( ) to denote the set of all ground instances of , and define grnd (Π) = ⋃︀ ∈Π grnd ( ). To define preferred repairs, we first need to define when a repair satisfies a ground preference rule.
Intuitively, a repair satisfies a ground preference rule if whenever (together with the ontology) entails the body of , the head of is fulfilled by . We formally define these notions below. For a prioritized knowledge base = (, Σ , Π) , by consistent subset of we mean a set ⊆ such that (, Σ) is consistent.
Definition 5. Let = (, Σ , Π) be a prioritized knowledge base, a consistent subset of , and a ground preference rule in grnd (Π) of the form (a) ≻ (b) ← ∃ Z (Z, c). We say that fulfills (a) ≻ (b) (w.r.t. ) if (, Σ) |= (b) implies (, Σ) |= (a). We say that satisfies (w.r.t. ) if (, Σ) |= ∃Z (Z, c) implies fullfils (a) ≻ (b) w.r.t. . □
Notice that we do not transitively close preferences. In contrast, we look for an explicit preference rule saying that (a) is preferred over (b). A transitive closure would require (iteratively) adding a ground preference rule ≻ ← body 1, body 2 for each pair of ground preference rules ≻ ← body 1 and ≻ ← body 2, which can yield an exponential blow-up in the number of preference rules. Nonetheless, if needed, transitivity can still be stated by explicitly including a transitive closure in Π .
For a repair of a prioritized knowledge base = (, Σ , Π) , we use (, ) to denote the set of all preference rules in grnd (Π) that are satisfied by (w.r.t. ). We define preferred repairs as follows.
Definition 6. A repair of a prioritized knowledge base is preferred if there is no repair ′ of s.t. (, ) ⊊ (′, ). The set of all preferred repairs of is denoted as PRep(). □
Thus, preferred repairs satisfy an inclusion-maximal set of ground preference rules. Other criteria are possible, such as defining preferred repairs as those that satisfy a cardinality-maximal set of preference rules. All such approaches are interesting, in much the same way as cardinality and set-inclusion maximality are both interesting when defining (standard) repairs. We plan to investigate other criteria in future work.
Example 7. Consider the prioritized knowledge base = (, Σ , Π) and repairs 1–4 of Examples 1–2. First of all, note that only ground preference rules in grnd (Π) whose body contains order o can be diferently satisfied by 1–4, as the body of any other ground preference rule in grnd (Π) is never entailed by (, Σ) , for each ∈ {1, 2, 3, 4}. Thus, such preference rules are satisfied by all repairs. Hence, we can focus on these three ground preference rules: ′1 : hasWine(o) ≻ hasBeer(o) ← hasMeat(o), ′2 : dessert(o, cake) ≻ dessert(o, cherries) ← main(o, beef), ′3 : dessert(o, pie) ≻ dessert(o, cake) ← ∃ hasDrink(o), side(o, ).
Notice that ′1 is applicable in all repairs. Repairs 1 and 2 satisfy ′1 because they both contain red wine; 4 satisfies ′1 because it does not include any wine or beer; 3 does not satisfy ′1 because it includes beer and no wine.
The preference rule ′2 is applicable in all repairs as well, and it is satisfied by all of them, essentially because none of them contain dessert(o, cherries).
Finally, 1, 3, and 4 satisfy ′3, while 2 does not. Thus, 1 and 4 satisfy all preference rules, while 2 and 3 do not, and thus 1 and 4 are preferred. □
We now provide our inconsistency-tolerant semantics over preferred repairs.
A prioritized knowledge base = (, Σ , Π) entails a BCQ under the • PAR semantics if (, Σ) • IPAR semantics if ( , Σ) • ICPR semantics if ( , Σ) |= , for every ∈ PRep().
|= , where = ⋂︀{ | ∈ PRep()}. |= , where = ⋂︀{Cn((, Σ)) | ∈ PRep()}.
□ Example 9. Consider again the prioritized knowledge base and the query from Examples 1– 2. The preferred repairs of are PRep() = {1, 4} (cf. Example 7). Then, entails under the PAR, IPAR, and ICPR semantics, while is not entailed under any of the standard inconsistency-tolerant semantics. □
We performed a thorough study of the data and combined complexity of the “preferred” variant of classical problems in the context of querying inconsistent knowledge bases. The first problem, which we dub Preferred Repair Checking (PRC), given a prioritized knowledge base and a database ′, asks whether ′ ∈ PRep(). The remaining problems, called -Entail, with ∈ {PAR, IPAR, ICPR}, given a prioritized knowledge base and a BCQ , ask whether entails under the semantics.
Language Comb.
PSpace
Exp Exp 2Exp Exp PNExp 2Exp
Data Π p2
Comb.
PSpace
Exp Exp 2Exp Exp PNExp 2Exp
Data Π p2
Comb.
PSpace
Exp Exp 2Exp Exp PNExp 2Exp
Data Π p2
Comb.
PSpace
Exp Exp 2Exp
Exp- 2Exp PNExp- ExpNExp 2Exp- 3Exp
Expressing preferences is a common need in various domains, such as querying inconsistent
knowledge bases [
Related work. In the context of logic programming, logic programs have been combined
with preferences so as to determine a set of preferred answer sets—e.g., see [
Another related framework are (existential) active integrity constraints (EAICs) [
Future work. An interesting direction for future work is to extend our analysis to the
fixedprogram combined complexity, that is, when the ontology is assumed to be fixed, and to the
bounded-arity combined complexity, that is, when it is assumed that the maximum arity of the
predicates is bounded by an integer constant. Another direction for future work is to apply
preferences rules to diferent kinds of repairs, e.g., cardinality-maximal ones. Also, it would
be interesting to extend the notion of an explanation, already investigated under existential
rules [