Michael Benedikt

Pierre Bourhis Balder Ten Cate

Gabriele Puppis

Querying Visible and Invisible Information

We provide a wide-ranging study of the scenario where a subset of the relations in the schema are visible -that is, their complete contents are known -while the remaining relations are invisible. We also have integrity constraints (invariants given by logical sentences) which may relate the visible relations to the invisible ones. We want to determine which information about a query (a positive existential sentence) can be inferred from the visible instance and the constraints. We consider both positive and negative query information, that is, whether the query or its negation holds. We consider the instance-level version of the problem, where both the query and the visible instance are given, as well as the schema-level version, where we want to know whether truth or falsity of the query can be inferred in some instance of the schema.

Introduction

There are many applications scenarios where there is a collection of relations representing information of interest to a set of users, but a given user or class of users has access to only a subset of these relations. For example a data owner may restrict access to a subset of the stored relations for privacy reasons. Another example comes from information integration where the schema exposed to users contains both stored relations and "virtual relations". The virtual relations can be referenced in user queries, but are defined by logical constraints relating them to stored relations. Both of these scenarios can be subsumed by considering a schema consisting of a set of relations that must satisfy a set of integrity constraints (invariants specified by sentences in some logic) with only a subset of the relations visible. A basic computational problem is what questions can be answered by means of reasoning with the constraints and access to the visible relations. Can someone use the content of the visible relations along with constraints to answer a given question about the invisible relations?

We study exactly this scenario, where a set of semanticallyrelated relations are hidden while for another set the complete contents are visible. We will consider semantic relationships specified in a variety of logical languages that are rich enough to capture complex relationships between relations, including relationships that arise in information integration, as well as common integrity constraints within a single source. The basic analysis problem will be the following: given a schema and a query Q (also given as a logical formula; for simplicity we focus on sentences), can we in- The query Q = ∃ a ȳ Appointment("Smith", a, "Jones", ȳ) asking whether patient Smith made an appointment with Dr. Jones will be secure under this schema in one sense: an external user with access to Patient will never be sure that the query is true, in any instance. We say that there can be no Positive Query Implication for this query and schema, on any instance. But suppose we consider whether a user can infer the query to be false? On many instances, such an inference is not possible. But on an instance where the visible relation Patient is empty, an external user will know that the query is false. We say that there is a Negative Query Implication on the visible instance where Patient is empty.

Our results. We will consider the instance-based problems: given a query and instance, can a user determine that the query is true (Positive Query Implication) or that the query is false (Negative Query Implication)? We also look at the corresponding schemalevel problem: given a query and a schema, is there some instance where a query implication of one of the above types occurs?

We start by observing that the instance-level problems, both positive and negative, are decidable for a broad class of constraints. However, when we analyze the complexity of the decision problem as the size of the instance increases, we see surprisingly different behavior between the positive and negative case. For very simple constraints the negative query implication problems are wellbehaved as the instance changes, namely, in polynomial time and definable within a well-behaved query language. For the same class of constraints, the corresponding positive query implication questions are hard even when the schema and query are fixed.

When we turn to the schema-level problems, even decidability is not obvious. We prove a set of "critical instance" results, showing that whenever there is an instance where information about the query can be implied, the "obvious instance" witnesses this. Thus, schema-level problems reduce to special cases of the instance-level problems. Although we use this technique to obtain decidability and complexity results both for positive and for negative query implication, the classes of constraints to which they apply are different. We give undecidability results that show that when the classes are even slightly enlarged, decidability of the existence of a schema with a query implication is lost. Our techniques. We introduce a number of tools for reasoning on mixtures of complete and incomplete information.

• Embeddings in rich decidable logics. Our first technique involves showing that a large class of instance-level problems can be solved by translating them into satisfiability problems for a rich fragment of first-order logic, the guarded nega-tion fragment. This exploits powerful prior decidability results "off-the-shelf". However, to get tight complexity bounds, we also need a new analysis of the complexity of this logic.

• Decidability via canonical counterexamples. The schemalevel analysis asks if there is some instance on which information about the query can be derived. As mentioned above, we show that whenever there is some instance, this can be taken to be the "simplest possible instance". While this idea has been used before to simplify analysis of undecidability (e.g. [START_REF] Gogacz | All-instances termination of chase is undecidable[END_REF]), we give a broad result that allows the use of it for decidability.

• Tractability via greatest fixed-point. We show that some of our instance-level implication problems can be reduced to evaluating a certain query of greatest fixedpoint Datalog (GFP-Datalog) on the given visible instance. Since GFP-Datalog queries can be evaluated in polynomial time, this shows tractability in the instance size. The reduction to GFP-Datalog requires a new analysis of when these inference problems are "active-domain controllable" (it suffices to see that the query value is invariant over all hidden databases that lie within the active domain of the visible instance).

• Relationships between problems. We prove reductions relating the positive and negative implication problems, the schema-and instance-level problems, and the widely-studied "certain answer problem". We use these reductions to derive tight complexity bounds.

•

Coding techniques for lower bounds. We introduce methods for coding computation in query implication problems, yielding both undecidability and complexity lower bounds.

Related work. Two different communities have studied the problem of determining the information that can be inferred from accessing data in a subset of the relations of a schema using constraints that relate the subset to the full vocabulary.

In the database community, the focus has been on views. The schema is divided into base tables and view tables, with the latter being defined by queries (typically conjunctive queries, abbreviated CQs) in terms of the former. Given a query over the schema, the basic computational problem is determining which answers can be inferred using only the values of the views. Abiteboul and Duschka [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF] isolate the complexity of this problem in the case where views are defined by CQs; in their terminology, it is querying under the Closed World Assumption, emphasizing the fact that the possible worlds revealed by the views are those where the view tables have exactly their visible content. In our terminology, this corresponds exactly to the Positive Query Implication (PQI) problem in the case where the constraints consist entirely of CQ view definitions. Another subcase of PQI that has received considerable attention is the case where the constraints consist only of completeness assertions between the invisible and visible portions of the schema (e.g. [START_REF] Fan | Relative information completeness[END_REF]).

The PQI problem is also related to works on instance-based determinacy (see in particular the results of Howe et al. in [START_REF] Koutris | Query-based data pricing[END_REF]), while the Negative Query Implication (NQI) problem is studied in the view context by Mendelzon and Zhang [START_REF] Zhang | Authorization views and conditional query containment[END_REF], under the name of conditional emptiness. In both cases, the emphasis has been on view definitions rather than more general constraints which may restrict both the visible and invisible instance. In contrast, our work deals with constraint classes that can restrict the visible and invisible data in ways incomparable to view definitions. However, our techniques do extend to solve the corresponding problems for view definitions; this extension is discussed in the full version.

The PQI problem also relates to works in description logics (e.g. [START_REF] Franconi | Query answering with DBoxes is hard[END_REF][START_REF] Lutz | Ontology-mediated queries with closed predicates[END_REF]) focusing on hybrid closed and open world query answering (DBoxes), where the schema is divided into closedworld and open-world relations. The problem in this setting is to find out if a Boolean CQ holds in all instances that can add facts to the open-world relations but do not change the closedworld relations. Thus, closed and open worlds match our notions of visible and invisible relations, and the hybrid closed and open world query answering problem matches our notion of Positive Query Implication, except that in our setting we restrict to the case where the open-world/invisible relations are empty. It is easy to see that this restriction is actually without loss of generality: one can reduce the general case to the case we study with a simple linear time reduction, making a closed-world copy R of each openworld relation R, and adding an inclusion dependency from R to R. The main distinction between our study of the PQI problem and the prior work in the description logic community concerns the classes of constraints considered. Lutz et al. [START_REF] Lutz | Ontology-based data access with closed predicates is inherently intractable(sometimes)[END_REF][START_REF] Lutz | Ontology-mediated queries with closed predicates[END_REF] study the complexity of this problem for the constraint languages EL and DL-LITE. [START_REF] Lutz | Ontology-mediated queries with closed predicates[END_REF] gives a criteria identifying constraints for which all queries are first-order rewritable, while [START_REF] Lutz | Ontology-based data access with closed predicates is inherently intractable(sometimes)[END_REF] carries out an analysis at the level of constraints and queries. Franconi et al. [START_REF] Franconi | Query answering with DBoxes is hard[END_REF] show co-NP-completeness for a disjunction-free description logic. Our results on the data complexity of PQI consider the same problem, but for decidable constraint languages that are more expressive and, in particular, can handle relations of arbitrary arity, rather than arity at most 2 as in [START_REF] Franconi | Query answering with DBoxes is hard[END_REF][START_REF] Lutz | Ontology-based data access with closed predicates is inherently intractable(sometimes)[END_REF][START_REF] Lutz | Ontology-mediated queries with closed predicates[END_REF].

