Alan Nash

Aleph One

Llc Luc

Victor Vianu

U C San

Views and Queries: Determinacy and Rewriting

We investigate the question of whether a query can be answered using a set V of views. We first define the problem in information-theoretic terms: we say that V determines if V provides enough information to uniquely determine the answer to . Next, we look at the problem of rewriting in terms of V using a specific language. Given a view language and query language , we say that a rewriting language ℛ is complete for -to-rewritings if every ∈ can be rewritten in terms of V∈ using a query in ℛ, whenever V determines . While query rewriting using views has been extensively investigated for some specific languages, the connection to the information-theoretic notion of determinacy, and the question of completeness of a rewriting language, have received little attention. In this paper we investigate systematically the notion of determinacy and its connection to rewriting. The results concern decidability of determinacy for various view and query languages, as well as the power required of complete rewriting languages. We consider languages ranging from first-order to conjunctive queries.

Introduction

The question of whether a given set of queries on a database can be used to answer another query arises in many different contexts. Recently, this has been a central issue in data integration, where the problem is framed in terms of query rewriting using views. In the exact local as view (LAV) flavor of the problem, data sources are described by views of a virtual global database. Queries against the global database are answered, if possible, by rewriting them in terms of the views specifying the sources. A similar problem arises in semantic caching: answers to some set of queries against a data source are cached, and one wishes to know if a newly arrived query can be answered using the cached information, without accessing the source. Yet another framework where the same problem arises (only in reverse) is security and privacy. Suppose access to some of the information in a database is provided by a set of public views, but answers to other queries are to be kept secret. This requires verifying that the disclosed views do not provide enough information to answer the secret queries.

The question of whether a query can be answered using a set V of views can be formulated at several levels. The most general definition is information theoretic: V determines (which we denote V↠ ) iff V( 1 ) = V( 2 ) implies ( 1 ) = ( 2), for all database instances 1 and 2 . Intuitively, determinacy says that V provides enough information to uniquely determine the answer to . However, it does not say that this can be done effectively, or using a particular query language. The next formulation is language specific: a query can be rewritten using V in a language ℛ iff there exists some query ∈ ℛ such that ( ) = (V( )) for all databases . Let us denote this by ⇒ V . As usual, there are two flavors to the above definitions, depending on whether database instances are unrestricted (finite or infinite) or restricted to be finite. The finite flavor is the default in all definitions, unless stated otherwise.

1 What is the relationship between determinacy and rewriting? Suppose ℛ is a rewriting language. Clearly, if ⇒ V for some ∈ ℛ then V↠ . The converse is generally not true. Given a view language and query language , if ℛ can be used to rewrite a query in using V in whenever V↠ , we say that ℛ is a complete rewriting language for -to-rewritings. Clearly, a case of particular interest is when itself is complete for -to-rewritings, because then there is no need to extend the query language in order to take advantage of the available views.

Query rewriting using views has been investigated in the context of data integration for some query languages, primarily conjunctive queries (CQs). Determinacy, and its connection to rewriting, has not been investigated in the relational framework. For example, CQ rewritings received much attention in the LAV data integration context, but the question of whether CQ is complete as a rewriting language for CQ views and queries has not been addressed.

In this paper we undertake a systematic investigation of these issues. We consider view languages and query languages ranging from first-order logic (FO) to CQ and study two main questions:

(i) is it decidable whether V↠ for V in and in ? (ii) is complete for -to-rewritings? If not, how must be extended in order to express such rewritings?

It is easily seen that determinacy becomes undecidable as soon as the query language is powerful enough so that satisfiability of sentences in becomes undecidable. The same holds if validity of sentences in is undecidable. Thus, (i) is moot for such languages, in particular for FO queries and views. However, determinacy is also undecidable for much weaker languages. Indeed, we show undecidability even for views and queries expressed as unions of conjunctive queries (UCQs). This is shown by a direct reduction of the word problem for finite monoids, known to be undecidable [START_REF] Gurevich | The word problem for some classes of semigroups[END_REF]. The question remains open for CQs, and appears to be quite challenging. Determinacy is shown to be decidable for special classes of CQs, such as Boolean or monadic CQs.

Before summarizing our results on question (ii), we mention two problems that are closely related, and that can be fruitfully used to gain insight into (ii). Suppose V↠ . Consider the query V associating to each view answer V( ) the corresponding query answer ( ), where is a database instance. In other words1 , = V ∘ V. To answer (ii), it is useful to understand the properties of the queries V , since this provides information on the rewriting language needed to express them. One useful piece of information is the complexity of computing the answer to V given a view instance V( ), also known as the query answering problem. We occasionally consider the complexity of query answering as a tool for resolving (ii). Other useful information on V concerns properties such as (non-)monotonicity, closure under extensions, etc. Again, we use such information to establish properties required of a language for rewriting using V.

We consider again languages ranging from FO to CQ. We only mention the results for some key combinations of query and view languages, that imply the results for most other combinations. In the unrestricted case, FO turns out to be complete for FO-to-FO rewritings, as a consequence of Craig's Interpolation theorem [START_REF] Chang | Model Theory[END_REF]. Unfortunately this does not extend to the finite case: FO is no longer complete for FO-to-FO rewritings, and indeed the query answering problem for this case is Turing complete. In fact, we show that any language complete for FO-to-FO rewritings must express all computable queries.

For views expressed in weaker languages, less powerful rewriting languages are needed. If views are expressed in ∃FO (existential FO), FO is still not complete for ∃FO-to-FO rewritings. However, both ∃SO and ∀SO (existential and universal second-order logic formulas) are complete for such rewritings. In fact, this is a lower bound: we show that every language complete for ∃FO-to-FO rewritings must be able to express all queries in ∃SO ∩ ∀SO. The lower bound holds even if views are restricted to UCQs. The proof uses results on the expressive power of implicit definability [START_REF] Lindell | The Logical Complexity of Queries on Unordered Graphs[END_REF][START_REF] Grumbach | Generalized implicit definitions on finite structures[END_REF]. It turns out that FO does not become complete as a rewriting language even if queries are in CQ ¬ (CQ with safe negation). This uses the fact, shown by Gurevich, that there exist order-invariant queries defined by FO with access to an order on the domain that are not definable in FO without order (see Exercise 17.27 in [START_REF] Abiteboul | Foundations of Databases[END_REF]).

The case of CQs is of particular interest in the context of answering queries using views, and has been intensively studied. The conventional wisdom has been that CQs must be complete for CQ-to-CQ rewritings. Surprisingly, we show that this is not the case. We do this by exhibiting a set of CQ views V and query such that V↠ but V is non-monotonic. Thus, no monotonic language can be complete for CQ-to-CQ rewritings. The same is shown for CQ ∕ = and UCQs.

Given the above, it is natural to ask whether CQ (and similarly CQ ∕ = and UCQ) remain complete in the case when the mapping V is monotonic. We answer this in the affirmative, for CQ as well as CQ ∕ = and UCQ.

What is then the rewriting power needed for CQ-to-CQ rewritings? A plausible candidate for a complete language for CQ-to-CQ rewritings would be FO. We are able to show that for all CQ views V and query for which V determines in the unrestricted case, there is an effective FO rewriting of using V.

The question remains open in the finite case, for which the best known upper bounds remains ∃SO ∩ ∀ .

Finally, we provide several special classes of CQ views and queries for which CQ remains complete for rewriting, and for which determinacy is decidable. One such class consists of monadic CQ views and arbitrary CQ queries. Another class consists of Boolean CQ views and queries. Beyond these, CQ can only remain complete for very limited classes of views. Indeed, we show that non-monotonic rewrite languages are required even for very simple CQ views whose patterns are trees, and that differ from simple paths by a single edge. We show that CQ remains complete for a binary view consisting of one simple path.

Related work

Answering queries using views arises in numerous contexts including data integration [START_REF] Ullman | Information integration using logical views[END_REF], query optimization and semantic caching [START_REF] Dar | Semantic data caching and replacement[END_REF], data warehousing [START_REF] Agrawal | Automated selection of materialized views and indexes Microsoft SQL Server[END_REF], support of physical data independence by describing storage schemas as views [START_REF] Deutsch | Physical data independence, constraints and optimization with universal plans[END_REF][START_REF] Tsatalos | Describing and using query capabilities of heterogeneous sources[END_REF][START_REF] Yang | Query transformation for PSJ-queries[END_REF], etc. The problem comes in several flavors, depending on assumptions on the views and their use. Mainly, the different settings vary along these dimensions:

(i) assumptions on the views: these may be exact (i.e. contain precisely the set of tuples in their definitions), or just sound (they provide only a subset of the tuples in the answer) (ii) how the views are used: query rewriting requires reformulating the query using the views, in some query language. One may require an equivalent rewriting, or just a maximally contained one. Another use of views is called query answering. This consists of finding all certain answers to a query given an instance of the view [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF].

In our investigation, we focus on exact view definitions, and equivalent query rewritings, with the accompanying information-theoretic notion of determinacy. We also consider the complexity of the query answering problem, but only in the case when the view determines the query (so the certain and possible answers coincide). Results on equivalent query rewriting using exact views have focused primarily on CQs and UCQs. It is shown in [START_REF] Alon | Answering queries using views[END_REF] that it is NP-complete whether a given (U)CQ query has an equivalent (U)CQ rewriting in terms of given (U)CQ views. Several polynomial-time special cases are identified for CQs in [START_REF] Chekuri | Conjunctive query containment revisited[END_REF]. Answering queries using views in the presence of binding patterns is considered in [START_REF] Rajaraman | Answering queries using templates with binding patterns[END_REF]. Views and queries defined by CQs with arithmetic comparisons over dense orders are considered in [START_REF] Afrati | Answering queries using views with arithmetic comparisons[END_REF], where it is shown that the existence of an equivalent rewriting using Datalog with comparisons is decidable. The problem for recursive queries is considered in [START_REF] Duschka | Answering recursive queries using views[END_REF], where it is shown that it is undecidable if a Datalog query can be rewritten using some Datalog program in terms of a set of CQ views. Answering queries using views in semi-structured databases represented by directed labeled graphs is considered in [START_REF] Calvanese | Rewriting of regular expressions and regular path queries[END_REF][START_REF] Calvanese | View-based query processing for regular path queries with inverse[END_REF][START_REF] Calvanese | Lossless regular views[END_REF]. Here the views and queries are defined by regular path expressions, possibly including inverse edge navigation. In [START_REF] Calvanese | Rewriting of regular expressions and regular path queries[END_REF] it is shown that the exact rewriting problem is 2expspace-complete.

The relation of rewriting to the information-theoretic notion of determinacy has received little attention. In [START_REF] Grumbach | Querying aggregate data[END_REF][START_REF] Grumbach | On the content of materialized aggregate views[END_REF], Grumbach and Tininini consider the problem of computing an aggregate function using a given set of aggregate functions including count, average, sum, product, maximum. In particular, [START_REF] Grumbach | On the content of materialized aggregate views[END_REF] introduces the notion of subsumption of a query by a view, which is identical to our notion of determinacy. Using this, they define completeness of a rewriting algorithm, and produce such an algorithm for simple aggregate functions on a single relation. Despite the similarity in flavor, none of the results transfer to the setting we consider.

In [START_REF] Calvanese | Lossless regular views[END_REF], the authors consider the notion of lossless view with respect to a query, in the context of regular path queries on semi-structured data. A set of views is lossless with respect to a query if for every database, the views are sufficient to answer the query. Losslessness is considered under the exact view assumption and under the sound view assumption. In the first case, losslessness is equivalent to determinacy and it remains open whether losslessness is decidable for regular path views and queries. In the second case, losslessness is shown to be decidable using automata-theoretic techniques. Again, these results have no bearing upon ours because of the differences in the settings and because we consider exact views.

In the context of view updates, Bancilhon and Spyratos introduced the notion of view complement [START_REF] Bancilhon | Update semantics of relational views[END_REF]. The complement of a view is another view so that together they uniquely determine the underlying database. This information-theoretic notion is a special kind of determinacy: a view and its complement determine the identity query on the database.

Suppose a set of views V does not determine a query . In this case one is typically interested to compute from a view extent the certain answers to . For exact views, the set of certain answers is

( ) = ∩{ ( ) | V( ) = }.
The data complexity of computing ( ) from has been studied by Abiteboul and Dutschka [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF] for various query and view languages (for both exact and sound views). The rewriting problem for exact views is to find a query in some rewriting language ℛ, such that for every extent of V, ( ) = ( ). If such exists for every V ∈ and ∈ , let us say that ℛ is complete for -to-rewritings of certain answers. Clearly, if

↠ then for every database , ( ) = (V( )). Thus, for exact views, every rewriting language that is complete for -to-rewritings of certain answers must also be complete for -torewritings according to our definition. In particular, our lower bounds on the expressive power of languages complete for -to-rewritings still hold for languages complete for -to-rewritings of certain answers. Also, upper bounds shown in [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF] on the data complexity of computing certain answers for exact views also apply to the data complexity of computing V in our framework.

For sound views,

( ) = ∩{ ( ) | ⊆ V( )}. If V↠ , it is easily seen that ( ) = V ( ) for all in the image of V iff V is monotonic, i.e. V( 1 ) ⊆ V( 2 ) implies ( 1 ) ⊆ ( 2 )
. In this case, the upper bounds shown in [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF] on the data complexity of computing for sound views also apply to the data complexity of computing V . Likewise, if a language ℛ can be used to rewrite in terms of V for sound views, and V is monotonic, then ℛ can be used to rewrite in terms of V in our sense.

