Computing Approximate Query Answers over Inconsistent Knowledge Bases

1 Introduction

Reasoning in the presence of inconsistent information is a problem that has attracted much interest in the last decades. Many inconsistency-tolerant semantics for query answering have been proposed, and most of them rely on the notions of consistent query answer and repair. A consistent answer to a query is a query answer that is entailed by every repair, where a repair is a "maximal" consistent subset of the facts of the knowledge base. Different maximality criteria have been investigated, but all the resulting notions of repair share the same drawback: a fact is either kept or deleted altogether, and deleting entire facts can cause loss of "reliable" information.

Example 1. Consider the knowledge base (D,Σ) where D contains the following facts:

works

and Σ is an ontology consisting of the following equalitygenerating dependency (EGD) σ:

As an example, the fact works(john, cs, nyc) states that john is an employee working in the cs department located in nyc. The dependency σ says that every department must be located in a single city. Clearly, the last two facts violate σ, so every repair would discard either of them.

If we pose a query asking for the employees' name, the only consistent answer is john. However, intuitively, we might consider reliable the information on mary being an employee, as the only uncertainty concerns the math department and its city-roughly speaking, the information in the first column of the works table can be considered "clean". Dropping entire facts causes loss of information.

To overcome the drawback illustrated above, we propose a notion of repair based on updating values within facts. Update-based repairing allows for rectifying errors in facts without deleting them altogether, thereby preserving consistent values.

If we ask again for the employees' name, both mary and john are consistent answers.

We consider knowledge bases where ontologies are expressed through (a particular class of) EGDs. Equalitygenerating dependencies are one of the two major types of data dependencies-the other major type consists of tuplegenerating dependencies (TGDs)-and can model several kinds of constraints commonly arising in practice, such as functional dependencies and thus also key dependencies.

We show that consistent query answering in this setting is coNP-complete. Then, we show how to compute a "universal" repair, which compactly represents all repairs and can be computed in polynomial time. A universal repair is a valuable tool to compute approximate query answers. We propose a polynomial time approximation to compute a sound (but possibly incomplete) set of consistent query answers. The basic idea is illustrated in the following example.

Example 3. A universal repair for the two repairs of Example 2 is reported below:

where ⊥1 is a labeled null, and the "global" condition at the bottom restricts the admissible values for ⊥1, which are rome and sydney. We exploit such a representation for query answering, by combining the condition of the universal repair with provenance information during query evaluation. For instance, if we ask for the departments that are not located in nyc, we get math with condition ⊥1 ≠ nyc, which combined with the global condition allows us to conclude that math is a consistent answer (as its city is either rome or sydney, and thus cannot be nyc for sure).

As shown in the following, leveraging universal repairs, our approximation schema yields strictly better results than well-known approximation approaches such as the intersection of repairs and the intersection of closed repairs semantics [Lembo et al., 2010; Bienvenu et al., 2014].

Below we provide a further example showing that even when knowledge bases are expressed by unary/binary facts only, our approach can preserve more information than the classic notion of repair.

Example 4. Consider the knowledge base (D,Σ) where

Here emp(john, sydney) means that john is an employee living in sydney, and stud(john, nyc) means that john is a student living in nyc.

The EGD says that every person must be associated with the same city in emp and stud. Clearly, the knowledge base is inconsistent.

Consider now the query asking for the people who are both an employee and a student. Assuming that the only uncertain values are john's cities, we can still say that john is certainly an employee and a student, even if we are not sure where he lives. This information is preserved by our framework, as john is a consistent answer, but it is completely lost using the classic notion of repair, as there are no consistent answers. In fact, in our framework, there are two repairs obtained from D by changing either sydney into nyc or nyc into sydney-in both of them john is an employee and a student. According to the classical notion of repair, there are two repairs obtained from D by deleting either emp(john, sydney) or stud(john, nyc)-in the former john is a student but not an employee while in the latter he is an employee but not a student.

Contributions.

We consider the problem of querying possibly inconsistent knowledge bases in the presence of acyclic sets of EGDs. In this setting, we propose a new notion of repair based on a more fine-grained repair primitive, which updates values within facts rather than deleting them altogether, enabling us to preserve more information of the knowledge base. For such a repair strategy, we introduce the notion of a universal repair, which is a compact representation of all repairs, can be computed in polynomial time, and can be leveraged to compute consistent query answers.

We then develop a chase-like procedure to compute a universal repair, introducing a formalism that augments instances with provenance information. We show that consistent query answering in our framework is coNP-complete (data complexity). In light of this, we leverage universal repairs and provenance information to develop an approximation algorithm that provides a sound (but possibly incomplete) set of consistent query answers in polynomial time.

Organization.

