Abstract 1 Introduction 2 Preliminaries 3 Dataset repairs of inconsistent databases or knowledge bases 4 Inconsistency-tolerant semantics 5 Preferred repairs 6 Computational complexity of reasoning with (preferred) repairs 7 Implementations of (preferred) repair-based semantics 8 Summary and outlook References

Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

Camille Bourgaux ORCID DI ENS, ENS, CNRS, PSL University & Inria, Paris, France
Abstract

Real-world datasets are plagued by data quality issues which may render the data inconsistent w.r.t. a set of constraints, be they given by database integrity constraints or ontologies. A prominent way to handle such inconsistent data is to use inconsistency-tolerant semantics to obtain meaningful answers to queries. Most of these semantics are based on some notion of repairs, which represent ways of restoring the data consistency. The most basic kind of repairs is that of subset repairs, which are maximal consistent subsets of the dataset. However, in many scenarios, one can define preferred repairs based on some preference information. These lecture notes present inconsistency-tolerant semantics, focusing on the repair-based ones, then review different kinds of preferred repairs that have been considered in the literature. We present in particular the relationships between different kinds of preferred repairs and other notions related to inconsistency handling, the computational complexity of reasoning with (preferred) repairs, and some implementations.

Keywords and phrases:
Knowledge bases, databases, inconsistency handling, repairs, preferences
Category:
Invited Paper
Copyright and License:
[Uncaptioned image] © Camille Bourgaux; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Automated reasoning
; Computing methodologies Description logics ; Computing methodologies Nonmonotonic, default reasoning and belief revision ; Computing methodologies Reasoning about belief and knowledge ; Information systems Data cleaning
Related Version:
Full Version: https://inria.hal.science/hal-05291421
Acknowledgements:
I am grateful to the RW 2025 organizers for the invitation to give this lecture. Several sections of these lecture notes are based on some work on priority-based repairs that I co-authored with Meghyn Bienvenu.
Funding:
This lecture was supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014).
Editors:
Alessandro Artale, Meghyn Bienvenu, Yazmín Ibáñez García, and Filip Murlak

1 Introduction

Many relational datasets are associated with either some integrity constraints, which aim at preventing errors by expressing properties expected from the stored data [1], or with an ontology, which expresses knowledge on the domain of interest and allows a user to formulate queries in familiar terms and obtain more complete answers through logical reasoning [124, 136, 40]. Integrity constraints and ontologies both consist of logical formulas that can be written as first-order logic sentences. In particular, ontologies are typically expressed in some description logics [14] or extensions of Datalog [20, 56]. The main difference between the database setting, which considers a dataset equipped with a set of integrity constraints, and the knowledge base setting, where a dataset is enriched with an ontology, is that the former uses the logical formulas to check whether the data complies with some rules it is expected to follow while the latter uses them to infer implicit information from the explicitly stored data. However, the question of how to handle the case where the dataset is inconsistent w.r.t. the background knowledge is crucial in both settings. Indeed, it is widely acknowledged that real-world datasets are plagued by data quality issues, and it is not always possible to restore consistency since it may be difficult to identify the erroneous parts of the data, and removing all potentially erroneous facts may lead to unacceptable loss of information.

A prominent way to tackle this issue is to use some inconsistency-tolerant semantics. Such a semantics was first proposed in the database area under the name of consistent query answering, with the goal of obtaining query answers that would be consistent w.r.t. the database constraints even though the database itself was not [8, 25]. In a nutshell, a query answer is consistent if it can be obtained from all repairs of the database, where a repair is a dataset consistent w.r.t. the constraints which minimally differs from the original dataset. As the inconsistency issue is even more problematic for knowledge bases, since everything is entailed by an inconsistent knowledge base under the classical semantics, consistent query answering was adapted to knowledge bases under the name of AR semantics (AR standing for ABox Repair, as a dataset is called an ABox in description logic parlance) [98, 99]. While this semantics remains the most studied and well-established, many other inconsistency-tolerant semantics have been proposed, e.g., to address the intractability of consistent query answering via approximations, or to get a finer classification of the reliability of query answers. A great deal of research effort has been put into exploring the problem of querying inconsistent databases and knowledge bases under these semantics, in particular on the theoretical side, with extensive studies of the computational complexity of this problem in various settings, but also with more practically-oriented research aiming at developing and implementing efficient algorithms for this problem (see surveys [25, 26, 29, 28]).

The notion of repair is at the basis of most of inconsistency-tolerant semantics. However, in many scenarios, one can define preferred repairs based on some preference information, and use these preferred repairs instead of standard ones when querying inconsistent databases or knowledge bases to obtain more accurate answers. For example, optimal repairs based on weights associated to the dataset facts, on a priority relation between facts, or on preference rules have been considered [102, 129, 73, 33, 30, 100, 122, 50, 107, 32].

The goal of these lecture notes is to provide an overview of inconsistency handling based on database or knowledge base (preferred) repairs. After some preliminaries, we introduce the basic notion of a repair in Section 3 and present some characterizations of repairs, based on the concept of conflict hypergraph and argumentation frameworks. In Section 4, we briefly present existing inconsistency-tolerant semantics, focusing on the repair-based ones. We then review the different kinds of preferred repairs that have been considered in the literature in Section 5, focusing on their properties and relationships, and presenting known links to other frameworks for inconsistency handling. We also expand the focus to consider related work on other ways of defining optimal consistent datasets that are not repairs per se. In Section 6, we present some results on the computational complexity of deciding whether a dataset is a repair and of reasoning under repair-based semantics, then on the impact of using preferred repairs instead of standard ones, focusing in particular on data complexity. In Section 7, we give a concise overview of systems that have been implemented for querying inconsistent databases and knowledge bases under (preferred) repair-based semantics and illustrate some prominent practical approaches. We conclude with a discussion of recent related work and research directions in Section 8.

2 Preliminaries

In this section, we introduce the database and knowledge base settings we will consider throughout this chapter and recall some relevant results on their computational complexity. We assume a basic knowledge of first-order logic (FO) syntax and semantics.

2.1 Databases, knowledge bases, queries

Let 𝐏, 𝐂, and 𝐕 be three disjoint countable sets of predicates, constants and variables respectively. Each predicate is associated with an arity, i.e., a non-negative integer. A term is a constant or a variable and a (relational) atom has form P(t1,,tn) where P is a predicate of arity n and t1,,tn are terms. A fact is a ground atom, i.e., an atom that does not contain any variable. A dataset is a finite set of facts. We consider pairs 𝒦=𝒟,𝒯 where 𝒟 is a dataset and 𝒯 is a logical theory, i.e., a finite set of logical formulas, which is interpreted either as a set of integrity constraints, or as an ontology. In the former case, we call 𝒦 a database, and in the latter, a knowledge base (KB). As ontology languages, we consider description logics and Datalog± (a.k.a. existential rules with negative constraints). We use interpretations to define the semantics of databases and KBs. An interpretation =(Δ,) consists of a domain Δ and an interpretation function , which maps each constant c𝐂 to some domain element cΔ and each n-ary predicate P𝐏 to a set of n-tuples P(Δ)n. Given an interpretation and an FO sentence ϕ, we write ϕ to denote that satisfies ϕ under the standard FO semantics. Given a dataset 𝒟, we define the interpretation corresponding to 𝒟 as follows: 𝒟=(𝐂,𝒟) and 𝒟 interprets each constant by itself and each predicate P by the set of tuples {(c1,,cn)P(c1,,cn)𝒟}.

Database integrity constraints.

An integrity constraint (IC) is simply an FO sentence. A dataset 𝒟 satisfies an IC ϕ iff 𝒟ϕ. If 𝒟 does not satisfy ϕ, we also say that 𝒟 violates ϕ. A database 𝒦=𝒟,𝒯 is consistent if 𝒟 satisfies all ICs in 𝒯, inconsistent otherwise (written 𝒦). The dataset 𝒟 is 𝒯-(in)consistent if 𝒟,𝒯 is (in)consistent. Most studied IC languages can be written as disjunctive rules of the form:

x(β[x]ϵ[x]i=1kyiηi[x,yi]) (1)

where β[x] and ηi[x,yi] (for 1ik) are conjunctions of relational atoms whose terms are in x and xyi, respectively, and ϵ[x] is a conjunction of inequality atoms whose terms are in x. Moreover, every variable in x is required to occur in β[x] to ensure safety. We often omit the universal quantifier and write β[x]ϵ[x]i=1kyiηi[x,yi]. The left-hand side β[x]ϵ[x] is called the body of the rule and the right-hand side i=1kyiηi[x,yi] its head. Figure 1 (left) shows a hierarchy of IC languages [11] (in this picture, FO stands for domain independent FO sentences).

  • A universal constraint (UC) is a rule of form (1) without existential quantifiers. Any UC can be written as a set of rules of form β[x]ν[x]ϵ[x], where ν[x] is a conjunction of negated relational atoms (e.g., P(x,y)Q(x)(R(x,y)S(y)) can be written as two rules P(x,y)¬Q(x)¬R(x,y) and P(x,y)¬Q(x)¬S(y)).

  • A denial constraint (DC) is a rule of form (1) with an empty head: β[x]ϵ[x].

  • An equality-generating dependency (EGD) is a DC where ϵ[x] is a single inequality and is often written as β[x]xi=xj.

  • Given a predicate P of arity n, a functional dependency (FD) over P is of the form P(x1,,xn)P(y1,,yn)iIxi=yijJxj=yj for two disjoint sets of indexes I,J{1,,n}. Any FD can be written as a set of EGDs (e.g., P(x1,x2,x3)P(y1,y2,y3)x1=y1x2=y2x3=y3 can be written as two EGDs P(x1,x2,x3)P(x1,y2,y3)xi=yi for i{2,3}).

  • A key constraint is an FD such that IJ={1,,n}.

  • A disjunctive tuple-generating dependency (-TGD) is a rule of form (1) with an empty ϵ[x], i.e., no inequalities.

  • A tuple-generating dependency (TGD) is a -TGD without disjunction (i.e., where k=1).

  • A local-as-view TGD (lav TGD) is a TGD where the body β[x] is a single atom.

  • An inclusion dependency (ID) is a lav TGD where the head η[x,y] is also a single atom.

  • A full (-)TGD is a (-)TGD that does not contain any existential quantifier.

DCs (hence all ICs encompassed by DCs) are anti-monotone constraints: if a dataset 𝒟 satisfies a DC ϕ, then every 𝒟𝒟 also satisfies ϕ.

Example 1.

Consider the following university database 𝒟𝖣𝖡,𝒯𝖣𝖡. The predicate 𝖲𝗍𝗎𝖽𝖾𝗇𝗍 is used to register students with their identifiers, first names and last names, 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾 associates students and courses they are enrolled in, and 𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾 and 𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾 list the graduate and undergraduate courses, respectively. There are five ICs: (𝖨𝖢𝟣) is a key constraint that states that the identifier determines the student name; (𝖨𝖢𝟤) is a TGD that states that every student must be enrolled in some course; (𝖨𝖢𝟥) is a full -TGD that states that every course must be registered as a graduate or undergraduate course; (𝖨𝖢𝟦) is a DC that ensures that no student identifier occurs in the second position of 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾, which is intended for course identifiers; (𝖨𝖢𝟧) is a DC that states that graduate and undergraduate courses are disjoint. The database 𝒟𝖣𝖡,𝒯𝖣𝖡 is inconsistent: it violates (𝖨𝖢𝟣) because of the two first facts, (𝖨𝖢𝟥) because 456 is not registered as a graduate nor an undergraduate course while it occurs in second position in 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456), (𝖨𝖢𝟦) because of 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒) and 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456), and (𝖨𝖢𝟧) because of the last two facts. Note that if we remove 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456) from 𝒟𝖣𝖡, (𝖨𝖢𝟥) and (𝖨𝖢𝟦) will be satisfied, but (𝖨𝖢𝟤) will become violated since 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456) is the only fact that associates some course to 123.

𝒯𝖣𝖡={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(x,y,z)𝖲𝗍𝗎𝖽𝖾𝗇𝗍(x,y,z)x=xy=yz=z, (𝖨𝖢𝟣)
𝖲𝗍𝗎𝖽𝖾𝗇𝗍(x,y,z)v𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(x,v), (𝖨𝖢𝟤)
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(x,y)𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(y)𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(y), (𝖨𝖢𝟥)
𝖲𝗍𝗎𝖽𝖾𝗇𝗍(x,y,z)𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(v,x), (𝖨𝖢𝟦)
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(x)} (𝖨𝖢𝟧)
𝒟𝖣𝖡={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑛,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
Figure 1: Hierarchies of database integrity contraint languages (left) [11, Fig. 1] and of some ontology languages (right). There is a downward path from 1 to 2 if any set of ICs (resp. any ontology) in 2 can be rewritten into an equivalent set of ICs (resp. ontology) in 1.
Datalog±.

A Datalog± ontology, or Datalog± program, is a finite set of rules of two kinds:

  • TGDs (also called existential rules), i.e., rules of the form β[x]yη[x,y], and

  • negative constraints (NCs), which are rules of the form β[x] where β[x] is a conjunction of relational atoms with variables x (and may contain constants) [104].

However, the semantics of Datalog± is different from that of database integrity constraints. Indeed, while databases are interpreted under the closed world assumption, KBs are interpreted under the open world assumption, so that facts that do not belong to the dataset are not deemed to be false. Hence, instead of evaluating rules on the interpretation corresponding to the dataset as in the database setting, one reasons over the set of all models of the KB. A model of a Datalog± KB 𝒦=𝒟,𝒯 is an interpretation =(Δ,) such that

  • Δ contains all constants from 𝒟 and c=c for each constant c that occurs in 𝒟 (standard name assumption),

  • P(c1,,cn), i.e., (c1,,cn)P, for every P(c1,,cn)𝒟, and

  • ϕ for every ϕ𝒯.

A KB is consistent, or satisfiable, if it has a model, inconsistent otherwise (𝒦). Again, 𝒟 is 𝒯-(in)consistent if 𝒟,𝒯 is (in)consistent. A KB entails an FO sentence ϕ, written 𝒦ϕ, if ϕ for every model of 𝒦. To illustrate the difference between TGDs used as ICs or as ontology language, consider 𝒟={P(c)} and 𝒯={P(x)Q(x)}. The database 𝒟,𝒯 is inconsistent while the KB 𝒟,𝒯 is not (and entails Q(c)). Since query answering in Datalog± is undecidable (this is already the case for existential rules, without NCs), a wealth of decidable fragments have been designed. Some of the most studied are as follows [104].

  • Recall that a TGD is called full if it does not have any existential quantifier. We denote by F the ontology language of full TGDs, also known as Datalog.

  • A set of TGDs is acyclic if its predicate graph, defined as the directed graph with vertices 𝐏 and an edge from P to Q iff there is a rule whose body contains P and whose head contains Q, is acyclic. We denote by A the language of acyclic sets of TGDs.

  • A TGD is guarded if its body has an atom (called a guard) that contains all variables occurring in the body. We denote by G the language of guarded TGDs.

  • A TGD is linear if its body contains a single atom. We denote by L the language of linear TGDs.

  • A set of TGDs is sticky if it respects a syntactic condition which ensures that terms that unify with variables that appear more than once in the body of some rule are always propagated by the rules. We denote by S the language of sets of sticky TGDs.

  • A, G and S come with their respective “weak” versions which restrict the acyclicity, guardedness and stickiness syntactic conditions to take into account only potentially “harmful” variables: weakly acyclic (WA), weakly guarded (WG) and weakly sticky (WS).

For every TGD language X, we denote by 𝖷 its extension with NCs. Figure 1 (right) shows a hierarchy of ontology languages, including these Datalog± fragments.

Example 2.

Consider the KB 𝒟𝖪𝖡,𝒯𝖪𝖡 obtained from the database of Example 1 by dropping (𝖨𝖢𝟣) and (𝖨𝖢𝟥) (since key constraints and disjunctive TGDs are not supported by Datalog±), which belongs to all the Datalog± fragments of Figure 1 except 𝖥.

𝒯𝖪𝖡={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(x,y,z)v𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(x,v), (𝖳𝖦𝖣)
𝖲𝗍𝗎𝖽𝖾𝗇𝗍(x,y,z)𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(v,x), (𝖭𝖢𝟣)
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(x)} (𝖭𝖢𝟤)
𝒟𝖪𝖡={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑛,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}

𝒟𝖪𝖡,𝒯𝖪𝖡 is inconsistent since for every interpretation , if 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒) and 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456), then does not satisfy (𝖭𝖢𝟣), and similarly, every interpretation that satisfies the two last facts violates (𝖭𝖢𝟤). However, in contrast with the database setting, removing the facts 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456) and, e.g., 𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1) from 𝒟𝖪𝖡 yields a consistent KB. For example, the interpretation =(𝐂,) below is a model of 𝒟𝖪𝖡{𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)},𝒯𝖪𝖡. Note that uses a fresh element n to witness a course taken by 123 and satisfy the TGD.

c= c for every c𝐂
𝖲𝗍𝗎𝖽𝖾𝗇𝗍= {(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),(123,𝐴𝑛𝑛,𝐴𝑧𝑢𝑟𝑒),(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒)}
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾= {(123,n),(456,CS1)}
𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾= {CS1}
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾=
Table 1: Syntax and semantics of DL concept and role constructors and TBox axioms: a denotes an individual name, C, C1 and C2 concepts (concept names or complex concepts), R and S role names or inverse roles, and n a natural number.
Name Syntax Semantics
Top concept Δ
Bottom concept
Nominal {a} {a}
Negation ¬C Δ\C
Conjunction C1C2 C1C2
Disjunction C1C2 C1C2
Existential restriction R {d1there exists (d1,d2)R}
Qualified existential restriction R.C {d1there exists (d1,d2)R with d2C}
Qualified universal restriction R.C {d1d2C for all (d1,d2)R}
Qualified cardinality restrictions nR.C {d1|{d2(d1,d2)R and d2C}|n}
nR.C {d1|{d2(d1,d2)R and d2C}|n}
Inverse role R {(d2,d1)(d1,d2)R}
Concept inclusion C1C2 C1C2
Role inclusion RS RS
Complex role inclusion R1RnS R1RnS
Role disjointness R¬S RS=
Transitivity axiom (𝗍𝗋𝖺𝗇𝗌 R) RRR
Description logics.

Description logics (DLs) form a family of ontology languages that are incomparable with Datalog±: on the one hand the DL syntax restricts a lot what can be expressed in TGD-like rules, but on the other hand some DL languages allow for features not available in Datalog± TGDs, such as disjunction in the head, use of constants, or cardinality restrictions. DL predicates can only have arity 1 or 2, and are called concept and role names, respectively. Note that in DL parlance, constants are called individual names, facts are called assertions, datasets are called ABoxes, and ontologies TBoxes. Moreover, the ontology axioms are not written as FO sentences but in a concise syntax, which enforces restrictions on the language expressivity. Table 1 gives the syntax and semantics of the most common DL axioms and we list below a few examples among the many DL languages.

  • 𝒜𝒞 is the prototypical DL and allows for concept inclusions (and no other kind of axiom) using the constructors ,,¬C,C1C2,C1C2,R.C,R.C.

  • The expressive 𝒮𝒬 extends 𝒜𝒞 with role inclusions, transitivity axioms, inverse roles, and qualified cardinality restrictions, with the restriction that roles that occur in qualified cardinality restrictions are required to be simple, meaning that they should not have any transitive subrole (i.e., R is simple if 𝒯SR implies (𝗍𝗋𝖺𝗇𝗌 S)𝒯).

  • One can further extend 𝒮𝒬 with nominals, complex role inclusions, role disjointness axioms, a universal role and a 𝑆𝑒𝑙𝑓 concept, with again some restrictions on the use of complex roles to ensure decidability. The resulting language, called 𝒮𝒪𝒬, is closely related to OWL, the ontology language standard for the Semantic Web [121].

  • The lightweight DL is the fragment of 𝒜𝒞 that only allows for ,,C1C2,R.C.

  • Another family of lightweight DLs is the DL-Lite family. In particular:

    • A DL-Litecore TBox consists of concept inclusions of the form BC where B:=AR with A a concept name and R a role name or inverse role, and C:=B¬B.

    • DL-LiteR extends DL-Litecore with role inclusions and role disjointness axioms.

    • DL-LiteR,⊓ 111DL-Lite𝗁𝗈𝗋𝗇 [12], the variant of DL-LiteR,⊓ [58] without role disjointness axioms, may be more common. However, both languages have the same computational behavior [12]. extends DL-LiteR with concept inclusions of the form A1AnA.

An interpretation =(Δ,) is a model of a DL KB 𝒦=𝒟,𝒯 if

  • satisfies all facts in 𝒟 (i.e., aA and (a,b)R for all concept and role assertions A(a) and R(a,b) in 𝒟) and

  • satisfies all axioms in 𝒯 as explained in Table 1.

The only difference with the semantics of Datalog± KBs is that we do not need to make the standard name assumption, nor the unique name assumption (even though these assumptions are sometimes made): in general, two different constants from 𝒟 can be interpreted by the same element of Δ.

Example 3.

The database of Example 1 can be “translated” into the 𝒮𝒬 KB 𝒟𝖣𝖫,𝒯𝖣𝖫. Since predicates of arity greater than 2 are not allowed, the ternary predicate 𝖲𝗍𝗎𝖽𝖾𝗇𝗍 is replaced by a concept 𝖲𝗍𝗎𝖽𝖾𝗇𝗍 that stores the student identifiers and two roles 𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾 and 𝖫𝖺𝗌𝗍𝖭𝖺𝗆𝖾 that associate identifiers with first and last names. (𝖺𝗑𝟣)-(𝖺𝗑𝟤) state that students have at most one first name and one last name, (𝖺𝗑𝟥) that every student takes some course, (𝖺𝗑𝟦) that everything in the range of 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾 is a graduate course or an undergraduate course, (𝖺𝗑𝟧) that the concept 𝖲𝗍𝗎𝖽𝖾𝗇𝗍 and the range of 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾 are disjoint, and (𝖺𝗑𝟨) that 𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾 and 𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾 are disjoint.

𝒯𝖣𝖫={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍1𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾.,𝖲𝗍𝗎𝖽𝖾𝗇𝗍1𝖫𝖺𝗌𝗍𝖭𝖺𝗆𝖾., (𝖺𝗑𝟣)-(𝖺𝗑𝟤)
𝖲𝗍𝗎𝖽𝖾𝗇𝗍𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾., (𝖺𝗑𝟥)
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾.𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾, (𝖺𝗑𝟦)
𝖲𝗍𝗎𝖽𝖾𝗇𝗍𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾., (𝖺𝗑𝟧)
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾} (𝖺𝗑𝟨)
𝒟𝖣𝖫={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456),𝖫𝖺𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑧𝑢𝑟𝑒),𝖫𝖺𝗌𝗍𝖭𝖺𝗆𝖾(456,𝐵𝑙𝑢𝑒),
𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑎),𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛),𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(456,𝐵𝑒𝑎),
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}

As in Example 2, the KB is inconsistent but removing the facts 𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456) and 𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1) makes it consistent, when interpreted without the unique name assumption: a model of 𝒟𝖣𝖫{𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)},𝒯𝖣𝖫 simply interprets Ann and Ana by the same domain element (however, if interpreted under the unique name assumption, the KB would be inconsistent).

Queries.

An FO query is simply an FO formula, whose free variables are called the answer variables. A tuple a=(a1,,an) is a (certain) answer to a query q(x) with answer variables x=(x1,,xn) over a KB 𝒦=𝒟,𝒯 if 𝒦q(a), where q(a) is the FO sentence obtained by replacing each xi by ai in q(x). For a database 𝒦=𝒟,𝒯, we simply define 𝒦q(a) by 𝒟q(a). A conjunctive query (CQ) is an FO query of the form q(x)=yφ(x,y) where φ(x,y) is a conjunction of relational atoms. A union of conjunctive queries (UCQ) has form q(x)=i=1nqi(x) where each qi(x) is a CQ. We often see a UCQ as a finite set of CQs. A query that has no answer variable is called a Boolean query (BCQ, BUCQ).

Example 4.

Consider the dataset 𝒟𝖣𝖫={𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1)} and the ontology 𝒯𝖣𝖫 from Example 3. The CQ q(x)=y𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(x,y) has two certain answers over 𝒟𝖣𝖫,𝒯𝖣𝖫: (123) and (456).

FO- and UCQ-rewritability.

We say that CQ answering under an ontology language is UCQ-rewritable (resp. FO-rewritable) if for every BCQ q and ontology 𝒯 in , there exists a BUCQ (resp. an FO query) qr such that for every dataset 𝒟, 𝒟,𝒯q iff 𝒟qr. In the BUCQ case, we denote the set of BCQs in qr by 𝖱𝖾𝗐(q,𝒯).

Fact 5.

CQ answering under L, A and S is UCQ-rewritable (cf. [131, Def. 2.19 and Properties 4, 5, 6], and [104, Sec. 3.2.1]), as well as under DL-LiteR,⊓ and its sub-languages [58].

Example 6.

Given the DL-Litecore ontology 𝒯={𝖲𝗍𝗎𝖽𝖾𝗇𝗍𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾} and BCQ q=y𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,y), 𝖱𝖾𝗐(q,𝒯)={q,q} with q=𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123).

Proposition 7 (Consistency checking via UCQ-rewritability).

For every Datalog± fragment X, if CQ answering under X is UCQ-rewritable, then for every ontology 𝒯 in 𝖷, there exists a BUCQ q𝒯 such that for every dataset 𝒟, 𝒟,𝒯 iff 𝒟q𝒯.

Proof.

For every Datalog± KB 𝒟,𝒯, 𝒟,𝒯 iff there exists β[x]𝒯 such that 𝒟,𝒯+xβ[x], where 𝒯+ is the set of TGDs in 𝒯, so if 𝒯+ is in X and CQ answering under X is UCQ-rewritable, 𝒟,𝒯 iff 𝒟q for some qβ[x]𝒯𝖱𝖾𝗐(xβ[x],𝒯+).

2.2 Computational complexity

We consider two ways of measuring the computational complexity of decision problems: the data complexity is measured w.r.t. the size of the dataset 𝒟 while the combined complexity takes into account the size of the whole input.

Complexity classes.

We will refer to the following complexity classes:

  • Below P:

    • 𝖠𝖢0: problems solvable by a family of circuits of constant depth and polynomial size w.r.t. the size of the input, with unbounded-fanin AND and OR gates.

    • L: problems solvable in logarithmic space w.r.t. the size of the input.

    • NL: problems solvable in non-deterministic logarithmic space. These are problems for which there exists a certificate of polynomial size which can be verified by a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape. It is known (by Immerman–Szelepcsényi theorem) that NL=coNL.

  • The polynomial hierarchy and other classes between P and PSpace:

    • P=Σ0P: problems which are solvable in polynomial time w.r.t. the size of the input.

    • NP=Σ1P: problems which are solvable in non-deterministic polynomial time. These are problems for which there exists a certificate of polynomial size which can be verified by a deterministic polynomial-time Turing machine.

    • coNP=Π1P: problems whose complement is in NP.

    • In general, for i0, Δi+1P=PΣiP is the class of problems solvable in polynomial time with access to a ΣiP oracle, Σi+1P=NPΣiP, and Πi+1P=coNPΣiP.

    • Θi+1P is the class of problems solvable in polynomial time with at most logarithmically many calls to a ΣiP oracle. It is known that these are problems solvable by polynomially many independent (parallel) calls to a ΣiP oracle [47].

    • DP: problems that are the intersection of a problem in NP and a problem in coNP.

    • PSpace: problems which are solvable in polynomial space. It is known (by Savitch’s theorem) that PSpace=NPSpace.

  • The (weak) exponential hierarchy and other classes between Exp and 2Exp:

    • Exp=Σ0Exp: problems which are solvable in exponential time, i.e., in O(2p(n)) where p is a polynomial function and n is the input size.

    • NExp=Σ1Exp: problems which are solvable in non-deterministic exponential time.

    • coNExp=Π1Exp: problems whose complement is in NExp.

    • In general, for i0, Δi+1Exp=ExpΣiP is the class of problems solvable in exponential time with access to a ΣiP oracle, Σi+1Exp=NExpΣiP, and Πi+1Exp=coNExpΣiP.

    • DExp: problems that are the intersection of a problem in NExp and one in coNExp.

    • PNExp: problems that are solvable in polynomial time with an NExp oracle. It is known (since the strong exponential hierarchy collapses [89]) that NPNExp=PNExp.

    • 2Exp: problems which are solvable in double-exponential time.

Complexity of BCQ entailment and consistency checking.