In a broader historical context, the topic of this paper is related to the notion of implicit definability in logic, first introduced by Tarski [START_REF] Tarski | Einige methodologische Untersuchungen über die Definierbarkeit der Begriffe[END_REF]. The analog of completeness of a language for view-to-query rewritings is the notion of completeness for definitions of a logical language, also defined in [START_REF] Tarski | Einige methodologische Untersuchungen über die Definierbarkeit der Begriffe[END_REF]. In particular, FO was shown to be complete for definitions by Beth [START_REF] Beth | On Padoa's method in the theory of definition[END_REF] and later by Craig [START_REF] Craig | Three uses of the Herbrand-Gentzen theorem in relation to model theory and proof theory[END_REF], as an application of his Interpolation Theorem. Maarten Marx provides additional historical perspective on problems related to determinacy and rewriting [START_REF] Marx | Queries determined by views: pack your views[END_REF].

Recent work following up on the results of [START_REF] Segoufin | Views and queries: determinacy and rewriting[END_REF][START_REF] Nash | Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress Report[END_REF] has sought to identify additional classes of views and queries that are well behaved with respect to determinacy and rewriting. In [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF], Foto Afrati considers the case of path queries asking for nodes connected by a path of given length in a binary relation representing a directed graph. It is shown there that determinacy is decidable for path views and queries, and FO rewritings of the path query in terms of the path views can be effectively computed (see Remark 5.3). Taking a different approach, Maarten Marx considers in [START_REF] Marx | Queries determined by views: pack your views[END_REF] syntactic restrictions FO and UCQ yielding packed FO and UCQ, and shows for these fragments decidability of determinacy and completeness for rewritings (see Remarks 3.11,5.23).

The present paper is the extended version of the conference publications [START_REF] Segoufin | Views and queries: determinacy and rewriting[END_REF][START_REF] Nash | Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress Report[END_REF].

Organization After introducing some basic concepts in Section 2, we discuss determinacy and rewriting for FO queries and views in Section 3. We then proceed with unions of conjunctive queries and views in Section 4, and conjunctive queries and views in Section 5. We end with brief conclusions.

Preliminaries

We begin with some basic definitions and notation. Unless otherwise indicated, we follow standard terminology (see [START_REF] Abiteboul | Foundations of Databases[END_REF] and [START_REF] Libkin | Elements of finite model theory[END_REF]).

A database schema is a finite set of relation symbols with associated non-negative arities. A relation with arity zero is referred to as a proposition. We assume fixed an infinite domain dom of values. A database instance over associates a relation D( ) of appropriate arity with values from dom to each relation symbol in (true/false for propositions). The active domain of an instance consists of the set of elements in dom occurring in and is denoted adom( ). The set of all instances over is denoted by ℐ( ). By default, all instances are assumed to be finite unless otherwise specified. In terms of classical logic, a database instance is a relational structure whose universe is the active domain of the instance. In some proofs, we will need to apply known results of model theory that apply to classical relational structures, whose universe may strictly include the active domain. In this case, we will explicitly use the term relational structure. Queries are defined as usual, as computable mappings from instances of an input schema to instances of an output schema that are generic, i.e. commute with isomorphisms of dom (e.g., see [START_REF] Abiteboul | Foundations of Databases[END_REF]). We assume familiarity with the query languages in Figure 1. As usual for two queries and ′ , we denote by ⊆ ′ the fact that over all instances , ( ) is always a subset of ′ ( ). As usual, notation language FO first-order logic over relations ∃FO existential FO ∃SO existential second-order logic ∀SO universal second-order logic CQ conjunctive queries without =, ∕ =, constants UCQ unions of conjunctive queries (U)CQ = (U)CQs extended with =, ∕ = (U)CQ ∕ = Figure 1: Query languages used in the paper unless otherwise specified, constant values from dom may be used in queries. These are not part of the schema, and are always interpreted as themselves. This differs from constants in classical logic, which are part of the vocabulary and are interpreted as arbitrary values from the universe of the structure. Given a query , we define its active domain adom( ) to be the set of constant values used in . Given a database instance , we denote adom( , ) = adom( ) ∪ adom( ). The semantics of over an instance is defined with respect to the universe adom( , ). In particular, if is a first-order logic formula, all variables (free and quantified) range over adom( , ). If is in second-order logic, its first-order variables range over adom( , ) and its second-order variables range over relations over adom( , ). The semantics for relational structures is defined as usual with respect to the specified universe.

Let and V be database schemas. A view V from ℐ( ) to ℐ( V ) is a set consisting of one query ℐ( ) → ℐ({ }) for each ∈ V . We refer to and V as the input and output schemas of V, respectively.

Consider a query over schema and a view V with input schema and output schema V . We say that V determines , denoted V↠ , iff for all 1 , 2 ∈ ℐ( ), if V( 1 ) = V( 2 ) then

( 1 ) = ( 2 ). Let be a query over ℐ( V ). We say that is a rewriting of using V iff for each ∈ ℐ( ), ( ) = (V( )). In other words, = ∘ V. This is denoted by ⇒ V . Note that several 's may satisfy this property, since such 's may behave differently on instances in ℐ( V ) that are not in the image of V. The notions of determinacy and rewriting are related as there is a query such that ⇒ V iff V↠ .

Let be a query language and a view language. A query language ℛ is complete for -torewritings iff for every ∈ and V ∈ for which V↠ , there exists ∈ ℛ such that ⇒ V .

The notions of determinacy and rewriting come in two flavors: finite and unrestricted, depending on whether instances are restricted to be finite. We always assume the finite variant unless explicitly stated otherwise.

We next present some basic but useful observations about determinacy and rewriting.

Proposition 2.1 Let and be languages such that satisfiability of sentences in is undecidable or validity of sentences in is undecidable. Then it is undecidable whether V↠ , where is in and V is a set of views defined in .

Proof: Suppose first that satisfiability of sentences in is undecidable. Let be a sentence in over database schema . Consider the database schema ∪ { } where is unary. Let V be empty and = ∧ ( ). Clearly, V↠ iff is unsatisfiable.

Next, suppose validity of sentences in is undecidable. Let be a sentence in over schema . Consider the database schema ∪ { } with unary, and V consisting of the view ∧ ( ). Let consist of the query ( ). Clearly, V↠ iff is valid. □ Corollary 2.2 If is FO or is FO, it is undecidable whether V↠ for views V in and queries in .

In looking for fragments of FO for which determinacy might be decidable, it is tempting to reduce determinacy to satisfiability testing. This can be done as follows. Let be a database schema and V and be views and a query over . Let 1 and 2 be two disjoint copies of , and V , ( = 1, 2) versions of V and operating on 1 and 2 . Consider the FO sentence over

1 ∪ 2 : ∀¯ (V 1 (¯ ) ↔ V 2 (¯ )) ∧ ∃¯ ( 1 (¯ ) ∧ ¬ 2 (¯ )).
Clearly, V↠ iff is not finitely satisfiable. Unfortunately, even for CQ views and queries, does not belong to an FO fragment known to have a decidable satisfiability problem [START_REF] Börger | The Classical Decision Problem[END_REF]. Thus, we need to take advantage of the finer structure of the query languages we consider in order to settle decidability of determinacy.

Finally, suppose V↠ . Let then V be the mapping associating to every instance V( ) in the image of V the corresponding ( ). Note that V is defined only on the image of V. Therefore when we say " V is computable" we mean that for any instance in the image of V, V ( ) is computable. Similarly, genericity of V only applies to the image of V. Proposition 2.3 Suppose V and are computable views and queries without constants, over database schema , and V↠ . Let V be the mapping associating to every instance in the image of V the corresponding value of . Then V is generic and computable. In particular, for all ∈ ℐ( ): (i) adom( ( )) ⊆ adom(V( )), and (ii) every permutation of dom that is an automorphism of V( ) is also an automorphism of ( ).

Proof: Let be a permutation of dom.

Let = V( ). Then V ( ( )) = V ( (V( ))) = V (V( ( ))) = ( ( )) = ( ( )) = ( V (V( ))) = ( V ( ))
. Thus, V is generic, and (i) and (ii) are immediate consequences. To compute V on input in the image of V, find some over for which ( ) = , which is guaranteed to exist. Then compute ( ). □ Remark 2.4 Suppose V and are as in Proposition 2.3 and V halts on every instance in the image of V. One may wonder if V can be extended to a computable, halting query on all of ℐ( V ). A simple recursion-theoretic argument shows that this is not the case. In fact, there exist V and both in FO for which V↠ but V cannot be extended to a halting computable query on all of ℐ( V ).

FO Queries and Views

In this section we investigate determinacy and rewriting for FO queries and views. Determinacy is clearly undecidable for FO in view of Corollary 2.2. We therefore focus on rewriting. Is FO complete for FO-to-FO rewritings? The answer turns out to be radically different in the unrestricted and the finite cases.

We begin by considering the unrestricted variant. Recall that in the unrestricted case, database instances are allowed to be arbitrary (finite or infinite). We denote the fact that V determines for unrestricted instances by V ∞ ↠ . Theorem 3.1 below follows from the work of Beth and Craig [START_REF] Beth | On Padoa's method in the theory of definition[END_REF][START_REF] Craig | Three uses of the Herbrand-Gentzen theorem in relation to model theory and proof theory[END_REF]. We include a direct proof here for the sake of self containment.

Theorem 3.1 In the unrestricted case, FO is complete for FO-to-FO rewritings.

Proof: The general idea of the proof is simple, if V ∞ ↠ then V does not depend on the database but only on V( ). In other words V is invariant under the choice of , assuming V( ) remains fixed. This property can be specified in FO. Then, using Craig interpolation theorem, all reference to can be removed from the specification above, yielding a first-order formula which turns out to be the desired FO rewriting.

In developing the details, some care is needed because Craig's interpolation theorem applies to relational structures while the notion of determinacy involves database instances. Recall from Section 2 that a relational structure explicitly provides a universe that may be larger than the active domain of the same structure viewed as a database instance. In order to cope with this technical difference, we will explicitly restrict all quantifications to the active domain in the formula expressing that V determines , and use an extension of Craig's interpolation theorem that yields an interpolant that also quantifies over the active domain.

In this proof we will consider extensions of relational schemas with a finite set of constant symbols. If the schema contains constants, an instance over the schema provides values to the constants in addition to the relations. For FO sentences , over the same schema, we use the notation |= to mean that every structure (finite or infinite) satisfying also satisfies . We also use the notation ∃(∀)¯ ∈ for a unary symbol and vector of variables ¯ = 1 . . .

as shorthand for ∃(∀) 1 ∈ . . . ∃(∀)
∈ . Let be the database schema, V = { 1 , ⋅ ⋅ ⋅ , } be the output schema of V, and 1 , ⋅ ⋅ ⋅ , be the corresponding queries defining V. Suppose V ∞ ↠ where V and are FO views and queries over schema .

Let 1 , 2 be disjoint copies of . Let be the number of free variables of and let ¯ be constant symbols. Let 1 , 2 , be three new unary symbols. We now consider relational structures over the schema

= 1 ∪ 2 ∪ V ∪ {¯ , 1 , 2 ,
}. The intended meaning of a structure over is that its projection over 1 and 2 form two database instances having the same view which is the projection of the structure over V . Moreover 1 , 2 and are respectively the active domain of relations occurring in 1 , 2 and . For = 1 or = 2 we denote by the query obtained from by replacing every symbol from with its copy in , by enforcing that every free variable belongs to and by restricting each quantification to range over . For all ≤ we define similarly copies 1 and 2 of by restricting the range of quantification in the appropriate way. Finally we denote by the formula stating that the elements of appear in some relation of . For = 1 or 2, consider the following formula which will be denoted by V = V in the sequel:

⋀ =1,⋅⋅⋅ , ∀¯ ∈ (¯ ) ↔ (¯ ) ∧ ∧ ⋀ =1,⋅⋅⋅ , ∀¯ ∈ (¯ ) → ¯ ∈ ∧ ∀ ∈ ∃¯ ∈ ⋁ =1,⋅⋅⋅ , (¯ , )
This formula says that (i) when restricted to the elements of , is indeed the th view of the database , (ii) the elements of contains at least the elements of the view of the restriction of the database to elements of , and (iii) contains only elements of the view of database restricted to elements . Altogether this says that the restriction of to elements of is exactly the th view of the restriction to elements of of the database . The following result is now a simple consequence of the fact that V( ) determines .

Claim 3.2 ( 1 ∧ V 1 = V ∧ 1 (¯ )) |= [( 2 ∧ V 2 = V ) → 2 (¯ )] (1)
Proof: Let be a relational structure over such that |= ( 1

∧V 1 = V ∧ 1 (¯ )). We need to show that |= [( 2 ∧V 2 = V ) → 2 (¯ )].
For this we further assume that |= 2 ∧V 2 = V and we show that |= 2 (¯ ).

For = 1 or = 2, let be the database instance over constructed from by keeping only the restriction of the relations of to the elements of . Let be the database instance constructed from by keeping only the restriction of the relations of V to the elements of . By definition of V 1 = V and V 2 = V we have V( 1 ) = =V( 2 ). Let ¯ be the interpretation in of the constants ¯ . As the free variables of 1 were restricted to elements of 1 , from |= 1 (¯ ) we have 1 |= (¯ ). Hence, because V ∞ ↠ we must have 2 |= (¯ ). By construction of 2 this implies that |= 2 (¯ ) as required.