Section 2 discusses related work. Preliminaries are reported in Section 3. Our inconsistency-tolerant semantics and its complexity are investigated in Section 4. A compact representation of all repairs and its computation are proposed in Section 5. Query evaluation is addressed in Section 6. Our approximation algorithm is introduced in Section 7. Conclusions and directions for future work are reported in Section 8.

2 RelatedWork

Reasoning in the presence of inconsistent information is a problem that has attracted a great deal of interest in the AI and database communities. Consistent query answering was first proposed in [Arenas et al., 1999]. Query answering under various inconsistency-tolerant semantics for ontologies expressed in DL languages has been studied in [Lembo et al., 2010; 2011; 2015; Bienvenu, 2011; 2012; Rosati, 2011; Bienvenu and Rosati, 2013], and in [Lukasiewicz et al., 2012b; 2015; 2012a] for ontologies expressed by fragments of Datalog+/-. Several notions of maximality for a repair have been considered in [Bienvenu et al., 2014]. Bienvenu and Rosati (2013) have proposed an approach for the approximation of consistent query answers from above and from below. Furfaro et al. (2007) proposed an approach based on threevalued logic to compute a sound but possibly incomplete set of consistent query answers.

Different from our proposal, all the approaches above adopt the most common notion of repair, where whole facts are removed. This can cause loss of information, as illustrated in the toy scenario of Example 1-in real-life scenarios, it might well be the case that facts have much more attributes and only a few of them are involved in inconsistencies, leading to significant loss of useful data.

There have also been different proposals adopting a notion of repair that allows values to be updated [Bohannon et al., 2005; Bertossi et al., 2008; Greco and Molinaro, 2008; 2012; Flesca et al., 2010]. Our repair strategy behaves similar to the one of [Bohannon et al., 2005; Greco and Molinaro, 2008; 2012] in that values on the right-hand side of functional dependencies (FDs) are updated. However, those works focus on FDs only. [Bertossi et al., 2008] allow only numerical attributes to be updated, one primary key per relation is allowed, but keys are assumed to be satisfied by the original database: thus, no repairing is possible w.r.t. keys, while we allow it, and we allow much more general constraints. Our repair strategy can be seen as an instantiation of the valuebased family of policies proposed in [Martinez et al., 2014], even though the two approaches differ in how multiple dependencies are handled, and they focus on FDs only. Flesca et al. (2010) consider numerical databases and a different class of (aggregate) constraints.

The main difference between this paper and the aforementioned ones is that none of them has investigated the approximate computation of consistent query answers-notice that [Bertossi et al., 2008; Bohannon et al., 2005] have proposed approximation algorithms for computing a repair with minimum distance from the original database, and [Greco and Molinaro, 2008] consider approximate probabilistic query answers. Also, we introduce the notion of a universal repair, which compactly represents all repairs and can be used for exact/approximate query answering.

Approximation algorithms for computing sound but possibly incomplete sets of query answers in the presence of nulls have been proposed in [Guagliardo and Libkin, 2016; Libkin, 2015; 2016; Greco et al., 2017; Fiorentino et al., 2018], but no dependencies are considered therein, and thus the database is assumed to be consistent.

3 Preliminaries

We assume the existence of the following pairwise disjoint (countably infinite) sets: a set Const of constants, a set Var of variables, and a set Null of labeled nulls. Nulls are denoted by the symbol ⊥ subscripted. A term is a constant, variable, or null. We also assume a set of predicates, disjoint from the aforementioned sets, with each predicate being associated with an arity, which is a non-negative integer.

An atom A is of the form p(t1, . . . , tn), where p is an nary predicate and the ti's are terms. We write an atom also as p(t), where t is a sequence of terms. An atom without variables is also called a fact. An instance is a finite set of facts. A database is an instance containing constants only.

A homomorphism is a mapping h ∶ Const ∪ Var ∪ Null → Const ∪ Var ∪ Null that is the identity on Const. Homomorphisms are also applied to atoms and set of atoms in the natural fashion, that is, h(p(t1, . . . , tn)) = p(h(t1), . . . , h(tn)), and h(S) = {h(A) ∣ A ∈ S} for any set S of atoms. A valuation is a homomorphism ν whose image is Const, that is, ν(t) ∈ Const for every t ∈ Const ∪Var ∪Null.

Conditional instances.

Conditional instances (also known as "conditional tables" [Imielinski and Lipski, 1984; Grahne, 1991]) are instances augmented with conditions restricting the set of admissible values for nulls. Let E be the set of all expressions, called conditions, that can be built using the standard logical connectives ∧, ∨, ¬, ⇒ and expressions of the form ti = tj, true, and false, where ti, tj ∈ Const ∪ Null. We will also use ti ≠ tj as a shorthand for ¬(ti = tj). We say that a valuation ν satisfies a condition φ, denoted ν ⊧ φ, if its assignment of constants to nulls makes φ true. Formally, a conditional instance (CI) is a pair ⟨I,Φ⟩, where I is an instance and Φ ∈ E. The semantics of C = ⟨I,Φ⟩ is given by the set of its possible worlds, that is, the set of databases pw(C) = {ν(I) ∣ ν is a valuation and ν ⊧ Φ}.