We illustrate the computational complexity of the decision problems we consider on a few selected languages from Figure 1. Table 2 shows the data and combined complexity of BCQ entailment, the decision problem which takes as input a database or KB 𝒦=𝒟,𝒯 and a Boolean conjunctive query q and outputs “yes” if 𝒦q, and “no” otherwise. Table 3 shows the data and combined complexity of consistency checking, the decision problem which takes as input a database or KB 𝒦=𝒟,𝒯 and outputs “yes” if 𝒦 is consistent, and “no” otherwise.

Table 2: Complexity of BCQ entailment. All non-“in” entries are completeness results. For Datalog± fragments, references are given for X rather than 𝖷, cf. Remark 9.
Data complexity Combined complexity
DLs DL-LiteR in 𝖠𝖢0 [12, Th. 8.9] NP
[58, Th. 44]
+ easy extension
DL-LiteR,⊓ in 𝖠𝖢0 NP
P [125, Th. 2] NP [125, Th. 2]
𝒜𝒞 coNP [120, Th. 4.6] Exp [110, Th. 4]
𝒮𝒬 coNP [84, Cor. 36] 2Exp [84, Cor. 33]
Datalog± 𝖫 in 𝖠𝖢0 [56, Cor. 10] PSpace [55, Th. 12.7]
𝖠 in 𝖠𝖢0 [104, Pr. 3.3] NExp [104, Pr. 3.3]
𝖦 P [54, Th. 6.1] 2Exp [54, Th. 6.1]
𝖲 in 𝖠𝖢0 [57, Th. 3.5] Exp [57, Th. 3.3 & 3.4]
𝖥 P [70, Th. 4.4] Exp [70, Th. 4.5]
Database in 𝖠𝖢0 [135, Tab. 1] NP [63, Th. 7]
Table 3: Complexity of consistency checking. All non-“in” entries are completeness results.
Data complexity Combined complexity
DLs DL-LiteR in 𝖠𝖢0 [12, Th. 8.3] NL [12, Th. 8.2]
DL-LiteR,⊓ in 𝖠𝖢0 P
P [13, Th. 4][59, Th. 7] P [13, Th. 4][59, Th. 7]
𝒜𝒞 NP [90, Th. 2] Exp [132, Cor. 3.1]
𝒮𝒬 NP Exp [132, Cor. 6.30]
Datalog± 𝖫 in 𝖠𝖢0
Table 2 and
Remark 9
PSpace
Table 2 and
Remark 9
𝖠 in 𝖠𝖢0 coNExp
𝖦 P 2Exp
𝖲 in 𝖠𝖢0 Exp
𝖥 P Exp
ICs FD in 𝖠𝖢0
FO query
evaluation
[135, Tab. 1]
in L folklore (e.g., [11])
DC in 𝖠𝖢0 coNP
BCQ eval. [63, Th. 7]
extend. to BCQ with
safe ¬ and
full TGD in 𝖠𝖢0 coNP
UC in 𝖠𝖢0 coNP
TGD in 𝖠𝖢0 Π2P [123, Th. 3.1]
 Remark 8 (Database setting).

In the database setting, ICs do not play any role in BCQ evaluation, so we do not distinguish between the different IC languages in Table 2. Regarding consistency checking, 𝒟,𝒯 iff 𝒟ϕ𝒯¬ϕ. This straightforwardly yields the 𝖠𝖢0 data complexity upper bounds and the coNP upper bounds for the IC languages such that the ¬ϕ are BCQs with safe negation and inequalities (i.e., for universal constraints).

 Remark 9 (Datalog±: X versus 𝖷).

For Datalog± fragments, most complexity results have actually been shown for BCQ entailment in X rather than in 𝖷, but they extend to both inconsistency checking and BCQ entailment in 𝖷:

  • Lower bounds: If 𝒯 contains only TGDs, for any BCQ q, 𝒟,𝒯q iff 𝒟,𝒯{q}, hence inconsistency checking in 𝖷 is at least as hard as BCQ entailment in X.

  • Combined complexity and P data complexity upper bounds: Recall that (i) 𝒟,𝒯 iff there exists β[x]𝒯 such that 𝒟,𝒯+xβ[x], where 𝒯+ is the set of TGDs in 𝒯 (meaning that 𝒯+ is in X if 𝒯 is in 𝖷), and (ii) for every BCQ q, 𝒟,𝒯q iff either 𝒟,𝒯+q or 𝒟,𝒯 (since an inconsistent KB entails every query).

    • We thus only need a linear number of checks of BCQ entailment under X to decide (in)consistency checking and BCQ entailment under 𝖷. This yields the P data complexity upper bounds and the Exp and 2Exp combined complexity upper bounds.

    • For the PSpace upper bound for 𝖫, guess an NC β[x]𝒯 (or q in the BCQ entailment case) and check in PSpace that 𝒟,𝒯+xβ[x] (or 𝒟,𝒯+q). The result follows from the fact that NPSpace=PSpace.

    • For the NExp/coNExp upper bounds for 𝖠, proceed as above, but guess the BCQ xβ[x] (or q) together with the certificate that shows that it is entailed by 𝒟,𝒯+, which can be verified in exponential time since BCQ entailment in A is in NExp.

  • 𝖠𝖢0 upper bounds: If 𝖷{𝖫,𝖠,𝖲}, since CQ answering under X is UCQ-rewritable (Fact 5), by Proposition 7, for every ontology 𝒯 in 𝖷, there exists a BUCQ q𝒯 such that for every dataset 𝒟, 𝒟,𝒯 iff 𝒟q𝒯. Moreover, for every BCQ q, 𝒟,𝒯q iff 𝒟q𝒯q𝖱𝖾𝗐(q,𝒯+)q where 𝒯+ is the set of TGDs in 𝒯. This yields the 𝖠𝖢0 data complexity upper bound for consistency checking and BCQ entailment in 𝖷.

3 Dataset repairs of inconsistent databases or knowledge bases

In this section, we define the central notion of a (dataset) repair then present some characterizations of repairs based on the conflict hypergraph of a database or KB and on abstract argumentation frameworks.

3.1 Definition

We assume that all logical theories (sets of ICs or ontologies) we consider are satisfiable and reliable, so that if a database or KB 𝒦=𝒟,𝒯 is inconsistent, the problem stems from the dataset 𝒟. In this context, it makes sense to define (dataset) repairs of 𝒦 as consistent datasets that minimally differ from 𝒟. In the database setting, one can restore consistency by deleting and/or adding facts to 𝒟 (if 𝒟={P(c)} and 𝒯={P(x)Q(x)}, we can obtain a consistent database by removing P(c) or by adding Q(c) to 𝒟), except for anti-monotone constraints for which only deleting facts can solve a constraint violation. In the KB setting, because of the open world assumption, repairs can only be obtained by removing facts.

Definition 10 (Dataset repairs).

A symmetric difference repair, or Δ-repair, of 𝒟 w.r.t. 𝒯 is a 𝒯-consistent dataset such that there is no 𝒯-consistent such that Δ𝒟Δ𝒟, where Δ is the symmetric difference operator: S1ΔS2=(S1S2)(S2S1).

A subset repair (resp. superset repair), or -repair (resp. -repair), of 𝒟 w.r.t. 𝒯 is a 𝒯-consistent dataset such that 𝒟 (resp. 𝒟) and there is no 𝒯-consistent such that 𝒟 (resp. 𝒟).

For 𝒦=𝒟,𝒯 and x{Δ,,}, we use S-𝑅𝑒𝑝x(𝒦) or S-𝑅𝑒𝑝x(𝒟,𝒯) to denote the set of all x-repairs of 𝒦, i.e., x-repairs of 𝒟 w.r.t. 𝒯. When 𝒦 is a KB or a database with anti-monotone ICs, S-𝑅𝑒𝑝Δ(𝒦)=S-𝑅𝑒𝑝(𝒦) and S-𝑅𝑒𝑝(𝒦)= if 𝒦 is inconsistent, so we can simply write S-𝑅𝑒𝑝(𝒦) for S-𝑅𝑒𝑝(𝒦) and talk about “repairs” instead of -repairs.

In the above definition, the “S” in S-𝑅𝑒𝑝x(𝒦) can be understood as “standard” or “set-inclusion-based”, in contrast with the optimal repairs that we consider in Section 5 and which compare datasets using other criteria than set-inclusion. It follows from the definition that S-𝑅𝑒𝑝(𝒦)S-𝑅𝑒𝑝Δ(𝒦) and S-𝑅𝑒𝑝(𝒦)S-𝑅𝑒𝑝Δ(𝒦).

Example 11.

Recall 𝒟𝖣𝖡,𝒯𝖣𝖡 from Example 1. The Δ-repairs of 𝒟𝖣𝖡 w.r.t. 𝒯𝖣𝖡 are as follows, among which only 1 and 1 are -repairs:

1={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
1={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
2={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(456),
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
2={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(456),
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
3={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(456),
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
3={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(456),
𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
4c={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,c),
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)} for c𝐂
4c={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,c),
𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)} for c𝐂
5c={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,c),
𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)} for c𝐂
5c={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456,𝐵𝑒𝑎,𝐵𝑙𝑢𝑒),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,c),
𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)} for c𝐂

plus for each repair that contains 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑎,𝐴𝑧𝑢𝑟𝑒), the repair obtained by replacing this fact by 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123,𝐴𝑛𝑛,𝐴𝑧𝑢𝑟𝑒). Note that there are infinitely many repairs since c can be any constant.

Now recall 𝒟𝖣𝖫,𝒯𝖣𝖫 from Example 3. The repairs of 𝒟𝖣𝖫 w.r.t. 𝒯𝖣𝖫 are as follows:

1= {𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
2= {𝖲𝗍𝗎𝖽𝖾𝗇𝗍(456),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
3= {𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖴𝗇𝖽𝖾𝗋𝗀𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}
4= {𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(123,456),𝖦𝗋𝖺𝖽𝖢𝗈𝗎𝗋𝗌𝖾(CS1)}

with

={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(123),𝖫𝖺𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑧𝑢𝑟𝑒),𝖫𝖺𝗌𝗍𝖭𝖺𝗆𝖾(456,𝐵𝑙𝑢𝑒),𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑎),
𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛),𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(456,𝐵𝑒𝑎),𝖳𝖺𝗄𝖾𝖢𝗈𝗎𝗋𝗌𝖾(456,CS1)}

Note that if we made the unique name assumption, we would obtain eight repairs {i,i′′1i4} with i=i{𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑎)} and i′′=i{𝖥𝗂𝗋𝗌𝗍𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛)}.

 Remark 12 (KBs with closed predicates).

KBs with closed predicates, in which some predicates are interpreted under the closed world assumption, have also been studied (e.g., [111, 119, 39]). In this context, it makes sense to consider Δ-repairs also for KBs. However, the investigation of inconsistency handling for such KBs has just started, and focused on -repairs [116].

3.2 Repair characterization via the conflict hypergraph

If 𝒦=𝒟,𝒯 is a KB or a database with anti-monotone ICs (hence for which Δ-repairs and -repairs coincide), it is well known that the (subset) repairs of 𝒟 w.r.t. 𝒯 are the maximal independent sets of the conflict hypergraph whose vertices are the facts in 𝒟 and whose hyperedges are the conflicts of 𝒦:

Definition 13 (Conflicts of a KB or database with anti-monotone constraints).

Let 𝒦=𝒟,𝒯 be a KB or a database with anti-monotone ICs. A conflict of 𝒦 is a -minimal 𝒯-inconsistent subset of 𝒟. We denote by 𝐶𝑜𝑛𝑓(𝒦) or 𝐶𝑜𝑛𝑓(𝒟,𝒯) the set of all conflicts of 𝒦.

Proposition 14.

Let 𝒦=𝒟,𝒯 be a KB or a database with anti-monotone ICs and 𝒟. Then S-𝑅𝑒𝑝(𝒦) iff is a maximal independent set of 𝒢=(𝒟,𝐶𝑜𝑛𝑓(𝒦)).

Example 15.

Let 𝒦=𝒟,𝒯 with 𝒟={A(a),B(a),C(a),D(a),E(a)} and

𝒯={ ABC,AD,CE,DE}.

The conflict hypergraph 𝒢=(𝒟,𝐶𝑜𝑛𝑓(𝒦)) is pictured below, and the repairs of 𝒦 are its three maximal independent sets.

For databases with constraints which are not anti-monotone, which may be violated because of the absence of some fact, the notion of conflict hypergraph is less direct. However, for universal constraints (which have no existential quantifier in the head), we can define a conflict hypergraph whose vertices are literals (i.e., facts or negated facts) that express whether a fact belongs to the dataset or not [32]. Conflicts can then be defined as minimal sets of literals that necessarily lead to a constraint violation.

Definition 16 (Conflicts of a database with universal constraints).

Let 𝒦=𝒟,𝒯 be a database such that 𝒯 is a set of UCs. Let 𝐹𝑎𝑐𝑡𝑠𝒟𝒯 be the union of 𝒟 and facts of the form P(c1,,cn) where P is a predicate that occurs in 𝒯, and c1,,cn are constants that occur in 𝒟, and let 𝐿𝑖𝑡𝑠𝒟𝒯=𝒟{¬αα𝐹𝑎𝑐𝑡𝑠𝒟𝒯𝒟} be the set of literals of 𝒟. A conflict of 𝒦 is a -minimal set 𝒞𝐿𝑖𝑡𝑠𝒟𝒯 such that for every interpretation , if 𝒞, then ⊧̸𝒯.

Proposition 17 ([32, Prop. 2]).

Let 𝒦=𝒟,𝒯 be a database such that 𝒯 is a set of UCs and 𝐹𝑎𝑐𝑡𝑠𝒟𝒯. Let 𝐼𝑛𝑡𝒟()=(𝒟){¬αα𝐹𝑎𝑐𝑡𝑠𝒟𝒯(𝒟)} be the set of literals upon which and 𝒟 agree. Then S-𝑅𝑒𝑝Δ(𝒦) iff 𝐼𝑛𝑡𝒟() is a maximal independent set of 𝒢=(𝐿𝑖𝑡𝑠𝒟𝒯,𝐶𝑜𝑛𝑓(𝒦)).

Example 18 ([32]).

Let 𝒟={A(a),B(a)} and 𝒯 be the following set of UCs:

𝒯={ A(x)C(x),B(x)D(x),C(x)D(x)}

The conflicts, conflict graph (binary conflicts) and Δ-repairs of 𝒟 w.r.t. 𝒯 are as follows:

𝐶𝑜𝑛𝑓(𝒟,𝒯)={{A(a),¬C(a)},{B(a),¬D(a)},{A(a),B(a)}}
S-𝑅𝑒𝑝Δ(𝒟,𝒯)={,{A(a),C(a)},{B(a),D(a)}}

The first (resp. second) conflict directly violates the first (resp. second) IC. To see why {A(a),B(a)} is also a conflict, consider any interpretation such that {A(a),B(a)}. Then if ⊧̸C(a) or ⊧̸D(a), violates the first or second constraint, respectively, and if C(a) and D(a), it violates the third constraint.

We can obtain, e.g., the second repair, {A(a),C(a)} by considering the maximal independent set of the conflict hypergraph {A(a),¬D(a)}, which gives the literals upon which the repair and 𝒟 agree (so implicitly also those on which they disagree: B(a) and ¬C(a), which have to be “flipped” to obtain the repair {A(a),C(a)}).

3.3 Connections with abstract argumentation

A long line of work connects inconsistent KBs and argumentation frameworks, a formalism that aims at representing and reasoning with contradictory information [7, 85, 67, 10]. We present here some very simple reductions from inconsistent KBs or databases to abstract argumentation frameworks, which will also serve as a basis when we discuss the relationships between more involved notions of preferred repair and abstract argumentation in Section 5.

Background on abstract argumentation.

We start by introducing the basics of abstract argumentation frameworks [76] and their extension with collective attacks [81].

Definition 19 (Argumentation framework).

An argumentation framework (AF) is a pair (𝐴𝑟𝑔𝑠,) where 𝐴𝑟𝑔𝑠 is a finite set of arguments and 𝐴𝑟𝑔𝑠×𝐴𝑟𝑔𝑠 is the attack relation. When (α,β), we say that α attacks β, alternatively denoted by αβ.

Definition 20 (Set-based argumentation framework).

A set-based AF (SETAF) is a pair (𝐴𝑟𝑔𝑠,) where 𝐴𝑟𝑔𝑠 is a finite set of arguments and (2𝐴𝑟𝑔𝑠{})×𝐴𝑟𝑔𝑠 is the attack relation. We say that S attacks α, and write Sα, to mean (S,α).

Given an AF (𝐴𝑟𝑔𝑠,) and some A𝐴𝑟𝑔𝑠, let A+={βαβ for some αA} be the set of arguments attacked by arguments from A. A set A𝐴𝑟𝑔𝑠 defends γ𝐴𝑟𝑔𝑠 iff {ββγ}A+. If (𝐴𝑟𝑔𝑠,) is a SETAF, these definitions are adapted as expected: A+={βSβ for some SA} and A defends β iff A+S whenever Sβ.

Given a (SET)AF F=(𝐴𝑟𝑔𝑠,), a set A𝐴𝑟𝑔𝑠 is conflict-free if AA+=. The characteristic function ΓF:2𝐴𝑟𝑔𝑠2𝐴𝑟𝑔𝑠 of F is defined as follows: ΓF(A)={αα is defended by A}. A set A𝐴𝑟𝑔𝑠 is admissible if it is conflict-free and defends itself: AΓF(A). (SET)AF semantics are based upon sets of arguments called extensions.

Definition 21 (Extensions).

Let F=(𝐴𝑟𝑔𝑠,) be a (SET)AF. Then E𝐴𝑟𝑔𝑠 is a:

  • naive extension iff E is a -maximal conflict-free subset of 𝐴𝑟𝑔𝑠;

  • preferred extension iff E is a -maximal admissible set;

  • stable extension iff E+=𝐴𝑟𝑔𝑠E.

Stable extensions are preferred extensions but the converse does not hold in general [76].

Example 22.

The AF depicted below has the following extensions.

Naive extensions: {α,γ}, {α,δ}, {α,ϵ}, {β,δ}, {β,ϵ}
Preferred extensions: {α}, {β,δ}
Stable extension: {β,δ}
From KB and database repairs to (SET)AF extensions.

Let 𝒦=𝒟,𝒯 be a KB or a database with anti-monotone ICs and assume that 𝒟 does not contain any self-conflicting fact (i.e., there is no fact α𝒟 such that {α},𝒯). The SETAF associated to 𝒦 is F𝒦=(𝒟,𝒦), where 𝒦={(𝒞{α},α)𝒞𝐶𝑜𝑛𝑓(𝒦),α𝒞} [30]. This SETAF is strongly symmetric, which implies that preferred and stable extensions coincide [30].

Proposition 23 ([30]).

Let 𝒦=𝒟,𝒯 be a KB or a database with anti-monotone ICs without self-conflicting facts, F𝒦=(𝒟,𝒦) be its associated SETAF and 𝒟.

  • S-𝑅𝑒𝑝(𝒦) iff is a naive extension of F𝒦.

  • S-𝑅𝑒𝑝(𝒦) iff is a preferred extension of F𝒦.

  • S-𝑅𝑒𝑝(𝒦) iff is a stable extension of F𝒦.

Example 24.

Consider 𝒦=𝒟,𝒯 defined in Example 15. The SETAF associated to 𝒦 is F𝒦=({A(a),B(a),C(a),D(a),E(a)},𝒦) where 𝒦 is as follows.

{A(a),B(a)}𝒦C(a) {A(a),C(a)}𝒦B(a) {B(a),C(a)}𝒦A(a)
{A(a)}𝒦D(a) {D(a)}𝒦A(a)
{C(a)}𝒦E(a) {E(a)}𝒦C(a)
{D(a)}𝒦E(a) {E(a)}𝒦D(a)

Since this reduction relies entirely on the relationship between repairs and conflicts, it is not difficult to extend it to handle the case of Δ-repairs of database with UCs, using literals instead of facts as the set of arguments. We did however not define conflicts for a database whose ICs have existential quantifiers in the head so we cannot easily extend the preceding reduction to such databases. However, there is also a connection between -repairs of databases with inclusion dependencies (of the form P(x)yQ[x,y]) and functional dependencies (of the form P(x)P(y)iIxi=yijJxj=yj) and AF extensions [113]. Let 𝒦=𝒟,𝒯 be a database such that 𝒯 is a set of IDs and FDs. The AF associated to 𝒦 is F𝒦=(𝐴𝑟𝑔𝑠𝒦,𝒦), where 𝐴𝑟𝑔𝑠𝒦=𝒟{ατα𝒟,τ𝒯,α=P(c),τ=P(x)yQ[x,y]} and

𝒦={ (α,β),(β,α)τ𝒯,τ FD ,{α,β},{τ}}
{ (ατ,α),(ατ,ατ)ατ𝐴𝑟𝑔𝑠𝒦}
{ (β,ατ)ατ𝐴𝑟𝑔𝑠𝒦,α=P(c),τ=P(x)yQ[x,y],β𝒟,β=Q[c,d]}.

The first line corresponds to the attack relation of the (SET)AF associated to 𝒟,𝒯𝖥𝖣, where 𝒯𝖥𝖣 is the set of FDs in 𝒯, as defined before, while the second and third lines deal with the IDs: each ατ attacks α𝒟 that requires the presence of some fact to satisfy τ and is attacked by such facts β that are in 𝒟.

Proposition 25 ([113]).

Let 𝒦=𝒟,𝒯 with 𝒯 a set of IDs and FDs, F𝒦=(𝐴𝑟𝑔𝑠𝒦,𝒦) be its associated AF and 𝒟. Then S-𝑅𝑒𝑝(𝒦) iff is a preferred extension of F𝒦.

Naive, stable and preferred extensions may not coincide in this case, as illustrated below.

Example 26.

Let 𝒟={α,β,γ,δ} with α=P(c), β=P(d), γ=Q(d,e), and δ=Q(d,f) and 𝒯 consists of the ID τ=P(x)yQ(x,y) and the FD Q(x,y)Q(x,z)y=z. The AF associated with 𝒦 is such that 𝐴𝑟𝑔𝑠𝒦={α,β,γ,δ,ατ,βτ}, and 𝒦 is as follows.

γ𝒦δ δ𝒦γ ατ𝒦α ατ𝒦ατ βτ𝒦β βτ𝒦βτ γ𝒦βτ δ𝒦βτ

The naive extensions of F𝒦=(𝐴𝑟𝑔𝑠𝒦,𝒦) are {α,β,γ} and {α,β,δ}. Its preferred extensions are {β,γ} and {β,δ} (since α is not defended against ατ), which are also the two -repairs of 𝒦. However, there is no stable extension (since for every E𝐴𝑟𝑔𝑠𝒦, either ατE so that ατE+ while ατ𝐴𝑟𝑔𝑠𝒦E, or ατE so that ατE+ while ατ𝐴𝑟𝑔𝑠𝒦E).

From AF extensions to database repairs.

Interestingly, it was recently shown that in the other direction, every AF can be encoded as an inconsistent database (using IDs and FDs) whose -repairs correspond to the preferred extensions of the AF [112].

4 Inconsistency-tolerant semantics

In this section, we briefly review the inconsistency-tolerant semantics that have been proposed in the literature, with a focus on those based on dataset repairs. For more details and examples, we refer to previous chapter and survey on inconsistency handling in DL KBs [29, 28].

4.1 Repair-based semantics

In the following definitions we use the notation S-𝑅𝑒𝑝(𝒦) even when 𝒦 is a database with general ICs, meaning that we can choose between S-𝑅𝑒𝑝Δ(𝒦), S-𝑅𝑒𝑝(𝒦) or S-𝑅𝑒𝑝(𝒦) when relevant to get three variants of each semantics. The relationships between the semantics and their properties are summarized in Figure 2, and Example 36 illustrates them.

Consistent query answering (CQA), a.k.a. AR semantics.

The most studied and well-established inconsistency-tolerant semantics, called consistent query answering (CQA) in the database community [8, 25] and AR (ABox Repair) semantics in the DL community [98, 99], considers that a query answer holds if it holds in every repair. This mode of reasoning is also known as cautious reasoning, e.g., in the area of abstract argumentation.