In summary, the database and description logic communities considered the Positive Query Implication problems addressed here, but for different classes of constraints. The Negative Query Implication problems are not well-studied in the prior literature, and we do not know any work dealing with the schema-level questions (existence of an instance with a query implication). Despite this, we show (Subsection 4.2) that there is a close relation between the schema-level questions and the work of Lutz et al. [START_REF] Lutz | Conservative extensions in the lightweight description logic EL[END_REF] concerning conservativity and modularity of constraints.

For space reasons, some proofs and further applications of the techniques we develop are deferred to the full version; they can also be found in the technical report [START_REF] Benedikt | Query visible and invisible tables in the presence of constraints[END_REF].

Definitions

We consider schemas S = S h S v , where the partition elements S h and S v are finite sets of relation names (or simply, relations), each with an associated arity. These are the hidden and visible relations, respectively. An instance of a schema maps each relation to a set of tuples of the associated arity. The active domain of any instance I, denoted adom(I), is the set of values occurring within the interpretations of the relations of I. As a suggestive notation, we will use F for instances over S and V for instances over S v . Given an instance F for S, its restriction to the S v relations will be referred to as its visible part, denoted Visible(F ).

Instances will be used as inputs to the computational problems considered in this work -when used as inputs, the instances must be finite. We will also consider problems that quantify over instances -in this case the quantification can be either over finite instances or over all (finite or infinite) instances. We will deal with both possibilities, but when we do not specify otherwise, instances are assumed to be unrestricted.

We will consider formalisms based on first-order logic for expressing constraints and queries. Note that, in general, the evaluation of a first-order formula may depend on the underlying domain (not just on the instance and its active domain). We will always assume the formulas used in queries and constraints are domainindependent, which will allow us to evaluate queries and constraints over instances; this can be enforced, for example, by using relational algebra syntax.

We will mainly look at integrity constraints defined by tuplegenerating dependencies (TGDs), which are first-order sentences of the form ∀ x φ( x) → ∃ȳ ρ( x, ȳ), where φ and ρ are conjunctions of atoms containing variables and constants, and where all the universally quantified variables x appear in φ( x). We will often omit the universal quantifiers, writing just φ( x) → ∃ȳ ρ( x, ȳ). Moreover, for all the problems considered in this work, one can take w.l.o.g. the right-hand side ρ to consist of a single atom, and we will assume this henceforth. We will consider the following classes of TGDs:

• Linear TGDs: those where φ consists of a single atom.

• Inclusion dependencies (IDs): where each of φ and ρ is a single atom having no constants and no repeated variables. In Example 1, both the constraints were IDs.

• Frontier-guarded TGDs (FGTGDs) [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF]: these are TGDs where one of the conjuncts of φ is an atom that includes all the universally quantified variables occurring in ρ.

•

Connected TGDs: TGDs such that the co-occurrence graph of φ is connected. The nodes of this graph are the universally quantified variables x, and they are connected by an edge if they co-occur in an atom of φ. Note that every ID is a linear TGD, and every linear TGD is frontier-guarded. Many of our results apply to even richer constraints, which allow disjunction and (in the second case below) negation.

• Disjunctive FGTGDs: these are sentences of the form ∀ x φ( x) → ∃ȳ i ρ i ( x, ȳ), where, for each i, ρ i is a conjunction of atoms and there is an atom in φ that includes all the variables x j occurring in ρ i .

•

The Guarded negation fragment (GNFO): this is the fragment of first-order logic in which every negation is conjoined with an atom that contains all the free variables of the negated formula. Formally, GNFO sentences are built up according to the following grammar:

φ ::= R(t) | ∃x φ | φ ∨ φ | φ ∧ φ | R(t, ȳ) ∧ ¬φ(ȳ)
where R is either a relation symbol or the equality relation x = y, and the t i 's are either variables or constants. The reader only needs to know a few facts about GNFO. It is very expressive, so results about GNFO constraints immediately apply to many classes of constraints mentioned above. GNFO contains all positive existential formulas, is closed under Boolean combinations of sentences, and subsumes Disjunctive FGTGDs (up to equivalence), and hence also subsumes FGTGDs and IDs. Moreover, GNFO is "tame": Theorem 1 ( [START_REF] Bárány | Guarded negation[END_REF]). Satisfiability of GNFO sentences can be tested effectively, and is 2Exp-complete. Furthermore, every satisfiable sentence has a finite satisfying model.

Finally, we will also consider equality-generating dependencies (EGDs), of the form ∀ x φ( x) → x i = x j , where φ is a conjunction of atoms and x i , x j are variables or constants. EGDs generalize well-known relational database constraints, such as functional dependencies and key constraints.

To express queries we use conjunctive queries (CQs), i.e. firstorder formulas built up from relational atoms via conjunction and existential quantification (equivalently, relational algebra queries built via selection, projection, join, and rename operations), as well as disjunctions of CQs, abbreviated UCQs. Boolean UCQs (abbreviated BUCQs) are UCQs without free variables and Boolean CQs (BCQs) are CQs without free variables. Although for brevity we focus on Boolean queries in this work, the techniques extend to the non-Boolean case, as explained in [START_REF] Benedikt | Query visible and invisible tables in the presence of constraints[END_REF]. Every CQ Q is associated with a canonical database CanonDB(Q), whose domain consists of variables and constants of Q and whose facts are the atoms of Q.

We remark that in our constraint and query languages above, with the exception of IDs, constants are allowed by default. We will mention explicitly when we want to restrict to formulas without constants. We will further assume that we have associated with each value a corresponding constant, and we will identify constants with their values. Thus distinct constants will always be forced to denote distinct domain elements -this is often called the "unique name assumption" [START_REF] Abiteboul | Foundations of Databases[END_REF]. There are several problems that we study where the presence of such constants adds significant complications. In contrast, it is easy to show that the presence of constants without the unique name assumption will never make any difference in any of our results. None of our lower bounds rely on the presence of constants, except when explicitly stated otherwise.

We now define the crucial problems of Positive Query Implication (PQI) and Negative Query Implication (NQI): Definition 2. Let Q be a BUCQ over schema S, C a set of constraints over S, and V an instance over a visible schema S v ⊆ S.

• PQI(Q, C, S, V) = true if for every instance F satisfying C, if V = Visible(F ) then Q(F ) = true. • NQI(Q, C, S, V) = true if for every instance F satisfying C, if V = Visible(F ) then Q(F ) = false. We say that an S v -instance V is realizable w.r.t. C if there is an S-instance F satisfying C such that V = Visible(F ). If V is not realizable w.r.t. C, then, trivially, PQI(Q, C, S, V) = NQI(Q, C, S, V) = true.
In practice, realizable instances are the only S v -instances we should ever encounter. For simplicity we state our instance-level results for the PQI and NQI problems that take as input an arbitrary instance of S v . But since our lower bound arguments will only involve realizable instances, an alternative definition that assumes realizable inputs yields the same complexity bounds.