Equality generating dependencies.

An equality generating dependency (EGD) σ is a first-order formula of the form ∀xϕ(x) → xi = xj, where ϕ(x) is a conjunction of atoms (without labeled nulls) whose variables are exactly x, and xi and xj are variables from x. We call ϕ(x) the body of σ, and call xi = xj the head of σ. We will omit the universal quantification in front of dependencies and assume that all variables are universally quantified. With a slight abuse of notation, we sometimes treat a conjunction as the set of its atoms. An instance I satisfies σ, denoted I ⊧ σ, if whenever there exists a homomorphism h s.t. h(ϕ(x)) ⊆ I, then h(xi) = h(xj). A instance I satisfies a set Σ of EGDs, denoted I ⊧ Σ, if I ⊧ σ for every σ ∈ Σ.

A knowledge base (KB) is a pair (D,Σ), where D is a database and Σ is a finite set of EGDs. It is consistent if D ⊧ Σ, otherwise it is inconsistent.

Query language.

The query language we consider is non-recursive safe Datalog with negation. This choice will ease presentation of our approximation algorithm.

A (positive) rule is of the form p(x) ← φ(x,y), γ(z), where there are no nulls, p(x) is an atom (whose variables are x), φ(x, y) is a conjunction of atoms (whose variables are x and y), γ(z) is a conjunction of expressions (whose variables are z) of the form t = t′ or t ≠ t′ with t, t′ ∈ Const ∪Var, and z ⊆ x ∪ y. W.l.o.g. we assume that there cannot be multiple occurrences of the same variable in φ(x,y)-so equalities must be made explicit in γ(z).

A (negative) rule is of the form p(x) ← p′ (x),¬p′′ (x), where p(x), p′ (x), and p′′ (x) are atoms without nulls. W.l.o.g. we assume that there cannot be multiple occurrences of the same variable in p′ (x).

In the rules above, p(x) is called the head of the rule, and φ(x, y), γ(z) (resp. p′ (x), ¬p′′ (x)) is called the body.

A program P is a finite set of rules. The predicate graph of P is a directed graph whose vertices are the predicates appearing in P , and there is a directed edge from a predicate p′ to a predicate p if there is a rule in P where p′ appears in the body and p appears in the head. As we consider non-recursive Datalog, the predicates of P can be ordered into a sequence ⟨p1, . . . , pn⟩ according to a topological sorting of the predicate graph. Given a predicate p appearing in P , we use P[p] to denote the set of all rules in P having p in the head.

The immediate consequence operator TP of a program P is defined as follows. For every database D,

TP (D) = D ∪ {ν(p(x)) ∣ there exist a valuation ν and a rule p(x) ← φ(x, y), γ(z) of P s.t. ν(φ(x, y)) ⊆ D and ν ⊧ γ(z)} ∪ {ν(p(x)) ∣ there exist a valuation ν and a rule p(x) ← p′ (x), ¬p′′ (x) of P s.t. ν(p′ (x)) ∈ D and ν(p′′ (x)) ∉ D}.

Given a database D and a program P , we define:

A query Q is a pair (P, p), where P is a program and p is a predicate. The result of evaluating Q on a database D is Q(D) = {p(t) ∣ p(t) ∈ CN(P,D)}.

4 Repairing and Querying Inconsistent KBs

In this section, we present our notion of repair and analyze the computational complexity of two central problems: repair checking and consistent query answering.

We start by defining the EGDs we consider. Let Σ be a set of EGDs. An argument of Σ is an expression of the form p[i], where p is an n-ary predicate appearing in Σ and 1 ≤ i ≤ n.

Definition 1 (Argument and dependency graphs). The argument graph of a set Σ of EGDs is a directed graph GΣ = (V,E), where V is the set of all arguments of Σ, and E contains a directed edge from p[i] to q[j] labeled σ iff there is an EGD σ ∈ Σ such that:

• the body of σ contains an atom p(t1, . . . , tn) such that either ti is a constant or ti is a variable occurring more than once in the body of σ, and
• the body of σ contains an atom q(u1, . . . ,um) such that uj is a variable also appearing in the head of σ.

The dependency graph of Σ is a directed graph ΓΣ = (Σ, Ω), where Ω is the following set:

We say that Σ is acyclic if its dependency graph is acyclic.