Definition 27 (CQA semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the CQA semantics iff ,𝒯q(a) for every S-𝑅𝑒𝑝(𝒦).

Under-approximations of CQA.

Several semantics that under-approximate CQA, in the sense that they provide a subset of the consistent query answers, have been considered, either with the goal of achieving a lower computational complexity of reasoning or to obtain answers that are even more “sure” than the consistent query answers. The first one, introduced under the name of IAR (Intersection of ABox Repairs) semantics [98, 99] and sometimes called intersection semantics, evaluates the queries over the intersection of the repairs.

Definition 28 (Intersection semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the intersection semantics iff ,𝒯q(a) where =S-𝑅𝑒𝑝(𝒦).

The ICR (Intersection of Closed Repairs) semantics achieves a finer approximation of CQA than the intersection semantics by logically closing repairs with respect to the ontology before intersecting them [27]. Given a 𝒯-consistent dataset , the closure of w.r.t. 𝒯, denoted 𝖼𝗅𝒯(), is the set of all facts entailed by ,𝒯.

Definition 29 (ICR semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the ICR semantics iff cl,𝒯q(a) where cl=S-𝑅𝑒𝑝(𝒦)𝖼𝗅𝒯().

 Remark 30.

If 𝒦 is a database, 𝖼𝗅𝒯()= so the ICR and intersection semantics coincide.

The family of k-support semantics was introduced to generalize the intersection semantics and obtain more fine-grained under-approximations of CQA, such that increasing the value of k yields a closer approximation [41]. A support of a Boolean query q in 𝒦=𝒟,𝒯 is a 𝒯-consistent subset 𝒮𝒟 such that 𝒮,𝒯q.

Definition 31 (k-support semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the k-support semantics iff there exist k (not necessarily distinct) supports 𝒮1,,𝒮k of q(a) in 𝒦 such that for every S-𝑅𝑒𝑝(𝒦), there is some 𝒮i.

Over-approximations of CQA.

Instead of approximating CQA from below, we can over-approximate it, by computing a super-set of the consistent query answers. The brave semantics considers all answers that hold in some repair [41].

Definition 32 (Brave semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the brave semantics iff ,𝒯q(a) for some S-𝑅𝑒𝑝(𝒦).

The non-objection semantics refines the brave semantics by retaining only the brave query answers that are consistent with all repairs [23].

Definition 33 (Non-objection semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the non-objection semantics iff (i) ,𝒯q(a) for some S-𝑅𝑒𝑝(𝒦) and (ii) for every S-𝑅𝑒𝑝(𝒦), there is a model of ,𝒯 such that q(a).

The majority-based semantics is another refinement of brave that requires that the answer holds in more than half of the repairs [19]. This semantics can be adapted to use any threshold instead of 12 and is closely related to the semantics that associates to each brave query answer the percentage (or number) of repairs in which it holds, which attracted quite a lot of attention in the database setting, with theoretical results on the precise complexity of the counting problem depending on the classes of constraints and queries [118, 48, 52] as well as approximation schemes [49].

Definition 34 (Majority-based semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the majority-based semantics iff |S-𝑅𝑒𝑝(𝒦),,𝒯q(a)||S-𝑅𝑒𝑝(𝒦)|>12.

Finally, the family of k-defeater semantics provides fine-grained over-approximations of CQA, where increasing the value of k yields a closer approximation [41] (note that even if the following definition does not mention a repair, the set is a subset of a repair that does not entail the query, so we consider this semantics as “repair-based”).

Definition 35 (k-defeater semantics).

A tuple a is an answer to the query q(x) over 𝒦=𝒟,𝒯 under the k-defeater semantics iff there does not exist a 𝒯-consistent subset of 𝒟 with ||k such that 𝒮,𝒯 for every minimal support 𝒮 of q(a) in 𝒦.

Properties and relationships between repair-based semantics.

Figure 2 (left) shows the relationships between the repair-based inconsistency-tolerant semantics. Following [29, 28], we also recall in Figure 2 (right) which desirable properties these semantics have (note that all repair-based semantics have the Consistent Support property, contrary to some non repair-based inconsistency-tolerant semantics, cf. Section 4.2). We conclude with an example to illustrate the differences between these semantics.

Semantics with the property
Consistent Support all
Consistent Results intersection, ICR, k-support,
CQA, non-objection
Unique Base intersection, ICR
  • Consistent Support: for every 𝒟,𝒯, q(x) and a, if a is an answer to q(x) over 𝒟,𝒯 under Sem, then there exists a 𝒯-consistent subset 𝒮 of 𝒟 such that 𝒮,𝒯q(a).

  • Consistent Results: for every 𝒟,𝒯, there exists a model of 𝒯 such that for every q(x) and a, if a is an answer to q(x) over 𝒟,𝒯 under Sem, then q(a).

  • Unique Base: for every 𝒟,𝒯, there exists a 𝒯-consistent dataset 𝒟 such that for every q(x) and a, a is an answer to q(x) over 𝒟,𝒯 under Sem iff 𝒟,𝒯q(a).

Figure 2: (left) Relationships between repair-based semantics (adapted from [28, Fig. 1]). An arrow SemSem means that if a is an answer to q(x) over 𝒦 under Sem, then it is also an answer under Sem. (right) Properties of repair-based semantics (adapted from [28, Fig. 2]).
Example 36.

Consider the following DL-Litecore KB. The ontology expresses that associate and full professors are professors, professors and postdoctoral fellows are PhD holders and belong to some department, postdoctoral fellows have some supervisor, that one cannot be both an associate and a full professor or a postdoctoral fellow and a professor, and that the range of the roles 𝖢𝗁𝖺𝗂𝗋 and 𝖳𝖾𝖺𝖼𝗁 are disjoint.

𝒯={ 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿𝖯𝗋𝗈𝖿,𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿𝖯𝗋𝗈𝖿,𝖯𝗋𝗈𝖿𝖯𝗁𝖽,𝖯𝗈𝗌𝗍𝖽𝗈𝖼𝖯𝗁𝖽,
𝖯𝗋𝗈𝖿𝖣𝖾𝗉𝖺𝗋𝗍𝗆𝖾𝗇𝗍,𝖯𝗈𝗌𝗍𝗈𝖼𝖣𝖾𝗉𝖺𝗋𝗍𝗆𝖾𝗇𝗍,𝖯𝗈𝗌𝗍𝖽𝗈𝖼𝖲𝗎𝗉𝖾𝗋𝗏𝗂𝗌𝗈𝗋,
𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿¬𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿,𝖯𝗈𝗌𝗍𝖽𝗈𝖼¬𝖯𝗋𝗈𝖿,𝖢𝗁𝖺𝗂𝗋¬𝖳𝖾𝖺𝖼𝗁}
𝒟={ 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙),
𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅),
𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}

The repairs of 𝒟,𝒯 are as follows:

1={ 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
2={ 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
3={ 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
4={ 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵)}
5={ 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
6={ 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
7={ 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
8={ 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵)}
9={ 𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
10={ 𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
11={ 𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}
12={ 𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅),𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵)}

The KB 𝒟,𝒯 entails the BCQ:

  • 𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜) under the intersection semantics, since i=112i={𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜)};

  • 𝖯𝗁𝖽(𝐶𝑎𝑟𝑜𝑙) under

    • the ICR semantics, since i=112𝖼𝗅𝒯(i)={𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐴𝑙𝑔𝑜),𝖯𝗁𝖽(𝐶𝑎𝑟𝑜𝑙)},

    • the 3-support semantics, since the three supports {𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙)}, {𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙)} and {𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙)} cover all repairs,

    but not under the intersection semantics nor under the 2-support semantics;

  • y𝖣𝖾𝗉𝖺𝗋𝗍𝗆𝖾𝗇𝗍(𝐶𝑎𝑟𝑜𝑙,y) under the CQA semantics, since it is entailed by every repair, but not under the ICR semantics;

  • 𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙) under the majority semantics (it holds in 23 of the repairs), but not under

    • the CQA semantics, since it does not hold in 912,

    • the non-objection semantics, since for i{9,12}, i{𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙)},𝒯,

    • the 1-defeater semantics, since one fact (𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙)) is sufficient to contradict the two minimal supports of 𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙) ({𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙)} and {𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙)});

  • y𝖲𝗎𝗉𝖾𝗋𝗏𝗂𝗌𝗈𝗋(𝐶𝑎𝑟𝑜𝑙,y) under the non-objection semantics since it holds in repairs 912 and is consistent with all repairs, but not under

    • the CQA semantics, since it does not hold in 18,

    • the majority semantics, since it holds only in 13 of the repairs,

    • the 1-defeater semantics, since one fact (e.g., 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙)) is sufficient to contradict the only minimal support of y𝖲𝗎𝗉𝖾𝗋𝗏𝗂𝗌𝗈𝗋(𝐶𝑎𝑟𝑜𝑙,y) ({𝖯𝗈𝗌𝗍𝖽𝗈𝖼(𝐶𝑎𝑟𝑜𝑙)});

  • y𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,y) under the 1-defeater semantics, since we need two facts (𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵) and 𝖳𝖾𝖺𝖼𝗁(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)) to contradict the minimal supports {𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐷𝐵)} and {𝖢𝗁𝖺𝗂𝗋(𝐶𝑎𝑟𝑜𝑙,𝐾𝑅)}, but not under the CQA semantics (cf. 1, 5 and 9);

  • 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(𝐶𝑎𝑟𝑜𝑙) under the brave semantics but not under the non-objection, majority or 1-defeater semantics.

4.2 Related work: Semantics that are not based on dataset repairs

Not all inconsistency-tolerant semantics that have been proposed for KBs or databases are based on dataset repairs. We review them only briefly since they are not the main focus of this chapter and received comparatively less attention than the main repair-based semantics.

𝓣-consistent subsets of some closure of 𝓓.

In the KB context, several semantics based on repairs of some closure of the original dataset w.r.t. the ontology were proposed, with the motivation of retaining more consequences and being independent from the KB syntax. The first ones, called the CAR (Closed ABox Repair) and ICAR (Intersection of Closed ABox Repairs) semantics, are the counterparts of the AR (CQA) and IAR (intersection) semantics that use closed repairs defined below instead of dataset repairs [98]. The consistent closure of 𝒟 w.r.t. 𝒯, denoted 𝖼𝗈𝗇𝗌𝖼𝗅𝒯(𝒟), is the set of facts entailed by 𝒯-consistent subsets of 𝒟.

Definition 37 (Closed repairs).

A closed repair of 𝒟,𝒯 is a 𝒯-consistent 𝖼𝗈𝗇𝗌𝖼𝗅𝒯(𝒟) for which there is no 𝒯-consistent 𝖼𝗈𝗇𝗌𝖼𝗅𝒯(𝒟) such that either (i) 𝒟𝒟 or (ii) 𝒟=𝒟 and .

The closed repairs of 𝒟,𝒯 may differ from the (dataset) repairs of 𝖼𝗈𝗇𝗌𝖼𝗅𝒯(𝒟) (see [29, Example 13] for an example) so we get different semantics by using the latter. Another notion of closure of the original dataset was proposed in the context of Datalog± KBs: the positive closure of 𝒟 w.r.t. 𝒯, denoted 𝗉𝗈𝗌𝖼𝗅𝒯(𝒟), is the set of facts entailed by 𝒟,𝒯+ where 𝒯+ is the set of TGDs in 𝒯 [19]. This yields yet another family of semantics based on the repairs of 𝗉𝗈𝗌𝖼𝗅𝒯(𝒟). However, it is not clear how to define positive closure for expressive DLs such as 𝒜𝒞 and 𝒮𝒬, since they cannot be written as Datalog± rules.

Note that in contrast with the repair-based semantics, these semantics do not satisfy the Consistent Support property (cf. [29, Example 15]).

𝓣-consistent quantified datasets.

A long line of work in DL is concerned by modifying a (consistent) KB so that some unwanted consequences do not hold anymore, while preserving as much as possible the other consequences. Some recent work targets in particular dataset modifications, using quantified ABoxes, which allow variables to be used in facts [16, 15]. By identifying sets of atoms with their conjunctions, we can view such a quantified ABox 𝒟 as a BCQ y𝒟 where y contains all variables in 𝒟. The extension of this framework to inconsistent KBs gives rise to an alternative notion of syntax-independent, consequence-preserving, repairs [17, 18]. These repairs have been defined for Horn-DL ontologies, which are such that 𝒯 can be split into a “positive part” 𝒯+, which is such that any dataset is 𝒯+-consistent, and a “negative part” 𝒯 which contains only concept inclusions of the form C. Intuitively, a repair of a dataset 𝒟 w.r.t. an ontology 𝒯 is a quantified ABox y such that 𝒟,𝒯+y, y,𝒯+⊧̸xC(x) for every C𝒯 (and y,𝒯+⊧̸q for other unwanted consequences q, if any). An optimal consequence-preserving repair is then a repair y such that there is no repair z such that z,𝒯+y but y,𝒯+⊧̸z. We omit the formal definitions and details on this framework and simply illustrate how it can be applied in our context.

Example 38.

Let 𝒟,𝒯 be as follows. 𝒯+ contains the two first axioms, 𝒯 the last one.

𝒯={ 𝖳𝖾𝖺𝖼𝗁𝖯𝖾𝗋𝗌𝗈𝗇,𝖳𝖾𝖺𝖼𝗁𝖢𝗈𝗎𝗋𝗌𝖾,𝖯𝖾𝗋𝗌𝗈𝗇𝖢𝗈𝗎𝗋𝗌𝖾}
𝒟={ 𝖳𝖾𝖺𝖼𝗁(𝐷𝑎𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐷𝑎𝑛,𝐾𝑅),𝖳𝖾𝖺𝖼𝗁(𝐴𝑙𝑔𝑜,𝐷𝑎𝑛)}

It holds that the quantified ABoxes x{𝖳𝖾𝖺𝖼𝗁(𝐷𝑎𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐷𝑎𝑛,𝐾𝑅),𝖳𝖾𝖺𝖼𝗁(𝐴𝑙𝑔𝑜,x)} and x{𝖳𝖾𝖺𝖼𝗁(x,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(x,𝐾𝑅),𝖳𝖾𝖺𝖼𝗁(𝐴𝑙𝑔𝑜,𝐷𝑎𝑛)} are optimal consequence-preserving repairs of 𝒟 w.r.t. 𝒯, as well as all those obtained by adding some consequences w.r.t. 𝒯+, such as x{𝖳𝖾𝖺𝖼𝗁(𝐷𝑎𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐷𝑎𝑛,𝐾𝑅),𝖳𝖾𝖺𝖼𝗁(𝐴𝑙𝑔𝑜,x),𝖯𝖾𝗋𝗌𝗈𝗇(𝐷𝑎𝑛),𝖢𝗈𝗎𝗋𝗌𝖾(𝐷𝐵)}. Indeed, two equivalent (quantified) datasets are both optimal repairs or not. Using such repairs allows us to keep the information that 𝐾𝑅 and 𝐷𝐵 courses are taught by the same person, so that x𝖳𝖾𝖺𝖼𝗁(x,𝐷𝐵)𝖳𝖾𝖺𝖼𝗁(x,𝐾𝑅) is entailed under the CQA semantics based on this kind of repair. We also obtain that xy𝖳𝖾𝖺𝖼𝗁(x,𝐾𝑅)𝖳𝖾𝖺𝖼𝗁(𝐴𝑙𝑔𝑜,y) holds under CQA based on such repairs, which shows that the Consistent Support property is not satisfied.

𝓣-consistent subsets of 𝓓 that may not be -maximal.

Some semantics relax the notion of repairs by allowing “too many” facts to be removed to restore consistency. Motivated by computational complexity considerations, the family of k-lazy semantics restores consistency in each connected component of the conflict hypergraph by either removing at most k facts, or by removing the whole connected component if removing k facts is not sufficient to achieve consistency [109]. To get a database counterpart of conflict-free sets of arguments considered in the context of abstract argumentation, a recent work defines “repairs” as 𝒯-consistent subsets of 𝒟, calling “maximal repairs” the standard -repairs [112]. This very relaxed notion of repairs is the basis of the definition of maximally covering (resp. fully covering) repairs which are 𝒯-consistent subsets of 𝒟 that retain as much as possible (resp. all) the constants occurring in 𝒟 at some predicate positions.

Repairs modifying 𝓣.

While most inconsistency-tolerant semantics consider that the logical theory is reliable and repair only the dataset, generalized repairs allow to modify 𝒯 as well as 𝒟 to restore consistency [78]. The definition also allows for splitting 𝒯 and 𝒟 into a hard and a soft part, so that only the soft parts can be modified by a repair.

Attribute-based repairs.

In the database area, attribute-based repairs, which modify the tuples instead of removing them, have been proposed. Many different kinds of attribute-based repairs have been considered: the attribute values can be taken from a database-independent domain, the database domain, or be “nulls” with a specific semantics, and minimality of change can be measured by a numerical aggregation function over differences of attribute values, or set-minimality of the sequence of updates yielding the repair [43, 102, 88, 26].

Operational repairs.

Also in the database area, operational repairs have been defined as the result of applying a repairing sequence of update operations that has to fulfill some conditions [51, 53]. This kind of repair also allows for taking into account the probability of the updates, hence of the repairs and query answers.

5 Preferred repairs

In many scenarios, one can define preferred repairs based on some preference information, such as the relative or absolute reliability of the facts, or some rules modeling the user preferences. In this section, we present the different kinds of preferred (dataset) repair that have been proposed in the literature, their properties, relationships and links with other formalisms for inconsistency handling. Preferred repairs have mostly been defined for -repairs, since it is less natural to consider, e.g., the reliability of some missing facts, but we also consider preferred Δ-repairs when they have been studied. As in Section 4, we conclude with a brief overview of other notions of “optimal repairs” which are not dataset repairs.

Before delving into the specific preferred repair definitions, we start with two general observations on the impact of using preferred (dataset) repairs on repair-based semantics: (1) it increases the number of query answers under CQA and intersection semantics while it decreases the number of answers under brave semantics, and (2) it preserves the relationships between the semantics presented in Figure 2.

Proposition 39.

Let X-CQA, X-intersection and X-brave be the counterparts of the CQA, intersection and brave semantics that use preferred repairs from some X-𝑅𝑒𝑝(𝒦)S-𝑅𝑒𝑝(𝒦) instead of standard (- or Δ-)repairs. If q is entailed by 𝒦 under:

  • CQA (resp. intersection), then it is also entailed under X-CQA (resp. X-intersection);

  • X-brave, then it is also entailed under brave.

Moreover, if q is entailed by 𝒦 under:

  • X-intersection, then it is entailed under X-CQA;

  • X-CQA, then it is entailed under X-brave.

5.1 Preferred repairs based on a preorder over datasets (,𝒘,𝑷,𝑷)

The first category of preferred repairs is based on a generalization of the definition of dataset repairs (cf. Definition 10) using a preorder (i.e., a reflexive and transitive binary relation) over datasets instead of set-inclusion. We write to indicate that and .

Definition 40 (Strictly -monotone preorder).

A preorder over datasets is strictly -monotone iff implies .

Definition 41 (-optimal repairs).

Let be a strictly -monotone preorder over datasets.

  • A -optimal -repair of 𝒟 w.r.t. 𝒯 is a 𝒯-consistent dataset 𝒟 such that there is no 𝒯-consistent 𝒟 such that .

  • A -optimal Δ-repair of 𝒟 w.r.t. 𝒯 is a 𝒯-consistent dataset such that there is no 𝒯-consistent such that Δ𝒟Δ𝒟.

We write -𝑅𝑒𝑝(𝒦) (resp. -𝑅𝑒𝑝(𝒦), -𝑅𝑒𝑝Δ(𝒦)) to denote the set of -optimal (resp. -, Δ-) repairs of 𝒦.

 Remark 42.

The condition that is strictly -monotone implies that -optimal -repairs are indeed -repairs, and -optimal Δ-repairs are Δ-repairs (i.e., -𝑅𝑒𝑝(𝒦)S-𝑅𝑒𝑝(𝒦) and -𝑅𝑒𝑝Δ(𝒦)S-𝑅𝑒𝑝Δ(𝒦)). Hence Proposition 39 applies.

We next introduce the four types of -optimal repairs that received the most attention. Their properties and relationships as well as examples are given at the end of this section.

Cardinality ().

Cardinality-based repairs use the preorder that compares datasets based on their cardinality:

 iff ||||.

The -optimal Δ-repairs are those that make the fewest updates. In particular, -optimal -repairs drop the fewest facts, and are thus more appropriate when it is believed that all the facts in the dataset have the same (small) probability of being erroneous. Cardinality-based repairs have been studied for DL and Datalog± KBs [33, 108] as well as for both Δ-repairs and -repairs in the database setting [9, 102, 4, 74].

Weight (𝒘).

Weight-based repairs require a function w that assigns a (positive) weight to each fact and induces a preorder w over datasets:

w iff Σαw(α)Σαw(α).

Weights can be used to model the reliability of different facts in 𝒟 (e.g., if it is built using information extraction techniques, the weights may be derived from the confidence levels output by the extraction tool). In the case of Δ-repairs, one needs to assign a weight to all possible facts (since w-optimal Δ-repairs minimize the weight of the symmetric difference between 𝒟 and the repair). This can be done, e.g., by assigning the same weight to all facts that do not belong to 𝒟, to penalize every addition in the same way while taking into account different reliability levels for facts from 𝒟. This kind of repair has been studied for DL and Datalog± KBs [73, 33, 107] and for databases [102, 100, 122].

Prioritized set inclusion (𝑷).

Repairs based on priority levels and set-inclusion require that the dataset 𝒟 is partitioned into priority levels: a prioritization of 𝒟 is a tuple P=𝒫1,,𝒫n of disjoint datasets such that 𝒟=i=1n𝒫i. Facts in 𝒫1 are considered the most reliable and those in 𝒫n the least reliable. A prioritization P=𝒫1,,𝒫n induces a set-inclusion-based preorder P:

P iff either 𝒫i=𝒫i for every 1in,
or there is some 1in such that
𝒫i𝒫i and 𝒫j=𝒫j for 1j<i.

Prioritizations are a natural way to distinguish facts coming from different sources, separate a part of the dataset that has already been validated from recent additions, or to take into account that some predicates are known to be more reliable than others. P-optimal repairs have been mostly studied for DL and Datalog± KBs [33, 107] but also extended to Δ-repairs of databases with universal constraints [32]. In this case, we consider a prioritization P=𝒫1,,𝒫n of the set of relevant literals 𝐿𝑖𝑡𝑠𝒟𝒯 (cf. Definition 16) so that we keep the intuition that the more reliable a literal λ (which expresses whether a fact is true or false w.r.t. 𝒟), the smaller the index of 𝒫i that contains λ. We then simply drop the negation in literals to get the corresponding prioritization of all relevant facts 𝐹𝑎𝑐𝑡𝑠𝒟𝒯, P=𝒫1,,𝒫n with 𝒫i=(𝒫i𝒟){α¬α𝒫i}, and use P instead of P in the definition of P (additionally setting P for every 𝐹𝑎𝑐𝑡𝑠𝒟𝒯 and 𝐹𝑎𝑐𝑡𝑠𝒟𝒯). We can show that the definition of P-optimal Δ-repairs given in [32] is indeed equivalent to that of Definition 41 using this preorder by observing that for all ,𝐹𝑎𝑐𝑡𝑠𝒟𝒯, Δ𝒟PΔ𝒟 iff there is some 1in such that

  • 𝐼𝑛𝑡𝒟()𝒫i𝐼𝑛𝑡𝒟()𝒫i (recall from Proposition 17 that 𝐼𝑛𝑡𝒟()=(𝒟){¬αα𝐹𝑎𝑐𝑡𝑠𝒟𝒯(𝒟)} is the set of literals upon which and 𝒟 agree) and

  • 𝐼𝑛𝑡𝒟()𝒫j=𝐼𝑛𝑡𝒟()𝒫j for 1j<i.

Prioritized cardinality (𝑷).

A prioritization P=𝒫1,,𝒫n also induces a cardinality-based preorder P:

P iff either |𝒫i|=|𝒫i| for every 1in,
or there is some 1in such that
|𝒫i|<|𝒫i| and |𝒫j|=|𝒫j| for 1j<i.

P-optimal repairs have been studied for DL and Datalog± KBs [33, 107] but we can extend their definition to Δ-repairs of databases with universal constraints in the same way as for P-optimal repairs. Note that with P and P, a single fact on level 𝒫i is preferred to any number of facts from 𝒫i+1. This makes these preorders best suited for cases in which there is a significant difference in the perceived reliability of adjacent priority levels.

Properties and relationships.

In this paragraph, we use -𝑅𝑒𝑝(𝒦) ({,w,P,P}) and S-𝑅𝑒𝑝(𝒦) to denote the (-optimal) - or Δ-repairs of a KB or database 𝒦.

  • If w assigns the same weight to every fact, then w-𝑅𝑒𝑝(𝒦) and -𝑅𝑒𝑝(𝒦) coincide, i.e., weight-based repairs generalize cardinality-based repairs.

  • Given a prioritization P=𝒫1,,𝒫n, let u=(𝗆𝖺𝗑i=1n|𝒫i|)+1, and let w be defined by w(α)=uni for α𝒫i (or in case of Δ-repairs, w(α)=uni for α𝒫i or ¬α𝒫i). Then for every 𝒯, P-𝑅𝑒𝑝(𝒟,𝒯) and w-𝑅𝑒𝑝(𝒟,𝒯) coincide [44, Lemma 6.2.5]. Hence weight-based repairs also generalize repairs based on prioritized cardinality.

  • If a prioritization assigns all facts (or literals) to the same priority level, then P-𝑅𝑒𝑝(𝒦) and S-𝑅𝑒𝑝(𝒦) coincide, and P-𝑅𝑒𝑝(𝒦) and -𝑅𝑒𝑝(𝒦) coincide.

Examples.

Examples 43 and 44 illustrate the four kinds of -optimal repair, for KBs and Δ-repairs of databases with UCs, respectively.

Example 43 ([44]).

Consider the DL-Litecore KB 𝒦=𝒟,𝒯 defined as follows.

𝒯={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍𝖯𝖾𝗋𝗌𝗈𝗇,𝖯𝗋𝗈𝖿𝖯𝖾𝗋𝗌𝗈𝗇,𝖲𝗍𝗎𝖽𝖾𝗇𝗍¬𝖯𝗋𝗈𝖿,
𝖳𝖾𝖺𝖼𝗁𝖯𝗋𝗈𝖿,𝖳𝖾𝖺𝖼𝗁𝖢𝗈𝗎𝗋𝗌𝖾,𝖢𝗈𝗎𝗋𝗌𝖾¬𝖯𝖾𝗋𝗌𝗈𝗇}
𝒟={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛),𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐾𝑅),
𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐵𝑜𝑏),𝖯𝗋𝗈𝖿(𝐵𝑜𝑏),𝖳𝖾𝖺𝖼𝗁(𝐾𝑅,𝐵𝑜𝑏),𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,𝐴𝑙𝑔𝑜)}

The set of repairs S-𝑅𝑒𝑝(𝒦) contains:

1= {𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐵𝑜𝑏)}
2= {𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐾𝑅),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐵𝑜𝑏)}
3= {𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛),𝖯𝗋𝗈𝖿(𝐵𝑜𝑏),𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,𝐴𝑙𝑔𝑜)}
4= {𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐾𝑅),𝖯𝗋𝗈𝖿(𝐵𝑜𝑏),𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,𝐴𝑙𝑔𝑜)}
5= {𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛),𝖳𝖾𝖺𝖼𝗁(𝐾𝑅,𝐵𝑜𝑏)}
6= {𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐾𝑅,𝐵𝑜𝑏)}

Observe that 𝖯𝖾𝗋𝗌𝗈𝗇(𝐴𝑛𝑛) is entailed under CQA semantics, but not under intersection semantics, as the intersection of the repairs is empty. On the other hand, every fact from 𝒟 is entailed under brave. By using -optimal repairs, we can obtain further answers under -CQA and -intersection semantics, and eliminate some answers under -brave semantics.

  • We have -𝑅𝑒𝑝(𝒦)={4}, so 𝖯𝗋𝗈𝖿(𝐴𝑛𝑛) and 𝖯𝗋𝗈𝖿(𝐵𝑜𝑏) are entailed under -intersection, while they were not entailed under (plain) CQA semantics. On the other hand, using -optimal repairs rules out 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛), 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐵𝑜𝑏) and 𝖳𝖾𝖺𝖼𝗁(𝐾𝑅,𝐵𝑜𝑏), which do not hold under the -brave semantics.

  • Suppose we have the prioritization P=𝒫1,𝒫2, based on the reliability of the predicates:

    𝒫1= {𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛),𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐵𝑜𝑏),𝖯𝗋𝗈𝖿(𝐵𝑜𝑏)}
    𝒫2= {𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐷𝐵),𝖳𝖾𝖺𝖼𝗁(𝐴𝑛𝑛,𝐾𝑅),𝖳𝖾𝖺𝖼𝗁(𝐾𝑅,𝐵𝑜𝑏),𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,𝐴𝑙𝑔𝑜)}

    We obtain P-𝑅𝑒𝑝(𝒦)={1,3} and P-𝑅𝑒𝑝(𝒦)={3}. Now 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛) is entailed under the P-intersection and P-intersection semantics, whereas it was not entailed under (plain) CQA semantics, and it conflicts with a fact entailed under the -intersection semantics. Note that 𝖯𝗋𝗈𝖿(𝐵𝑜𝑏) is entailed under P-intersection semantics, but only the less specific 𝖯𝖾𝗋𝗌𝗈𝗇(𝐵𝑜𝑏) is entailed under P-CQA semantics.

  • If we assign facts in 𝒫1 a weight of 2, and facts of 𝒫2 a weight of 1, w-𝑅𝑒𝑝(𝒦)={3,4}. Under w-CQA semantics, neither 𝖯𝗋𝗈𝖿(𝐴𝑛𝑛) nor 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(𝐴𝑛𝑛) is entailed, but only 𝖯𝖾𝗋𝗌𝗈𝗇(𝐴𝑛𝑛). Under w-intersection semantics, 𝖯𝗋𝗈𝖿(𝐵𝑜𝑏) is entailed.

Example 44.

Consider the database (with UCs) 𝒦=𝒟,𝒯 defined as follows.

𝒯={ 𝖭𝖺𝗆𝖾(x,y)𝖯𝖾𝗋𝗌𝗈𝗇(x),𝖳𝖾𝖺𝖼𝗁(x,y)𝖯𝖾𝗋𝗌𝗈𝗇(x),
𝖳𝖾𝖺𝖼𝗁(x,y)𝖢𝗈𝗎𝗋𝗌𝖾(y),𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖯𝖾𝗋𝗌𝗈𝗇(x)}
𝒟={ 𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛),𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,123)}

The set of Δ-repairs S-𝑅𝑒𝑝Δ(𝒦) contains:

1={𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛), 𝖯𝖾𝗋𝗌𝗈𝗇(123)}
i.e., 1Δ𝒟={𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,123),𝖯𝖾𝗋𝗌𝗈𝗇(123)}
2={𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,123), 𝖯𝖾𝗋𝗌𝗈𝗇(𝐵𝑜𝑏),𝖢𝗈𝗎𝗋𝗌𝖾(123)}
i.e., 2Δ𝒟={𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛),𝖯𝖾𝗋𝗌𝗈𝗇(𝐵𝑜𝑏),𝖢𝗈𝗎𝗋𝗌𝖾(123)}
3=
i.e., 3Δ𝒟={𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛),𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,123)}
  • -𝑅𝑒𝑝Δ(𝒦)={1,3} since 1 and 3 have the smallest symmetric differences with 𝒟.

  • If we take the prioritization P=𝒫1,𝒫2 where 𝒫1 contains 𝖳𝖾𝖺𝖼𝗁(𝐵𝑜𝑏,123) and all negative literals (to strongly penalize fact additions) and 𝒫2={𝖭𝖺𝗆𝖾(123,𝐴𝑛𝑛)}, then P-𝑅𝑒𝑝Δ(𝒦)={2,3} and P-𝑅𝑒𝑝Δ(𝒦)={3}. Indeed, 3Δ𝒟P1Δ𝒟 while 2Δ𝒟 and 3Δ𝒟 are incomparable w.r.t. P. However, 3Δ𝒟<P2Δ𝒟 since 2Δ𝒟 contains two facts of level 1 while 3Δ𝒟 only one.

  • If we assign to literals in 𝒫1 a weight of 2, and to those in 𝒫2 a weight of 1, we obtain that w-𝑅𝑒𝑝Δ(𝒟,𝒯)={3} since 3Δ𝒟 has weight 3, 1Δ𝒟 4 and 2Δ𝒟 5.

5.2 Optimal repairs based on a priority relation

The second category of preferred repairs we consider is based on a priority relation defined over conflicting facts (or literals in the case of Δ-repairs of databases with UCs, even if most work on these kinds of repairs has focused on databases with anti-monotone ICs and KBs).