We also observe that the above problems quantify over all instances, finite and infinite in line with our default assumption. One can also consider versions of these problems where the quantification is over finite infinite instances. We will show that taking the quantification over finite instances will not impact our results. That is, we will show that the finite and unrestricted versions of PQI and NQI coincide for a large class of arguments Q, C, S, V. We express this by saying that PQI(Q, C, S, V) is finitely controllable, and similarly for NQI. Finite controllability will also allow us to make use of infinite instances freely in our proofs.

We will also be interested in studying the behavior of the above problems when Q, S, C are fixed, i.e. analysing how the computation time varies in the size of V only. We refer to this as the data complexity of the PQI and NQI problems.

The PQI problem contrasts with the usual Open-World Query Answering or Certain Answer problem, denoted here OWQ(Q, C, F ), which is studied extensively in databases and description logics. The latter problem takes as input a Boolean query Q, a finite instance F , and a set of constraints C, and returns true iff the query holds in any finite instance F containing all facts of F . The difference of this problem from PQI (and NQI) is that in PQI we further constrain the instance to be fixed on the visible part while requiring the invisible part of the input instance to be empty. This is the mix of "Closed World" and "Open World", and we will see that this Closed World restriction can make the complexity significantly higher.

Example 2. Consider a schema with inclusion dependencies V 1 (x) → ∃y H(x, y) and H(x, y) → V 2 (y), where V 1 , V 2 are visible and H is not. Let Q be the CQ ∃x H(x, x) and V the instance consisting only of facts V 1 (a), V 2 (a). Here we have a Positive Query Implication: the visible fact V 1 (a) and the first constraint imply the existence of a fact H(a, c), for some value c, but the second constraint and the content of V 2 imply c = a, whence ∃x H(x, x). In contrast, one can see that Q is not certain in the usual sense, where V 1 and V 2 can be freely extended with additional facts.

Our schema-level problems concern determining if there is a realizable instance that admits a query implication: Definition 3. For Q a BCQ over schema S, and C a set of constraints over S, we let:

• ∃PQI(Q, C, S) = true if there exists a realizable S v -instance V such that PQI(Q, C, S, V) = true; • ∃NQI(Q, C, S) = true if there exists a realizable S v -instance V such that NQI(Q, C, S, V) = true.
In Example 1, ∃PQI(Q, C, S) = false, because the user could never infer that the query was true. But ∃NQI(Q, C, S) = true, due to the empty instance. Note that the schema-level problems quantify over instances twice. As before, we say the schema-level problems are finitely controllable if both quantifications over instances can be simultaneously replaced with quantifications over finite instances.

Positive Query Implication

Instance-level problem

We begin by showing that the instance-level problem PQI is decidable for constraints in the rich logic GNFO. The key observation is that PQI can be expressed as a GNFO unsatisfiability problem.

Theorem 4. PQI(Q, C, S, V) is in 2Exp, as Q ranges over BUCQs and C over GNFO constraints. Furthermore, for such constraints the problem is finitely controllable.

Proof. PQI(Q, C, S, V) = true translates to unsatisfiability of ¬Q ∧ C ∧ R∈Sv R(ā) ∈ V R(ā) ∧ ∀ x R( x) → R(ā) ∈ V x = ā .
If the constraints are in GNFO, then the formula above is also in GNFO. Finite controllability and the 2Exp bound on GNFO satifiability (Theorem 1) imply the conclusion.

Above we are using decidability of satisfiability of GNFO as a black-box. The decision procedure for GNFO works by translating a formula into a tree automaton, which is then tested for nonemptiness. In the full version, we do a finer analysis of the translation, using a method developed in [START_REF] Benedikt | The complexity of boundedness for guarded logics[END_REF]. The analysis shows that for each fixed formula and schema, we can generate a two-way alternating tree automaton of size polynomial in the instance. From this and standard results in automata theory, it follows that the data complexity of PQI is only singly-exponential.

Theorem 5. Given a BUCQ Q and set C of GNFO constraints over schema S, the data complexity of PQI(Q, C, S, V), as V varies over instances, is in Exp.

The above data complexity bound is tight even for inclusion dependencies:

Theorem 6. There is a BCQ Q and a set C of IDs over a schema S for which the problem PQI(Q, C, S, V) is Exp-hard in data complexity.

Note that this contrasts sharply with the case of OWQ for GNFO constraints which has data complexity in co-NP [START_REF] Bárány | Queries with guarded negation[END_REF]. The proof (given in the full version, as most of our lower bounds are) proceeds by showing that a universal machine for alternating PSpace can be constructed by fixing appropriate Q, C, S in a PQI problem. The input of the machine is represented in the visible instance V, and an encoding of the computation is induced in some hidden relations by the constraints. Encodings of rejecting computations and badly-formed encodings are also allowed, but these particular cases can be detected by the query. In particular, we have that PQI(Q, C, S, V) = false iff there exists an encoding of a successful computation of the alternating PSpace Turing machine. We also remark that the proof requires a schema with arity above 2. In fact, if we move up from IDs to linear TGDs, we can show Exp-hardness even for arity 2.

We conclude the analysis of the instance-level PQI problem by establishing that the 2Exp combined complexity upper bound is tight even for IDs. Theorem 7. PQI(Q, C, S, V) is 2Exp-hard for combined complexity, as Q ranges over BCQs and C over sets of IDs.

The proof of this lower bound is similar to that of Theorem 6; we reduce the acceptance problem for an alternating ExpSpace Turing machine M to the negation of PQI(Q, C, S, V). The technical difficulty here is to encode a tape of exponential size, which cannot be done succinctly using a visible instance. We overcome this problem by representing the positions of the tape as leaves of a full binary tree of linear height (of course this makes the schema and the constraints depend on the input of the machine).

Schema-level problem

We now turn to the schema-level problem ∃PQI. Let V {a} be the instance for the visible part of a schema S whose active domain contains the single value a and whose visible relations are singleton relations of the form {(a, . . . , a)}. We will show that, for certain constraint languages, whenever ∃PQI(Q, C, S) = true, then the witnessing instance can be taken to be V {a} . This can be viewed as an extension of the "critical instance" method which has been applied previously in undecidability results. E.g., Gogacz and Marcincowski [START_REF] Gogacz | All-instances termination of chase is undecidable[END_REF] refer to this instance as a "well of positivity". The following result shows that for ∃PQI, this technique works with TGDs and EGDs without constants. Theorem 8. For every BUCQ Q without constants and every set C of TGDs and EGDs without constants,

∃PQI(Q, C, S) = true iff PQI(Q, C, S, V {a} ) = true. In particular, ∃PQI(Q, C, S) = true iff there is a finite realizable instance V such that PQI(Q, C, S, V) = true.
We will prove the theorem first for constraints consisting only of TGDs without constants; then we will show how to generalize it in the presence of EGDs without constants.

First of all, we note that, by introducing additional invisible relations, we can assume w.l.o.g. that all TGDs have exactly one atom in the right-hand side. Next, we introduce a variant of the "classical" chase procedure [START_REF] Abiteboul | Foundations of Databases[END_REF] that returns a collection of instances (not necessarily finite); the extension is along the lines of the "Disjunctive Chase" of [START_REF] Deutsch | The chase revisited[END_REF]. As in the classical chase, the procedure receives as input a relational schema S, some constraints C, and an initial instance F 0 for the schema S, which does not need to satisfy the constraints in C. The procedure chases the constraints starting from the instance F 0 , guaranteeing at the same time that the visible relations of the constructed instances agree with F 0 . This variant of the chase will be used to prove Theorem 8, as well as other results related to the ∃NQI problem.