In the following, we write σi < σj if (σi,σj) ∈ Ω or there is σk such that σi < σk and σk < σj.

Example 5. Consider the following set of EGDs Σ:

GΣ has two edges: one from works[1] to works[2] labeled σ1, and another one from works[2] to works[3] labeled σ2. Then, ΓΣ has only the edge (σ1, σ2). Thus, Σ is acyclic.

In the rest of the paper we consider acyclic sets of EGDsso, from now on, Σ is understood to be acyclic. Even if the tools developed in the paper can be generalized to arbitrary EGDs, we focus on acyclic sets because for them we can easily compute a compact representation of all repairs in polynomial time. This is particularly important for our purpose of developing polynomial time approximation algorithms.

Before introducing our notion of repair, we provide some intuitions. As already mentioned, it is based on updating values within facts. Specifically, we adopt a chase-like procedure that acts as follows: whenever an EGD ϕ(x) → xi = xj is not satisfied by a set of facts ν(ϕ(x)) (for some valuation ν), and thus ν(xi) ≠ ν(xj), then either ν(xi) replaces ν(xj) or vice versa. A repair is obtained through an exhaustive application of this repair step guaranteeing that the set of changes is minimal. Note that there is a non-deterministic choice to be made when updating values, and this may lead to multiple repairs.

By enforcing σ1 into the first two facts, either cs or math can be chosen as john's department. If the latter is chosen, then the database D′ below is obtained.

Suppose now that σ2 is enforced into the last two facts of D′ . Then, either rome or sydney can be chosen as math's city. If the former is chosen, then the database D′′ below is obtained.

No further dependency enforcement is applicable at this point and thus D′′ is a repair.

Notice that it might be possible to restore consistency in other different ways. For instance, in the first step of the example above, one may modify the employee names. However, we do not consider this option because it is unclear which (different) values should be assigned (any constant in Const is a candidate value). For instance, john in the first fact might be replaced with rome, but this is somewhat arbitrary and indeed does not make much sense. In contrast, our repair strategy chooses candidate values that are in sense "justified" by the content of the database (e.g., in the example above, john works for either the cs or the math department). Moreover, when EGDs are key dependencies, the aforementioned way of restoring consistency may lead to the introduction of entities that are not meaningful. Indeed, our choice has been made by different approaches relying on value updates (e.g., [Bohannon et al., 2005]).

The computation of repairs as informally described above is quite involved in that, when applying a repair step, we have to check that the current database has not been previously obtained (to avoid infinite repair steps) and check minimality of the changes performed. In the following, we show how to deal with such issues and compute repairs efficiently.

When repairing inconsistent databases, conditional instances can be used to keep track of which values must be equal and which constants can be assigned to nulls. For instance, in Example 6 above, after the last dependency enforcement, we have to make sure that the last column contains the same city (which can be either rome or sydney).

Below we introduce the technical definitions, starting with the notion of a repair step.

Definition 2 (Repair step). Let ⟨I,Φ⟩ be a CI, Σ a set of EGDs, and σ an EGD ϕ(x) → xi = xj ∈ Σ. Let h be a homomorphism s.t. h(ϕ(x)) ⊆ h(I), h ⊧ Φ, and h(xi) ≠ h(xj ).

Moreover, let ⊥m be a fresh null and ⟨I ′ ,Φ′ ⟩ the CI obtained from ⟨I,Φ⟩ as follows:

1. for each fact p(u1, ...,un) in I, if ϕ(x) contains an atom p(t1, ..., tn) s.t. h(p(t1, ..., tn)) = h(p(u1, ...,un)), then for every 1 ≤ k ≤ n, if tk ∈ {xi, xj},
2. replace uk in p(u1, ...,un) with ⊥m;
3. if uk ∈ Null, replace every occurrence of uk elsewhere with ⊥m;

Intuitively, a repair step enforces an EGD that is not satisfied by the knowledge base.

A repair sequence of a knowledge base (D,Σ) is a (possibly empty) finite sequence of repair steps Ci σi ,hi leftrightline→ Ci+1 (0 ≤ i < m) such that C0 = ⟨D, true⟩ and σi ∈ Σ for every i. We also say that the repair sequence is from C0 to Cm. We call Cm the result of the repair sequence. Also, we say that the repair sequence is maximal if there does not exist a repair step of the formCm σm,hm leftrightline→ Cm+1.

It is easy to see that for each repair step ⟨I,Φ⟩ σ,h leftrightline→ ⟨I ′ , Φ′ ⟩, if h′ is a homomorphism s.t. h′ ⊧ Φ′ , then it assigns constants to nulls as dictated by Φ′ (see item 2 of Definition 2). Thus, all h′ satisfying Φ′ yield the same database h′ (I ′ ). For a conditional instance (I, Φ) obtained by means of a repair sequence, we use the notation Φ(I) to denote the database derived from I by iteratively replacing nulls with constants or other nulls as dictated by Φ.