Definition 45 (Priority relation [129]).

A priority relation for a dataset 𝒟 w.r.t. an ontology or set of anti-monotone ICs (resp. UCs) 𝒯 is an acyclic binary relation over the facts (resp. literals) of 𝐶𝑜𝑛𝑓(𝒟,𝒯) such that if αβ, there is 𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯) s.t. {α,β}𝒞.

We say that is total if for every pair αβ such that {α,β}𝒞 for some 𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯), either αβ or βα. A completion of is a total priority relation .

A priority relation is score-structured if there is a function s:𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯)𝒞 such that for every {α,β}𝒞 with 𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯), αβ iff s(α)>s(β).

Definition 46 (Prioritized KB/database).

A prioritized KB (resp. database) 𝒦=(𝒦,) consists of a KB (resp. database) 𝒦=𝒟,𝒯 and a priority relation for 𝒟 w.r.t. 𝒯.

Specifying the priority relation.

Before defining the optimal repairs based on a priority relation, let us start by briefly explaining how one can specify such a relation, since it is not realistic to expect users to manually input a binary relation between facts or literals. This question has been recently tackled by a rule-based approach to specifying preferences over conflicting facts [37]. In a nutshell, the idea is that the user defines a few rules that are evaluated on 𝒟, possibly taking into account 𝒯 and/or some metadata (such as the sources of the facts or the dates they have been added to the dataset) to produce preference statements over facts (using fact identifiers). If these statements yield a cyclic relation, cycle removal techniques are used to obtain a proper priority relation (possibly taking into account a stratification of the preference rules into more or less important ones). While this framework has been defined for KBs, we can in principle extend preference rules to specify a priority relation over literals in the case of databases with UCs.

Example 47 (Adapted from [37]).

The following preference rules express that (i) more recently added facts are preferred, (ii) if 𝒟 contains both 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(c) and 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(c) for some c, then the former is preferred, and (iii) if a person is declared to belong to 𝖲𝗍𝗎𝖽𝖾𝗇𝗍 and to a subclass Y of 𝖯𝗋𝗈𝖿, but there is no 𝖳𝖾𝖺𝖼𝗁-fact about this person in 𝒟, then the 𝖲𝗍𝗎𝖽𝖾𝗇𝗍-fact is deemed more reliable.

(i) 𝖣𝖺𝗍𝖾(x1,y1)𝖣𝖺𝗍𝖾(x2,y2)y2<y1𝗉𝗋𝖾𝖿(x1,x2)
(ii) x1=id(𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(y))x2=id(𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(y))𝗉𝗋𝖾𝖿(x1,x2)
(iii) Y𝖯𝗋𝗈𝖿x1=id(𝖲𝗍𝗎𝖽𝖾𝗇𝗍(y))x2=id(Y(y))¬(z𝖳𝖾𝖺𝖼𝗁(y,z))𝗉𝗋𝖾𝖿(x1,x2)

Assume that

𝒯={ 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿𝖯𝗋𝗈𝖿,𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿𝖯𝗋𝗈𝖿,𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿¬𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿,𝖯𝗋𝗈𝖿¬𝖲𝗍𝗎𝖽𝖾𝗇𝗍}
𝒟={ 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(a),𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(a),𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(a)}

and that 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(a) is associated to a more recent date than 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(a). The rules yield the following preference statements: (i) 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(a) is preferred to 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(a), (ii) 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(a) is preferred to 𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(a), and (iii) 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(a) is preferred to the two other facts. Since there is a cycle in the preference statements, we need to either remove the whole cycle, which produces the priority relation 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(a)𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(a), 𝖲𝗍𝗎𝖽𝖾𝗇𝗍(a)𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(a), or to rely on some information on the relative importance of the rules. For example, if rule (ii) has priority over (i), we additionally obtain 𝖥𝗎𝗅𝗅𝖯𝗋𝗈𝖿(a)𝖠𝗌𝗌𝗈𝖼𝗂𝖺𝗍𝖾𝖯𝗋𝗈𝖿(a).

5.2.1 Pareto-, globally- and completion-optimal repairs

We now present the three kinds of optimal repair for a prioritized database or KB [129, 30, 32].

Definition 48 (Optimal repairs of a KB or database with anti-monotone constraints).

Consider a prioritized KB or database with anti-monotone ICs 𝒦=(𝒦,) with 𝒦=𝒟,𝒯, and let S-𝑅𝑒𝑝(𝒦).

  • A Pareto improvement of (w.r.t. ) is a 𝒯-consistent 𝒟 such that there exists β such that βα for every α.

  • A global improvement of (w.r.t. ) is a 𝒯-consistent 𝒟 such that and for every α, there exists β such that βα.

The repair is a:

  • Pareto-optimal repair of 𝒦 if there is no Pareto improvement of w.r.t. .

  • Globally-optimal repair of 𝒦 if there is no global improvement of w.r.t. .

  • Completion-optimal repair of 𝒦 if is a globally-optimal repair of 𝒦, for some completion of .

We denote by P-𝑅𝑒𝑝(𝒦), G-𝑅𝑒𝑝(𝒦), and C-𝑅𝑒𝑝(𝒦) the sets of Pareto-, globally-, and completion-optimal repairs.

For Δ-repairs, recall from Section 3.2 that 𝐼𝑛𝑡𝒟()=(𝒟){¬αα𝐹𝑎𝑐𝑡𝑠𝒟𝒯(𝒟)} is the set of literals upon which and 𝒟 agree.

Definition 49 (Optimal repairs of a database with universal constraints).

Consider a prioritized database 𝒦=(𝒦,) with 𝒦=𝒟,𝒯 where 𝒯 is a set of UCs, and let S-𝑅𝑒𝑝Δ(𝒦).

  • A Pareto improvement of (w.r.t. ) is a 𝒯-consistent dataset such that there is μ𝐼𝑛𝑡𝒟()𝐼𝑛𝑡𝒟() such that μλ for every λ𝐼𝑛𝑡𝒟()𝐼𝑛𝑡𝒟().

  • A global improvement of (w.r.t. ) is a 𝒯-consistent dataset s.t. 𝐼𝑛𝑡𝒟()𝐼𝑛𝑡𝒟() and for every λ𝐼𝑛𝑡𝒟()𝐼𝑛𝑡𝒟(), there exists μ𝐼𝑛𝑡𝒟()𝐼𝑛𝑡𝒟() such that μλ.

The Pareto-, globally-, and completion-optimal Δ-repairs of 𝒦 (P-𝑅𝑒𝑝Δ(𝒦), G-𝑅𝑒𝑝Δ(𝒦) and C-𝑅𝑒𝑝Δ(𝒦)) are then defined as in Definition 48.

A Pareto improvement is a global improvement, and a global improvement w.r.t. is a global improvement w.r.t. any completion of , so optimal repairs are related as follows.

Proposition 50 ([129, 32]).

For every prioritized KB or database 𝒦, it holds that

C-𝑅𝑒𝑝(𝒦)G-𝑅𝑒𝑝(𝒦)P-𝑅𝑒𝑝(𝒦)S-𝑅𝑒𝑝(𝒦),

and similarly for X-𝑅𝑒𝑝Δ(𝒦) in the case of Δ-repairs.

Examples 51 and 52 illustrate the three kinds of optimal repair for prioritized KBs and Δ-repairs of prioritized databases with UCs, respectively.

Example 51.

Consider the KB 𝒦 from Example 15, whose conflict hypergraph and repairs are recalled below, and assume that E(a)C(a), C(a)A(a) and A(a)D(a).

We show that C-𝑅𝑒𝑝(𝒦)=G-𝑅𝑒𝑝(𝒦)={1} and P-𝑅𝑒𝑝(𝒦)={1,3}.

  • 2 is not Pareto-optimal (hence not globally- nor completion-optimal) because {A(a),E(a)} is a Pareto improvement of 2 (since E(a)C(a)).

  • 3 is not globally-optimal (hence not completion-optimal) since {B(a),E(a),A(a)} is a global improvement of 3 (since E(a)C(a) and A(a)D(a)). However, it is Pareto-optimal, since replacing only C(a) by E(a) leads to a contradiction between D(a) and E(a), and similarly replacing only D(a) with A(a) leads to a conflict {A(a),B(a),C(a)}.

  • 1 is completion-optimal (hence globally- and Pareto-optimal), since every completion of is such that E(a)D(a) (to avoid cycle E(a)C(a)A(a)D(a)E(a)). Indeed, this implies that for every completion , a globally-optimal repair of 𝒦 must contain E(a) (otherwise {C(a),D(a)}{E(a)} would be a global improvement of w.r.t. ), hence does not contain C(a) nor D(a), so that =1.

Example 52 ([32]).

Let 𝒟={S(a,b),S(a,c),R(d,b),R(d,c)} and 𝒯 contains the UCs:

S(x,y)S(x,z)yz S(x,y)A(x) R(y,x)S(z,x)
R(x,y)R(x,z)yz S(x,y)B(x)

The conflicts are all binary, so the conflict hypergraph is a graph, whose edges are pictured below. Assume that R(d,b)S(a,b), S(a,b)¬A(a), S(a,c)R(d,c), S(a,c)¬B(a). We use an arrow λμ when λμ and plain lines for conflicting literals with no priority.

It can be verified that the optimal repairs are as follows:

C-𝑅𝑒𝑝Δ(𝒦)= {{R(d,b),S(a,c),A(a),B(a)}}
G-𝑅𝑒𝑝Δ(𝒦)= C-𝑅𝑒𝑝Δ(𝒦){{R(d,b)},{R(d,c)}}
P-𝑅𝑒𝑝Δ(𝒦)= G-𝑅𝑒𝑝Δ(𝒦){{R(d,c),S(a,b),A(a),B(a)}}

and that S-𝑅𝑒𝑝Δ(𝒦)=P-𝑅𝑒𝑝Δ(𝒦).

There always exists at least one completion-(hence Pareto- and globally-)optimal repair, which can be obtained by the following greedy procedure: while some fact of 𝒟 (or literal from 𝐿𝑖𝑡𝑠𝒟𝒯) has not been considered, pick one that is maximal w.r.t. among the facts (or literals) not yet considered (i.e., pick some α such that there is no βα), and add it to the current set if it does not lead to a contradiction [129, 32].

 Remark 53 ([129, 32]).

When is total, |P-𝑅𝑒𝑝(𝒦)|=1 (hence C-𝑅𝑒𝑝(𝒦)=G-𝑅𝑒𝑝(𝒦)=P-𝑅𝑒𝑝(𝒦)). It follows that we may replace “globally-optimal” by “Pareto-optimal” in the definition of completion-optimal repairs.

The following example shows that the binary relation P-imp between datasets defined by “P-imp iff = or is a Pareto improvement of ” is not a preorder over datasets, so that we cannot recast Pareto-optimal repairs in the terms of Section 5.1 in this way, and similarly for globally-optimal repairs.

Example 54.

Let 𝒟={α,β,γ,δ} and assume that 𝒯 is such that 𝐶𝑜𝑛𝑓(𝒟,𝒯)={{α,β},{α,γ},{δ,β},{δ,γ},{β,γ}}. Let βα, βδ and γβ. There are three repairs: 1={α,δ}, 2={β}, and 3={γ}. 2 is a Pareto improvement of 1 and 3 is a Pareto improvement of 2, but 3 is a not a Pareto improvement of 1: the relation “is a Pareto improvement of” is not transitive, so P-imp is not a preorder. This example also shows that the relation “is a global improvement of” is not transitive.

The case of score-structured priority relations.

When is score-structured with scoring function s:𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯)𝒞, the corresponding prioritization of 𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯)𝒞 is P=𝒫1,,𝒫n such that for every 1in, there exists m such that 𝒫i={αs(α)=m}, 𝒫i, and for every αi𝒫i, αj𝒫j, i<j iff s(αi)>s(αj). The corresponding prioritization of the whole dataset 𝒟 (or set of literals 𝐿𝑖𝑡𝑠𝒟𝒯 in the case of Δ-repairs of databases with UCs) is obtained by adding the facts from 𝒟𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯)𝒞 (or literals from 𝐿𝑖𝑡𝑠𝒟𝒯𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯)𝒞) to 𝒫1 (this is an arbitrary choice as we could add them to any of the priority levels and obtain the following result). In this case, all three notions of optimal repairs coincide with P-optimal repairs.

Proposition 55 ([44, Prop. 6.1.14] and [32, Prop. 5]).

If 𝒦 is a prioritized KB or database with a score-structured priority relation , and P is the corresponding prioritization, then

C-𝑅𝑒𝑝(𝒦)=G-𝑅𝑒𝑝(𝒦)=P-𝑅𝑒𝑝(𝒦)=P-𝑅𝑒𝑝(𝒦),

and similarly for X-𝑅𝑒𝑝Δ(𝒦) in the case of Δ-repairs.

5.2.2 Links with abstract argumentation and active integrity constraints

We now present some correspondences between Pareto-optimal repairs and other notions defined in frameworks that deal with inconsistent information, which speaks in favor of the naturalness of Pareto-optimal repairs.

Abstract argumentation

Recall from Section 3.3 that given a KB (or database with anti-monotone ICs) 𝒦=𝒟,𝒯, its associated SETAF F𝒦=(𝒟,𝒦), with 𝒦={(𝒞{α},α)𝒞𝐶𝑜𝑛𝑓(𝒦),α𝒞}, is such that S-𝑅𝑒𝑝(𝒦) iff is a naive/stable/preferred extension of F𝒦. To capture prioritized KBs (or databases), we need to use preference-based SETAFs (PSETAFs) [30].

Definition 56 (Preference-based set-based argumentation framework).

A PSETAF is a triple (𝐴𝑟𝑔𝑠,,), where (𝐴𝑟𝑔𝑠,) is a SETAF, and is an acyclic binary relation over 𝐴𝑟𝑔𝑠 called the preference relation.

The semantics of PSETAFs is given by a reduction to SETAFs:

Definition 57 (PSETAF extensions).

Given a PSETAF (𝐴𝑟𝑔𝑠,,), its corresponding SETAF is (𝐴𝑟𝑔𝑠,), where the relation (2𝐴𝑟𝑔𝑠{})×𝐴𝑟𝑔𝑠 is defined as follows: Sα iff Sα and αβ for every βS. A subset E𝐴𝑟𝑔𝑠 is a stable (resp. preferred) extension of a PSETAF (𝐴𝑟𝑔𝑠,,) iff it is a stable (resp. preferred) extension of the corresponding SETAF.

From Pareto-optimal repairs to PSETAF extensions.

Let 𝒦 be a prioritized KB (or database with anti-monotone ICs) such that 𝒦=𝒟,𝒯 and 𝒟 does not contain any self-conflicting fact. The PSETAF F𝒦, associated to 𝒦 is obtained from the SETAF associated to 𝒦 by using the priority relation as the preference relation, i.e., F𝒦,=(𝒟,𝒦,) [30].

Proposition 58 ([30, Th. 35, 36 and 37]).

Let 𝒦=(𝒦,) be a prioritized KB (or database with anti-monotone ICs) such that 𝒦=𝒟,𝒯 and 𝒟 does not contain any self-conflicting fact, F𝒦,=(𝒟,𝒦,) be its associated PSETAF, and 𝒟.

  • P-𝑅𝑒𝑝(𝒦) iff is a stable extension of F𝒦,.

  • If is transitive, then P-𝑅𝑒𝑝(𝒦) iff is a preferred extension of F𝒦,.

  • If every 𝒞𝐶𝑜𝑛𝑓(𝒦) is such that |𝒞|=2, then P-𝑅𝑒𝑝(𝒦) iff is a preferred extension of F𝒦,.

Note that it follows that globally-optimal and completion-optimal repairs correspond to proper subsets of the stable extensions of F𝒦,, but they do not at present have any analogue in the argumentation setting.

Example 59.

Consider again the prioritized KB 𝒦 of Example 51. The PSETAF associated to 𝒦 is F𝒦,=(𝒟,𝒦,) where 𝒦 is the attack relation defined in Example 24. The SETAF corresponding to the PSETAF F𝒦, is ({A(a),B(a),C(a),D(a),E(a)},) where is as follows.

{A(a),C(a)}B(a) {B(a),C(a)}A(a)
{A(a)}D(a)
{E(a)}C(a)
{D(a)}E(a) {E(a)}D(a)

As in the case of standard repairs, it is not difficult to extend this reduction to the case of Pareto-optimal Δ-repairs of databases with UCs.

Active integrity constraints

Active integrity constraints (AICs) provide a framework in which universal constraints are enriched with information on what are the allowed update actions (fact deletions or additions) to resolve a given constraint violation [80, 61, 42].

Background on AICs.

In this section, we consider that UCs are written in the form β[x]ν[x]ϵ[x], with β[x] a conjunction of relational atoms, ν[x] a conjunction of negated relational atoms and ϵ[x] a conjunction of inequalities (cf. Section 2.1).

Definition 60 (Update actions).

An update atom is of the form +P(x) or P(x) where P(x) is a relational atom. We use a function 𝖿𝗂𝗑 to map relational literals to the corresponding update atoms: 𝖿𝗂𝗑(P(x))=P(x) and 𝖿𝗂𝗑(¬P(x))=+P(x). An update action is a ground update atom, i.e., is of the form α or +α with α a fact. A set of update actions 𝒰 is consistent if 𝒰 does not contain both α and +α for some fact α. The result of applying a consistent set of update actions 𝒰 on a dataset 𝒟 is 𝒟𝒰:=𝒟{αα𝒰}{α+α𝒰}.

Definition 61 (Active integrity constraints).

An active integrity constraint takes the form r=1n{A1,,Ak}, where τr:=1n is a UC, and {A1,,Ak} is a non-empty set of update atoms such that each Aj is equal to 𝖿𝗂𝗑(i) for some i. A literal of r is non-updatable if 𝖿𝗂𝗑(){A1,,Ak}. A dataset 𝒟 satisfies r (𝒟r) if it satisfies τr.

A ground AIC is an AIC that contains no variables. The set gr𝒟(r) contains all ground AICs obtained from r by (i) replacing variables by constants that occur in 𝒟, (ii) removing all true cd atoms, and (iii) removing all ground AICs with an atom cc. We let gr𝒟(η):=rηgr𝒟(r), and observe that 𝒟r iff 𝒟rg for every rggr𝒟(r).

An AIC is called normal if its head contains a single update atom. The normalization of r=1n{A1,,Ak} is the set N(r)={1n{Ai}1ik}. The normalization of a set of AICs η is N(η)=rηN(r).

Definition 62 (Repair updates).

A repair update222Repair updates are usually called repairs in the AIC literature, we use this term to avoid confusion. of a dataset 𝒟 w.r.t. a set of AICs η is a consistent -minimal set of update actions 𝒰 such that 𝒟𝒰 satisfies all AICs in η. We denote the set of repair updates of 𝒟 w.r.t. η by 𝑈𝑝(𝒟,η).

It is easy to check that {𝒟𝒰𝒰𝑈𝑝(𝒟,η)}=S-𝑅𝑒𝑝Δ(𝒟,𝒯η) where 𝒯η is the set of UCs that correspond to AICs in η. To take into account the restrictions on the possible update actions expressed by the AICs, several classes of repair updates have been defined.

Definition 63 (Founded, well-founded, grounded and justified repair updates).

A repair update 𝒰 of 𝒟 w.r.t. η is:

  • Founded if for every A𝒰, there exists rgr𝒟(η) such that A is an update action of r and 𝒟𝒰{A}⊧̸r.

  • Well-founded if there is a sequence of actions A1,,An such that 𝒰={A1,,An}, and for each 1in, there exists rigr𝒟(η) such that Ai is an update action of ri and 𝒟{A1,,Ai1}⊧̸ri.

  • Grounded if for every 𝒱𝒰, there is rgr𝒟(N(η)) such that 𝒟𝒱⊧̸r and the (only) update action of r is in 𝒰𝒱 (recall that N(η) is the normalization of η).

  • Justified if ne(𝒟,𝒟𝒰)𝒰 is a minimal set of update actions closed under η that contains the set of no-effect actions ne(𝒟,𝒟𝒰) where

    • ne(𝒟,𝒟𝒰)={+αα𝒟(𝒟𝒰)}{αα𝒟(𝒟𝒰),α𝐹𝑎𝑐𝑡𝑠𝒟𝒯}

    • 𝒱 is closed under η if for every rgr𝒟(η), if 𝒱 satisfies all the non-updatable literals of r, then 𝒱 contains an update action of r.

We denote the sets of Δ-repairs obtained by applying some founded, well-founded, grounded or justified repair update of 𝒟 w.r.t. η by 𝐹𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η), 𝑊𝑒𝑙𝑙𝐹𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η), 𝐺𝑟𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η) and 𝐽𝑢𝑠𝑡-𝑅𝑒𝑝Δ(𝒟,η), respectively.

The relationships between the various kinds of repairs are represented below, where a plain arrow from X to Y means XY and the dotted arrow represents an inclusion that only holds when η is a set of normal AICs. All inclusions may be strict [62, 69, 68].

From Pareto-optimal repairs to repairs w.r.t. AICs.

Given a prioritized database 𝒦 where 𝒦=𝒟,𝒯 with 𝒯 a set of UCs, its corresponding set of ground AICs [32] is

η𝒯={r𝒞𝒞𝐶𝑜𝑛𝑓(𝒦)} where r𝒞:=λ𝒞λ{𝖿𝗂𝗑(λ)λ𝒞,μ𝒞,λμ}.

Intuitively, η𝒯 expresses that conflicts of 𝒦 should be fixed by modifying their least preferred literals according to . The Pareto-optimal repairs of 𝒦 coincide with several kinds of repairs of 𝒟 w.r.t. η𝒯.

Proposition 64 ([32, Prop. 7]).

Let 𝒦=(𝒟,𝒯,) be a prioritized database such that 𝒯 is a set of UCs, and η𝒯 be its corresponding set of ground AICs.

P-𝑅𝑒𝑝Δ(𝒦)=𝐽𝑢𝑠𝑡-𝑅𝑒𝑝Δ(𝒟,η𝒯)=𝐺𝑟𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η𝒯)=𝐹𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η𝒯)
𝑊𝑒𝑙𝑙𝐹𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η𝒯)
Example 65.

We modify slightly the UCs of Example 52 so that some Δ-repairs are not Pareto-optimal. Let 𝒟={S(a,b),S(a,c),R(d,b),R(d,c)} and 𝒯 contains the UCs:

S(x,y)S(x,z)yz S(x,y)A(y)
R(x,y)R(x,z)yz R(y,x)S(z,x)

The edges of the conflict graph and the optimal repairs are shown below, assuming that R(d,b)S(a,b), S(a,b)¬A(b), S(a,c)R(d,c), S(a,c)¬A(c).

C-𝑅𝑒𝑝Δ(𝒦)= G-𝑅𝑒𝑝Δ(𝒦)={{R(d,b),S(a,c),A(c)}}
P-𝑅𝑒𝑝Δ(𝒦)= G-𝑅𝑒𝑝Δ(𝒦){{R(d,c),S(a,b),A(b)}}
S-𝑅𝑒𝑝Δ(𝒦)= P-𝑅𝑒𝑝Δ(𝒦){{R(d,b)},{R(d,c)}}

The set of ground AICs η𝒯 corresponding to 𝒦 contains the following AICs:

r1: R(d,b)S(a,b){S(a,b)} r4: S(a,b)S(a,c){S(a,b),S(a,c)}
r2: R(d,c)S(a,c){R(d,c)} r5: R(d,b)R(d,c){R(d,b),R(d,c)}
r3: S(a,b)¬A(b){+A(b)} r6: S(a,c)¬A(c){+A(c)}

We can check that the two Pareto-optimal Δ-repairs correspond exactly to the justified, grounded and founded repair updates:

  • 𝒰1={S(a,b),S(a,c),R(d,c)} and 𝒰2={S(a,b),S(a,c),R(d,b)}, which correspond respectively to the Δ-repairs 1={R(d,b)} and 2={R(d,c)}, are not founded (hence not grounded nor justified). Indeed, S(a,c)𝒰1 while the only AIC with S(a,c) in the head (r4) is satisfied by 1{S(a,c)}. Regarding 𝒰2, S(a,b)𝒰2 and the two AICs with S(a,b) in the head (r1 and r4) are satisfied by 2{S(a,b)}.

  • The repair update 𝒰3={R(d,b),S(a,c),+A(b)}, which corresponds to the Pareto-optimal Δ-repair 3={R(d,c),S(a,b),A(b)} is grounded (hence founded) and justified. Indeed, (1) for every 𝒱𝒰3, there is r in the normalization N(η𝒯) of η𝒯 such that 𝒟𝒱⊧̸r and the only update action of r is in 𝒰3𝒱, so 𝒰3 is grounded, and (2) ne(𝒟,𝒟𝒰3)𝒰3={+R(d,c),+S(a,b),A(c),R(d,b),S(a,c),+A(b)} is a minimal set of update actions closed under η𝒯 that contains ne(𝒟,𝒟𝒰3)={+R(d,c),+S(a,b),A(c)} (since this set of update actions satisfies all the non-updatable literals of r3, r4 and r5).

  • The repair update 𝒰4={R(d,c),S(a,b),+A(c)}, which corresponds to the Pareto-optimal Δ-repair 4={R(d,b),S(a,c),A(c)} is also grounded, founded and justified.

The above reduction is data-dependent and requires us to create potentially exponentially many ground AICs (one for every conflict). In the case of denial constraints, however, there exists an alternative data-independent reduction, provided that the priority relation is specified in the dataset [32]. It assumes the existence of a predicate P𝐏, that the first attribute of each relation in 𝐏{P} stores a unique fact identifier, and that P stores pairs of such identifiers. Then given a set of DCs 𝒯 over 𝐏{P}, 𝑚𝑖𝑛(𝒯) is the set of DCs that is equivalent to 𝒯 but has the property that for every dataset 𝒟, the conflicts of 𝒟 w.r.t. 𝒯 are precisely the images of constraint bodies of 𝑚𝑖𝑛(𝒯) on 𝒟. This can be achieved by replacing each φ𝒯 with all refinements obtained by (dis)equating variables in φ with each other, then removing any subsumed constraints. For example, if 𝒯={R(x,x),R(x,y)S(y)}, then 𝑚𝑖𝑛(𝒯) contains R(x,x) and R(x,y)S(y)xy, so {R(a,a),S(a)} is no longer an image of a constraint body. The set of AICs corresponding to 𝒯, η𝒯, contains all AICs

(1nεj{1,,n},ji¬P(idi,idj)){i}

such that 1nε𝑚𝑖𝑛(𝒯), i{1,,n}, and for every 1kn, k=R(idk,t) for some R,t.

Proposition 66 ([32, Prop. 8]).

Let 𝒦=(𝒟,𝒯,) be a prioritized database such that 𝒯 is a set of DCs, and η𝒯 be the set of AICs corresponding to 𝒯.

P-𝑅𝑒𝑝(𝒦)=𝐽𝑢𝑠𝑡-𝑅𝑒𝑝Δ(𝒟,η𝒯)=𝐺𝑟𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η𝒯)=𝐹𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η𝒯)
𝑊𝑒𝑙𝑙𝐹𝑜𝑢𝑛𝑑-𝑅𝑒𝑝Δ(𝒟,η𝒯)
From repairs w.r.t. AICs to Pareto-optimal repairs.

Interestingly, certain “well-behaved” sets of AICs, for which, in particular, justified, grounded and founded repairs coincide, can be translated into prioritized databases whose Pareto-optimal repairs coincide with these repairs [32]. The conditions on the AICs are quite involved though.

5.3 Preferred repairs based on preference rules

The last category of preferred repairs we consider is inspired by work in logic programming [46] and uses preference rules to express context-dependent preferences. Preferred repairs are then those that maximally (w.r.t. some preorder) satisfy these preference rules [50].

Definition 67 (Preference program [50]).

A preference rule ρ is an expression of the form

P[x]Q[y]zφ[z,w],

where P[x] and Q[y] are two relational atoms whose variables are x and y respectively (and may contain constants), xz=yz=, and φ[z,w] is a (possibly empty) conjunction of relational atoms with variables zw. A set of preference rules is called a preference program.

Definition 68 (Preference program-based prioritized KB or database [50]).

A (preference program-based) prioritized KB or database 𝒦Π=(𝒦,Π) consists of a KB (or database with anti-monotone ICs) 𝒦=𝒟,𝒯 and a preference program Π.

