Inconsistency-Tolerant Semantics Based on (Preferred) Repairs
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, preferencesCategory:
Invited Paper2012 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 cleaningAcknowledgements:
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 MurlakSeries and Publisher:
Open Access Series in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
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 where is a predicate of arity and 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 to some domain element and each -ary predicate to a set of -tuples . 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 by the set of tuples .
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:
| (1) |
where and (for ) are conjunctions of relational atoms whose terms are in and , respectively, and is a conjunction of inequality atoms whose terms are in . Moreover, every variable in is required to occur in to ensure safety. We often omit the universal quantifier and write . The left-hand side is called the body of the rule and the right-hand side 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 , where is a conjunction of negated relational atoms (e.g., can be written as two rules and ).
-
A denial constraint (DC) is a rule of form (1) with an empty head: .
-
An equality-generating dependency (EGD) is a DC where is a single inequality and is often written as .
-
Given a predicate of arity , a functional dependency (FD) over is of the form for two disjoint sets of indexes . Any FD can be written as a set of EGDs (e.g., can be written as two EGDs for ).
-
A key constraint is an FD such that .
-
A disjunctive tuple-generating dependency (-TGD) is a rule of form (1) with an empty , i.e., no inequalities.
-
A tuple-generating dependency (TGD) is a -TGD without disjunction (i.e., where ).
-
A local-as-view TGD (lav TGD) is a TGD where the body is a single atom.
-
An inclusion dependency (ID) is a lav TGD where the head 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 is not registered as a graduate nor an undergraduate course while it occurs in second position in , () because of and , and () because of the last two facts. Note that if we remove from , () and () will be satisfied, but () will become violated since is the only fact that associates some course to .
| () | ||||
| () | ||||
| () | ||||
| () | ||||
| () | ||||
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 , and
-
negative constraints (NCs), which are rules of the form where is a conjunction of relational atoms with variables (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 for each constant that occurs in (standard name assumption),
-
, i.e., , for every , 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 and . The database is inconsistent while the KB is not (and entails ). 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 to iff there is a rule whose body contains and whose head contains , 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 .
| () | ||||
| () | ||||
| () | ||||
is inconsistent since for every interpretation , if and , 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 and, e.g., from yields a consistent KB. For example, the interpretation below is a model of . Note that uses a fresh element to witness a course taken by and satisfy the TGD.
| Name | Syntax | Semantics |
|---|---|---|
| Top concept | ||
| Bottom concept | ||
| Nominal | ||
| Negation | ||
| Conjunction | ||
| Disjunction | ||
| Existential restriction | ||
| Qualified existential restriction | ||
| Qualified universal restriction | ||
| Qualified cardinality restrictions | ||
| Inverse role | ||
| Concept inclusion | ||
| Role inclusion | ||
| Complex role inclusion | ||
| Role disjointness | ||
| Transitivity axiom |
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 .
-
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., is simple if implies ).
-
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 .
-
Another family of lightweight DLs is the DL-Lite family. In particular:
-
–
A DL-Litecore TBox consists of concept inclusions of the form where with a concept name and a role name or inverse role, and .
-
–
DL-LiteR extends DL-Litecore with role inclusions and role disjointness axioms.
- –
-
–
An interpretation is a model of a DL KB if
-
satisfies all facts in (i.e., and for all concept and role assertions and 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.
| ()-() | ||||
| () | ||||
| () | ||||
| () | ||||
| () | ||||
As in Example 2, the KB is inconsistent but removing the facts and makes it consistent, when interpreted without the unique name assumption: a model of simply interprets and 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 is a (certain) answer to a query with answer variables over a KB if , where is the FO sentence obtained by replacing each by in . For a database , we simply define by . A conjunctive query (CQ) is an FO query of the form where is a conjunction of relational atoms. A union of conjunctive queries (UCQ) has form where each 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 and the ontology from Example 3. The CQ has two certain answers over : and .
FO- and UCQ-rewritability.
We say that CQ answering under an ontology language is UCQ-rewritable (resp. FO-rewritable) if for every BCQ and ontology in , there exists a BUCQ (resp. an FO query) such that for every dataset , iff . In the BUCQ case, we denote the set of BCQs in by .
Fact 5.
Example 6.
Given the DL-Litecore ontology and BCQ , with .
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 such that for every dataset , iff .
Proof.
For every Datalog± KB , iff there exists such that , where is the set of TGDs in , so if is in X and CQ answering under X is UCQ-rewritable, iff for some .
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:
-
–
: 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 .
-
–
-
The polynomial hierarchy and other classes between P and PSpace:
-
–
: problems which are solvable in polynomial time w.r.t. the size of the input.
-
–
: 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.
-
–
: problems whose complement is in NP.
-
–
In general, for , is the class of problems solvable in polynomial time with access to a oracle, , and .
-
–
is the class of problems solvable in polynomial time with at most logarithmically many calls to a oracle. It is known that these are problems solvable by polynomially many independent (parallel) calls to a 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 .
-
–
-
The (weak) exponential hierarchy and other classes between Exp and 2Exp:
-
–
: problems which are solvable in exponential time, i.e., in where is a polynomial function and is the input size.
-
–
: problems which are solvable in non-deterministic exponential time.
-
–
: problems whose complement is in NExp.
-
–
In general, for , is the class of problems solvable in exponential time with access to a oracle, , and .
-
–
DExp: problems that are the intersection of a problem in NExp and one in coNExp.
-
–
: problems that are solvable in polynomial time with an NExp oracle. It is known (since the strong exponential hierarchy collapses [89]) that .
-
–
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 and outputs “yes” if , 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.
| Data complexity | Combined complexity | ||||||
| DLs | DL-LiteR | in | [12, Th. 8.9] | NP |
|
||
| DL-LiteR,⊓ | in | 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 | [56, Cor. 10] | PSpace | [55, Th. 12.7] | |||
| in | [104, Pr. 3.3] | NExp | [104, Pr. 3.3] | ||||
| P | [54, Th. 6.1] | 2Exp | [54, Th. 6.1] | ||||
| in | [57, Th. 3.5] | Exp | [57, Th. 3.3 & 3.4] | ||||
| P | [70, Th. 4.4] | Exp | [70, Th. 4.5] | ||||
| Database | in | [135, Tab. 1] | NP | [63, Th. 7] | |||
| Data complexity | Combined complexity | ||||||||
| DLs | DL-LiteR | in | [12, Th. 8.3] | NL | [12, Th. 8.2] | ||||
| DL-LiteR,⊓ | in | 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 |
|
PSpace |
|
|||||
| in | coNExp | ||||||||
| P | 2Exp | ||||||||
| in | Exp | ||||||||
| P | Exp | ||||||||
| ICs | FD | in |
|
in L | folklore (e.g., [11]) | ||||
| DC | in | coNP |
|
||||||
| full TGD | in | coNP | |||||||
| UC | in | coNP | |||||||
| TGD | in | [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 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 , iff , 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 such that , where is the set of TGDs in (meaning that is in X if is in ), and (ii) for every BCQ , iff either 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 (or in the BCQ entailment case) and check in PSpace that (or ). The result follows from the fact that .
-
–
For the NExp/coNExp upper bounds for , proceed as above, but guess the BCQ (or ) 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.
-
–
-
upper bounds: If , since CQ answering under X is UCQ-rewritable (Fact 5), by Proposition 7, for every ontology in , there exists a BUCQ such that for every dataset , iff . Moreover, for every BCQ , iff where is the set of TGDs in . This yields the 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 and , we can obtain a consistent database by removing or by adding 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: .
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 , we use or to denote the set of all -repairs of , i.e., -repairs of w.r.t. . When is a KB or a database with anti-monotone ICs, and if is inconsistent, so we can simply write for and talk about “repairs” instead of -repairs.
In the above definition, the “S” in 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 and .
Example 11.
Recall from Example 1. The -repairs of w.r.t. are as follows, among which only and are -repairs:
plus for each repair that contains , the repair obtained by replacing this fact by . Note that there are infinitely many repairs since can be any constant.
Now recall from Example 3. The repairs of w.r.t. are as follows:
with
Note that if we made the unique name assumption, we would obtain eight repairs with and .
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 iff is a maximal independent set of .
Example 15.
Let with and
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 where is a predicate that occurs in , and 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 iff is a maximal independent set of .
Example 18 ([32]).
Let and be the following set of UCs:
The conflicts, conflict graph (binary conflicts) and -repairs of w.r.t. are as follows:
|
|
The first (resp. second) conflict directly violates the first (resp. second) IC. To see why is also a conflict, consider any interpretation such that . Then if or , violates the first or second constraint, respectively, and if and , it violates the third constraint.
We can obtain, e.g., the second repair, by considering the maximal independent set of the conflict hypergraph , which gives the literals upon which the repair and agree (so implicitly also those on which they disagree: and , which have to be “flipped” to obtain the repair ).
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 is the attack relation. We say that attacks , and write , to mean .
Given an AF and some , let be the set of arguments attacked by arguments from . A set defends iff . If is a SETAF, these definitions are adapted as expected: and defends iff whenever .
Given a (SET)AF , a set is conflict-free if . The characteristic function of is defined as follows: . A set is admissible if it is conflict-free and defends itself: . (SET)AF semantics are based upon sets of arguments called extensions.
Definition 21 (Extensions).
Let be a (SET)AF. Then is a:
-
naive extension iff is a -maximal conflict-free subset of ;
-
preferred extension iff is a -maximal admissible set;
-
stable extension iff .
Stable extensions are preferred extensions but the converse does not hold in general [76].
Example 22.
The AF depicted below has the following extensions.
|
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 , 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, be its associated SETAF and .
-
iff is a naive extension of .
-
iff is a preferred extension of .
-
iff is a stable extension of .
Example 24.
Consider defined in Example 15. The SETAF associated to is where is as follows.
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 ) and functional dependencies (of the form ) and AF extensions [113]. Let be a database such that is a set of IDs and FDs. The AF associated to is , where and
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, be its associated AF and . Then iff is a preferred extension of .
Naive, stable and preferred extensions may not coincide in this case, as illustrated below.
Example 26.
Let with , , , and and consists of the ID and the FD . The AF associated with is such that , and is as follows.
The naive extensions of 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 , either so that while , or so that while ).
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 even when is a database with general ICs, meaning that we can choose between , or 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 is an answer to the query over under the CQA semantics iff for every .
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 is an answer to the query over under the intersection semantics iff where .
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 is an answer to the query over under the ICR semantics iff where .
Remark 30.
If is a database, so the ICR and intersection semantics coincide.
The family of -support semantics was introduced to generalize the intersection semantics and obtain more fine-grained under-approximations of CQA, such that increasing the value of yields a closer approximation [41]. A support of a Boolean query in is a -consistent subset such that .
Definition 31 (-support semantics).
A tuple is an answer to the query over under the -support semantics iff there exist (not necessarily distinct) supports of in such that for every , there is some .
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 is an answer to the query over under the brave semantics iff for some .
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 is an answer to the query over under the non-objection semantics iff (i) for some and (ii) for every , there is a model of such that .
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 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 is an answer to the query over under the majority-based semantics iff .
Finally, the family of -defeater semantics provides fine-grained over-approximations of CQA, where increasing the value of 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 (-defeater semantics).
A tuple is an answer to the query over under the -defeater semantics iff there does not exist a -consistent subset of with such that for every minimal support of 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, -support, |
| CQA, non-objection | |
| Unique Base | intersection, ICR |
-
Consistent Support: for every , and , if is an answer to over under Sem, then there exists a -consistent subset of such that .
-
Consistent Results: for every , there exists a model of such that for every and , if is an answer to over under Sem, then .
-
Unique Base: for every , there exists a -consistent dataset such that for every and , is an answer to over under Sem iff .
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:
The KB entails the BCQ:
-
under the intersection semantics, since ;
-
under
-
–
the ICR semantics, since ,
-
–
the 3-support semantics, since the three supports , and cover all repairs,
but not under the intersection semantics nor under the 2-support semantics;
-
–
-
under the CQA semantics, since it is entailed by every repair, but not under the ICR semantics;
-
under the majority semantics (it holds in of the repairs), but not under
-
–
the CQA semantics, since it does not hold in ,
-
–
the non-objection semantics, since for , ,
-
–
the 1-defeater semantics, since one fact () is sufficient to contradict the two minimal supports of ( and );
-
–
-
under the non-objection semantics since it holds in repairs and is consistent with all repairs, but not under
-
–
the CQA semantics, since it does not hold in ,
-
–
the majority semantics, since it holds only in of the repairs,
-
–
the 1-defeater semantics, since one fact (e.g., ) is sufficient to contradict the only minimal support of ();
-
–
-
under the 1-defeater semantics, since we need two facts ( and ) to contradict the minimal supports and , but not under the CQA semantics (cf. , and );
-
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 where 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 . Intuitively, a repair of a dataset w.r.t. an ontology is a quantified ABox such that , for every (and for other unwanted consequences , if any). An optimal consequence-preserving repair is then a repair such that there is no repair such that but . 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 and are optimal consequence-preserving repairs of w.r.t. , as well as all those obtained by adding some consequences w.r.t. , such as . 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 is entailed under the CQA semantics based on this kind of repair. We also obtain that 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 -lazy semantics restores consistency in each connected component of the conflict hypergraph by either removing at most facts, or by removing the whole connected component if removing 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 -CQA, -intersection and -brave be the counterparts of the CQA, intersection and brave semantics that use preferred repairs from some instead of standard (- or -)repairs. If is entailed by under:
-
CQA (resp. intersection), then it is also entailed under -CQA (resp. -intersection);
-
-brave, then it is also entailed under brave.
Moreover, if is entailed by under:
-
-intersection, then it is entailed under -CQA;
-
-CQA, then it is entailed under -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., and ). 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:
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 that assigns a (positive) weight to each fact and induces a preorder over datasets:
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 -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 of disjoint datasets such that . Facts in are considered the most reliable and those in the least reliable. A prioritization induces a set-inclusion-based preorder :
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. -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 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 that contains . We then simply drop the negation in literals to get the corresponding prioritization of all relevant facts , with , and use instead of in the definition of (additionally setting for every and ). We can show that the definition of -optimal -repairs given in [32] is indeed equivalent to that of Definition 41 using this preorder by observing that for all , iff there is some such that
-
(recall from Proposition 17 that is the set of literals upon which and agree) and
-
for .
Prioritized cardinality ().
A prioritization also induces a cardinality-based preorder :
-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 -optimal repairs. Note that with and , a single fact on level is preferred to any number of facts from . 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 () and to denote the (-optimal) - or -repairs of a KB or database .
-
If assigns the same weight to every fact, then and coincide, i.e., weight-based repairs generalize cardinality-based repairs.
-
Given a prioritization , let , and let be defined by for (or in case of -repairs, for or ). Then for every , and 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 and coincide, and 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 contains:
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 , 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 , based on the reliability of the predicates:
We obtain and . Now is entailed under the -intersection and -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 -intersection semantics, but only the less specific is entailed under -CQA semantics.
-
If we assign facts in a weight of 2, and facts of a weight of 1, . Under -CQA semantics, neither nor is entailed, but only . Under -intersection semantics, is entailed.
Example 44.
Consider the database (with UCs) defined as follows.
The set of -repairs contains:
-
since and have the smallest symmetric differences with .
-
If we take the prioritization where contains and all negative literals (to strongly penalize fact additions) and , then and . Indeed, while and are incomparable w.r.t. . However, since contains two facts of level 1 while only one.
-
If we assign to literals in a weight of 2, and to those in a weight of 1, we obtain that since has weight 3, 4 and 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 such that for every with , iff .
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 and for some , then the former is preferred, and (iii) if a person is declared to belong to and to a subclass of , but there is no -fact about this person in , then the -fact is deemed more reliable.
| (i) | |||
| (ii) | |||
| (iii) |
Assume that
and that is associated to a more recent date than . The rules yield the following preference statements: (i) is preferred to , (ii) is preferred to , and (iii) 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 , , 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 .
5.2.1 Pareto-, globally- and completion-optimal repairs
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 .
-
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 , , and 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 .
-
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 (, and ) 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
and similarly for 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 , and .
We show that and .
-
is not Pareto-optimal (hence not globally- nor completion-optimal) because is a Pareto improvement of (since ).
-
is not globally-optimal (hence not completion-optimal) since is a global improvement of (since and ). However, it is Pareto-optimal, since replacing only by leads to a contradiction between and , and similarly replacing only with leads to a conflict .
-
is completion-optimal (hence globally- and Pareto-optimal), since every completion of is such that (to avoid cycle ). Indeed, this implies that for every completion , a globally-optimal repair of must contain (otherwise would be a global improvement of w.r.t. ), hence does not contain nor , so that .
Example 52 ([32]).
Let and contains the UCs:
The conflicts are all binary, so the conflict hypergraph is a graph, whose edges are pictured below. Assume that , , , . 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:
and that .
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, (hence ). 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 between datasets defined by “ 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: , , and . is a Pareto improvement of and is a Pareto improvement of , but is a not a Pareto improvement of : the relation “is a Pareto improvement of” is not transitive, so 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 , the corresponding prioritization of is such that for every , there exists such that , , and for every , , iff . 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 (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 -optimal 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 , with , is such that iff is a naive/stable/preferred extension of . 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 is defined as follows: iff and for every . A subset 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 associated to is obtained from the SETAF associated to by using the priority relation as the preference relation, i.e., [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, be its associated PSETAF, and .
-
iff is a stable extension of .
-
If is transitive, then iff is a preferred extension of .
-
If every is such that , then iff is a preferred extension of .
Note that it follows that globally-optimal and completion-optimal repairs correspond to proper subsets of the stable extensions of , but they do not at present have any analogue in the argumentation setting.
Example 59.
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 , with a conjunction of relational atoms, a conjunction of negated relational atoms and a conjunction of inequalities (cf. Section 2.1).
Definition 60 (Update actions).
An update atom is of the form or where is a relational atom. We use a function to map relational literals to the corresponding update atoms: and . 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 , where is a UC, and is a non-empty set of update atoms such that each is equal to for some . A literal of is non-updatable if . A dataset satisfies () if it satisfies .
A ground AIC is an AIC that contains no variables. The set contains all ground AICs obtained from by (i) replacing variables by constants that occur in , (ii) removing all true atoms, and (iii) removing all ground AICs with an atom . We let , and observe that iff for every .
An AIC is called normal if its head contains a single update atom. The normalization of is the set . The normalization of a set of AICs is .
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 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 , there exists such that is an update action of and .
-
Well-founded if there is a sequence of actions such that , and for each , there exists such that is an update action of and .
-
Grounded if for every , there is such that and the (only) update action of is in (recall that is the normalization of ).
-
Justified if is a minimal set of update actions closed under that contains the set of no-effect actions where
-
–
-
–
is closed under if for every , if satisfies all the non-updatable literals of , then contains an update action of .
-
–
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 to means 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
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.
Example 65.
We modify slightly the UCs of Example 52 so that some -repairs are not Pareto-optimal. Let and contains the UCs:
The edges of the conflict graph and the optimal repairs are shown below, assuming that , , , .
The set of ground AICs corresponding to contains the following AICs:
We can check that the two Pareto-optimal -repairs correspond exactly to the justified, grounded and founded repair updates:
-
and , which correspond respectively to the -repairs and , are not founded (hence not grounded nor justified). Indeed, while the only AIC with in the head () is satisfied by . Regarding , and the two AICs with in the head ( and ) are satisfied by .
-
The repair update , which corresponds to the Pareto-optimal -repair is grounded (hence founded) and justified. Indeed, (1) for every , there is in the normalization of such that and the only update action of is in , so is grounded, and (2) is a minimal set of update actions closed under that contains (since this set of update actions satisfies all the non-updatable literals of , and ).
-
The repair update , which corresponds to the Pareto-optimal -repair 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 , that the first attribute of each relation in stores a unique fact identifier, and that stores pairs of such identifiers. Then given a set of DCs over , 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 , then contains and , so is no longer an image of a constraint body. The set of AICs corresponding to , , contains all AICs
such that , , and for every , for some .
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 .
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
where and are two relational atoms whose variables are and respectively (and may contain constants), , and is a (possibly empty) conjunction of relational atoms with variables . 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 (w.r.t. ) if implies that or , i.e., if the following holds:
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.
There are six repairs:
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:
Since all repairs trivially satisfy the ground instances obtained by replacing by , we identify each with its ground instance obtained by replacing by in what follows.
-
and satisfy all rules. For example, satisfies because , and because .
-
satisfies all rules but : and while . Note that it satisfies because .
-
satisfies all rules but ; satisfies all rules but ; and satisfies all rules but .
Hence, for , , 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 :
We obtain while . Indeed satisfies all rules but ; satisfies all rules but ; and satisfies , , , and .
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 is preferred to (counterpart of ), is preferred to (counterpart of ), is preferred to (counterpart of ), and is preferred to (counterpart of ), which yields (assuming that all rules are equally important) the priority relation , . The optimal repairs w.r.t. this priority relation are for and for .
Capturing -optimal repairs for .
Given and a preorder 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 such that and do not occur in , , and for all subsets and of (which is equal to in this case) let iff . 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 -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 ).
5.4.1 Repairs based on non strictly -monotone weight-based preorders
A generalization of -optimal repairs based on aggregation functions has been defined for databases with anti-monotone ICs [122]. An aggregation function maps every dataset (associated with a weight function ) to a non-negative rational number (cf. [122] for the precise definition). Prominent examples of such functions are (which yields -optimal repairs), , or .
Definition 71 (Aggregation-based repairs).
Given an aggregation function and a KB (or database with anti-monotone ICs) with a weight function , a -repair of is a -consistent such that (i) there is no -consistent with and (ii) for every -consistent , if and , then .
Note that if we define the preorder corresponding to an aggregation function as iff , condition (i) of Definition 71 can be written as “there is no -consistent with ”. 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 -repair needs to be -maximal among the -maximal -consistent subsets of . The following example shows that this is not sufficient to ensure that -repairs are dataset repairs.
Example 72 ([122]).
Let be such that is -consistent, so that , and assume that and . Consider the aggregation function defined by . Then is the only -repair of w.r.t. since . Hence the set of -repairs is not a subset of .
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 of (i.e., iff for some conflict , , and ), 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 of .
-
The possibilistic repair of is , where is the inconsistency degree of , which is such that is -inconsistent and is -consistent.
-
The linear repair of is with:
-
–
if is -consistent, otherwise;
-
–
for , if is -consistent, otherwise.
-
–
-
The non-defeated repair of is where .
-
The linear-based non-defeated repair of is with:
-
–
;
-
–
for , .
-
–
-
The prioritized inclusion-based non-defeated repair of is where . Equivalently, .
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 [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 .
-
.
-
.
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 , recall that the characteristic function of is defined by . Then is a complete extension iff is conflict-free and , and the grounded extension of is the -minimal complete extension, or equivalently, the least fixpoint of .
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 associated with (cf. Section 5.2.2).
-
For , the analogue of is .
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 (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 )
holds for all but , -
Sound w.r.t. prioritized intersection:
included in the intersection of optimal repairs
holds for all but ,
Example 76.
Assume that has the conflict graph depicted below and let be the prioritization of defined by: , , , . Arrows on the conflict graph indicate the priority relation induced by . The optimal repairs () 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).
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 . A soft repair of w.r.t. is a dataset such that
is minimal, i.e., there is no such that .
Soft repairs are not dataset repairs since they may be -inconsistent. However, they generalize -optimal repairs.
Proposition 79 ([60]).
If is a function that assigns a positive weight to each fact of , then is equal to the set of soft repairs of w.r.t. using where for each and 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 with for every concept inclusion . 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 and output “yes” if entails 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.
| Data complexity | Combined complexity | ||||||
|
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 | ||||||
|
in L | Prop. 82 | PSpace | [107, Tab. 3] | |||
| in L | DExp | ||||||
| P | Prop. 81 | 2Exp | |||||
| in L | Prop. 82 | Exp | |||||
| P | Prop. 81 | Exp | |||||
|
FD | in L | [11, Tab. 3] | in L | [11, Tab. 3] | ||
| DC | in L | DP | |||||
|
full TGD | P | [11, Tab. 3] | DP | [11, Tab. 3] | ||
| UC | coNP | ||||||
| TGD | coNP | ||||||
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.
check that ,
-
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.
check that and that ,
-
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 of propositional formulas, decide whether is satisfiable and is unsatisfiable. We assume that and 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 and be two sets of clauses and over variables and (and truth values 1, 0), respectively. We define an KB by:
and with:
We claim that iff is satisfiable and is unsatisfiable. Indeed, it is easy to show that for , is -consistent iff is satisfiable, since there is a one-to-one correspondence between models of , which assign each to or in a way that does not enforce any to be assigned to , and valuations of the ’s that satisfy . Moreover, is -consistent, since in this case there is a model that assigns all individuals but to . Since and 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 such that for every dataset , iff iff , where is the set of DCs that contains for each BCQ in . Hence, iff .
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 , 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,
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).
| Data complexity | Combined complexity | ||||||||
| CQA | Int. | brave | CQA | Int. | brave | ||||
|
DL-LiteR | coNP | in | in | NP | NP | |||
| DL-LiteR,⊓ | coNP | in | in | NP | |||||
| coNP | coNP | NP | NP | ||||||
| Exp | Exp | Exp | |||||||
| 2Exp | 2Exp | 2Exp | |||||||
|
coNP | in | in | PSpace | PSpace | PSpace | |||
| coNP | in | in | |||||||
| coNP | coNP | NP | 2Exp | 2Exp | 2Exp | ||||
| coNP | in | in | Exp | Exp | Exp | ||||
| coNP | coNP | NP | Exp | Exp | Exp | ||||
|
FD | coNP | in | in | |||||
| DC | coNP | in | in | ||||||
|
full TGD | coNP | coNP | P | Exp | ||||
| UC | |||||||||
| 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 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 in Algorithm 2 when . 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 .
Input: a KB or database with anti-monotone ICs and a BCQ
Output: iff entails under CQA semantics based on
Input: a KB or database with anti-monotone ICs and a BCQ
Output: iff entails under brave semantics based on
Input: a KB or database with anti-monotone ICs and a BCQ
Output: iff entails under intersection semantics based on
When the conflicts can be computed efficiently, Algorithm 4 provides an efficient way of deciding BCQ entailment under intersection semantics.
Input: a KB or database with anti-monotone ICs and a BCQ
Output: iff entails 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.
Proposition 83 ([41, Theorems 1, 2, 3]).
If CQ answering under is FO-rewritable and for every ontology in and BCQ , there exist and such that for every , (i) every minimal -consistent subset of such that has cardinality at most and (ii) every conflict of has cardinality at most , then CQ answering under the intersection and brave semantics in is FO-rewritable: for every ontology and BCQ , there exists an FO-sentence (resp. ) such that for every , is entailed by under intersection (resp. brave) semantics iff (resp. ).
Corollary 84 ( bounds).
BCQ entailment under intersection and brave semantics is in 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:
-
(i)
for DCs (hence also FDs) the size of minimal -consistent subsets of such that is bounded by , and for , and (hence also DL-LiteR and DL-LiteR,⊓), it is bounded by the maximal number of atoms in some BCQ in ;
-
(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 such that for every dataset , iff so the size of conflicts is bounded by the maximal number of atoms in some BCQ of .
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 , which belongs to , and . For every , we can build a dataset of size which is a conflict (of itself) w.r.t. : .
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 , 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 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 , -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 . The lower bound comes from that of BCQ entailment in .
The 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 , and the fact that [89, 104]. The lower bound follows from the reduction from the -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 , it follows that is valid iff is not entailed under brave semantics.
Data complexity of brave and intersection semantics in databases.
For brave and intersection BCQ entailment over databases, the 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 , is entailed by under brave semantics iff 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 is such that . Since BCQ evaluation is monotone, it follows that there exists such that holds in iff holds in . Finally, since iff holds in (by the fixpoint semantics of Datalog, cf. [1, Sec. 12.3]), we obtain that is entailed by under brave semantics iff 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 over variables and define by:
We claim that is entailed by under intersection semantics iff is unsatisfiable. Indeed, if there exists a valuation of that satisfies , the following dataset is a -repair of w.r.t. , so does not hold under intersection semantics.
In the other direction, if there is a -repair of w.r.t. such that , then and (otherwise would be -consistent). Since , there must exist such that or is included in (otherwise would be -consistent), and we can show that for every , there must exist such that either or is included in . Moreover, since , for every , either or does not belong to so the valuation defined by iff 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 , 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.
| Repair checking | CQA | Intersection | Brave | |
|---|---|---|---|---|
| coNP | ||||
| coNP | † | † | † | |
| coNP | † | † | † | |
| in P | coNP | coNP | NP | |
| in P | coNP | coNP | NP | |
| in P | coNP | coNP | NP | |
| coNP |
| Repair checking | CQA | Intersection | Brave | |
|---|---|---|---|---|
| coNP | ||||
| coNP |
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 and in P for X-optimal repairs for . 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 . 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].
Input: and (and weight function or prioritization when relevant)
Output: iff
Input: and
Output: iff
Input: with prioritization and
Output: iff
Input: and
Output: iff
Input: and
Output: iff
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 - and -optimal repair checking, since -optimal repairs can be obtained as special cases of - or -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 be a conjunction of clauses of three literals over variables .
-
For the FD case, define with
We can show that is not a -optimal repair of iff is satisfiable. Indeed, is -consistent and , so iff there exists a -consistent of size at least . Such necessarily contains only facts of the form because of the last FD, so contains exactly facts because of the first two FDs. It is easy to check that the valuation of the defined by iff contains some satisfies every clause. In the other direction, every valuation that satisfies can be used to build a repair of size .
-
For the DL-Litecore (and NC) case, define with
We can show that is not a -optimal repair of iff is satisfiable. Indeed, is -consistent and , so iff there exists a -consistent of size at least . Since every repair of contains at most one fact of the form or per , and such fact prevents the corresponding to belong to the repair, the only way to obtain a repair of size is to select exactly one or per , remove all , and keep . Since each cannot occur both in - and -facts, such repair corresponds to a valuation of the such that iff contains some and it is easy to check that satisfies . In the other direction, every satisfying valuation can be used to build a repair of size .
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 ;
-
(resp. ) for ;
-
for ;
-
for and for 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 , 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 . Similarly, for semantics based on globally-optimal repairs, since globally-optimal repair checking is in coNP, the and 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 -optimal repairs to -optimal ones and Algorithms 11, 12 and 13 for semantics based on -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.
Input: , a weight function
Output: the weight of -optimal repairs
Input: , a weight function , and a BCQ
Output: iff entails under CQA semantics based on
Input: , a weight function , and a BCQ
Output: iff entails under brave semantics based on
Input: , a weight function , and a BCQ
Output: iff entails under intersection semantics based on
The number of calls to the NP oracle is logarithmically bounded in 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 independent of such that for every , since in this case . In particular, this is the case for -optimal repairs (case ). For -optimal repairs, we use the reduction to -optimal repairs presented in Section 5.1: given , let , and for , then . Again, if is bounded by a constant independent from , the resulting weights are bounded by so and the number of oracle calls is logarithmic.
Lower bounds.
For semantics based on X-optimal repairs with , the coNP and NP lower bounds have been shown in the case of -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 , Pareto- and completion-optimal repairs coincide with -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 or using a priority relation that can be induced by a prioritization.
For semantics based on globally-optimal repairs, the and lower bounds have been shown for DL-Litecore using ontologies equivalent to sets of NCs [30, Theorem 10], and the -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 from the dataset, and every repair that does not contain contains . Hence is entailed under G-CQA iff it is entailed under G-intersection iff is not entailed G-brave semantics.
For semantics based on X-optimal repairs with , a lower bound has been shown for -CQA, -intersection and -brave semantics (hence transfers to - and -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 -hard problem [103, Lemma 6]: given a graph and a vertex , decide if belongs to all (cardinality) maximum independent sets (MISs) of . Assume w.l.o.g. that every belongs to some and define as follows, where for , is the number of edges of in which occurs.
We show that belongs to all MISs of iff is entailed under -CQA (resp. -intersection) semantics, iff is not entailed under -brave semantics. We first show a correspondence between -optimal repairs of and MISs of :
-
Given an independent set of , define . satisfies the second FD by construction and the first one because is an independent set. Hence is -consistent. Moreover, .
-
Given a -consistent subset , define . For each , does not contain any fact of the form (or it would violate the second FD) and for each , by definition of , does not contain any fact of the form . Hence .
-
Let . We show that is an independent set of . Assume for a contradiction that there is an edge such that . For , let . Since is -consistent, it is easy to check that the are also -consistent. Since , must contain some facts of the form and (by definition of ). Hence does not contain any fact of the form nor . Moreover, by the first FD, there is such that does not contain for . Hence there is such that is obtained from by adding exactly facts of the form and removing at most facts of the form so . This contradicts the fact that . Hence is an independent set of .
-
Let . We have shown that is an independent set of and . Assume for a contradiction that there exists an independent set of such that . We have shown that is -consistent and . It follows that , which contradicts . We conclude that is a MIS of .
-
Let be a MIS of . Since is an independent set, is -consistent and . Assume for a contradiction that and let . We have shown that is an independent set of and . Since we assumed that , it follows that , which contradicts that is a MIS of . We conclude that .
Assume that belongs to every MIS of and let . Since is a MIS of , so there exists and does not contain any fact of form and contains (by maximality). Hence is entailed under -intersection (hence -CQA) semantics and is not entailed under -brave semantics. In the other direction, assume that there exists a MIS of such that . Then is such that there is no fact of the form in and so is entailed under -brave semantics and is not entailed under -CQA (hence nor under -intersection) semantics.
For semantics based on X-optimal repairs with (in the case where the weights and priority levels are not bounded independently from the data), a lower bound has been shown for -CQA, -intersection and -brave semantics (hence transfers to -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 -hard problem [96]: given a satisfiable CNF formula over variables , decide whether the lexicographically maximum truth assignment satisfying with respect to is such that . Define and a prioritization as follows:
We can show that is entailed under -CQA (resp. -intersection, -brave) semantics iff . Indeed, since is satisfiable, for each satisfying valuation , we can obtain a -consistent subset of facts from by selecting exactly one fact of the form per and complete it into a (standard) repair by adding all such that no fact of the form has been selected. Since it is not possible to keep more than facts from because of the first FD, and each other contains a single fact, the -repairs all contain the same set of facts from and these facts correspond to the 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 (-, 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 for standard repairs.
-
Those for which the complexity of repair checking and BCQ entailment under CQA increases to coNP-complete and - or -complete (-, -, -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 -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 -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 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 , and ). 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 (-complete) but the one of intersection semantics increases from NP-complete to or when -, -, - or -optimal repairs are used [33, Figure 1], and the one of brave semantics increases similarly when using -, - or -optimal repairs (but remains NP-complete in the case of -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 -CQA semantics is -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 -complete (resp. -complete when the weights are bounded) data complexity for BCQ entailment under -CQA, as well as under -intersection (extended as usual to 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 (resp. ) together with (resp. and the ) 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 -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 /-complete (cf. Table 5) [32, Theorem 3]. For -optimal repairs, the data complexity actually decreases: it is -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
| semantics | input supported | main techniques | |
|---|---|---|---|
| [37] | X-CQA/X-inter./X-brave | , metadata, pref. rules, | ASP |
| (2025) | for | DCs, UCQ | |
| [31] | X-CQA/X-inter./X-brave | binary , , | SAT + poly. approx. |
| (2022) | for | pot. answers + causes | |
| [33, 35] | X-CQA/X-inter./X-brave | (possibly with ), | SAT + poly. approx. |
| (2014) | for | DL-LiteR onto., CQ | |
| [73] | -CQA | , , onto., | SAT |
| (2013) | CQ without | ||
| [74] | -CQA | , UCs, | SAT |
| (2010) | CQ | ||
| [133] | S-inter. | , onto. | (disj.) Datalog¬ rew. |
| (2018) | (with restr.), CQ | ||
| [134] | S-inter. | , DL-LiteR onto., | comp. |
| (2016) | CQ | ||
| [127, 99] | S-inter. | , DL-LiteA onto., | FO rewriting |
| (2012) | CQ | annot. with | |
| comp. | |||
| [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 (-, Pareto- and completion-optimal);
-
the second group consists of implementations of - 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 -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 , and a tuple , a cause for in is a -minimal -consistent subset of such that . We denote by the set of all causes for 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 is satisfiable iff is not an answer to over under the CQA semantics.
and . Intuitively, the set of facts such that is assigned to true by a satisfying valuation for is -consistent and contradicts every cause for in , hence can be extended into a repair of that does not entail . Indeed, for each cause of in , ensures that we choose some and some such that , and select all facts from , and 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 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 is satisfiable iff is not an answer to over under the CQA semantics based on Pareto-optimal repairs.
, , and is the set of facts reachable from in the following sense: is reachable from if or if there exists reachable from 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 .
The only cause for is and the SAT encodings to decide whether holds under CQA based on standard and Pareto-optimal repairs, respectively, are as follows (for readability we write instead of in indexes).
is satisfiable (assign , and to true and to false), and indeed is not entailed under CQA based on standard repairs because of . On the other hand, holds under P-CQA and is indeed unsatisfiable: to satisfy (first line), we need to assign and to true, which implies that and are assigned to false to satisfy (last line), but assigning to false implies that must be assigned to true to satisfy . Note that is much bigger than : this is because we need to take into account all facts reachable from and 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 such that for every , is entailed by under intersection iff . For example, if we extend the ontology of Example 15 with and and consider the query , an FO-rewriting of w.r.t. is .
-
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 ;
-
–
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.