□

Notice now that the formula of the left-hand side of (1) contains only symbols from 1 ∪ V ∪ {¯ , 1 , } and all quantifications are restricted to elements either in 1 or in , while the formula of the right-hand side contains only symbols from 2 ∪ V ∪ {¯ , 2 , } and all quantifications are restricted to elements either in 2 or in . Hence, by the relativized Craig's Interpolation Theorem proved by Martin Otto [START_REF] Otto | An Interpolation Theorem[END_REF] there exists a sentence (¯ ) that uses only symbols from V ∪ {¯ , } where all quantifications are restricted to elements of and such that:

( 1 ∧ V 1 = V ∧ 1 (¯ )) |= (¯ ) (2)
(¯ ) |= [( 2 ∧ V 2 = V ) → 2 (¯ )] (3)
Note first that as quantifications in are restricted to elements of we can assume that does not contain any atom of the form ( ) where is a quantified variable (otherwise we replace it by true). Let now Θ be the formula obtained from by ignoring the restriction of the quantifications to , by replacing ¯ with free variables ¯ and by replacing all terms of the form ( ) where is a constant by true.

We now show that Θ is a rewriting of using V. Let be a database instance over and let be V( ). We need to show that for all tuples ¯ of elements of we have ¯ ∈ ( ) iff ¯ ∈ Θ( ). Let be the relational structure whose universe is the active domain of and whose relations of 1 , 2 and V are respectively the corresponding relations of and , where ¯ is interpreted as ¯ and where 1 , 2 and are the active domains of relations respectively in 1 , 2 and V .

Assume first that ¯ ∈ ( ). By construction of and because of the restrictions on the quantifications we have

|= ( 1 ∧ V 1 = V ∧ 1 (¯ )). From (2) we have |= (¯ )
. By construction of Θ, this implies that ¯ ∈ Θ( ).

Assume now that ¯ ∈ Θ( ). By construction of and Θ this implies that |= (¯ ). Hence from [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF]

we have |= [( 2 ∧ V 2 = V ) → 2 (¯ )]. Now by construction |= 2 ∧ V 2 = V . Therefore |= 2 (¯ ).
As 2 restricts its quantification to 2 which is the active domain of this implies ¯ ∈ ( ). □

The proof of Theorem 3.1 relies crucially on Craig's Interpolation Theorem. This fundamental result in model theory holds for unrestricted instances but fails in the finite case [START_REF] Ebbinghaus | Finite Model Theory[END_REF]. Indeed, Theorem 3.1 does not hold in the finite case, as shown next.

Example 3.3 Let be a database schema and ≤ the extension of with a binary relation "≤". Let (≤) be an FO sentence over ≤ . Let be the FO sentence checking that ≤ is a linear order. Now consider the set of views V with V = ∪ { }, where is zero-ary. V returns the value of (in ) and the content of for each ∈ . Let be the query ∧ (≤). It it easy to verify that if is order invariant (i.e. its answer is independent of the choice of the order relation ≤) then V↠ . If FO is complete for FO-to-FO rewritings in the finite, then there exists an FO query over V = ∪ { } such that is equivalent to . On ordered finite instances, this means that (≤) is equivalent to ( / ), obtained by replacing the proposition with true in . However, Gurevich has shown that there exist order-invariant FO queries (≤) expressing queries that are not finitely definable in FO (see Exercise 17.27 in [START_REF] Abiteboul | Foundations of Databases[END_REF]). This is a contradiction.

The following characterizes the expressive power needed for completeness wrt FO-to-FO rewriting in the finite case.

Theorem 3.4 If ℛ is complete for FO-to-FO rewritings (for finite instances) then ℛ expresses all computable queries.

Proof: Let be an arbitrary Turing machine expressing a total, computable generic query whose inputs and outputs are graphs (the argument can be easily extended to arbitrary schemas). More precisely, consider a directed graph with sets of nodes adom( ), and ≤ a total order on the nodes. We consider a standard encoding ≤ ( ) of as a string in {0, 1} * of length |adom( )| 2 whose ⟨ , ⟩-th position in lexicographic order is 1 iff ⟨ , ⟩ ∈ where and have rank resp. with respect to the order ≤.

computes iff on input ≤ ( ) halts with output ≤ ( ( )), for every total order ≤ on adom( ). Consider the database schema = { 1 , 2 , ≤, } where 1 , 2 and ≤ are binary, and is ternary. The intended meaning is that 1 is the input graph, ≤ is a total order over some set ⊇ adom( 1 ) with adom( 1 ) as initial elements, and represents a halting computation of on input ≤ ( 1 ), with output ≤ ( 2 ). More specifically, ( , , ) holds if in the -th configuration of , the content of the -th tape cell is (the position of the head and the state are encoded in tape symbols). In the encoding, is represented by the element of rank in the ordering ≤. Using standard techniques (see for instance [START_REF] Abiteboul | Foundations of Databases[END_REF]) one can construct an FO sentence over stating that ≤ is indeed a total order including adom( ) as initial elements, and that is a correct representation of a halting computation of on input ≤ ( 1 ), with output ≤ ( 2 ). Let V be the view with V = { 1 } defined by 1 = ∧ 1 ( , ), and be the query ∧ 2 ( , ).

We claim that V↠ and = ∘ V. Indeed if V is empty then either is false or 1 is empty. In both cases is empty (note that by genericity (∅) = ∅) and so = ∘ V. If V is not empty then holds and V returns 1 . As holds, equals 2 = ( 1 ). Thus, = ∘ V. □

In terms of complexity, Theorem 3.4 says that there is no complexity bound for the query answering problem for FO views and queries. It is clearly of interest to identify cases for which one can show bounds on the complexity of query answering. We next show that for views restricted to ∃FO, the complexity of query answering is NP ∩ co-NP. The bound is tight, even when the views are further restricted to UCQs. This will be shown using a logical characterization of NP ∩ co-NP by means of implicit definability [START_REF] Lindell | The Logical Complexity of Queries on Unordered Graphs[END_REF][START_REF] Grumbach | Generalized implicit definitions on finite structures[END_REF].

Recall that Fagin's Theorem shows that ∃SO expresses NP, and ∀SO expresses co-NP (see [START_REF] Libkin | Elements of finite model theory[END_REF]). Thus, to show the NP ∩ co-NP complexity bound it is sufficient to prove the completeness of ∃SO and ∀SO for ∃FO-to-FO rewritings. We do this next. Theorem 3.5 ∃SO and ∀SO are both complete for ∃FO-to-FO rewritings.

Proof: Let V be a view from ℐ( ) to ℐ( V ) defined in ∃FO. Let be an instance over ℐ( V ) in the image of V. We start with the following lemma showing that among the database instances such that V( ) = there is one of size polynomial in | |. Lemma 3.6 Let V be defined in ∃FO and be the maximum number of variables and constants in a view definition of V, in prenex form. If ∈ ℐ( V ) and is in the image of V then there exists ∈ ℐ( ) such that V( ) = and |adom( )| ≤ |adom( )| .

Proof: Let , V be as in the statement. Let ′ ∈ ℐ( ) be such that V( ′ ) = . Consider ∈ V with corresponding view and let ¯ be a tuple in ( ) (its arity is at most ). Each such ¯ is witnessed by an assignment ¯ extending ¯ to the existentially quantified variables of . Let be the set of all elements of ′ occurring in ¯ for some tuple ¯ of . Let be the restriction of ′ to . By construction, each assignment ¯ still witnesses ¯ . Therefore, ⊆ V( ). Because V is in ∃FO, V is closed under extension, so V( ) ⊆ V( ′ ) = . Altogether V( ) = and adom( ) = has size bounded by |adom( )| .

□ Assume now that is in FO and that V↠ . Recall that V is the mapping associating to every instance in the image of V the corresponding value of . Recall that, by Proposition 2.3, adom( V ( )) ⊆ adom( ). By Lemma 3.6 a non-deterministic polynomial algorithm for checking whether a tuple ¯ over adom( ) is in V ( ) goes as follows: guess a database instance over of size polynomial in | |, check that V( ) = and check that ¯ ∈ ( ). Also from Lemma 3.6 we have the following universal polynomial algorithm: For all database instances of size polynomial in | |, if V( ) = , check that ¯ ∈ ( ). The first algorithm is in NP while the second is in co-NP. By Fagin's theorem this implies that ¯ ∈ V ( ) can be expressed by both ∃SO and ∀SO formulas (¯ ). By universality of constants, it follows that there are ∃SO and ∀SO formulas (¯ ) defining V . □

We next show that Theorem 3.5 is tight, i.e. every rewriting language complete for ∃FO-to-FO rewritings must be able to express all properties in ∃SO ∩ ∀SO. In fact, the lower bound holds even for UCQ-to-FO rewritings.

Theorem 3.7 Let be a schema. For every query on instances over , definable in ∃SO ∩ ∀SO, there exists a set V of UCQ views and an FO sentence such that V↠ and V defines .

Proof: We use a result of [START_REF] Lindell | The Logical Complexity of Queries on Unordered Graphs[END_REF] (see also [START_REF] Grumbach | Generalized implicit definitions on finite structures[END_REF]) on the expressive power of implicit definability over finite instances. We briefly recall the result and related definitions. Let be a database schema. Let be a query over returning a -ary relation. Such a query is said to be implicitly definable over if there exists a schema ′ = ∪ { , ¯ }, where is -ary and ¯ are new relation symbols, and a FO( ′ ) sentence ( , ¯ ) such that (i) for all ∈ ℐ( ) there exists a sequence ¯ of relation over adom( ) such that |= ( ( ), ¯ ) and (ii) for all relations and ¯ over adom( ) we have |= ( , ¯ ) implies = ( ). The set of queries implicitly definable over is denoted by GIMP( ). We use the following known result [START_REF] Lindell | The Logical Complexity of Queries on Unordered Graphs[END_REF][START_REF] Grumbach | Generalized implicit definitions on finite structures[END_REF]: GIMP( ) consists of all queries whose data complexity is NP ∩ co-NP. In view of Fagin's Theorem, this yields: Theorem 3.8 [START_REF] Lindell | The Logical Complexity of Queries on Unordered Graphs[END_REF][START_REF] Grumbach | Generalized implicit definitions on finite structures[END_REF] GIMP( ) consists of all queries over expressible in ∃SO ∩ ∀SO.

Thus, to establish Theorem 3.7 it is enough to show that every language complete for UCQ-to-FO rewritings must express every query in GIMP( ).

Let be a schema and a query in GIMP( ). Thus, there exists an FO sentence ( , ¯ ) over ′ = ∪ { , ¯ } such that is implicitly defined over by ( , ¯ ). We may assume wlog that ( , ¯ ) uses only ∧, ¬, ∃.

We construct and V as follows. We first augment ′ with some new relation symbols. For each subformula (¯ ) of with free variables consider two relation symbols and ¯ of arity . In particular, is a proposition. Let be the set of such relations, and ′′ = ′ ∪ . Given ∈ ℐ( ′ ), the intent is for to contain ( ( ′ )) and for ¯ to be the complement of (for technical reasons, ¯ is needed even when ¬ is not a subformula of ). The interest of the auxiliary relations is that can be checked by verifying that each has the expected content using a straightforward structural induction on . This is done by checking simple connections between the relations in :

(1) ¯ = adom( ) - , ¬ = ¯ , ( 2
) 1 ∧ 2 (¯ , ¯ , ¯ ) = 1 (¯ , ¯ ) ∧ 2 (¯ , ¯ ), and (3) ∃ ( ,¯ ) (¯ ) = ∃ ( ,¯ ) ( , ¯ ).
Let be an FO( ′′ ) formula which checks that all relations , ¯ ∈ satisfy (1)-( 3) above. Let be the query ∧ ( , ¯ ) ∧ (¯ ). Thus, for for ∈ ℐ( ′′ ) satisfying and for which additionally the relations of ( ) satisfy ( 1)-( 3), ( ) returns ( ) = ( ( )).

We now define a set V of UCQ views. On input ∈ ℐ( ′′ ), a first subset V of V simply returns ( ). In particular, V provides the active domain of . A second set of views, V , allows verifying whether the relations in satisfy (1)-( 3) without providing any information on ( ). Specifically, V contains the following:

(i) Views allowing to check (1). To verify that ¯ is the complement of , we use two views: the first is defined by (¯ ) ∧ ¯ (¯ ) and the second (¯ ) ∨ ¯ (¯ ). If is the arity of , (1) holds iff the first view returns ∅ and the second returns .

(ii) Views allowing to check [START_REF] Abiteboul | Foundations of Databases[END_REF]. Let (¯ , ¯ , ¯ ) = 1 (¯ , ¯ ) ∧ 2 (¯ , ¯ ), where ¯ , ¯ , ¯ are disjoint sequences of free variables. We use three views. The first is defined by

1 (¯ , ¯ ) ∧ 2 (¯ , ¯ ) ∧ ¯ (¯ , ¯ , ¯ ), the second by (¯ , ¯ , ¯ ) ∧ ¯ 1 (¯ , ¯ )
, and the third by (¯ , ¯ , ¯ ) ∧ ¯ 2 (¯ , ¯ ). Note that (2) holds for iff the three views return the empty set.