A ground instance of a preference rule ρ (w.r.t. 𝒦 and Π) is a preference rule obtained from ρ by replacing all its free variables by constants that occur in 𝒦 or Π. The set of all ground instances of all rules in Π is denoted by 𝑔𝑟𝑛𝑑𝒦(Π).

A 𝒯-consistent dataset satisfies a ground instance P(a)Q(b)zφ[z,c] (w.r.t. 𝒦) if ,𝒯zφ[z,c] implies that ,𝒯⊧̸Q(b) or ,𝒯P(a), i.e., if the following holds:

,𝒯zφ[z,c](,𝒯Q(b),𝒯P(a))

The set of preference rules from 𝑔𝑟𝑛𝑑𝒦(Π) satisfied by is denoted by 𝐺𝑟𝑆𝑎𝑡(,𝒦Π).

Definition 69 (Preference program-based preferred repairs [50]).

Let 𝒦Π=(𝒦,Π) be a (preference program-based) prioritized KB (or database) and be a preorder on the subsets of 𝑔𝑟𝑛𝑑𝒦(Π). A repair of 𝒦 is Π-preferred iff there is no repair of 𝒦 such that 𝐺𝑟𝑆𝑎𝑡(,𝒦Π)𝐺𝑟𝑆𝑎𝑡(,𝒦Π). We denote by 𝑃𝑟-𝑅𝑒𝑝(𝒦Π) the set of Π-preferred repairs.

Note that even if the binary relation over datasets Π defined by Π iff 𝐺𝑟𝑆𝑎𝑡(,𝒦Π)𝐺𝑟𝑆𝑎𝑡(,𝒦Π) is a preorder, we cannot recast Π-preferred repairs in the terms of Section 5.1. Indeed, Π is not strictly -monotone, since the empty set trivially satisfies every preference rule ground instance, hence is Π-maximal.

Example 70.

Consider the KB 𝒦=𝒟,𝒯, where 𝒯 expresses that computer science (CS), economics (Eco) and literature (Lit) courses and professors, respectively, are disjoint.

𝒯={ 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾¬𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾,𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾¬𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾,𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾¬𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾,
𝖢𝖲𝖯𝗋¬𝖤𝖼𝗈𝖯𝗋,𝖢𝖲𝖯𝗋¬𝖫𝗂𝗍𝖯𝗋,𝖫𝗂𝗍𝖯𝗋¬𝖤𝖼𝗈𝖯𝗋}
𝒟={ 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖢𝖲𝖯𝗋(p),𝖤𝖼𝗈𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)}

There are six repairs:

1={ 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖢𝖲𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)} 2={ 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖤𝖼𝗈𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)}
3={ 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖢𝖲𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)} 4={ 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖤𝖼𝗈𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)}
5={ 𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖢𝖲𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)} 6={ 𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖤𝖼𝗈𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)}

Assume that Π contains the following preference rules, which express that when a course is taught by a professor in a given subject, we prefer the fact that states that this course is on that subject to facts that state it is on another subject:

ρ1: 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(x) y𝖳𝖾𝖺𝖼𝗁(y,x)𝖢𝖲𝖯𝗋(y)
ρ2: 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(x) y𝖳𝖾𝖺𝖼𝗁(y,x)𝖤𝖼𝗈𝖯𝗋(y)
ρ3: 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(x) y𝖳𝖾𝖺𝖼𝗁(y,x)𝖢𝖲𝖯𝗋(y)
ρ4: 𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(x) y𝖳𝖾𝖺𝖼𝗁(y,x)𝖫𝗂𝗍𝖯𝗋(y)
ρ5: 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(x) y𝖳𝖾𝖺𝖼𝗁(y,x)𝖤𝖼𝗈𝖯𝗋(y)
ρ6: 𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(x)𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(x) y𝖳𝖾𝖺𝖼𝗁(y,x)𝖫𝗂𝗍𝖯𝗋(y)

Since all repairs trivially satisfy the ground instances obtained by replacing x by p, we identify each ρi with its ground instance obtained by replacing x by c in what follows.

  • 1 and 4 satisfy all rules. For example, 1 satisfies ρ1 because 1,𝒯𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c), and ρ2 because 1,𝒯⊧̸y𝖳𝖾𝖺𝖼𝗁(y,c)𝖤𝖼𝗈𝖯𝗋(y).

  • 2 satisfies all rules but ρ2: 2,𝒯y𝖳𝖾𝖺𝖼𝗁(y,c)𝖤𝖼𝗈𝖯𝗋(y) and 2,𝒯𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c) while 2,𝒯⊧̸𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c). Note that it satisfies ρ5 because 2,𝒯⊧̸𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c).

  • 3 satisfies all rules but ρ1; 5 satisfies all rules but ρ3; and 6 satisfies all rules but ρ5.

Hence, for {,}, 𝑃𝑟-𝑅𝑒𝑝(𝒦Π)={1,4}, which correspond to the two ways of repairing 𝒟 by selecting a pair of a course and a professor with matching subject.

To illustrate how choosing or may lead to different Π-preferred repairs, consider 𝒦=𝒟,𝒯 where 𝒯 keeps only the three first axioms of 𝒯 (i.e., a course has only one subject but professors can teach several subjects). There are three repairs of 𝒦:

1={ 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖢𝖲𝖯𝗋(p),𝖤𝖼𝗈𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)}
2={ 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖢𝖲𝖯𝗋(p),𝖤𝖼𝗈𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)}
3={ 𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c),𝖢𝖲𝖯𝗋(p),𝖤𝖼𝗈𝖯𝗋(p),𝖳𝖾𝖺𝖼𝗁(p,c)}

We obtain 𝑃𝑟-𝑅𝑒𝑝(𝒦Π)={1,2,3} while 𝑃𝑟-𝑅𝑒𝑝(𝒦Π)={1,2}. Indeed 1 satisfies all rules but ρ2; 2 satisfies all rules but ρ1; and 3 satisfies ρ1, ρ2, ρ4, and ρ6.

While the preference rules used to define a priority relation among conflicting facts in Section 5.2 (cf. Example 47) are quite similar to the ones considered here from a syntactic point of view, they have a different semantics: the former aim at defining a priority relation between conflicting facts globally, taking into account the whole dataset 𝒟, while the latter aim at defining directly a preference relation between repairs, so that the relation between facts is specific to each repair. If we consider the counterparts of the preference rules of Example 70 that specify a priority relation as in Example 47 and evaluate them over 𝒟, we obtain that 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c) is preferred to 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c) (counterpart of ρ1), 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c) is preferred to 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c) (counterpart of ρ2), 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c) is preferred to 𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c) (counterpart of ρ3), and 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c) is preferred to 𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c) (counterpart of ρ5), which yields (assuming that all rules are equally important) the priority relation 𝖢𝖲𝖢𝗈𝗎𝗋𝗌𝖾(c)𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c), 𝖤𝖼𝗈𝖢𝗈𝗎𝗋𝗌𝖾(c)𝖫𝗂𝗍𝖢𝗈𝗎𝗋𝗌𝖾(c). The optimal repairs w.r.t. this priority relation are {1,2,3,4} for 𝒦 and {1,2} for 𝒦.

Capturing -optimal repairs for {,𝒘,𝑷,𝑷}.

Given 𝒦=𝒟,𝒯 and a preorder {,w,P,P} over the subsets of 𝒟, it is possible to define a preference program Π, a fact α and a preorder on the subsets of 𝑔𝑟𝑛𝑑𝒦(Π) such that there is a one-to-one correspondence between -optimal repairs of 𝒦 and Π-preferred repairs of 𝒦=𝒟{α},𝒯. More precisely:

𝑃𝑟-𝑅𝑒𝑝(𝒦Π)={{α}-𝑅𝑒𝑝(𝒦)}.

The idea is simply to encode the preorder over the subsets of 𝒟 in Π: take α=A(a) such that A and a do not occur in 𝒦, Π={βαβ𝒟}, and for all subsets S and S of 𝑔𝑟𝑛𝑑𝒦(Π) (which is equal to Π in this case) let SS iff {ββαS}{ββαS}. Then for all 𝒯-consistent and subsets of 𝒟, iff 𝐺𝑟𝑆𝑎𝑡({α},𝒦Π)𝐺𝑟𝑆𝑎𝑡({α},𝒦Π). Since all repairs of 𝒦 contain α (so that subsets of 𝒟, which trivially satisfy all rules from Π, are not repairs of 𝒦, hence not Π-preferred repairs), it follows that is a -optimal repair of 𝒦 iff {α} is a Π-preferred repair of 𝒦. In the case of , this reduction can be adapted into a data-independent one [50, Prop. 42].

Comparison with optimal repairs based on a priority relation.

Given a prioritized KB or database 𝒦, we can consider the preference program Π={αβαβ}. However, the Π-preferred repairs of 𝒦Π are incomparable with the optimal repairs of 𝒦 [50]. For example, assume that 𝒟={α,β,γ}, 𝐶𝑜𝑛𝑓(𝒟,𝒯)={{α,β},{α,γ}} and αβ. There are two repairs, {α} and {β,γ}. The priority relation is score-structured so Pareto-, globally-, completion- and P-optimal repairs coincide and both {α} and {β,γ} are optimal. However, only {α} is a Π-preferred (resp. Π-preferred) repair. For an example where there are more Π-preferred repairs, consider 𝒟={α,β,γ}, 𝐶𝑜𝑛𝑓(𝒟,𝒯)={{α,β},{β,γ}} and αβ, βγ. Again is score-structured, and the only optimal repair of 𝒦 is {α,γ}. However both {α,γ} and {β} are Π-preferred repairs of 𝒦Π because {β} satisfies βγ while {α,γ} does not. More examples and discussion can be found in [50, Sec. 6].

5.4 Related work: “Optimal repairs” that are not dataset repairs

We conclude this section with a brief presentation of other notions of “optimal repairs” which are not dataset repairs (i.e., do not form a subset of S-𝑅𝑒𝑝(𝒦)).

5.4.1 Repairs based on non strictly -monotone weight-based preorders

A generalization of w-optimal repairs based on aggregation functions has been defined for databases with anti-monotone ICs [122]. An aggregation function g maps every dataset (associated with a weight function w) to a non-negative rational number g() (cf. [122] for the precise definition). Prominent examples of such functions are Σ()=Σαw(α) (which yields w-optimal repairs), max()=maxαw(α), or 𝖺𝗏𝖾𝗋𝖺𝗀𝖾()=Σαw(α)||.

Definition 71 (Aggregation-based repairs).

Given an aggregation function g and a KB (or database with anti-monotone ICs) 𝒦=𝒟,𝒯 with a weight function w, a g-repair of 𝒦 is a 𝒯-consistent 𝒟 such that (i) there is no 𝒯-consistent 𝒟 with g()<g() and (ii) for every 𝒯-consistent 𝒟, if g()=g() and , then =.

Note that if we define the preorder corresponding to an aggregation function g as g iff g()g(), condition (i) of Definition 71 can be written as “there is no 𝒯-consistent 𝒟 with g”. This definition thus modifies Definition 41 by (1) dropping the condition that the preorder is strictly -monotone and (2) partially compensating the effects of dropping this requirement with condition (ii), which expresses that a g-repair needs to be -maximal among the g-maximal 𝒯-consistent subsets of 𝒟. The following example shows that this is not sufficient to ensure that g-repairs are dataset repairs.

Example 72 ([122]).

Let 𝒟={β,γ} be such that 𝒟 is 𝒯-consistent, so that S-𝑅𝑒𝑝(𝒟,𝒯)={𝒟}, and assume that w(β)=1 and w(γ)=2. Consider the aggregation function min defined by min()=minαw(α). Then {γ} is the only min-repair of 𝒟 w.r.t. 𝒯 since min({β,γ})=1<min({γ})=2. Hence the set of min-repairs is not a subset of S-𝑅𝑒𝑝(𝒟,𝒯).

5.4.2 Selecting a single 𝓣-consistent dataset from a prioritized dataset

Instead of considering all optimal repairs of a prioritized KB or database 𝒦, one may be interested in selecting a single 𝒯-consistent dataset. Several such “repairs” have been proposed, depending on whether is based on a prioritization P=𝒫1,,𝒫n of 𝒟 (i.e., αβ iff {α,β}𝒞 for some conflict 𝒞, α𝒫i, β𝒫j and i<j), a preorder over 𝒟 (i.e., αβ iff {α,β}𝒞 for some conflict 𝒞 and αβ), or is an arbitrary priority relation. These notions of repair stem from the KB area, so we give the definitions for KBs or databases with anti-monotone ICs, but we could in principle extend them to handle database with universal constraints by considering literals as in Section 5.2. We provide below all definitions before presenting their relationships, properties, and an example.

The next definition presents the different kinds of “unique repair” that have been proposed when the dataset is partitioned into priority levels, i.e., the most restricted case.

Definition 73 (Unique repairs based on a prioritization [24]).

Let 𝒦 be a prioritized KB (or database with anti-monotone ICs) such that 𝒦=𝒟,𝒯 and is based on a prioritization P=𝒫1,,𝒫n of 𝒟.

  • The possibilistic repair of 𝒦 is π(𝒦)=𝒫1𝒫inc(𝒦)1, where inc(𝒦) is the inconsistency degree of 𝒦, which is such that 𝒫1𝒫inc(𝒦) is 𝒯-inconsistent and 𝒫1𝒫inc(𝒦)1 is 𝒯-consistent.

  • The linear repair of 𝒦 is (𝒦)=(𝒟) with:

    • (𝒫1)=𝒫1 if 𝒫1 is 𝒯-consistent, (𝒫1)= otherwise;

    • for i>1, (𝒫1𝒫i)=(𝒫1𝒫i1)𝒫i if (𝒫1𝒫i1)𝒫i is 𝒯-consistent, (𝒫1𝒫i)=(𝒫1𝒫i1) otherwise.

  • The non-defeated repair of 𝒦 is 𝑛𝑑(𝒦)=i=1ni where i=S-𝑅𝑒𝑝(𝒫1𝒫i,𝒯).

  • The linear-based non-defeated repair of 𝒦 is 𝑛𝑑(𝒦)=𝑛𝑑(𝒟) with:

    • 𝑛𝑑(𝒫1)=S-𝑅𝑒𝑝(𝒫1,𝒯);

    • for i>1, 𝑛𝑑(𝒫1𝒫i)=𝑛𝑑(𝒫1𝒫i1)S-𝑅𝑒𝑝(𝑛𝑑(𝒫1𝒫i1)𝒫i,𝒯).

  • The prioritized inclusion-based non-defeated repair of 𝒦 is 𝑝𝑖𝑛𝑑(𝒦)=i=1nP,i where P,i=P-𝑅𝑒𝑝(𝒫1𝒫i,𝒯). Equivalently, 𝑝𝑖𝑛𝑑(𝒦)=P-𝑅𝑒𝑝(𝒦).

The “unique repairs” of Definition 74, for the case where only a preorder over the facts is available, rely on completing the preorder in all possible ways, yielding prioritizations used to apply notions from Definition 73. Two additional proposals, called 𝐶𝐸𝑙𝑒𝑐𝑡 [22] and Cπ [97], add facts using the logical closure w.r.t. the ontology, thus are typically not subsets of 𝒟.

Definition 74 (Unique repairs based on a preorder [22]).

Let 𝒦 be a prioritized KB (or database with anti-monotone ICs) such that corresponds to a preorder over 𝒟. For each total preorder extending , let correspond to the prioritization induced by .

  • 𝐸𝑙𝑒𝑐𝑡(𝒦)= total extension of 𝑛𝑑(𝒦).

  • 𝑃𝑎𝑟𝑡𝑖𝑎𝑙𝑃𝑅(𝒦)= total extension of 𝑝𝑖𝑛𝑑(𝒦).

The main “unique repair” that has been proposed in the general case of an arbitrary priority relation stems from abstract argumentation. Hence, we need to define the grounded extension of a SETAF. Given a (SET)AF F=(𝐴𝑟𝑔𝑠,), recall that the characteristic function of F is defined by ΓF(A)={αα is defended by A}. Then E𝐴𝑟𝑔𝑠 is a complete extension iff E is conflict-free and E=ΓF(E), and the grounded extension of F is the -minimal complete extension, or equivalently, the least fixpoint of ΓF.

Definition 75 (Unique repairs based on an arbitrary priority relation [30]).

Let 𝒦 be a prioritized KB (or database with anti-monotone ICs).

  • The grounded repair of 𝒦, 𝑔𝑟𝑜𝑢𝑛𝑑𝑒𝑑(𝒦), is the grounded extension of the PSETAF F𝒦, associated with 𝒦 (cf. Section 5.2.2).

  • For X{C,G,P}, the analogue of 𝑝𝑖𝑛𝑑(𝒦) is X-𝑅𝑒𝑝(𝒦).

Figure 3 shows the inclusion relationships between these types of repairs in the most specific case, when is induced by a prioritization. To obtain the relationships between repairs for preordered datasets, simply remove from the picture those that are not defined in this case. Finally, for arbitrary priority relations, it holds that 𝑔𝑟𝑜𝑢𝑛𝑑𝑒𝑑(𝒦)P-𝑅𝑒𝑝(𝒦)G-𝑅𝑒𝑝(𝒦)C-𝑅𝑒𝑝(𝒦) (the last two inclusions directly come from the relationship between completion-, globally- and Pareto-optimal repairs). Figure 3 also indicates relevant properties these repairs may have. In particular, they can be computed in polynomial time when the conflict hypergraph is given, except for the intersections of optimal repairs. We conclude with an example to illustrate the difference between all these “unique repairs”.

  • Polynomial computation:
    given the conflict hypergraph and , the repair can be computed in polynomial time
    holds for all but 𝑝𝑖𝑛𝑑(𝒦)

  • Complete w.r.t. isolated vertices:
    contains all facts that do not belong to any conflict (i.e., includes =S-𝑅𝑒𝑝(𝒦))
    holds for all but π(𝒦), (𝒦)

  • Sound w.r.t. prioritized intersection:
    included in the intersection of optimal repairs
    holds for all but (𝒦), 𝑛𝑑(𝒦)

Figure 3: (left) Relationships between “unique repairs” when is induced by a prioritization of the dataset [24, 22, 30]. An arrow XY means that XY. (right) Relevant properties [24, 30].
Example 76.

Assume that 𝒦=𝒟,𝒯 has the conflict graph depicted below and let P=𝒫1,𝒫2,𝒫3,𝒫4 be the prioritization of 𝒟 defined by: 𝒫1={α,β,γ}, 𝒫2={δ,ϵ,ζ}, 𝒫3={η,θ,κ}, 𝒫4={λ,μ}. Arrows on the conflict graph indicate the priority relation induced by P. The optimal repairs (P-𝑅𝑒𝑝(𝒦)) and “unique repairs” are given below. This example shows that all inclusions given in Figure 3 can be strict and that π(𝒦) and (𝒦) do not satisfy Complete w.r.t. isolated vertices, since they do not contain μ, while (𝒦) and 𝑛𝑑(𝒦) do not satisfy Sound w.r.t. prioritized intersection, since they contain η which does not belong to the intersection of the optimal repairs (actually, η does not belong to any of the optimal repairs).

P-𝑅𝑒𝑝(𝒦)={ {α,γ,δ,θ,λ,μ}, {α,γ,ϵ,θ,λ,μ}, {β,γ,δ,θ,λ,μ}, {β,γ,ϵ,θ,λ,μ}} 𝑝𝑖𝑛𝑑(𝒦)= {γ,θ,λ,μ} 𝑔𝑟𝑜𝑢𝑛𝑑𝑒𝑑(𝒦)= {γ,θ,μ} 𝑛𝑑(𝒦)= {γ,μ} π(𝒦)= (𝒦)= {η,θ,κ} 𝑛𝑑(𝒦)= {γ,η,θ,μ}

 Remark 77.

It is easy to define variants of π(𝒦) and (𝒦) that satisfy Complete w.r.t. isolated vertices: simply start by modifying the prioritization to add a level of highest priority that contains all facts that do not belong to any conflict.

5.4.3 Soft repairs for weighted constraints

In the database setting, soft constraints, which are expected to generally hold in the dataset but not necessarily in a perfect manner, have been considered. In this context, weights are used to represent the cost of deleting some fact or violating some constraint [60].

Definition 78 (Soft repairs of a database with anti-monotone constraints [60]).

Let 𝒦=𝒟,𝒯 be a database where 𝒯 is a set of anti-monotone ICs and let w:𝒟𝒯{}. A soft repair of 𝒟 w.r.t. 𝒯 is a dataset 𝒟 such that

𝖼𝗈𝗌𝗍𝒦w()=Σα𝒟w(α)+Στ𝒯w(τ)|𝐶𝑜𝑛𝑓(,{τ})|

is minimal, i.e., there is no 𝒟 such that 𝖼𝗈𝗌𝗍𝒦w()<𝖼𝗈𝗌𝗍𝒦w().

Soft repairs are not dataset repairs since they may be 𝒯-inconsistent. However, they generalize w-optimal repairs.

Proposition 79 ([60]).

If w is a function that assigns a positive weight to each fact of 𝒟, then w-𝑅𝑒𝑝(𝒟,𝒯) is equal to the set of soft repairs of 𝒟 w.r.t. 𝒯 using w where w(τ)= for each τ𝒯 and w(α)=w(α) for each α𝒟.

The generalization of soft constraints to DL KBs does not give rise to “soft repairs” but rather to “soft models”, since the optimization is done at the level of the interpretation instead of the dataset [36]. In this context, the cost of an interpretation is 𝖼𝗈𝗌𝗍𝒦w()=Σα𝒟,⊧̸αw(α)+Στ𝒯w(τ)|𝗏𝗂𝗈τ()| with 𝗏𝗂𝗈CD()=(C¬D) for every concept inclusion CD. Interpretations with minimal (or bounded) cost are then used to define variants of the certain and possible semantics.

6 Computational complexity of reasoning with (preferred) repairs

In this section, we present some complexity results on the following decision problems:

  • Repair checking takes as input a database or KB 𝒦=𝒟,𝒯 and a dataset , and outputs “yes” if is a (preferred) repair of 𝒦, and “no” otherwise;

  • BCQ entailment under CQA (resp. intersection, brave) semantics takes as input a database or KB 𝒦=𝒟,𝒯 and a BCQ q and output “yes” if 𝒦 entails q under the (preferred repair-based) CQA (resp. intersection, brave) semantics, and “no” otherwise.

We focus on these three semantics since CQA is the most studied inconsistency-tolerant semantics and intersection and brave provide the most and least cautious under- and over-approximations (cf. Figure 2). The complexity of reasoning under most of the other inconsistency-tolerant semantics mentioned in Section 4.1 is summarized in [28, Fig. 3] for DL-Lite KBs, with more details in [29]. Other relevant tasks that received significant attention include, e.g., the problem of enumerating the (preferred) repairs, counting them, or deciding whether there is a unique preferred repair [93, 30, 101].

6.1 The case of standard repairs

We first present the complexity of reasoning with standard dataset repairs.

6.1.1 Repair checking

Table 4 shows the data and combined complexity of repair checking (in the database case we focus on Δ-repairs but the complexity of - and -repair checking has also been studied [4, 130]). In Table 4, results for Datalog± and database ICs are mainly taken from [107, Table 3] and [11, Table 3], respectively, where the interested reader can find results for different complexity measures, additional languages, and proofs or pointers to the literature. Propositions 80, 81 and 82 state the results for DLs and refined data complexity results for Datalog±. Most of these results are known but they are not always explicitly stated in the literature, and the proofs illustrate the use of classical algorithms.

Table 4: Complexity of repair checking. All non-“in” entries are completeness results.
Data complexity Combined complexity
DLs
S-𝑅𝑒𝑝(𝒦)
DL-LiteR in L Prop. 82 NL Prop. 82
DL-LiteR,⊓ in L P Prop. 81
P Prop. 81 P
𝒜𝒞 DP Prop. 80 Exp Prop. 80
𝒮𝒬 DP Exp
Datalog±
S-𝑅𝑒𝑝(𝒦)
𝖫 in L Prop. 82 PSpace [107, Tab. 3]
𝖠 in L DExp
𝖦 P Prop. 81 2Exp
𝖲 in L Prop. 82 Exp
𝖥 P Prop. 81 Exp
ICs
S-𝑅𝑒𝑝(𝒦)
FD in L [11, Tab. 3] in L [11, Tab. 3]
DC in L DP
ICs
S-𝑅𝑒𝑝Δ(𝒦)
full TGD P [11, Tab. 3] DP [11, Tab. 3]
UC coNP Π2P
TGD coNP Π3P
Algorithms for repair checking.

The complexity upper bounds are shown using two classical algorithms for repair checking. Let 𝒦=𝒟,𝒯 be a KB or a database and be a dataset (repair candidate). The non-deterministic algorithm is as follows:

  1. 1.

    check that ,𝒯⊧̸,

  2. 2.

    check that minimally differs from 𝒟 by considering the complement (co-2): to show that does not minimally differ from 𝒟, guess such that ,𝒯⊧̸ and Δ𝒟Δ𝒟.

The deterministic algorithm works for KBs or databases with anti-monotone ICs, since in these cases, must be a subset of 𝒟 and is not maximal iff there is an immediate superset of in 𝒟 which is 𝒯-consistent:

  1. 1.

    check that 𝒟 and that ,𝒯⊧̸,

  2. 2.

    check that is maximal by checking that for each α𝒟, {α},𝒯.

Basic lower bounds.

Complexity lower bounds for consistency checking (Table 3) immediately transfer to repair checking since 𝒟 is a repair of 𝒟,𝒯 iff 𝒟 is 𝒯-consistent.

Proposition 80 (𝒜𝒞 and 𝒮𝒬).

For 𝒜𝒞 and 𝒮𝒬, repair checking is DP-complete w.r.t. data complexity, and Exp-complete w.r.t. combined complexity.

Proof.

The combined complexity upper bound follows from the deterministic algorithm for repair checking and the fact that consistency checking is in Exp. The matching lower bound comes from the Exp-hardness of consistency checking.

For the data complexity upper bound, we use the non-deterministic algorithm. Since consistency checking is in NP, step 1 can be done with a call to an NP oracle and step 2 with a call to a coNP oracle: indeed, (co-2) is in NP since we can guess a certificate of polynomial size that consists of (i) 𝒟 and (ii) a certificate that ,𝒯⊧̸, and check this certificate in P. We obtain the DP lower bound via a reduction from the DP-complete problem SAT-UNSAT: given a pair (φ1,φ2) of propositional formulas, decide whether φ1 is satisfiable and φ2 is unsatisfiable. We assume that φ1 and φ2 are sets of clauses such that each clause has exactly 2 positive and 2 negative literals, and can use truth constants true (1) and false (0) instead of variables (this is w.l.o.g. since 2+2SAT is NP-complete [128]). Let φ1 and φ2 be two sets of clauses {c11,,cm11} and {c12,,cm22} over variables x11,,xn11 and x12,,xn22 (and truth values 1, 0), respectively. We define an 𝒜𝒞 KB 𝒦=𝒟,𝒯 by:

𝒯={VTF,TF,P1.FP2.FN1.TN2.TF,Cl.FF}

and 𝒟=𝒟1𝒟2{F(0),T(1)} with:

𝒟i= {T(φi)}{Cl(φi,cki)1kmi}{V(xji)1jni}
{P(cki,xji){1,2},xji is the th positive literal of cki}
{N(cki,xji){1,2},¬xji is the th negative literal of cki}

We claim that 𝒟{T(φ2)}S-𝑅𝑒𝑝(𝒦) iff φ1 is satisfiable and φ2 is unsatisfiable. Indeed, it is easy to show that for i{1,2}, 𝒟i{F(0),T(1)} is 𝒯-consistent iff φi is satisfiable, since there is a one-to-one correspondence between models of 𝒟i{F(0),T(1)},𝒯, which assign each xji to T or F in a way that does not enforce any cki to be assigned to F, and valuations of the xji’s that satisfy φi. Moreover, 𝒟i{F(0),T(1)}{T(φi)} is 𝒯-consistent, since in this case there is a model that assigns all individuals but 1 to F. Since 𝒟1 and 𝒟2 are disjoint, the claim follows easily.

Proposition 81 (P bounds).

For all ontology languages from Table 4 but 𝒜𝒞 and 𝒮𝒬, repair checking is in P w.r.t. data complexity. Matching lower bounds hold for , 𝖦 and 𝖥. For DL-LiteR, DL-LiteR,⊓ and , repair checking is also in P w.r.t. combined complexity. Matching lower bounds hold for DL-LiteR,⊓ and .

Proof.

For the upper bounds, we use the deterministic algorithm and the fact that consistency checking is in P for the considered languages and complexity measures. The lower bounds come from P-hardness of consistency checking in data or combined complexity.