Formally, the procedure builds a tree-shaped collection of instances starting from the singleton consisting of the input S-instance F 0 . It extends the collection by repeatedly applying the following process. It chooses an instance K at some leaf of the current tree, a TGD R 1 ( x1 ) ∧ . . . ∧ R m ( xm ) → ∃ȳ S (z) in C, where z is a sequence of (possibly repeated) variables chosen among x1 , . . . , xm , ȳ, and a homomorphism f that maps R 1 ( x1 ), . . . , R m ( xm ) to some facts in K. The procedure constructs a new instance from K by adding the fact S ( f (z)), where f is an extension of f that injectively maps the existentially quantified variables in ȳ to some fresh null values. When the relation S is visible, the procedure replaces the instance K = K ∪ S ( f (z)) with copies of itself of the form g(K ) such that Visible(g(K )) = Visible(F 0 ), for all possible homomorphisms g from the variables z to values in the active domain of Visible(F 0 ); in particular, if the active domain is {a 1 , . . . , a n }, the latter step can be seen as chasing a disjunctive EGD of the form

S (z) → z(i) = a 1 ∨ . . . ∨ z(i) = a n .
The resulting instances g(K ) are then appended as new children of K. In the special case where there are no homomorphisms g such that Visible(g(K )) = Visible(F 0 ), we append a dummy instance ⊥ as a child of K: this denotes the fact that the chase step from K led to an inconsistency (the dummy node will never be extended during the subsequent chase steps). If S is not visible, then the instance K is simply appended as a new child of K.

In the limit, the process generates a possibly infinite tree-shaped collection of instances, a chase tree. We assume that the chase strategy is "fair": whenever a dependency was applicable in a node on a maximal path of the chase tree, then it was fired at some descendant of that node along the same maximal path (unless the path ends with ⊥). It now remains to complete the collection with "limits" in order to guarantee that all constraints are satisfied. Consider any infinite path π = K 0 , K 1 , . . . in the chase tree. By construction, the instances along π form a chain of homomorphic embeddings K 0

h 0 ---→ K 1 h 1
---→ . . .. Such chains of homomorphic embeddings admit a natural notion of limit, which we denote by lim n∈N K n . We refer to [START_REF] Chang | Model Theory[END_REF] for further details about the construction of this limit. Here we only remark that lim n∈N K n satisfies the constraints C. We denote by Chases vis (C, S, F 0 ) the collection of all non-dummy instances that occur as leaves of the chase tree and all the limits of the infinite paths in it. This is well-defined only once the ordering of steps is chosen, but for the results below which order is chosen will not matter, so we abuse notation by referring to Chases vis (C, S, F 0 ) as a single object.

It is clear that every instance in Chases vis (C, S, F 0 ) satisfies the constraints in C and agrees with F 0 on the visible part of the schema. One can also show that Chases vis (C, S, F 0 ) satisfies the following universal property: Lemma 9. Let F 0 , F be two instances of the same schema S such that F 0 ⊆ F , Visible(F 0 ) = Visible(F ), and F satisfies a set C of TGDs without constants. There exist an instance K ∈ Chases vis (C, S, F 0 ) and a homomorphism from K to F .

An interesting use of the chase procedure is to characterize the instance-level PQI problem: Proposition 10. Let Q be a BUCQ without constants, C a set of TGDs without constants, V a visible instance. PQI(Q, C, S, V) = true iff Q holds on all instances of Chases vis (C, S, V).

Proof. Suppose that PQI(Q, C, S, V) = true and recall that every instance in Chases vis (C, S, V) satisfies the constraints in C and agrees with V on the visible part. This means that Q holds on every instance of Chases vis (C, S, V).

Conversely, if PQI(Q, C, S, V) = false, there is an S-instance F that has V as visible part, satisfies the constraints in C, but not the query Q. By Lemma 9, letting F 0 = V, we get an instance K ∈ Chases vis (C, S, V) and a homomorphism from K to F . Since Q is preserved under homomorphisms, K does not satisfy Q.

Next, we recall that the visible instance V {a} is constructed over a singleton active domain and that the constraints C have no constants. This implies that there are no disjunctive choices to perform while chasing the constraints starting from V {a} . Moreover, it is easy to see that this chase always succeeds, that is, returns a collection Chases vis (C, S, V {a} ) with exactly one instance -this also shows that V {a} is a realizable instance. By a slight abuse of notation, we denote by chase vis (C, S, V {a} ) the unique instance in the collection Chases vis (C, S, V {a} ).

The last ingredient is given by the following lemma:

Lemma 11. If C is a set of TGDs without constants over a schema S and V is an instance of the visible part of S, then ev-ery instance K ∈ Chases vis (C, S, V) maps homomorphically to chase vis (S, C, V {a} ).

Now that we established the key lemmas, we can reduce the schema-level problem to an instance-level problem:

Proof of Theorem 8. Recall that for the moment we assume that the constraints consist only of TGDs. Clearly, PQI(Q, C, S, V {a} ) = true implies ∃PQI(Q, C, S) = true. For the converse, suppose that ∃PQI(Q, C, S) = true. This implies the existence of a realizable instance V such that PQI(Q, C, S, V) = true. By Proposition 10, every instance in Chases vis (S, C, V) satisfies the query Q. Moreover, by Lemma 11, every instance in Chases vis (S, C, V) maps homomorphically to chase vis (S, C, V {a} ). Hence chase vis (S, C, V {a} ) also satisfies Q. By applying Proposition 10 again, we conclude that PQI(Q, C, S, V {a} ) = true. Now, we explain how to generalize the above proof to deal with both TGDs and EGDs (still without constants). For this we modify the procedure for Chases vis (S, C, V) to take into account the additional EGDs that can be triggered on instances of the chase tree. Formally, chasing an EGD of the form R 1 ( x1 ) ∧ . . . ∧ R m ( xm ) → x = x amounts to applying a suitable homomorphism that identifies the two values h(x) and h(x ) whenever the facts R 1 (h( x1 )), . . . , R m (h( xm )) belong to the instance under consideration. Note that this operation leads to a failure (i.e. a dummy instance) when h(x) and h(x ) are distinct values from the active domain of the visible part V. With the new definition of Chases vis (S, C, V) at hand, the proofs of Lemmas 9 and 11 do not pose particular problems, as we just need to handle the standard case of an EGD, and Proposition 10 and Theorem 8 carry over without modifications.

By pairing Theorem 8 with Theorem 4 we obtain:

Corollary 12. ∃PQI(Q, C, S) is in 2Exp and finitely controllable, where Q ranges over BUCQs without constants and C over sets of FGTGDs without constants.

The uniqueness of the instance chase vis (C, S, V {a} ) played a key role in the argument above. We show that adding disjunction to the constraints, thus causing this uniqueness to fail, leads to undecidability. Intuitively, this shows that the interaction of disjunctive linear TGDs and linear EGDs (implicit in the visibility assumption) breaks the critical instance approach.

Theorem 13. The problem ∃PQI(Q, C, S) is undecidable as Q ranges over BUCQs and C over sets of disjunctive linear TGDs.

The proof uses a technique that will be exploited for many of our undecidability arguments. We will reduce the existence of a tiling to ∃PQI. The tiling itself will correspond to the visible instance that has a PQI. The invisible relations will store "challenges" to the correctness of the tiling. There will be challenges to the labelling of adjacent cells, to the initial tile, and to the shape of the adjacency relationship -that is, challenges that the tiling is really grid-like. A correct tiling corresponds to every challenge being passed, and the UCQ Q will have disjuncts that hold exactly when the challenges are passed. Thus, a correct tiling corresponds to a visible instance where every extension satisfies Q. The undecidability argument also applies to the variant of ∃PQI that quantifies over finite instances.

Perhaps even more surprisingly, we show that disjunction can be simulated using constants (under UNA), and thus even the addition of constants causes the critical instance technique to break. The proof adapts the technique of "coding Boolean operations and truth values in the schema", which has been used to eliminate the need for disjunction in several past works (e.g. [START_REF] Gottlob | On the complexity of single-rule datalog queries[END_REF]). Proposition 14. There is a polynomial-time reduction from ∃PQI(Q, C, S), as Q ranges over BUCQs and C over sets of disjunctive linear TGDs, to ∃PQI(Q , C , S ), as Q ranges over BUCQs and C over sets of linear TGDs (with constants).