For ease of presentation, we assume that one can keep of a given fact f in the database during the repair process despite the value changes. Thus, we use D[f, i] to denote the i-th term of a fact f in a database D. Given a repair sequence S from C0 = (D, true) to Cm = (Im,Φm), we define the set of changes made by S as update(S) = {(f, i) ∣ D[f, i] ≠ Φm(Im)[f, i]}, where f is a fact of the database.

No further repair steps are applicable at this point. Notice that ⊥3 = sydney can be deleted from the condition of C3 because it does not play a role anymore. A repair is obtained from C3 by replacing every occurrence of ⊥1 with math, and every occurrence of ⊥4 with rome.

Definition 3 (Repair). A repair for a knowledge base K = ⟨D,Σ⟩ is a database Φ(J) such that there exists a maximal repair sequence S of K from ⟨D, true⟩ to ⟨J,Φ⟩ and update(S) is minimal w.r.t. ⊆.

We use repair(D,Σ) to denote the set of all repairs of a knowledge base (D,Σ). The following simple proposition states that every repair is indeed consistent.

Proposition 1. Let (D,Σ) be a knowledge base. For every D′ ∈ repair(D,Σ), D′ ⊧ Σ.

The consistent answers to a query are defined in the standard way as follows.

Definition 4 (Consistent Query Answers). Let (D,Σ) be a knowledge base and Q a query. The consistent answers to Q over (D, Σ) are

In the context of managing inconsistent knowledge bases, two fundamental problems are repair checking and consistent query answering, which are defined as follows. Let (D, Σ) be a knowledge base, D′ a database, Q a query, and f a fact of constants. Then, the following two problems are defined:

• repair checking: decide whether D′ ∈ repair(D,Σ);
• consistent query answering: decide whether f ∈ Q(D,Σ).

Below we show that the first problem is in PTIME and the second one is coNP-complete All the complexity results in this paper are in the data complexity, that is, the query and the EGDs are fixed.

Theorem 2. Repair checking is in PTIME.

Proof. (Sketch) Let (D,Σ) be a knowledge base and D′ a database. As stated in Theorems 4 and 5 reported in the next section, it is possible to compute in polynomial time a CI C = ⟨I,Φ⟩ such that pw(C) = repair(D,Σ). After C is computed, for each null ⊥i in I, replace every occurrence of ⊥i in I and Φ with the corresponding constant in D′-if there are different constants corresponding to (different occurrences of) ⊥i, then answer 'no'. After that, if the updated instance I is equal to D′ and the updated condition Φ is true, then answer 'yes', otherwise answer 'no'. Clearly, the entire process can be carried out in polynomial time.

Theorem 3. Consistent query answering is coNP-complete.

Proof. (Sketch) Membership. Let (D,Σ) be a knowledge base, Q a query, and f a fact of constants. The complementary problem is in NP. In fact, we can guess a database D′ and verify that (i) D′ ∈ repair(D,Σ) and (ii) f ∉ Q(D′ ). By the definition of repair, the size of D′ is linear in the size of D. By Theorem 2, condition (i) can be verified in polynomial time, and obviously condition (ii) too.

Hardness. We reduce 3DNF TAUTOLOGY to our problem. Let φ be a 3DNF formula d1 ∨ ... ∨ dm over variables X = {x1, ...,xn}. For every literal ℓ in φ, we define var(ℓ) = xi if ℓ = xi or ℓ = ¬xi, tval(ℓ) = t if ℓ = xi, and tval(ℓ) = f if ℓ = ¬xi, where t, f, and the xi's are constants.

We define Dφ as follows. For each disjunct di = (ℓ1 ∧ ℓ2 ∧ ℓ3), 1 ≤ i ≤ m, Dφ contains the following facts:

Then, Σ contains the following EGDs:

It can be easily verified that Σ is acyclic.

Finally, Q = (P, sat), where P contains the following rule:

It can be shown that φ is a tautology iff sat() ∈ Q(Dφ,Σ).

Indeed, coNP-hardness holds even for Boolean conjunctive queries. In the next section we introduce the notion of a universal repair, which is a compact representation of all repairs for a given knowledge base, and can be computed in polynomial time.

5 Universal Repair

In this section, we show how to compute a conditional instance U, called universal repair, that represents all repairs of a knowledge base, that is, the possible worlds of U are exactly the repairs. As shown in the following, such a representation will prove to be a valuable tool for query answering.

Roughly speaking, we generalize the repair step introduced in the previous section in order to keep track of all possible choices, and when each choice should be applied.

Any conjunction of atoms ϕ(x) in the body of an EGD can be rewritten as follows:

• every occurrence of a constant c in ϕ(x) is replacedwith a fresh variable z and (z = c) is added to the conjunction;
• for every variable occurring n > 1 times in ϕ(x), replace n-1 occurrences with n-1 fresh variables x2, ..., xn and add (x = x2) ∧ ... ∧ (x = xn) to the conjunction.

As an example, r(x, y, x) ∧ s(x, a, a), where a is a constant, can be rewritten into r(x, y, x2) ∧ s(x3, za, z′a ) ∧ (x = x2) ∧ (x = x3) ∧ (za = a) ∧ (z′a = a). In the following definition, we assume that the body of every EGD has been rewritten as above, and thus it is of the form ϕ(x) ∧ eq(x′ ), where ϕ(x) is a conjunction of atoms (with no constants and no multiple occurrences of the same variable) and eq(x′ ) is a conjunction of equalities over variables x′ ⊆ x.

Definition 5 (Universal repair step). Let C = ⟨I,Φ⟩ be a CI and σ an EGD ϕ(x)∧eq(x′ ) → xi = xj . Let h be a homomorphism s.t. h(ϕ(x)) ⊆ I and for which there exists a valuation ν s.t. ν ⊧ h(eq(x′ )), ν ⊧ Φ, and ν(h(xi)) ≠ ν(h(xj)).

Moreover, let ⊥ℓ and ⊥m be two fresh nulls, and ⟨I ′ , Φ′ ⟩ be the CI obtained from ⟨I, Φ⟩ as follows:

1. for each fact p(u1, ...,un) in I, if ϕ(x) contains an atom p(t1, ..., tn) s.t. ν(h(p(t1, ..., tn))) = ν(p(u1, ...,un)), then for every 1 ≤ k ≤ n, if tk = xi or (tk = xi) appears in eq(x′ ) (resp. tk = xj or (tk = xj) appears in eq(x′ )), then replace uk in p(u1, ..., un) with ⊥ℓ (resp. ⊥m);
2. Φ′ = Φ ∧ φ, where φ is defined as follows: (h(eq (x′ )) ⇒ ((⊥m =⊥ℓ) ∧ (⊥ℓ =h(xi) ∨ ⊥m =h(xj )))) ∧ (¬(h(eq(x′ ))) ⇒ (⊥ℓ = h(xi) ∧ ⊥m =h(xj )));
3. for each uk of Item 1 above, if uk ∈ Null, replace every occurrence of uk with ⊥ℓ (resp. ⊥m) in both the current instance and condition Φ′ .

We say that ⟨I,Φ⟩ σ,h leftfootline→ ⟨I ′ ,Φ′ ⟩ is a universal repair step.

In the previous definition, h is a homomorphism used to map ϕ(x) into I, while ν is a valuation used to check if h(ϕ(x)) may violate σ, that is, ν(h(ϕ(x))) are admissible facts (cf. ν ⊧ Φ) that satisfy the join conditions in the body of σ (cf. ν ⊧ h(eq(x′ ))) but do not satisfy the head condition (cf. ν(h(xi)) ≠ ν(h(xj))).

A universal repair sequence of a knowledge base (D,Σ) is a (possibly empty) finite sequence of universal repair steps Ci σi ,hi leftfootline→ Ci+1 (0 ≤ i < m) such that C0 = ⟨D, true⟩ and σi ∈ Σ for every i. We call Cm the result of the universal repair sequence. Also, we say that the repair sequence is maximal if there does not exist a universal repair step of the form Cm σm,hm leftfootline→ Cm+1. A universal repair sequence is said to be ordered if for each Ci σi ,hj leftrightline→ Ci+1 there is no Cj σj ,hi leftrightline→ Cj+1 such that j > i and σj < σi (intuitively, EGDs in Σ must be considered according to a topological sorting of ΓΣ). If C is the result of an ordered maximal universal repair sequence, then C is called a universal repair.

Example 8. Consider the database of Example 6 and the set of EGDs of Example 5. After the application of σ1 to the first two facts we get the following conditional instance:

Φ1

where Φ1 is as follows:

By applying σ2 to the first and third facts, we get:

where Φ2 is as follows:

By applying σ2 to the first two facts, we get:

where Φ3 is as follows:

Then, ⊥3 is replaced with ⊥5 everywhere, that is, in both Φ2 and Φ3, yielding new conditions Φ′2 and Φ′3 . The result of this step is the CI consisting of the instance above and the condition Φ1 ∧ Φ′2 ∧ Φ′3 .

As no further universal repair step can be applied, the conditional instance above is a universal repair.

The following theorems say that all the universal repairs of a knowledge base are equivalent in that they "represent" its repairs and computing one of them can be done in polynomial time.