Proposition 82 (Below P).

Repair checking is in L w.r.t. data complexity for DL-LiteR, DL-LiteR,⊓, 𝖫, 𝖠 and 𝖲, and NL-complete w.r.t. combined complexity for DL-LiteR.

Proof.

For the data complexity upper bound, the DL-LiteR and DL-LiteR,⊓ cases follow from the 𝖲 case (cf. Figure 1). For 𝖫, 𝖠 and 𝖲, we use a data-independent reduction from repair checking in any of these languages to repair checking for a database with DCs, which is in L w.r.t. data complexity (cf. Table 4). Indeed, by Proposition 7, since L, A and S are UCQ-rewritable (Fact 5), for every ontology 𝒯, there exists a BUCQ q𝒯 such that for every dataset , ,𝒯 iff q𝒯 iff ,𝒯𝖣𝖢, where 𝒯𝖣𝖢 is the set of DCs that contains q for each BCQ q in q𝒯. Hence, S-𝑅𝑒𝑝(𝒟,𝒯) iff S-𝑅𝑒𝑝(𝒟,𝒯𝖣𝖢).

Regarding the combined complexity for DL-LiteR, the lower bound comes from the NL-hardness of consistency checking. For the upper bound, observe that since consistency checking is in NL w.r.t. combined complexity, and NL=coNL, inconsistency checking is also in NL. The deterministic algorithm for repair checking can thus be adapted as follows: guess a certificate that consists of (i) a certificate that ,𝒯⊧̸ and (ii) certificates that {α},𝒯 for each α𝒟. The certificate is of polynomial size and can be verified by a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape, since each certificate from (i)-(ii) is of polynomial size and verifiable by such a machine, and all certificates can be verified independently.

6.1.2 BCQ entailment under CQA, intersection, and brave semantics

Table 5 shows the data and combined complexity of deciding BCQ entailment under the CQA, intersection, and brave semantics. The results given in Table 5 are taken from:

  • [11, Tab. 1] for the CQA semantics over databases with ICs,

  • [104, Tab. 2, 3 & 6] for the CQA and intersection semantics over Datalog± KBs,

  • [29, Fig. 2, 3 & 4] for DL-LiteR, and 𝒜𝒞, [41, Th. 3 & Fig. 1] for DL-LiteR,⊓, and [126, Fig. 2] for 𝒮𝒬 (plus straightforward upper bound for brave).

The complexity of BCQ entailment under the intersection and brave semantics over databases and brave semantics in Datalog± has not been systematically investigated. In the remaining of this section, we present some classical algorithms for BCQ entailment under the three semantics and provide proofs for the few new results on Datalog± and databases (for which we consider data complexity, on which we focus in the next section on preferred repairs).

Table 5: Complexity of BCQ entailment under CQA, intersection, and brave semantics. All non-“in” entries are completeness results (except undecidability results).
Data complexity Combined complexity
CQA Int. brave CQA Int. brave
DLs
S-𝑅𝑒𝑝(𝒦)
DL-LiteR coNP in 𝖠𝖢0 in 𝖠𝖢0 Π2P NP NP
DL-LiteR,⊓ coNP in 𝖠𝖢0 in 𝖠𝖢0 Π2P Θ2P NP
coNP coNP NP Π2P Θ2P NP
𝒜𝒞 Π2P Π2P Σ2P Exp Exp Exp
𝒮𝒬 Π2P Π2P Σ2P 2Exp 2Exp 2Exp
Datalog±
S-𝑅𝑒𝑝(𝒦)
𝖫 coNP in 𝖠𝖢0 in 𝖠𝖢0 PSpace PSpace PSpace
𝖠 coNP in 𝖠𝖢0 in 𝖠𝖢0 PNExp PNExp PNExp
𝖦 coNP coNP NP 2Exp 2Exp 2Exp
𝖲 coNP in 𝖠𝖢0 in 𝖠𝖢0 Exp Exp Exp
𝖥 coNP coNP NP Exp Exp Exp
ICs
S-𝑅𝑒𝑝(𝒦)
FD coNP in 𝖠𝖢0 in 𝖠𝖢0 Π2P
DC coNP in 𝖠𝖢0 in 𝖠𝖢0 Π2P
ICs
S-𝑅𝑒𝑝Δ(𝒦)
full TGD coNP coNP P Exp
UC Π2P Π2P Σ2P Π2Exp
TGD undec. undec.
Classical algorithms.

Most upper complexity bounds are shown using the non-deterministic versions of Algorithms 1, 2 and 3, where one guesses a repair that does not entail the query to show that it does not hold under CQA semantics, a repair that entails the query to show that it holds under brave semantics, and the appropriate and 1,,n to show that the query is not entailed under intersection semantics. Note that in the case of brave semantics, since every 𝒯-consistent subset of 𝒟 can be extended into a standard repair, it is sufficient to check that ,𝒯⊧̸ instead of S-𝑅𝑒𝑝(𝒦) in Algorithm 2 when X=S. These algorithms can be adapted for semantics based on Δ-repairs of databases with UCs, by considering subsets of 𝐹𝑎𝑐𝑡𝑠𝒟𝒯 (whose size is exponential w.r.t. the maximal arity of the predicates in 𝒯 and polynomial w.r.t. the size of 𝒟) instead of subsets of 𝒟. This does not extend to ICs with existential quantifiers in the head such as TGDs, since in this case repairs may use constants that do not occur in 𝒦.

Algorithm 1 X-CQA.

Input: a KB or database with anti-monotone ICs 𝒦=𝒟,𝒯 and a BCQ q
Output: 𝗍𝗋𝗎𝖾 iff 𝒦 entails q under CQA semantics based on X-𝑅𝑒𝑝(𝒦)

Algorithm 2 X-brave.

Input: a KB or database with anti-monotone ICs 𝒦=𝒟,𝒯 and a BCQ q
Output: 𝗍𝗋𝗎𝖾 iff 𝒦 entails q under brave semantics based on X-𝑅𝑒𝑝(𝒦)

Algorithm 3 X-intersection.

Input: a KB or database with anti-monotone ICs 𝒦=𝒟,𝒯 and a BCQ q
Output: 𝗍𝗋𝗎𝖾 iff 𝒦 entails q under intersection semantics based on X-𝑅𝑒𝑝(𝒦)

When the conflicts can be computed efficiently, Algorithm 4 provides an efficient way of deciding BCQ entailment under intersection semantics.

Algorithm 4 Intersection semantics from conflicts.

Input: a KB or database with anti-monotone ICs 𝒦=𝒟,𝒯 and a BCQ q
Output: 𝗍𝗋𝗎𝖾 iff 𝒦 entails q under (plain) intersection semantics

Basic lower bounds.

Complexity lower bounds for BCQ entailment under the classical semantics (Table 2) immediately transfer to BCQ entailment under CQA, intersection and brave semantics. Indeed, the hardness results for BCQ entailment under the classical semantics hold in the case where 𝒟 is assumed to be 𝒯-consistent, and in this case the classical, CQA, intersection and brave semantics all coincide.

𝗔𝗖𝟎 upper bounds.

The 𝖠𝖢0 upper bounds in Table 5 follow from the following result [41].

Proposition 83 ([41, Theorems 1, 2, 3]).

If CQ answering under is FO-rewritable and for every ontology 𝒯 in and BCQ q, there exist and m such that for every 𝒟, (i) every minimal 𝒯-consistent subset 𝒮 of 𝒟 such that 𝒮,𝒯q has cardinality at most and (ii) every conflict of 𝒟,𝒯 has cardinality at most m, then CQ answering under the intersection and brave semantics in is FO-rewritable: for every ontology 𝒯 and BCQ q, there exists an FO-sentence φ𝒯,q (resp. φ𝒯,qbrave) such that for every 𝒟, q is entailed by 𝒟,𝒯 under intersection (resp. brave) semantics iff 𝒟φ𝒯,q (resp. 𝒟φ𝒯,qbrave).

Corollary 84 (𝖠𝖢0 bounds).

BCQ entailment under intersection and brave semantics is in 𝖠𝖢0 w.r.t. data complexity for DL-LiteR, DL-LiteR,⊓, 𝖫, 𝖠, 𝖲, FDs and DCs.

Proof.

These languages satisfy the conditions of Proposition 83. Indeed, CQ answering is UCQ-rewritable (cf. Fact 5), hence FO-rewritable and:

  1. (i)

    for DCs (hence also FDs) the size of minimal 𝒯-consistent subsets 𝒮 of 𝒟 such that 𝒮,𝒯q is bounded by |q|, and for 𝖫, 𝖠 and 𝖲 (hence also DL-LiteR and DL-LiteR,⊓), it is bounded by the maximal number of atoms in some BCQ in 𝖱𝖾𝗐(q,𝒯);

  2. (ii)

    for DCs (hence also FDs) the size of conflicts is bounded by the maximal number of atoms in some DC body, and for 𝖫, 𝖠 and 𝖲 (hence also DL-LiteR and DL-LiteR,⊓), by Proposition 7, for every ontology 𝒯, there exists a BUCQ q𝒯 such that for every dataset 𝒟, 𝒟,𝒯 iff 𝒟q𝒯 so the size of conflicts is bounded by the maximal number of atoms in some BCQ of q𝒯.

Example 85 illustrates why Proposition 83 does not apply to the other ontology languages considered in Table 5: the size of the conflicts cannot be bounded independently from 𝒟.

Example 85.

Let 𝒯={R(x,y)A(x)A(y),A(x)B(x)}, which belongs to 𝖥, 𝖦 and . For every n1, we can build a dataset 𝒟 of size n+2 which is a conflict (of itself) w.r.t. 𝒯: 𝒟={A(a0),R(a0,a1),,R(an1,an),B(an)}.

Note that if we interpret 𝒯 as a set of UCs in Example 85, it also shows that the size of the conflicts cannot be bounded independently from 𝒟 for databases with UCs. It is actually undecidable to determine whether there exists such that for every dataset 𝒟, max𝒞𝐶𝑜𝑛𝑓(𝒟,𝒯)|𝒞| when 𝒯 is a set of full TGDs [32, Theorem 5]333Theorem 5 in [32] is stated for universal constraints but the proof uses only full TGDs..

Brave semantics in Datalog±.

For brave semantics and Datalog±, the 𝖠𝖢0 upper bounds come from Corollary 84 and the other bounds in Table 5 follows easily from known results:

Proposition 86.

BCQ entailment under brave semantics is PSpace-complete for 𝖫, PNExp-complete for 𝖠, 2Exp-complete for 𝖦, and Exp-complete for 𝖲 and 𝖥 w.r.t. combined complexity, and NP-complete for 𝖦 and 𝖥 w.r.t. data complexity.

Proof.

The NP data complexity upper bounds follow from the non-deterministic version of Algorithm 2, since both repair checking and BCQ entailment are in P w.r.t. data complexity for 𝖦 and 𝖥. For the matching lower bound, we remark that the reduction used in the proof of NP-hardness of BCQ entailment under brave semantics in [29, Theorem 29] builds an ontology without existential on the right-hand side, which is thus in 𝖦 and 𝖥.

The 2Exp and Exp combined complexity upper bounds for 𝖦, 𝖲 and 𝖥 follow from Algorithm 2 (since repair checking and BCQ entailment are both in 2Exp or Exp, respectively) and the lower bounds from the respective combined complexity of BCQ entailment.

The PSpace combined complexity upper bound for 𝖫 follows from the non-deterministic version of Algorithm 2, since repair checking and BCQ entailment are in PSpace for 𝖫 and NPSpace=PSpace. The lower bound comes from that of BCQ entailment in 𝖫.

The PNExp combined complexity upper bound for 𝖠 follows from the non-deterministic version of Algorithm 2, since repair checking is in DExp and BCQ entailment in NExp for 𝖠, so that the “check” phase can be done in PNExp, and the fact that NPNExp=PNExp [89, 104]. The lower bound follows from the reduction from the PNExp-hard extended exponential tiling problem used to show the lower bound for intersection semantics in [104, Theorem 6.2]: given an extended tiling system , a KB 𝒟,𝒯 is built such that is valid iff 𝖸𝖾𝗌() is entailed by 𝒟,𝒯 under intersection semantics, and since (i) 𝖸𝖾𝗌()𝒟, (ii) 𝖸𝖾𝗌() does not occur in the body of any TGD and (iii) the only NC that contains 𝖸𝖾𝗌() is ϕ(x)𝖸𝖾𝗌()𝖭𝗈(), it follows that is valid iff q=xϕ(x)𝖭𝗈() is not entailed under brave semantics.

Data complexity of brave and intersection semantics in databases.

For brave and intersection BCQ entailment over databases, the 𝖠𝖢0 upper bounds come from Corollary 84, the data complexity results for UCs are taken from [32, Tab. 1] (they follow from the proof of [32, Theorem 3]), and the other results given in Table 5 are proved below.

Proposition 87 (Full TGD).

For the IC language of full TGDs and data complexity, BCQ entailment under brave semantics is P-complete and BCQ entailment under intersection semantics is coNP-complete.

Proof.

For brave semantics, we remark that for every database 𝒦=𝒟,𝒯 such that 𝒯 is a set of full TGDs, for every BCQ q, q is entailed by 𝒦 under brave semantics iff q is (classically) entailed by the F (a.k.a. Datalog) KB 𝒦𝖥=𝒟,𝒯. Indeed, it is known that for full TGDs, there exists a unique -repair , which can be computed in polynomial time w.r.t. the size of the dataset via the chase procedure [130], and we can show that every S-𝑅𝑒𝑝Δ(𝒦) is such that . Since BCQ evaluation is monotone, it follows that there exists S-𝑅𝑒𝑝Δ(𝒦) such that q holds in iff q holds in . Finally, since 𝒦𝖥q iff q holds in (by the fixpoint semantics of Datalog, cf. [1, Sec. 12.3]), we obtain that q is entailed by 𝒦 under brave semantics iff q is classically entailed by 𝒦𝖥. The upper bound then follows from the fact that BCQ entailment in F is in P and the lower bound from the reduction that shows P-hardness of BCQ entailment in F [70, Th. 4.4].

For intersection semantics, the coNP upper bound follows from the non-deterministic version of Algorithm 3 (adapted for databases with UCs), since repair checking and BCQ entailment are in P and the repair size is polynomially bounded w.r.t. data complexity. For the lower bound, we use a reduction from UNSAT. Let φ be a conjunction of clauses c1,,cm over variables x1,,xn and define 𝒦=𝒟,𝒯 by:

𝒯={ 𝖭𝖾𝗑𝗍(z1,z2)𝖢𝗁𝖾𝖼𝗄(z2)𝖯𝗈𝗌(z2,x1)𝖳𝗋𝗎𝖾(x1)𝖢𝗁𝖾𝖼𝗄(z1),
𝖭𝖾𝗑𝗍(z1,z2)𝖢𝗁𝖾𝖼𝗄(z2)𝖭𝖾𝗀(z2,x1)𝖥𝖺𝗅𝗌𝖾(x1)𝖢𝗁𝖾𝖼𝗄(z1),
𝖢𝗁𝖾𝖼𝗄(z)𝖴𝗇𝗌𝖺𝗍(z)𝖡(),𝖳𝗋𝗎𝖾(x)𝖥𝖺𝗅𝗌𝖾(x)𝖡()}
𝒟={ 𝖴𝗇𝗌𝖺𝗍(c0)}{𝖢𝗁𝖾𝖼𝗄(cm)}{𝖭𝖾𝗑𝗍(cj1,cj)1jm}{𝖯𝗈𝗌(cj,xi)xicj}
{ 𝖭𝖾𝗀(cj,xi)¬xicj}{𝖳𝗋𝗎𝖾(xi),𝖥𝖺𝗅𝗌𝖾(xi)1in}

We claim that 𝖴𝗇𝗌𝖺𝗍(c0) is entailed by 𝒦 under intersection semantics iff φ is unsatisfiable. Indeed, if there exists a valuation ν of x1,,xn that satisfies φ, the following dataset is a Δ-repair of 𝒟 w.r.t. 𝒯, so 𝖴𝗇𝗌𝖺𝗍(c0) does not hold under intersection semantics.

ν={ 𝖢𝗁𝖾𝖼𝗄(cj)0jm}{𝖭𝖾𝗑𝗍(cj1,cj)1jm}{𝖯𝗈𝗌(cj,xi)xicj}
{ 𝖭𝖾𝗀(cj,xi)¬xicj}{𝖳𝗋𝗎𝖾(xi)ν(xi)=1}{𝖥𝖺𝗅𝗌𝖾(xi)ν(xi)=0}

In the other direction, if there is a Δ-repair of 𝒟 w.r.t. 𝒯 such that 𝖴𝗇𝗌𝖺𝗍(c0), then 𝖡() and 𝖢𝗁𝖾𝖼𝗄(c0) (otherwise {𝖴𝗇𝗌𝖺𝗍(c0)} would be 𝒯-consistent). Since 𝖢𝗁𝖾𝖼𝗄(c0), there must exist xi such that {𝖭𝖾𝗑𝗍(c0,c1),𝖢𝗁𝖾𝖼𝗄(c1),𝖯𝗈𝗌(c1,xi),𝖳𝗋𝗎𝖾(xi)} or {𝖭𝖾𝗑𝗍(c0,c1),𝖢𝗁𝖾𝖼𝗄(c1),𝖭𝖾𝗀(c1,xi),𝖥𝖺𝗅𝗌𝖾(xi)} is included in (otherwise {𝖢𝗁𝖾𝖼𝗄(c0)} would be 𝒯-consistent), and we can show that for every 1jm, there must exist xi such that either {𝖭𝖾𝗑𝗍(cj1,cj),𝖢𝗁𝖾𝖼𝗄(cj),𝖯𝗈𝗌(cj,xi),𝖳𝗋𝗎𝖾(xi)} or {𝖭𝖾𝗑𝗍(cj1,cj),𝖢𝗁𝖾𝖼𝗄(cj),𝖭𝖾𝗀(cj,xi),𝖥𝖺𝗅𝗌𝖾(xi)} is included in . Moreover, since 𝖡(), for every xi, either 𝖳𝗋𝗎𝖾(xi) or 𝖥𝖺𝗅𝗌𝖾(xi) does not belong to so the valuation ν defined by ν(xi)=1 iff 𝖳𝗋𝗎𝖾(xi) satisfies all clauses of φ.

6.2 Reasoning with preferred repairs

In this section, we present the impact of using preferred repairs on the computational complexity. Table 7 shows the data complexity of reasoning with X-optimal repairs for X{,w,P,P,Pareto,globally,completion}, for languages for which repairs are -repairs and consistency checking and BCQ entailment are in P. The lower bounds apply to languages that extend either DL-Litecore, FD, or NC, yielding tight data complexity bounds for all semantics based on optimal repairs for DL-Litecore, DL-LiteR, DL-LiteR,⊓, 𝖫, 𝖠, 𝖦, 𝖲, 𝖥, FD and DC. Similarly, Table 7 shows the data complexity of reasoning with preference program-based prioritized KBs, for languages for which repairs are -repairs and consistency checking and BCQ entailment are in P, but since such repairs have not been considered in as many settings as the others, we only report the lower bounds for the languages considered in the original paper [50]. For the results given in Table 7, we present the algorithms that yield the upper bounds [33, 107, 102, 129] and give references or show the lower bounds in Sections 6.2.1 and 6.2.2. We then discuss these results and mention some additional complexity results that do not fall into the setting considered in Table 7 (e.g., on combined complexity or for more expressive languages) in Section 6.2.3.

Table 6: Data complexity of repair checking and BCQ entailment under CQA, intersection, and brave semantics with -optimal repairs, or Pareto-, globally- or completion-optimal repairs. Upper bounds hold for every ontology or anti-monotone IC language for which consistency checking and BCQ entailment are in P. Lower bounds hold for every language that extends either DL-Litecore, FD, or NC. : Θ2P if there is a data-independent bound on the weights or number or priority levels.
Repair checking CQA Intersection Brave
-𝑅𝑒𝑝(𝒦) coNP Θ2P Θ2P Θ2P
w-𝑅𝑒𝑝(𝒦) coNP Δ2P Δ2P Δ2P
P-𝑅𝑒𝑝(𝒦) coNP Δ2P Δ2P Δ2P
P-𝑅𝑒𝑝(𝒦) in P coNP coNP NP
P-𝑅𝑒𝑝(𝒦) in P coNP coNP NP
C-𝑅𝑒𝑝(𝒦) in P coNP coNP NP
G-𝑅𝑒𝑝(𝒦) coNP Π2P Π2P Σ2P
Table 7: Data complexity of repair checking and BCQ entailment under CQA, intersection, and brave semantics with Π-preferred repairs. Upper bounds hold for every ontology or anti-monotone IC language for which consistency checking and BCQ entailment are in P. Lower bounds hold for all Datalog± fragments we consider [50] (note that [50] allows for constants in TGDs and NCs). The results for brave semantics are not explicitly given in [50] but both the upper and lower bounds can be obtained by adapting straightforwardly the proofs for the other semantics.
Repair checking CQA Intersection Brave
𝑃𝑟-𝑅𝑒𝑝(𝒦Π) coNP Π2P Π2P Σ2P
𝑃𝑟-𝑅𝑒𝑝(𝒦Π) coNP Θ2P Θ2P Θ2P

6.2.1 Repair checking

This section presents the proofs for the results on repair checking given in Table 7.

Proposition 88.

For every ontology language or anti-monotone IC language for which consistency checking and BCQ entailment are in P w.r.t. data complexity, the data complexity of repair checking is in coNP for X-optimal repairs for X{,w,P,globally} and in P for X-optimal repairs for X{P,Pareto,completion}. Matching coNP lower bounds hold for every ontology language or IC language that extends DL-Litecore, NC or FD.

Upper bounds.

The upper bounds are obtained via Algorithms 5 to 9, using the non-deterministic versions of Algorithms 5 and 6 where one guesses an appropriate 𝒟 to show that X-𝑅𝑒𝑝(𝒦). The correctness of the algorithms straightforwardly follows from the respective definitions of preferred repairs, except for the completion-optimal repair case, which was shown in [129, Corollary 4].

Algorithm 5 -optimal repair checking for {,w,P}.

Input: 𝒦=𝒟,𝒯 and 𝒟 (and weight function w or prioritization P when relevant)
Output: 𝗍𝗋𝗎𝖾 iff -𝑅𝑒𝑝(𝒦)

Algorithm 6 Globally-optimal repair checking.

Input: 𝒦=(𝒟,𝒯,) and 𝒟
Output: 𝗍𝗋𝗎𝖾 iff G-𝑅𝑒𝑝(𝒦)

Algorithm 7 P-optimal repair checking.

Input: 𝒦=𝒟,𝒯 with prioritization P=𝒫1,,𝒫n and 𝒟
Output: 𝗍𝗋𝗎𝖾 iff P-𝑅𝑒𝑝(𝒦)

Algorithm 8 Pareto-optimal repair checking.

Input: 𝒦=(𝒟,𝒯,) and 𝒟
Output: 𝗍𝗋𝗎𝖾 iff P-𝑅𝑒𝑝(𝒦)

Algorithm 9 Completion-optimal repair checking.

Input: 𝒦=(𝒟,𝒯,) and 𝒟
Output: 𝗍𝗋𝗎𝖾 iff C-𝑅𝑒𝑝(𝒦)

Lower bounds.

The coNP lower bound for globally-optimal repair checking has been shown for a logical theory that contains four FDs [129, Theorem 2] as well as for a DL-Litecore ontology that contains only axioms that can be written as NCs [30, Theorem 10]. The coNP lower bound for -optimal repair checking (hence also for w- and P-optimal repair checking, since -optimal repairs can be obtained as special cases of w- or P-optimal repairs) has been shown for a logical theory that contains a single NC [103, Corollary 1]. We show next that it also holds for FD and for DL-Litecore (using only axioms that can be written as NCs) by two reductions from 3-SAT. Let φ=c1cm be a conjunction of clauses of three literals over variables x1,,xn.

  • For the FD case, define 𝒦𝖥𝖣=𝒟𝖥𝖣,𝒯𝖥𝖣 with

    𝒯𝖥𝖣={ P(x1,x2,x3,x4,x5)P(y1,y2,y3,y4,y5)x1=y1x2=y2,
    P(x1,x2,x3,x4,x5)P(y1,y2,y3,y4,y5)x2=y2x3=y3,
    P(x1,x2,x3,x4,x5)P(y1,y2,y3,y4,y5)x4=y4x5=y5}
    𝒟𝖥𝖣={ P(cj,xi,1,a,b)xicj,1jm}{P(cj,xi,0,a,b)¬xicj,1jm}
    {P(dj,e,f,a,c)1jm1}

    We can show that ={P(dj,e,f,a,c)1jm1} is not a -optimal repair of 𝒦𝖥𝖣 iff φ is satisfiable. Indeed, is 𝒯𝖥𝖣-consistent and ||=m1, so -𝑅𝑒𝑝(𝒦𝖥𝖣) iff there exists a 𝒯𝖥𝖣-consistent 𝒟𝖥𝖣 of size at least m. Such necessarily contains only facts of the form P(cj,xi,_,a,b) because of the last FD, so contains exactly m facts because of the first two FDs. It is easy to check that the valuation ν of the xi defined by ν(xi)=1 iff contains some P(cj,xi,1,a,b) satisfies every clause. In the other direction, every valuation that satisfies φ can be used to build a repair of size m.

  • For the DL-Litecore (and NC) case, define 𝒦𝖣𝖫=𝒟𝖣𝖫,𝒯𝖣𝖫 with

    𝒯𝖣𝖫={ P¬Nk1,k3}{U¬P,U¬N13}
    { S¬U}{P¬Pk,N¬Nk,P¬Nk1k3}
    𝒟𝖣𝖫={ S(φ)}{U(φ,cj)1jm}
    { P(cj,xi)xi is the th literal of cj}{N(cj,xi)¬xi is the th literal of cj}

    We can show that ={U(φ,cj)1jm} is not a -optimal repair of 𝒦𝖣𝖫 iff φ is satisfiable. Indeed, is 𝒯𝖣𝖫-consistent and ||=m, so -𝑅𝑒𝑝(𝒦𝖣𝖫) iff there exists a 𝒯𝖣𝖫-consistent 𝒟𝖣𝖫 of size at least m+1. Since every repair of 𝒦𝖣𝖫 contains at most one fact of the form P(cj,xi) or Nk(cj,xi) per cj, and such fact prevents the corresponding U(φ,cj) to belong to the repair, the only way to obtain a repair of size m+1 is to select exactly one P(cj,xi) or Nk(cj,xi) per cj, remove all U(φ,cj), and keep S(φ). Since each xi cannot occur both in P- and Nk-facts, such repair corresponds to a valuation ν of the xi such that ν(xi)=1 iff contains some P(cj,xi) and it is easy to check that ν satisfies φ. In the other direction, every satisfying valuation can be used to build a repair of size m+1.

6.2.2 BCQ entailment under CQA, intersection, and brave semantics

This section presents the proofs for the results on BCQ entailment under the different semantics given in Table 7.

Proposition 89.

For every ontology language or anti-monotone IC language for which consistency checking and BCQ entailment are in P w.r.t. data complexity, the data complexity of BCQ entailment under CQA or intersection (resp. brave) with X-optimal repairs is in

  • coNP (resp. NP) for X{P,Pareto,completion};

  • Π2P (resp. Σ2P) for X=globally;

  • Δ2P for X{w,P};

  • Θ2P for X= and for X{w,P} if there is a data-independent bound on the weights or number of priority levels.

Matching lower bounds hold for every ontology language or IC language that extends DL-Litecore, NC or FD.

Upper bounds.

For semantics based on X-optimal repairs with X{P, Pareto,completion}, since X-optimal repair checking is in P, the coNP and NP upper bounds for BCQ entailment under X-CQA, X-brave and X-intersection semantics follow from the non-deterministic versions of Algorithms 1, 2 and 3 for X{P,P,C}. Similarly, for semantics based on globally-optimal repairs, since globally-optimal repair checking is in coNP, the Π2P and Σ2P upper bounds for BCQ entailment under G-CQA, G-brave and G-intersection follow from these algorithms. For the other kinds of repairs, we use the reduction of - and P-optimal repairs to w-optimal ones and Algorithms 11, 12 and 13 for semantics based on w-optimal repairs. These algorithms rely on an NP oracle to check the existence of 𝒟 as required both in the function 𝖮𝗉𝗍𝗂𝗆𝖺𝗅𝖶𝖾𝗂𝗀𝗁𝗍𝖡𝗒𝖡𝗂𝗇𝖺𝗋𝗒𝖲𝖾𝖺𝗋𝖼𝗁 (Algorithm 10) and the final condition.