(iii) Views allowing to check [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF]. Let (¯ ) = ∃ 1 ( , ¯ ). We use two views. The first is defined by ∃ 1 ( , ¯ ) ∧ ¯ (¯ ), and the second by ∃ 1 ( , ¯ ) ∨ ¯ (¯ ). If is the arity of then (3) holds iff the first view is empty while the second is .

Finally, V contains a view that returns the value of , which coincides with that of . We now claim that V↠ . Consider ∈ ℐ( ′′ ). As described above, the views V provide enough information to determine if the relations in satisfy (1)- [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF]. In particular, this determines the value of . If is false then ( ) = ∅. If is true, provides the value of . If is false then ( ) = ∅. If is true then ( ) returns ( ) = ( ( )) which is uniquely determined by ( ) by definition of GIMP. Since V provides ( ), it follows that V↠ . Now consider V . By definition, V computes ( ( )) on instances ∈ ℐ( V )) extending ( ) to V with relations ∅ or adom( ( )) for the view relations in V corresponding to the case when is satisfied by the pre-image of the view, as described in (i)-(iii), and with true for , corresponding to the case when the pre-image satisfies . This extension is trivial, and easily expressible from ( ), hence V has the same complexity as . □

Note that Theorem 3.7 requires only UCQ views and therefore Theorem 3.5 is also tight when views are restricted to UCQs. As an immediate consequence of Theorem 3.7 any language not capturing NP ∩ co-NP fails to be complete for UCQ-to-FO rewritings. As this is the case for Datalog ¬ and fixpoint logic2 FO+LFP [START_REF] Libkin | Elements of finite model theory[END_REF] we have: Corollary 3.9 Datalog ¬ and FO+LFP are not complete for UCQ-to-FO rewritings.

We can show that FO is not a complete rewriting language even if the views are restricted to CQ ¬ , where CQ ¬ is CQ extended with safe negation. Proposition 3.10 FO is not complete for CQ ¬ -to-FO rewritings.

Proof: We revisit Example 3.3. We use a strict linear order < rather than ≤. As in the example, we use schemas and < , an FO sentence checking that < is a strict total order, and the FO query = ∧ (<) for some order-invariant FO( < ) sentence which is not FO-definable over alone.

Let V consist of the following views:

1. < ∧ < 2. < ∧ < ∧ ¬( < ),
3. for each pair of relations 1 , 2 ∈ and appropriate , , one view 1 (. . . , , . . .)∧ 2 (. . . , , . . .)∧ ¬( < ) ∧ ¬( < )

4. for each ∈ , one view returning .

We claim that V↠ . First, note that holds (i.e. < is a strict total order on the domain) iff views (1) and ( 2) are empty and the view (3) contains all the tuples ( , ) for in adom( ). Indeed, this ensures antisymmetry (1), transitivity (2), and totality [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF]. If any of these views is not empty, then is false so is false. Otherwise, returns the value of (<) on the relations in < , which by the order invariance of (<) depends only on the relations in . These are provided by the views [START_REF] Agrawal | Automated selection of materialized views and indexes Microsoft SQL Server[END_REF]. Thus, V↠ and V allows defining (<) using just the relations in , which cannot be done in FO. □ Remark 3.11 In work subsequent to [START_REF] Segoufin | Views and queries: determinacy and rewriting[END_REF][START_REF] Nash | Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress Report[END_REF], Maarten Marx identifies a well-behaved fragment of FO with respect to determinacy and rewriting [START_REF] Marx | Queries determined by views: pack your views[END_REF]. The fragment, called packed FO (PFO), is an extension of the well-known guarded fragment [START_REF] Grädel | On the restraining power of guards[END_REF]. In a nutshell, guarded FO is restricted by allowing only quantifiers of the form ∃¯ ( (¯ , ¯ ) ∧ (¯ , ¯ )) where (¯ , ¯ ) is an atom, and (¯ , ¯ ) is itself a guarded formula with free variables ¯ , ¯ . In terms of the relational algebra, guarded FO corresponds to the semi-join algebra [START_REF] Leinders | The semijoin algebra and the guarded fragment[END_REF]. Packed FO relaxes the guarded restriction by allowing as guards conjunctions of atoms so that each pair of variables occurs together in some conjunct. The results in [START_REF] Marx | Queries determined by views: pack your views[END_REF] show that infinite and finite determinacy coincide for PFO, determinacy is decidable in 2-exptime, and PFO is complete for PFO-to-PFO rewritings. Similar results are obtained for the packed fragment of UCQ, see Remark 5.23.

UCQ Views and Queries

We have seen that determinacy is undecidable for FO views and queries, and indeed for any query language with undecidable satisfiability problem and any view language with undecidable validity problem. However, determinacy remains undecidable for much weaker languages. We show next that this holds even for UCQs. The undecidability result is quite strong, as it holds for a fixed database schema, a fixed view, and UCQs with no constants.

Theorem 4.1 There exists a database schema and a fixed view V over defined by UCQs, for which it is undecidable, given a UCQ query over , whether V↠ .

Proof: The proof is by reduction from the word problem for finite monoids: Consider a finite set of equations of the form ⋅ = , where , , are symbols. Let be an equation of the form = . Given a monoid ( , ∘), the symbols are interpreted as elements in and ⋅ as the operation ∘ of the monoid. Given and as above, the word problem for finite monoids asks whether implies over all finite monoids. This is known to be undecidable [START_REF] Gurevich | The word problem for some classes of semigroups[END_REF].

For the purpose of this proof, we will not work directly on monoids but rather on monoidal operations. Let be a finite set. A function : × → is said to be monoidal if it is complete (total and onto) and defines an associative operation. The operation of a monoid is always monoidal due to the presence of an identity element. It is immediate to extend Gurevich's undecidability result to monoidal functions by augmenting a monoidal function, if needed, with an identity element.

We construct a view V and, given and as above, a query , such that V ↠ , iff implies over all finite monoidal functions. We proceed in two steps. We construct V and , in UCQ = , then we show how equality can be removed. Consider the database schema = { , 1 , 2 } where is ternary and 1 , 2 are zero-ary (propositions). We intend to represent ⋅ = by ( , , ).

It is easily seen that for every satisfying the above equalities, ≃ is a congruence. We now modify V by replacing the query that checks that is the graph of a function (equation (ii)) by a set of queries corresponding to the new equations above and, replacing in the others all equalities = by ∃ , ( , , ) ∧ ( , , ). We also modify the query , , by replacing all equalities = by ∃ , ( , , ) ∧ ( , , ). As before, we can show that V↠ , iff implies over all finite pseudo-monoidal relations. The latter is undecidable, since implication over finite pseudo-monoidal relations is the same as implication over finite monoidal functions. This follows from the fact that every finite monoidal function is in particular a finite pseudo-monoidal relation, and every finite pseudo-monoidal relation can be turned into a finite monoidal function by taking its quotient with the equivalence relation ≃ defined above.

Finally, note that the zero-ary relations 1 and 2 can be avoided in the database schema if so desired by using instead two Boolean CQs over some non-zero-ary relation, whose truth values are independent of each other. For example, such sentences using a binary relation might be

1 = ∃ , , (
, ) ∧ ( , ) ∧ ( , ) and 2 = ∃ , ( , ) ∧ ( , ). □
We next turn to the question of UCQ-to-UCQ rewritings. Unfortunately, UCQ is not complete for UCQ-to-UCQ rewritings, nor are much more powerful languages such as Datalog ∕ = . Indeed, the following shows that no monotonic language can be complete even for UCQ-to-CQ rewritings. In fact, this holds even for unary databases, views, and queries. Proposition 4.2 Any language complete for UCQ-to-CQ rewritings must express non-monotonic queries. Moreover, this holds even if the database relations, views, and query are restricted to be unary.

Proof: Consider the schema = { , } where and are unary. Let V be the set consisting of three views 1 , 2 , 3 defined by the following queries:

1 ( ) : ∃ ( ) ∧ ( ) 2 ( ) :
( ) ∨ ( )

( ) : ( ).

Let ( ) be the query ( ). It is easily seen that V↠ . Indeed, if ∕ = ∅ then 1 provides the answer to ; if = ∅ then 2 provides the answer to . Finally, 3 provides . Therefore, V↠ . Now consider V , associating ( ) to V( ). We show that V is not monotonic. Indeed, let 1 be the database instance where = { , } and is empty.

Let 2 consist of = { } and = { }. Then V( 1 ) = ⟨∅, { , }, ∅⟩, V( 2 ) = ⟨{ }, { , }, { }⟩, so V( 1 ) ⊆ V( 2 ). However, ( 1 ) = { , }, ( 2 ) = { }, and ( 1 ) ∕ ⊆ ( 2 ). □
We next show a similar result for CQ ∕ = views and CQ queries.

Proposition 4.3 Any language complete for CQ ∕ = -to-CQ rewritings must express non-monotonic queries. Moreover, this holds even if the views and query are monadic (i.e. they answers are unary relations).

Proof: Let = { }, where is binary. Consider the view V consisting in three views 1 , 2 , 3 defined as follows:

1 ( ) = ∃ ( , ) ∧ ( , ), 2 ( ) = ∃ ( , ) ∧ ( , ) ∧ ∕ = and 3 ( ) = ∃ ( , ) ∧ ( , ) ∧ ( , ) ∧ ∕ = .
Consider the query ( ) defined by ( , ). It is easy to check that V↠ . Indeed can be defined by ( 1 ∧ ¬ 2 ) ∨ 3 . Consider the databases instances and ′ where is respectively {( , )} and {( , ), ( , )}.

Then V( ) = ⟨{ }, ∅, ∅⟩, V( ′ ) = ⟨{ , }, { , }, ∅⟩, ( ) = { } and ( ′ ) = ∅. Thus, V( ) ⊂ V( ′ ) but ( ) ∕ ⊆ ( ′ ).
Therefore cannot be rewritten in terms of V using a monotonic language. □ From Proposition 4.2 and Proposition 4.3 we immediately have:

Corollary 4.4 Datalog ∕ = is not complete for CQ ∕ = -to-CQ rewritings or for UCQ-to-CQ rewritings, even if the views and query are restricted to be monadic.

Proposition 4.2 provides a lower bound of sorts for any rewriting language complete for UCQ-to-UCQ rewritings or for CQ ∕ = -to-CQ rewritings. Note that it also follows from Theorem 4.1 that UCQ is not complete for UCQ-to-UCQ rewritings. Indeed, by Theorem 3.9 in [START_REF] Alon | Answering queries using views[END_REF], it is decidable if a UCQ query can be rewritten in terms of a set of UCQ views V using a UCQ. Therefore, completeness of UQC for UCQ-to-UCQ rewritings would contradict the undecidability of determinacy.

Recall that, from Theorem 3.5, we know that ∃SO and ∀SO are both complete for UCQ-to-UCQ rewritings and for CQ ∕ = -to-CQ rewritings. It remains open if we can do better. In particular, we do not know if FO is complete for UCQ-to-UCQ rewritings or for CQ ∕ = -to-CQ rewritings.

Conjunctive views and queries

Conjunctive queries are the most widely used in practice, and the most studied in relation to answering queries using views. Given CQ views V and a CQ query , it is decidable whether can be rewritten in terms of V using another CQ ( [START_REF] Alon | Answering queries using views[END_REF]). But is CQ complete for CQ-to-CQ rewriting? Note that this would immediately imply decidability of determinacy for CQ views and queries, by the above result of [START_REF] Alon | Answering queries using views[END_REF]. Surprisingly, we show that CQ is not complete for CQ-to-CQ rewriting. Moreover, the decidability of determinacy for conjunctive views and queries remains open, and appears to be a hard question. The problem is only settled for some special fragments of CQs, described later in this section.

CQ is not Complete for CQ-to-CQ Rewriting

In this section, we show that CQ is not complete for CQ-to-CQ rewriting. In fact, no monotonic language can be complete for CQ-to-CQ rewriting.

Before proving the main result of the section, we recall a test for checking whether a CQ query has a CQ rewriting in terms of a given set of CQ views. The test is based on the chase.

Let be a database schema and (¯ ) a CQ over with free variables ¯ . In this section, we will use the standard technique of identifying each conjunctive query with an instance called its frozen body. To this end, let var be an infinite set of variables disjoint from dom, such that all variable used in conjunctive queries belong to var. Instead of instances over dom, we will consider in this section instances over the extended domain dom ∪ var. Now we can associate an instance to a conjunctive query as follows. The frozen body of , denoted [ ], is the instance over such that ( 1 , . . . , ) ∈ iff ( 1 , . . . , ) is an atom in . Note that ( 1 , . . . , ) may contain constants (from dom) as well as variables (from var). For a set V of CQs, [V] is the union of the [ ]'s for all ∈ V. For a mapping from variables to variables and constants, we denote by ([ ]) the instance obtained by applying to all variables in [ ].

A homomorphism from an instance to an instance over the extended domain dom ∪ var is a classical homomorphism that is the identity on dom. Recall that a tuple ¯ is in ( ) for a CQ and database instance iff there exists a homomorphism ℎ from [ ] to such that ℎ(¯ ) = ¯ . In this case we say that ℎ witnesses ¯ ∈ ( ), or that ¯ ∈ ( ) via ℎ.