From the previous two results we immediately see that the addition of (distinct) constants leads to undecidability: Corollary 15. ∃PQI(Q, C, S) is undecidable as Q ranges over BUCQs and C over sets of linear TGDs (with constants).

We now turn to analysing how the complexity scales with less powerful constraints, e.g. linear TGDs without constants. We use the reduction of the schema-level problem ∃PQI(Q, C, S) to the instance-level problem PQI(Q, C, S, V {a} ) given in Proposition 8, and use some ideas from Johnson and Klug's [START_REF] Johnson | Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies[END_REF] to show that for linear TGDs the latter problem is in polynomial space: Theorem 16. PQI(Q, C, S, V {a} ) is in PSpace, as Q ranges over BUCQs without constants and C over sets of linear TGDs without constants. Thus by Proposition 8 the same holds for ∃PQI(Q, C, S).

Proof. By Proposition 10, PQI(Q, C, S, V {a} ) = true is equivalent to asking the existence of a CQ Q i in Q and a homomorphism h from CanonDB(Q i ) to chase vis (C, S, V {a} ). We can easily guess the CQ Q i , the homomorphism h, and its image I = h(CanonDB(Q i )). Thus, it remains to show that I ⊆ chase vis (C, S, V {a} ) can be tested in PSpace.

Recall that chase vis (C, S, V {a} ) is obtained as the limit of a series of operations that consist of alternatively adding new facts, according to the TGDs in C, and identifying with the constant a those values that appear in some visible relation. Note that the second type of operation may also affect tuples that belong to hidden relations and that were inferred during previous steps of the chase. We show that, at the exact moment when a new fact R(b 1 , . . . , b k ) is inferred by chasing a linear TGD, one can also detect whether a value b i will be eventually identified with the constant a -in this case we can safely replace the fact R(b 1 , . . . , b k ) with R(b 1 , . . . , b i-1 , a, b i+1 , . . . , b k ). To detect this we test whether C entails a dependency of the form R( x) → ∃ȳ S (z), where x is a sequence of (possibly repeated) variables that has the same equality type as b (i.e. x( j) = x( j ) iff b( j) = b( j )), S is a visible relation, z is a sequence of variables among x, ȳ, and x(i) = z( j) for some 1 ≤ j ≤ |z|. The above entailment can be seen as a containment between two CQs under a given set of linear TGDs C, and we know from [START_REF] Johnson | Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies[END_REF] that the latter problem is in PSpace. We have just described an alternative construction of chase vis (C, S, V {a} ) that avoids substitutions of values with constants, and in which every step can be performed using a PSpace sub-procedure.

Below, we explain how to adapt the techniques from [START_REF] Johnson | Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies[END_REF] to this alternative variant of the chase in order to decide whether an instance I is contained in chase vis (C, S, V {a} ). For this, it is convenient to think of chase vis (C, S, V {a} ) as a directed graph, whose nodes denote the facts in chase vis (C, S, V {a} ) and the edges denote the inference steps deriving new facts from existing ones -because the constraints are linear TGDs, each inference step depends on at most one fact. By the previous arguments, one can check in PSpace whether an edge exists between two given nodes. We focus on the minimal set of edges that connects all the facts of I to the facts of V {a} (the roots of the graph). The graph restricted to this set of edges is a forest. Its height is at most exponential in |I|, and each level in it contains at most |I| nodes. Thus, the restricted graph can be explored by a non-deterministic polynomial-space algorithm that guesses the nodes at a level on the basis of the nodes at the previous level and the linear TGDs in C. The algorithm succeeds once it has visited all the facts in I, witnessing I ⊆ chase vis (C, S, V {a} ). Otherwise, the computation is rejected after seeing exponentially many levels.

Recall that Open-World Query Answering (OWQ) is the "classical" variant of the query implication problem: all relations can be freely extended, and all relations are allowed to be non-empty. It is easy to show that OWQ reduces to PQI; i.e. PQI is at least as hard as OWQ (and as our results have shown, it is sometimes harder). We can also reduce OWQ to ∃PQI, which will allow us to show that the upper bound for linear TGD in Theorem 16 is tight.

Proposition 17. For any class of constraints containing linear TGDs, OWQ reduces to ∃PQI.

Proof. Let Q be a query, C a set of constraints over a schema S, and F an instance of the schema S. We show how to reduce the Open-World Query Answering problem for Q, C, S, and F to a problem ∃PQI(Q , C , S ). The idea is to create a copy of the instance F in the hidden part of the schema, which can be then extended arbitrarily.

Formally, we let the transformed schema S consist of all the relations in S, which are assumed to be hidden, plus an additional visible relation Good of arity 0. We then introduce a variable y b for each value in the active domain of F , and we let C contain all the constraints from C, plus a constraint of the form Good → ∃ȳ Q F , where ȳ contains one variable y b for each value b in the active domain of F and Q F is the conjunction of the atoms of the form A(y b 1 , . . . , y b k ), for all facts A(b 1 , . . . , b k ) in F . The visible instance V that contains the atom Good is realizable, since it can be completed (using the chase) to an S -instance F that satisfies the constraints C . Moreover, every S -instance F that contains the atom Good and satisfies the constraints C , contains an isomorphic copy of F . Thus, if we finally let Q = Q ∧ Good, we have that ∃PQI(Q , C , S ) = true iff every S-instance F that contains the fact Good and satisfies the constraints C , also satisfies the query Q. This reduces the Open-World Query Answering problem for Q, C, and S to the problem ∃PQI(Q , C , S ).

We recall that [START_REF] Casanova | Inclusion dependencies and their interaction with functional dependencies[END_REF] showed that the implication problem for IDs (does one ID follow from a set of IDs) is PSpace-hard. There is also a simple reduction from the latter implication problem to OWQ: given the problem of deciding whether a set of IDs Σ implies an ID λ → ρ, one can produce the OWQ problem with constraints Σ, instance given by the canonical database of λ, and query formed from ρ by changing the free variables to constants. Thus OWQ is PSpace-hard for IDs as well, and the PSpace-hardness of ∃PQI follows using the result above. Thus, applying the reduction of Proposition 17, we see that the prior upper bound from Theorem 16 is tight: Corollary 18. ∃PQI(Q, C, S) is PSpace-hard, as Q ranges over BCQs and C over sets of linear TGDs.

Similarly applying existing lower bounds on OWQ for FGTGDs [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF] we see that the prior upper bound from Corollary 12 is tight:

Corollary 19. ∃PQI(Q, C, S) is 2Exp-hard,

Negative Query Implication 4.1 Instance-level problem

We now consider the problem NQI(Q, C, S, V). As in the positive case, for GNFO constraints we get decidability via reduction to satisfiability.

Theorem 20. NQI(Q, C, S, V), as Q ranges over BUCQs and C over GNFO constraints, is 2Exp in combined complexity, Exp in data complexity, and finitely controllable.

Proof. As in the positive case, we reduce NQI(Q, C, S, V) to unsatisfiability of the GNFO formula

Q ∧ C ∧ R∈Sv R(ā) ∈ V R(ā) ∧ ∀ x R( x) → R(ā) ∈ V x = ā .
The data complexity analysis is as in Theorem 5, since the formulas agree on the part that varies with the instance.

The fact that the above bounds are tight follows from the lower bounds for combined and data complexity of PQI given in Theorems 6 and 7, since PQI reduces to NQI for rich enough constraints: Theorem 21. For any class of constraints that includes connected FGTGDs, PQI(Q, C, S, V) reduces in polynomial time to NQI(Q , C , S , V ). Further, Q , C , S depend only on Q, C, S, and thus the reduction preserves data complexity.

Proof. We first provide a reduction that works with any class of constraints allowing arbitrary conjunctions in the left-hand sides (e.g. frontier-guarded TGDs). Subsequently, we show how to modify the constructions in order to preserve connectedness.

The schema S is obtained by copying both the visible and the hidden relations from S and by adding the following relations: a visible relation Error of arity 0 and a hidden relation Good of arity 0. The constraints C will contain the same constraints from C, plus one frontier-guarded TGD of the form