Algorithm 10 𝖮𝗉𝗍𝗂𝗆𝖺𝗅𝖶𝖾𝗂𝗀𝗁𝗍𝖡𝗒𝖡𝗂𝗇𝖺𝗋𝗒𝖲𝖾𝖺𝗋𝖼𝗁.

Input: 𝒦=𝒟,𝒯, a weight function w:𝒟
Output: the weight uopt of w-optimal repairs

Algorithm 11 w-CQA.

Input: 𝒦=𝒟,𝒯, a weight function w:𝒟, and a BCQ q
Output: 𝗍𝗋𝗎𝖾 iff 𝒦 entails q under CQA semantics based on w-𝑅𝑒𝑝(𝒦)

Algorithm 12 w-brave.

Input: 𝒦=𝒟,𝒯, a weight function w:𝒟, and a BCQ q
Output: 𝗍𝗋𝗎𝖾 iff 𝒦 entails q under brave semantics based on w-𝑅𝑒𝑝(𝒦)

Algorithm 13 w-intersection.

Input: 𝒦=𝒟,𝒯, a weight function w:𝒟, and a BCQ q
Output: 𝗍𝗋𝗎𝖾 iff 𝒦 entails q under intersection semantics based on w-𝑅𝑒𝑝(𝒦)

The number of calls to the NP oracle is logarithmically bounded in Σα𝒟w(α) so is polynomial w.r.t. the size of 𝒟 if the weights (considered part of 𝒟) are encoded in binary, and logarithmic if the weights are encoded in unary or if there exists a constant k independent of 𝒟 such that w(α)k for every α, since in this case Σα𝒟w(α)k|𝒟|. In particular, this is the case for -optimal repairs (case w(α)=1). For P-optimal repairs, we use the reduction to w-optimal repairs presented in Section 5.1: given P=𝒫1,,𝒫n, let u=(𝗆𝖺𝗑i=1n|𝒫i|)+1, and w(α)=uni for α𝒫i, then P-𝑅𝑒𝑝(𝒟,𝒯)=w-𝑅𝑒𝑝(𝒟,𝒯). Again, if n is bounded by a constant k independent from 𝒟, the resulting weights are bounded by (|𝒟|+1)k1 so Σα𝒟w(α)(|𝒟|+1)k and the number of oracle calls is logarithmic.

Lower bounds.

For semantics based on X-optimal repairs with X{P, Pareto,completion}, the coNP and NP lower bounds have been shown in the case of P-optimal repair-based semantics for DL-Litecore [44, Prop. 6.2.3 and 6.2.8] and the ontologies used in the reduction are equivalent to sets of NCs. Since in the case where a priority relation is induced by a prioritization P=𝒫1,,𝒫n, Pareto- and completion-optimal repairs coincide with P-optimal repairs, these lower bounds transfer to the cases of Pareto- and completion-optimal repairs. For FD, the coNP and NP lower bounds have been shown for X-CQA [129, Theorem 3] and for X-intersection and X-brave [31, Theorem 3], either directly for X=P or using a priority relation that can be induced by a prioritization.

For semantics based on globally-optimal repairs, the Π2P and Σ2P lower bounds have been shown for DL-Litecore using ontologies equivalent to sets of NCs [30, Theorem 10], and the Π2P-hardness proof for G-CQA with FDs [129, Theorem 2] immediately yields the lower bound for G-intersection and G-brave semantics. Indeed, it uses as query a fact p from the dataset, and every repair that does not contain p contains p. Hence p is entailed under G-CQA iff it is entailed under G-intersection iff p is not entailed G-brave semantics.

For semantics based on X-optimal repairs with X{,w,P}, a Θ2P lower bound has been shown for -CQA, -intersection and -brave semantics (hence transfers to w- and P-optimal repair-based semantics, even in the case where the weights are bounded by a constant and there is a single priority level) [44, Prop. 6.2.4 and 6.2.9] and the reductions can be easily adapted to use only NCs. The lower bound for -CQA has also been shown for a logical theory that contains a single NC [103, Theorem 4]. For FD, we use a reduction from the following Θ2P-hard problem [103, Lemma 6]: given a graph 𝒢=(V,E) and a vertex vdV, decide if vd belongs to all (cardinality) maximum independent sets (MISs) of 𝒢. Assume w.l.o.g. that every vV belongs to some eE and define 𝒦=𝒟,𝒯 as follows, where for vV, 𝑛𝑒(v)=|{eve,eE}| is the number of edges of 𝒢 in which v occurs.

𝒯={ R(x1,x2,x3,x4)R(y1,y2,y3,y4)x1=y1x2=y2,
R(x1,x2,x3,x4)R(y1,y2,y3,y4)x2=y2x3=y3}
𝒟={ R(e,v,1,j)ve,eE,1j2}{R(v,v,0,i)vV,1i2𝑛𝑒(v)1}

We show that vd belongs to all MISs of 𝒢 iff xR(x,vd,1,1) is entailed under -CQA (resp. -intersection) semantics, iff R(vd,vd,0,1) is not entailed under -brave semantics. We first show a correspondence between -optimal repairs of 𝒦 and MISs of 𝒢:

  • Given an independent set SV of 𝒢, define S={R(e,v,1,j)R(e,v,1,j)𝒟,vS}{R(v,v,0,i)R(v,v,0,i)𝒟,vS}. S satisfies the second FD by construction and the first one because S is an independent set. Hence S is 𝒯-consistent. Moreover, |S|=ΣvS2𝑛𝑒(v)+ΣvS(2𝑛𝑒(v)1)=ΣvV2𝑛𝑒(v)|VS|.

  • Given a 𝒯-consistent subset 𝒟, define S={vR(e,v,1,j)}. For each vS, does not contain any fact of the form R(v,v,0,i) (or it would violate the second FD) and for each vS, by definition of S, does not contain any fact of the form R(e,v,1,j). Hence ||ΣvS2𝑛𝑒(v)+ΣvS(2𝑛𝑒(v)1)=ΣvV2𝑛𝑒(v)|VS|.

  • Let -𝑅𝑒𝑝(𝒦). We show that S is an independent set of 𝒢. Assume for a contradiction that there is an edge e0=(v1,v2) such that v1,v2S. For k{1,2}, let k={R(e,vk,1,j)vke,eE,1j2}{R(vk,vk,0,i)1i2𝑛𝑒(vk)1}. Since is 𝒯-consistent, it is easy to check that the k are also 𝒯-consistent. Since v1,v2S, must contain some facts of the form R(e1,v1,1,j) and R(e2,v2,1,j) (by definition of S). Hence does not contain any fact of the form R(v1,v1,0,i) nor R(v2,v2,0,i). Moreover, by the first FD, there is k{1,2} such that does not contain R(e0,vk,1,j) for 1j2. Hence there is k{1,2} such that k is obtained from by adding exactly 2𝑛𝑒(vk)1 facts of the form R(vk,vk,0,i) and removing at most 2𝑛𝑒(vk)2 facts of the form R(e,vk,1,j) so |k|>||. This contradicts the fact that -𝑅𝑒𝑝(𝒦). Hence S is an independent set of 𝒢.

  • Let -𝑅𝑒𝑝(𝒦). We have shown that S is an independent set of 𝒢 and ||ΣvV2𝑛𝑒(v)|VS|. Assume for a contradiction that there exists an independent set S of 𝒢 such that |S|>|S|. We have shown that |S| is 𝒯-consistent and |S|=ΣvV2𝑛𝑒(v)|VS|. It follows that |S|=ΣvV2𝑛𝑒(v)|VS|>ΣvV2𝑛𝑒(v)|VS|||, which contradicts -𝑅𝑒𝑝(𝒦). We conclude that S is a MIS of 𝒢.

  • Let SV be a MIS of 𝒢. Since S is an independent set, S is 𝒯-consistent and |S|=ΣvV2𝑛𝑒(v)|VS|. Assume for a contradiction that S-𝑅𝑒𝑝(𝒦) and let -𝑅𝑒𝑝(𝒦). We have shown that S is an independent set of 𝒢 and ||ΣvV2𝑛𝑒(v)|VS|. Since we assumed that ||>|S|, it follows that |S|>|S|, which contradicts that S is a MIS of 𝒢. We conclude that S-𝑅𝑒𝑝(𝒦).

Assume that vd belongs to every MIS of 𝒢 and let -𝑅𝑒𝑝(𝒦). Since S is a MIS of 𝒢, vdS so there exists R(ed,vd,1,j) and does not contain any fact of form R(vd,vd,0,j) and contains R(ed,vd,1,1) (by maximality). Hence xR(x,vd,1,1) is entailed under -intersection (hence -CQA) semantics and R(vd,vd,0,1) is not entailed under -brave semantics. In the other direction, assume that there exists a MIS S of 𝒢 such that vdS. Then S-𝑅𝑒𝑝(𝒦) is such that there is no fact of the form R(e,vd,1,j) in S and R(vd,vd,0,1)S so R(vd,vd,0,1) is entailed under -brave semantics and xR(x,vd,1,1) is not entailed under -CQA (hence nor under -intersection) semantics.

For semantics based on X-optimal repairs with X{w,P} (in the case where the weights and priority levels are not bounded independently from the data), a Δ2P lower bound has been shown for P-CQA, P-intersection and P-brave semantics (hence transfers to w-optimal repair-based semantics) in DL-Litecore [44, Prop. 6.2.4 and 6.2.9] and the ontology used in the reductions uses only NCs. For FD, we use a reduction from the following Δ2P-hard problem [96]: given a satisfiable CNF formula φ=c1cm over variables x1,,xn, decide whether the lexicographically maximum truth assignment ν𝗆𝖺𝗑 satisfying φ with respect to (x1,,xn) is such that ν𝗆𝖺𝗑(xn)=1. Define 𝒦=𝒟,𝒯 and a prioritization P=𝒫1,,𝒫n+1 as follows:

𝒯={ R(x1,x2,x3)R(y1,y2,y3)x1=y1x2=y2,
R(x1,x2,x3)R(y1,y2,y3)x2=y2x3=y3}
𝒟= 𝒫1𝒫n+1 with
𝒫1={ R(cj,xi,1)xicj,1jm}{R(cj,xi,0)¬xicj,1jm}
𝒫i+1={ R(xi,xi,1)} for 1in

We can show that R(xn,xn,1) is entailed under P-CQA (resp. P-intersection, P-brave) semantics iff ν𝗆𝖺𝗑(xn)=1. Indeed, since φ is satisfiable, for each satisfying valuation ν, we can obtain a 𝒯-consistent subset of m facts from 𝒫1 by selecting exactly one fact of the form R(cj,xi,ν(xi)) per cj and complete it into a (standard) repair by adding all R(xi,xi,1) such that no fact of the form R(cj,xi,0) has been selected. Since it is not possible to keep more than m facts from 𝒫1 because of the first FD, and each other 𝒫i contains a single fact, the P-repairs all contain the same set of facts from i=1n𝒫i+1 and these facts correspond to the xi set to 1 by ν𝗆𝖺𝗑.

6.2.3 Comments and additional results

When looking at Tables 7 and 7, we can distinguish three kinds of preferred repairs depending on their impact on the data complexity:

  • Those for which the complexity of repair checking and BCQ entailment under CQA is the same as in the case of standard repairs (P-, Pareto- and completion-optimal). Intuitively, these preferred repairs correspond to some “local” preference, so that given a repair, we can decide whether it is a preferred repair without guessing or computing another preferred repair. Note that the complexity of intersection and brave semantics nevertheless increases for the cases where it was in 𝖠𝖢0 for standard repairs.

  • Those for which the complexity of repair checking and BCQ entailment under CQA increases to coNP-complete and Δ2P- or Θ2P-complete (-, w-, P-optimal and Π-preferred). Intuitively, for these kinds of preferred repairs, we can precompute the value of a global parameter (such as the weight of the w-optimal repairs or the number of preference rules satisfied by Π-preferred repairs) that allows us to check efficiently that a 𝒯-consistent subset of 𝒟 is a preferred repair.

  • Those for which the complexity of repair checking and BCQ entailment under CQA jumps to coNP-complete and Π2P-complete (globally-optimal and Π-preferred). Intuitively, for these kinds of preferred repairs, there is no better option than relying on the naïve guess-and-check algorithm to determine whether a repair is a preferred repair.

We conclude this section by mentioning various other complexity results for reasoning under CQA, intersection and brave semantics using preferred repairs.

Combined complexity.

The combined complexity of BCQ entailment under CQA and intersection semantics based on -optimal repairs over Datalog± KBs have been studied for {,w,P,P} and shown to coincide with the standard repair case for all fragments of Datalog± we consider (cf. [108, Tables 2 and 3] for and [107, Tables 4, 5, 6, 7] for w, P and P). Intuitively, this is because the combined complexity of BCQ entailment under these semantics is already very high when using standard repairs. In contrast, for DL-LiteR, the combined complexity of CQA does not change (Π2P-complete) but the one of intersection semantics increases from NP-complete to Θ2P or Δ2P when -, P-, w- or P-optimal repairs are used [33, Figure 1], and the one of brave semantics increases similarly when using -, w- or P-optimal repairs (but remains NP-complete in the case of P-optimal repairs) [44, Table 6.1]. Note that this difference between CQA and intersection or brave in combined complexity contrasts with the data complexity where CQA and intersection have the same complexity and brave is complete for the complement class.

Preferred repairs for more expressive DLs.

It has been shown that fact entailment over 𝒮𝒬 KBs under w-CQA semantics is Θ2P-complete when the input size is measured by the number of facts in 𝒟 (hence assuming a data-independent bound on the weights) [73]. We can extend this result and obtain Δ2P-complete (resp. Θ2P-complete when the weights are bounded) data complexity for BCQ entailment under w-CQA, as well as under w-intersection (extended as usual to P and ). The lower bounds are inherited from DL-Litecore and the upper bounds follow from Algorithms 11 and 13. Indeed, since consistency checking in 𝒮𝒬 is in NP, an NP-oracle can decide whether there exists a 𝒯-consistent subset of 𝒟 of at least a given weight by guessing the certificate of the 𝒯-consistency of together with , and similarly, since BCQ entailment is in coNP, the oracle can guess the certificate that ,𝒯⊧̸q (resp. 𝒟,𝒯⊧̸q) together with (resp. and the 1,,n) and the 𝒯-consistency certificate(s).

Preferred 𝚫-repairs of databases with universal constraints.

The data complexity of reasoning with optimal repairs based on a priority relation has been studied in the case of databases with UCs: in this case, using P-optimal, Pareto-optimal, completion-optimal or globally-optimal repairs instead of standard Δ-repairs does not increase the data complexity of BCQ entailment under CQA, intersection and brave semantics, which remains Π2P/Σ2P-complete (cf. Table 5) [32, Theorem 3]. For -optimal repairs, the data complexity actually decreases: it is Θ2P-complete [74, Theorem 4]. The lower bound comes from the FD case and the upper bound follows from the fact that we can pre-compute by binary search the minimal size of the symmetric difference between a Δ-repair and 𝒟, then use it to check in P whether a subset of 𝐹𝑎𝑐𝑡𝑠𝒟𝒯 is a -optimal Δ-repair.

Optimal repairs based on a transitive priority relation.

In the case of repairs based on a priority relation , it has been shown (for DL-Litecore and NCs) that all lower bounds given in Table 7 hold even in the case where is assumed to be transitive [30, Theorem 14] (while transitivity decreases the complexity of deciding whether there is a unique globally-optimal repair [92, Corollary 7.7]).

7 Implementations of (preferred) repair-based semantics

Table 8: Overview of implementations of (preferred) repair-based semantics. X-Sem stands for semantics Sem based on repairs from X-𝑅𝑒𝑝(𝒦). Recall that a system that supports w-Sem also supports -Sem, and that a system that supports P- or C-Sem also supports P-Sem. We focus on (preferred) repair-based semantics (cf. Section 4.1) and omit here the alternative semantics implemented in some systems.
semantics input supported main techniques
[37] X-CQA/X-inter./X-brave 𝒟, metadata, pref. rules, ASP
(2025) for X{S,P,C} DCs, UCQ
𝖮𝖱𝖡𝖨𝖳𝖲 [31] X-CQA/X-inter./X-brave binary 𝐶𝑜𝑛𝑓(𝒦), , SAT + poly. approx.
(2022) for X{S,P,C} pot. answers + causes
𝖢𝖰𝖠𝖯𝗋𝗂 [33, 35] X-CQA/X-inter./X-brave 𝒟 (possibly with P), SAT + poly. approx.
(2014) for X{S,P} DL-LiteR onto., CQ
[73] w-CQA 𝒟, w, 𝒮𝒬 onto., SAT
(2013) CQ without
[74] -CQA 𝒟, UCs, SAT
(2010) CQ
[133] S-inter. 𝒟, dr onto. (disj.) Datalog¬ rew.
(2018) (with restr.), CQ
𝖲𝖺𝖰𝖠𝖨 [134] S-inter. 𝒟, DL-LiteR onto., comp. S-𝑅𝑒𝑝(𝒦)
(2016) CQ
𝖰𝗎𝖨𝖣 [127, 99] S-inter. 𝒟, DL-LiteA onto., FO rewriting
(2012) CQ annot. with 𝐶𝑜𝑛𝑓(𝒦)
comp. S-𝑅𝑒𝑝(𝒦)
𝖢𝖠𝗏𝖲𝖠𝖳 [71, 72] S-CQA 𝒟, DCs, SAT + poly. approx.
(2019) CQ SQL rewriting
𝖤𝖰𝖴𝖨𝖯 [95] S-CQA 𝒟, keys, BIP + poly. approx.
(2013) CQ
[86, 87, 77, 117] S-CQA 𝒟, keys to UCs, logic programing
[114, 115](2001-15) CQ to UCQ¬
𝖧𝗂𝗉𝗉𝗈 [64, 65] S-CQA 𝒟, DCs, indep. set of 𝐶𝑜𝑛𝑓(𝒦)
(2004) UCQ without
𝖫𝗂𝗇𝖢𝖰𝖠 [79] S-CQA 𝒟, keys, SQL rewriting
(2023) FO rew. CQ non-rec. Datalog¬ rew.
𝖢𝗈𝗇𝗊𝗎𝖾𝗌𝗍𝗈 [91] S-CQA 𝒟, keys, non-rec. Datalog¬ rew.
(2020) FO rew. CQ
𝖢𝗈𝗇𝗊𝗎𝖾𝗋 [82, 83] S-CQA 𝒟, keys, SQL rewriting
(2005) FO rew. CQ annot. with 𝐶𝑜𝑛𝑓(𝒦)

Table 8 provides a (partial) overview of the systems that have been implemented for answering queries under (preferred) repair-based semantics. They are divided in four groups, based on the semantics they support:

  • the systems of the first group target CQA, intersection and brave semantics with both standard and preferred repairs based on priority (P-, Pareto- and completion-optimal);

  • the second group consists of implementations of w- and/or -CQA for expressive DLs or database constraints;

  • the systems of the third group implement (plain) intersection semantics for DL KBs;

  • the last group consists of systems that implement (plain) CQA for databases.

Most of the systems in this last group further fall into two categories: approaches that handle general CQs and potentially expressive ICs and rely on solvers (e.g., SAT, Binary Integer Programming (BIP), Answer Set Programming (ASP)), and those that impose strong restrictions on the setting (key constraints and restriction to some classes of CQs) to ensure that CQA is FO rewritable and apply rewriting techniques. Indeed, the database community conducted an extensive study of the complexity of BCQ entailment under CQA with key constraints for different kinds of CQ, which is out of the scope of these lecture notes.

In the remainder of the section, we illustrate the prominent approach of CQA relying on solvers by presenting some SAT encodings for CQA based on standard or Pareto-optimal repairs, then give a few details on the approaches to tractable semantics and approximations.

7.1 Examples of encodings for CQA

When encoding BCQ entailment under some intractable semantics into SAT, BIP, or ASP, it is crucial to produce encodings that are small enough to be handled efficiently. Localization techniques have been considered since the early implementations based on logic programing (see e.g., [77]). In this section, we present some examples of SAT encodings for CQA semantics using standard or Pareto-optimal repairs (applicable to P-optimal repairs) that have been proposed for cases where the conflicts and minimal 𝒯-consistent subsets of the dataset that support the query can be efficiently computed (in polynomial time w.r.t. data complexity), such as DL-Lite, 𝖫, 𝖠, or 𝖲 KBs, or databases with DCs. Indeed, most of the recent implementations of CQA that handle unrestricted CQs and relatively expressive constraints use encodings based on these sets [95, 33, 71, 31, 37]. Several variants of such encodings have been proposed. In particular, we can treat each candidate answer separately, reducing each entailment to an instance of (here) SAT, or use the same encoding to handle all potential answers, and rely on some optimization variant (e.g., weighted MaxSAT), or incremental solving. We refer the interested reader to [31] for a comparison of different SAT encodings and different reasoning modes of SAT solvers. The encodings we present next are used by 𝖢𝖰𝖠𝖯𝗋𝗂 [33] and implemented among others by 𝖮𝖱𝖡𝖨𝖳𝖲 [31] (restricted to the case of binary conflicts, which simplifies the encodings). An ASP version of these encodings (for the general case where conflicts may not be binary) has also recently been implemented [37].

Given a KB or database 𝒦=𝒟,𝒯, a CQ q(x), and a tuple a, a cause for q(a) in 𝒦 is a -minimal 𝒯-consistent subset 𝒞 of 𝒟 such that 𝒞,𝒯q(a). We denote by 𝐶𝑎𝑢𝑠𝑒𝑠(q(a),𝒦) the set of all causes for q(a) in 𝒦. Recall from Sections 3.3 and 5.2.2 that given a prioritized KB or database 𝒦=(𝒦,) we have the following notation (attack relations of the SETAF corresponding to 𝒦 and of the PSETAF corresponding to 𝒦, respectively):

  • 𝒦α iff {α}𝐶𝑜𝑛𝑓(𝒦) and α;

  • α iff 𝒦α and αβ for every β.

The propositional formula Φ𝖢𝖰𝖠(q(a)) is satisfiable iff a is not an answer to q(x) over 𝒦 under the CQA semantics.

Φ𝖢𝖰𝖠(q(a))=(𝒞𝐶𝑎𝑢𝑠𝑒𝑠(q(a),𝒦)φ¬𝒞)φ𝖼𝗈𝗇𝗌(F) where
φ¬𝒞=(α𝒞,𝒦αx)α𝒞,𝒦α,β¬xxβ and φ𝖼𝗈𝗇𝗌(F)=αF,𝒦α(¬xαβ¬xβ)

and F={βxβ occurs in 𝒞𝐶𝑎𝑢𝑠𝑒𝑠(q(a),𝒦)φ¬𝒞}. Intuitively, the set of facts β such that xβ is assigned to true by a satisfying valuation for Φ𝖢𝖰𝖠(q(a)) is 𝒯-consistent and contradicts every cause for q(a) in 𝒦, hence can be extended into a repair of 𝒦 that does not entail q(a). Indeed, for each cause 𝒞 of q(a) in 𝒦, φ¬𝒞 ensures that we choose some α𝒞 and some such that {α}𝐶𝑜𝑛𝑓(𝒦), and select all facts from , and φ𝖼𝗈𝗇𝗌(F) ensures that the set of selected facts is 𝒯-consistent.

To use Pareto-optimal repairs instead of standard ones, it suffices to slightly modify φ¬𝒞 to take into account the priority relation and to add an additional component φ𝖯-𝗆𝖺𝗑(F) that ensures that the selected facts can be extended into a Pareto-optimal repair by stating that a relevant fact α can only be omitted if we include a contradicting set of facts that are not dominated by α. The propositional formula Φ𝖯-𝖢𝖰𝖠(q(a)) is satisfiable iff a is not an answer to q(x) over 𝒦 under the CQA semantics based on Pareto-optimal repairs.

Φ𝖯-𝖢𝖰𝖠(q(a))=(𝒞𝐶𝑎𝑢𝑠𝑒𝑠(q(a),𝒦)φ¬𝒞)φ𝖯-𝗆𝖺𝗑(F)φ𝖼𝗈𝗇𝗌(F) where
φ¬𝒞=(α𝒞,αx)α𝒞,α,β¬xxβ and 
φ𝖯-𝗆𝖺𝗑(F)=α𝖱(F)(xααx)α𝖱(F),α,β¬xxβ

F={βxβ occurs in 𝒞𝐶𝑎𝑢𝑠𝑒𝑠(q(a),𝒦)φ¬𝒞}, F={βxβ occurs in φ𝖯-𝗆𝖺𝗑(F)}, and 𝖱(F) is the set of facts reachable from F in the following sense: β is reachable from F if βF or if there exists γ reachable from F and such that β and γ.

Example 90.

Recall the KB 𝒦 from Examples 15, 51 and 59, whose conflict hypergraph, priority relation and Pareto-optimal repairs are recalled below, and let q(x)=B(x).

The only cause for q(a) is 𝒞={B(a)} and the SAT encodings to decide whether q(a) holds under CQA based on standard and Pareto-optimal repairs, respectively, are as follows (for readability we write A,B,C,D,E instead of A(a),B(a),C(a),D(a),E(a) in indexes).

Φ𝖢𝖰𝖠(q(a))= x{A,C}(¬x{A,C}xA)(¬x{A,C}xC)
(¬xA¬xB¬xC)
Φ𝖯-𝖢𝖰𝖠(q(a))= x{A,C}(¬x{A,C}xA)(¬x{A,C}xC)
(xAx{B,C})(¬x{B,C}xB)(¬x{B,C}xC)
(xBx{A,C})(¬x{A,C}xA)(¬x{A,C}xC)
(xCx{E})(¬x{E}xE)
(xDx{A}x{E})(¬x{A}xA)(¬x{E}xE)
(xEx{D})(¬x{D}xD)
(¬xA¬xB¬xC)(¬xA¬xD)(¬xC¬xE)(¬xD¬xE)

Φ𝖢𝖰𝖠(q(a)) is satisfiable (assign x{A,C}, xA and xC to true and xB to false), and indeed q(a) is not entailed under CQA based on standard repairs because of 2. On the other hand, q(a) holds under P-CQA and Φ𝖯-𝖢𝖰𝖠(q(a)) is indeed unsatisfiable: to satisfy φ¬𝒞 (first line), we need to assign xA and xC to true, which implies that xD and xE are assigned to false to satisfy φ𝖼𝗈𝗇𝗌(F) (last line), but assigning xE to false implies that xD must be assigned to true to satisfy (xEx{D})(¬x{D}xD). Note that Φ𝖯-𝖢𝖰𝖠(q(a)) is much bigger than Φ𝖢𝖰𝖠(q(a)): this is because we need to take into account all facts reachable from A(a) and C(a) to ensure Pareto-optimality. However, in practice, the size of both kinds of encodings remains typically much smaller than the dataset size.

7.2 Tractable semantics and approximations

Several methods have been proposed for tractable semantics, in particular for the intersection semantics and languages for which CQ answering is UCQ-rewritable. Indeed, UCQ-rewritability ensures that the size of the conflicts and causes can be bounded independently from the dataset, hence that CQ answering under intersection semantics is FO-rewritable (cf. Proposition 83 and Corollary 84). The methods for intersection semantics in this tractable case fall into two categories:

  • Data-independent rewritings: compute φ𝒯,q such that for every 𝒟, q is entailed by 𝒟,𝒯 under intersection iff 𝒟φ𝒯,q. For example, if we extend the ontology of Example 15 with BQ and EQ and consider the query q(x)=Q(x), an FO-rewriting of q(x) w.r.t. 𝒯 is φ𝒯,q(x)=Q(x)(B(x)¬A(x))(B(x)¬C(x))(E(x)¬C(x)¬D(x)).

  • Methods based on the computation of 𝐶𝑜𝑛𝑓(𝒦), which can be computed in polynomial time w.r.t. data complexity and used in different manners:

    • evaluate the queries on ,𝒯 where =S-𝑅𝑒𝑝(𝒦)=𝒟𝒞𝐶𝑜𝑛𝑓(𝒦)𝒞;

    • annotate the facts in 𝒟 that belong to some conflicts and rewrite the queries to ignore the annotated facts;

    • compute the query causes in polynomial time w.r.t. data complexity and check whether some cause is such that none of its fact belongs to some conflict.

