Vol-3194/paper62
Wolfgang Fahl
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3194/paper62 |
| wikidataid | Q117344960→Q117344960 |
| title | Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- under Cardinality-Based Repairs |
| pdfUrl | https://ceur-ws.org/Vol-3194/paper62.pdf |
| dblpUrl | https://dblp.org/rec/conf/sebd/LukasiewiczMV22 |
| volume | Vol-3194→Vol-3194 |
| session | → |
Paper[edit]
| Paper | |
|---|---|
| edit
| |
| description | |
| id | Vol-3194/paper62 |
| wikidataid | Q117344960→Q117344960 |
| title | Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- under Cardinality-Based Repairs |
| pdfUrl | https://ceur-ws.org/Vol-3194/paper62.pdf |
| dblpUrl | https://dblp.org/rec/conf/sebd/LukasiewiczMV22 |
| volume | Vol-3194→Vol-3194 |
| session | → |
Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- under Cardinality-Based Repairs[edit]
Complexity of Inconsistency-Tolerant Query
Answering in Datalog+/– under Cardinality-Based
Repairs⋆
(Discussion Paper)
Thomas Lukasiewicz1 , Enrico Malizia2 and Andrius Vaicenavičius1
1
Department of Computer Science, University of Oxford, UK
2
DISI, University of Bologna, Italy
Abstract
Querying inconsistent ontological knowledge bases is an important problem in practice, for which
several inconsistency-tolerant semantics have been proposed. In these semantics, the input database is
erroneous, and a repair is a maximally consistent database subset. Different notions of maximality (such
as subset and cardinality maximality) have been considered. In this paper, we give a precise picture of
the computational complexity of inconsistency-tolerant query answering in a wide range of Datalog+/–
languages under the cardinality-based versions of three prominent repair semantics.
Keywords
Knowledge representation, Existential rules, Inconsistencies, Query answering, Complexity
1. Introduction
In many ontology-based applications, such as ontology-based data extraction from the Web, or
ontology-based integration of different data sources, it is very likely that the data are inconsis-
tent with the ontology, and thus inconsistency-tolerant semantics for ontology-based query
answering are urgently needed. Among the most prominent ontology languages are description
logics (DLs) [2] and existential rules from the context of Datalog± [3].
The most widely accepted semantics for querying inconsistent ontological knowledge bases is
perhaps consistent query answering (CQA), which was first developed for relational databases [4]
and then generalized as the ABox repair (AR) semantics for several DLs [5]. Consistent query
answering is based on the concept of repair, which is a maximal consistent subset of the
input database. A fact/query is entailed by an ontological knowledge base in consistent query
answering, if it is (classically) entailed by all the repairs (under the ontology). Several other
repair semantics for querying inconsistent knowledge bases have recently been developed as
alternatives. In the intersection of repairs (IAR) semantics [5], an answer is considered to be
SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy
⋆
This is a short version of the AAAI-19 paper [1].
$ thomas.lukasiewicz@cs.ox.ac.uk (T. Lukasiewicz); enrico.malizia@unibo.it (E. Malizia);
andrius.vaicenavicius@cs.ox.ac.uk (A. Vaicenavičius)
� 0000-0002-7644-1668 (T. Lukasiewicz); 0000-0002-6780-4711 (E. Malizia)
© 2022 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)
�valid, if it can be inferred from the intersection of the repairs (and the ontology). The intersection
of closed repairs (ICR) [6] is another semantics, in which an answer is valid, if it can be inferred
from the intersection of the closure of the repairs (and the ontology). Recently, the AR semantics
was extended to the generalized repair (GR) semantics [7]. In the GR semantics, also ontological
rules may be removed. This generalization was extended to the IAR and ICR semantics in [8]
Interestingly, the IAR and the ICR semantics can be seen as under-approximation of the AR
semantics and analyzing their complexity helps to understand whether such approximations
have actually lower complexities (see also [9, 10] for other approximation approaches). Beside
this, a crucial advantage of the IAR and the ICR semantics is that their intersection of (closed)
repairs can be materialized [11, 12], while the AR semantics exists only virtually.
The complexity of consistent query answering when the ontology is described via one of
the main DLs is well-understood. Rosati [13] studied the data and combined complexity for a
wide spectrum of DLs, while Bienvenu [6] identified cases for simple ontologies (within the
DL-Lite family) for which tractable data complexity results can be obtained. In [14], the data
and different types of combined complexity of consistent query answering have been studied
for ontologies described via existential rules and negative constraints.
Alternative maximality notions for repairs, such as cardinality-maximal repairs [15], rather
than subset-maximal ones, have been explored less. Bienvenu et al. [16] analyzed the data
and the combined complexity of query answering under the AR and IAR semantics over the
language DL-Liteℛ for various notions of maximal repairs, among which maximum cardinality.
This paper continues this line of research on cardinality-maximal consistent query answering,
and we analyze the complexity of the above three inconsistency-tolerant query answering
semantics for a wide range of Datalog± languages and for several different complexity measures.
2. Preliminaries
We here briefly recall some basics on existential rules from the context of Datalog± [3].
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 assume a set of predicates, each associated with an arity.
An atom has the form 𝑝(𝑡1 , . . . , 𝑡𝑛 ), where 𝑝 is an 𝑛-ary predicate, and 𝑡1 , . . . , 𝑡𝑛 are terms. An
atom containing only constants is called fact. Conjunctions of atoms are also identified with
the sets of their atoms. An instance 𝐼 is a (possibly infinite) set of atoms defined over constants
and nulls. A database 𝐷 is a finite instance containing only constants. A homomorphism is a
substitution ℎ : C ∪ N ∪ V ↦→ C ∪ N ∪ V that is the identity on C and maps N to C ∪ N. With
a slight abuse of notation, homomorphisms are applied also to (sets/conjunctions of) atoms. A
conjunctive query (CQ) 𝑞 has the form ∃Y𝜑(X, Y), where 𝜑(X, Y) is a conjunction of atoms
without nulls. The answer to 𝑞 over an instance 𝐼, denoted 𝑞(𝐼), is the set of all |X|-tuples
t over C for which there is a homomorphism ℎ such that ℎ(𝜑(X, Y)) ⊆ 𝐼 and ℎ(X) = t. A
Boolean CQ (BCQ) 𝑞 is a CQ ∃Y𝜑(Y), i.e., all variables are existentially quantified; 𝑞 is true
over 𝐼, denoted 𝐼 |= 𝑞, if 𝑞(𝐼) ̸= ∅, i.e., there is a homomorphism ℎ with ℎ(𝜑(Y)) ⊆ 𝐼.
Dependencies. A tuple-generating dependency (TGD) 𝜎 is an FO formula ∀X∀Y 𝜙(X, Y) →
∃Z 𝑝(X, Z), where X, Y, and Z are pairwise disjoint sets of variables, 𝜙(X, Y) is a conjunction
of atoms, and 𝑝(X, Z) is an atom, all without nulls. An instance 𝐼 satisfies 𝜎, written 𝐼 |= 𝜎,
�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) → ⊥, where X ⊆ V, 𝜙(X) is a conjunction of atoms without
nulls, and ⊥ denotes the truth constant false. An instance 𝐼 satisfies 𝜈, written 𝐼 |= 𝜈, if there
is no homomorphism ℎ such that ℎ(𝜙(X)) ⊆ 𝐼. 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 (instead of ∧) for conjoining atoms.
For a TGD class C, C⊥ denotes the formalism obtained by combining C with arbitrary NCs.
Finite sets of TGDs and NCs are also called programs, and TGDs are also called existential rules.
The Datalog± languages ℒ that we consider to guarantee decidability are among the most
frequently analyzed in the literature, namely, linear (L) [3], guarded (G) [17], sticky (S) [18], and
acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticky (WS) [18] and
weakly acyclic TGDs (WA) [19], 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 also recall the following further inclusions: L ⊂ G and
F ⊂ WA ⊂ WS. We refer to [14] for a more detailed overview.
Knowledge Bases. A knowledge base is a pair (𝐷, Σ), where 𝐷 is a database, and Σ is a program.
For a program Σ, Σ𝑇 and ΣNC denote the TGDs and NCs subsets, respectively, of Σ. The set
mods(KB ) of models of KB = (𝐷, Σ) is the set of instances {𝐼 | 𝐼 ⊇ 𝐷 ∧ 𝐼 |= Σ}; KB is
consistent if mods(KB ) ̸= ∅,⋂︀otherwise KB is inconsistent. The answer to a CQ 𝑞 w.r.t. KB is the
set of tuples ans(𝑞, KB ) = {𝑞(𝐼) | 𝐼 ∈ mods(KB )}. The answer to a BCQ 𝑞 is true, denoted
KB |= 𝑞, if ans(𝑞, KB ) ̸= ∅. Another way to define the existential rules semantics is via the
concept of the Chase (see, e.g., [20, 21]). The decision version of the CQ answering problem is:
for a knowledge base KB , a CQ 𝑞, and a tuple of constants t, decide whether t ∈ ans(𝑞, KB ).
Since CQ answering can be reduced in logspace to BCQ answering, we focus on BCQs. BCQ(ℒ)
denotes the problem of BCQ answering when restricted over programs belonging to ℒ.
Following Vardi [22], the combined complexity of BCQ answering considers the database,
the set of dependencies, and the query as part of the input. The bounded-arity-combined (or
ba-combined) complexity assumes that the arity of the underlying schema is bounded by an
integer constant. The fixed-program-combined (or fp-combined) complexity considers the sets of
TGDs and NCs as fixed; the data complexity also assumes the query fixed. Table 1 recalls the
complexity results of BCQ answering for the languages here considered [14].
A language ℒ is FO-rewritable if given any program Σ ∈ ℒ and any BCQ 𝑞, there exists an
FO-query 𝑞Σ such that, for all databases 𝐷 we have that (𝐷, Σ) |= 𝑞 iff 𝐷 |= 𝑞Σ . All languages
from Table 1 with ac0 data complexity are FO-rewritable.
Inconsistency-Tolerant Semantics. In classical BCQ answering, an inconsistent knowledge
base entails every query, as everything follows from a contradiction. Clearly, the answers
obtained in such cases are not meaningful. Three prominent inconsistency-tolerant semantics for
query answering under existential rules are the ABox repair (AR) semantics, its approximation
by the intersection of repairs (IAR), and the intersection of closed repairs (ICR) semantics [5, 6];
all three are based on the notion of repair, which is a maximal consistent subset of the database.
Symmetrically, the concept of repair is linked to that of culprit. Intuitively, a culprit is a
minimal subset of 𝐷 that, together with Σ𝑇 entails some NC; a culprit for an NC is a “minimal
�Table 1
Complexity of BCQ answering under existential rules [14].
ℒ Data fp-comb. ba-comb. Comb.
0
L, LF, AF ≤ ac np np pspace
S, SF ≤ ac0 np np exp
A ≤ ac0 np nexp nexp
G p np exp 2exp
F, GF p np np exp
WS, WA p np 2exp 2exp
WG exp exp exp 2exp
explanation” [23, 24] of the NC. By deleting from 𝐷 a minimal hitting set [25, 26, 27] of facts 𝑆
intersecting all culprits, we obtain a repair 𝑅 = 𝐷 ∖ 𝑆.
We now define inconsistency-tolerant semantics for a generic concept of repair maximality.
Given a knowledge base KB = (𝐷, Σ), a selection 𝐷′ of KB is a database such that 𝐷′ ⊆ 𝐷.
A selection 𝐷′ of KB is consistent, if mods((𝐷′ , Σ)) ̸= ∅. Consistent selections of knowledge
bases can be ordered according to some criteria to select the more desired ones. Given a preorder
≼ over a set 𝒮 of databases, for two elements 𝐷′ , 𝐷′′ ∈ 𝒮, 𝐷′ ≺ 𝐷′′ denotes that 𝐷′ ≼ 𝐷′′ and
𝐷′′ ̸≼ 𝐷′ . A database 𝐷 ∈ 𝒮 is ≼-maximal in 𝒮 iff there is no 𝐷′ ∈ 𝒮 such that 𝐷 ≺ 𝐷′ .
Definition 1. A ≼-repair of a knowledge base KB is a consistent selection of KB that is
≼-maximal in the set of all the consistent selections of KB .
We now define the three different inconsistency-tolerant semantics for BCQ answering.
Rep ≼ (KB ) denotes the set of all ≼-repairs of KB . The closure Cl (KB ) of KB is the set of all
facts built from constants in 𝐷 and Σ, entailed by 𝐷 and the TGDs of Σ.
Definition 2. Let KB be a knowledge base, let 𝑞 be a BCQ, and let ≼ be an order over the
consistent selections of KB .
• KB entails 𝑞 under the ABox repair semantics and order ≼ (≼-AR), denoted by KB |=≼-AR 𝑞,
if, for all 𝐷′ ∈ Rep ≼ (KB ), (𝐷′ , Σ) |= 𝑞.
• KB entails 𝑞 under the intersection of repairs⋂︀ semantics and order ≼ (≼-IAR), denoted by
KB |=≼-IAR 𝑞, if (𝐷* , Σ) |= 𝑞, where 𝐷* = {𝐷′ | 𝐷′ ∈ Rep ≼ (KB )}.
• KB entails 𝑞 under the intersection of closed repairs
⋂︀ semantics and order ≼ (≼-ICR), denoted
by KB |=≼-ICR 𝑞, if (𝐷𝐼 , Σ) |= 𝑞, where 𝐷𝐼 = {Cl ((𝐷 , Σ)) | 𝐷′ ∈ Rep ≼ (KB )}.
′
An interesting class of repairs are those selected by the cardinality order ‘≤’ [16]. A ≤-repair
of a knowledge base KB is a maximum cardinality consistent selection of KB . Here, we consider
only the ‘≤’ order, hence, we often call ≤-repairs simply repairs, and by Rep(KB ), we mean
Rep ≤ (KB ). Cardinality-maximal repairs are very appropriate when it is known (or believed)
that all the facts in the database have the same (possibly small) probability of being erroneous.
In these cases, larger repairs are preferred, because fewer facts are dropped [16]. When facts in
the database have different likelihoods of being erroneous, then other concepts of repairs can
also be taken into consideration [6, 28].
�Table 2
Complexity of ≤-AR/IAR/ICR BCQ answering—all completeness results. + Different membership
proof for AR/IAR in [16]. * Different hardness proof for AR/IAR for L⊥ , G⊥ , S⊥ , and WS⊥ , in [16].
≤-AR BCQ answering ≤-IAR/ICR BCQ answering
ℒ Data fp-comb. ba-comb. Comb. Data fp-comb. ba-comb. Comb.
L⊥ , LF⊥ , AF⊥ Θp2 +* Πp2 Θp3 pspace Θp2 +* Θp2 Θp3 pspace
S⊥ , SF⊥ Θp2 +* Πp2 Θp3 exp Θp2 +* Θp2 Θp3 exp
A⊥ Θp2 + Πp2 nexp
p pnexp Θp2 + Θp2 pnexp pnexp
G⊥ Θp2 +* Πp2 exp 2exp Θp2 +* Θp2 exp 2exp
F⊥ , GF⊥ Θp2 + Πp2 Θp3 exp Θp2 + Θp2 Θp3 exp
WS⊥ , WA⊥ Θp2 +* Πp2 2exp 2exp Θp2 +* Θp2 2exp 2exp
WG⊥ exp exp exp 2exp exp exp exp 2exp
3. Complexity Analysis
Compared to the case where subset maximality is considered, using maximum cardinality in
several cases comes at a cost, needed to compute the largest repair’s size. However, this is
sometimes masked out by the complexity of classical/AR/IAR/ICR BCQ answering. Compared
to ≤-AR-BCQ answering, the complexity of ≤-IAR- and ≤-ICR-BCQ answering slightly drops
and is the same. Their complexity is the same because the complexity of either classical BCQ
reasoning or of computing the biggest repairs’ size dominate the task’s complexity. Therefore, in
this setting ICR has an advantage over IAR, as ICR is a finer AR’s approximation than IAR.
3.1. Membership Results
A first result allows us to show most of the complexity upper-bounds of Table 2. The intuition
behind this theorem is as follows. First we can compute the size of the biggest repairs via a
binary search, then through some additional oracle calls it is possible to check whether the
query is entailed or not under the inconsistency-tolerant semantics (see [1] for more details).
Theorem 3. Let 𝐿 be a Datalog± language. If BCQ answering from knowledge bases over 𝐿 is
in C in the data / ba-combined / combined complexity (resp., data / ba-combined complexity),
then ≤-AR and ≤-IAR (resp., ≤-ICR) BCQ answering from knowledge bases over 𝐿 is in p
with an oracle for npC [𝑂(log 𝑛)] in the data / ba-combined / combined complexity (resp., data /
ba-combined complexity).
The previous result relies on the guess of a query entailment disprover to be passed to the
oracle. However, this cannot be done for the ICR case in the combined complexity, as the guess
might need be too large. We hence need a tailored proof analyzing all languages case by case.
Theorem 4. ≤-ICR BCQ answering in the combined complexity from knowledge bases over
Datalog± the languages 𝐿 here considered is in the complexity classes shown in Table 2.
For the upper-bounds in the fp-combined setting, we can actually provide tighter ones, as
checking the consistency of a set of facts is feasible in the complexity class of BCQ answering
in the data complexity (and not in the fp-complexity), because the NCs are fixed.
�Theorem 5. If BCQ answering from knowledge bases over a Datalog± language 𝐿 is in D in the
data complexity and in C in the fp-combined complexity, then ≤-AR (resp., ≤-IAR and ≤-ICR)
BCQ answering from knowledge bases over 𝐿 is possible by a computation in p with an oracle
for npD [𝑂(log 𝑛)], followed by a computation in co-npC (resp., C), in the fp-combined complexity.
3.2. Hardness Results
We can show matching lower-bounds for the upper-bounds found in the previous section.
The following result is via a reduction from the Θp2 -complete problem InAllMaxIS [15]: for
a graph 𝐺 and a vertex 𝑤, decide if 𝑤 belongs to all the max-size independent sets of 𝐺.
Theorem 6. For every 𝐶 ∈ {AR, IAR, ICR}, ≤-C BCQ answering from knowledge bases over
LF⊥ , AF⊥ , and SF⊥ is Θp2 -hard in the data complexity.
For the next result, the reduction is from the classical Πp2 -complete problem of deciding the
validity of a QBF ∀𝑋∃𝑌 𝜑(𝑋, 𝑌 ).
Theorem 7. ≤-AR BCQ answering from knowledge bases over LF⊥ , AF⊥ , and SF⊥ is Πp2 -hard
in the fp-combined complexity.
The Θp3 -hardness of the following problems is via a reduction from the Θp3 -complete problem
Comp-Valid2 : given sets 𝐴 and 𝐵 of QBFs with 2 alternating quantifiers, decide whether the
number of valid formulas in 𝐴 is bigger than the number of valid formulas in 𝐵 [29] (this is a
generalization of the Comp-SAT problem [30]).
Theorem 8. For every 𝐶 ∈ {AR, IAR, ICR}, ≤-C BCQ answering from knowledge bases over
LF⊥ , AF⊥ , and SF⊥ is Θp3 -hard in the ba-combined complexity.
The next hardness is obtained via a reduction from the following pnexp -hard problem [14]: for
a triple (𝑚, TP 1 , TP 2 ), where 𝑚 is an integer in unary notation, and TP 1 and TP 2 are two
tiling problems for the exponential square 2𝑛 × 2𝑛 , decide whether there is an initial condition
𝑤 of length 𝑚, such that TP 1 has no solution with 𝑤, and TP 2 has a solution with 𝑤.
Theorem 9. For any 𝐶 ∈ {AR, IAR, ICR}, ≤-C BCQ answering for A⊥ are pnexp -hard in the
ba-combined and combined complexity.
The remaining hardness results follows from the hardness of BCQ answering.
4. Summary and Outlook
We have analyzed BCQ answering under different cardinality-maximal inconsistency-tolerant
semantics, for the most popular Datalog± languages and complexity measures.
Future research include defining other semantics for inconsistency-tolerant ontological query
answering, considering weighed repairs and more elaborate user preferences over repairs [31,
32, 33, 34, 35]. Also, in the line of a more recent research, it would be interesting to extend the
concepts of explanations for inconsistency-tolerant query answering [36, 37] to cardinality-
maximal repairs, and mix this with the notions of preferred explanations [38] and explanations
for negative query answers [39].
�Acknowledgments
This work was supported by the Alan Turing Institute under the UK EPSRC grant EP/N510129/1,
and by the EPSRC grants EP/R013667/1, EP/L012138/1, and EP/M025268/1.
References
[1] T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Complexity of inconsistency-tolerant query
answering in Datalog+/– under cardinality-based repairs, in: AAAI, 2019, pp. 2962–2969.
[2] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The
Description Logic Handbook, 2nd ed., Cambridge University Press, 2007.
[3] A. Calì, G. Gottlob, T. Lukasiewicz, A general Datalog-based framework for tractable query
answering over ontologies, J. Web Sem. 14 (2012) 57–83.
[4] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases,
in: PODS, 1999, pp. 68–79.
[5] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics
for description logics, in: RR, 2010, pp. 103–117.
[6] M. Bienvenu, On the complexity of consistent query answering in the presence of simple
ontologies, in: AAAI, 2012, pp. 705–711.
[7] T. Eiter, T. Lukasiewicz, L. Predoiu, Generalized consistent query answering under exis-
tential rules, in: KR, 2016, pp. 359–368.
[8] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering
under inconsistency in Datalog± , in: IJCAI, 2018, pp. 1921–1927.
[9] S. Greco, C. Molinaro, Probabilistic query answering over inconsistent databases, Ann.
Math. Artif. Intell. 64 (2012) 185–207.
[10] S. Greco, C. Molinaro, I. Trubitsyna, Computing approximate query answers over incon-
sistent knowledge bases, in: IJCAI, 2018, pp. 1838–1846.
[11] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant query
answering in ontology-based data access, J. Web Sem. 33 (2015) 3–29.
[12] M. Bienvenu, C. Bourgaux, Inconsistency-tolerant querying of description logic knowledge
bases, in: Reasoning Web, 2016, pp. 156–202.
[13] R. Rosati, On the complexity of dealing with inconsistency in description logic ontologies,
in: IJCAI, 2011, pp. 1057–1062.
[14] T. Lukasiewicz, E. Malizia, M. V. Martinez, C. Molinaro, A. Pieris, G. I. Simari, Inconsistency-
tolerant query answering for existential rules, Artif. Intell. 307 (2022) art. no. 103685.
[15] A. Lopatenko, L. E. Bertossi, Complexity of consistent query answering in databases under
cardinality-based and incremental repair semantics, in: ICDT, 2007, pp. 179–193.
[16] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge
bases under preferred repair semantics, in: AAAI, 2014, pp. 996–1002.
[17] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive
relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174.
[18] A. Calì, G. Gottlob, A. Pieris, Towards more expressive ontology languages: The query
answering problem, Artif. Intell. 193 (2012) 87–128.
�[19] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: Semantics and query answering,
Theor. Comput. Sci. 336 (2005) 89–124.
[20] E. Tsamoura, D. Carral, E. Malizia, J. Urbani, Materializing knowledge bases via trigger
graphs, VLDB Endow. 14 (2021) 943–956.
[21] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Exploiting equality generating dependen-
cies in checking chase termination, VLDB Endow. 9 (2016) 396–407.
[22] M. Vardi, The complexity of relational query languages, in: STOC, 1982, pp. 137–146.
[23] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers
under existential rules, in: IJCAI, 2019, pp. 1639–1646.
[24] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for ontology-
mediated query answering in description logics, in: ECAI, 2020, pp. 672–679.
[25] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, SIAM J. Comput. 47 (2018) 456–492.
[26] J. Chomicki, J. Marcinkowski, Minimal-change integrity maintenance using tuple deletions,
Inf. Comput. 197 (2005) 90–121.
[27] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, in: LICS, 2014, pp. 43:1–43:10.
[28] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant
query answering under existential rules, in: KR, 2020, pp. 203–212.
[29] T. Lukasiewicz, E. Malizia, A novel characterization of the complexity class Θ𝑃𝑘 based on
counting and comparison, Theor. Comput. Sci. 694 (2017) 21–33.
[30] T. Lukasiewicz, E. Malizia, On the complexity of 𝑚CP-nets, in: AAAI, 2016, pp. 558–564.
[31] 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.
[32] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142.
[33] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636.
[34] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential
active integrity constraints, Expert Syst. Appl. 168 (2021) art. no. 114297.
[35] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, The complexity of the nucleolus in compact
games, ACM Trans. Comput. Theory 7 (2014) 3:1–3:52.
[36] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query
answering under existential rules, in: AAAI, 2020, pp. 2909–2916.
[37] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under
inconsistency-tolerant semantics, in: IJCAI, 2022.
[38] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Preferred explanations
for ontology-mediated queries under existential rules, in: AAAI, 2021, pp. 6262–6270.
[39] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Explanations for
negative query answers under existential rules, in: KR, 2020, pp. 223–232.
�
Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- under Cardinality-Based Repairs[edit]
Complexity of Inconsistency-Tolerant Query
Answering in Datalog+/– under Cardinality-Based
Repairs⋆
(Discussion Paper)
Thomas Lukasiewicz1 , Enrico Malizia2 and Andrius Vaicenavičius1
1
Department of Computer Science, University of Oxford, UK
2
DISI, University of Bologna, Italy
Abstract
Querying inconsistent ontological knowledge bases is an important problem in practice, for which
several inconsistency-tolerant semantics have been proposed. In these semantics, the input database is
erroneous, and a repair is a maximally consistent database subset. Different notions of maximality (such
as subset and cardinality maximality) have been considered. In this paper, we give a precise picture of
the computational complexity of inconsistency-tolerant query answering in a wide range of Datalog+/–
languages under the cardinality-based versions of three prominent repair semantics.
Keywords
Knowledge representation, Existential rules, Inconsistencies, Query answering, Complexity
1. Introduction
In many ontology-based applications, such as ontology-based data extraction from the Web, or
ontology-based integration of different data sources, it is very likely that the data are inconsis-
tent with the ontology, and thus inconsistency-tolerant semantics for ontology-based query
answering are urgently needed. Among the most prominent ontology languages are description
logics (DLs) [2] and existential rules from the context of Datalog± [3].
The most widely accepted semantics for querying inconsistent ontological knowledge bases is
perhaps consistent query answering (CQA), which was first developed for relational databases [4]
and then generalized as the ABox repair (AR) semantics for several DLs [5]. Consistent query
answering is based on the concept of repair, which is a maximal consistent subset of the
input database. A fact/query is entailed by an ontological knowledge base in consistent query
answering, if it is (classically) entailed by all the repairs (under the ontology). Several other
repair semantics for querying inconsistent knowledge bases have recently been developed as
alternatives. In the intersection of repairs (IAR) semantics [5], an answer is considered to be
SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy
⋆
This is a short version of the AAAI-19 paper [1].
$ thomas.lukasiewicz@cs.ox.ac.uk (T. Lukasiewicz); enrico.malizia@unibo.it (E. Malizia);
andrius.vaicenavicius@cs.ox.ac.uk (A. Vaicenavičius)
� 0000-0002-7644-1668 (T. Lukasiewicz); 0000-0002-6780-4711 (E. Malizia)
© 2022 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)
�valid, if it can be inferred from the intersection of the repairs (and the ontology). The intersection
of closed repairs (ICR) [6] is another semantics, in which an answer is valid, if it can be inferred
from the intersection of the closure of the repairs (and the ontology). Recently, the AR semantics
was extended to the generalized repair (GR) semantics [7]. In the GR semantics, also ontological
rules may be removed. This generalization was extended to the IAR and ICR semantics in [8]
Interestingly, the IAR and the ICR semantics can be seen as under-approximation of the AR
semantics and analyzing their complexity helps to understand whether such approximations
have actually lower complexities (see also [9, 10] for other approximation approaches). Beside
this, a crucial advantage of the IAR and the ICR semantics is that their intersection of (closed)
repairs can be materialized [11, 12], while the AR semantics exists only virtually.
The complexity of consistent query answering when the ontology is described via one of
the main DLs is well-understood. Rosati [13] studied the data and combined complexity for a
wide spectrum of DLs, while Bienvenu [6] identified cases for simple ontologies (within the
DL-Lite family) for which tractable data complexity results can be obtained. In [14], the data
and different types of combined complexity of consistent query answering have been studied
for ontologies described via existential rules and negative constraints.
Alternative maximality notions for repairs, such as cardinality-maximal repairs [15], rather
than subset-maximal ones, have been explored less. Bienvenu et al. [16] analyzed the data
and the combined complexity of query answering under the AR and IAR semantics over the
language DL-Liteℛ for various notions of maximal repairs, among which maximum cardinality.
This paper continues this line of research on cardinality-maximal consistent query answering,
and we analyze the complexity of the above three inconsistency-tolerant query answering
semantics for a wide range of Datalog± languages and for several different complexity measures.
2. Preliminaries
We here briefly recall some basics on existential rules from the context of Datalog± [3].
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 assume a set of predicates, each associated with an arity.
An atom has the form 𝑝(𝑡1 , . . . , 𝑡𝑛 ), where 𝑝 is an 𝑛-ary predicate, and 𝑡1 , . . . , 𝑡𝑛 are terms. An
atom containing only constants is called fact. Conjunctions of atoms are also identified with
the sets of their atoms. An instance 𝐼 is a (possibly infinite) set of atoms defined over constants
and nulls. A database 𝐷 is a finite instance containing only constants. A homomorphism is a
substitution ℎ : C ∪ N ∪ V ↦→ C ∪ N ∪ V that is the identity on C and maps N to C ∪ N. With
a slight abuse of notation, homomorphisms are applied also to (sets/conjunctions of) atoms. A
conjunctive query (CQ) 𝑞 has the form ∃Y𝜑(X, Y), where 𝜑(X, Y) is a conjunction of atoms
without nulls. The answer to 𝑞 over an instance 𝐼, denoted 𝑞(𝐼), is the set of all |X|-tuples
t over C for which there is a homomorphism ℎ such that ℎ(𝜑(X, Y)) ⊆ 𝐼 and ℎ(X) = t. A
Boolean CQ (BCQ) 𝑞 is a CQ ∃Y𝜑(Y), i.e., all variables are existentially quantified; 𝑞 is true
over 𝐼, denoted 𝐼 |= 𝑞, if 𝑞(𝐼) ̸= ∅, i.e., there is a homomorphism ℎ with ℎ(𝜑(Y)) ⊆ 𝐼.
Dependencies. A tuple-generating dependency (TGD) 𝜎 is an FO formula ∀X∀Y 𝜙(X, Y) →
∃Z 𝑝(X, Z), where X, Y, and Z are pairwise disjoint sets of variables, 𝜙(X, Y) is a conjunction
of atoms, and 𝑝(X, Z) is an atom, all without nulls. An instance 𝐼 satisfies 𝜎, written 𝐼 |= 𝜎,
�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) → ⊥, where X ⊆ V, 𝜙(X) is a conjunction of atoms without
nulls, and ⊥ denotes the truth constant false. An instance 𝐼 satisfies 𝜈, written 𝐼 |= 𝜈, if there
is no homomorphism ℎ such that ℎ(𝜙(X)) ⊆ 𝐼. 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 (instead of ∧) for conjoining atoms.
For a TGD class C, C⊥ denotes the formalism obtained by combining C with arbitrary NCs.
Finite sets of TGDs and NCs are also called programs, and TGDs are also called existential rules.
The Datalog± languages ℒ that we consider to guarantee decidability are among the most
frequently analyzed in the literature, namely, linear (L) [3], guarded (G) [17], sticky (S) [18], and
acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticky (WS) [18] and
weakly acyclic TGDs (WA) [19], 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 also recall the following further inclusions: L ⊂ G and
F ⊂ WA ⊂ WS. We refer to [14] for a more detailed overview.
Knowledge Bases. A knowledge base is a pair (𝐷, Σ), where 𝐷 is a database, and Σ is a program.
For a program Σ, Σ𝑇 and ΣNC denote the TGDs and NCs subsets, respectively, of Σ. The set
mods(KB ) of models of KB = (𝐷, Σ) is the set of instances {𝐼 | 𝐼 ⊇ 𝐷 ∧ 𝐼 |= Σ}; KB is
consistent if mods(KB ) ̸= ∅,⋂︀otherwise KB is inconsistent. The answer to a CQ 𝑞 w.r.t. KB is the
set of tuples ans(𝑞, KB ) = {𝑞(𝐼) | 𝐼 ∈ mods(KB )}. The answer to a BCQ 𝑞 is true, denoted
KB |= 𝑞, if ans(𝑞, KB ) ̸= ∅. Another way to define the existential rules semantics is via the
concept of the Chase (see, e.g., [20, 21]). The decision version of the CQ answering problem is:
for a knowledge base KB , a CQ 𝑞, and a tuple of constants t, decide whether t ∈ ans(𝑞, KB ).
Since CQ answering can be reduced in logspace to BCQ answering, we focus on BCQs. BCQ(ℒ)
denotes the problem of BCQ answering when restricted over programs belonging to ℒ.
Following Vardi [22], the combined complexity of BCQ answering considers the database,
the set of dependencies, and the query as part of the input. The bounded-arity-combined (or
ba-combined) complexity assumes that the arity of the underlying schema is bounded by an
integer constant. The fixed-program-combined (or fp-combined) complexity considers the sets of
TGDs and NCs as fixed; the data complexity also assumes the query fixed. Table 1 recalls the
complexity results of BCQ answering for the languages here considered [14].
A language ℒ is FO-rewritable if given any program Σ ∈ ℒ and any BCQ 𝑞, there exists an
FO-query 𝑞Σ such that, for all databases 𝐷 we have that (𝐷, Σ) |= 𝑞 iff 𝐷 |= 𝑞Σ . All languages
from Table 1 with ac0 data complexity are FO-rewritable.
Inconsistency-Tolerant Semantics. In classical BCQ answering, an inconsistent knowledge
base entails every query, as everything follows from a contradiction. Clearly, the answers
obtained in such cases are not meaningful. Three prominent inconsistency-tolerant semantics for
query answering under existential rules are the ABox repair (AR) semantics, its approximation
by the intersection of repairs (IAR), and the intersection of closed repairs (ICR) semantics [5, 6];
all three are based on the notion of repair, which is a maximal consistent subset of the database.
Symmetrically, the concept of repair is linked to that of culprit. Intuitively, a culprit is a
minimal subset of 𝐷 that, together with Σ𝑇 entails some NC; a culprit for an NC is a “minimal
�Table 1
Complexity of BCQ answering under existential rules [14].
ℒ Data fp-comb. ba-comb. Comb.
0
L, LF, AF ≤ ac np np pspace
S, SF ≤ ac0 np np exp
A ≤ ac0 np nexp nexp
G p np exp 2exp
F, GF p np np exp
WS, WA p np 2exp 2exp
WG exp exp exp 2exp
explanation” [23, 24] of the NC. By deleting from 𝐷 a minimal hitting set [25, 26, 27] of facts 𝑆
intersecting all culprits, we obtain a repair 𝑅 = 𝐷 ∖ 𝑆.
We now define inconsistency-tolerant semantics for a generic concept of repair maximality.
Given a knowledge base KB = (𝐷, Σ), a selection 𝐷′ of KB is a database such that 𝐷′ ⊆ 𝐷.
A selection 𝐷′ of KB is consistent, if mods((𝐷′ , Σ)) ̸= ∅. Consistent selections of knowledge
bases can be ordered according to some criteria to select the more desired ones. Given a preorder
≼ over a set 𝒮 of databases, for two elements 𝐷′ , 𝐷′′ ∈ 𝒮, 𝐷′ ≺ 𝐷′′ denotes that 𝐷′ ≼ 𝐷′′ and
𝐷′′ ̸≼ 𝐷′ . A database 𝐷 ∈ 𝒮 is ≼-maximal in 𝒮 iff there is no 𝐷′ ∈ 𝒮 such that 𝐷 ≺ 𝐷′ .
Definition 1. A ≼-repair of a knowledge base KB is a consistent selection of KB that is
≼-maximal in the set of all the consistent selections of KB .
We now define the three different inconsistency-tolerant semantics for BCQ answering.
Rep ≼ (KB ) denotes the set of all ≼-repairs of KB . The closure Cl (KB ) of KB is the set of all
facts built from constants in 𝐷 and Σ, entailed by 𝐷 and the TGDs of Σ.
Definition 2. Let KB be a knowledge base, let 𝑞 be a BCQ, and let ≼ be an order over the
consistent selections of KB .
• KB entails 𝑞 under the ABox repair semantics and order ≼ (≼-AR), denoted by KB |=≼-AR 𝑞,
if, for all 𝐷′ ∈ Rep ≼ (KB ), (𝐷′ , Σ) |= 𝑞.
• KB entails 𝑞 under the intersection of repairs⋂︀ semantics and order ≼ (≼-IAR), denoted by
KB |=≼-IAR 𝑞, if (𝐷* , Σ) |= 𝑞, where 𝐷* = {𝐷′ | 𝐷′ ∈ Rep ≼ (KB )}.
• KB entails 𝑞 under the intersection of closed repairs
⋂︀ semantics and order ≼ (≼-ICR), denoted
by KB |=≼-ICR 𝑞, if (𝐷𝐼 , Σ) |= 𝑞, where 𝐷𝐼 = {Cl ((𝐷 , Σ)) | 𝐷′ ∈ Rep ≼ (KB )}.
′
An interesting class of repairs are those selected by the cardinality order ‘≤’ [16]. A ≤-repair
of a knowledge base KB is a maximum cardinality consistent selection of KB . Here, we consider
only the ‘≤’ order, hence, we often call ≤-repairs simply repairs, and by Rep(KB ), we mean
Rep ≤ (KB ). Cardinality-maximal repairs are very appropriate when it is known (or believed)
that all the facts in the database have the same (possibly small) probability of being erroneous.
In these cases, larger repairs are preferred, because fewer facts are dropped [16]. When facts in
the database have different likelihoods of being erroneous, then other concepts of repairs can
also be taken into consideration [6, 28].
�Table 2
Complexity of ≤-AR/IAR/ICR BCQ answering—all completeness results. + Different membership
proof for AR/IAR in [16]. * Different hardness proof for AR/IAR for L⊥ , G⊥ , S⊥ , and WS⊥ , in [16].
≤-AR BCQ answering ≤-IAR/ICR BCQ answering
ℒ Data fp-comb. ba-comb. Comb. Data fp-comb. ba-comb. Comb.
L⊥ , LF⊥ , AF⊥ Θp2 +* Πp2 Θp3 pspace Θp2 +* Θp2 Θp3 pspace
S⊥ , SF⊥ Θp2 +* Πp2 Θp3 exp Θp2 +* Θp2 Θp3 exp
A⊥ Θp2 + Πp2 nexp
p pnexp Θp2 + Θp2 pnexp pnexp
G⊥ Θp2 +* Πp2 exp 2exp Θp2 +* Θp2 exp 2exp
F⊥ , GF⊥ Θp2 + Πp2 Θp3 exp Θp2 + Θp2 Θp3 exp
WS⊥ , WA⊥ Θp2 +* Πp2 2exp 2exp Θp2 +* Θp2 2exp 2exp
WG⊥ exp exp exp 2exp exp exp exp 2exp
3. Complexity Analysis
Compared to the case where subset maximality is considered, using maximum cardinality in
several cases comes at a cost, needed to compute the largest repair’s size. However, this is
sometimes masked out by the complexity of classical/AR/IAR/ICR BCQ answering. Compared
to ≤-AR-BCQ answering, the complexity of ≤-IAR- and ≤-ICR-BCQ answering slightly drops
and is the same. Their complexity is the same because the complexity of either classical BCQ
reasoning or of computing the biggest repairs’ size dominate the task’s complexity. Therefore, in
this setting ICR has an advantage over IAR, as ICR is a finer AR’s approximation than IAR.
3.1. Membership Results
A first result allows us to show most of the complexity upper-bounds of Table 2. The intuition
behind this theorem is as follows. First we can compute the size of the biggest repairs via a
binary search, then through some additional oracle calls it is possible to check whether the
query is entailed or not under the inconsistency-tolerant semantics (see [1] for more details).
Theorem 3. Let 𝐿 be a Datalog± language. If BCQ answering from knowledge bases over 𝐿 is
in C in the data / ba-combined / combined complexity (resp., data / ba-combined complexity),
then ≤-AR and ≤-IAR (resp., ≤-ICR) BCQ answering from knowledge bases over 𝐿 is in p
with an oracle for npC [𝑂(log 𝑛)] in the data / ba-combined / combined complexity (resp., data /
ba-combined complexity).
The previous result relies on the guess of a query entailment disprover to be passed to the
oracle. However, this cannot be done for the ICR case in the combined complexity, as the guess
might need be too large. We hence need a tailored proof analyzing all languages case by case.
Theorem 4. ≤-ICR BCQ answering in the combined complexity from knowledge bases over
Datalog± the languages 𝐿 here considered is in the complexity classes shown in Table 2.
For the upper-bounds in the fp-combined setting, we can actually provide tighter ones, as
checking the consistency of a set of facts is feasible in the complexity class of BCQ answering
in the data complexity (and not in the fp-complexity), because the NCs are fixed.
�Theorem 5. If BCQ answering from knowledge bases over a Datalog± language 𝐿 is in D in the
data complexity and in C in the fp-combined complexity, then ≤-AR (resp., ≤-IAR and ≤-ICR)
BCQ answering from knowledge bases over 𝐿 is possible by a computation in p with an oracle
for npD [𝑂(log 𝑛)], followed by a computation in co-npC (resp., C), in the fp-combined complexity.
3.2. Hardness Results
We can show matching lower-bounds for the upper-bounds found in the previous section.
The following result is via a reduction from the Θp2 -complete problem InAllMaxIS [15]: for
a graph 𝐺 and a vertex 𝑤, decide if 𝑤 belongs to all the max-size independent sets of 𝐺.
Theorem 6. For every 𝐶 ∈ {AR, IAR, ICR}, ≤-C BCQ answering from knowledge bases over
LF⊥ , AF⊥ , and SF⊥ is Θp2 -hard in the data complexity.
For the next result, the reduction is from the classical Πp2 -complete problem of deciding the
validity of a QBF ∀𝑋∃𝑌 𝜑(𝑋, 𝑌 ).
Theorem 7. ≤-AR BCQ answering from knowledge bases over LF⊥ , AF⊥ , and SF⊥ is Πp2 -hard
in the fp-combined complexity.
The Θp3 -hardness of the following problems is via a reduction from the Θp3 -complete problem
Comp-Valid2 : given sets 𝐴 and 𝐵 of QBFs with 2 alternating quantifiers, decide whether the
number of valid formulas in 𝐴 is bigger than the number of valid formulas in 𝐵 [29] (this is a
generalization of the Comp-SAT problem [30]).
Theorem 8. For every 𝐶 ∈ {AR, IAR, ICR}, ≤-C BCQ answering from knowledge bases over
LF⊥ , AF⊥ , and SF⊥ is Θp3 -hard in the ba-combined complexity.
The next hardness is obtained via a reduction from the following pnexp -hard problem [14]: for
a triple (𝑚, TP 1 , TP 2 ), where 𝑚 is an integer in unary notation, and TP 1 and TP 2 are two
tiling problems for the exponential square 2𝑛 × 2𝑛 , decide whether there is an initial condition
𝑤 of length 𝑚, such that TP 1 has no solution with 𝑤, and TP 2 has a solution with 𝑤.
Theorem 9. For any 𝐶 ∈ {AR, IAR, ICR}, ≤-C BCQ answering for A⊥ are pnexp -hard in the
ba-combined and combined complexity.
The remaining hardness results follows from the hardness of BCQ answering.
4. Summary and Outlook
We have analyzed BCQ answering under different cardinality-maximal inconsistency-tolerant
semantics, for the most popular Datalog± languages and complexity measures.
Future research include defining other semantics for inconsistency-tolerant ontological query
answering, considering weighed repairs and more elaborate user preferences over repairs [31,
32, 33, 34, 35]. Also, in the line of a more recent research, it would be interesting to extend the
concepts of explanations for inconsistency-tolerant query answering [36, 37] to cardinality-
maximal repairs, and mix this with the notions of preferred explanations [38] and explanations
for negative query answers [39].
�Acknowledgments
This work was supported by the Alan Turing Institute under the UK EPSRC grant EP/N510129/1,
and by the EPSRC grants EP/R013667/1, EP/L012138/1, and EP/M025268/1.
References
[1] T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Complexity of inconsistency-tolerant query
answering in Datalog+/– under cardinality-based repairs, in: AAAI, 2019, pp. 2962–2969.
[2] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The
Description Logic Handbook, 2nd ed., Cambridge University Press, 2007.
[3] A. Calì, G. Gottlob, T. Lukasiewicz, A general Datalog-based framework for tractable query
answering over ontologies, J. Web Sem. 14 (2012) 57–83.
[4] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases,
in: PODS, 1999, pp. 68–79.
[5] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics
for description logics, in: RR, 2010, pp. 103–117.
[6] M. Bienvenu, On the complexity of consistent query answering in the presence of simple
ontologies, in: AAAI, 2012, pp. 705–711.
[7] T. Eiter, T. Lukasiewicz, L. Predoiu, Generalized consistent query answering under exis-
tential rules, in: KR, 2016, pp. 359–368.
[8] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering
under inconsistency in Datalog± , in: IJCAI, 2018, pp. 1921–1927.
[9] S. Greco, C. Molinaro, Probabilistic query answering over inconsistent databases, Ann.
Math. Artif. Intell. 64 (2012) 185–207.
[10] S. Greco, C. Molinaro, I. Trubitsyna, Computing approximate query answers over incon-
sistent knowledge bases, in: IJCAI, 2018, pp. 1838–1846.
[11] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant query
answering in ontology-based data access, J. Web Sem. 33 (2015) 3–29.
[12] M. Bienvenu, C. Bourgaux, Inconsistency-tolerant querying of description logic knowledge
bases, in: Reasoning Web, 2016, pp. 156–202.
[13] R. Rosati, On the complexity of dealing with inconsistency in description logic ontologies,
in: IJCAI, 2011, pp. 1057–1062.
[14] T. Lukasiewicz, E. Malizia, M. V. Martinez, C. Molinaro, A. Pieris, G. I. Simari, Inconsistency-
tolerant query answering for existential rules, Artif. Intell. 307 (2022) art. no. 103685.
[15] A. Lopatenko, L. E. Bertossi, Complexity of consistent query answering in databases under
cardinality-based and incremental repair semantics, in: ICDT, 2007, pp. 179–193.
[16] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge
bases under preferred repair semantics, in: AAAI, 2014, pp. 996–1002.
[17] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive
relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174.
[18] A. Calì, G. Gottlob, A. Pieris, Towards more expressive ontology languages: The query
answering problem, Artif. Intell. 193 (2012) 87–128.
�[19] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: Semantics and query answering,
Theor. Comput. Sci. 336 (2005) 89–124.
[20] E. Tsamoura, D. Carral, E. Malizia, J. Urbani, Materializing knowledge bases via trigger
graphs, VLDB Endow. 14 (2021) 943–956.
[21] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Exploiting equality generating dependen-
cies in checking chase termination, VLDB Endow. 9 (2016) 396–407.
[22] M. Vardi, The complexity of relational query languages, in: STOC, 1982, pp. 137–146.
[23] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers
under existential rules, in: IJCAI, 2019, pp. 1639–1646.
[24] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for ontology-
mediated query answering in description logics, in: ECAI, 2020, pp. 672–679.
[25] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, SIAM J. Comput. 47 (2018) 456–492.
[26] J. Chomicki, J. Marcinkowski, Minimal-change integrity maintenance using tuple deletions,
Inf. Comput. 197 (2005) 90–121.
[27] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, in: LICS, 2014, pp. 43:1–43:10.
[28] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant
query answering under existential rules, in: KR, 2020, pp. 203–212.
[29] T. Lukasiewicz, E. Malizia, A novel characterization of the complexity class Θ𝑃𝑘 based on
counting and comparison, Theor. Comput. Sci. 694 (2017) 21–33.
[30] T. Lukasiewicz, E. Malizia, On the complexity of 𝑚CP-nets, in: AAAI, 2016, pp. 558–564.
[31] 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.
[32] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142.
[33] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636.
[34] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential
active integrity constraints, Expert Syst. Appl. 168 (2021) art. no. 114297.
[35] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, The complexity of the nucleolus in compact
games, ACM Trans. Comput. Theory 7 (2014) 3:1–3:52.
[36] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query
answering under existential rules, in: AAAI, 2020, pp. 2909–2916.
[37] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under
inconsistency-tolerant semantics, in: IJCAI, 2022.
[38] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Preferred explanations
for ontology-mediated queries under existential rules, in: AAAI, 2021, pp. 6262–6270.
[39] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Explanations for
negative query answers under existential rules, in: KR, 2020, pp. 223–232.