Let V be a CQ view from ℐ( ) to ℐ( V ). Let be a database instance over ℐ( V ) and a set of elements. We define the V-inverse of relative to a domain , denoted V -1 ( ), as the instance over defined as follows. Let be a relation in V , with corresponding query (¯ ). For every tuple ¯ belonging to in , we include in the tuples of ([ ]) where (¯ ) = ¯ and maps every variable of [ ] not in ¯ to some new distinct value not in adom( ) ∪ . For the reader familiar to the chase, V -1 ( ) is obtained as a chase of with respect to the tuple generating dependencies ∀¯ ( (¯ ) → ∃¯ (¯ , ¯ )), where ∈ V and is the body of the query defining in V, in which all values introduced as witnesses are outside adom( ) and . To simplify, we usually assume that consists of the entire active domain of when V -1 is applied, and omit specifying it explicitly. Thus, all witnesses introduced by an application of V -1 are new elements.

The following key facts were also observed in [START_REF] Deutsch | Physical data independence, constraints and optimization with universal plans[END_REF]:

Proposition 5.1 Let (¯ ) be a CQ (with free variables ¯ ) and = V([ ]). Let V (¯ ) be the CQ over V for which [ V ] = . We have the following:

(i) ⊆ V ∘ V -1 ( ); (ii) ⊆ V ∘ V; (iii) If ¯ ∈ (V -1 ( )) then ≡ V ∘ V.
In particular, V↠ .

(iv) If has a CQ rewriting in terms of V, then V is such a rewriting.

Proof: Part(i) is obvious from the definition of V -1 ( ).

For part (ii) notice that by definition of V the frozen body of V ∘ V is isomorphic to V -1 ( ). The inclusion then follows from the fact that there is a homomorphism from V -1 ( ) to [ ] preserving ¯ . To see this, recall that every tuple ¯ ∈ ([ ]) is witnessed by a homomorphism ℎ ¯ from [ ] to [ ] and also induces an copy of [ ] in V -1 ( ). The union of all the ℎ ¯ yields the desired homomorphism from V -1 ( ) to [ ].

Consider now (iii). If ¯ ∈ (V -1 ( )) then there is a homomorphism from [ ] to V -1 ( ) fixing ¯ . As the body of V ∘ V is V -1 ( ), it follows that V ∘ V ⊆ and we conclude using (ii).

It remains to show (iv). Suppose that V is a CQ rewriting of using V. In particular we have for all , ( ) = V ∘ V( ). We show that ¯ ∈ (V -1 ( )) and we conclude using (iii). We have

¯ ∈ ([ ]). Hence ¯ ∈ V (V([ ])) = V ( ). By (i), ⊆ V ∘ V -1 ( ). Because V is conjunctive, so monotonic, we also have ¯ ∈ V (V ∘ V -1 ( )). But V (V ∘ V -1 ( )) is V ∘ V(V -1 ( )). Hence ¯ ∈ (V -1 ( )). □
Note that Proposition 5.1 applies both to the finite and unrestricted cases.

We can now show the following.

Theorem 5.2 CQ is not complete for CQ-to-CQ rewriting. Remark 5.4 Note that Theorem 5.2 holds in the finite as well as the unrestricted case. This shows that Theorem 3.3 in [START_REF] Segoufin | Views and queries: determinacy and rewriting[END_REF], claiming that CQ is complete for CQ-to-CQ rewriting in the unrestricted case, is erroneous. Also, Theorem 3.7 in [START_REF] Segoufin | Views and queries: determinacy and rewriting[END_REF], claiming decidability of determinacy in the unrestricted case as a corollary, remains unproven. The source of the problem is Proposition 3.6 in [START_REF] Segoufin | Views and queries: determinacy and rewriting[END_REF], which is unfortunately false (the views and queries used in the above proof are a counterexample). Specifically, part [START_REF] Agrawal | Automated selection of materialized views and indexes Microsoft SQL Server[END_REF] of that proposition would imply that ( , ) ∈ (V -1 ( ))) for V and in the proof of Theorem 5.2, which is false.

As a consequence of the proof of Theorem 5.2 we have: where is the relation depicted in Figure 2. By construction, V( 1 ) ⊂ V( 2 ). However, ⟨ , ⟩ ∈ ( 1 ) but ⟨ , ⟩ / ∈ ( 2 ), so ( 1 ) ∕ ⊆ ( 2 ). Thus the mapping V is non-monotonic. □

Completeness for monotonic mappings

To show that CQ is not complete for CQ-to-CQ rewritings, we exhibited in the proof of Theorem 5.2 a set V of CQ views and a CQ query such that V↠ and V is non-monotonic. One might wonder if there are always CQ rewritings in the cases when V is monotonic. An affirmative answer is provided by the following result.

Theorem 5.6 Let V be a set of CQ views and a CQ query such that V↠ . If V is monotonic, then there exists a CQ rewriting of using V.

Proof: Let V be a set of CQ views and (¯ ) a CQ query (with free variables ¯ ) such that V↠ and V is monotonic. We use the notation of Proposition 5.1. Let 1 = [ ] be the database consisting of the body of , and

2 = V -1 (V([ ]). By construction, V( 1 ) ⊆ V( 2 ). Since V is monotonic, ( 1 ) ⊆ ( 2 ). Note that ¯ ∈ ( 1 ). It follows that ¯ ∈ ( 2 )
, so by (iii) of Proposition 5.1, V is a CQ rewriting of using V. □ respect to V. Since expanded with the view definition is an infinite union ∪ ≥0 of conjunctive queries over the input database and is a finite union of conjunctive queries over the same, it easily follows that is equivalent to a finite union of conjunctive queries among { | ≥ 0}, so can be rewritten as a finite union of conjunctive queries over V. Furthermore, if is in CQ then is equivalent to a single conjunctive query among { | ≥ 0}. Note that this provides an alternative proof to Theorem 5.6. Now consider (ii). The proof is an extension of that of Theorem 5.6. For readability, we sketch the proof for the case when V consists of a single UCQ view . Let We claim that defines . In other words, is equivalent to

∘ . Consider ⊆ ∘ . Let = ∃¯ ( ⋀ ¯ ∈ ( ¯ )) ∘ .
Clearly, it is enough to show that ⊆ for every , 1 ≤ ≤ . Let us fix such . Let Σ be the set of mappings from to {1, . . . , } such that ¯ ∈ ( ) ([ ]) for every ∈ . For each ∈ Σ , let (¯ ) be the CQ whose free variables are ¯ and whose frozen body is

[ ] = ∪ ¯ ∈ -1 ( ¯ ) ( ¯ ).
= [ ]. By construction, ( 1 ) = ([ ]) = ⊆ ( 2 ).
Since is monotonic, it follows that ( 1 ) ⊆ ( 2 ). However, ¯ ∈ ( 1 ), so ¯ ∈ ( 2 ) and there is , 1 ≤ ≤ , such that ¯ ∈ ( 2 ). Thus, there is a homomorphism from [ ] to [ ] fixing ¯ , and so ⊆ ⊆ . Since = ⋁ ∈Σ , it follows that ⊆ . □

Effective FO rewriting in the unrestricted case

As shown above, CQ is not complete for CQ-to-CQ rewriting. What is the rewriting power needed of a complete language? In the finite case, it is open whether FO is sufficient, and the best known upper bounds remain ∃SO and ∀SO. In the unrestricted case, we know from Theorem 3.1 that FO is complete for CQ-to-CQ rewriting. However, this does not necessarily guarantee effective rewritings. We next show that such effective FO rewritings do indeed exist for CQ-to-CQ rewritings. Recall that it is open whether finite and unrestricted determinacy coincide for CQ views and queries. First, we review a characterization of determinacy in the unrestricted case, based on the chase. Let V be a set of CQ views and (¯ ) a CQ over the same database schema . We construct two possibly infinite instances ∞ and ′ ∞ such that V( ∞ ) = V( ′ ∞ ) as follows. We first define inductively a sequence of instances { , , , ′ , ′ , ′ } ≥0 , constructed by a chase procedure. Specifically, , ′ are instances over the database schema , and , , ′ , ′ are instances over the view schema V . We will define ∞ = ∪ and ′ ∞ = ∪ ′ . For the basis,

0 = [ ], 0 = 0 = V([ ]), ′ 0 = ′ 0 = ∅, and ′ 0 = V -1 ( 0 ). Inductively, ′ +1 = V( ′ ), ′ +1 = ′ +1 - , +1 = ∪ V -1 ( ′ +1 ), +1 = V( +1 ), +1 = +1 -′ +1
, and ′ +1 = ′ ∪ V -1 ( +1 ) (recall that new witnesses are introduced at every application of V -1 ).

Referring to the proof of Theorem 5.2, note that the instance depicted in Figure 2 coincides with ′ 0 .

Example 5.10 We illustrate with a simple example the first steps in the chase construction. Consider a database schema consisting of a single binary relation . Consider the binary view ( , ) = ∃ ( , ) ∧ ( , ) ∧ ( , ). Consider the Boolean query defined by ∃ , ( , ) ∧ ( , ). We construct the first steps the chase, specifically 0 , 0 , ′ 0 , ′ 1 , 1 , 1 . Since all instances are binary, we represent them as directed graphs.

By definition, 0 = [ ] is the graph x y

Clearly, 0 = V( 0 ) is the same graph x y

We can now compute ′ 0 = V -1 ( 0 ) obtain the graph x y a b where a and b are distinct new variables.

Next, ′ 1 = V( ′ 0 ) is the graph x y a b Recall that ′ 1 = ′ 1 -0 and 1 = 0 ∪ V -1 ( ′ 1 )
. Thus, 1 is the graph It can be easily seen that the chase never terminates for this example, so ∞ and ′ ∞ are infinite instances. Although immaterial to the chase construction, note that { } ↠ . Indeed, is equivalent to ∃ ∃ ( ( , ) ∧ ( , )). □ We will use the following properties.

Proposition 5.11 Let ∞ and ′ ∞ be constructed as above. The following hold:

1. V( ∞ ) = V( ′ ∞ ).
2. There exist homomorphisms from ∞ into [ ] and from ′ ∞ into [ ] that are the identity on ([ ]). [START_REF] Abiteboul | Foundations of Databases[END_REF]. First, note that, by construction, ( ) ∩ ( ′ ) = ( ) (recall that = V( )). We show by induction the following.

For every pair of database instances

, ′ such that V( ) = V( ′ )
′ } ≥0 are non-decreasing, V( ∞ ) = ∪ ≥0 V( ) and V( ′ ∞ ) = ∪ ≥0 V( ′ ). We show that V( ) ⊆ V( ′ ). Recall that by definition V( ) is = ′ ∪ and that ′ is ′ -1 ∪ V -1 ( ). Because V is CQ, we have ′ ∪ V ∘ V -1 ( ) ⊆ V( ′ ). By ( ) of Proposition 5.1, ⊆ V ∘ V -1 ( ) and hence V( ) ⊆ V( ′ ). Similarly we can show that V( ′ ) ⊆ V( +1 ). It follows that V( ∞ ) = V( ′ ∞ ). Next, consider
( †) for each ≥ 0 exist homomorphisms ℎ from to [ ] and ℎ ′ from ′ to [ ] that agree their common domain ( ) and are the identity on ( ) ∩ ([ ]). Furthermore, ℎ +1 extends ℎ and ℎ ′ +1 extends ℎ ′ .

For = 0, 0 = [ ] and ′ 0 = V -1 (V([ ])) so ℎ 0 is the identity and ℎ ′ 0 extends ℎ 0 to the new witnesses in V -1 (V([ ])). In particular, ℎ 0 and ℎ ′ 0 agree on ( 0 ) ∩ ( ′ 0 ) = ( 0 ). Now let ≥ 0 and suppose ℎ and ℎ ′ have the desired properties for 0 ≤ ≤ . In particular, ℎ extends ℎ 0 , and since ℎ 0 is the identity on ([ ]), ℎ is also the identity on [ ]. We define ℎ +1 and ℎ ′ +1 as follows. Recall that ′ +1 = V( ′ ) -V( ) and +1 = ∪ V -1 ( ′ +1 ). By construction, there exists a homomorphism from V -1 ( ′ +1 ) to ′ that is the identity on ( ) ∪ ( ′ ) (since new witnesses are used in every application of V -1 ). It follows that

∘ ℎ ′ a homomorphism from V -1 ( ′ +1 ) to [ ] that agrees with ℎ on ( ) ∩ ( ′ ) so on ( ) ∩ (V -1 ( ′ +1
)). Let ℎ +1 be the union of ℎ and ∘ ℎ ′ (so in particular ℎ +1 extends ℎ ). Thus, ℎ +1 a homomorphism from +1 to [ ] that is the identity on ([ ]). Next, recall that ′ +1 = ′ ∪ V -1 ( +1 ), where +1 = V( +1 ) -V( ′ ). By definition, there is a homomorphism from V -1 ( +1 ) to +1 that is the identity on ( +1 ). It follows that

We are now ready to show that FO is complete for CQ-to-CQ rewriting in the unrestricted case, and that the FO rewriting can be effectively computed. Let V be a set of CQ views and (¯ ) be a CQ with free variables ¯ , both over database schema . Recall the sequence { , , , ′ , ′ , ′ } ≥0 defined above for each V and . For each finite instance over V , let be the conjunction of the literals ( ) such that ∈ V and ∈ ( ). Note that is simply true if = ∅. Let ≥ 0 be fixed. We define a sequence of formulas { } =0 by induction on , backward from . Let ¯ be the elements in adom( )adom( ′ ) if > 0 and in adom( 0 ) -{¯ } if = 0. For the basis, let