Q i (ȳ) ∧ Good → Error
for each CQ of Q of the form ∃ȳ Q i (ȳ). Finally, the query and the visible instance are defined as follows: Q = Good and V = V.

We now verify that PQI(Q, C, S, V) = false iff NQI(Q , C , S , V ) = false. Suppose that PQI(Q, C, S, V) = false, namely, that there is an S-instance F such that F Q, F C, and Visible(F ) = V. Let F be the S -instance obtained from F by adding the single hidden fact Good. Clearly, F satisfies the query Q and also the constraints in C ; in particular, it satisfies every constraint

Q i (ȳ) ∧ Good → Error because F violates every disjunct ∃ȳ Q i of Q. Hence, we have NQI(Q , C , S , V ) = false.
Conversely, suppose that NQI(Q , C , S , V ) = false, namely, that there is an S -instance F such that F Q , F C , and Visible(F ) = V . By copying the content of F for those relations belong to the schema S, we obtain an S-instance F that satisfies the constraints C. Moreover, because F contains the fact Good but not the fact Error, F violates every conjunct ∃ȳ Q i (ȳ) of Q, and so F does. This shows that PQI(Q, C, S, V) = false.

We observe that the constraints in the above reduction use lefthand sides that are not connected. In order to preserve connectedness, it is sufficient to modify the above constructions by adding a dummy variable that is shared by all atoms. More precisely, we expand the relations of the schema S and the relation Good with a new position, and we introduce a new visible relation Check of arity 1. The dummy variable will be used to enforce connectedness in the left-hand sides, and the relation Check will gather all the values associated with the "dummy" position. Using the visible instance, we can guarantee that the relation Check contains exactly one value. The constraints are thus modified as follows. Every con-

straint R 1 ( x1 ) ∧ . . . ∧ R m ( xm ) → ∃ȳ S (z) in C is transformed into R 1 ( x1 , w)∧. . .∧R m ( xm , w) → ∃ȳ S (z, w). In particular, the constraint Q i (ȳ) ∧ Good → Error becomes Q i (ȳ, w) ∧ Good(w) → Error(w),
which is now a connected frontier-guarded TGD. Furthermore, for every relation R( x) in S, we add the constraint R( x, w) → Check(w) and we do the same for the relation Good:

Good(w) → Check(w) .
Finally, the query is transformed into Q = ∃w Good(w) and the visible instance V is expanded with a fresh dummy value a on the additional position and with the visible fact Check(a).

From the above reduction and from Theorems 6 and 7, we get the following hardness results for instance-based NSB.

Corollary 22. There are a BUCQ Q and a set C of connected FGTGDs over a schema S for which the problem NQI(Q, C, S, V) is Exp-hard in data complexity (that is, as V varies over instances).

Corollary 23. The problem NQI(Q, C, S, V), as C ranges over sets of connected FGTGDs, S over schemas, Q over BCQs and V over instances, is 2Exp-hard.

Thus far, the complexity of NQI has been similar to that of PQI. We will now show a strong contrast in the case of linear TGDs. Recall from Theorem 6 that PQI was highly intractable even for fixed schema with linear TGDs and fixed query. We begin by showing that NQI(Q, C, S, V) can be solved easily by looking only at full instances that agree with V on the visible part and whose active domains are the same as that of V:

Definition 24. NQI(Q, C, S, V) is active domain controllable if it is equivalent to asking that for all instances F over the active domain adom(V) of V, if F satisfies C and Visible(F ) = V, then Q(F ) = false.
It is clear that the the problem NQI(Q, C, S, V) is simpler when it is active domain controllable, as in this case we could guess a full instance F over the active domain of V and reduce the problem to checking whether Q holds on F .

We give a simple argument that NQI under IDs is active domain controllable. Let C be a set of IDs, Q a BUCQ, and V a visible instance such that NQI(Q, C, S, V) = false. This means that there is a full instance F such that F C, Visible(F ) = V, and F Q. Take any value a ∈ adom(V) and let h be the homomorphism that is the identity over adom(V) and maps any other value from adom(F )\adom(V) to a. Since, C consists of IDs (in particular, since the left-hand side atoms do not have constants or repeated occurrences of the same variable), we know that h(F ) C. Similarly, we have h(F ) Q. Hence, h(F ) is an instance over the active domain of V that equally witnesses NQI(Q, C, S, V) = false.

The following example shows that linear TGDs are not always active domain controllable.

Example 3. Let S be the schema with a hidden relation H of arity 2 and two visible relations V 1 , V 2 of arities 1, 0, respectively. Consider the linear TGDs

H(x, y) → V 1 (x) H(x, x) → V 2
the CQ Q = ∃x y H(x, y), and the visible instance V that consists of the single fact V 1 (a). Clearly, every full instance F over the active domain {a} of V that satisfies the above constraints and CQ Q must also contain the facts H(a, a) and V 2 , and so it cannot agree with V on the visible part. On the other hand, the full instance that contains the facts V 1 (a) and H(a, b), for a fresh value b, satisfies the constraints and the CQ Q, and furthermore agrees with V. This shows that NQI(Q, C, S, V) is not active domain controllable.

Despite the above example, we show that we can still transform any schema with linear TGDs (which may include constants) and any query for an NQI problem so as to enforce active domain controllability. Moreover, we can do so while preserving the visible instance of the problem: Theorem 25. Given a schema S, a set C of linear TGDs (possibly including constants), and a BUCQ Q, one can construct in exponential time a new schema S , a set C of linear TGDs (with constants), and a BUCQ Q such that S v = S v and, for all instances V over S v :

1. NQI(Q, C, S, V) = NQI(Q , C , S , V), 2. NQI(Q , C , S , V) is active domain controllable.
The idea for proving the above result is to project away from the tuples of the hidden relations of S those positions that store values outside the active domain of V. In doing so, one needs to recall the equality relationships between pairs of removed positions and between those positions and the constants used in the constraints -this is important because different linear TGDs may be triggered on the basis of these equalities. For example, consider a hidden ternary relation R = (a, a, c), (a,c,d),(b,c,c),(c,d,e),(c,d,c) for the original schema S, where a, b are the only values of the visible active domain. In the modified schema, the relation R is represented by copies of it of the form R I,ϕ , one for each set I of removed positions and for each equality type ϕ. Precisely, the copies of R in the modified instance will be: R ∅, = ∅, R {z}, = (a, a) , R {y,z}, = (a), (b) , R {y,z},y=z = (b) , R {x,y,z}, = () , R {x,y,z},x=z = () , R {x,y,z},x=y = R ∅,y=z = R ∅,x=y=z = ∅. With the new schema S defined, we introduce copies of the original constrains on the basis of the intended semantics of the relations R I,ϕ . The goal is to simulate the behaviour of the original tuples using only their projection on the visible active domain and the information about the equalities between the removed positions and the constants. For example, if R(x, y, z) → ∃w S (w, w) is a linear TGD in C, then we add to C linear TGDs of the form R ∅, (x, y, z) → ∃w S ∅, (w, w) R ∅, (x, y, z) → ∃w S {w,w }, () R ∅, (x, y, z) → ∃w S {w,w },w=w () . . . Finally, we process the UCQ Q in a similar way. A fully detailed construction of S , C , and Q , with the proof that they satisfy the desired properties, is given in the full version. Now we show how to exploit active domain controllability to prove that NQI can be solved not only efficiently, but "definably", using well-behaved query languages. For this, we introduce a variant of Datalog programs, called GFP-Datalog programs, whose semantics is given by greatest fixpoints. GFP-Datalog programs are defined syntactically in the same way as Datalog programs [START_REF] Abiteboul | Foundations of Databases[END_REF] i.e. as finite sets of rules of the form R( x) ← Q( x) where the xi are implicitly universally quantified and Q is a CQ whose free variables are exactly x. As for Datalog programs, we distinguish between extensional (i.e. input) predicates and intensional (i.e. output) predicates. In the above rules we restrict the left-hand sides to contain only intensional predicates. Given a GFP-Datalog program P, the immediate consequence operator for P is the function that, given an instance F consisting of both extensional and intensional relations, returns the instance F where the extensional relations are as in F and the tuples of each intensional relation R are those satisfying Q(R), where Q is any query appearing on the right of a rule with R. The immediate consequence operator is monotone, and the semantics of the GFP-Datalog program on an extensional database instance F is defined as the greatest fixpoint of this operator starting at the database instance F 0 that extends F by setting each intensional relation "maximally" -that is, to the tuples of values from the active domain of F plus the constants appearing in the GFP-Datalog program. A program may also include a distinguished intensional predicate, the goal predicate G -in this case the result is taken to be the projection onto G of the greatest fixpoint.