Theorem 4. Let U be a universal repair of a knowledge base (D,Σ). Then, pw(U) = repair(D,Σ).

Theorem 5. Computing a universal repair is in PTIME.

The main idea behind the proof of the previous theorem is to apply universal repair steps according to a topological sorting of the dependency graph of Σ.

6 Query Evaluation

In this section, we show how to evaluate queries over universal repairs and keep track of provenance information. This will be used later on to develop an approximation algorithm. In order to do that, we need to extend conditional instances to allow individual conditions for facts too.

A conditional fact is a pair ⟨p(t),φ⟩, where p(t) is a fact and φ is a condition, also called local condition.

An extended conditional instance (ECI) is a pair ⟨E,Φ⟩, where E is a finite set of conditional facts and Φ is a condition, which we also call global condition. Given a valuation ν, we define ν(E) = {ν(p(t)) ∣ ⟨p(t),φ⟩ ∈ E and ν ⊧ φ}. Thus, ν(E) is the database obtained from E by applying ν to every fact and keeping only the facts whose condition is satisfied by ν. The possible worlds of an ECI G = ⟨E, Φ⟩ are pw(G) = {ν(E) ∣ ν is a valuation s.t. ν ⊧ Φ}.

We now define how to evaluate queries over ECIs. To this end, we generalize the immediate consequence operator TP (cf. Section 3) so as to perform a "conditional" evaluation of a query in the presence of conditional facts. We point out that our conditional evaluation is a slight variant of the one for conditional tables [Grahne, 1991]. Below we use (t1, ..., tn) = (u1, ..., un) as a shorthand for ⋀ni=1 (ti = ui).

With a slight abuse of notation, given a program P we overload TP so that when its input is a set E of conditional facts, then TP(E) = E ∪E′ , where E′ is the following set of conditional facts:

Then, CN(P,E) = T n P (E), where T iP is defined in exactly the same way as in Section 3.

It can be easily verified that the conditional evaluation above can be carried out in polynomial time. The main reason is that the immediate consequence operator TP above extends the classical one by just adding conditions of polynomial size to facts, so the time complexity remains polynomial.

Proposition 6. Given a program P and a finite set E of conditional facts, computing CN(P,E) is in PTIME.

Given two conditions φ,φ′ , we write φ ⊧ φ′ if for every valuation ν, if ν ⊧ φ, then ν ⊧ φ′ . Below we define the certain answers to a query over an extended conditional instance.

Definition 6. Let G = ⟨E,Φ⟩ be an ECI and Q = (P, p) be a query. The certain answers to Q over G are defined as follows:

Thus, to compute the certain answers to Q over G we need to compute CN(P,E) and check for which conditional facts Φ ⊧ φ holds true. The last entailment checking can be carried out by rewriting the formula as a propositional formula and using SAT solvers [Gomes et al., 2008]. Satisfiability solvers are becoming increasingly efficient and effective in solving large satisfiability problems and, despite the worst-case exponential run time of all known algorithms, they are very efficient in solving hard problems with millions of variables and tens of millions of constraints.

The tools developed thus far will be exploited in the next section to devise an approximation algorithm.

7 Approximation Algorithm

In light of Theorem 3, we develop a polynomial time approximation algorithm to compute a sound (but possibly incomplete) set of consistent query answers.

The basic idea of our approximation algorithm is as follows. Given a knowledge base and a query, we first compute a universal repair U of the knowledge base, and then transform U into an ECI Utrue where each fact is associated with the trivial condition true. After that, the query is "conditionally" evaluated over Utrue (i.e., as described in the previous section). The result is a set of conditional facts, whose conditions are evaluated together with the condition of Utrue in order to determine a sound (but possibly incomplete) set of consistent query answers (we will illustrate the entire process in Example 9). For positive queries, a simple approximation can be obtained by deleting facts containing nulls from Utrue and ignoring its global condition.

First, we need some auxiliary definitions. Given a condition Φ and two nulls ⊥i,⊥j ∈ Null, we write ⊥i ≈Φ ⊥j if ⊥i = ⊥j (or ⊥j = ⊥i) appears in Φ. Then, ≈∗Φ is the reflexive and transitive closure of ≈Φ. Given a term t ∈ Const ∪ Null and a condition Φ, we denote by domΦ(t) the domain of t w.r.t. Φ, defined as follows: domΦ(c) = {c} if c ∈ Const, whereas domΦ(⊥i) = {c ∣ ⊥i ≈∗Φ ⊥k and ⊥k = c appears in Φ} if ⊥i ∈ Null. Intuitively, domΦ(⊥i) is a set of possible values that ⊥i might assume in some repair.

We assume the strict ordering false < unknown < true, and ¬true = false, ¬false = true, and ¬unknown = unknown. Given two conditions ϕ and Φ, we define evalΦ(ϕ) as follows:

