S Lawomir Staworko
email: slawomir.staworko@inria.fr

Jan Chomicki
email: chomicki@cse.buffalo.edu

Steve Donald

Mary Donald

Consistent Query Answers in the Presence of Universal Constraints ⋆

Keywords: Inconsistent databases, consistent query answers, repair checking, database repairing

The framework of consistent query answers and repairs has been introduced to alleviate the impact of inconsistent data on the answers to a query. A repair is a minimally different consistent instance and an answer is consistent if it is present in every repair. In this article we study the complexity of consistent query answers and repair checking in the presence of universal constraints.

We propose an extended version of the conflict hypergraph which allows to capture all repairs w.r.t. a set of universal constraints. We show that repair checking is in PTIME for the class of full tuple-generating dependencies and denial constraints, and we present a polynomial repair algorithm. This algorithm is sound, i.e. always produces a repair, but also complete, i.e. every repair can be constructed. Next, we present a polynomial-time algorithm computing consistent answers to ground quantifier-free queries in the presence of denial constraints, join dependencies, and acyclic full-tuple generating dependencies. Finally, we show that extending the class of constraints leads to intractability. For arbitrary full tuple-generating dependencies consistent query answering becomes coNP-complete. For arbitrary universal constraints consistent query answering is Π p 2 -complete and repair checking coNPcomplete.

Introduction

Traditionally, the consistency of a database with a set of integrity constraints was maintained by a DBMS [START_REF] Ramakrishnan | Database Management Systems[END_REF]. While integrity constraints continue to express important properties of the stored data, in many novel database applications enforcing the consistency becomes problematic. For example, in the scenario of data integration even if the sources are separately consistent, together they may contribute conflicting data. Because data sources are often autonomous and their contents cannot be altered, the consistency cannot be restored by means of data manipulation. Consistency violations occur naturally also in the context of long running data manipulations, delayed updates on data warehouses, and legacy databases. Finally, consistency enforcement may be deactivated for efficiency reasons. At the same time, the semantic properties expressed by integrity constraints often influence the way the user formulates her queries. Hence, if the database is inconsistent, evaluating the queries may yield incorrect and misleading answers.

To address the problem of the potential impact of inconsistencies on query results Arenas et al. have proposed the framework of repairs and consistent query answers [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF]. A repair is a consistent database instance minimally different from the original one. The consistent query answers are the answers present in every repair. Intuitively, the repairs represent all possible ways to restore consistency in the database and an answer is consistent if it is obtained regardless of the way the conflicts are resolved, i.e. the answer that is not affected by the inconsistencies. This framework has served as a foundation for most of the subsequent work in the area of querying inconsistent databases (for the surveys of the area, see [START_REF] Bertossi | Query answering in inconsistent databases[END_REF][START_REF] Bertossi | Consistent query answering in databases[END_REF][START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF][START_REF] Chomicki | Consistent query answering: Five easy pieces[END_REF][START_REF] Fan | Dependencies revisited for improving data quality[END_REF]).

Example 1 We consider a database that stores information on the occurrence of a genetically inherited disease neurofibromatosis (NF) causing tumors of the nervous tissue. NF is an autosomal dominant disorder, which means that only one mutated gene needs to be present in the genome of an affected person. Typically, this gene is inherited from one of the parents. 1 The schema of the database contains two relations: N F (N ame, Diag) and P arent(N ame, Child), where the underline indicates the (primary) key of a Donald is diagnosed with NF while neither of his parents are. This violation can be resolved in three ways:

(1) By inserting a tuple with a positive diagnosis for one of the Donald's parents. Because of the key dependency, this creates a conflict with the already existing tuple which is consequently deleted. This yields the following repairs: (2) By removing one of the tuples of P arent relation, which gives the following repairs: (3) By removing the tuple with the diagnosis of Donald giving the following repair:

I ′ 1 = {N F (Steve,
I ′ 3 = {N F (Steve,
I ′ 5 = {N F (Steve, no), N F (M ary, no), P arent(Steve, Donald), P arent(M ary, Donald)}.

Consider now the query N F (Steve, no) asking if Steve is not diagnosed with NF. The answer to this query in the instance I is true. However, true is not the consistent query answer because of the repair I 1 (which indicates that the diagnosis of Steve may be incorrect).

We note that the framework of consistent query answers is parametrized by the notion of minimality used to define repairs. The original notion uses the symmetric set difference (between databases as sets of tuples) and set inclusion, i.e. the repairs are obtained by deleting and inserting a minimal set of tuples. This notion is most commonly considered in the literature and it is used in this paper. Other investigated notions of minimality use asymmetric set difference [START_REF] Cali | On the decidability and complexity of query answering over inconsistent and incomplete databases[END_REF] and the cardinality of the symmetric difference [START_REF] Arenas | Answer sets for consistent query answering in inconsistent databases[END_REF][START_REF] Lopatenko | Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics[END_REF]. Finally, various notions of minimality have been considered to accommodate repairs obtained by attribute value modification [START_REF] Lopatenko | Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics[END_REF][START_REF] Bertossi | Complexity and approximation of fixing numerical attributes in databases under integrity constraints[END_REF][START_REF] Lopatenko | Logic based data integration[END_REF][START_REF] Bohannon | A cost-based model and effective heuristic for repairing constraints by value modification[END_REF][START_REF] Wijsen | Condensed representation of database repairs for consistent query answering[END_REF].

It was observed very early that the number of possible repairs may be exponential even if we consider one functional dependency [START_REF] Arenas | Scalar aggregation in inconsistent databases[END_REF]. A naïve approach to compute consistent query answers by materializing all repairs and consequently evaluating the query in every repair may thus be simply impractical. Consequently, to establish the tractability of database repairing and computing consistent query answers two fundamental decision problems have been investigated: (i) repair checking -checking if a given database instance is a repair, and (ii) consistent query answering -checking if an answer to a query is present in every repair. Most of the research in this area uses the notion of data complexity, commonly used to study tractability of computing answers in relational databases [START_REF] Vardi | The complexity of relational query languages[END_REF]. It allows to express the complexity of the problems in terms of the database size only: the set of integrity constraints and the query are assumed to be fixed. We note that the study of complexity of the two decision problems is motivated by the belief that tractable decision algorithms can be converted into efficient algorithms that compute consistent query answers and construct repair(s) of an inconsistent database. This belief is validated, for example, by existing polynomial-time algorithms where decision problems play a central role in the computation of consistent query answers [START_REF] Chomicki | Hippo: A system for computing consistent answers to a class of SQL queries[END_REF][START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF].

The problems of repair checking and consistent query answering are parameterized by the class of integrity constraints. Denial constraints allow the user to specify sets of tuples that cannot be simultaneously present in the database because they create a conflict. This class of constraints includes equality-generating dependencies, thus also functional dependencies, and exclusion constraints [START_REF] Abiteboul | Foundations of Databases[END_REF]. The standard definition of denial constraints allows to use conjunctions of = and = comparisons to relate the values of the tuples creating conflicts. A more general version of denial constraints allows using any Boolean combination of formulas using =, =, <, ≤, >, and ≥ [START_REF] Baudinet | Constraint-generating dependencies[END_REF]. This version has also been studied in the context of consistent query answers [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]. There, the authors proposed the conflict hypergraph to store all conflicts present in the database and subsequently use it to construct repairs and efficiently compute consistent query answers.

Universal constraints generalize denial constraints by allowing to express conflicts created not only by the presence of some tuples but also by simultaneous absence of other tuples. This class of constraints contains full tuple-generating dependencies (full TGDs) which have been thoroughly studied in the context of relational databases [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Maher | Constrained dependencies[END_REF][START_REF] Maher | Chasing constrained tuple-generating dependencies[END_REF]. Full TGDs contain an important class of join dependencies (JDs), and thus also its subclass multi-valued dependencies (MVDs), which are frequently used in the in the setting of denormalized databases [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Ramakrishnan | Database Management Systems[END_REF]. In this context, the constraints are typically not actively enforced which permits the occurrence of insertion/deletion/update anomalies.

Example 2 Consider a denormalized database that stores the information about locations and the offer of different chains of coffee shops. The schema is CoffeeShop(Chain, Location, Beverage). The list of beverages offered by a particular chain is the same in every coffee shop, which is expressed with the following join dependency: Espresso is offered at Starbucks on Delaware Avenue but not at Starbucks on Main Street. This instance has three repairs:

CoffeeShop ✶: [{Chain, Location}, {Chain, Beverage}].
(1) The first corresponds to the scenario where Espresso has been added to the offer of Starbucks but the change has not been propagated properly. This repair is obtained by inserting the tuple CoffeeShop(Starbucks, M ain Str., Espresso).

(2) The second corresponds to the scenario where Espresso has been removed from the offer of Starbucks but the change has not been propagated properly. This repair is obtained by deleting the tuple CoffeeShop(Starbucks, Delaware Ave., Espresso).

(3) The third corresponds to the scenario where the coffee shop located on Main Street is being closed. This repair is obtained by deleting the tuple CoffeeShop(Starbucks, M ain Str., Latte).

Now, consider the query CoffeeShop(Starbucks, Delaware Ave., Latte). true is the consistent answer to this query because it is true in every repair. If we consider the query CoffeeShop(Starbucks, Delaware Ave., Espresso), we note that the answer to this query is true in the original answer. We observe, however, that true is not the consistent query answer because the query is not true in every repair.

The complexity of repair checking and consistent query answering in the presence of general universal constraints has not been thoroughly studied. Previous research conducted in this area shows that computing consistent query answers is:

• in PTIME for the class of binary universal constraints and a restricted class of quantifier-free queries [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF]. • in PTIME for the class of denial constraints and quantifier-free queries [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF].

• in PTIME when at most one primary key per relation is present and the queries belong to a restricted class of conjunctive queries C f orest [START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF][START_REF] Fuxman | Efficient Query Processing Over Inconsistent Databases[END_REF][START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF]. • coNP-complete for primary keys and arbitrary conjunctive queries [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]. • Π 2 p -complete for arbitrary sets of functional and inclusion dependencies [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF], when repairs are constructed using deletions only.

• undecidable for arbitrary sets of functional and inclusion dependencies [START_REF] Cali | On the decidability and complexity of query answering over inconsistent and incomplete databases[END_REF].

We remark that the class of universal constraints captures only full inclusion dependencies and in the paper we do not consider general inclusion dependencies.

In this paper we investigate computing consistent query answers and repairs in the presence of universal constraints. This research constitutes a continuation and substantial extension of [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]. Similarly to [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF] in the constraint definition we allow any Boolean combination of atomic formulas that use the binary relations: =, =, <, ≤, >, and ≥. We propose an extended version of the conflict hypergraph whose hyperedges span both tuples present and absent in the database. The size of the extended conflict hypergraph is still polynomial in the size of the database and every repair corresponds to a maximal independent set. Although, the converse correspondence is not necessarily true, i.e. not every maximal independent set defines a repair, we consider the extended conflict hypergraph to be a compact representation of all repairs.

Next, we study the computational implications of universal constraints. In this paper we show that:

• The complexity of repair checking is: -in PTIME for arbitrary full tuple-generating dependencies and denial constraints. Consequently, we present a polynomial database repairing algorithm that is both sound (always constructing a repair) and complete (able to construct every repair). -coNP-complete for arbitrary universal constraints.

• The complexity of consistent query answering is: -in PTIME for quantifier-free closed queries in the presence of join dependencies, acyclic full tuple-generating dependencies, and denial constraints. -coNP-complete for atomic queries in the presence of arbitrary full tuplegenerating dependencies and denial constraints. -Π 2 p -complete for atomic queries in the presence of arbitrary universal constraints.

The paper is organized as follows. Section 2 contains basic notions and definitions. In Section 3 we present the extended conflict hypergraph, study its properties, and investigate basic properties of the framework. In Section 4 we study the complexity of repair checking in the presence of full tuple-generating dependencies and we present a database repairing algorithm. In Section 5 we investigate the complexity of consistent query answering in the presence of full tuple-generating dependencies. In Section 6 we investigate the complexity of consistent query answering and repair checking in the presence of arbitrary universal constraints. In Section 7 we discuss related work. Section 8 contains final conclusions and the discussion of future work.

Preliminaries

A database schema S is a set of relation names of fixed arity (greater than 0) and we use R, P, . . . to denote relation names. Relation attributes are drawn from an infinite set of names U , and we use A, B, C, . . . to denote elements of U and X, Y, Z, . . . to denote finite subsets of U . For R ∈ S we denote the set of all attributes of R by attrs(R). Every element of U is typed and we consider only two disjoint infinite domains: Q (rationals) and D (uninterpreted constants). We assume that two constants are equal if and only if they have the same name, and we allow the standard built-in relation symbols = and = over D. We also allow the built-in relation symbols =, =, <, ≤, >, and ≥ with their natural interpretation over Q. We use these symbols together with the vocabulary of relational names S to build a first-order language L. An L-formula is:

• closed (or a sentence) if it has no free variables, • ground if it has no variables whatsoever, • quantifier-free if it has no quantifiers, • atomic if it has no quantifiers and no Boolean connectives.

Finally, a fact is an atomic ground L-formula and a literal is a fact or the negation of a fact.

Database instances are finite, first-order structures over the schema. Often, we will find it more convenient to view an instance I as the finite set of all facts satisfied by the instance

{R(t) | R ∈ S, I |= R(t)}.
In the sequel, we will denote tuples of variables by x, ȳ, . . ., tuples of constants by t, s, . . ., facts by p, q, r, . . ., quantifier-free formulas using only built-in predicates by ϕ, and instances by I, J, . . .

Integrity constraints

An integrity constraint is an L-sentence, i.e. a closed first-order L-formula. In this paper we consider the class of universal constraints, L-sentences of the form

∀x. ¬[R 1 (x 1 ) ∧ . . . ∧ R n (x n ) ∧ ¬P 1 (ȳ 1 ) ∧ . . . ∧ ¬P m (ȳ m ) ∧ ϕ(x)], (2)
where ϕ(x) is a quantifier-free formula referring to built-in relation names only and ȳ1 ∪ . . . ∪ ȳm ⊆ x1 ∪ . . . ∪ xn = x (this is a standard safety requirement [START_REF] Abiteboul | Foundations of Databases[END_REF]). Also, we make a natural assumption that n + m > 0. The constraint (2) will be often presented as:

R 1 (x 1 ) ∧ . . . ∧ R n (x n ) ∧ ϕ(x) → P 1 (ȳ 1 ) ∨ . . . ∨ P m (ȳ m ), (3)
where all the variables are implicitly universally quantified.

The class of universal constraints contains the following basic classes of integrity constraints:

(1) Full tuple-generating dependencies (full TGDs): universal constraints with one atom in rhs (m = 1). Often, the full TGDs considered in literature have a conjunction of atoms in rhs. We remark, however, that a multihead full TGD is equivalent to a set of single-head full TGDs [START_REF] Abiteboul | Foundations of Databases[END_REF]. (2) Join dependencies (JDs) commonly formulated as R ✶: [X 1 , . . . , X k ], where R is a relation name and X 1 , . . . , X k are subsets of attributes of R whose union contains all attributes of R. A common relational algebra definition is: R = π X 1 (R) ✶ . . . ✶ π X k (R). The equivalent full tuple-generating dependency is:

R(x 1 ) ∧ . . . ∧ R(x k ) ∧ 1≤i,j≤k xi [X i ∩ X j ] = xj [X j ∩ X i ] → R(ȳ),
where z[Y ] is the subvector of z that corresponds to the attributes in Y , and ȳ

⊆ x1 ∪ . . . ∪ xn such that ȳ[X i \ 1≤j<i X j ] = xi [X i \ 1≤j<i X j ] for i ∈ {1, . . . , k}. (3
) Denial constraints: universal constraints with no atoms in the rhs (m = 0):

R 1 (x 1 ) ∧ . . . ∧ R n (x n ) ∧ ϕ(x) → false.
(4) Functional dependencies (FDs) commonly formulated as R : X → Y , where X and Y are sets of attributes of R. An FD R : X → Y is expressed by the following denial constraint:

R(x 1 ) ∧ R(x 2 ) ∧ x1 [X] = x2 [X] ∧ ¬(x 1 [Y ] = x2 [Y ]) → false.
The following restriction will allow us to identify a tractable class of integrity constraints.

Definition 1 (Acyclic constraints) The dependency graph D(S, F ) of a set of universal constraints F is a directed graph whose set of vertices is the relational schema S and for any constraint (2) in F there is an edge from P j to R i for every i ∈ {1, . . . , n} and every j ∈ {1, . . . , m}. The set of constraints F is acyclic if D(S, F ) is an acyclic graph.

We also adapt the standard notions of height and depth of a node in a tree to (possibly cyclic) dependency graphs [START_REF] Cormen | Introduction to Algorithms[END_REF]. Given a dependency graph D(S, F ), the acyclic depth of a node R, denoted depth(R), is the maximal length of a directed acyclic path that ends in R, where the length of a path is the number of edges it comprises. The acyclic height of R, denoted height(R), is the maximal length of a directed acyclic path that originates in R. The acyclic height of D(S, F ) is maximum acyclic height of all node in D(S, F ). We note that both the acyclic height and acyclic depth of a node are bounded by the acyclic height of the dependency graph. The acyclic height of this graph is 3.

Database consistency is defined in the standard way.

Definition 2 Given a database instance I and a set of integrity constraints

F , I is consistent with F if I |= F in the standard model-theoretic sense; otherwise I is inconsistent.
We observe that because we do not allow relation names of arity 0 and we consider universal constraints satisfying the safety requirement, the constraint (2) can have negative atoms only if it has positive atoms as well, i.e. m > 0 implies n > 0. Therefore, the prerequisite of a constraint violation is the existence of some facts in the database. Consequently, if the instance is empty, then all the constraints are satisfied. We note this conforms to the behavior of typical SQL database management systems: an empty database satisfies any set of constraints expressed in SQL.

Queries

In this paper we deal only with closed queries, i.e. closed L-formulas. The query answers are Boolean: true or false. A query is atomic (quantifier-free) if the L-formula is atomic (quantifier-free, respectively). A conjunctive query is an existentially quantified conjunction of atomic L-formulas.

Definition 3 true is the answer to a closed query Q in an instance I if I |= Q; otherwise the answer to Q is false.

Repairs

Repairs are defined as consistent instances that are minimally different from the original one. The differences are measured in terms of the set of facts that need to be deleted and inserted. Because we view an instance as the set of facts, the (symmetric) difference ∆(I 1 , I 2 ) of the instances I 1 and I 2 is defined as

∆(I 1 , I 2 ) = I 1 \ I 2 ∪ I 2 \ I 1 .
Given an instance I, the relative proximity relation ≤ I on instances is defined as

I 1 ≤ I I 2 ⇐⇒ ∆(I, I 1 ) ⊆ ∆(I, I 2 ).
We note that ≤ I is a partial order and we write I 1 < I I 2 if I 1 ≤ I I 2 and

I 1 = I 2 .
Definition 4 ( [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF]) Given a set of integrity constraints F and database instances I and I ′ , we say that I ′ is a repair of I w.r.t. F if I ′ is a ≤ I -minimal instance consistent with F . By Repairs(I, F ) we denote the set of all repairs of I w.r.t. F .

Because an empty instance over a schema always satisfies any set of universal constraints over the schema, the set of repairs is guaranteed to be non-empty.

Consistent query answers

Finally, we use the repairs to define the consistent query answers.

Definition 5 ([3]) true (false) is the consistent answer to a closed query Q, denoted I |= F Q (I |= F Q resp.) if and only if true (false resp.
) is the answer to Q in every repair of I w.r.t. F .

We note that our approach can be easily extended to open queries along the lines of [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF][START_REF] Chomicki | Computing consistent query answers using conflict hypergraphs[END_REF]. In essence, from an open query Q(x) we derive a query Q E (x) that defines an envelope, a superset of consistent query answers to Q(x). For every tuple t from the envelope, t is a consistent answer to Q(x) if and only if true is the consistent answer to the closed query Q(t).

Decision problems

We consider here the following complexity classes:

• PTIME: the class of decision problems solvable in polynomial time by deterministic Turing machines; • coNP: the class of decision problems whose complements are solvable in polynomial time by nondeterministic Turing machines; • Π p 2 : the class of decision problems whose complements are solvable in polynomial time by nondeterministic Turing machines with an NP oracle.

To investigate tractability of the framework of consistent query answers we use the notion of data complexity [START_REF] Vardi | The complexity of relational query languages[END_REF]. This notion allows to describe the complexity of the problems in terms of the size of the database only and assume the remaining parts of the input to be fixed. There are two classical decision problems that are investigated in the context of consistent query answers [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]: (i) repair checking -determining if a database instance is a repair of a given database instance, i.e. the complexity of the following set

B F = {(I, I ′ ) | I ′ ∈ Repairs(I, F )}.
(ii) consistent query answering -determining if true is the consistent answer to a given closed query in a given database w.r.t. a given set of integrity constraints, i.e. the complexity of the following set

D F,Q = {I | I |= F Q}.

Basic constructions and facts

In this section we generalize the conflict hypergraph for denial constraints [START_REF] Arenas | Scalar aggregation in inconsistent databases[END_REF][START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF].

In the scope of this section, we fix an instance I and a set of universal constraints F .

Extended conflict hypergraph

For denial constraints, a conflict is a set of facts whose presence violates a constraint. For universal constraints, a conflict is created not only by the presence of some facts but also by the simultaneous absence of other facts.

Definition 6 (Conflict) A set of literals

{R 1 (t 1 ), . . . , R n (t n ), ¬P 1 (s 1 ), . . . , ¬P m (s m )} is a conflict w.r.t. a constraint ∀x. ¬[R 1 (x 1 ) ∧ . . . ∧ R n (x n ) ∧ ¬P 1 (ȳ 1 ) ∧ . . . ∧ ¬P m (ȳ m ) ∧ ϕ(x)],
if there exists a ground substitution θ of variables x such that θ(x i ) = t i for i ∈ {1, . . . , n}, θ(ȳ j ) = s j for j ∈ {1, . . . , m}, and ϕ(θ(x)) holds.

If the constraints are limited to denial constraints, conflicts can be resolved only by deleting facts. Moreover, deleting a fact will not create further conflicts. Therefore, only conflicts created by the facts from the original instance need to be considered.

In the case of universal constraints, the picture is more complex. First, a conflict can be resolved not only by deleting facts but also by inserting a fact. Second, deleting a fact can create conflicts caused by the absence of the fact. Similarly, inserting a fact can create conflicts caused by the presence of the fact. Moreover, a cascading propagation of conflicts can easily take place: resolving one conflict leads to the creation of another conflict whose resolution leads to yet another one, and so on.

I 4 = I ∪ {P (2)} \ {R(2, 3)}.
Clearly, to capture all repairs it is not enough to consider only the facts present in the original database instance. Also the facts potentially inserted need to be considered. We capture the set of relevant facts in the following way.

Definition 7 (Hull) The hull is the minimal set of literals Hull(I, F ) satisfying the following conditions:

(1)

I ⊆ Hull(I, F ), (2)
if a set e is a conflict w.r.t. a constraint in F such that every fact of e belongs to Hull(I, F ), then for every ¬P (t) in e, both ¬P (t) and P (t) belong to Hull(I, F ).

We note that this definition can be easily translated to a negation-free Datalog program which computes the set of literals in the hull. The arities of the predicates are equal to the arities of the corresponding relation names.

Example 5 For the set of constraints F from Example 4 we construct the following Datalog program:

R H (x, y) ← R(x, y). P H (x) ← P (x). P H (y) ← R H (x, y), P H (x). P H (y) ← R H (x, y), P H (x).
Now, if we treat the instance I as the extensional database, the program above has the following solution (least fixpoint):

I∪{R H (1, 2), R H (2, 3), P H (1)} ∪ {P H (2), P H (3), P H (2), P H (3)}, which corresponds to Hull(I, F ) = I ∪ {P (2), ¬P (2), P (3), ¬P (3)}.
Our intention is to use hyperedges to restrict the sets of literals used to construct a repair so that no conflicts are present. Because the hull may contain a fact and its negation, we also use an edge to prevent us from considering these two together.

Definition 8 (Extended conflict hypergraph) The extended conflict hypergraph G(I, F ) is a hypergraph whose set of vertices is Hull(I, F ) and whose set of hyperedges consists of the following two types of sets:

(1) conflict hyperedges e ⊆ Hull(I, F ) such that e is a conflict w.r.t a constraint in F , (2) stabilizing edges {P (t), ¬P (t)} such that both P (t) and ¬P (t) belong to Hull(I, F ).

An independent set of the extended conflict hypergraph G(I, F ) is any subset of Hull(I, F ) that contains no hyperedges. M is a maximal independent set if there exists no independent set M ′ ⊆ Hull(I, F ) such that M M ′ .

P (1) ¬P (2)
R(2, 3) line is used for stabilizing edges connecting a fact and its negation (if present).

P (2) ¬P (3) P (3)
We observe that deleting P (1) does not lead to a conflict, and consequently, ¬P (1) is not present in the hull.

Since we assume the set of constraints to be fixed, the cardinalities of each conflict in G(I, F ) are bounded by the maximal number of atoms used in a constraint definition, a constant K. To construct the set of hyperedges we need to consider all subsets of cardinality bounded by K. Consequently,

Proposition 1

The extended conflict hypergraph G(I, F ) can be constructed in time polynomial in the size of I (data complexity). Also, the size of G(I, F ) is polynomial in the size of I.

The presented extension of the conflict hypergraph is backward-compatible with [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]: if we restrict the set of constraints to denial constrains only, the hull is equal to the original instance and we obtain the standard conflict hypergraph [START_REF] Arenas | Scalar aggregation in inconsistent databases[END_REF][START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]. Finally, in the presence of denial constraints, because the repairs are obtained by deleting facts only, the repairs are maximal consistent subsets of the original instance.

Proposition 2 ([15]

) If F is a set of denial constraints, each repair of I w.r.t. F corresponds to a maximal independent set of G(I, F ), and vice versa.

The same equivalence does not hold for the extended conflict hypergraph. For instance, while the repair I 1 (Example 4) is a maximal independent set of G 1 (Fig. 4), the repairs I 2 , I 3 , and I 4 are not. One reason for this is the use of negated facts in the extended conflict hypergraph. We observe, however, that if we complement I 2 = {R(2, 3), P (1)} with the (relevant) negations of facts that are not present in I 2 , we obtain a maximal independent set {R(2, 3), P (1), ¬P (2), ¬P (3)}. This holds for every repair.

Proposition 3 For any repair I ′ ∈ Repairs(I, F ) the set

Compl(I ′ ) = I ′ ∪ {¬R(t) ∈ Hull(I, F ) | R(t) ∈ I ′ } is a maximal independent set of G(I, F ). Proof: Naturally, Compl(I ′ ) is independent because I ′ is consistent. Before showing that Compl(I ′
) is a maximal independent set we make two observations following from the construction of the hull:

1 o For every ¬R(t) in Hull(I, F ), the fact R(t) is also present in Hull(I, F ). 2 o For every fact R(t), if ¬R(t) is not present in Hull(I, F ), then R(t) ∈ I. Now, take any fact p ∈ Hull(I, F ) \ Compl(I ′ ). If p = ¬R(t), then R(t) ∈ Compl(I ′
) and adding ¬R(t) to Compl(I ′ ) introduces the stabilizing edge {R(t), ¬R(t)}. Analogously, we show that Compl(I ′ ) cannot be extended with a fact R(t) whose negation is present in Hull(I, F ). The only remaining case is extending Compl(I ′ ) with a fact R(t) that belongs to I. We observe that for R(t) ∈ I \ I ′ , we have I ′ ∪ {R(t)} < I I ′ and so I ′ ∪ {R(t)} is inconsistent. Consequently, Compl(I ′ ) ∪ {R(t)} contains a conflicting hyperedge.

We note that the converse of Proposition 3 is not necessarily true, i.e. for a maximal independent set M of the extended conflict hypergraph, its positive projection M + = {R(t) | R(t) ∈ M } needs not to be a repair. For instance, if we take the maximal independent set

M = {R(1, 2), ¬P (2), R(2, 3), ¬P (3)
} of G 1 (Fig. 4), its positive projection

M + = {R(1, 2), R(2, 3)} is not a repair.
Nevertheless, the extended conflict hypergraph allows us to capture all the repairs. And since its size is polynomial in the size of I, we consider it to be a compact representation of the repairs of I.

Proposition 4 For any maximal independent set M of G(I, F ) either M + is a repair of I w.r.t. F or there exists a maximal independent set N of G(I, F ) such that N + < I M + .

Proof: Take any maximal independent set M of G(I, F ) such that M + is not a repair. Naturally, M + is consistent and therefore there exists a repair I ′ such that I ′ < I M + . It suffices to note that Compl(I ′ ) + = I ′ and by Proposition 3 Compl(I ′ ) is a maximal independent set of G(I, F ).

Grounding constraints

Often, we will find it more convenient to view conflict hyperedges as grounded integrity constraints. This helps to pinpoint the exact reasons for integrity violations and the facts that can be inserted and deleted to resolve the conflict.

Definition 9 For any conflict hyperedge

{R 1 (t 1 ), . . . , R n (t n ), ¬P 1 (s 1 ), . . . , ¬P m (t m )} in G(I, F ) the implication R 1 (t 1 ) ∧ . . . ∧ R n (t n ) → P 1 (s 1 ) ∨ . . . ∨ P m (s m )
is a ground rule (or simply a rule) in G(I, F ). By Rules(I, F ) we denote the set of all ground rules in G(I, F ).

A denial (full TGD, JD, or non-JD, resp.) rule is a rule obtained from a conflict w.r.t. a denial constraint (full TGD, JD, or non-JD resp.) The facts in the lhs and the rhs of a ground rule are represented as sets, i.e. no particular order is assumed and duplicates are removed.

Naturally, the cardinality of the set of the ground rules is equal to the number of the conflict hyperedges, and thus it is polynomial in the size of I. We also note that when considering the instances using facts from the hull only, satisfaction of the set of constraints F implies the satisfaction of Rules(I, F ). The converse is also true because the hull contains all relevant facts.

Proposition 5 For any instance J such that J ⊆ Hull(I, F ), J |= F if and only if J |= Rules(I, F ).

Repairing in the presence of full tuple-generating dependencies

Now, we show that repair checking in the presence of full tuple-generating dependencies and denial constraints is tractable. We use the result to construct a complete and sound repairing algorithm. In the scope of this section we fix an instance I and a set F of denial constraints and full tuple-generating dependencies.

Repair checking

We begin by presenting an alternative characterization of repairs w.r.t. a set of full TGD and denial constraints. If we view full TGDs as Datalog programs we can use the standard consequence operator to identify the facts that need to be added to satisfy the constraints.

Definition 10 For a set of facts J ⊆ Hull(I, F ), the operator of immediate consequence of F on J is defined as

T F (J) = J ∪ {P (s) |R 1 (t 1 ) ∧ . . . ∧ R(t n ) → P (s) ∈ Rules(I, F ) s.t. {R(t 1 ), . . . , R(t n )} ⊆ J}.
T * F is defined as the transitive closure of T F .

It is a classical result that T * F (J) can be computed in time polynomial in the size of J [START_REF]Knowledge Representation, Reasoning and Declarative Problem Solving[END_REF]. Now, we present an alternative characterization of a repair w.r.t. a set of full TGDs and denial constraints. Essentially, every repair is obtained by closing under T * F some subset of the original instance and verifying that the resulting instance is consistent.

Lemma 1 I ′ is a repair of I w.r.t. F if and only if the following conditions are satisfied:

(i) I ′ is consistent, (ii) T * F (I ′ ∩ I) = I ′ , (iii) there is no R(t) ∈ I \ I ′ such that J ′ = T * F (I ′ ∪ {R(t)}) is consistent and J ′ \ I = I ′ \ I.
Proof: For the only if part I ′ ∈ Repairs(I, F ) implies that (i) holds.

To show (ii) we note that T * F (I ∩ I ′ ) by definition is the minimal set that contains I ∩ I ′ and satisfies all full TGDs from F . Hence, T * F (I ∩ I ′ ) ⊆ I ′ and, as a subset of a consistent instance I ′ , T * F (I ∩ I ′ ) satisfies also all denial constraints from F . We also note that T * F (I ∩ I ′ ) and I ′ agree on the facts in I. I ′ is the ≤ I -minimal consistent instance that contains all of I ∩ I ′ and none of I \ I ′ , which implies that

I ′ = T * F (I ∩ I ′ ).
To show (iii) we take any R(t

) ∈ I \ I ′ such that J ′ = T * F (I ′ ∪ {R(t)}) is consistent. Since I ′ is a ≤ I -minimal consistent instance, J ′ ≤ I I ′ . This implies J ′ \ I ⊆ I ′ \ I because I \ J ′ ⊆ I \ I ′ .
For the if part take any ≤ I -minimal consistent instance I ′′ such that I ′′ ≤ I I ′ . Such instance exists because by (i) I ′ is consistent. I ′′ is a repair, and it satisfies (ii). Therefore it suffices to show that I ′ ∩ I = I ′′ ∩ I. I ′′ ≤ I I ′ shows directly that I ′ ∩ I ⊆ I ′′ ∩ I. This also shows that I ′ ⊆ I ′′ .

To show I ′′ ∩I ⊆ I ′ ∩I, suppose there exists R(t) ∈ I ′′ ∩I such that R(t) ∈ I ′ ∩I. Naturally, T * F (I ′ ∪ {R(t)}) ⊆ I ′′ and since I ′ ⊆ I ′′ , we have

T * F (I ′ ∪ {R(t)}) \ I ⊆ I ′′ \ I ⊆ I ′ \ I.
On the other hand, we note that R(t) ∈ I \ I ′ and T * F (I ′ ∪ {R(t)}) is consistent as a subset of a consistent instance closed under T * F . By (iii), we obtain

T * F (I ′ ∪ {R(t)}) ⊆ I ′ \ I,
which is a contradiction. Thus, I ′ = I ′′ and I ′ is a repair.

We observe that the conditions of Lemma 1 can be checked in time polynomial in the size of the instances I and I ′ . Consequently, Theorem 1 Repair checking is in PTIME for any set of denial constraints and full tuple-generating dependencies.

Constructing a repair

In this subsection we present a polynomial-time algorithm for constructing repairs of an instance w.r.t. a set of full TGDs and denial constraints. Rather than trying to resolve all the conflicts present in the instance, the algorithm constructs a repair from scratch: it begins with an empty instance, iterates over the facts of the original instance, and for every fact makes a decision whether to discard the fact or to add it to the constructed instance. It should be noted that those two actions, although related, are different and should not be confused with inserting and deleting facts from the original instance in order to resolve conflicts.

Before we present the algorithm for full TGDs and denial constraints, we recall a simpler algorithm [START_REF] Staworko | Preference-driven querying of inconsistent relational databases[END_REF] that constructs repairs in the presence of denial constraints. Algorithm 1 constructs a maximal consistent subset of the input Algorithm 1 Constructing a repair of I w.r.t. a set of denial constraints F

1: I o ← I 2: J ← ∅ 3: while I o = ∅ do 4:
choose R(t) ∈ I o 5:

I o ← I o \ {R(t)} 6: if J ∪ {R(t)} |= F then 7:
J ← J ∪ {R(t)} 8: return J instance by iterating over the facts of the input instance (using I o to store the remaining facts) and adding the current fact if doing so does not violate the constraints. Since maximal consistent subsets of the original instance correspond to maximal independent set of the conflict hypergraph, by Proposition 2 this algorithm always returns a repair, i.e. it is sound. We also note that it is complete, i.e. every repair of the original instance can be constructed: it suffices to chose first the facts of the desired repair.

An approach that constructs a maximal consistent subset of the original instance is also sound for constructing a repair in the presence of denial constraints and general TGDs [START_REF] Kolaitis | [END_REF]. However, in the presence of TGDs a repair needs not be a subset of the original instance and consequently this approach is not necessarily complete.

Example 7 For the schema S = {R(A), P (A)} with a set of constraints F = {R(x) → P (x)} consider the instance I = {R(1), R(2)}. This instance has four repairs w.r.t. F :

I ′ 1 = ∅, I ′ 2 = {R(1), P (1)}, I ′ 3 = {R(2), P (2)}, I ′ 4 = {R(1), P (1), R(2), P (2)}.
Only the repair I ′ 1 is a subset of the original instance.

Our approach extends Algorithm 1 by allowing it also to add a fact together with the facts implied by full TGDs. In this way, for instance, the repair I 2 is obtained by adding R(1) together with P (1) and discarding R(2). Hence, from now on when we add a fact, we implicitly add the facts that are required to satisfy full TGDs (i.e., we keep the instance closed under T * F ).

In the general scenario, because of the complex interaction among facts, the decision whether to add or to discard a fact becomes quite intricate. We illustrate this in the following example.

Example 8 We take the schema S = {R(A, B, C), P (A, B)} with a set of constraints F = {R(x, y, z) → P (x, y), P : A → B}.

First, we consider the instance I 1 = {P (1, 1), R(1, 2, 1)}. We start with an empty instance and begin with the fact P (1, 1). We add it as doing so does not violate the constraints. Adding the next fact R(1, 2, 1) would require adding also the fact P (1, 2). This would, however, create a conflict. Hence, we must discard R(1, 2, 1). The obtained instance {P (1, 1)} is a repair of I 1 .

Now, let's consider the instance I 2 = {R(1, 2, 1), R(1, 2, 2)} and begin with the fact R(1, 2, 1). Adding the fact R(1, 2, 1) would require adding also the fact P (1, 2) which is not present in the instance constructed so far. Therefore, we can consider both adding and discarding R(1, 2, 1). We decide to discard it, but we note that the set of facts {P (1, 2)} cannot become included later on in the constructed instance. We store it on the list of banned sets. Intu-itively, a banned set contains tuples whose mutual absence in the constructed instance justifies discarding some other tuple. Consequently, we must prevent adding any tuples which may cause a banned set to be included in the constructed instance. For instance, adding the next fact R(

I o ← I o \ {R(t)} 7: J ′ ← T * F (J ∪ {R(t)}) 8: if        J ′ |= F or (*) b ∧ J ′ \ (I ∪ J) = ∅ or (**) ∃B ∈ Banned. B ⊆ J ′ (***) then 9: if J ′ |= F then Banned ← Banned ∪ {J ′ \ (I ∪ J)} 10:
else skip 11:

else J ← J ′ 12: return J the original instance I. Banned is a collection of banned sets of facts, i.e. sets that are not to be included in the constructed instance J. We note that some elements of those sets can, however, be included in J.

For every fact R(t) the algorithm makes a choice b whether or not it should try discarding the fact. Here, this choice is nondeterministic but, in practice, it could be based on the user preference. The fact R(t) is discarded if one of the following conditions is satisfied: (*) Adding R(t) violates the constraints. (**) Adding R(t) does not violate constraints, but b is set to true and adding R(t) implies adding facts that are not present in J and I. (***) Adding R(t) leads to inclusion of some previously created banned set.

If the fact is discarded even though adding it does not violate the constraints, a banned set is added to Banned (line 9). Finally, if none of the conditions above is satisfied, the fact is added to J (line 11).

Before proving that Algorithm 2 is sound and complete, we make several observations. First, we note that J is always closed under T * F . Moreover, J is always consistent because the condition (*) ensures that facts are added to J only if doing so does not violate the constraints. Finally, the main loop of Algorithm 2 satisfies the following invariant:

Inv ≡ ∀B ∈ Banned. B ⊆ J.
Indeed, the invariant is trivially satisfied before the execution enters the main loop. Also, the condition (***) ensures that facts are added to the constructed instance J only if doing so does not violate Inv. Hence, we need only to check that creating a new banned set does not violate the invariant. We observe that a new banned set is created only if (**) or (***) are satisfied. (**) implies directly that the new banned set satisfies Inv. (***) implies this implicitly. In this case there exists a banned set B such that B ⊆ J ′ = T * F (J ∪ {R(t)}). We note that all banned sets contain no fact from I. B ⊆ J by Inv. Thus, the newly created banned set B ′ = J ′ \ (I ∪ J) is not included in J.

Theorem 2 Algorithm 2 is a sound and complete repairing algorithm for any instance and any set of denial constraints and full tuple-generating dependencies. Algorithm 2 works in time polynomial in the size of the input instance I.

Proof: Soundness. We show that for any execution of Algorithm 2 the returned instance, denoted here by I ′ , satisfies the conditions (i), (ii), and (iii) of Lemma 1.

The conditions (i) and (ii) are satisfied trivially because, as observed before, at every time the constructed instance J is consistent and closed under T * F .

To show (iii) we take any R(t) ∈ I \ I ′ such that J ′ = T * F (I ′ ∪ {R(t)}) |= F . Consider the iteration of the main loop during which R(t) was chosen and note that J ⊆ I ′ . We observe that the condition (*) is not satisfied, but since R(t) is not added to I ′ , (**) or (***) is. Consequently, a banned set B = J ′ \ (I ∪ J) is added to Banned. It is easy to see that B ⊆ J ′ \ I. On the other hand, Inv implies that B ⊆ I ′ \ I, which proves that J ′ \ I ⊆ I ′ \ I.

Completeness. Take any repair I ′ ∈ Repairs(I, F ) and consider an execution of Algorithm 2 during which: 1) in the first phase, it selects all facts from I ∩I ′ and sets b to false; 2) in the second phase, it chooses all facts from I \ I ′ and sets b to true. We show that this execution returns I ′ . First, we consider the facts chosen in the first phase and we show that none of the conditions (*), (**), and (***) is satisfied. Indeed, the condition (*) is not satisfied because I ′ is consistent (and so is any of its subsets closed under T * F ). Trivially, the condition (**) is also not satisfied because b is chosen to be f alse. The condition (***) is not satisfied because during the first phase Banned remains empty. Note that the instance J obtained after the first phase consists exactly of the facts of I ′ ∩ I closed under T * F . By (ii) of Lemma 1, J = I ′ . Now, we show with a simple inductive argument that none of the facts from I \I ′ are added in the second phase. By (iii) of Lemma 1, for a fact R(t

) ∈ I \I ′ , if (*) is not satisfied, then T * F (J ∪ {R(t)}) \ I ⊆ J \ I. This implies that T * F (J ∪ {R(t)}) \ (I ∪ J) is nonempty, i.e. (**) is satisfied (b is true).
We finish the proof by showing that Algorithm 2 works in time polynomial in the size of I. First, we observe the algorithm iterates over the facts of I. For every fact it creates at most one banned set, and so the cardinality of Banned is bounded by the size of I. Each banned set is a subset of Hull(I, F ), and thus of polynomial size as well. Consequently, for every fact all of the conditions (*), (**), and (***) can be checked in polynomial time.

Consistent query answering for full TGDs

In this section we investigate consistent query answering in the presence of full tuple-generating dependencies and denial constraints. We begin by presenting a polynomial algorithm for computing consistent answers to quantifier-free queries in the presence of acyclic full TGDs and denial constraints. Next, we extend this approach to handle join dependencies as well. Finally, we show that for arbitrary full TGDs consistent query answering is coNP-complete.

Warm-up: acyclic full TGDs and denial constraints

In this section we extend the algorithm computing consistent query answers to closed quantifier-free queries in the presence of denial constraints [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]. The main idea of the algorithm is to check if there exists a repair that does not satisfy the query, i.e. satisfies the negated query. The negated query specifies the facts that need to be present and the facts that need to be absent in the repair. To find if the repair in question can be constructed we devise supports and blocks of the facts that need to be respectively present and absent in the repair. Intuitively, a support of a fact is a set of facts from the original instance that, if contained in the repair, guarantees the presence of this fact. Conversely, a block of a fact specifies facts that lead to a conflict with this fact and so their presence guarantees the absence of the fact in the repair. Additionally, a block can specify facts that must not be included during the repairing process. Finally, we show how to check that a combination of supports and blocks can be realized in the same repair.

We fix an instance I and a set F of denial constraints and acyclic full tuplegenerating dependencies. For brevity, we use inference-like rules to define the supports and blocks of a fact. A rule of the form A B reads: "B provided A". Also, in A we often use ground rules which implicitly belong to Rules(I, F ).

Definition 11 (Support) A support of a fact R(t) ∈ Hull(I, F ) is a subset of I defined with the following rules:

S 0 : R(t) ∈ I {R(t)} ∈ Supp(R(t)) S 1 : R 1 (t 1 ) ∧ . . . ∧ R n (t n ) → R(t) R(t) ∈ I S i ∈ Supp(R i (t i )) ∀i ∈ {1, . . . , n} i S i ∈ Supp(R(t))
where Supp(R(t)) is the set of all supports of R(t).

Essentially, a support of a tuple from the original instance is a singleton consisting of that tuple (rule S 0 ). If a tuple does not belong to the original instance but there is a full TGD rule having the tuple in its rhs, then a support of that tuple is a union of the supports of the tuples in the lhs (rule S 1 ).

Example 9

We take the schema S = {R(A, B, C), P (A, B), Q(A)} with the set of constraints F = {R(x, y, z) → P (x, y), P (x, y) → Q(x), P : A → B}, and consider the instance

I = {R(1, 1, 1), R(1, 2, 1), P (1, 2), Q(2)}. The hull is Hull(I, F ) = I ∪ {P (1, 1), Q(1)}. The set of ground rules is Rules(I, F ) = {R(1, 1, 1) → P (1, 1), R(1, 2, 1) → P (1, 2), P (1, 1) → Q(1), P (1, 2) → Q(1), P (1, 1) ∧ P (1, 2) → false}.
The following proposition ensures tractability of our approach.

Proposition 8 For any fact the number of all of its supports and the number of all of its blocks can be computed in time polynomial in the size of the instance I.

This claim is proved with a simple combinatorial argument. Also here, the acyclicity of F is essential. The proof of a more general claim (Proposition 12) can be found in Appendix A.

Finally, we show how to check if there exists a repair that realizes a given combination of supports and blocks.

Lemma 2 For any (possibly cyclic) set of full TGDs and denial constraints F , an instance I, and two sets of facts P ⊆ I and N ⊆ Hull(I, F )\I, a repair containing all facts from P and no facts from N exists if and only if T * F (P ) is consistent and disjoint with N .

Proof: The only if part of the proof is trivial. For the if part take any repair I ′ such that I ′ ≤ I T * F (P ). Such an instance exists because T * F (P ) is consistent. We show that I ′ is the desired repair. First, I ′ ≤ I T * F (P ) and P ⊆ I imply that P ⊆ I ′ , and consequently T * F (P ) ⊆ I ′ (as

I ′ is consistent). I ′ ≤ I T * F (P ) implies also N ∩ I ′ = ∅ because N contains no fact from I.
We use the previous results to construct Algorithm 3 computing the consistent answer to a quantifier-free query to Q in the instance I w.r.t. a set of denial constraints and acyclic full TGDs F .

We assume that the query Q is in CNF and we note that true is not the consistent answer to Q if and only if there exists a conjunct of Q that is not satisfied by some repair. Consequently, for each conjunct Q i of Q we check if there exists a repair that satisfies ¬Q i (line 2). A negated conjunct is a conjunction of positive and negative atomic formulas

¬Q i ≡ R 1 (t 1 ) ∧ . . . ∧ R n (t n ) ∧ ¬P 1 (s 1 ) ∧ . . . ∧ P m (t m )
and therefore a repair satisfying ¬Q i is a repair that contains all R i (t i )'s and no P j (s j )'s. The existence of such a repair is checked with the function ExistsRepair.

Because all repairs are constructed from facts in Hull(I, F ), we can assume that all R i (t i )'s and P j (s j )'s belong to Hull(I, F ). Indeed, if some R i (t i ) does not belong to Hull(I, F ), then a repair containing R i (t i ) does not exist (line 7). Similarly, if some P j (s j ) does not belong to Hull(I, F ), then no repair contains P j (s j ) (line 9). Using Propositions 6 and 7 we show that there exists a repair I ′ containing all R i (t i )'s and no P j (s j )'s if and only if for every R i (t i ) Algorithm 3 Computing the consistent answer to Q in I w.r.t. F . function CQA(Q, I, F ) precompute: Hull(I, F ), Supp, and Block for I and F .

1: let Q ≡ Q 1 ∧ . . . ∧ Q w /*
let ¬Q i ≡ R 1 (t 1 ) ∧ . . . ∧ R n (t n ) ∧ ¬P 1 (s 1 ) ∧ . . . ∧ ¬P m (s m ) 4:
if existsRepair({R 1 (t 1 ), . . . , R n (t n )}, {P 1 (s 1 ), . . . , P m (s m )}) then

T N ← T N ∩ Hull(I, F ) 11: let {R 1 (t 1 ), . . . , R n (t n )} ≡ T P 12: let {P 1 (s 1 ), . . . , P m (t m )} ≡ T N 13: for S 1 ∈ Supp(R 1 (t 1 )), . . . , S n ∈ Supp(R n (s n ) do 14: for (B 1 , N 1 ) ∈ Block(P 1 (s 1 )), . . . , (B m , N m ) ∈ Block(P m (s m )) do 15: P ← S 1 ∪ . . . ∪ S n ∪ B 1 ∪ . . . ∪ B m 16: N ← N 1 ∪ . . . ∪ N m 17: if T * F (P ) |= F and T * F (P ) ∩ N = ∅ then 18:
return true 19: return false end function there exists a support S i and for every P j (s j ) there exists a block (B j , N j ) such that I ′ contains all S i 's and B j 's and is disjoint with every N j 's.

Hence, it suffices to exhaustively enumerate over all combinations of supports of R i (t i )'s (line 13) and blocks of P j (s j )'s (line 14) and use Lemma 2 to check if a combination can be realized by a repair (line 17).

Finally, to show that Algorithm 3 works in time polynomial in the size of I, we note that the size of the query is considered to be a fixed constant and by Proposition 8 the number of supports and blocks of every fact is polynomial in the size of I. We remark that acyclicity is used only in Propositions 7 and 8. Theorem 3 Consistent query answering is in PTIME for any quantifier-free query and any acyclic set of denial constraints and full tuple-generating dependencies.

Example 11 (cont. Example 10) We execute Algorithm 3 with the follow-ing query:

Q = (Q(1) ∨ ¬R(1, 1, 1)) ∧ (Q(2) ∨ ¬P (1, 2)) ∧ (R(1, 2, 1) ∨ ¬P (1, 2)).
The negation of the first conjunct is ¬Q 1 = R(1, 1, 1) ∧ ¬Q [START_REF] Abiteboul | Foundations of Databases[END_REF]. The fact R(1, 1, 1) has only one support {R(1, 1, 1)} and the fact Q(1) only one block (∅, {Q(1)}). Although T * F ({R(1, 1, 1)}) = {R(1, 1, 1), P (1, 1), Q(1)} is consistent, it contains Q(1). Hence, there does not exists a repair that satisfies ¬Q 1 .

The negation of the second conjunct is ¬Q 2 = P (1, 2) ∧ ¬Q [START_REF] Afrati | Repair checking in inconsistent databases: algorithms and complexity[END_REF]. Because the fact Q(2) has no block, there is no repair that does not contain Q(2), and consequently there does not exists a repair satisfying ¬Q 2 .

The negation of the third conjunct is ¬Q 3 = P (1, 2) ∧ ¬R(1, 2, 1). The fact P (1, 2) has only one support {R(1, 1, 1)} and the fact R(1, 2, 1) has two blocks: (∅, {Q(1)}) and (B 2 , N 2 ) = ({R(1, 1, 1)}, ∅). Similarly to ¬Q 1 , combining the support with the first block does not guarantee the existence of a repair satisfying ¬Q 3 . However, if we use the support with the second block, then P = {R(1, 1, 1)} and N = ∅ satisfy Lemma 2 which implies that there exists a repair satisfying ¬Q 3 . Indeed, this repair is

I ′ 2 .
Consequently, the query Q does not hold in the repair I ′ 2 and true is not the consistent answer to Q.

Adding join dependencies

In this section we extend Algorithm 3 to include also JDs. For this we generalize the definitions of supports and blocks and we show that Propositions 6, 7, and 8 continue to hold. Here, we present only the constructions and main claims. Complete proofs are presented in Appendix A.

The following folklore result shows that we need to consider the case where there is only one JD per relation.

Proposition 9

For any (possibly empty) set of JDs {jd 1 , . . . , jd n } on the same relation name there exists a JD jd * such that an instance satisfies {jd 1 , . . . , jd n } if and only if it satisfies jd * .

We remark that in particular every relation R in every instance satisfies the trivial JD R ✶:[attrs(R)]. Hence, we fix an instance I and a set of constraints F consisting of a set of acyclic full TGDs, denial constraints, and exactly one JD per relation. Also, to distinguish JD rules we write them R(t 1 ) ∧ . . . ∧ R(t n ) ✶ → R(t). We remark, however, that → continues to be used for all rules, including those obtained from conflicts w.r.t. JDs. Finally, we observe that any JD R ✶:[X 1 , . . . , X k ] yields rules R(t) ✶ → R(t) for all R(t) ∈ Hull(I, F ). Because we assume that F contains one JD on every relation in S, ✶ → and → (which subsumes ✶ → ) are reflexive on facts from Hull(I, F ).

Previously, the acyclicity of the set of integrity constraints implicitly provided a bound on the depth of the derivation of supports and blocks. This bound is essential when showing that supports and blocks can be constructed in time polynomial in the size of the database. Although JDs translate to cyclic full TGDs, it is sufficient to consider derivations of supports and blocks of bounded depth.

Lemma 3 If Rules(I, F ) contains the following two ground rules

r ′ = R(t ′ 1 ) ∧ . . . ∧ R(t ′ k ) ✶ → R(t i ) and r ′′ = R(t 1 ) ∧ . . . ∧ R(t k ) ✶ → R(t)
for some i ∈ {1, . . . , k}, then there exists j ∈ {1, . . . , k} such that Rules(I, F ) contains also

r * = R(t 1 ) ∧ . . . ∧ R(t i-1 ) ∧ R(t ′ j ) ∧ R(t i+1 ) ∧ . . . ∧ R(t k ) ✶ → R(t).
Because the set of constraints is cyclic, we construct the supports in an iterative manner allowing us to bound the derivation depth. The new rules for supports are obtained by appropriately incorporating JD-rules into S 0 and S 1 (Definition 11).

Definition 13 (Support) Let h be the acyclic height of the dependency graph D(S, F ). For ℓ ∈ {-1, 0, . . . , h} an ℓ-support of a fact R(t) ∈ Hull(I, F ) is a subset of I defined with the following rules:

S -1 0 : R(t) ∈ I {R(t)} ∈ Supp -1 (R(t)) S ℓ 1 : R(t 1 ) ∧ . . . ∧ R(t k ) ✶ → R(t) R i,1 (t i,1 ) ∧ . . . ∧ R i,n i (t i,n i ) → R(t i ) ∀i ∈ {1, . . . , k} R(t) ∈ I S i,j ∈ Supp ℓ-1 (R i,j (t i,j )) ∀i ∈ {1, . . . , k}, ∀j ∈ {1, . . . , n i } i,j S i,j ∈ Supp ℓ (R(t))
where Supp ℓ (R(t)) denotes the set of all ℓ-supports of R(t). A support of R(t) is any element of the set Supp(R(t)) = Supp h (R(t)).

We note that because → and ✶ → are reflexive on facts from Hull(I, F ), the rule S ℓ 1 properly propagates supports, i.e any (ℓ -1)-support of R(t) is also an ℓ-support of R(t). We also note that if all the JDs in F are trivial, then the set of supports of a fact coincides with the set of supports from Definition 11 The if part is proved with a simple induction over the depth of derivation of a block. The proof of the only if part is based on the following simple idea. R(t) ∈ I \ I ′ is absent in the repair I ′ because its presence would cause a violation of some ground rule. We identify this rule by considering an inconsistent instance I ′ ∪ {R(t)}. We use this rule to show that R(t) has a block that validates the claim.

Proposition 12 For any fact R(t) the sets Supp(R(t)) and Block(R(t)) can be constructed in time polynomial in the size of I.

A simple combinatorial proof is presented in Appendix A.

We recall that the proof of Theorem 3 relies on the Lemma 2 and Propositions 6, 7, and 8. The proof of Lemma 2 does not assume the set of constraints to be acyclic and the corresponding Propositions 10, 11, and 12 have been proved for generalized supports and blocks. Consequently, Corollary 1 Consistent query answering is in PTIME for any quantifierfree query and any set of join dependencies, denial constraints, and acyclic full tuple-generating dependencies.

Negative results

It appears to be difficult to extend our approach beyond quantifier-free queries because of the following result.

Theorem 4 ([15]

) There exists an FD and a closed conjunctive query (using existential quantifiers) for which consistent query answering is coNP-complete.

Also, the class of constraints is likely to be maximal as having even one cyclic full TGD that is not a JD leads to intractability.

Theorem 5 There exists a positive atomic query and a set of integrity constraints consisting of one FD and one cyclic full tuple-generating dependency for which consistent query answering is coNP-complete.

Proof: The membership of consistent query answering in coNP follows from the definition of consistent query answers and Theorem 1.

We show coNP-hardness by reducing the complement of 3COL to consistent query answering. 3COL is a classic NP-complete problem of testing if a graph has a legal 3-coloring [START_REF] Papadimitriou | Computational Complexity[END_REF]. A 3-coloring is an assignment of one of 3 colors to each vertex of the graph. It is legal if no two adjacent vertices have the same color. Take any undirected graph G = (V, E), and let V = {v 1 , . . . , v n } and E = {e 1 , . . . , e m }. We assume that G has no isolated vertices (i.e. vertices incident to no edge).

We use the schema S = {R(A, B, C, D), P (C)} with the set of integrity constraints

F = {R : A → B, R(x 1 , y 1 , z 1 , z 2 ) ∧ R(x 2 , y 2 , z 1 , z 2 ) ∧ P (z 1 ) ∧ y 1 = y 2 → P (z 2 )}.
We use the following facts:

• p k i,j = R(i, k, j -1, j)
for each vertex v i with color k incident to the edge e j (we create a separate copy for each edge incident to the vertex and for each color); • q j = P (j) indicating that the edges e 1 , . . . , e j connect properly colored vertices (for j ∈ {0, . . . , m}); • 3 special facts: r = R(n + 1, 0, m, m + 1), r ′ = R(n + 2, 1, m, m + 1) and r ′′ = P (m + 1).

The constructed instance is:

I G = {p k i,j | v i ∈ V, e j ∈ E, v i ∈ e j , 1 ≤ k ≤ 3} ∪ {q 0 , r, r ′ }.
Now, we outline the interaction among the facts induced by the integrity constraints. The FD ensures that every vertex has at most one color assigned to it, i.e. for any v i ∈ V , any two e j 1 , e j 2 ∈ E adjacent to v i , and any two different colors k 1 , k 2 ∈ {1, 2, 3}:

p k 1 i,j 1 ∧ p k 2 i,j 2 → false. ( 4
)
The full TGD ensures that the facts q j are properly used to incrementally verify that all edges connect legally colored vertices, i.e. for any edge e j = {v i 1 , v i 2 } and any two different colors k 1 , k 2 ∈ {1, 2, 3}:

p k 1 i 1 ,j ∧ p k 2 i 2 ,j ∧ q j-1 → q j .
The full TGD also requires that if q m is inserted, which indicates a legal coloring, then r or r ′ is to be deleted or r ′′ is to be inserted:

r ∧ r ′ ∧ q m → r ′′ .
Consequently, the query used in the reduction checks if r is not removed from any of the repairs.

Q = r.
The main claim is that:

G ∈ 3COL ⇐⇒ ∃I ′ ∈ Repairs(I G , F ). r ∈ I ′ .
For the only if part, let f be the legal 3-coloring of G. We construct the following instance

I ′ = {p f (i) i,j | v i ∈ V, e j ∈ E, v i ∈ e j } ∪ {q 0 , . . . , q m , r ′ }.
It can be easily verified that this instance satisfies (i), (ii), and (iii) of Lemma 1 and hence I ′ is a repair and r ∈ I ′ .

For the if part, we note that since r ∈ I ′ , by (iii) of Lemma 1 both q m and r ′ are present in I ′ and r ′′ ∈ I ′ . q m ∈ I ′ implies that {q 0 , . . . , q m } ⊆ I ′ . Therefore, for every j ∈ {1, . . . , m} if e j = {v i 1 , v i 2 }, there exist two different colors k 1 and k 2 such that p k 1 i 1 ,j and p k 2 i 2 ,j are present in I ′ . Moreover, for any two p k 1 i,j 1 and p k 2 i,j 2

we have k 1 = k 2 . Hence, the function f (i) = k such that there exists p k i,j ∈ I ′ is a properly defined legal 3-coloring of G.

Finally, we note that the role of the FD can be simulated with a full TGD giving almost the same reduction. Indeed, if we replace the FD with the TGD R(x, y, z 1 , z 2 ) ∧ R(x, y ′ , z ′ 1 , z ′ 2 ) → R(0, 0, 0, 0) and by d denote the fact R(0, 0, 0, 0), then the rules (4) are replaced by p k 1 i,j 1 ∧ p k 2 i,j 2 → d, for every v i ∈ V , any two edges e j 1 , e j 2 adjacent to v i , and any two different colors k 1 , k 2 ∈ {1, 2, 3}. We note that the fact d is not involved in any other rules, and therefore it is only present in a repair which assign two different colors to the same vertex. Now, the query needs to be augmented to check that in no repair r is deleted while d is not inserted, i.e. in all repairs r is absent only if

d is present, Q = (¬r) ⇒ d = r ∨ d.
Corollary 2 There exists a quantifier-free ground query and a set of two full cyclic TGDs for which consistent query answering is coNP-complete.

The complexity of computing consistent answers to atomic ground queries in the presence of full TGDs only remains an open question.

Universal constraints

In this section we investigate the complexity of consistent query answering and repair checking in the presence of arbitrary universal constraints. Lemma 4 For any set of universal constraints F and any closed query Q, repair checking is in coNP and consistent query answering is in Π p 2 .

Proof: We observe that checking if a set of facts is a maximal independent set is in PTIME. The definition of a nondeterministic Turing machine checking if an instance I ′ is not a repair follows from Propositions 3 and 4. First, the machine constructs Compl(I ′ ) and checks if it is a maximal independent set.

If so, it nondeterministically attempts to construct a maximal independent set N such that N + < I I ′ .

The definition of a nondeterministic machine (with an NP oracle) that checks if true is not the consistent query answer follows from Definition 5: true is not the consistent answer if and only if there exists a repair where the query answer is false. Hence, the machine nondeterministically creates an instance I ′ , verifies that I ′ is a repair by using the NP oracle (checking that I ′ is not accepted by the machine constructed above), and verifies that the query answer in I ′ is false.

Theorem 6 There exists a positive atomic query, and a set of two FDs and a universal constraint for which consistent query answering is Π p 2 -complete.

Proof: The membership is proved in Lemma 4. We prove Π p 2 -hardness by reducing the problem of validity of ∀ * ∃ * QBF to D F,Q .

Consider the following ∀ * ∃ * QBF formula: [START_REF] Papadimitriou | Computational Complexity[END_REF].

Ψ = ∀x 1 , . . . , x n . ∃x n+1 , . . . , x n+m . Φ, where Φ = C 1 ∧ . . . ∧ C k is quantifier-free 3CNF i.e., C j is a clause of three literals L j,1 ∨ L j,2 ∨ L j,3 . Recall that checking the validity of ∀ * ∃ * QBF is a classical Π p 2 -complete problem
We assume that no two clauses of Φ are identical. For ease of reference, we call the variables x 1 , . . . , x n universal and the variables x n+1 , . . . , x n+m existential. We also use the following functions on the literals of Φ:

var(x i ) = i, var(¬x i ) = i, sgn(x i ) = 1, sgn(¬x i ) = 0, q(x i ) = q(¬x i ) =    1 if i ≤ n, 0 otherwise.
The schema contains two relation names:

S = {R(A 1 , B 1 , A 2 , B 2 ), D(A 1 , B 1 , C 1 , D 1 , . . . , A 4 , B 4 , C 4 , D 4 )}.
The set of integrity constraints is:

F = {R : A 1 → B 1 , R : A 2 → B 2 , D(x 1 , x2 , x3 , x4 ) → R(x 1 ) ∨ R(x 2 ) ∨ R(x 3 ) ∨ R(x 4 )},
where each xi is a vector of 4 variables. We use the following types of facts in the reduction:

• facts corresponding to the valuations of universal variables (i ∈ {1, . . . , n}): p i = R(i, 1, 0, 0) and pi = R(i, 0, 0, 0), and the valuations of existential variables (i ∈ {n + 1, . . . , n + m}):

p i = R(i, 1, 1, 0) and pi = R(i, 0, 1, 0),
• facts corresponding to the clauses (j ∈ {1, . . . , k}): q j = D(var(l j,1 ), sgn(l j,1 ), q(l j,1 ), 0, var(l j,2 ), sgn(l j,2 ), q(l j,2 ), 0, var(l j,3 ), sgn(l j,3 ), q(l j,3 ), 0, 0, 1, 1, 1),

• 2 special facts:

r = R(0, 1, 1, 1
) and r = R(0, 0, 0, 0).

The constructed instance is

I Ψ = {p 1 , p1 , . . . , p n+m , pn+m , q 1 , . . . , q k , r}.
For the clarity of further considerations by ℓ j,p we will denote the fact corresponding to the satisfying valuation of the literal L j,p , i.e.:

ℓ j,p =    p i when L j,p = x i , pi when L j,p = ¬x i .
Now, we outline the interaction among the facts induced by the integrity constraints. We start with the simple observation that the FD R : A 1 → B 1 ensures that in every repair there is at most one fact corresponding to a valuation of each variable. In symbols:

p i ∧ pi → false for i ∈ {1, . . . , n + m},
The full TGD ensures that for every conjunct if the repair does not have a fact corresponding to a valuation satisfying the conjunct, then the fact q j is deleted or the fact r is inserted:

q j → ℓ j,1 ∨ ℓ j,2 ∨ ℓ j,3 ∨ r for j ∈ {1, . . . , k}.
Inserting r requires removing all the facts corresponding to valuations of the existential variables (the FD R : A 2 → B 2 ):

p i ∧ r → false and pi ∧ r → false for i ∈ {n + 1, . . . , n + m}.
It is important to note that this makes inserting r quite a drastic way to repair the instance I Ψ . Since r does not belong to I Ψ and all facts corresponding to valuations of existential variables do, ≤ I -minimality ensures that such a way of repairing is considered only if for a given valuation of universal variables there does not exist a valuation of existential variables satisfying Ψ. Also, we observe that inserting r requires deleting r, i.e. r ∧ r → false.

Consequently, the query used in the reduction checks if the fact r is not deleted from any of the repairs:

Q = r.
Figure 5 contains the extended conflict hypergraph of

I Ψ for Ψ = ∀x 1 , x 2 , x 3 . ∃x 4 , x 5 . (¬x 1 ∨ x 4 ∨ x 2 ) ∧ (¬x 2 ∨ ¬x 5 ∨ x 3 ).
The dotted lines are used for stabilizing edges.

p 1 p1 p 4 p4 p 2 p2 p 5 p5 p 3 p3 r r ¬p 1 ¬p 4 ¬p 2 ¬r ¬p 2 ¬p 5 ¬p 3 q 1 q 2 Fig. 5. G(I Ψ , F ) for Ψ = ∀x 1 , x 2 , x 3 . ∃x 4 , x 5 . (¬x 1 ∨ x 4 ∨ x 2 ) ∧ (¬x 2 ∨ ¬x 5 ∨ x 3 ).
The main claim of the reduction is :

I Ψ |= F r ⇐⇒ |= Ψ,
where |= Ψ denotes that Ψ is valid.

For the only if part, we start by observing that no repair contains r. We also show that for any consistent instance I 1 ⊆ {p 1 , p1 , . . . , p n , pn } there exists a repair I ′ such that I ′ ≤ I I 1 and such that {q 1 , . . . , q k } ⊆ I ′ . Indeed, consider J = I 1 ∪ {q 1 , . . . , q k , r}. Clearly, it is consistent and since no repair contains r, J is not a repair. Consequently, there exists a repair I ′ such that I ′ < I J.

It is easy to see that I ′ is the required repair. Now, we take any valuation of universal variables V 1 , construct the consistent instance

I 1 = {p i | V 1 (x i ) = true, i ∈ {1, . . . , n}} ∪ {p i | V 1 (x i ) = false, i ∈ {1, . . . , n}},
and take the repair I ′ as described above. Naturally, for every i ∈ {1, . . . , n} either p i or pi belongs to I ′ . The same holds for i ∈ {n + 1, . . . , n + m} because r ∈ I ′ and I ′ is ≤ I -minimal. Consequently, the following valuation of the existential variables x n+1 , . . . , x n+m is properly defined

V 2 (x i ) =    true if p i ∈ I ′ , false if pi ∈ I ′ .
We claim that V 1 ∪ V 2 |= Φ. Take any clause C j and observe that at least one of ℓ j,1 , ℓ j,2 , ℓ j,3 is present in I ′ because r ∈ I ′ , q j ∈ I ′ , and I ′ is a repair. Consequently, V 1 ∪ V 2 assigns true to at least one of L j,1 , L j,2 , L j,3 . Now, we show the if part by contradiction: we assume there exists a repair I ′ such that r ∈ I ′ and we construct a consistent instance I ′′ such that I ′′ < I I ′ .

First, we observe that r ∈ I ′ implies that r ∈ I ′ . By ≤ I -minimality this gives {q 1 , . . . , q k } ⊆ I ′ . Also, for every i ∈ {1, . . . , n} either p i or pi belongs to I ′ and for i ∈ {n + 1, . . . , n + m} neither p i or pi belongs to I ′ .

Consequently, the following valuation of the universal variables x 1 , . . . , x n is properly defined

V 1 (x i ) =    true if p i ∈ I ′ , false if pi ∈ I ′ .
Since |= Ψ, there exists a valuation of the existential variables V 2 such that

V = V 1 ∪ V 2 |= Φ.
The instance I ′′ is defined as follows:

I ′′ ={r, q 1 , . . . , q k } ∪ {p i | V (x i ) = true, i ∈ {1, . . . , n + m}} ∪ {p i | V (x i ) = false, i ∈ {1, . . . , n + m}}.
V |= Φ implies that I ′′ is consistent. Note that I ′ and I ′′ agree on the facts {p 1 , p1 , . . . , p n , pn }, both contain {q 1 , . . . , q k } but I ′′ contains r and some of the facts {p n+1 , pn+1 , . . . , p n+m , pn+m } whereas I ′ contains none of them. This shows that I ′′ is relatively closer to I than I ′ , i.e. I ′′ < I I ′ .

Corollary 3 There exists a set of 2 FDs and one universal constraint for which repair checking is coNP-complete.

Proof: We use the reduction from the proof of Theorem 6 to reduce B F to the complement of 3SAT: a 3CNF Φ is treated as a ∀ * ∃ * QBF with no universally quantified variables. Let F be the set of constraints as defined in the previous reduction and I Φ be the instance obtained from Φ. We take I ′ Φ = {r, q 1 , . . . , q k } and claim that Φ ∈ 3SAT ⇐⇒ I ′ Φ ∈ Repairs(I Φ , F ). The proof of this claim is analogous to the proof of Theorem 6.

Related work

Here we only discuss work relevant to our contributions and we refer the reader to surveys of the topic [START_REF] Bertossi | Consistent query answering in databases[END_REF][START_REF] Bertossi | Query answering in inconsistent databases[END_REF][START_REF] Chomicki | Consistent query answering: Five easy pieces[END_REF][START_REF] Fan | Dependencies revisited for improving data quality[END_REF].

In general, three different approaches to compute consistent query answers have been proposed: query rewriting, logic programming, and compact representation of repairs. Our work belongs to the last category.

Query rewriting was the first approach proposed to compute consistent query answers [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF]. A query Q is rewritten into a query Q ′ whose evaluation returns the set of consistent query answers to Q. An indisputable advantage of this approach is the ease of its incorporation into already existing applications. However, applicability of this approach is limited and certain conjunctive queries are known not to have rewritings [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF][START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF][START_REF] Wijsen | On the consistent rewriting of conjunctive queries under primary key constraints[END_REF].

Arenas et al. [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF] use the notion of residues obtained from constraints to identify potential impact of integrity violations on the query results. The residues are used to construct rewriting rules for the atoms used in the query. This approach has been shown to be applicable to quantifier-free conjunctive queries in the presence of binary universal constraints. Chomicki and Marcinkowski [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF] observe that if the set of constraints contains one FD per relation only, the conflict graph is a union of disjoint full multipartite graphs. This simple structure allows to construct rewriting for simple conjunctive queries, i.e conjunctive queries without repeated relation names and no variable sharing. The result of Chomicki and Marcinkowski has been further generalized by Fuxman and Miller [24,[START_REF] Fuxman | Efficient Query Processing Over Inconsistent Databases[END_REF][START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF] to allow restricted variable sharing (joins) in the conjunctive queries. The class C f orest of allowed queries is defined using the notion of join graph of a query whose vertices are the literals used in the query and an edge runs from a literal R i to literal R j if there is a variable which occurs on a non-key attribute of R i and any attribute of R j (both occurrences have to be different if i = j). The class C f orest consist of queries whose join graph is a forest, the joins are full and the join conditions are non-key to key. Wijsen [START_REF] Wijsen | On the consistent rewriting of conjunctive queries under primary key constraints[END_REF] presents a rewriting scheme for the class of rooted queries which further extends C f orest . We remark that the class of rooted queries is semantically defined and its subclass is captured with syntactic characterization using an alternative notion of the join graph.

Several approaches have been developed to compute consistent query answers using logic programs with disjunction and classical negation [START_REF] Arenas | Answer sets for consistent query answering in inconsistent databases[END_REF][START_REF] Barcelo | Logic programs for querying inconsistent databases[END_REF][START_REF] Eiter | Efficient evaluation of logic programs for querying data integration systems[END_REF][START_REF] Greco | A logic programming approach to the integration, repairing and querying of inconsistent databases[END_REF][START_REF] Greco | A logical framework for querying and repairing inconsistent databases[END_REF][START_REF] Van Nieuwenborgh | Preferred answer sets for ordered logic programs[END_REF]. Essentially, all of them use disjunctive rules to model the process of repairing violations of constraints. In this way stable models of a program correspond to the repairs of the inconsistent database. A query evaluated under the cautious semantics returns the answers present in every model, which naturally yields the consistent query answers.

The main advantage of using this approach is its generality: typically arbitrary first-order (or even Datalog ¬ ) queries are handled in the presence of universal constraints. Also, the repairing programs can be easily evaluated with existing logic program environments like Smodels or dlv [START_REF] Eiter | Declarative problem-solving in dlv[END_REF]. We note, however, that the systems computing answers to logic programs usually perform grounding, which may be cost prohibitive if we are to work with large databases. Another disadvantage of this approach is that the class of disjunctive logic programs is known to be Π 2 p -complete.

These difficulties are addressed in the INFOMIX system [START_REF] Eiter | Efficient evaluation of logic programs for querying data integration systems[END_REF] with several optimizations geared toward effective execution of repairing programs. One is localization of conflicts with identification of the affected database which consists of all facts involved in constraint violations and all syntactically propagated conflict-bound facts (analogous to applying T * F ). Another optimization involves using bit-vectors to encode fact membership to each repair and subsequent use of bitwise aggregate function to find tuples that present in every repair. This optimization, however, may be insufficient to handle databases with large numbers of conflicts because typically the number of repairs is exponential in the number of conflicts. Recently, this deficiency has been addressed with repair factorization [START_REF] Eiter | Repair localization for query answering from inconsistent databases[END_REF]. Essentially, the affected database is decomposed into parts that are conflict-disjoint (no two mutually conflicting facts are in separate parts). When computing consistent answers to a query only parts that are simultaneously spanned by the query are considered at a time. We observe an analogy to computing consistent query answers using hypergraphs: when finding whether true is the consistent answer to a ground query Algorithm 3 analyzes base fragments of repairs obtained by combining the hyperedges adjacent to facts from the query.

Our work was inspired by positive results for denial constraints presented in [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF]. There, the repairs are obtained by deleting facts only and consequently the repairs are subsets of the original instance. Chomicki and Marcinkowski [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF] Using subset repairs is natural in scenarios like data warehousing, where the data are complete but may be incorrect. In particular we can assume that if a fact is not present in the original database, then it is not true. Obtaining repairs by deletion of facts only is not necessarily a natural approach in the scenarios where we cannot assume that information missing in the database is false, for instance in the context of integration of sources that may be missing some information. Then, we might want to consider standard repairs obtained by deleting and inserting a minimal set of facts, i.e. repairs in the sense of Definition 4. We observe, however, that while in the case of universal constraints the missing facts that create conflicts are implicitly defined, the presence of existentially quantified variables in INDs leads to possibly infinite number of repairs.

Cali et al. in [START_REF] Cali | On the decidability and complexity of query answering over inconsistent and incomplete databases[END_REF] Another compact representation of all repairs is nucleus [START_REF] Wijsen | Condensed representation of database repairs for consistent query answering[END_REF][START_REF] Wijsen | Database repairing using updates[END_REF]. In this approach all repairs are represented by a tableau (a table with free variables), and queries are evaluated in the standard way (answers with variables are discarded). We note that for some classes of constraints, constructing the nucleus may take an exponential time to complete.

Afrati and Kolaitis [START_REF] Afrati | Repair checking in inconsistent databases: algorithms and complexity[END_REF] provides an thorough study of the complexity of repair checking for four different notions of minimality used to define repairs: minimality of symmetric set difference (Definition 4), minimality of asymmetric set difference (which yields subset repairs), minimality of the cardinality of symmetric set difference, and minimality of the cardinality of symmetric difference on every relation. The classes of the considered integrity constraints include denial constraints, inclusion dependencies, equality-generating dependencies, and weakly acyclic and local-as-view (LAV) tuple-generating dependencies. The results offer additional insight into the problem of repair checking in the presence of full TGDs for the symmetric and asymmetric set difference notion of minimality. The authors show that for full TGDs repair checking is PTIME-hard, which in view of Theorem 1 makes the problem PTIMEcomplete. It is a general belief, based on the assumption NC PTIME, that there do not exist fast parallel algorithms for PTIME-complete problems. This suggest that database repairing (Algorithm 2) using a parallel computation model does not guarantee an efficiency improvement. However, the authors also show that for weakly acyclic LAV tuple-generating dependencies the prob-lem is in LOGSPACE (which is included in NC). On the other hand, repair checking easily becomes coNP-complete if we relax the restrictions on the set of constraints; for instance, if we consider weakly acyclic TGDs without the LAV restriction. We remark that these results are orthogonal to Theorem 1 as the classes of constraints are incomparable.

Conclusions and future work

In this paper we investigated the complexity of computing consistent query answers in the presence of universal constraints. We proposed an extended version of the conflict hypergraph. Its size is polynomial in the size of the database and it captures all repairs w.r.t. to the given set of universal constraints. Hence, we consider it to be a compact representation of all repairs. This property is essential for using the extended conflict hypergraph to compute consistent query answers.

Extending the notions of conflicts to include negations of facts leads, however, to a significant increase of computational complexity. Consistent query answering is Π 2 P -complete in the presence of universal constraints even when using atomic queries. The problem becomes coNP-complete when we restrict the set of constraints to contain full tuple-generating dependencies and denial constraints only; then the conflicts can contain at most one negation of a fact. If we further restrict the integrity constraints to join dependencies, denial constraints, and acyclic full tuple-generating dependencies, then the problem of consistent answering becomes tractable for quantifier-free queries. Consequently, we present an extension of the algorithm of Chomicki and Marcinkowski [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF] that finds if true is the consistent answer to a closed quantifier-free query.

The problem of repair checking is also intractable for universal constraints. It becomes tractable if we restrict the constraints to full tuple-generating dependencies and denial constraints. Consequently, we present a polynomial repairing algorithm. It is both sound (always produces a repair) and complete (every repair can be produced).

The summary of computational complexity results is presented in Table 1; its last row is taken from [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF].

We envision several possible directions of future study. First, we would like to investigate practical applicability of our approach. The main obstacle lays in the high degree of the polynomials used to bound the number of of all supports and blocks, and consequently in the high degree of the polynomial describing the complexity of Algorithm 3. We observe that the bounds are we believe that the positive results carry to the setting of subset repairs as well.

A Omitted proofs Proposition 9 For any set of JDs {jd 1 , . . . , jd n } on the same relation there exists a JD jd * such that an instance satisfies {jd 1 , . . . , jd n } if and only if it satisfies jd * .

Proof: The proof is by induction over n. For n = 0 we note that every relation satisfies the trivial JD: R ✶:[attrs(R)], where attrs(R) is the set of all attributes of R. The hypothesis is also trivially satisfied for n = 1. To show the inductive step it suffices to show that two JDs jd 1 = R ✶:[X 1 , . . . , X n ] and

jd 2 = R ✶:[Y 1 , . . . , Y m ] are equivalent to jd * = R ✶:[X 1 ∩ Y 1 , . . . , X 1 ∩ Y m , . . . , X n ∩ Y 1 , . . . , X n ∩ Y m ].
To prove this equivalence we use standard relation algebra [START_REF] Abiteboul | Foundations of Databases[END_REF] and recall that a JD R ✶:[Z 1 , . . . , Z k ] is defined as R = π Z 1 (R) ✶ . . . ✶ π Z k (R).

First we note that every instance satisfies π Z 1 (R) ✶ . . . ✶ π Z k (R) ⊆ R for any sets Z 1 , . . . , Z k of attributes of R whose union is attrs(R). Hence, it suffices to show that R ⊆ π X 1 ∩Y 1 (R) ✶ . . . π X 1 ∩Ym (R) ✶ . . . ✶ π Xn∩Y 1 (R) ✶ . . . π Xn∩ym (R) in any instance I that satisfies jd 1 and jd 2 .

We fix an instance I and let r be the set of all tuples that belong to the relation R in I. Take any t ∈ r and let t X i = π X i (t) , t Y j = π Y j , and t X i ∩Y j = π X i ∩Y j (t) for any i ∈ {1, . . . , n} and any j ∈ {1, . . . , m}. Since I satisfies jd 1 and jd 2 , we have that t = t X 1 ✶ . . . ✶ t Xn ∈ r and t = t Y 1 ✶ . . . ✶ t Ym ∈ r. Now, we observe that t X 1 ∩Y 1 ✶ . . . ✶ t X 1 ∩Ym ✶ . . . ✶ t Xn∩Y 1 ✶ . . . ✶ t Xn∩Ym = t X 1 ✶ . . . ✶ t Xn .

We recall that the lhs of a ground rule is represented with a set of facts obtained from grounding the atoms of some constraint. If the same fact is obtained by grounding more than one atom in the constraint, then it is not repeated in the ground rule. We continue to use this representation, but on some occasions we will require to know the duplicates in ground JD rules. Then, the lhs is represented with a bag rather than a set, and we call such a rule unfolded.

Naturally, every rule can be unfolded, although not always unambiguously. We remark that this ambiguity does not affect the correctness our considerations, and hence we ignore it.

Example 12 (Unfolded rule) Suppose a schema consisting of one relation name R(A, B, C, D) and let the set of integrity constraints contain one JD R ✶:[AB, BC, CD] which is represented with the following formula R(x, y, z, s) ∧ R(x ′ , y, z ′ , s ′ ) ∧ R(x ′′ , y ′′ , z ′ , s ′′ ) → R(x, y, z ′ , s ′′ ).

The following ground rule is one of possible instantiations of the formula above. R(0, 0, 0, 0) ∧ R(1, 0, 0, 1) → R(0, 0, 0, 1).

Its unfolding is R(0, 0, 0, 0) ∧ R(1, 0, 0, 1) ∧ R(1, 0, 0, 1) → R(0, 0, 0, 1).

Lemma 3 If Rules(I, F ) contains the following two unfolded ground rules

r ′ = R(t ′ 1 ) ∧ . . . ∧ R(t ′ k ) ✶ → R(t i ) and r ′′ = R(t 1 ) ∧ . . . ∧ R(t k ) ✶ → R(t)
for some i ∈ {1, . . . , k}, then there exists j ∈ {1, . . . , k} such that Rules(I, F ) contains also r * = R(t 1 ) ∧ . . . ∧ R(t i-1 ) ∧ R(t ′ j ) ∧ R(t i+1 ) ∧ . . . ∧ R(t k ) ✶ → R(t).

Proof: We assume that the rules are obtained from grounding the join dependency R ✶:[X 1 , . . . , X k ] and recall that it is represented as the following full TGD:

R(x 1 ) ∧ . . . ∧ R(x k ) ∧ 1≤α,β≤k xα [X α ∩ X β ] = xβ [X β ∩ X α ] → R(ȳ),
where ȳ ⊆ x1 ∪ . . . ∪ xn such that ȳ[X α \ 1≤β<α X β ] = xα [X α \ 1≤β<α X β ] for α ∈ {1, . . . , k}. W.l.o.g. we assume that the order of facts in the lhs of rules r ′ and r ′′ corresponds to the order of the atoms in the definition of the constraints. With this assumption a rule R(s 1 ) ∧ . . . ∧ R(s k ) ✶ → R(s) belongs to Rules(I, F ) if and only if

s α [X α ] = s[X α ]
for every α ∈ {1, . . . , k} (A.1)

s α [X α ∩ X β ] = s β [X α ∩ X β ]
for every α, β ∈ {1, . . . , k}. (A.2)

Also, with the assumption on the order in which the facts are listed in rules, we show that the claim of the lemma holds for j = i. The if part is proved with a simple induction over the depth of derivation of a block. The proof of the only if part, although technically complex, is based on the following simple idea. R(t) ∈ I \ I ′ is absent in the repair I ′ because its presence would cause a violation of some ground rule. We identify this rule by considering an inconsistent instance I ′ ∪ {R(t)}. We use this rule to show that R(t) has a proper block.

Recall that the acyclic depth depth(R) in D(S, F ) of a relation name R is the maximal length of a directed acyclic path that ends in R. For ℓ ∈ {-1, 0, . . . , h} we define S ℓ = {R ∈ S | depth(R) ≤ ℓ}. Note that S h = S as the acyclic depth of every relation name is bounded by the acyclic height of D(S, F ).

We show with an induction over ℓ that for R ∈ S ℓ R(t) ∈ I ′ ⇒ ∃(B, N ) ∈ Block ℓ (R(t)). B ⊆ I ′ ∧ N ∩ I ′ = ∅.

For ℓ = -1 the claim is trivially true because S -1 = ∅. We prove the inductive step by contradiction: we assume that the set of facts that are not in I ′ and that do not have a proper ℓ-block, T = {R(t) ∈ Hull(I, F ) \ I ′ | R ∈ S l ∧ R(t) has no proper ℓ-block} endalign* is nonempty. We note that T ⊆ I \ I ′ because any fact R(t) ∈ Hull(I, F ) \ I has a proper block obtained with the rule B -1 0 . Now, take any element R(t) ∈ T , let jd R ∈ F be the JD on relation R, and consider the set V = T {jd R } (I ′ ∪ {R(t)}) \ I ′ . For any R(t ′ ) ∈ V by r R(t ′ ) we denote an arbitrarily chosen ground JD rule R(t) ∧ R(t 1 ) ∧ . . . R(t k ) ✶ → R(t ′ ) such that every R(t i ) ∈ I ′ . We claim that: (1) I ′ ∪ V is consistent, and (2) V ⊆ T .

(1) Because I ′ ∪ V is obtained by adding facts using the relation name R to a consistent instance, we only need to verify that ground rules having R in their lhs are satisfied.

First, take an (unfolded) ground JD rule

r ′′ = R(t ′ 1 ) ∧ . . . ∧ R(t ′ p ) ∧ R(t 1 ) ∧ . . . ∧ R(t k ) ✶ → R(s)
such that every R(t ′ i ) belongs to V and every R(t i ) belongs to I ′ . We iteratively apply Lemma 3 to the rule above using rules r R(t ′ i ) and obtain the rule

R(t * 1 ) ∧ . . . ∧ R(t * p ) ∧ R(t 1 ) ∧ . . . ∧ R(t k ) ✶ → R(s),
where each R(t * i ) is either R(t) or belongs to I ′ . If all R(t * i )'s belong to I ′ , then R(s) ∈ I ′ because I ′ is consistent. Otherwise, R(s) ∈ V .

For the remaining (non-JD) ground rules, we show that if such a rule is not satisfied in I ′ ∪ V , then a proper ℓ-block for R(t) can be constructed (which contradicts R(t) ∈ T ). If there is a ground denial rule

R(t ′ 1 ) ∧ . . . ∧ R(t ′ n ) ∧ R 1 (s 1 ) ∧ . . . ∧ R m (s m ) → false
such that every R(t ′ i ) ∈ V and every R j (s j ) ∈ I ′ , then a proper ℓ-block of R(t) is constructed with the rule B -1 1 . Similarly, if there is a ground rule

R(t ′ 1 ) ∧ . . . ∧ R(t ′ n ) ∧ R 1 (s 1 ) ∧ . . . ∧ R m (s m ) → P (s)
such that every R(t ′ i ) ∈ V , every R j (s j ) ∈ I ′ , and P (s) ∈ I ′ ∪ V , then by IH P (s) has a proper (ℓ -1)-block and a proper ℓ-block is constructed with the rule B ℓ 2 .

(2) For R(t ′ ) ∈ V we show that if R(t ′ ) has a proper ℓ-block, then R(t) has a proper ℓ-block as well (which contradicts R(t) ∈ T ). Suppose some R(t ′ ) ∈ V has a proper ℓ-block constructed with the following instance of the rule B ℓ 2 :

r = R(t ′ 1 ) ∧ . . . ∧ R(t ′ n ) ∧ R 1 (s 1 ) ∧ . . . ∧ R m (s m ) → P (s) r i = R(t ′ ) ∧ R(t ′ i,1 ) ∧ . . . ∧ R(t ′ i,k i ) ✶ → R(t ′ i )
∀i ∈ {1, . . . , n} S i,j ∈ Supp(R(t ′ i,j )) ∀i ∈ {1, . . . , n}, ∀j ∈ {1, . . . , k i } S p ∈ Supp(R p (t p )) ∀p ∈ {1, . . . , m} R(t ′ ) ∈ I (B, N ) ∈ Block ℓ-1 (P (s)) ( i,j S i,j ∪ p S p ∪ B, N ) ∈ Block ℓ (R(t ′ ))

For every i ∈ {1, . . . , n} we apply Lemma 3 to r ′ = r R(t ′ ) and r ′′ = r i , and obtain r * i . 2 We observe that for every i ∈ {1, . . . , n} if the ground rule r * i does not have R(t) in its lhs, then all the facts in its lhs belong

Fig. 1 .

 1 Fig. 1. Inconsistent database I 1 .

2 =

 2 yes), N F (M ary, no), N F (Donald, yes), P arent(Steve, Donald), P arent(M ary, Donald)}. I ′ {N F (Steve, no), N F (M ary, yes), N F (Donald, yes), P arent(Steve, Donald), P arent(M ary, Donald)}.

4 =

 4 no), N F (M ary, no), N F (Donald, yes), P arent(M ary, Donald)}. I ′ {N F (Steve, no), N F (M ary, yes), N F (Donald, yes), P arent(Steve, Donald)}.

Example 3 Figure 3 Fig. 3 .

 333 Fig. 3. A cyclic dependency graph.

Example 4

 4 Consider a schema S = {R(A, B), P (C)} with one constraint F = {R(x, y) ∧ P (x) → P (y)} and take I = {R(1, 2), R(2, 3), P (1)}. The conflict {R(1, 2), P (1), ¬P (2)} can be resolved by inserting P (2) into the instance I to obtain: I ∪ {P (2)}. This creates the conflict {R(2, 3), P (2), ¬P (3)} which can be resolved by further inserting P (3). Finally, we obtain the repair I 1 = I ∪{P (2), P (3)}. The other repairs are I 2 = I \{R(1, 2)}, I 3 = I \{P (1)}, and

Example 6 Figure 4

 64 contains the extended conflict hypergraph G 1 for the instance I w.r.t the set of universal constraints F from Example 4. A dotted R(1, 2)

Fig. 4 .

 4 Fig. 4. The extended conflict hypergraph G 1 for I and F from Example 4.

5 :

 5 choose R(t) ∈ I o and b ∈ {true, false} 6:

  existsRepair(T P , T N ) 7: if T P ⊆ Hull(I, F ) then 8: return false 9: if T N ⊆ Hull(I, F ) then 10:

  Now, recall that T ⊆ I ′ \ I, and therefore I ′ \ T ≤ I I ′ . Since I ′ is ≤ I -minimal consistent instance, I ′ \ T = I ′ , and consequently T = ∅.Proposition 11 For every I ′ ∈ Repairs(I, F ) and every R(t) ∈ Hull(I, F )R(t) ∈ I ′ ⇐⇒ ∃(B, N ) ∈ Block(R(t)). B ⊆ I ′ ∧ N ∩ I ′ = ∅.Proof: We fix a repair I ′ and we say that an ℓ-block (B, N ) of R(t) ∈ Hull(I, F ) is proper if B ⊆ I ′ and N ∩ I ′ = ∅.

  1, 2, 2) would require adding also P (1, 2), and cause inclusion of the banned set {P (1, 2)}. Hence, we discard R(1, 2, 2), and finally, obtain the empty repair ∅. We observe that if the fact R(1, 2, 2) were added (together with P (1, 2)), the obtained instance {R(1, 2, 2), P (1, 2)}, although consistent, would not be ≤ I 2 -minimal (the repair {R(1, 2, 1), R(1, 2, 2), P (1, 2)} is relatively closer to I 2 ).Finally, we consider the instance I 3 = {R(1, 1, 1), P (1, 1), P (1, 2)} and begin with the fact R(1, 1, 1). Discarding it would require memorizing the banned set {P (1, 1)}. However, this set is not appropriate for our purposes because the fact P (1, 1) is present in the original instance and later we might be forced to add it to the constructed instance. Hence, we add the fact R(1, 1, 1) (together

with P (1, 1)). Next, we add the fact P (1, 1) but ignore the fact P (1, 2). The constructed instance {R(1, 1, 1), P (1, 1)} is a repair. Now, we present a sound and complete Algorithm 2 constructing a repair of a (possibly inconsistent) instance I w.r.t. a set F of full TGDs and denial constraints. It starts with an empty instance J and iterates over the facts of Algorithm 2 Constructing a repair of I w.r.t. a set of full TGDs F 1: I o ← I 2: J ← ∅ 3: Banned ← ∅ 4: while I o = ∅ do

  Query in CNF */ 2: for i ← 1, . . . , w do

	3:

  also investigate using subset repairs obtained to define consistent query answers in the presence of inclusion dependencies (IND), i.e. formulas of the form ∀x1 ∃x 3 . R(x 1 ) → P (x 2 , x3 ), where x2 ⊆ x1 . An IND of this form is commonly written R[X] ⊆ P [Y ],where X and Y are the sets of attributes corresponding to x2 in R and P respectively. An IND R[X] ⊆ P [Y ] is a foreign-key dependency if Y is the key of P . We note that universal constraints capture only full INDs, i.e. INDs with no existentially quantified variables.[START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF] shows that consistent query answering is in PTIME for quantifier-free and simple conjunctive queries in the presence of foreign-key dependencies and one key dependency per relation.It is also shown that relaxing the restriction on the set of integrity constraints leads to intractability and consistent query answering for arbitrary sets of INDs and FDs becomes Π p 2 -complete.

  show that consistent query answering becomes undecidable for arbitrary sets of INDs and FDs. The problem becomes decidable when the set of integrity constraints is restricted to non-key-conflicting INDs; IND R[X] ⊆ P [Y ] is non-key-conflicting if Y is not a strict superset of the key of P . Then, the problem of consistent query answering is Π 2

p -complete.

More precisely, we take an unfolded version of r ′′ and apply Lemma

to every occurrence of R(t ′ ) in r ′′ .

and, from IH, at most (R K+1 N K 2 ) ℓ+1 (ℓ -1)-blocks. Together, this gives us exactly P = (R K+1 N K 2 ) ℓ+2 . Finally, we observe that both N and P are polynomials when viewed as functions of the size of I.

Preprint submitted to Information Systems

⋆ Research partially supported by NSF grants IIS-0119186 and IIS-0307434 and Enumeration project ANR-07-blanc * Corresponding author. Part of this research was done when the author was a PhD student at the University at Buffalo 1

Repairs(I, F ) consists of the following instances:

{R(1, 1, 1), P (1, 1), Q(1), Q(2)}, I ′ 3 = {R(1, 2, 1), P (1, 2), Q(1), Q(2)}.

The facts from I have simple supports obtained with the rule S 0 :

Supp(R(1, 1, 1)) = {{R(1, 1, 1)}}, Supp(P (1, 2)) = {{P (1, 2)}}, Supp(R(1, 2, 1)) = {{R(1, 2, 1)}}, Supp(Q(2)) = {{Q(2)}}.

The fact P (1, 1) has only one support obtained with the rule S 1 :

Supp(P (1, 1)) = {{R(1, 1, 1)}}.

Finally, Q(1) has two supports:

The supports of a fact define conditions that ensure that it is present in the repair.

Proposition 6 For every I ′ ∈ Repairs(I, F ) and every R(t) ∈ Hull(I, F ) R(t) ∈ I ′ ⇐⇒ ∃S ∈ Supp(R(t)). S ⊆ I ′ .

The proof is by a simple induction over the position of the relation name R in a topological sort of the dependency graph D(S, F ). The proof of a more general claim (Proposition 10) can be found in Appendix A.

Blocking a fact is more complex. First, the facts that are not present in the original instance I need to be added in the process of creating a repair. In this case we can explicitly forbid adding this fact (rule B 0 ). For instance, the fact Q(1) can be blocked this way. Facts that belong to I can be blocked using conflicts they are involved in. If a fact is involved in a denial conflicts then it is blocked by the presence of other facts that together lead to a conflict (rule B 1 ). Finally, blocks can be propagated using full TGDs (rule B 2 ).

Consequently, a block of a fact consists of two sets: one indicating the facts from I that need to be present in the repair and the other one indicating a fact that must not be added to the repair.

Definition 12 (Block) A block of a fact R(t) ∈ Hull(I, F ) is a pair that consists of a subset of I and a set of at most one fact from Hull(I, F ) \ I, defined with the following rules:

where Block(R(t)) being the set of all blocks of R(t).

Blocks specify the conditions that ensure a fact to be absent in a repair.

Proposition 7 For every I ′ ∈ Repairs(I, F ) and every R(t) ∈ Hull(I, F )

The proof is by induction over the position of R in a reverse topological sorting of D(S, F ). The proof of a more general claim (Proposition 11) can be found in Appendix A. We remark, however, that acyclicity of F is essential here.

Example 10 (cont. Example 9) The facts Q(1) and P (1, 1) have simple blocks obtained with the rule B 0 :

The fact R(1, 1, 1) has one block obtained with the rule B 2 :

The fact P (1, 2) has two blocks obtained with the rules B 1 and B 2 :

The fact R(1, 2, 1) has two blocks obtained with the rule B 2 :

Finally, the fact Q(2) has no blocks (it does not participate in any conflict):

Proposition 10 For every I ′ ∈ Repairs(I, F ) and every R(t) ∈ Hull(I, F )

The if part is proved with a simple induction over the depth of the derivation of a support. The proof of the only if is based on the following simple idea. A fact R(t) ∈ I ′ \ I is present in the repair I ′ to satisfy some ground (full TGD) rule.

We identify this ground rule by considering an inconsistent instance I ′ \{R(t)}.

We use this rule to show that R(t) has a support that validates the claim.

Again, because the set of constraints is cyclic, we construct the block iteratively to bound their derivation depth. The new rules for block are obtained by appropriately incorporating JD-rules into B 0 , B 1 , and B 2 (Definition 12).

Definition 14 (Block) Let h be the acyclic height of the dependency graph D(S, F ). For ℓ ∈ {-1, 0, . . . , h} an ℓ-block of a fact R(t) ∈ Hull(I, F ) is a pair that consists of a subset of I and a set of at most one fact from Hull(I, F ) \ I, defined with the following rules:

where

Also this time, we observe that because → and ✶ → are reflexive, the rule B ℓ 1 properly propagates blocks, i.e. any (ℓ -1)-block of R(t) is also an ℓ-block of R(t). We also note that this definition of blocks generalizes Definition 12.

Proposition 11 For every I ′ ∈ Repairs(I, F ) and every R(t) ∈ Hull(I, F ) estimates of the pessimistic case where the number of conflicts (ground rules) in the database is very high and the set of integrity constraints very complex. We believe that in practical scenarios the amount of conflicts is small enough to be stored in the main memory and the acyclic height of the set of integrity constraints rather small. Although computing consistent answers to arbitrary conjunctive queries is long known to be intractable [START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF], considerable effort has been made to find practical subclasses of conjunctive queries for which consistent answering is tractable [START_REF] Wijsen | On the consistent rewriting of conjunctive queries under primary key constraints[END_REF][START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF][START_REF] Grieco | Consistent query answering under key and exclusion dependencies: algorithms and experiments[END_REF]. Usually, tractability comes at the price of restricting the class of constraints to primary key constraints. However, it would be interesting to see for what subclasses of universal constraints similar techniques could be used to handle conjunctive queries. Another interesting challenge in this direction is a generalization of Algorithm 3 to handle sets of universal constraints and arbitrary queries with quantifiers. Because of the negative complexity results, we cannot expect that a generalized algorithm would work in polynomial time (unless P=NP). We believe, however, that in most practical cases such an algorithm should not require exponential time. This belief is based on the promising results of heuristics used to optimize the INFOMIX system [START_REF] Eiter | Efficient evaluation of logic programs for querying data integration systems[END_REF][START_REF] Eiter | Repair localization for query answering from inconsistent databases[END_REF] and its conceptual closeness to Algorithm 3 (see Section 7).

It would be interesting to see if using an alternative definition of repairs would affect the complexity of consistent query answering and repair checking in the presence of universal constraints. For instance, we observe that if we consider repairs obtained by deleting facts only, then the repairs are maximal consistent subsets of the original instance. It would seem that this property simplifies reasoning about repairs allowing to employ algorithms similar to those used for denial constraints (where all repairs are obtained by deleting facts only). For example, a subset I ′ of an instance I is a repair of I w.r.t. to a set of denial constraints if and only if I ′ ∪ {R(t)} is inconsistent for any R(t) ∈ I \ I ′ . This is not necessarily true in the case of universal constraints, where we need to check that I ′ ∪ X is inconsistent for every nonempty X ⊆ I \ I ′ . In fact, our preliminary research shows that this problem remains coNP-complete. Also,

and from (A.2) for r ′ (for

for every β ∈ {1, . . . , k}. The remaining equations needed to prove r * follow trivially from (A.1) and (A.2) for r ′′ . Proposition 10 For every I ′ ∈ Repairs(I, F ) and every R(t) ∈ Hull(I, F )

Proof: We fix a repair I ′ and we say that an ℓ-support S of R(t

The if part is proved with a simple induction over the depth of the derivation of a support. The proof of the only if is based on the following simple idea. A fact R(t) ∈ I ′ \ I is present in the repair I ′ to satisfy some ground (full TGD) rule. We identify this ground rule by considering an inconsistent instance I ′ \{R(t)}. We use this rule to show that R(t) has a proper support.

Recall that the acyclic height height(R) in D(S, F ) of a relation name R is the maximal length of a directed acyclic path that begins in R. For ℓ ∈ {-1, 0, . . . , h} define S ℓ = {R ∈ S | height(R) ≤ ℓ} and note that S h = S.

We show with induction over ℓ ∈ {-1, 0, . . . , h} that for R ∈ S ℓ R(t) ∈ I ′ ⇒ ∃S ∈ Supp ℓ (R(t)). S ⊆ I ′ .

For ℓ = -1 the claim is trivially true because S -1 = ∅. We prove the inductive step by taking the set of all facts in I ′ that do not have a proper support:

We observe that T ⊆ I ′ \ I because all facts that belong to I have a proper support obtained with the rule S -1 0 . Also, by IH T contains no facts using a relation name from S ℓ-1 , i.e. T contains only facts using relations names whose acyclic height is ℓ. Now, we show that I ′ \ T is consistent. As a subset of a consistent instance it satisfies all denial constraints. Hence, we only need to check satisfiability of ground full TGD rules having in the rhs a relation name of acyclic height ℓ.

First, we take a non-JD ground rule

such that every R(t i ) ∈ I ′ \ T . Repeatedly we use Lemma 3 and instances of S ℓ 1 , used to obtain proper ℓ-supports of R(t i )'s, to show the existence of the following elements:

for every p ∈ {1, . . . , k},

• proper (ℓ -1)-supports S * p,q of R p,q (t * p,p ) for every p ∈ {1, . . . , k} and q ∈ {1, . . . , n p }.

For p ∈ {1, . . . , k}, let the ℓ-support of R(t p ) be obtained with the following instance of S ℓ 1 :

We apply Lemma 3 to

to obtain

where R(t * p ) = R(t ′ j ) for some j ∈ {1, . . . , k p } indicated by Lemma 3. From the instance of S ℓ 1 , for r * p we take r ′ p,j , and for S * p,q we take S j,q for every q ∈ {1, . . . , m j }.

The elements above show that R(t) has a proper support, i.e. R(t) ∈ T . Again, R(t) ∈ I ′ because I ′ is consistent. This finishes the proof that I ′ \ T is consistent.

to I ′ and consequently have a proper support. Let X ⊆ {1, . . . , n} be the set of indexes of all rules r * i which have R(t) in their lhs. Using B ℓ 1 with the ground rules r, r * i for i ∈ X, the corresponding proper supports, and the proper (ℓ -1)-block of P (s) we obtain a proper ℓ-block of R(t).

Finally, we observe that I ′ ∪ V < I I ′ because V ⊆ T ⊆ I \ I ′ . However, I ′ is by definition a ≤ I -minimal consistent instance; a contradiction. Proposition 12 For any fact R(t) the sets Supp(R(t)) and Block(R(t)) can be constructed in time polynomial in the size of I.

Proof: Here we only give a combinatorial argument showing that the number of all supports and blocks of a fact is bounded by a polynomial of the size of I. A polynomial algorithm that generates the supports and blocks can be easily derived.

By K we denote the maximum number of atoms used in the definition of a constraint in F . Since we assume the set of constraints to be fixed, K is a constant. Also, note that the acyclic height h of the dependency graph D(S, F ) is bounded by the cardinality of S.

We recall that every ground rule corresponds to a subset of Hull(I, F ) of cardinality at most K. Hence, the number of all ground rules is bounded by

First, with a simple induction over ℓ ∈ {-1, 0, . . . , h} we show that the number of all ℓ-supports of a fact is bounded by N = R (K+1) 2(ℓ+1) . This bound holds trivially for ℓ = -1. To show the inductive step, we note that S ℓ 1 can be instantiated with at most R K+1 possible combinations of ground rules and (ℓ -1)-supports of K 2 facts. By IH each of the facts has at most R (K+1) 2ℓ (ℓ -1)-supports. Together, the number of possible combinations is bounded by

=R (K+1) 2(ℓ+1) -(2K+1)(K+1) 2ℓ +K+1 ≤ R (K+1) 2(ℓ+1) .

Hence the number of all supports of a fact is bounded by N = R (K+1) 2(h+1) . Now, with a simple induction over ℓ ∈ {-1, 0, . . . , h} we show that the number of all ℓ-blocks of a fact is bounded by (R K+1 N K 2 ) ℓ+2 . For ℓ = -1 the set of supports is constructed either with B -1 0 or B -1 1 . For the former the claim holds trivially. For the latter we observe that there are at most R K+1 combinations of ground rules and N K 2 combinations of supports used in B -1 1 , giving together R K+1 N K 2 . Similarly, for the inductive step we observe that B ℓ 2 can be instantiated with R K+1 combinations of rules, N K 2 combinations of supports,