= ∃ ¯ . For 0 ≤ < let = ∃ ¯ [ ∧ ∀ ¯ ′ +1 ( ′ +1 → +1 )]
where ¯ are as above and ¯ ′ +1 are the elements in adom( ′ +1 )adom( ). We now show the following. Theorem 5.13 Let V be a set of CQ views and be a CQ, both over database schema . If

V ∞ ↠ , then there ≥ 0 such that ∞ ⇒ V 0 . Proof: Suppose V ∞ ↠ .
Let ¯ be the free variables of . By Proposition 5.12, there exists a homomorphism from [ ] into ′ ∞ fixing free variables ¯ of . Since ′ ∞ = ∪ ≥0 ′ , it follows that there exists ≥ 0 for which there is a homomorphism from [ ] to ′ fixing ¯ . Let be the minimum such . We claim that 0 is a rewriting of using V. We need to show that for every database instance , ( ) = 0 (V( )).

Consider ( ) ⊆ 0 (V( )). Let ¯ ∈ ( ) via some homomorphism ℎ. We show that ¯ ∈ 0 (V( )). To this end we construct below a tree of partial valuations of the variables in into , extending ℎ, such that for each ≥ 0:

1. each node at depth 2 is a valuation of the variables of which is a homomorphism from to such that V( ), |= ; in particular, provides a valuation for ¯ 2. each node at depth 2 + 1 is an extension ′ of its parent valuation to the variables of ′

+1

such that V( ), ′ |= ′ +1 ; in particular, ′ provides a valuation for ¯ ′ +1 3. the valuation at each node is consistent with the valuation at its parent node.

Note that the set of variables of 0 is included in the set of variables in . In particular, every valuation at level 2 provides values for all variables of 0 .

The tree is constructed inductively as follows.

• the root consists of ℎ; in particular, ℎ provides a valuation for the variables in ¯ 0 ∪ ¯ sending ¯ to ¯ . By definition, this valuation satisfies (1).

• consider a node at depth 2 consisting of a valuation for the variables in . Then, by construction of the tree of partial valuations ((2) and (3) above), has one child for each of its extensions ′ to the variables of ′ +1 such that V( ), ′ |= ′ +1 . By construction, (2) and (3) hold.

• consider a node at depth 2 +1 consisting of a valuation ′ . By construction of the tree of partial valuations, V( ), ′ |= ′ +1 , so there exists an extension of ′ mapping {V -1 (¯ ) | ¯ ∈ ′ +1 } into . By construction of +1 , is a homomorphism from +1 to and V( ), |= +1 .

Using the above tree of valuations, we can show that V( ), ℎ| ¯ |= 0 . Intuitively, each valuation at depth 2 has as children all its extensions to ¯ ′ +1 satisfying ′ 2 +1 , while each valuation at depth 2 + 1 has a single child inducing an extension to ¯ +1 . We show by reverse induction (from to 0) that the nodes at even levels 2 provide valuation for the existentially quantified variables ¯ of 0 , witnessing the fact that ¯ ∈ 0 (V( )). Let us denote by ¯ the formula ∧∀ ¯ ′ +1 ( ′ +1 → +1 ), that is without its existential quantification ∃ ¯ . Let = and be a valuation at level 2 . By construction of the tree of partial valuations, V( ), |= = ¯ . For the induction step, suppose that for every valuation at level 2( + 1), V( ), |= ¯ +1 . Consider a valuation at level 2 . We have that V( ), |= and for every extension ′ of to ′ +1 satisfying ′ +1 , there exists an extension of ′ to ¯ +1 such that V( ), |= ¯ +1 . In particular, V( ),

′ |= ∃ ¯ +1 ¯ +1 = +1 . Thus, V( ), |= ∧ ∀ ¯ ′ +1 ( ′ +1 → +1 ),
which completes the induction. Thus, for = 0, we have that V( ), ℎ| ( ¯ 0 ∪¯ ) |= ¯ 0 , so V( ), ℎ|¯ |= ∃ ¯ 0 ¯ 0 = 0 . In other words, ¯ ∈ 0 (V( )). Thus, ( ) ⊆ 0 (V( )). Now consider 0 (V( )) ⊆ ( ). Suppose ¯ ∈ 0 (V( )). We prove that there exists a homomorphism from ′ into mapping ¯ to ¯ . Since there is a homomorphism from [ ] to ′ fixing ¯ , this suffices to conclude.

We construct valuations ℎ the variables in ¯ and ′ -1 (for simplicity we assume that ′ -1 = ∅) into such that ℎ a homomorphism of ′ -1 into and V( ), ℎ |= . Note that for = 0, ℎ 0 simply maps ¯ to ¯ .

We shall use the following simple claim:

Claim 5.14 Let ℎ be a valuation of the variables in ¯ and ′ -1 that induces a homomorphism from ′ -1 into . Suppose there exists a valuation of the variables in , compatible with ℎ, such that V( ), |=

. Then there exists a valuation of the variables in ¯ and ′ , extending ℎ and inducing a homomorphism from ′ to .

Proof: By construction, ′ is obtained from ′ -1 by adding to it V -1 ( ). Because V( ), |= , ( ) ⊆ V( ). Thus, there is a homomorphism consistent with ℎ mapping V -1 ( ( )) to , and ℎ ∪ a homomorphism from ′ to extending ℎ. □

We now construct the valuations ℎ by induction, for 0 ≤ ≤ + 1 (ℎ +1 is the desired homomorphism from ′ into ). Specifically, for each we exhibit a valuation ℎ on the variables in ¯ and ′ -1 that induces a homomorphism from ′ -1 to and for which V( ), ℎ |= . For the basis, V( ), ℎ 0 |= 0 since ¯ ∈ 0 (V( )). For the inductive step, consider , 0 ≤ ≤ and suppose we have constructed ℎ such that V( ), ℎ |= and ℎ induces a homomorphism from ′ -1 to . Suppose first that = . Then, as = ∃ ¯ , there exists a valuation of ¯ , compatible with ℎ , such that V( ), |=

. By Claim 5.14 there exists an extension of ℎ to a homomorphism ℎ +1 from ′ to , as desired. Suppose now that < . Then, as there exists an FO rewriting of using V. However, this result is not constructive, as the interpolation theorem itself is not constructive. On the other hand, Theorem 5.13 provides a constructive algorithm to obtain the rewriting formula. Indeed, assume that V ∞ ↠ and V and are CQs. Then we know that there is a such that ¯ ∈ ( ′ ). Therefore, can be computed by generating successively the ′ until ¯ ∈ ( ′ ). Once we have , the formula 0 is easy to compute. Note that Theorem 5.13 works only for CQ views and queries, while the interpolation argument applies to all FO views and queries.

= ∃ ¯ ( ∧ ∀ ¯ ′ +1 ( ′ +1 → +1 )), it is possible to extend ℎ with a valuation of ¯ such that V( ), (ℎ ∪ ) |= [ ∧ ∀ ¯ ′ +1 ( ′ +1 → +1 )].

Well-Behaved Classes of CQ Views and Queries

We next consider restricted classes of views and queries for which CQ remains complete for rewriting. As a consequence, determinacy for these classes is decidable.

Monadic Views

We first consider the special case when the views are monadic. A monadic conjunctive query (MCQ) is a CQ with one free variable. We show the following.

Theorem 5.16 (i) CQ is complete for MCQ-to-CQ rewriting. (ii) Determinacy is decidable for MCQ views and CQ queries.

Note that (ii) is an immediate consequence of (i), in view of Proposition 5.1. Towards proving (i), we first note that it is enough to consider monadic queries. Indeed, we show that for MCQ views, determinacy of arbitrary CQ queries can be reduced to determinacy of MCQ queries. Proposition 5.17 Let V be a set of MCQ views and ( 1 , . . . , ) a CQ query with free variables 1 , . . . , , over the same database schema . Let ( ) be the MCQ with free variable , obtained by quantifying existentially in all for ∕ = .

(

i) if V↠ then is equivalent to ⋀ =1 ( ); (ii) if = ⋀ =1 ( ) then V↠ iff V↠ ( ) for 1 ≤ ≤ .
Proof: Consider (i). Suppose V↠ and consider [ ]. We show that for ∕ = , no tuple of [ ] containing is connected to a tuple of [ ] containing in the Gaifman graph (see [START_REF] Libkin | Elements of finite model theory[END_REF]) of [ ]. This clearly proves (i).

Consider instances and over defined as follows. Let consist of elements { 1 , . . . , }. Let = { ( , . . . , ) | ∈ , ∈ }, and let contain, for each ∈ of arity , the cross-product

We next proceed with Lemma 5.18. Note that the statement is slightly more general than we need, since we do not even assume that V↠ . Lemma 5.18 Let V be a set of MCQs over a database schema , an MCQ over the same schema , and let 0 and 0 be constructed as above. There exist finite instances and such that:

1. ֒→ 0 , 2. ֒→ 0 , and 3. V( ) = V( ).

Proof: As above, let = adom(V( 0 )). Recall that, by construction of 0 , there exists a homomorphism ℎ from 0 to 0 preserving . We begin with the following observations:

(i) every ∈ has the same type in V( 0 ) and V( 0 ), and

(ii) the maximal types realized in 0 and 0 are the same.

By construction, for every ∈ and ∈ V, ∈ ( 0 ) iff ∈ ( 0 ). Thus, (i) holds. For part (ii), we show that every type realized in 0 is included in a type ′ realized 0 , and every type ′ realized in 0 is included in a type realized in 0 . Suppose is a type realized in 0 . Let be such that ( 0 , ) = . By (i), since ∈ , ( 0 , ) = ( 0 , ). Thus, ⊆ ( 0 , ). Now let ′ be a type realized in 0 . Let ∈ adom(V( 0 )) be such that ( 0 , ) = ′ . Consider ℎ( ) ∈ adom(V( 0 )). Since ℎ a homomorphism from 0 to 0 , if ∈ ( 0 ) then ℎ( ) ∈ ( 0 ). Thus, ′ = ( 0 , ) ⊆ ( 0 , ℎ( )). This establishes (ii).

Next, for each type = ∅, let be the query ⋀ ∈ ( ), where is a fresh variable (here ( ) stands for the query over defining the -th view). For technical reasons, we enforce that the for distinct 's have disjoint domains. By slight abuse of notation, we use to denote both the query ⋀ ∈ ( ) and its frozen body, as needed. Clearly, if ⊆ ′ then → ′ . We construct and in three steps. Similarly, let 1 be the disjoint union of 0 with the same set of instances. Note that ( 1 , ) = ( 1 , ) = . This ensures that 1 and 1 realize the same set of types. Moreover, 1 ֒→ 0 and 1 ֒→ 0 , because 0 and 0 have the same maximal realized types (by (ii) above) so ֒→ 0 and ֒→ 0 for every realized in 0 or in 0 .

(b) Now consider an arbitrary instance and ∈ adom( ). We can construct ′ ⊇ such that adom( ′ )adom( ) = { ′ } as follows. Make every relation ′ ( ) contain all the tuples of ( ) together with the set of tuples ′ where ∈ ( ) and where every occurence of in has been replaced with ′ . It is easy to verify that every ∈ adom( ) has the same type in and ′ and that ′ has the same type in ′ as . Furthermore ′ ֒→ by the homomorphism which is the identity on and where ( ′ ) = . By repeatedly adding new elements to an instance in this way, we can increase #( , ) for any type realized in to whatever count we desire without changing the type of any other element. By an easy induction, it follows that we can construct 2 and 2 such that 2 ֒→ 1 ֒→ 0 and 2 ֒→ 1 ֒→ 0 and such that for all ⊆ [ ] we have #( , 2 ) = #( , 2 ). In particular, this means that V( 2 ) and V( 2 ) are isomorphic by an isomorphism that preserves . We assume that all new elements added in constructing 1 , 2 , 1 , and 2 are distinct.

(c) Let ¯ be the extension of the isomorphism obtained in (b) with the identity on adom( 2 )adom(V( 2)). Let = ¯ ( 2 ) and = 2 . Clearly, ֒→ 0 , ֒→ 0 and V( ) = V( ) as desired. □

We illustrate the constructions of Lemma 5.18 with an example Example 5.19 Let consist of a single binary relation so that instances over are directed graphs. Let 1 ( ) = ∃ ( , ) and 2 ( ) = ∃ ( , ). That is, 1 returns the set of all nodes with an outgoing edge and 2 returns the set of all nodes with an incoming edge. Consider the query ( ) = ( , ), which returns the set of all nodes with a self-loop. Then 0 = { ( , )}, 1 ( 0 ) = 2 ( 0 ) = { }, and 0 = { ( , ), ( , )}. The types {1}, {2} and {1, 2} are all realized in both 0 and 0 , whereas ∅ is not. Furthermore, {1} = { ( , )}, {2} = { ( , )} {1,2} = { ( , ), ( , )}, for some newly chosen , , , , , , . In step (a) of the construction, we obtain 1 and 1 by adding disjoint versions of {1} , {2} , {1,2} to 0 and 0 . This yields 1 = { ( , ), ( , ), ( , ), ( , ), ( , )} and 1 = { ( , ), ( , ), ( ′ , ′ ), ( ′ , ′ ), ( ′ , ′ ), ( ′ , ′ )}. The elements of type {1} in 1 are , , and in 1 they are , ′ , ′ , ′ . The elements of type {2} in 1 are , , and in 1 they are , ′ , ′ , ′ . The elements of type {1, 2} in 1 are { , } and in 1 they are { , ′ }. Notice that both 1 and 1 have two elements of type {1, 2}, but disagree on the counts of the types {1} and {2}. In step (b) of the construction, we therefore add to 1 an element of type {1} and an element of type {2} to obtain 2 . We set 2 = 1 and 2 = { ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )}.