Many systems that implement intractable semantics use tractable approximations to reserve the use of solvers for the complex cases. For example, when computing answers to a query under CQA semantics (based on standard repairs) 𝖤𝖰𝖴𝖨𝖯, 𝖢𝖰𝖠𝖯𝗋𝗂, 𝖢𝖠𝗏𝖲𝖠𝖳 and 𝖮𝖱𝖡𝖨𝖳𝖲 all use the intersection semantics to get a subset of the answers that hold under CQA in polynomial time, before checking whether the other potential answers hold via translation to BIP or SAT. Even in the case of preferred repairs, for which all semantics are intractable, 𝖢𝖰𝖠𝖯𝗋𝗂 and 𝖮𝖱𝖡𝖨𝖳𝖲 use as a tractable under-approximation of Pareto- or completion-optimal repair-based intersection (hence also of CQA and brave) semantics the set of answers that have some cause 𝒞 such that for every α𝒞, there is no α.

8 Summary and outlook

We have seen that many inconsistency-tolerant semantics have been proposed to handle inconsistent databases or knowledge bases, most of them being based on repairs, and surveyed the different kinds of preferred repairs that can be used to obtain more accurate answers when some preference information is available. We presented the properties of these preferred repairs, their relationships and how they relate to other formalisms for inconsistency handling (such as abstract argumentation). We also summarized some results on the computational complexity of reasoning with (preferred) repairs and gave a brief overview of existing implementations. We conclude these lecture notes by mentioning some recent related work on repair-based semantics and research directions.

Extensions of repair-based semantics to new settings.

Repairs, CQA, brave and intersection semantics have been defined for RDF graphs that do not validate a set of SHACL (Shapes Constraint Language) constraints [5, 6]. SHACL is related to DLs but makes the closed-world assumption. In this case, a repair is obtained by deleting some facts and/or adding some facts from a given set of hypotheses. Both subset-minimal and cardinality-minimal repairs, corresponding to Δ- and -optimal Δ-repairs, have been considered. Repairs and CQA have also been studied in the related setting of graph databases [21, 3], and preferred repairs (based on weights or on a partial order over the set of edge labels and data values) have started to be considered in this context [2]. Another relevant setting is that of temporal databases or KBs [66, 45, 38], which includes a large number of frameworks, since the dataset facts may be annotated with time points or time intervals, the constraints may be atemporal or temporal (including rigid predicates whose interpretation is required not to change over time), and several temporal query languages have been designed. Several definitions of repair have been proposed in these contexts. When facts are annotated with time points and constraints are atemporal, we can repair each snapshot individually, possibly taking into account predicate rigidity [45], or use a more global approach to favor fact persistence (so that, e.g., two identical consecutive snapshots are repaired in the same way) [66]. When time intervals and temporal constraints are used, three notions of repair have been defined, based upon deleting whole facts, seing intervals as sets of time points and deleting punctual facts, or minimally shrinking the time intervals of facts [38]. Finally, CQA has recently been extended to databases whose facts are annotated with values from a naturally ordered positive semiring [94]. In this setting, the answer to a Boolean query is a semiring value, and the consistent answer of such query is defined as the minimum of the semiring values that the query takes over all repairs.

Reasoning tasks beyond query answering.

The question of explaining the result of a query attracted a lot of attention, both in the database and KB settings, and is all the more crucial when dealing with repair-based semantics, since an answer can be true under a given semantics and not under another one. Some work in this direction has been conducted for DL and Datalog± KBs, with explanations defined as (sets of) subsets of the dataset [34, 35, 105, 106]. Preferences among these explanations (smallest explanations…) have also been considered. Research effort is still needed to make such data-centric explanations more understandable, e.g., by relating them to the ontology and presenting them in a concise way. Moreover, while the existing definitions of explanations could be straightforwardly extended to preferred repair-based semantics, they would probably not be useful to understand the query result by themselves. For example, a cause is an explanation for query entailment under the brave semantics, but while in the case of standard repairs, every cause can be extended to a repair, we would need to explain why a cause belongs to some preferred repair to justify entailment under preferred repair-based brave semantics. Another related reasoning task that attracted some attention in the context of inconsistent KBs is that of abduction, i.e., the task of minimally extending the dataset so that some query is entailed under intersection semantics [75].

References

  • [1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
  • [2] Sergio Abriola, Santiago Cifuentes, Nina Pardal, and Edwin Pin Baque. Data-graph repairs: the preferred approach. In Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW), 2023.
  • [3] Sergio Abriola, María Vanina Martínez, Nina Pardal, Santiago Cifuentes, and Edwin Pin Baque. On the complexity of finding set repairs for data-graphs. Journal of Artificial Intelligence Research (JAIR), 76:721–759, 2023. doi:10.1613/JAIR.1.13994.
  • [4] Foto N. Afrati and Phokion G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In Proceedings of the 12th International Conference on Database Theory (ICDT), 2009.
  • [5] Shqiponja Ahmetaj, Robert David, Magdalena Ortiz, Axel Polleres, Bojken Shehu, and Mantas Simkus. Reasoning about explanations for non-validation in SHACL. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2021.
  • [6] Shqiponja Ahmetaj, Timo Camillo Merkl, and Reinhard Pichler. Consistent query answering over SHACL constraints. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR), 2024.
  • [7] Leila Amgoud and Claudette Cayrol. Inferring from inconsistency in preference-based argumentation frameworks. Journal of Automated Reasoning (JAR), 29(2):125–169, 2002. doi:10.1023/A:1021603608656.
  • [8] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In Proceedings of the 18th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 1999.
  • [9] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Answer sets for consistent query answering in inconsistent databases. Theory and Practice of Logic Programming (TPLP), 3(4-5):393–424, 2003. doi:10.1017/S1471068403001832.
  • [10] Abdallah Arioua, Madalina Croitoru, and Srdjan Vesic. Logic-based argumentation with existential rules. International Journal of Approximate Reasoning, 90:76–106, 2017. doi:10.1016/J.IJAR.2017.07.004.
  • [11] Sebastian Arming, Reinhard Pichler, and Emanuel Sallinger. Complexity of repair checking and consistent query answering. In Proceedings of the 19th International Conference on Database Theory (ICDT), 2016.
  • [12] Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev. The DL-Lite family and relations. Journal of Artificial Intelligence Research (JAIR), 36:1–69, 2009. doi:10.1613/JAIR.2820.
  • [13] Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the envelope. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), 2005.
  • [14] Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003.
  • [15] Franz Baader, Patrick Koopmann, and Francesco Kriegel. Optimal repairs in the description logic revisited. In Proceedings of the 18th European Conference on Logics in Artificial Intelligence (JELIA), 2023.
  • [16] Franz Baader, Patrick Koopmann, Francesco Kriegel, and Adrian Nuradiansyah. Computing optimal repairs of quantified ABoxes w.r.t. static TBoxes. In Proceedings of the 28th International Conference on Automated Deduction (CADE), 2021.
  • [17] Franz Baader and Francesco Kriegel. Pushing optimal ABox repair from towards more expressive Horn-DLs. In Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2022.
  • [18] Franz Baader, Francesco Kriegel, and Adrian Nuradiansyah. Inconsistency- and error-tolerant reasoning w.r.t. optimal repairs of ontologies. In Proceedings of the 13th International Symposium on Foundations of Information and Knowledge Systems (FoIKS), 2024.
  • [19] Jean-François Baget, Salem Benferhat, Zied Bouraoui, Madalina Croitoru, Marie-Laure Mugnier, Odile Papini, Swan Rocher, and Karim Tabia. A general modifier-based framework for inconsistency-tolerant query answering. In Proceedings of the 15th International Conference Principles of Knowledge Representation and Reasoning (KR), 2016.
  • [20] Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with existential variables: Walking the decidability line. Artificial Intelligence (AIJ), 175(9-10):1620–1654, 2011. doi:10.1016/J.ARTINT.2011.03.002.
  • [21] Pablo Barceló, Gaëlle Fontaine, Sylvain Salvati, and Sophie Tison. Corrections to "On the data complexity of consistent query answering over graph databases [Journal of Computer and System Sciences 88 (2017) 164-194]". Journal of Computer and System Sciences, 155:103694, 2026. doi:10.1016/J.JCSS.2025.103694.
  • [22] Sihem Belabbes, Salem Benferhat, and Jan Chomicki. Handling inconsistency in partially preordered ontologies: the Elect method. Journal of Logic and Computation, 31(5):1356–1388, 2021. doi:10.1093/LOGCOM/EXAB024.
  • [23] Salem Benferhat, Zied Bouraoui, Madalina Croitoru, Odile Papini, and Karim Tabia. Non-objection inference for inconsistency-tolerant query answering. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016.
  • [24] Salem Benferhat, Zied Bouraoui, and Karim Tabia. How to select one preferred assertional-based repair from inconsistent and prioritized DL-Lite knowledge bases? In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015.
  • [25] Leopoldo E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. doi:10.2200/S00379ED1V01Y201108DTM020.
  • [26] Leopoldo E. Bertossi. Database repairs and consistent query answering: Origins and further developments. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2019.
  • [27] Meghyn Bienvenu. On the complexity of consistent query answering in the presence of simple ontologies. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), 2012.
  • [28] Meghyn Bienvenu. A short survey on inconsistency handling in ontology-mediated query answering. Künstliche Intelligenz, 34(4):443–451, 2020. doi:10.1007/S13218-020-00680-9.
  • [29] Meghyn Bienvenu and Camille Bourgaux. Inconsistency-tolerant querying of description logic knowledge bases. In Tutorial Lectures of the 12th International Reasoning Web Summer School (RW), 2016.
  • [30] Meghyn Bienvenu and Camille Bourgaux. Querying and repairing inconsistent prioritized knowledge bases: Complexity analysis and links with abstract argumentation. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2020.
  • [31] Meghyn Bienvenu and Camille Bourgaux. Querying inconsistent prioritized data with ORBITS: Algorithms, implementation, and experiments. In Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2022.
  • [32] Meghyn Bienvenu and Camille Bourgaux. Inconsistency handling in prioritized databases with universal constraints: Complexity analysis and links with active integrity constraints. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2023.
  • [33] Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Querying inconsistent description logic knowledge bases under preferred repair semantics. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), 2014.
  • [34] Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Explaining inconsistency-tolerant query answering over description logic knowledge bases. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 2016.
  • [35] Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Computing and explaining query answers over inconsistent DL-Lite knowledge bases. Journal of Artificial Intelligence Research (JAIR), 64:563–644, 2019. doi:10.1613/JAIR.1.11395.
  • [36] Meghyn Bienvenu, Camille Bourgaux, and Robin Jean. Cost-based semantics for querying inconsistent weighted knowledge bases. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR), 2024.
  • [37] Meghyn Bienvenu, Camille Bourgaux, and Robin Jean. A rule-based approach to specifying preferences over conflicting facts and querying inconsistent knowledge bases. In Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR), 2025.
  • [38] Meghyn Bienvenu, Camille Bourgaux, and Atefe Khodadaditaghanaki. Inconsistency handling in DatalogMTL. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), 2025.
  • [39] Meghyn Bienvenu and Pierre Bourhis. Mixed-world reasoning with existential rules under active-domain semantics. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019.
  • [40] Meghyn Bienvenu and Magdalena Ortiz. Ontology-mediated query answering with data-tractable description logics. In Tutorial Lectures of the 11th Reasoning Web International Summer School (RW), 2015.
  • [41] Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of consistent query answering for robust ontology-based data access. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2013.
  • [42] Bart Bogaerts and Luís Cruz-Filipe. Fixpoint semantics for active integrity constraints. Artificial Intelligence (AIJ), 255:43–70, 2018. doi:10.1016/J.ARTINT.2017.11.003.
  • [43] Philip Bohannon, Michael Flaster, Wenfei Fan, and Rajeev Rastogi. A cost-based model and effective heuristic for repairing constraints by value modification. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2005.
  • [44] Camille Bourgaux. Inconsistency handling in ontology-mediated query answering. (Gestion des incohérences pour l’accès aux données en présence d’ontologies). PhD thesis, University of Paris-Saclay, France, 2016. URL: https://tel.archives-ouvertes.fr/tel-01378723.
  • [45] Camille Bourgaux, Patrick Koopmann, and Anni-Yasmin Turhan. Ontology-mediated query answering over temporal and inconsistent data. Semantic Web, 10(3):475–521, 2019. doi:10.3233/SW-180337.
  • [46] Gerhard Brewka, Ilkka Niemelä, and Miroslaw Truszczynski. Answer set optimization. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), 2003.
  • [47] Samuel R. Buss and Louise Hay. On truth-table reducibility to SAT. Information and Computation, 91(1):86–102, 1991. doi:10.1016/0890-5401(91)90075-D.
  • [48] Marco Calautti, Marco Console, and Andreas Pieris. Counting database repairs under primary keys revisited. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2019.
  • [49] Marco Calautti, Marco Console, and Andreas Pieris. Benchmarking approximate consistent query answering. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2021.
  • [50] Marco Calautti, Sergio Greco, Cristian Molinaro, and Irina Trubitsyna. Preference-based inconsistency-tolerant query answering under existential rules. Artificial Intelligence (AIJ), 312:103772, 2022. doi:10.1016/J.ARTINT.2022.103772.
  • [51] Marco Calautti, Leonid Libkin, and Andreas Pieris. An operational approach to consistent query answering. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018.
  • [52] Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. Counting database repairs entailing a query: The case of functional dependencies. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2022.
  • [53] Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. Combined approximations for uniform operational consistent query answering. Proceedings of the ACM on Management of Data (PACMMOD), 2(2):99, 2024. doi:10.1145/3651600.
  • [54] Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering under expressive relational constraints. Journal of Artificial Intelligence Research (JAIR), 48:115–174, 2013. doi:10.1613/JAIR.3873.
  • [55] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. Datalog extensions for tractable query answering over ontologies. In Semantic Web Information Management - A Model-Based Perspective, pages 249–279. 2009. doi:10.1007/978-3-642-04329-1_12.
  • [56] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. Journal of Web Semantics, 14:57–83, 2012. doi:10.1016/J.WEBSEM.2012.03.001.
  • [57] Andrea Calì, Georg Gottlob, and Andreas Pieris. Towards more expressive ontology languages: The query answering problem. Artificial Intelligence (AIJ), 193:87–128, 2012. doi:10.1016/J.ARTINT.2012.08.002.
  • [58] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of Automated Reasoning (JAR), 2007.
  • [59] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Data complexity of query answering in description logics. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2006.
  • [60] Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi. Database repairing with soft functional dependencies. ACM Transactions on Database Systems, 49(2):8:1–8:34, 2024. doi:10.1145/3651156.
  • [61] Luciano Caroprese, Sergio Greco, and Ester Zumpano. Active integrity constraints for database consistency maintenance. IEEE Transactions on Knowledge and Data Engineering, 21(7):1042–1058, 2009. doi:10.1109/TKDE.2008.226.
  • [62] Luciano Caroprese and Miroslaw Truszczynski. Active integrity constraints and revision programming. Theory and Practice of Logic Programming (TPLP), 11(6):905–952, 2011. doi:10.1017/S1471068410000475.
  • [63] Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), 1977.
  • [64] Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. Computing consistent query answers using conflict hypergraphs. In Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM), 2004.
  • [65] Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. Hippo: A system for computing consistent answers to a class of SQL queries. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT), 2004.
  • [66] Jan Chomicki and Jef Wijsen. Consistent query answering for atemporal constraints over temporal databases. In Proceedings of the 23rd International Symposium on Temporal Representation and Reasoning (TIME), 2016.
  • [67] Madalina Croitoru and Srdjan Vesic. What can argumentation do for inconsistent ontology query answering? In Proceedings of the 7th International Conference on Scalable Uncertainty Management (SUM), 2013.
  • [68] Luís Cruz-Filipe. Grounded fixpoints and active integrity constraints. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP), 2016.
  • [69] Luís Cruz-Filipe, Graça Gaspar, Patrícia Engrácia, and Isabel Nunes. Computing repairs from active integrity constraints. In Proceedings of the 7th International Symposium on Theoretical Aspects of Software Engineering (TASE), 2013.
  • [70] Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374–425, 2001. doi:10.1145/502807.502810.
  • [71] Akhil A. Dixit and Phokion G. Kolaitis. A SAT-based system for consistent query answering. In Proceedings of the 22nd International Conference on Theory and Applications of Satisfiability Testing (SAT), 2019.
  • [72] Akhil A. Dixit and Phokion G. Kolaitis. CAvSAT: Answering aggregation queries over inconsistent databases via SAT solving. In Proceedings of the International Conference on Management of Data (SIGMOD), 2021.
  • [73] Jianfeng Du, Guilin Qi, and Yi-Dong Shen. Weight-based consistent query answering over inconsistent 𝒮𝒬 knowledge bases. Knowledge and Information Systems, 34(2):335–371, 2013.
  • [74] Jianfeng Du, Yi-Dong Shen, and Guilin Qi. Decomposition-based consistent query answering in databases with universal constraints under cardinality-based semantics. In Proceedings of the International Conference on Computational Intelligence and Software Engineering (CISE), 2010.
  • [75] Jianfeng Du, Kewen Wang, and Yi-Dong Shen. Towards tractable and practical ABox abduction over inconsistent description logic ontologies. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), 2015.
  • [76] Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence (AIJ), 77(2):321–358, 1995. doi:10.1016/0004-3702(94)00041-X.
  • [77] Thomas Eiter, Michael Fink, Gianluigi Greco, and Domenico Lembo. Repair localization for query answering from inconsistent databases. ACM Transactions on Database Systems, 33(2):10:1–10:51, 2008. doi:10.1145/1366102.1366107.
  • [78] Thomas Eiter, Thomas Lukasiewicz, and Livia Predoiu. Generalized consistent query answering under existential rules. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2016.
  • [79] Zhiwei Fan, Paraschos Koutris, Xiating Ouyang, and Jef Wijsen. LinCQA: Faster consistent query answering with linear time guarantees. Proceedings of the ACM on Management of Data (PACMMOD), 1(1):38:1–38:25, 2023. doi:10.1145/3588718.
  • [80] Sergio Flesca, Sergio Greco, and Ester Zumpano. Active integrity constraints. In Proceedings of the 6th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP), 2004.
  • [81] Giorgos Flouris and Antonis Bikakis. A comprehensive study of argumentation frameworks with sets of attacking arguments. International Journal of Approximate Reasoning, 109:55–86, 2019. doi:10.1016/J.IJAR.2019.03.006.
  • [82] Ariel Fuxman, Elham Fazli, and Renée J. Miller. Conquer: Efficient management of inconsistent databases. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), 2005.
  • [83] Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. In Proceedings of the 10th International Conference on Database Theory (ICDT), 2005.
  • [84] Birte Glimm, Carsten Lutz, Ian Horrocks, and Ulrike Sattler. Conjunctive query answering for the description logic 𝒮𝒬. Journal of Artificial Intelligence Research (JAIR), 31:157–204, 2008. doi:10.1613/JAIR.2372.
  • [85] Nikos Gorogiannis and Anthony Hunter. Instantiating abstract argumentation with classical logic arguments: Postulates and properties. Artificial Intelligence (AIJ), 175(9-10):1479–1497, 2011. doi:10.1016/J.ARTINT.2010.12.003.
  • [86] Gianluigi Greco, Sergio Greco, and Ester Zumpano. A logic programming approach to the integration, repairing and querying of inconsistent databases. In Proceedings of the 17th International Conference on Logic Programming (ICLP), 2001.
  • [87] Gianluigi Greco, Sergio Greco, and Ester Zumpano. A logical framework for querying and repairing inconsistent databases. IEEE Transactions on Knowledge and Data Engineering, 15(6):1389–1408, 2003. doi:10.1109/TKDE.2003.1245280.
  • [88] Sergio Greco, Cristian Molinaro, and Irina Trubitsyna. Computing approximate query answers over inconsistent knowledge bases. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018.
  • [89] Lane A. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299–322, 1989. doi:10.1016/0022-0000(89)90025-1.
  • [90] Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Data complexity of reasoning in very expressive description logics. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), 2005.
  • [91] Aziz Amezian El Khalfioui, Jonathan Joertz, Dorian Labeeuw, Gaëtan Staquet, and Jef Wijsen. Optimization of answer set programs for consistent query answering by means of first-order rewriting. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM), 2020.
  • [92] Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. Detecting ambiguity in prioritized database repairing. In Proceedings of the 20th International Conference on Database Theory (ICDT), 2017.
  • [93] Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. Counting and enumerating preferred database repairs. Theoretical Computer Science, 837:115–157, 2020. doi:10.1016/J.TCS.2020.05.016.
  • [94] Phokion G. Kolaitis, Nina Pardal, Jonni Virtema, and Jef Wijsen. Rewriting consistent answers on annotated data. Proceedings of the ACM on Management of Data (PACMMOD), 3(2):110:1–110:26, 2025. doi:10.1145/3725247.
  • [95] Phokion G. Kolaitis, Enela Pema, and Wang-Chiew Tan. Efficient querying of inconsistent databases with binary integer programming. Proceedings of the VLDB Endowment, 6(6):397–408, 2013. doi:10.14778/2536336.2536341.
  • [96] Mark W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490–509, 1988. doi:10.1016/0022-0000(88)90039-6.
  • [97] Ahmed Laouar, Sihem Belabbes, and Salem Benferhat. Tractable closure-based possibilistic repair for partially ordered DL-Lite ontologies. In Proceedings of the 18th European Conference Logics in Artificial Intelligence (JELIA), 2023.
  • [98] Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant semantics for description logics. In Proceedings of the 4th International Conference on Web Reasoning and Rule Systems (RR), 2010.
  • [99] Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant query answering in ontology-based data access. Journal of Web Semantics, 33:3–29, 2015. doi:10.1016/J.WEBSEM.2015.04.002.
  • [100] Ester Livshits, Benny Kimelfeld, and Sudeepa Roy. Computing optimal repairs for functional dependencies. ACM Transactions on Database Systems, 45(1):4:1–4:46, 2020. doi:10.1145/3360904.
  • [101] Ester Livshits, Benny Kimelfeld, and Jef Wijsen. Counting subset repairs with functional dependencies. Journal of Computer and System Sciences, 117:154–164, 2021. doi:10.1016/J.JCSS.2020.10.001.
  • [102] Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In Proceedings of the 11th International Conference on Database Theory (ICDT), 2007.
  • [103] Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics (extended version). CoRR, abs/1605.07159, 2016. arXiv:1605.07159.
  • [104] Thomas Lukasiewicz, Enrico Malizia, Maria Vanina Martinez, Cristian Molinaro, Andreas Pieris, and Gerardo I. Simari. Inconsistency-tolerant query answering for existential rules. Artificial Intelligence (AIJ), 307:103685, 2022. doi:10.1016/J.ARTINT.2022.103685.
  • [105] Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro. Explanations for inconsistency-tolerant query answering under existential rules. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020.
  • [106] Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro. Explanations for negative query answers under inconsistency-tolerant semantics. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.
  • [107] Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro. Complexity of inconsistency-tolerant query answering in Datalog+/- under preferred repairs. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2023.
  • [108] Thomas Lukasiewicz, Enrico Malizia, and Andrius Vaicenavicius. Complexity of inconsistency-tolerant query answering in Datalog+/- under cardinality-based repairs. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, (AAAI), 2019.
  • [109] Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari. Inconsistency handling in Datalog+/- ontologies. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI), 2012.
  • [110] Carsten Lutz. The complexity of conjunctive query answering in expressive description logics. In Proceedings of the 4th International Joint Conference on Automated Reasoning, (IJCAR), 2008.
  • [111] Carsten Lutz, Inanç Seylan, and Frank Wolter. Ontology-mediated queries with closed predicates. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015.
  • [112] Yasir Mahmood, Markus Hecher, and Axel-Cyrille Ngonga Ngomo. Dung’s argumentation framework: Unveiling the expressive power with inconsistent databases. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), 2025.
  • [113] Yasir Mahmood, Jonni Virtema, Timon Barlag, and Axel-Cyrille Ngonga Ngomo. Computing repairs under functional and inclusion dependencies via argumentation. In Proceedings of the 13th International Symposium on Foundations of Information and Knowledge Systems (FoIKS), 2024.
  • [114] Marco Manna, Francesco Ricca, and Giorgio Terracina. Consistent query answering via ASP from different perspectives: Theory and practice. Theory and Practice of Logic Programming (TPLP), 13(2):227–252, 2013. doi:10.1017/S1471068411000640.
  • [115] Marco Manna, Francesco Ricca, and Giorgio Terracina. Taming primary key violations to query large inconsistent data via ASP. Theory and Practice of Logic Programming (TPLP), 15(4-5):696–710, 2015. doi:10.1017/S1471068415000320.
  • [116] Lorenzo Marconi and Riccardo Rosati. Consistent query answering over existential rules with open and closed predicates. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), 2025.
  • [117] Mónica Caniupán Marileo and Leopoldo E. Bertossi. The consistency extractor system: Answer set programs for consistent query answering in databases. Data & Knowledge Engineering, 69(6):545–572, 2010. doi:10.1016/J.DATAK.2010.01.005.
  • [118] Dany Maslowski and Jef Wijsen. A dichotomy in the complexity of counting database repairs. Journal of Computer and System Sciences, 79(6):958–983, 2013. doi:10.1016/J.JCSS.2013.01.011.
  • [119] Nhung Ngo, Magdalena Ortiz, and Mantas Simkus. Closed predicates in description logics: Results on combined complexity. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2016.
  • [120] Magdalena Ortiz, Diego Calvanese, and Thomas Eiter. Data complexity of query answering in expressive description logics via tableaux. Journal of Automated Reasoning (JAR), 41(1):61–98, 2008. doi:10.1007/S10817-008-9102-9.
  • [121] W3C OWL Working Group. OWL 2 Web Ontology Language: Document Overview, 2009. Available at http://www.w3.org/TR/owl2-overview/.
  • [122] Horacio Tellez Perez and Jef Wijsen. Generalized weighted repairs. In Proceedings of the 14th International Conference on Flexible Query Answering Systems (FQAS), 2021.
  • [123] Reinhard Pichler and Sebastian Skritek. The complexity of evaluating tuple generating dependencies. In Proceedings of the 14th International Conference on Database Theory (ICDT), 2011.
  • [124] Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati. Linking data to ontologies. Journal of Data Semantics, 10:133–173, 2008. doi:10.1007/978-3-540-77688-8_5.
  • [125] Riccardo Rosati. On conjunctive query answering in . In Proceedings of the International Workshop on Description Logics (DL), 2007.
  • [126] Riccardo Rosati. On the complexity of dealing with inconsistency in description logic ontologies. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 2011.
  • [127] Riccardo Rosati, Marco Ruzzi, Mirko Graziosi, and Giulia Masotti. Evaluation of techniques for inconsistency handling in OWL 2 QL ontologies. In Proceedings of the 11th International Semantic Web Conference (ISWC), 2012.
  • [128] Andrea Schaerf. On the complexity of the instance checking problem in concept languages with existential quantification. Journal of Intelligent Information Systems, 2(3):265–278, 1993. doi:10.1007/BF00962071.
  • [129] Slawek Staworko, Jan Chomicki, and Jerzy Marcinkowski. Prioritized repairing and consistent query answering in relational databases. Annals of Mathematics and Artificial Intelligence (AMAI), 64(2-3):209–246, 2012. doi:10.1007/S10472-012-9288-8.
  • [130] Balder ten Cate, Gaëlle Fontaine, and Phokion G. Kolaitis. On the data complexity of consistent query answering. Theory of Computing Systems (TOCS), 57(4):843–891, 2015. doi:10.1007/S00224-014-9586-0.
  • [131] Michaël Thomazo. Conjunctive query answering under existential rules - Decidability, complexity, and algorithms. PhD thesis, Montpellier 2 University, France, 2013. URL: https://tel.archives-ouvertes.fr/tel-00925722.
  • [132] Stephan Tobies. Complexity results and practical algorithms for logics in knowledge representation. PhD thesis, RWTH Aachen University, Germany, 2001. URL: http://sylvester.bth.rwth-aachen.de/dissertationen/2001/082/01_082.pdf.
  • [133] Despoina Trivela, Giorgos Stoilos, and Vasilis Vassalos. A framework and positive results for IAR-answering. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), 2018.
  • [134] Eleni Tsalapati, Giorgos Stoilos, Giorgos B. Stamou, and George Koletsos. Efficient query answering over expressive inconsistent description logics. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016.
  • [135] Moshe Y. Vardi. On the complexity of bounded-variable queries. In Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), 1995.
  • [136] Guohui Xiao, Diego Calvanese, Roman Kontchakov, Domenico Lembo, Antonella Poggi, Riccardo Rosati, and Michael Zakharyaschev. Ontology-based data access: A survey. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018.