Preference-based Inconsistency-Tolerant Query Answering under Existential Rules (Discussion Paper) Marco Calautti1 , Sergio Greco2 , Cristian Molinaro2 and Irina Trubitsyna2 1 DISI, University of Trento, Italy 2 DIMES, University of Calabria, Italy Abstract Query answering over inconsistent knowledge bases is a problem that has attracted a great deal of interest over the years. Different 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 different relevant problems. 1. Introduction The problem of querying inconsistent knowledge bases has been investigated for many years. Different inconsistency-tolerant semantics have been proposed in the literature, that is, ap- proaches to provide meaningful query answers despite the knowledge base being inconsistent. Several popular semantics rely on the notion of repair, which is a “maximal” consistent subset of the database. Since inconsistency can be resolved in different ways, in general there are multiple repairs, which are then used in various ways to determine “valid” query answers. For instance, the ABox repair (AR) semantics [1, 2] considers a query answer valid if it can be inferred from each of the repairs of the knowledge base. The intersection of repairs (IAR) semantics [2] considers an answer valid if it can be inferred from the intersection of the repairs. The intersection of closed repairs (ICR) semantics [3] considers an answer valid if it can be inferred from the intersection of the closures of the repairs. We illustrate these semantics in our running example below. Example 1. Consider a knowledge base (𝐷, Σ) describing orders in a restaurant, where 𝐷 is the following database: {meat(beef), order(o), main(o, beef), side(o, cheese), drink(o, red), drink(o, beer), dessert(o, cake), dessert(o, pie)}, SEBD 2021: The 29th Italian Symposium on Advanced Database Systems, September 5-9, 2021, Pizzo Calabro (VV), Italy " marco.calautti@unitn (M. Calautti); greco@dimes.unical.it (S. Greco); cmolinaro@dimes.unical.it (C. Molinaro); trubitsyna@dimes.unical.it (I. Trubitsyna) © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 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(𝑋, 𝑌 ). 1 An extended version of this paper has been accepted to KR 2020 [4]. 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. □ 2. Preliminaries We briefly recall some basics on existential rules from the Datalog± family [5] and inconsistency- tolerant semantics for querying inconsistent knowledge bases. 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 [6]. 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 2 We 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) [5], guarded (G) [7], sticky (S) [8], and acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticky (WS) [8] and weakly acyclic TGDs (WA) [9], as well as their “full” (i.e., existential-free) proper restrictions linear full (LF), guarded full (GF), sticky full (SF), and acyclic full TGDs (AF), respectively, and full TGDs (F) in general. We refer to [10] for an overview of the complexity of BCQ entailment for the above languages. 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 [10] and [11] for an overview of the complexity of AR- and IAR-/ICR-query answer- ing, respectively, for different TGD languages and complexity measures. 3. Preference Rules 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. Definition 3. 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) iff 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 𝜌 iff 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. 𝒦) iff (𝑅, Σ) |= 𝑞(b) implies (𝑅, Σ) |= 𝑝(a). We say that 𝑅 satisfies 𝜌 (w.r.t. 𝒦) iff (𝑅, Σ) |= ∃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 iff 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 differently 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. Definition 8. A prioritized knowledge base 𝒦 = (𝐷, Σ, Π) entails a BCQ 𝑄 under the • PAR semantics if (𝑅, Σ) |= 𝑄, for every 𝑅 ∈ PRep(𝒦). ⋂︀ • IPAR semantics if (𝐷𝐼 , Σ) |= 𝑄, where 𝐷𝐼 = {𝑅 | 𝑅 ∈ PRep(𝒦)}. ⋂︀ • ICPR semantics if (𝐷𝐶 , Σ) |= 𝑄, 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. □ 4. Complexity Results 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. PRC PAR IPAR ICPR Language Data Comb. Data Comb. Data Comb. Data Comb. L, LF, AF PSpace PSpace PSpace PSpace SF Exp Exp Exp Exp F, GF Exp Exp Exp Exp WA coNP 2Exp Πp2 2Exp Πp2 2Exp Πp2 2Exp S Exp Exp Exp Exp- 2Exp A PNExp PNExp PNExp PNExp - ExpNExp G, WS 2Exp 2Exp 2Exp 2Exp- 3Exp Table 1 Data and combined complexity of preferred repair checking and preferred entailment. Table 1 reports the data and combined complexity of the above problems, when considering different TGD languages. A single complexity class in a cell refers to a completeness result, while two classes C1 -C2 refer to C1 -hardness and C2 -membership. In the data complexity, the use of preference rules incurs an increase of complexity w.r.t. the standard setting with no preferences: the data complexity goes from membership in P to coNP-completeness. For the AR and ICR semantics, the data complexity goes from coNP- completeness of the standard setting to Πp2 -completeness of our preferred framework. For the IAR semantics, the data complexity increases from membership in AC0 or coNP-completeness (depending on the language) to Πp2 -completeness. In the combined complexity, moving from the classical semantics to the preferred ones does not yield an increase of complexity, except for the languages S, A, G, and WS under the ICPR semantics. Indeed, despite our efforts, in such cases, we did not manage to obtain completeness results. We point out that some of our results immediately extend to other TGD languages. For example, the Πp2 memberships in data complexity also hold for TGDs classes for which the so-called skolem chase always terminates, e.g. see [12, 13] – for such classes, classical BCQ entailment is always tractable in data complexity. 5. Conclusion Expressing preferences is a common need in various domains, such as querying inconsistent knowledge bases [14, 15], game theory [16], and answer set programming [17]. We have proposed a framework for querying inconsistent knowledge bases under existential rules in the presence of user preferences. We have analyzed the data and combined complexity of different relevant problems for a wide range of existential rule languages. 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 [17, 18]— while we use preferences to determine a set of preferred repairs. Another related framework are (existential) active integrity constraints (EAICs) [19], i.e. in- tegrity constraints that also specify the updates that are allowed to restore consistency when the constraint is violated. Founded repairs are those repairs obtained by applying only allowed updates. This expresses a sort of hard preference by partitioning conflicting facts into allowed and non-allowed ones, while our framework allows us to express preferences among arbitrary facts, and thus do not forbid any fact a priori. Future work. An interesting direction for future work is to extend our analysis to the fixed- program 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 different 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 [20, 21], to our framework with preferences. Finally, considering the intractability of our reasoning tasks, another interesting direction is to consider approximations, i.e., compute a subset of query answers over our semantics in polynomial time, as done in the context of querying incomplete databases [22, 23]. Moreover, one could also consider the counting variants of the PAR semantics, i.e., to count the number of preferred repairs that entail the query (together with the TGDs). This is a more refined measure providing useful insights when the query is not entailed by every preferred repair and has been thoroughly studied in the database setting for different integrity constraints, e.g., see [24, 25, 26, 27]. References [1] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in: Proc. PODS, 1999, pp. 68–79. [2] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics for description logics, in: RR, 2010, pp. 103–117. [3] M. Bienvenu, On the complexity of consistent query answering in the presence of simple ontologies, in: Proc. AAAI, 2012, pp. 705–711. [4] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query answering under existential rules, in: KR, 2020, pp. 203–212. [5] A. Calì, G. Gottlob, T. Lukasiewicz, A general Datalog-based framework for tractable query answering over ontologies, J. Web Sem. 14 (2012) 57–83. [6] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem through logic, in: Proc. LICS, 2014, pp. 43:1–43:10. [7] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174. [8] A. Calì, G. Gottlob, A. Pieris, Towards more expressive ontology languages: The query answering problem, Artif. Intell. 193 (2012) 87–128. [9] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: semantics and query answering, Theor. Comput. Sci. 336 (2005) 89–124. [10] T. Lukasiewicz, M. V. Martinez, A. Pieris, G. I. Simari, From classical to consistent query answering under existential rules, in: Proc. AAAI, 2015, pp. 1546–1552. [11] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering under inconsistency in Datalog+/–, in: Proc. IJCAI, 2018, pp. 1921–1927. [12] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Logic program termination analysis using atom sizes, in: Proc. IJCAI, volume 2015-January, 2015, pp. 2833–2839. [13] M. Calautti, S. Greco, I. Trubitsyna, Detecting decidable classes of finitely ground logic programs with function symbols, ACM Trans. Comput. Log. 18 (2017) 28:1–28:42. [14] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge bases under preferred repair semantics, in: Proc. AAAI, 2014, pp. 996–1002. [15] S. Staworko, J. Chomicki, J. Marcinkowski, Prioritized repairing and consistent query answering in relational databases, Ann. Math. Artif. Intell. 64 (2012) 209–246. [16] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, Non-transferable utility coalitional games via mixed-integer linear constraints, J. Artif. Intell. Res. 38 (2010) 633–685. [17] G. Brewka, I. Niemelä, M. Truszczynski, Answer set optimization, in: Proc. IJCAI, 2003, pp. 867–872. [18] S. Greco, I. Trubitsyna, E. Zumpano, On the semantics of logic programs with preferences, J. Artif. Intell. Res. 30 (2007) 501–523. [19] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential active integrity constraints, Expert Syst. Appl. 168 (2021) 114297. [20] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavicius, Explanations for query answers under existential rules, in: Proc. IJCAI, 2019, pp. 1639–1646. [21] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query answering under existential rules, in: Proc. AAAI, 2020, pp. 2909–2916. [22] N. Fiorentino, S. Greco, C. Molinaro, I. Trubitsyna, ACID: A system for computing approximate certain query answers over incomplete databases, in: Proc. SIGMOD, 2018, pp. 1685–1688. [23] S. Greco, C. Molinaro, I. Trubitsyna, Approximation algorithms for querying incomplete databases, Inf. Syst. 86 (2019) 28–45. [24] S. Greco, C. Molinaro, Probabilistic query answering over inconsistent databases, Ann. Math. Artif. Intell. 64 (2012) 185–207. [25] S. Greco, C. Molinaro, I. Trubitsyna, Computing approximate query answers over incon- sistent knowledge bases, in: IJCAI, 2018, pp. 1838–1846. [26] M. Calautti, M. Console, A. Pieris, Counting database repairs under primary keys revisited, in: D. Suciu, S. Skritek, C. Koch (Eds.), Proc. PODS, ACM, 2019, pp. 104–118. [27] E. Livshits, B. Kimelfeld, J. Wijsen, Counting subset repairs with functional dependencies, J. Comput. Syst. Sci. 117 (2021) 154–164.