• evalΦ((ti ≠ tj)) = ¬evalΦ((ti = tj))
• evalΦ((ϕ1 ∧ϕ2)) = min{evalΦ(ϕ1), evalΦ(ϕ2)}.

• evalΦ((ϕ1 ∨ϕ2)) = max{evalΦ(ϕ1), evalΦ(ϕ2)}.
• evalΦ((¬ϕ)) = ¬evalΦ(ϕ)
• evalΦ(v) = v for v ∈ {true, unknown, false}.

The following definition introduces the approximate evaluation of a query over an extended conditional instance.

Definition 7. Let G = ⟨E,Φ⟩ be an ECI and Q = (P, p) be a query. The approximate answers to Q over G are:

A conditional instance C = ⟨I, Φ⟩ can be "lifted to" an ECI by setting all local conditions to true. We denote by Ctrue the ECI ⟨{⟨p(t), true⟩ ∣ p(t) ∈ C},Φ⟩.

The evaluation technique of Definition 7 indeed provides a way to compute a sound (but possibly incomplete) set of consistent query answers, in polynomial time.

Definition 8. Let (D,Σ) be a knowledge base andQa query. The approximate consistent answers to Q over (D,Σ) are ̃Q(D,Σ) = approx(Q,Utrue), where U is a universal repair of (D,Σ).

Example 9. Consider the knowledge base of Example 1 and the query Q = ⟨P, diffCity⟩, asking for the pairs of departments located in different cities, where P consists of the rule:

A universal repair, say U, is shown in Example 3. The first step of our approach consists of converting U into an ECI Utrue by setting all local conditions to true. Thus, Utrue is as follows:

The conditional evaluation of Q over Utrue gives the following set of conditional facts:

As domΦ(⊥1) = {rome, sydney}, the approximate consistent answers are diffCity(cs, math) and diffCity(math, cs), which are indeed consistent query answers.

The following theorems state soundness of our approach and its complexity, which is in PTIME (data complexity).

Theorem7. Let (D,Σ) be a knowledge base and Q a query. Then, ̃Q(D,Σ) ⊆ Q(D,Σ).

Theorem8. Let (D,Σ) be a knowledge base and Q a query. Computing ̃Q(D,Σ) is in PTIME.

Proof. (Sketch) It follows from Theorem 5, Proposition 6, and because evalΦ(ϕ) can be evaluated in PTIME.

We conclude by comparing our approach with two wellknown approximation schemes that have been developed in the query answering inconsistency-tolerant area, namely the intersection of repairs (IAR) and the intersection of closed repairs (ICR) semantics [Lembo et al., 2010; Bienvenu et al., 2014]. The former semantics consists of querying the intersection of all repairs, while the second one consists of querying the intersection of the closure of all repairs. In our setting, since we do not consider tuple-generating dependencies, the two semantics coincide.

As stated in the following theorem, for every positive query (i.e., only positive rules and equalities are allowed), our approximation algorithm provides at least as many answers as IAR (and ICR).

Theorem 9. Let (D,Σ) be a knowledge base and Q a positive query. Then, Q(D∗ ) ⊆ ̃Q(D,Σ), where D∗ = ⋂{D′ ∣ D′ ∈ repair(D,Σ)}.

To show a simple case where our approximation algorithm yields strictly more consistent query answers, consider the knowledge base of Example 1, whose repairs are reported in Example 2. Consider also the query asking for the employees' names. Under the IAR semantics, the intersection keeps only the first fact of the original knowledge base, and thus the other two facts are lost altogether. So the only query answer is john. On the other hand, the universal repair (cf. Example 3) is much more informative: we still have the first fact of the original knowledge base, but we also have the other two facts, where consistent values are unchanged and thus preserved. Our approximation algorithm returns both john and mary.

As a further example, consider Example 6. The intersection of all repairs is empty. On the other hand, the universal repair (cf. Example 8) has valuable information, which again can be profitably exploited for (approximate) query answering.

8 Conclusion

We proposed a framework for query answering over inconsistent KBs based on (i) a notion of repair allowing values within facts to be updated, (ii) a compact representation of all repairs, (iii) an approximation algorithm to compute underapproximations of consistent query answers.

As a direction for future work, we plan to investigate further approximation algorithms based on different conditions' evaluations. Another issue to be investigated is the generalization of our framework to more general classes of dependencies, such as TGDs or arbitrary EGDs. One way of dealing with TGDs is by inserting new facts. Interestingly, by inserting facts with nulls (in a Chase-like manner) into a universal repair we can get a compact representation of all possible insertions. This also poses the issues of combining different repair primitives, such as fact updates and fact insertions (fact deletions might be considered as well).