Here we obtained ( , ) by replacing with in ( , ). Similarly, we obtained ( , ) by replacing with in ( , ). Now we define the isomorphism from V( 2 ) to V( 2 ) as follows:

′ ′ ′ ′ ′ ′ ′
As discussed in Remark 5.3, Foto Afrati recently considered in [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF] the case of multiple path views and a single path query, and showed that determinacy remains decidable in this case. Furthermore, if the views determine the query, an FO rewriting of the query in terms of the views exists and can be effectively computed. Remark 3.11, Maarten Marx provides in [START_REF] Marx | Queries determined by views: pack your views[END_REF] another well-behaved class of CQs with respect to determinacy and rewriting. The class is obtained by applying the packed condition used for FO to CQs, yielding Packed CQ (PCQ) (see Remark 3.11). The resulting fragment is a slight extension of the well-known acyclic CQs [START_REF] Gottlob | Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width[END_REF]. It is shown in [START_REF] Marx | Queries determined by views: pack your views[END_REF] that unrestricted and finite determinacy coincide for PCQs, both are decidable, and PCQ is complete for PCQ-to-PCQ rewriting. These results also extend to unions of PCQs.

Remark 5.23 As mentioned in

One View versus Multiple Views

So far we have discussed the case of multiple views and a single query. But is it essential to have multiple views? That is, can the problem of whether a set of CQ views determines a CQ query be reduced to the problem of whether a single CQ view determines a CQ query? It turns out that, in the unrestricted case (finite and infinite instances), the answer is yes. In the finite case the problem is still open.

Conclusion

The contribution of this paper is a systematic study of determinacy and its connection to rewriting for a variety of view and query languages ranging from FO to CQ. While the questions were settled for many languages, several interesting problems remain open.

From a practical point of view, the case of CQs is the most interesting, because this is the most widely used class of queries, and because, as shown by our negative results, even slight extensions lead to undecidability. For CQs, decidability of determinacy remains open in both the finite and unrestricted cases. In fact, it remains open whether unrestricted and finite determinacy coincide. Note that if the latter holds, this implies decidability of determinacy. Indeed, then determinacy would be r.e. (using the chase procedure) and co-r.e. (because failure of finite determinacy is witnessed by finite instances).

If it turns out that finite and infinite determinacy are distinct for CQs, then it may be the case that unrestricted determinacy is decidable, while finite determinacy is not. Also, we can obtain effective FO rewritings whenever V determines in the unrestricted case, while the best complete language in the finite case remains ∃SO ∩ ∀SO. Since unrestricted determinacy implies determinacy, an algorithm for testing unrestricted determinacy could be used in practice as a sound but incomplete algorithm for testing finite determinacy: all positive answers would imply finite determinacy, but the algorithm could return false negatives. When the algorithm accepts, we would also have a guaranteed FO rewriting. Thus, the unrestricted case may turn out to be of practical interest if finite determinacy is undecidable, or to obtain FO rewritings.

While we exhibited some classes of CQ views for which CQ remains complete as a rewriting language, we do not yet have a complete characterization of such well-behaved classes. Recall that even a slight increase in the power of the rewrite language, such as using UCQ or CQ ∕ = instead of CQ, does not help. Indeed, a consequence of Theorem 5.6 is the following: if CQ is not sufficient to rewrite in terms of V, then a non-monotonic language is needed for the rewriting.

For ℒ ∈ {CQ, CQ ∕ = , UCQ}, we know that ∃SO ∩ ∀SO is complete for ℒ-toℒ rewritings. It is of interest to know if there are less powerful languages that remain complete for such rewritings, such as FO or FO+LFP. This however remains open.

Determinacy and rewriting naturally lead to the following general problem (solved so far only for simple languages). Suppose ℛ is complete for -to-rewritings. Is there an algorithm that, given V ∈ and ∈ such that V↠ , produces ∈ ℛ such that ⇒ V ? For example, we know that FO is complete for FO-to-FO rewritings in the unrestricted case, but the rewritings cannot be effectively computed. In contrast, effective FO rewritings can be obtained for CQ-to-CQ rewritings in the unrestricted case (Theorem 5.13).

Finally, an interesting direction to be explored is instance-based determinacy and rewriting, where determinacy and rewriting are considered relative to a given view instance. Such results have been obtained for regular path queries in [START_REF] Calvanese | Lossless regular views[END_REF].

Figure 2 :

 2 Figure 2: The graph of V -1 ( ) (elements in adom( ) are in boldface).

Corollary 5 . 5

 55 No monotonic language is complete for CQ-to-CQ rewriting.Proof: Consider the set of CQ views V and the query used in the proof of Theorem 5.2. It was shown that V↠ Consider the database instances 1 = [ ] and 2 =

  is a CQ and ¯ are the free variables. Similarly, let (¯ ) = ⋁ =1 (¯ ) where each (¯ ) is a CQ and ¯ are the free variables. We use the notation developed in the proof of Proposition 5.1. Thus, for each we denote by [ ] the frozen body of and let = ([ ]). Let (¯ ) be the UCQ where ¯ contains all the bound variables of .

Finally, 1 = V( 1 )

 11 d, and e distinct new variables.

(a) Set 1

 1 to consist of the disjoint union of 0 with the set of instances { | is realized in 0 or 0 }.

  By Claim 5.14, ℎ can then be extended to a homomorphism ℎ +1 from ′ to . It remains to show that with this valuation +1 holds in V( ). By construction, ℎ +1 provides a valuation for all variables in ′ +1 , including ¯ ′ +1 . Furthermore, because by construction ′ +1 ⊆ V( ′ ), and ℎ +1 induces a homomorphism from ′ to , ℎ +1 ( ′ +1 ) ⊆ V( ), so V( ), ℎ +1 |= ′ +1 . We conclude that V( ), ℎ +1 |= +1 . This completes the induction. □ Remark 5.15 Recall that we earlier showed in Theorem 3.1, using Craig's Interpolation Theorem, that for any set V of FO views and FO query such that V

∞ ↠

For mappings and such that the image of is included in the domain of , the composition ∘ is the mapping defined by ∘ ( ) = ( ( )).

FO+LFP is FO extended with a least fixpoint operator, see[START_REF] Ebbinghaus | Finite Model Theory[END_REF]. For the definitions of Datalog variants, see[START_REF] Abiteboul | Foundations of Databases[END_REF].

( , ) ≡ ∃ [ 4 ( , ) ∧ ∀ ( 3 ( , ) → 4 ( , ))].

Acknowledgments.

The authors would like to thank Alin Deutsch and Sergey Melnik for useful discussions related to the material of this paper.

A ternary relation is monoidal if it is the graph of a monoidal function. That is, is the graph of a (i) complete (ii) function which is (iii) associative. We construct a view V which essentially checks that is monoidal.

In order to do this we check that This is encoded in the view V as follows. Let 1 ( , , ) be ( , , ), 2 be 1 ∨ 2 , 3 be 1 ∧ 2 , and, for each equation of the form = in the list above let be ( 1 ∧ ) ∨ ( 2 ∧ ). Let V consist of the queries 1 , 2 , 3 defining the views 1 , 2 , 3 and defining the view for each of the three equations above. We thus have: If 1 and 2 are such that V( 1 ) = V( 2 ) and exactly one of 1 , 2 is true in 1 and the other in 2 , then is monoidal. Indeed, for each equation above, ( 1 ) = ( 2) together with the assumption on 1 and 2 imply that satisfies . Note that ( ) guarantees that is total and onto, ( ) says that is a function, and ( ) ensures associativity. Thus is monoidal.

We now define , . Given and = { = }, with , occurring in , we set , ( , ) to ∃¯ ⋀

( 1 , 2 , 3 ) (in the formula all the variables are quantified except for and ). Let , ( , ) be

). We claim that V↠ , iff implies over all finite monoidal functions. Assume first that implies on all finite monoidal functions. Consider 1 and 2 such that

= adom( ) × adom( ). If 3 and 2 are false then , ( 1 ) = , ( 2 ) = ∅. In the remaining case exactly one of 1 , 2 is true in 1 and in 2 . If it is the same for 1 and 2 then we immediately have , ( 1 ) = , ( 2 ). Otherwise we have that 1 and 2 agree on (by 1 ) and is monoidal (by the remark above). Since implies on monoidal functions, , ( , ) ⇒ = . This yields , ( 1 ) = , ( 2 ). Assume now that V↠ , . Let be a monoidal graph. Consider the extension 1 of with 1 true and 2 false, and the extension 2 of with 1 false and 2 true. We have

and , ( , ) ⇒ = . Thus verifies implies .

In the above, equality is used explicitly in the formula for the view and query. Equality can be avoided as follows. A relation is said to be pseudo-monoidal if the equivalence relation defined by ≃ ′ iff ∃ , ( , , ) ∧ ( , , ′ ) is a congruence with respect to and / ≃ is a monoidal function.

The property that ≃ is a congruence with respect to can be enforced by the following equalities, ensuring that equivalent and ′ cannot be distinguished using :

Proof: We exhibit a set of CQ views V and a CQ such that V↠ but ¯ ∕ ∈ (V -1 ( )), where = V([ ]). By Proposition 5.1, this shows that has no CQ rewriting in terms of V.

Let the database schema consist of a single binary relation . Consider the set V consisting of the following three views (with corresponding graphical representations):

← → → → . We first show that V↠ . To do so, we prove that the formula

In other words, for each database over and , ∈ adom( ), ⟨ , ⟩ ∈ ( ) iff ( , ) holds on the instance ( ).