Theorem 26. If Q is a BUCQ, C a set of linear TGDs (with constants), and NQI(Q, C, S, V) is active domain controllable, then ¬NQI(Q, C, S, V), viewed as a query over the visible part V, is definable by a GFP-Datalog program that can be constructed in polynomial time from Q, C, and S.

Proof. We need to describe by means of a GFP-Datalog program the function ¬NQI(Q, C, S, V) that maps an instance V to true or false depending on whether or not Q holds over some instance F that satisfies the constraints C and such that Visible(F ) = V. Thanks to active domain controllability, it suffices to consider full instances constructed over the active domain of V, and define a witness F as a greatest fixpoint.

The extensional relations are those in the visible part V. The intensional relations are those in the hidden part of the schema S, plus an extra intensional relation A that derives the values in the active domain of V. For each extensional relation R and each position 1 ≤ i ≤ arity(R), we have the rule A(x i ) ← R( x), which collects the values from the active domain into A. In addition, for each intensional relation R, we have the rule

R( x) ← i A(x i ) ∧ R( x) → ∃ȳ S (z) linear TGD in C S (z) .
Let F be the instance consisting of the visible part V and the intensional relations R computed by the above Datalog program under the greatest fixpoint semantics. It is easy to see that F satisfies the constraints, that is: if R( x) → ∃ȳ S (z) is a linear TGD in C and F contains a fact of the form R(h( x)), for some homomorphism h, then F contains also a fact S (h ( x)), for some homomorphism h that extends h. Finally, to compute ¬NQI(Q, C, S, V), we add to the above program the goal predicate G and a rule G ← S 1 (z 1 ) ∧ . . . ∧ S n (z n ) for each CQ ∃ ȳ S 1 (z 1 ) ∧ . . . ∧ S n (z n ) of Q.

We remark that the naïve fixpoint algorithm for a GFP-Datalog program takes exponential time in the maximum arity of the intensional relations, but only polynomial time in the size of the extensional relations and the number of rules. Note also that the transformation of Theorem 25 does not change the visible relations, which determine the maximum arity of the intensional relations of the GFP-Datalog program. Thus the constructions of Theorems 25 and 26 give us:

Corollary 27. When C ranges over sets of linear TGDs and Q over BUCQs NQI(Q, C, S, V) has data complexity in P and combined complexity in Exp. Note that this result is in contrast to the situation with the OWQ problem for linear TGDs, where the instances for which an implication holds are definable in ordinary Datalog [START_REF] Baget | Walking the complexity lines for generalized guarded existential rules[END_REF]. We do not know whether the use of GFP-Datalog can be replaced by other logics, e.g. Datalog. However we can prove that to define ¬NQI(Q, C, S, V) from a given visible instance V, it is necessary to go beyond first-order logic: Proposition 28. NQI(Q, C, S, V) cannot be described by a firstorder query over V. More generally, there are BCQs Q and sets of IDs C such that NQI(Q, C, S, V) is P-hard in data complexity.

As for the combined complexity of NQI with linear TGDs, we can prove a tight Exp lower bound: Theorem 29. NQI(Q, C, S, V) is Exp-hard for combined complexity, as C ranges over IDs and Q over BUCQs.

The proof is based on a reduction from the acceptance problem for an alternating PSpace Turing machine to NQI(Q, C, S, V). Compared to the proof of Theorem 6, the techniques are similar. The only difference is that now, thanks to the dependency of the constraints from the machine and its input, we can directly avoid badly-formed encodings of computations. So, the query will only detect rejecting computations and, dually, it will be violated on the encodings of successful computations. In particular, we have that NQI(Q, C, S, V) = true iff all instances satisfying C encode a successful computation of the alternating PSpace Turing machine.

Schema-level problem

Here we consider the schema-level question, i.e. ∃NQI. We first show that when the constraints are preserved under disjoint unions (this holds, e.g., for connected FGTGDs), the existence of an NQI can be checked by considering a single "negative critical instance", namely the empty visible instance. For TGD constraints, this instance is easily seen to be realizable: the chase procedure that we introduced in Section 3.2 terminates immediately when initialized with the empty instance F 0 = ∅ and returns the singleton collection Chases vis (C, S, ∅) consisting of the empty S-instance satisfying C. Proof. Clearly, NQI(Q, C, S, ∅) = true implies ∃NQI(Q, C, S) = true. As for the converse, suppose that NQI(Q, C, S, ∅) = false and let F be an S-instance satisfying C and Q and such that Visible(F ) = ∅. We aim at proving that NQI(Q, C, S, V) = false for all realizable visible instances V. Let V be a realizable instance and F an S-instance that satisfies C and such that Visible(F ) = V. We define the new instance F as a disjoint union of F and F . Since the constraints C are preserved under disjoint unions, F satisfies C. Moreover, by monotonicity, F satisfies the UCQ Q. Since V = Visible(F ) = Visible(F ), we have NQI(Q, C, S, V) = false, whence ∃NQI(Q, C, S) = false.

By the above result and Theorem 20, we get that ∃NQI(Q, C, S) is decidable in 2Exp for GNFO constraints that are closed under disjoint unions, and in particular the problem is decidable for connected FGTGDs. Combining with Corollary 27 we also get an Exp bound for linear TGDs. In fact, we can improve the latter bound by observing that NQI over the empty visible instance reduces to Open-World Query Answering: Proposition 31. For any BCQ Q, constraints C, and schema S,

NQI(Q, C, S, ∅) = true iff OWQ(Q , C, CanonDB(Q)) = true, where Q = R ∈ Sv ∃ x R( x) and CanonDB(Q) is the canonical database of the CQ Q (defined in Section 2).
We know from previous results [START_REF] Bárány | Querying the guarded fragment[END_REF] that OWQ for CQs and linear TGDs is in PSpace. Thus the above reduction implies that NQI(Q, C, S, ∅) (and hence ∃NQI(Q, C, S), by Theorem 30) is in PSpace when C is a set of linear TGDs: Corollary 32. ∃NQI(Q, C, S) is in PSpace, as Q ranges over BUCQs and C over sets of linear TGDs.

There are matching lower bounds for ∃NQI. Recall that Theorem 30 and Theorem 20 implied a 2Exp bound for connected FGTGDs. To show a matching lower bound the key tool is the following reduction.

Proposition 33. There is a polynomial time reduction from OWQ over a set of connected FGTGDs without constants and a connected BCQ to an ∃NQI problem over a set of connected FGTGDs without constants and a BCQ.

The existence of such a reduction is surprising, since OWQ deals with deriving positive information while ∃NQI concerns negative information.

Towards proving this reduction, we first state a characterization of NQI(Q, C, S, ∅). Recall that the latter problem is related to ∃NQI: indeed, Theorem 30 reduces ∃NQI(Q, C, S) to NQI(Q, C, S, ∅) when the constraints C are preserved under disjoint unions. The proof of the characterization of NQI(Q, C, S, ∅), given in the full version, exploits the universality of our variant of the chase (Lemma 9). where S 1 ( x1 ), . . . , S m ( xm ) are the atoms in the CQ Q. The query Q is defined as the canonical query of the instance F , obtained by replacing each value v with a variable y v and by quantifying existentially over all these variables. Note that CanonDB(Q ) is isomorphic to the input instance F . Now, assume that the original constraints in C were connected FGTGDs and the CQ Q was also connected. By construction, the constraints in C turn out to be also connected FGTGDs. In particular, the satisfiability of these constraints is preserved under disjoint unions, and hence from Theorem 30, ∃NQI(Q , C , S ) = true iff NQI(Q , C , S , ∅) = true. Thus, it remains to show that NQI(Q , C , S , ∅) = true iff OWQ(Q, C, F ) = true.

By contraposition, suppose that OWQ(Q, C, F ) = false. This means that there is a S-instance F that contains F , satisfies the constraints in C, and violates the query Q. In particular, F , seen as an instance of the new schema S , without the visible fact Good, satisfies the query Q and the constraints in C (including the constraint that derives Good from the satisfiability of Q). The Sinstance F thus witnesses the fact that NQI(Q , C , S , ∅) = false.

Conversely, suppose that NQI(Q , C , S , ∅) = false. Recall that the constraints in C do not use constants and Q contains no visible facts. We can thus apply Proposition 34 and derive Chases vis (C , S , CanonDB(Q ))

∅. Note that CanonDB(Q ) is clearly isomorphic to the original instance F . In particular, there is an instance K in Chases vis (C , S , CanonDB(Q )) that contains the original instance F , satisfies the constraints in C , and does not contain the visible fact Good. From the latter property, we derive that K violates the query Q. Thus K, seen as an instance of the schema S, witnesses the fact that OWQ(Q, C, F ) = false.

We note that there are two variants of OWQ, corresponding to finite and infinite instances. However, by finite-controllability of FGTGDs, inherited from the finite model property of GNFO (see Theorem 1) these two variants agree. Hence we do not distinguish them. Similar remarks hold for other uses of OWQ within proofs in the paper.

From Proposition 33 and a prior 2Exp-hardness result [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF], we get the following lower bound: Theorem 35. ∃NQI(Q, C, S) is 2Exp-hard as Q ranges over BCQs and C over sets of connected FGTGDs.

Using a reduction from the implication problem for IDs, shown PSpace-hard in [START_REF] Casanova | Inclusion dependencies and their interaction with functional dependencies[END_REF], we get tightness of the bounds for linear TGDs: Theorem 36. ∃NQI(Q, C, S) is PSpace-hard as Q ranges over BCQs and C over sets of linear TGDs.

Finally, recall that our decidability result for ∃NQI applied only to connected FGTGDs. We can show that the connectedness property is critical for decidability.

Theorem 37. ∃NQI(Q, C, S) is undecidable, as Q ranges over BCQs and C over sets of FGTGDs.

Proof. We give a reduction from the model conservativity problem for EL TBoxes, shown undecidable in [START_REF] Lutz | Conservative extensions in the lightweight description logic EL[END_REF]. Intuitively, EL is a logic that defines FGTGDs over relations of arity 2, called "TBoxes". Given TBoxes φ 1 and φ 2 over two schemas S 1 and S 2 , respectively, with S 1 ⊆ S 2 , we say that φ 2 is a model conservative extension of φ 1 if every S 1 -instance V that satisfies φ 1 can be extended to an S 2 -instance that satisfies φ 2 without changing the interpretation of the predicates in S 1 , that is, by only adding an interpretation for the relations that are in S 2 but not in S 1 . The model conservativity problem consists of deciding whether φ 2 is a model conservative extension of φ 1 . In [START_REF] Lutz | Conservative extensions in the lightweight description logic EL[END_REF] this problem is proved to be undecidable for both finite instances and arbitrary instances.

We reduce the above problem to the complement of ∃NQI(Q, C, S), for suitable Q, C, and S, as follows. Given TBoxes φ 1 , φ 2 over schemas S 1 ⊆ S 2 , let S be the schema obtained from S 2 by adding a new predicate Good of arity 0 and by letting the visible part be S 1 (in particular, the relation Good is hidden). Further let C = {φ 1 , Good → φ 2 }, where Good → φ 2 is shorthand for the collection of FGTGDs obtained by adding Good as a conjunct to the left-hand side of each constraint of φ 2 (note that this makes the constraints unconnected). Finally, consider the query Q = Good. We have that ∃NQI(Q, C, S) = true iff there is an S 1 -instance V satisfying φ 1 , none of whose S 2 -expansions satisfies φ 2 .

A summary of results on negative implication is below. We notice that the decidable cases are orthogonal to those for positive implications: the dividing line for the positive case concerned the presence of disjunction, while for the negative case it concerns connectedness. Note also that unlike in the positive cases, we have tractable cases for data complexity.

Conclusions

This work gives a detailed examination of implication of query results from schemas with hidden relations in the presence of constraints in expressive integrity constraint languages. In future work

we will look at whether a query is implied over "typical models", in the spirit of Miklau and Suciu's [START_REF] Miklau | A formal analysis of information disclosure in data exchange[END_REF].

Example 1 .

 1 Consider a medical datasource with relation Appointment(p, a, . . .) containing patient names p, appointment ids a, and other information about the appointment, such as the name of the doctor. A dataowner makes available one projection of Appointment by creating a relation Patient(p) with the constraints: ∀ p Patient(p) → ∃ a d ȳ Appointment(p, a, d, ȳ) ∀ p a d ȳ Appointment(p, a, d, ȳ) → Patient(p) .

Example 4 .

 4 Returning to the medical example from the introduction, Example 1, we see that the GFP-Datalog program is quite intuitive: since Patient is empty in the instance and we have a referential constraint from Appointment into Patient, Appointment is removed as well, leaving the empty instance. The program then simply evaluates the query on the resulting instance, which returns false, indicating that an NQI does hold on the original instance.

Theorem 30 .

 30 If the constraints C consist of TGDs preserved under disjoint unions of instances, then ∃NQI(Q, C, S) = true iff NQI(Q, C, S, ∅) = true.

Proposition 34 .

 34 If Q is a BCQ and C is a set of TGDs without constants, then NQI(Q, C, S, ∅) = true iff either Q contains a visible atom, or it does not and in this case Chases vis (C, S, CanonDB(Q)) = ∅. Using this we can prove the reduction from OWQ to ∃NQI: Proof of Proposition 33. Consider the Open-World Query answering problem over a schema S, a set C of constraints without constants and closed under disjoint union, a BCQ Q, and a S-instance F . We reduce this problem to an ∃NQI problem over a new schema S , a new set of constraints C , and a new BCQ Q . The schema S is obtained from S by adding a relation Good of arity 0, which is assumed to be the only visible relation in S . The set of constraints C is equal to C unioned with the constraint S 1 ( x1 ) ∧ . . . ∧ S m ( xm ) → Good

  as Q ranges over BCQs and C over sets of FGTGDs without constants.The table below highlights the main results on PQI and ∃PQI.

		PQI Data	PQI Combined	∃PQI
	NoConst	Exp-complete	2Exp-complete	PSpace-complete
	Linear TGD	Thm 5/Thm 6	Thm 4/Thm 7	Thm 16/Cor 18
	NoConst	Exp-complete	2Exp-complete	2Exp-complete
	FGTGD	Thm 5/Thm 6	Thm 4/Thm 7	Cor 12/Cor 19
	NoConst Disj.	Exp-complete	2Exp-complete	undecidable
	Linear TGD	Thm 5/Thm 6	Thm 4/Thm 7	Thm 13
	Linear TGD	Exp-complete	2Exp-complete	undecidable
	& FGTGD	Thm 5/Thm 6	Thm 4/Thm 7	Cor 15
	& GNFO

Acknowledgements. Benedikt's work was sponsored by the Engineering and Physical Sciences Research Council of the United Kingdom, grants EP/M005852/1 and EP/L012138/1. Bourhis was supported by CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020 and ANR Aggreg project ANR-14-CE25-0017.