Suppose ⟨ , ⟩ ∈ ( ) via a homomorphism ℎ. Note that we have ⟨ , ⟩ ∈ 1 ([ ]), via a homomorphism ℎ ′ . It follows that ℎ∘ℎ ′ a homomorphism from [ 1 to mapping ⟨ , ⟩ to ⟨ , ℎ( )⟩. We let = ℎ( ) and from the above we have ⟨ , ⟩ ∈ 1 ( ). Now because there is an edge ⟨ , ⟩ in [ ] we have an edge ⟨ , ⟩ in . Therefore for every such that ⟨ , ⟩ ∈ 2 ( ), ⟨ , ⟩ ∈ 3 ( ). Thus, ( , ) holds on ( ). Conversely, suppose ( , ) holds on ( ). Then there exists such that ⟨ , ⟩ ∈ 1 ( ), so by definition of 1 there exist , such that ( , ) ∧ ( , ) ∧ ( , ) holds in . But then ⟨ , ⟩ ∈ 2 ( ) so by definition of , ⟨ , ⟩ ∈ 3 ( ). It follows that there exist ′ , ′ such that ( , ′ ) ∧ ( ′ , ′ ) ∧ ( ′ , ) holds in . This together with the fact that ( , ) holds in , implies that ⟨ , ⟩ ∈ ( ). Thus, ( , ) is a rewriting of using V, so V↠ . In view of Proposition 5.1, it remains to show that ⟨ , ⟩ ∕ ∈ (V -1 ( )), where

and V -1 ( ) is depicted in Figure 2.

It is easily checked that ⟨ , ⟩ does not belong to applied to the above instance. Thus, has no CQ rewriting in terms of V. □ Remark 5.3 A different and somewhat simpler proof of Theorem 5.2 has recently been exhibited in [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF].

It extends the technique in the above proof by providing an infinite set of examples of CQ views and queries for which the view determines the query but the query has no CQ rewriting in terms of the view. The examples involve path queries

( , ) on a binary relation stating that there is a path of length from to in ( > 1). For instance, it is shown that { 3 , 4 }↠ 5 but 5 has no CQ rewriting in terms of 3 and 4 . However, 5 has the FO rewriting Another way to look at Theorem 5.6 is as a kind of "gap theorem". Indeed, the theorem says that adding "small" features such as inequality, constants, or union to CQs does not increase its power as a language for CQ-to-CQ rewritings. Instead, in order to obtain any increase in rewriting power, one has to augment CQs all the way to a non-monotonic language.

A similar result can be obtained for some languages beyond CQs. Consider UCQs. Recall that no monotonic language can be complete for UCQ-to-UCQ rewriting, because, as in the case of CQs, there are UCQ views V and query such that V↠ and V is non-monotonic (see Proposition 4.2). A similar situation holds for CQ ∕ = views and CQ queries (see Proposition 4.3). It turns that the completeness result of Theorem 5.6 can be extended to these cases, as shown next. Theorem 5.7 (i) Let V ∈CQ ∕ = and ∈ (U)CQ. If V↠ and V is monotonic, then there exists ∈ (U)CQ such that ⇒ V . (ii) Let V ∈ UCQ and ∈ UCQ. If V↠ and V is monotonic, then there exists ∈ UCQ such that ⇒ V .

Proof: For proving part (i) we will make use of results of Abiteboul and Duschka [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF] on rewriting of certain answers to queries, in terms of sound views. For the sake of self containment, we briefly recall these results.

Let V be a set of views and a query over the same database schema. In the context of data integration, it is often of interest to consider sound views of a database with respect to V. An instance of V is a sound view of with respect to V iff ⊆ V( ). Given an instance over V that is a sound view of some database with respect to V, and a query , one is typically interested to compute the set of certain answers to with respect to V, defined as

∈ Datalog. We call an instance over V a sound view with respect to V iff ⊆ V( ) for some database instance . Note that, due to the presence of inequalities in V, not every instance over V is a sound view.

4.3 in [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF] states that the inequalities in V do not affect the certain answers to , so can be eliminated. More precisely: Lemma 5.8 (Theorem 4.3 in [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF]) Let V ∈CQ ∕ = and ∈ Datalog. Let V -be obtained from V by removing all inequalities. Then for every sound view with respect to V, ( ) with respect to V equals ( ) with respect to V -.

We next consider the rewriting question for certain answers and sound views. In this context, the question is to find a query over V such that ( ) = ( ) for every sound view with respect to V. We use again a result from [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF], that provides a rewriting of in terms of V when V ∈ and ∈ Datalog.

Lemma 5.9 (consequence of Theorem 4.2 in [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF]) Let V ∈ and ∈ Datalog. There exists a query ∈ Datalog, computable from V and , such that for every instance over V , ( ) = ( ) under the sound view semantics. Now consider V and as in ( ). Recall that

( ) for each in the image of V. Hence, for every database , ( ) = (V( )). Thus, it is enough to find a rewriting for . By Lemma 5.8, we can assume that V contains no inequalities. By Lemma 5.9, there exists a Datalog program over V that computes , so is also a rewriting of with

to [ ] that is the identity on [ ] and agrees with ℎ ′ on their common domain. Let ℎ ′ +1 be the union of ℎ ′ and ∘ ℎ +1 . In view of the above, ℎ ′ +1 is a homomorphism from ′ +1 to [ ] that agrees with ℎ +1 on ( +1 ) and is the identity on ( +1 ) ∩

([ ]). This completes the induction. By construction, ℎ +1 extends ℎ and ℎ ′ +1 extends ℎ ′ for every ≥ 0. This proves ( †).

To prove (2), let ℎ = ∪ ≥0 ℎ and ℎ ′ = ∪ ≥0 ℎ ′ . Since ℎ +1 extends ℎ and ℎ ′ +1 extends ℎ ′ for each ≥ 0, ℎ and ℎ ′ are well-defined homomorphisms from ∞ , resp. ′ ∞ , to [ ], that are the identity on

([ ]). Now consider [START_REF] Afrati | Rewriting Conjunctive Queries Determined by Views[END_REF]. Let , ′ be database instances as in the statement. We prove by induction the following.

( ‡) for each ≥ 0 there exist homomorphisms from to and ′ from ′ to ′ such that:

(i) 0 = , (ii) +1 extends and ′ +1 extends ′ , and (iii)

and ′ agree on ( ).

Clearly, ( ‡) suffices to prove (3). Indeed, let = ∪ ≥0 and ′ = ∪ ≥0 ′ . Due to ( ), and ′ are well defined homomorphisms from ∞ to , resp. ′ ∞ to ′ . From ( ) -( ) it then follows that ′ agrees with on every free variable of occurring in ′ ∞ (note that not all such free variables must occur in ′ ∞ , since we do not assume that V ∞ ↠ ). We now prove ( ‡). For the basis, let 0 = (thus, ( ) is satisfied). Clearly, ( 0 ) ⊆ V( ), so ( 0 ) ⊆ V( ′ ). Since ′ 0 = V -1 ( 0 ), it follows that there exists a homomorphism ′ 0 from ′ 0 to ′ that agrees with on ( 0 ). But = 0 , so ′ 0 agrees with 0 on ( 0 ). For the induction, suppose ≥ 0 and and ′ are constructed so that ( ), ( ) hold. Since

), there exists an extension +1 of such that +1 ( +1 ) ⊆ and +1 agrees with ′ on ( ′ +1 ). Since by the induction hypothesis and ′ agree on ( ), and +1 extends , it follows that +1 and ′ agree on

Since ′ +1 = ′ ∪V -1 ( +1 ), there exists an extension ′ +1 of ′ mapping ′ +1 to ′ and agreeing with +1 on ( +1 ). This in conjunction with the fact that +1 agrees with ′ on ( ′ +1 ) implies that +1 and ′ +1 agree on +1 . This completes the induction. □

As a consequence of the above we have the following.

Proposition 5.12 Let V be a set of CQ views and (¯ ) a CQ over the same database schema, where ¯ are the free variables of . Then

) is witnessed by ℎ. Let , ′ be database instances such that V( ) = V( ′ ). We have to show that ( ) = ( ′ ). By symmetry, it is enough to show that ( ) ⊆ ( ′ ). Let ¯ ∈ ( ). By (3) of Proposition 5.11, there exists a homomorphism ℎ ′ from ′ ∞ into ′ mapping ¯ to ¯ . The composition of ℎ and ℎ ′ a homomorphism from [ ] to ′ mapping ¯ to ¯ , and hence ¯ ∈ ( ′ ). □

. Clearly, V( ) = V( ) (all views return in both cases), so ( ) = ( ). But ( ) = , so ( ) =

. In particular, ⟨ 1 , . . . , ⟩ ∈ ( ). This is only possible if there is no path in the Gaifman graph of [ ] from a tuple containing to one containing for ∕ = . Part (ii) is obvious. □

In view of Proposition 5.17, to establish Theorem 5.16 it is enough to prove that CQ is complete for MCQ-to-MCQ rewriting. As a warm-up, let us consider first the case when V consists of a single view ( ), and the database schema is one binary relation. Let ( ) be an MCQ, and suppose that ↠ . We show that is equivalent to . Since is a query, ⊆ ( cannot introduce domain elements not in ). It remains to show that ⊆ . If ( ) ∕ = ∅ it follows by genericity of that ( ) ⊆ ( ); however, it is conceivable that

Clearly, ( ) = ( ). It follows that ( ) = ( ). Recall that is the free variable of , hence ∈ ([ ]) and ( , ) ∈ . Therefore ∈ ( ). But then ∈ ( ) = ([ ]), so there exists a homomorphism from [ ] to [ ] fixing . It follows that ⊆ , which completes the proof. Unfortunately, the above approach for single views does not easily extend to multiple monadic views. Indeed, suppose we have two views 1 , 2 . The stumbling block in extending the proof is the construction of two instances and such that 1 ( ) = 1 ( ) and 2 ( ) = 2 ( ), and forcing the existence of a homomorphism showing that can be rewritten using 1 , 2 . As we shall see, the multiple views case requires a more involved construction, which is used in Lemma 5.18 below.

We will need the following notions. For any instance , we define the type of ∈ adom( ) to be ( ,

A type is realizable if it is realized in some . A type is maximal if it is maximal under set inclusion among some set of types. We also denote by #( , ) the number of elements ∈ adom( ) for which ( , ) = .

Given two instances and ′ over the same schema, we write ′ → ′ if there is a homomorphism from ′ to . Suppose in addition that ⊆ ′ . We say that ′ retracts to , which we write ′ ֒→ if there is a homomorphism from ′ to fixing the domain of . We call such a homomorphism a retraction.

proof of Theorem 5.16 (i) is as follows. Let V a set of MCQ views and a CQ query with free variable , both over database schema , such that V↠ . We want to show that has a CQ rewriting in terms of V. By Proposition 5.17, we can assume wlog that is MCQ.

Set 0 = [ ] and 0 = V -1 (V([ ])). Let = adom(V( 0 )). Note that, by construction, ⊆ adom(V( 0 )). Also, note that ∈ . Indeed, suppose this is not the case. Let be a new element and let [ ] be the instance obtained from [ ] by replacing with . Then

We next prove Lemma 5.18 below, which allows us to conclude. Indeed, the lemma guarantees the existence of and such that ֒→ 0 , ֒→ 0 , and ( ) = ( ). Then

2. ∈ ( ) because 0 ⊆ , 3. ∈ ( ) because V↠ and ( ) = ( ), and therefore 4. ∈ ( 0 ) because ֒→ 0 (and recall that ∈ ( 0 )).

This implies that there is a homomorphism from to 0 preserving , as desired. In view of Proposition 5.1, this implies that has a CQ rewriting in terms of V, which concludes the proof of Theorem 5.16.

Note that 1 ( 2 ) = { , , , , , } and 2 ( 2 ) = { , , , , , } so adom( 2 )adom(V( 2)) = ∅. Thus, ¯ = and step (c) yields = ¯ ( 2 ) = { ( , ), ( ′ , ′ ), ( ′ , ′ ), ( ′ , ′ ), ( ′ , ′ ), ( , ), ( , )} while remains equal to 2 so = { ( , ), ( , ), ( ′ , ′ ), ( ′ , ′ ), ( ′ , ′ ), ( ′ , ′ )}.

This concludes the construction. Note that ֒→ 0 , ֒→ 0 , and V( ) = V( ) as desired. As an aside, note that V does not determine , since there is no homomorphism from to 0 . Indeed, determinacy is not required by the lemma and the construction does not assume it.

One might wonder if the nice behavior exhibited in Theorem 5.16 for monadic CQs extends to more powerful languages. Proposition 4.2 and Proposition 4.3 already settled this in the negative for UCQs and CQ ∕ = , by showing that V may be non-monotonic even for monadic views and query . Thus, the good behavior of CQs in the monadic case is lost with even small extensions to the language.

Single-path views We have seen above that CQ is complete for MCQ-to-CQ rewriting. Unfortunately, extending this result beyond monadic views is possible only in a very limited way. Recall the example used in the proof of Theorem 5.2. It shows that even very simple binary views render CQ incomplete. Indeed, the views used there are trees, and differ from simple paths by just a single edge. In this section we show that CQ is complete (and therefore determinacy is decidable) in the case where the database schema is a binary relation , and V consists of a single view

where ≥ 2, providing the nodes connected by a path of length . Note that the case where the view in a path of length 1 is trivial since then the view provides the entire database.

We show the following.

Theorem 5.20 Let be a CQ query over and ≥ 2. (i) If { }↠ then has a CQ rewriting in terms of . (ii) Given a CQ query , it is decidable whether { }↠ .

Proof: In view of (iv) of Proposition 5.1, the existence of a CQ rewriting is decidable, so (ii) follows from (i).

Consider (i). Let be a CQ and suppose { }↠ . We show that there is a CQ rewriting of using . To this end, we construct two finite instances and such that ( ) = ( ), consists of several disjoint copies of ′ 0 , and ¯ ∈ ( ). This implies that ¯ ∈ ( ′ 0 ) and (i) follows from Proposition 5.1. The construction of and is done using a careful modification of the chase procedure.

Consider the beginning of the chase sequence as defined in Section 5.1.

Lemma 5.21 Under the conditions of Theorem 5.20, 0 and ′ 1 have disjoint domains.

Proof: Suppose that ⟨ , ⟩ ∈ ( ′ 0 ) for some ∈ adom( 0 ) (the case when ∈ adom( 0 ) is similar). We show that cannot be in adom( ′ 0 )adom( 0 ). Since ⟨ , ⟩ ∈ ( ′ 0 ), there is a path of length from to in ′ 0 . Note that ′ 0 has no cycles of length less than . It follows that either = or ( , ) = . In the first case we are done. If ( , ) = and ∈ adom( 0 ), by construction of ′ 0 , can only be in adom( 0 ).

It is also useful to note the following. Lemma 5.26 Let V = { 1 , . . . , } be a set of CQs with disjoint sets of variables and a CQ such that

Proof: Recall the construction of ′ ∞ from V and . By Proposition 5.12,

Proof: Let V ′ be obtained by removing from V all views for which ([ ]) = ∅. Note first that V ′ ∕ = ∅. Indeed, otherwise V([ ]) = ∅. But we also have V(∅) = ∅, while ([ ]) ∕ = ∅ and (∅) = ∅. This is a contradiction with V ∞ ↠ . Thus,

↠ . Suppose first that ⊗V ′ ∞ ↠ . We show that V ′ ∞ ↠ . Let , be database instances such that V ′ ( ) = V ′ ( ). Clearly, ⊗V ′ ( ) = ⊗V ′ ( ). Since ⊗V ′ ∞ ↠ , it follows that ( ) = ( ). Thus, V ′ ∞ ↠ . Conversely, suppose V ′ ∞ ↠ and let , be database instances such that ⊗V ′ ( ) = ⊗V ′ ( ). If ⊗V ′ ( ) = ⊗V ′ ( ) ∕ = ∅ then by Lemma 5.25, V ′ ( ) = V ′ ( ). Since V ′ ∞ ↠ , it follows that ( ) = ( ). Finally, suppose ⊗V ′ ( ) = ⊗V ′ ( ) = ∅. Then there exist 1 , 2 ∈ V ′ such that 1 ( ) = ∅ and 2 ( ) = ∅. Since, by construction of V ′ , there a homomorphism from 1 and 2 to [ ], this implies that ⊆ 1 and ⊆ 2 and therefore ( ) = ( ) = ∅. Thus, ⊗V ′ ∞ ↠ . □ Remark 5. [START_REF] Lindell | The Logical Complexity of Queries on Unordered Graphs[END_REF] It remains open whether multiple CQ views can be replaced by single views in the case of finite determinacy. The difficulty is that Lemma 5.26 may no longer hold, since in the finite case it is not known whether views without a homomorphism into [ ] can be eliminated. However, is easy to show, similarly to the above, that if V is a set of CQ views such that every view in V has a homomorphism into [ ], then V↠ iff ⊗V↠ .