Nadime Francis

Asymptotic Determinacy of Path Queries using Union-of-Paths Views

We consider the view-based query determinacy problem over graph databases for queries defined as unions of path queries. These queries select pairs of nodes in a graph that are connected through a path whose length falls in a given set. A view specification is a set of such queries. We say that a view specification V determines a query Q if, for all databases D, the answers to V on D contain enough information to answer Q. Our main result states that, given a view V, there exists an explicit bound that depends on V such that we can decide the determinacy problem for all queries that ask for a path longer than this bound, and provide first-order rewritings for the queries that are determined. We call this notion asymptotic determinacy. As a corollary, we can also compute the set of almost all path queries that are determined by V.

Introduction

View determinacy is a static analysis problem on databases that consists in deciding whether a given set of initial queries, called a view, contains enough information to answer a new query, and this on all databases. Solving this problem has many applications, namely in query optimization and caching. Assume that querying the database is costly, but that answers to all previous queries are kept in cache. Then it is useful to know whether a new query can be answered using only cached information and without accessing the database. In that case, we are then interested in finding a rewriting, that is, a query that explicitly computes the desired information by querying only cached data. Query determinacy can also be stated as a security problem. Assume that views represent information that can be publicly accessed, but that the considered query contains private data that should not be disclosed. Then it should be ensured that the view does not determine the query, in other words that there exists no rewriting of the private queries using public data.

We consider this question over graph databases. Graph databases are relational databases in which all relations are binary. Equivalently, they can be seen as directed graphs whose edges carry a label from a finite alphabet. Such databases arise naturally in several scenarios, which include social networks, crime detection, biological data and the Semantic Web. For instance, in social networks, individual data such as name or phone number are represented as nodes, whereas relationships between members of the network are edges linking the corresponding nodes and labeled by the nature of the relationship. Thus, a person X is a friend of a person Y if there is an edge going from X to Y with the label friend.

Information contained in a graph database does not only lie in the content of the graph but also in its topology, that is, in how the different data nodes are connected to each other. Typical queries then ask about topological properties of the graph, namely the existence of edges, paths, and so on. In a social network, a user X could be interested in computing the transitive closure of the friend relation: she would like to retrieve all nodes Y such that there is a path going from X to Y using only the friend label.

The determinacy problem has been considered in various contexts (see [START_REF] Abiteboul | Complexity of answering queries using materialized views[END_REF], [START_REF] Alon | Answering queries using views[END_REF] among others). It was shown in [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF] that determinacy is decidable when queries and views are defined as path queries, that is, queries Q k that select pairs of nodes (x, y) such that there is a path from x to y whose length is a given integer k. For instance, it proves that the two views Q 3 and Q 4 determine the query Q 5 , which is not immediate to see.

The main contribution of our work is to extend this result by considering a broader class of views that allows disjunction. More precisely, we consider here unions of path queries. A union of path queries Q is a query that selects pairs of nodes in a graph that are connected through a path whose length falls in a given set. For instance, a query Q k, selects pairs of nodes that are linked either by a path of length k or a path of length . A typical case covered by our work is the following: views are Q 2 , Q 1,2 and Q 2,3 , and we will see that these views determine the query Q 5 . While most of our work can and should be understood in this setting, we also show how to extend it to cover arbitrary disjunctions, that is, unions of path queries whose associated sets are infinite.

In this paper, we show that, given a view V defined by unions of path queries, we can decide whether V determines a path query Q assuming Q is "big enough," that is, Q asks for the existence of a path longer than some n 0 that we can effectively compute from V. We call this notion asymptotic determinacy. Although n 0 is of exponential size, our decision procedure actually works in Π P 2 in the size of the queries that occur in the view. When it concludes that V determines Q, we also provide a first-order rewriting of Q using V. Otherwise, it produces a generic counter-example that shows that V does not determine Q. Our technique starts by reducing V to a much simpler view V which has many useful properties, including that some Q ∈ V is actually a path query Q c , for some integer c. This particular query is a key to our reasoning, as it allows us to reduce infinite structures to finite ones by computing modulo c. The finite number of small queries that we are not able to process are cases where both our criterion of determinacy and our generic counter-examples fail.

Related Work.

The determinacy problem has been considered in [START_REF] Calvanese | Lossless regular views[END_REF] for regular path queries, i.e. queries that select pairs of nodes that are connected through a path whose sequence of labels satisfies some regular expression. In [START_REF] Calvanese | Lossless regular views[END_REF], determinacy is known as losslessness under the exact views assumption. However, it is still unknown whether this property is decidable and what a good rewriting language could be. Note that, on a one-letter alphabet, regular path queries are actually weaker than infinite unions of path queries, and that finite unions of path queries are exactly regular path queries whose associated set is finite.

The determinacy problem has been solved in two specific cases. First, [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF] showed how to decide whether a path view determines a path query and provides first-order rewritings of the query using the view when it is the case. The work presented here can be seen as an extension of [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF], where we consider more expressive views, by allowing (possibly infinite) disjunction. In [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF], a simple criterion is given: the view determines the query if and only if the view image of a simple path satisfying the query is connected. We will see in Example 1 and Example 2 that this decision criterion no longer applies here, as the view images in these examples are connected, but the view does not determine the query.

Second, [START_REF] Francis | Datalog rewritings of regular path queries using views[END_REF] proved that regular path queries can always be rewritten as Datalog queries using regular path views, assuming monotone determinacy. Monotone determinacy is a stronger form of determinacy that is known to be decidable in this setting. It requires both determinacy and the fact that rewritings of the query using the view are monotone. Our work can be seen as an attempt to lift this monotonicity assumption, while still retaining some of the expressive power of regular path queries and views, such as disjunction and transitive closure. Of course, without assuming monotonicity there is no hope of finding a rewriting in Datalog, since it can only express monotone queries.

On the negative side, it was proved in [START_REF] Gogacz | The hunt for a red spider: Conjunctive query determinacy is undecidable[END_REF] that determinacy is undecidable for conjunctive queries and conjunctive views in the unrestricted case, that is, when the databases are allowed to be infinite. This work has later been expanded in [START_REF] Gogacz | Red spider meets a rainworm: Conjunctive query finite determinacy is undecidable[END_REF] to cover the standard case where databases are required to be finite, while maintaining the undecidability result. While conjunctive queries and views are not directly comparable to the languages that we consider, these results strongly hint at the fact that determinacy remains a difficult problem even in seemingly simple cases.

The simplest cases for which determinacy is undecidable and that contain path queries and union-of-paths views are provided by [START_REF] Francis | Datalog rewritings of regular path queries using views[END_REF]. There, it is shown that determinacy is undecidable for regular path queries, using either context-free path views or conjunctive regular path views. Admittedly, both settings offer considerably more expressive power than the query and view languages that we consider here, such as multiple labels in the alphabet, disjunctions in the query, and conjunctions in the view. However, to the best of our knowledge, there are no intermediate settings for which determinacy has been shown to be undecidable.

This paper is an extended version of [START_REF] Francis | Asymptotic determinacy of path queries using union-of-paths views[END_REF]. This extended version contains all the details of the proofs that were missing or merely sketched in the conference version. Additionally, Section 3 also covers an alternate and more intuitive statement of the asymptotic determinacy problem that was defined in [START_REF] Francis | Asymptotic determinacy of path queries using union-of-paths views[END_REF], and Section 5 discusses several possible extensions of this work, and the challenges that come with them.

Preliminaries Graph Databases.

A binary schema σ is a finite set of binary relational predicates. A graph database D over σ is a relational structure over a binary schema σ. Alternatively, it can also be seen as a directed edge-labeled graph whose labeling alphabet are symbols in σ. An element in the domain of D is called a node.

A path π in a database D from x 0 to x m is a finite sequence π = x 0 a 0 x 1 . . . x m-1 a m-1 x m , where each x i is a node of D, each a i is a symbol of σ, and for all i, a i (x i , x i+1 ) holds in D. Such a path is said to be simple if each node occurs at most once in π. We write π = x 0 . . . x m when the specific symbol of σ that holds for each pair (x i , x i+1 ) is irrelevant. The length of π, denoted by |π|, is the length of the word a 0 . . . a m-1 , in this case m. To denote the fact that π is a path from x 0 to x m , we will write x 0 π → x m . Similarly, we will sometimes use x k → y to say that there exists a path of length k going from x to y, when the sequence of symbols that occur along the path is irrelevant. By abuse of notation, we also consider π as a graph database that contains exactly the nodes x 0 , . . . , x m , and in which only a i (x i , x i+1 ) holds, for all i.

Queries.

A binary query Q over a schema σ is a mapping associating to each graph database D over σ a binary relation Q(D) over the domain of D. We consider the following two query languages.

A path query Q is defined by a single positive integer k. On a given database D, Q returns all the pairs of nodes (x, y) in D such that there exists a path in D from x to y of length k. In other words, Q(D) = {(x, y) ∈ D | ∃π, x π → y and |π| = k}. For ease of notation and consistency with what follows, we will write Q = {k}.

A union of path queries Q is defined by a finite set of positive integers {k 1 , k 2 , . . . , k n }, and returns all the pairs of nodes that are connected through a path whose length belongs to the set, i.e. Q(D) = {(x, y) ∈ D | ∃π, x π → y and |π| ∈ Q}. By abuse of notation, Q represents both the query and the associated set. Unions of path queries are a generalization of path queries, as any path query can be seen as a union of path queries whose associated set is of size 1.

Remark that these query languages cannot distinguish the specific labels that are used to build the required paths. The simplest way to compare them to other commonly used query languages is to assume that the schema σ on wich the databases are defined only contains a single predicate. In this case, path queries are conjunctive queries whose underlying graph is a directed path. Alternatively, they are also regular path queries whose associated language is a single word. Then, unions of path queries are simply unions of such queries, or regular path queries whose associated language is finite. If |σ| ≥ 2, then path queries are not strictly speaking conjunctive queries. Indeed, assume that σ = {a, b}, then the query Q = {2} selects all pairs of nodes (x, y) such that there exists a path π = xαzβy, with αβ ∈ {aa, bb, ab, ba}, which cannot be expressed as a conjunctive query. This means that path queries correspond to a very restricted form of disjunction. However, it is more natural to say that path queries are not directly evaluated on a graph database D, but on the underlying structure of D, which is an unlabeled graph. In this case, the first comparison applies.

Views.

Let σ and τ be two binary schemas. A view V from σ to τ is a set of binary queries over σ, one for each symbol in τ . Note that, since both σ and τ are finite, then V is also a finite set. Given a database D over σ, the view image of D, V(D), is defined as the database E over τ such that, for each b ∈ τ , the interpretation of b in E is precisely Q b (D), where Q b is the query in V associated with b. The nodes of E are exactly those that appear in one of those relations, also known as the active domain of E. See Figure 1 for an example of a database and its view image.

By abuse of notation, we will use the same symbol (typically V ) to denote both a symbol b ∈ τ and its associated query Q b ∈ V. Thus, it is the same to say that V (x, y) holds in V(D), or that (x, y) ∈ V (D). In other words, the interpretation of (the symbol) V in E = V(D), and the answers to (the query) V on D represent the same relation. Finally, for complexity purposes, we will use |V| to refer to the size of the set V, that is, the number of queries it contains, and V to refer to the sum of sizes of all queries that occur in V.

When a view is defined by queries that belong to a certain query language, we will informally extend the name of the query language to the view. For instance, a view defined by conjunctive queries will be called a conjunctive view, a view defined by path queries will be called a path view and a view defined by unions of path queries will be called a union-of-paths view.

Determinacy.

A formal definition of determinacy is given in [START_REF] Nash | Views and queries: Determinacy and rewriting[END_REF] as: Definition 1 (Determinacy). We say that a view V determines a query Q if:

∀D, D , V(D) = V(D ) ⇒ Q(D) = Q(D )
Intuitively, this means that a view V determines a query Q, which we write V Q, if, for all databases D, V(D) always contains enough information to answer Q on D. Moreover, we say that a query R is a rewriting of Q using

V if R(V(D)) = Q(D) for all D.
The determinacy problem is the problem of deciding, given a view V and a query Q, whether V Q. To the best of our knowledge, its decidability status is still open when Q is a conjunctive query and V a conjunctive view, and also when Q is a regular path query, and V a regular path view. Nonetheless, several cases have been considered and solved. The results in [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF] solve the problem when Q is a path query and V a path view. In [START_REF] Nash | Views and queries: Determinacy and rewriting[END_REF], this problem is considered for Q and V defined by conjunctive queries, and in [START_REF] Francis | Datalog rewritings of regular path queries using views[END_REF] for Q and V defined with regular path queries, both with the added restriction that V must determine Q in a monotone way, which means that a monotone rewriting of Q using V exists.

Here, we consider the determinacy problem for Q defined as a path query, and V defined as a set of unions of path queries. However, for each V, there exist a finite number of queries Q on which our technique does not work. Hence, we are actually solving a slightly weaker problem, that we call the α-asymptotic determinacy problem which allows, for each V, to exclude a finite number of queries Q. The excluded queries are those that ask for a path shorter than α(V), where α is a fixed function that maps each view to a natural number. Note that providing an answer or a rewriting in "almost all" cases is something that has already been considered in the same context, for instance in [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF]. We can now formally state the problem and our main result:

Problem : α-asymptotic determinacy Input :

A union-of-paths view V and a path query Q = {n}, with n > α(V) Question : Does V Q?

Theorem 1. There exists an explicit and computable function α for which the α-asymptotic determinacy problem is decidable. Moreover, when the view determines the query, the decision procedure effectively computes a first-order rewriting of the query using the view.

It will actually come from the proof that the specific α for which we can solve the problem grows exponentially in the size of the queries in V, as α(V) is in 2 O( V 4 ) . However, the decision procedure itself works with a much lower Π P 2 complexity.

Arithmetic Tools.

Some of the proofs in this work involve a lot of arithmetic reasoning. We present here the notations and properties that we use. We will make extensive use of Bezout's Identity, a fundamental arithmetic property stating that, for a given set of integer A = {n 1 , . . . , n k }, there exist integers a 1 , . . . , a k such that a 1 n 1 + . . . + a k n k = gcd(A). Moreover, it was proved in [START_REF] Bohdan | The complexity of greatest common divisor computations[END_REF] that these integers can be chosen so that |a i | ≤ max(|n 1 |, . . . , |n k |)/2, for all i. Remark also that if A contains both positive and negative numbers, then these integers can be chosen so that a i ≥ 0, for all i. We will refer to this as Bezout's Identity with positive coefficients. In this case, a naive way of producing such coefficients from those given by [START_REF] Bohdan | The complexity of greatest common divisor computations[END_REF] makes them to be of size at most |A| max(|n 1 |, . . . , |n k |) 2 , which will be sufficient for our analysis.

Additionally, for two binary relations R and S, we write R•S for {(x, z) | ∃y, R(x, y) and S(y, z)}. Let n be a positive integer, we also use R 1 = R, and

R n = R n-1 • R if n ≥ 2.
For two unions of path queries Q = {k 1 , . . . , k n } and P = { 1 , . . . , m }, we define Q • P = {k i + j | i ≤ n, j ≤ m}, and similarly define Q n . This notation is consistent with the fact that, for any database D, Q • P(D) = Q(D) • P(D). Remark that, when Q and P are path queries, then Q • P is also a path query, as is Q n .

Organization.

The rest of the paper investigates the determinacy problem for a path query Q using view V defined by unions of path queries. In Section 3, we start by providing some conditions on Q and V that are necessary for V to determine Q, which leads to a more intuitive statement of the asymptotic determinacy problem. Section 4 is dedicated to proving Theorem 1, which gives a procedure for deciding the determinacy problem for almost all path queries Q, as well as a first-order rewriting of Q using V for the queries that are determined. Finally, in Section 5, we discuss the issue that remains to be solved in order to decide determinacy for all queries, as well as possible extensions of this work.

Towards Asymptotic Determinacy

In this section and the next, we consider path queries and union-of-paths views. When we simply say "query" or "view", it is implied that they belong to those specific classes.

In Section 3.1, we provide a set of necessary conditions for a view V to determine a query Q. We then use these results in Section 3.2 to restate the asymptotic determinacy problem in a more intuitive way, which will justify its name.

First Results

Our first lemma states that a view V cannot possibly determine a query Q if V does not at least contain a path query. In other words, even though V is defined using unions of path queries, at least one of them cannot make use of the union.

Lemma 1. Assume that a view V and query Q are such that V Q. Then there exists C ∈ V such that |C| = 1.

Proof. Assume by contraposition that, for all V ∈ V, |V | > 1. Let Q = {n}. We build a database D over σ = {a} as follows:

• D contains n + 1 distinct nodes x 0 , . . . , x n .

• For all i < n, a(x i , x i+1 ) holds in D.

• For all i ≤ n and for all V ∈ V such that i ∈ V , we add to D a simple path π i,V from x 0 to

x i , such that

|π i,V | ∈ V -{i}. Such a path exists because |V | > 1.
We then construct another database D which is a copy of D except that a(x 0 , x 1 ) does not hold in D . It is then easy to check that V(D) = V(D ) and that Q(D) = Q(D ). In particular, (x 0 , x n ) ∈ Q(D) and (x 0 , x n ) / ∈ Q(D ). Hence V Q, which concludes the proof. This construction is illustrated in Figure 2.

x 0 x 1 x 2 x 3 x 4
Fig. 2: Illustration for the proof of Lemma 1, showing here that V = {2, 4} Q = {4}. Following the notations in the proof, the top path is π 2,V and the bottom path is π 4,V . Remark then that adding or removing the dashed edge does not change the view, but changes the query result.

In view of Lemma 1, we know that we can restrict our attention to views that contain a path query C. This allows us to state the following definition for such views:

Definition 2 (Complete view). Let V be a view and C ∈ V such that C = {c}. We say that V is C-complete if, for all i ∈ {0, . . . , c -1}, there exists V ∈ V and k ∈ V such that k ≡ i[c].
For our next necessary condition, we adapt the condition in [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF] which originally works as follows. Let Q = {n} be a path query and V be a path view, without unions. Consider a database D which consists of a simple path of length n: x 0 . . . x n . Let E = V(D), and let G be the underlying undirected graph of E, that is a graph whose set of nodes is exactly the set of nodes of E, and such that there is an undirected and unlabeled edge between two nodes x and y in G if and only if there is any edge going from x to y or from y to x in E. Then it was shown in [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF] that, if V Q, then x 0 and x n belong to the same connected component in G. We remark that this condition still holds when V is a union-of-paths view: Claim 1. Let V be a view and Q = {n}. Let π = x 0 . . . x n . If V Q then there is an undirected path from x 0 to x n in V(π).

This claim could quite easily be proved by looking at the construction given in [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF] and showing that it still applies when V contains unions. Instead, we give another simple argument: consider V to be the path view deduced from V by separating all the unions, that is, if V = {k 1 , . . . , k m } is a query in V, then V contains all the queries V i = {k i }. Then the result comes from applying the condition on V together with the two following remarks: first, if V Q, then V Q, as V yields strictly more information. Second, for any database D, V(D) and V (D) have the same connectedness properties.

This condition allows us to reduce any determinacy problem to an equivalent problem with the added hypothesis that the view is C-complete:

Lemma 2. Let V be a view and C ∈ V such that C = {c}. Let Q = {n}, and π = x 0 . . . x n .
Assume that there is a path from x 0 to x n in V(π). Then we can effectively compute a view

V with C ∈ V such that C = {c } and a query Q such that V is C -complete and V Q if and only if V Q .
Proof. Let V and Q be defined as in the statement of the lemma. Let U be the set of all numbers that appear in V, that is:

U = V ∈V u∈V {u} and d = gcd(U ). Assume d = 1. Then there exists u 1 , . . . , u k ∈ U such that u 1 + . . . + u k ≡ 1[c]. This means that there exists V 1 , . . . , V k ∈ V and v ∈ V = V 1 • . . . • V k such that v ≡ 1[c]. We define V as V = V ∪ c i=1 {V i } and Q = Q. It follows that V is C-complete. Indeed, for all k ∈ {0, . . . , c -1}, V k contains kv ≡ k[c]. Additionally, V
Q if and only if V Q, as all queries in V are also in V , and all queries in V can be written as compositions of queries in V.

Assume now that d = 1. Then d divides all the numbers in V. Additionally, we know that there exists a path from x 0 to x n in V(x 0 . . . x n ), which implies that d divides n as well. For each

V ∈ V, we define V = { u d | u ∈ V }. We then define V = {V | V ∈ V} and Q = { n d }. Claim 2. V Q if and only if V Q .
• Assume that V Q. Then there exists two databases D 1 and D 2 such that D 1 and D 2 agree on V but not on Q. We build two new databases D 1 and D 2 that are copies of D 1 and D 2 except that there is an edge between x and y in D i if and only if there is a path of length d from x to y in D i .

Let x and y be two nodes of D 1 such that (x, y) ∈ V (D 1 ) for some V ∈ V . Then there exists u ∈ V such that x and y are at distance u in D 1 . By construction, this means that x and y are at distance du in D 1 . Hence, (x, y) ∈ V (D 1 ). Then (x, y) ∈ V (D 2 ). Thus, there exists v ∈ V such that x and y are at distance v in D 2 . It follows that x and y are at distance v d in D 2 , and finally that (x, y) ∈ V (D 2 ). Hence D 1 and D 2 agree on V . A similar reasoning shows that D 1 and D 2 don't agree on Q , so that we can conclude that V Q .

• Assume that V Q . Then there exists two databases D 1 and D 2 such that D 1 and D 2 agree on V but not on Q . We build two new databases D 1 and D 2 as follows:

-For each node x of D i and each α ∈ {0, . . . , d -1}, (x, α) is a node of D i .

-For each x and each α < d -1, there is an edge from (x, α) to (x, α + 1).

-For each x, y such that there is an edge from x to y in D i , there is an edge from (x, d -1) to (y, 0) in D i .

Let (x, α) and (y, β) be two nodes of D 1 such that (x, α), (y, β) ∈ V (D 1 ) for some V ∈ V.

Then there exists u ∈ V such that (x, α) and (y, β) are at distance u in D 1 . Since u ∈ V , we have u ≡ 0[d], which implies that α = β. By construction, this implies that x and y are at distance u d in D 1 . Hence, (x, y) ∈ V (D 1 ). Then (x, y) ∈ V (D 2 ). Thus there exists v ∈ V such that x and y are at distance v in D 2 . By construction, this implies that (x, α) and (y, α) are at distance dv in D 2 , and thus (x, α), (y, α) ∈ V (D 2 ). Hence D 1 and D 2 agree on V. A similar reasoning shows that D 1 and D 2 don't agree on Q, so that we can conclude that V Q.

Finally, we get a new set of views V for which we can apply the first case of the proof and compute a new V that is C -complete.

The last lemma of this section shows that the set of queries determined by a view V which contains a path query C = {c} is closed under adding c. While perhaps obvious, this result is key to defining asymptotic determinacy, as will be explained in Section 3.2. Lemma 3. Let V be a view and C ∈ V such that C = {c}. Let Q = {n}, and assume that V Q. Then, for all positive integers k, V {n + kc}.

Proof. Let D and D be two databases such that V(D) = V(D ). Let Q 1 = {n+c}, and assume that there exists (x, y) in D, such that (x, y)

∈ Q 1 (D). Then, there exists z in D such that (x, z) ∈ Q(D) and (z, y) ∈ C(D). Since V Q, then x appears in V(D)
, and thus in V(D ). Similarly, since (z, y) ∈ C(D), then both z and y appear in both V(D) and V(D ). It remains to notice that (x, y)

∈ Q 1 (D ). Indeed, since V Q, then (x, z) ∈ Q(D )
, which implies that there exists a path of length n from x to z in D . Additionally, C(z, y) holds in V(D ) (because it also does in V(D)), which implies that there exists a path of length c from z to y in D . Altogether, these two paths combine to form a path of length n + c going from x to y in D , and conclude the proof that V Q 1 . It easily follows by induction that V Q k = {n + kc} for any positive integer k.

Asymptotic Determinacy

In this section, we show how to use the results of Section 3.1 to assess the situation from a slighty different perspective. Let V be a view defined by unions of path queries. Assume that, instead of being given a specific query Q for which we want to decide whether V Q, we want to compute the complete determinacy picture of V. In other words, we want to know all path queries Q such that V Q. We start by using Lemma 1. This allows us to say that, if V does not contain a path query C = {c}, then there is no path query Q such that V Q, which answers our question, as well as the asymptotic determinacy problem. Let us now assume that V does indeed contain a path query C = {c}. Consider a natural number o ∈ {0, . . . , c -1}. Then there are two cases for a query Q = {m} such that m ≡ o[c]:

• Case 1: V does not determine any query Q = {n} with n ≡ o[c].
In particular, this means that V Q, which answers our question for such queries.

• Case 2: There exists some query Q = {n} with n ≡ o[c] such that V Q. Let us assume, without loss of generality, that Q is actually the smallest such query. Then either m < n, in which case we can easily conclude that V Q, or m ≥ n, in which case Lemma 3 immediately proves that V Q. Thus the determinacy status for such queries is entirely determined by this specific n.

What this means is that, if we restrict our attention to big enough queries Q = {m} with m ≡ o[c], there are only two possibilities. Either none of them are determined by Q (Case 1), or all of them are (Case 2). Thus, deciding the determinacy status of big enough queries becomes much easier: it simply amounts to deciding, for each o ∈ {0, . . . , c -1}, if it behaves as in Case 1 or Case 2. This is what we call the asymptotic determinacy picture of V.

This gives a new perspective on the asymptotic determinacy problem: given a view V, we can first compute the asymptotic determinacy picture of V, and then compute a safety threshold α(V) that ensures that all queries Q that ask for paths longer than α(V) comply to this asymptotic determinacy picture. Then, given a query Q = {n} with n > α(V), it simply remains to check if n[c] is in Case 1 or Case 2, which determines whether V Q. Finally, by using Lemma 2, we can restrict our attention to C-complete views. Altogether, this discussion shows that Theorem 1 is a consequence of the following proposition: Proposition 1. Given a C-complete view V defined by unions of path queries, such that C ∈ V with C = {c} for some c ∈ N and a natural number o ∈ {0, . . . , c -1}, it is decidable in Π P 2 whether there exists a query Q = {n} such that n ≡ o[c] and V Q. If this is the case, such a query Q of size 2 O( V 4 ) and a first-order rewriting of Q with regards to V can be computed effectively.

Indeed, if V is C-complete, the specific α required by Theorem 1 can be defined as the function that, given V, computes a witness query for each o ∈ {0, . . . , c -1} as in Proposition 1, and then returns the size of the biggest one. If V is not C-complete, then Lemma 2 allows us to compute a C-complete view V for which the previous argument provides a suitable α . It then remains to define α(V) = kα (V ), where k is the gcd of all numbers that appear in V, as in the proof of Lemma 2. Then, given a query Q = {n}, with n ≥ α(V), we define Q = { n k } if k divides n, and apply Proposition 1 with V and Q , or conclude that V Q otherwise. Remark that, in order to produce the complete determinacy picture of V, and thus to solve the general determinacy problem, we would need to compute the smallest query that is determined by V for each o. We do not know how to solve this challenging task yet, and discuss it further in Section 5.1. The proof of Proposition 1 itself is the goal of Section 4.

Deciding Asymptotic Determinacy

This section is devoted to proving Proposition 1, and therefore Theorem 1. For the whole section, we fix a C-complete view V, with C = {c} ∈ V and a natural number o ∈ {0, . . . , c -1}, as in the statement of the proposition.

The proof is divided in three parts. In Section 4.1, we introduce a tool that describes the possible behaviors that can be observed through the view V. We use it to prove the propositions in Section 4.2 and Section 4.3. More precisely, Section 4.2 settles the case where no query Q = {n} with n ≡ o[c] is determined by V, and Section 4.3 builds an appropriate query Q when one does exist.

Behavior Graph

The goal of this section is to define a tool that will help us deal with the combinatorial complexity of trying to find a path of specific length in a database based on its view image. We now give a rough sketch of the idea behind this tool. Assume we want to prove that some database D contains a path π of length n by looking only at E = V(D). If D does indeed contain such a path, then the following properties must necessarily hold in E:

C1. E contains the n + 1 (not necessarily distinct) nodes of π, x 0 , . . . , x n .

C2. For each V ∈ V and u ∈ V , V (x i , x i+u ) holds in E for all i.

C3. For each x in E such that V (x, x i ) holds in E, there exists an appropriate value of k and j such that C k (x, x j ) holds in E. The values of k and j depend on the witness path that proves V (x, x i ), as shown in Figure 3.

x 0 x 1 x 2 x 3 x 4 x V implies x 0 x 1 x 2 x 3 x 4 x V C or x 0 x 1 x 2 x 3 x 4
x V C Fig. 3: Example of possible behaviors for a database (full) and its view (dashed), with C = {3} and V = {1, 2}. Assume we know the information represented in the top figure. Then, one of the two bottom pictures must hold. More generally, if C = {c} and V (x, x i ) holds in E, then C k (x, x j ) must also hold, with

j = i + (c -v[c]) and kc = v + (c -v[c]) for some v ∈ V .
If E = V(D) does not satisfy these properties, then we can safely conclude that D does not contain a path of length n going from x 0 to x n . Let us fix x 0 , . . . , x n and assume that E satisfies (C2) and (C3) for these fixed nodes. Our intention here is for these nodes to be the consecutive nodes of a path of length n going from x 0 to x n . Unfortunately, there are still many ways for E to satisfy (C2) and (C3) without D actually having a path of length n from x 0 to x n , let alone one that goes through all the x i 's in the right order.

Let µ be a path in D from some x i to some x j . We define the delay of this path as δ(µ) = |µ| -(j -i). The value δ(µ) caracterizes the difference between µ and the section of the path of length n going through the x i 's, that we expected to find in D. If µ is of the intended (j -i) length, then its delay will be zero. Otherwise δ(µ) can be positive, if µ is longer than expected, or negative, if µ is shorter than expected.

Let D be a database and E = V(D) such that E satisfies the necessary conditions above. For this D and E, we build a graph H D that represents the delays of the paths of D that are induced by the conditions (C1), (C2) and (C3) as follows:

• H D has n + 1 nodes that represent x 0 , . . . , x n , as in (C1). We simply note them 0, . . . , n.

• For all V ∈ V and u ∈ V , (C2) implies that V (x i , x i+u ) holds in E. Hence, there exists a path µ in D going from x i to x i+u of length v, for some v ∈ V . For each such µ:

-We represent it as an edge in

H D going from i to i + u of label δ(µ) = (v -u).
-For all u < v such that u ∈ V for some V ∈ V, we know that V (x, x i+u ) holds in E, where x is the node that occur at distance u before x i+u along µ. We apply (C3) as shown in Figure 4. This leads to a path µ in D from Assume that there is a path from node 0 to node n in H D whose sum of labels is 0. By composing all the paths in D that led to this path in H D , we can prove that there exists in D a path π from x 0 to x n such that δ(π) = 0. Hence, π is of length n, and we have actually found a path of length n from x 0 to x n in D.

x i to x i+u+(c-v [c]) such that δ(µ ) = (v -u) + (v -u ), for some v ∈ V . We similarly represent each such µ in H D . x i x i+u x i+u+q x v -u u V kc = v + q
Consider the case where this is true for all databases D, that is, for all databases D such that V(D) satisfies the necessary conditions, H D contains such a path. Then all these databases contain a path of length n from x 0 to x n . This means that the necessary conditions for the existence of a path of length n in D are also sufficient. Since these conditions can be checked by looking only at the view instance, it implies that V {n}. Unfortunately, the size of H D depends on the size of the target query. In order to have a representation that does not depend on n, we identify in H D all nodes i and j such that i ≡ j[c]. Note that this is consistent with the fact that such nodes were already linked by paths of delay 0 thanks to C ∈ V. This is exactly the idea behind choice graphs, that are formally defined below. While we do lose some information by doing this merging, these graphs are still rich enough to allow us to decide asymptotic determinacy, as we will see in the rest of the proof.

Definition 3 (Choice graph). Given a C-complete view V such that C ∈ V with C = {c}, we define H V as the set of all directed, edge-labeled graphs H such that:

1. H has c nodes, which we will simply note 0, 1, . . . , c -1.

2. The edges of H carry labels in {-2(m -1), . . . , 2(m -1)}, where m is the biggest element that appears in the views, that is m = max V ∈V max u∈V u.

3. For each i, j ∈ {0, . . . , c -1}, for each V ∈ V, for each u ∈ V such that u ≡ (j -i)[c], there exists v ∈ V such that:

• there is an edge in H from i to j labeled by v -u.

• for each V ∈ V, for each u ∈ V , there exist v ∈ V and an edge in

H from i to (j -v )[c] labeled by (v -u) + (v -u ).
Remark 1. For a given V, the number of nodes and edges of a graph H ∈ H V is bounded, thus H V is finite. Moreover all H ∈ H V are complete graphs, because V is C-complete.

Definition 4 (Weight). The weight of a path in a graph H is the sum of all labels along edges of the path. A path with no edge is of weight 0.

Definition 5 (Behavior graph). Given a C-complete view V such that C ∈ V with C = {c}, we define G V as the set of all directed, edge-labeled graphs G constructed as follows:

1. Pick H ∈ H V , and start with G = H. If G only contains cycles of positive weights or cycles of negative weights, skip Step 2 and Step 3. Otherwise, if G contains both cycles of positive and negative weights 1 :

2. Pick i, j ∈ {0, . . . , c -1} such that:

• There exists in G a path from i to j of weight (i -j)[c]. Let a be a minimal (in absolute value) weight of a path satisfying this property.

• For all a ≡ a[c], there exists i , j such that (j -i ) ≡ (j -i)[c], and there is no edge from i to j of label a .

Then, for all i , j such that (j -i ) ≡ (j -i)[c], add an edge from i to j of label a.

1 Please note that this definition differs slightly from the definition in [START_REF] Francis | Asymptotic determinacy of path queries using union-of-paths views[END_REF] in that we did not require in [START_REF] Francis | Asymptotic determinacy of path queries using union-of-paths views[END_REF] that G had both negative and positive cycles in order to proceed to Step 2. This minor difference does not actually change any of the proofs, as Lemma 6 did not make use of this part of the construction, and Lemma 9 already assumes that the graph contains cycles of both signs. It does however make the size analysis at the end of Section 4.1 (which was not featured in [START_REF] Francis | Asymptotic determinacy of path queries using union-of-paths views[END_REF]) easier.

Repeat

Step 2 until no more edges can be added.

Remark 2.

• Step 2 of the construction of G V can only be applied a finite number of times for each G, since it can be done at most once for each (i, j). Moreover, there is a finite number of choices at each step. Hence, G V is finite.

• As soon as there is a path from some i to some j of weight (i -j)[c], then there is a weight a ≡ (i -j)[c] such that all i , j that are at the same distance as i is from j are linked by an edge of this particular weight, provided that G contains cycles of both positive and negative weights.

Behavior graphs contain another necessary property of the existence of a path of length n that goes through the x i 's. Remark that a path π of delay i -j going from x i to x j is actually of length 0 modulo c. Hence π appears in E as a sequence of C edges. Then the reasoning shown in Figure 5 implies the existence of paths of identical delay from nodes x i-u to nodes x j+c-u for all u.

x k x C C C C
implies, for all u: All the intuitions presented in this section are made precise in Section 4.2 and Section 4.3, when this tool is actually used. Before moving on, we prove two lemmas that give upper bounds on the size of these graphs and the relevant paths they contain, which will be useful for the complexity analysis of the final algorithm.

x k x x k-u x +c-u C C C C C u c -u
Lemma 4. Let G be a weighted graph on nodes 0, . . . , c -1. Assume that there exists in G a path of weight d going from node i to node j. Then there exists in G a path of weight d going from node i to node j whose length is in O(c 4 m 4 d + c 6 m 5 ), where m is the weight of greatest absolute value that occurs in G.

Proof. Let π be a path of weight d going from i to j. By reordering the edges in π, we can assume that π has the following form:

i u 1 u 1 u 1 u 1 ρ 0 . . . θ 1,1 θ 1,2 θ 1,3 θ 1,k 1 u 2 u 2 u 2 u 2 ρ 1 . . . θ 2,1 θ 2,2 θ 2,3 θ 2,k 2 u 3 u 3 u 3 u 3 ρ 2 . . . θ 3,1 θ 3,2 θ 3,3 θ 3,k 3 ρ 3 . . . . . . u u u u ρ -1 . . . θ ,1 θ ,2 θ ,3 θ 3,k j ρ
In the picture above, i and j are the starting and ending points of the path. The u s 's are pairwise distinct nodes of G, among {0, . . . , c -1}. The paths θ s,k are simple cycles going from u s to u s , and the paths ρ s for s ∈ 1, . . . , -1 are simple paths going from u s to u s+1 . Finally ρ 0 and ρ l are simple paths linking respectively i to u 1 and u to j. This shape of path is achieved by selecting (arbitrarily) the position of each line of the picture (at an occurence of a new u i ) and then moving iteratively each simple cycle from u i to u i to its correct position in the path, until only simple cycles and paths remain. We also assume that all cycles θ s,k have non-zero weight, otherwise they can safely be removed without changing the weight of π.

Let ρ = ρ 0 • . . . • ρ . Since ≤ c and each ρ s is a simple path, then ρ is of length at most c(c + 1). Let W be the set of all weights in G, and let m = max w∈W (|w|). Let w ρ be the weight of ρ. Then -mc(c + 1) ≤ w ρ ≤ mc(c + 1).

Similarly, let w θ be the sum of the weights of all θ s,k cycles. Then

w θ + w ρ = d. Thus |w θ | ≤ |d| + |w ρ |.
Let Θ be the set of all weights of θ s,k cycles.

Case 1: Assume that Θ contains only positive or only negative integers. Then, there are at most |w θ | occurences of θ s,k cycles in π. Thus, the total length of π is bounded by c(c+1)+c|d|+mc 2 (c+1), which proves the claim.

Case 2: Assume that Θ contains both positive and negative integers. We know that gcd(Θ) divides w θ . Then, by applying Bezout's Identity with positive coefficients, we build a sequence of integers from Θ whose sum is w θ and whose length is at most |w θ ||Θ| 2 max(Θ) 2 , which is bounded by 4(|d| + mc(c + 1))(mc) 4 . We deduce from this sequence a new path µ from i to j of weight d by inserting each cycle from Θ used in the sequence at the correct position in ρ. Thus µ is of size at most 4(|d| + mc(c + 1))(mc) 4 + c(c + 1), which ends the proof of the lemma.

Lemma 5. Let G be a behavior graph in G V . Then G is of size at most O( V 4 ).
Proof. Let G be a graph in G V . Then there exists a graph H in H V from which G is built, using Definition 5. Now remark that by definition H has c nodes and at most 4mc 2 edges, where m is the biggest element that appears in any query in V, and with each edge carrying a weight of size at most 4m. If H only contains positive or negative cycles, then there is nothing else to prove, as G is then of size O( V 4 ).

Otherwise, it remains to consider the number of edges and size of the weights added by Step 2 of Definition 5. First, we notice that Step 2 adds at most c 2 edges, that is, no more than one for each pair of nodes of the graph. Next, we prove that the new weights are bounded in size. Indeed, since there exists at least a cycle of negative weight and a cycle of positive weight, we can deduce that all nodes have a cycle of positive weight and a cycle of negative weight, since H is a complete graph. Similarly, we can assume that each node has a positive cycle of weight at most 3u and a negative cycle of weight at least -3u, where u is the largest absolute value that appears in H. Indeed, as soon as a path's weight becomes larger than u or smaller than -u, any edge that returns to its starting point will turn it into a cycle of weight bounded by -3u and 3u. Finally, these cycles can be used to make sure that no added weight at Step 2 of Definition 5 can be less than -3cu or bigger than 3cu. All in all, Step 2 of the definition adds at most c 2 which carry weights whose size vary in a range of 6cu = 12cm. Thus, the added structure is of size O( V 4 ), which ends the proof of the lemma.

In Section 4.2, we show that, if there exists some behavior graph G such that there is no path of weight 0 from 0 to o in G, then we can build two databases that agree on the view but not on paths of length n ≡ o[c], for all n. In other words, we can build a database whose view satisfies all the necessary conditions for the existence of a path of length n, while still maintaining a non-zero delay between the relevant nodes. On the contrary, in Section 4.3, we show that, if for all behavior graphs G, there is a path of weight 0 from 0 to o in G, then it is enough to satisfy the necessary conditions in order to have a path of length n.

In Section 4.4, we give a precise proof of how our decision algorithm uses the properties of behaviour graphs. The proof can be outlined as follows. For a given C-complete view V and a given natural number o ∈ {0, . . . , c -1}, we are simply looking for the occurrence of a specific graph G ∈ G V , namely one that does not contain a path of weight 0 from node 0 to node o. If we do find one such G, then, for all n ≡ o[c], V {n}. Otherwise, V {n} for some n ≡ o[c]. We do not actually need to compute G V : we simply guess the appropriate graph G and check that it does contain the critical path. Since G is of size polynomial in V and the considered path, if it exists, can be assumed to be polynomial in the size of G, our decision algorithm works in PSpace, more precisely in Π P 2 .

Negative Direction: Building Counter-examples

In this section, we solve the negative case of Proposition 1 by proving the following proposition:

Proposition 2. Assume that there exists G ∈ G V such that there is no path of weight 0 from 0 to o. Then, for all n ≡ o[c], V {n}.

The proof of Proposition 2 is split across Lemma 6 and Lemma 9. The canonical counterexamples that we build in order to prove that V {n} depend on whether G only contains cycles of positive or negative weights, or if it actually has both. These two cases are respectively dealt with in Lemma 6 and Lemma 9, and Example 1 and Example 2 give examples of both situations.

Example 1. Let V = {C, V }, C = {2} and V = {1, 2}. Figure 6 represents one of the graphs in G V , that additionally satisfies the condition of Lemma 6. Namely, there is no path of weight 0 from 0 to 1, and 0 only has non-negative cycles.

Example 2. Let V = {C, V }, C = {3} and V = {1, 5}. Figure 7 represents one of the graphs in G V , that additionally satisfies the condition of Lemma 9. Namely, there is no path of weight 0 from 0 to 1, and 0 has positive and negative cycles. Since each u i belongs to M , then each u i is the maximal element of some V i ∈ V. Then, by construction of G, there exists a path from 0 to o whose weight is of the form (v 1 -u 1 ) + (v 2u 2 ) + . . . + (v k -u k ) where each v i is an element of V i . Hence, all terms of the sum are negative or zero. If all are zero, then there is a path of weight zero from 0 to o. Otherwise, there is a path of negative weight from 0 to o, and by applying the same reasoning from o to 0, we get a cycle of negative weight from 0 to 0. Both these cases are false by assumption, which proves the claim.

For each V i ∈ V , let u i be the maximal element of V i . By construction of d, we know that d divides u i . Let n be any natural number such that n ≡ o[c]. We can now construct a database D as follows:

• D contains two simple paths of length n, whose respective nodes are x 0 , . . . , x n and x 0 , . . . , x n .

• For each s, t ≤ n such that t -s ∈ V i for some i, and d does not divide t -s, we add to D a new path π i s,t of length u i -2, and we connect x s and x s to its initial node, and we connect its final node to x t and x t .

We then construct D , a copy of D, in which x j and x j switch roles for each j o [d]. Note that, since d does not divide o, this means that x 0 and x 0 are not switched, but n and x n are. See Figure 8 for an example of the construction. Claim 4. D and D agree on V, but each path from x 0 to x n in D is strictly longer than n. Hence D and D disagree on Q = {n}.

Let (x, y) ∈ V i (D) for some V i ∈ V. If either x or y belongs to one of the new paths of the form π j s,t , then the symmetry of the construction between the two original simple paths show that (x, y) ∈ V i (D ). Otherwise x = x s or x = x s and y = x t or y = x t , for some s and t. Then either t -s ≡ 0[d], in which case either both x and y are switched with their copy in D , or none are. Then, once again the symmetry of the construction concludes that (x, y) ∈ V i (D ). Otherwise, d does not divide t -s, which implies that (x, y) are linked by π i s,t in V i , and thus that (x, y) ∈ V i (D ). Hence, V(D) = V(D ). Remark now how each path from x 0 to x n in D has to cross one of the π j s,t , which is longer than t -s. It follows that each path from x 0 to x n in D is longer than n, which proves the claim.

It easily follows from this claim that V {n}. The case where 0 only has cycles of negative or zero weight is dealt with in a very similar way, which concludes the proof of the lemma. Remark how the left and right databases agree on V, while there exists a path of length 5 going from x 0 to x 5 in the left database, but no such path in the right one.

x 0 x 1 x 2 x 3 x 4 x 5 x 0 x 1 x 2 x 3 x 4 x 5 x 0 x 1 x 2 x 3 x 4 x 5 x 0 x 1 x 2 x 3 x 4 x 5
We now move on to the proof of Lemma 9. Note that this proof is a little more involved and mainly relies on the arithmetic properties of behavior graphs, that are given in Lemma 7: Lemma 7. Let G ∈ G V such that 0 has both cycles of positive and negative weight. Let W be the set of all weights of cycles of 0 in G, and let d = gcd(W ). Then G has the following properties:

1. For all i, j ∈ {0, . . . , c -1} all paths from i to j have the same weight modulo d. We denote this value by w(i, j). Moreover, w(i, j) is compatible with composition. Namely:

• w(i, i) ≡ 0[d] • For all k, w(i, k) + w(k, j) ≡ w(i, j)[d] • w(i, j) ≡ -w(j, i)[d] 2. For all 0 ≤ i < j < c ∧ d, w(i, j) ≡ i -j[c ∧ d],
where c ∧ d denotes gcd(c, d).

3. For all i ∈ {0, . . . , c -1}, w(i, i

+ c ∧ d) ≡ 0[d].
Proof.

1. By construction of d, we already know that all cycles of 0 have weight 0 [d]. Let i, j ∈ {0, . . . , c -1}. Let π 1 and π 1 be two paths from i to j of respective weights w 1 and w 1 . Let π 0 be a path from 0 to i of weight w 0 and π 2 be a path from j to 0 of weight w 2 . Then both π 0 • π 1 • π 2 and π 0 • π 1 • π 2 are cycles of 0. Hence, we have w 0 + w 1 + w 2 ≡ 0[d] and

w 0 + w 1 + w 2 ≡ 0[d], which implies w 1 ≡ w 1 [d],
so that w(i, j) is correctly defined, as in the statement of the lemma.

The other properties are easy consequences of this fact.

2. To prove this property, we make use of the following claim: Claim 5. For all i ∈ {0, . . . , c -1}, for all natural number k, there exists j ∈ {0, . . . , c -1} such that w(i, j)

≡ -j + k[c ∧ d].
Proof of claim. Let i ∈ {0, . . . , c -1}, let k be any natural number. Since V is complete, there exists V, V ∈ V such that there exists u ∈ V and u ∈ V with u ≡ 1[c] and

u ≡ i -k[c].
Then, Property 3 of Definition 3 with i -1, i, u and u gives v ∈ V and v ∈ V such that:

• w(i -1, i) ≡ (v -u)[d] • w(i -1, i -v ) ≡ (v -u) + (v -u )[d]
Then it follows that:

w(i -1, i -v ) ≡ (v -u) + (v -u )[c ∧ d] w(i -1, i -v ) ≡ (v -u) + (v -i + k)[c ∧ d] w(i -1, i) + w(i, i -v ) ≡ (v -u) + (v -i + k)[c ∧ d] (v -u) + w(i, i -v ) ≡ (v -u) + (v -i + k)[c ∧ d] w(i, i -v ) ≡ (v -i) + k[c ∧ d]
and we conclude the proof of the claim by renaming v -i to j.

We can now move on to the proof of the property. Assume by contradiction that there exists i, j such that w(i, j

) ≡ i -j[c ∧ d].
Then w(i, j) ≡ i -j + kd[c] for some k. Since gcd(W ) = d and W contains both positive and negative elements, by using Bezout's Identity with positive coefficients, we show that there exists a cycle of i of weight -kd. Hence, there exists a path from i to j of weight i -j[c]. Since this path satisfies the requirement in Definition 5, we can show that for all r ∈ {0, . . . , c -1}, w(r, r

+ (j -i)) ≡ i -j[c ∧ d].
This is a contradiction with the claim. Indeed, the claim implies that for all k, there exists l such that w(0, l)

≡ -l + k[c ∧ d]. Since, k can take c ∧ d different values, but j -i < c ∧ d, this
means that we can find two values k = k for which the claim produces l and l that are in the same class modulo j -i. More precisely, we have w(0, l) ≡ -l+k[c∧d], w(0, l ) ≡ -l +k [c∧d], and l ≡ l [j -i]. Hence, there exists some α such that l = l + α(j -i). By using what we just proved above α times, we get w(l, l

) ≡ α(i -j)[c ∧ d]. Hence, w(l, l ) ≡ l -l [c ∧ d].
Thus, we have:

w(0, l) ≡ -l + k[c ∧ d] w(0, l) + w(l, l ) ≡ w(l, l ) -l + k[c ∧ d] w(0, l ) ≡ l -l -l + k[c ∧ d] w(0, l ) ≡ -l + k[c ∧ d]
This final equality implies that k = k , which is a contradiction. The proof of Lemma 7 uses the following arithmetical result: Lemma 8. Let d ∈ N, and a 1 , . . . , a k ∈ {0, . . . , d-1}. Assume that for all i, j, a i +a i+1 +. . .

+a j ≡ i -j -1[d].
Then there are at most d -k -1 possible values for a k+1 such that the sequence a 1 , . . . , a k+1 also satisfies this property. In particular, if k = d -1, then there are no possible continuations.

Proof. Assume everything defined as in the statement of the lemma. We define F as:

F = {a ∈ {0, . . . , d -1} | ∃i, a i + . . . + a k + a ≡ i -k -2[d]} ∪ {d -1}
We refer to F as the set of forbidden values for a k+1 in the sense that if a k+1 ∈ F , then the resulting sequence a 1 , . . . , a k+1 does not satisfy the property of the lemma. In the same way, we say that an integer i ∈ {1, . . . , k} forbids a value a when a i + . . .

+ a k + a ≡ i -k -2[d].
In other words, a is the element of that is obtained for the quantification i in the definition of F . Remark that d -1 belongs to F , as it is always a forbidden value2 regardless of the remainder of the sequence.

We conclude the proof now by showing that |F | = k + 1, which reduces the set of possible values for a k+1 to at most d -k -1. This comes from two facts: (1) no i ∈ {1, . . . , k} forbids d -1 and (2) for all i, j, if i = j, then i and j forbid two distinct values. We now prove the two facts:

1. Assume that there exists i ∈ {1, . . . , k} such that i forbids d -1. Then a i + . . .

+ a k -1 ≡ i -k -2[d]. Hence, a i + . . . + a k ≡ i -k -1[d],
which is a contradiction.

2. Assume that there exists j > i such that i and j forbid the same value a. Then

a j + . . . + a k + a ≡ j -k -2[d] Then a ≡ j -k -2 -a j -. . . -a k [d]
But we also have

a i + . . . + a k + a ≡ i -k -2[d] Hence a i + . . . + a j-1 + j -k -2 ≡ i -k -2[d] Finally a i + . . . + a j-1 ≡ i -j[d]
which is a contradiction.

We are now ready to give the full proof of Lemma 9:

Lemma 9. Assume that there exists G ∈ G V such that 0 has both cycles of positive and negative weight, and that there is no path of weight 0 from 0 to o. Then, for all n ≡ o[c], V {n}.

Proof. Let G ∈ G V be defined as in the statement of the lemma. An example of such a case is given in Example 2. We also define d as in Lemma 7.

Let f be the function defined as follows:

∀i ∈ {0, . . . , c ∧ d -1}, f (i) = i + w(0, i)[d]
Remark that f is one-to-one. Indeed, assume that i, j are such that f (i) = f (j). Then :

i + w(0, i) ≡ j + w(0, j)[d] w(0, i) -w(0, j) ≡ j -i[d]
And by using Property 1 of Lemma 7 we get:

w(j, i) ≡ j -i[d]
This final equation implies that i = j. Otherwise, this would be a contradiction with Property 2 of Lemma 7. We can then define g as:

∀i ∈ {0, . . . , d -1}, g(i) = i + w(0, i)[d]
Property 3 of Lemma 7 then gives us:

∀i ∈ {0, . . . , d -1}, g(i) = i + w(0, i[c ∧ d])[d]
Remark now that g can also be written:

∀i ∈ {0, . . . , d -1}, g(i) = f (i[c ∧ d]) + (i -(i[c ∧ d]))[d]
from which we deduce that g is one-to-one, because f is. Thus g is a permutation of {0, . . . , d -1}.

We can now define two databases D and D such that D is a cycle of length d whose nodes are x 0 , . . . , x d-1 , and D is a copy of D in which x i is replaced by x g(i) for all i. This is well defined and also a cycle of length d because g is a permutation. See Figure 9 for an example of this construction. Claim 6. D and D agree on V.

Let x i and x j be two nodes of D such that (x i , x j ) ∈ V (D) for some V ∈ V. Then there exists u such that u ∈ V and j -i ≡ u[d]. Let γ be the length of any path from x i to x j in D . Then we have:

γ ≡ g -1 (j) -g -1 (i)[d] γ ≡ (j -w(0, j)) -(i -w(0, i))[d] γ ≡ (j -i) -(w(0, j) -w(0, i))[d] γ ≡ u -w(i, j)[d] By definition of G, there exists v ∈ V such that v -u ≡ w(i, j)[d]. Hence, we have γ ≡ v[d].
This means that there is a path from x i to x j in D of length v, and thus (x i , x j ) ∈ V (D ). A similar reasoning proves the other direction, and concludes the proof of the claim.

Claim 7. For all n ≡ o[c], g(n) ≡ n[d]. Assume that g(n) ≡ n[d]. Then w(0, n) ≡ 0[d]. Hence, Property 3 of Lemma 7 implies that w(0, o) ≡ 0[d].
Hence there exists a path in G from 0 to o of weight kd for some k. Since d is the gcd of all cycles of 0, Bezout's Identity implies that there exists a path from 0 to 0 of weight -kd. Hence there exists a path from 0 to o of weight 0, which is a contradiction.

It easily follows from the claim that, for all n ≡ 0[c], V {n}. Indeed, the only path of length n starting from x 0 ends in x n in D, whereas it ends in x g(n) in D . This concludes the proof of the lemma.

Positive Direction: Computing a Rewriting

In this section, we solve the positive case of Proposition 1. We start by giving a simple example that shows some of the features of the rewritings that will be used to prove Proposition 3.

Example 3. In this example, we work with:

• V = {C, V 1 , V 2 } • C = {2} • V 1 = {1, 2} • V 2 = {2, 3} • Q = {5}
We show that V Q. Indeed, the following formula R is a rewriting of Q using V.

R(x, y) = ∃x 0 , . . . , x 5 , x 0 = x∧x 5 = y ∧CQ π5 (x 0 , . . . ,

x 5 )∧ ∀z, V 1 (z, x 3 ) ⇒ (C(z, x 3 )∨C(z, x 4 ))
where π 5 is a simple path whose nodes are x 0 , . . . , x 5 and CQ π5 is the conjunctive query that states all the atoms that hold in V(π 5 ), as follows:

CQ π5 (x 0 , . . . , x 5 ) = 0≤i≤4 V 1 (x i , x i+1 ) ∧ 0≤i≤2 V 2 (x i , x i+3 ) 0≤i≤3 V 1 (x i , x i+2 ) ∧ V 2 (x i , x i+2 ) ∧ C(x i , x i+2 )
First, remark that R only states necessary conditions for the existence of a path of length 5 from x to y, as explained in Section 4.1, hence, for all D, Q(D) ⊆ R(V(D)).

Assume now that (x, y) ∈ R(V(D)). Let x 0 , . . . , x 5 be a quantification for which R(x, y) is satisfied. We can prove the following:

• C(x 0 , x 2 ), C(x 1 , x 3 ) and C(x 2 , x 4 ) hold in V(D).
Hence, these pairs of nodes are at distance 2 in D.

• V 1 (x 4 , x 5
) holds in V(D). Hence, x 4 and x 5 are either at distance 1 or 2. If this distance is 1, then we immediately get a path of length 5 from x 0 to x 5 by using the previous point, as

x 0 2 → x 2 2 → x 4 1 → x 5 .
• Similarly, V 2 (x 0 , x 3 ) holds in V(D). If the distance from x 0 to x 3 is 3, we immediately get

x 0 3 → x 3 2 → x 5 .
Otherwise, there exists z such that x 0 → z → x 3 . This implies V 1 (z, x 3 ).

• The remaining case is represented in Figure 10, with the two possible implications of V 1 (z, x 3 ) given by R. Both possibilities also imply a path of length 5 from x 0 to x 5 .

x 0 x 1 x 2 x 3 x 4 x 5 z 2 2 2 2
Fig. 10: Illustration for the last case of Example 3. The full edges represent paths in the database, along with their length when it is more than 1. The dotted edges represent the two possible implications of V 1 (z, x 3 ) given by R.

Proposition 3. Assume that for all G ∈ G V there is a path of weight 0 from 0 to o. Then there exists a computable n ≡ o[c] of size 2 O( V 4 ) such that V {n} and we can effectively compute a first-order rewriting that witnesses it.

Proof. For each G ∈ G V , let π G be the shortest path in G of weight 0 from 0 to o. Let ρ G be the longest path that is used to build G from some H ∈ H V , in Step 2 of Definition 5 and k G be the number of iterations of Step 2 used to build

G from H. Let k = max G∈G V k G . Let ρ = max G∈G V |ρ G |. Let K = ρ k . Let L = max G∈G V |π G |. Let M = 2ck + 3cm where m is the biggest number that occurs in one of the views. Let N = |H V |. Let n = K • L • M • N . Let n be the smallest number such that n ≡ o[c] and n ≥ n .
Using Definition 3, Definition 5, Lemma 4 and Lemma 5, we can check that:

• K is in O( V 18 V );
• L and M are polynomial in V , being respectively O( V 18 ) and O( V 2 );

• N is of size 2 O( V 4 ) , as it is the set of all behavior graphs for V, and each is of size O( V 4 ).

Thus n is in 2 O( V 4 ) .

Claim 8. V determines Q = {n}.

Let R 1 be the (n + 1)-ary conjunctive query deduced from V(x 0 . . . x n ), with x 0 , . . . , x n as free variables. It simply states all the atoms that hold in the view of the simple path x 0 . . . x n , as follows:

R 1 (x 0 , . . . , x n ) = V ∈V i,j (xi,xj )∈V (x0...xn) V (x i , x j )
We also define:

R 2 (x 0 , . . . , x n ) = ∀z, n i=0 V ∈V V (z, x i ) ⇒ c j=0 u∈V u≡j[c] V u-j c +1 c (z, x i+c-j )
and:

R 3 (x 0 , . . . , x n ) = n i,j=0 n+A c k=1 V k c (x i , x j ) ⇒ c-1 l=0 V k+1 c (x i-l , x j+c-l )
where A is the biggest weight that occurs in a graph in G V . Finally, we define R as:

R(x, y) = ∃x 0 , . . . , x n , x 0 = x ∧ x n = y ∧ 3 i=1 R i (x 0 , . . . , x n ) x αi x αi-l x αi+u x αi+u+c-(v [c]) π, |π| = v ∈ V π l , |π l | = l ≡ 0[c] z π 1 , |π 1 | = v -(v [c]) + c
Fig. 11: Illustration for the various notations in the definition of H r . An additional, undrawn, information is that the path from z to x αi+u along the drawn edges is of length u .

Intuitively, each R i enforces a necessary condition for the existence of a path of length n going from x = x 0 to y = x n , as explained in Section 4.1. R 1 and R 2 test conditions (C2) and (C3) respectively, while R 3 enforces the additional constraint of behavior graphs in Definition 5, as illustrated on Figure 5.

It now remains to show that these necessary conditions actually become sufficient under the hypotheses of the proposition. Thus, we can rephrase Claim 8 as: Claim 9. R is a rewriting of Q = {n} with regards to V.

Let D be a database, and x and y be two distinguished nodes of D. Assume that (x, y) ∈ Q(D). Then there exists a path of length n from x to y. Let x 0 , . . . , x n be the n + 1, possibly repeating, nodes of this path. Then it is easy to check that x 0 , . . . , x n satisfy R 1 , R 2 and R 3 in V(D). Hence, R(x, y) holds in V(D).

Conversely, assume that R(x, y) holds in V(D). There exists x 0 , . . . , x n such that x = x 0 , y = x n , and R 1 (x 0 , . . . , x n ), R 2 (x 0 , . . . , x n ) and R 3 (x 0 , . . . , x n ) all hold in V(D). We define, for all r < K • L • N :

p r = {x r•M +ck , x r•M +ck+1 , . . . , x r•M +ck+3cm = x (r+1)•M -ck }
Each p r is a set of 3cm + 1 consecutive nodes among the x i 's, and all p r 's are disjoint. Additionally, for all paths π in D from some x i to some x j , we define δ(π) = |π| -(j -i). To each p r we associate 3 a directed edge-labeled graph H r defined as follows:

• H r has c nodes which we will simply note 0, 1, . . . , c -1.

• For all i ∈ {0, . . . , c -1}, let

α i = r • M + ck + i + 2cm. Remark that α i ≡ i[c].
Then, for all V ∈ V, for all u ∈ V :

-We pick a path π in D from x αi to x αi+u that satisfies V . There exists one, because R 1 (x 0 , . . . , x n ) holds. Let v = |π|. We add to H r an edge from

i to i + u[c] labeled δ(π) = v -u.
-For all V ∈ V, for all u ∈ V , let l be the smallest number such that l + v ≥ u and l ≡ 0[c]. Let π l be a path of D of length l from x αi-l to x αi . There exists one because R 1 (x 0 , . . . , x n ) holds. Let π 0 = π l • π. Let z be the u th predecessor of x αi+u along this path. Then V (z, x αi+u ) holds. Then R 2 implies that there exists v ∈ V and a path π

1 in D from z to x αi+u+c-(v [c]) of length v -(v [c]) + c. Hence, there is a path π from x αi-l to x αi+u+c-(v [c]) of length ((l + v) -u + (v -(v [c]) + c)).
We then add to H r an edge from

i to i + u -v [c] labeled δ(π ) = (v -u) + (v -u ).
See Figure 11 for a visual representation of the various notations.

3 arbitrarily, when there are more than one possibility.

Claim 10.

• For all r, H r ∈ H V .

• For all r, for all edge of label a from i to j in H r , there exists x i and x j in p r such that there exists a path π in D from x i and x j with δ(π) = a, i ≡ i[c] and j ≡ j[c].

Since there are K • L • N different p r 's, then there are at least K • L of them that are attributed the same graph H ∈ H V . This means that there exists an increasing function f such that, for all r < K • L, p f (r) is attributed H. For ease of notations, we rename p f (r) to q 0 r and H to G 0 . Let G 0 , . . . , G k be k successive iterations as described in Definition 5 on G 0 . Then G k ∈ G V and for each s, G s+1 is deduced from G s by doing one iteration of Step 2 in Definition 5.

Claim 11. For all s ∈ {0, . . . , k}, there exist K•L ρ s disjoint sets q s r that consist of consecutive nodes among the x i 's such that:

1. The distance between q s r 's last index and q s r+1 's first index is at least 2c(k -s). Additionally, the first index of q s 0 is at least c(k -s) and the last index of

q s K•L ρ s is at most n -c(k -s).
2. For all r, for all edge of label a from i to j in G s , there exists x i and x j in q s r such that there exists a path π in D from x i and x j with δ(π) = a, i ≡ i[c] and j ≡ j[c].

We prove this claim by induction on s. For s = 0, the correctly named q 0 r 's already satisfy the required properties.

Assume that, at Step s, the properties are true for some q s r 's. For each l < K•L ρ s+1 , let α l be the first index of q s lρ and β l be the last index of q s (l+1)ρ-1 . Then we define q s+1 l as q s+1 l = {x α l -c , . . . , x β l +c }. It is easy to see that the q s+1 l 's defined as such satisfy Property 1 and also Property 2 for the edges of G s+1 that are already in G s . Let µ be the path in G s that is used to build G s+1 by applying Step 2. Then µ is a path of label a and of length η ≤ ρ and we have µ = i 0 a 1 i 1 . . . i η-1 a η i η , where, for all t, there is an edge of label a t from i t to i t+1 in G s . Then Property 2 applied at Step s implies that for all t there exists a two nodes x i t and x i t+1 in q s lρ+t such that there exists a path π t from x i t to x i t+1 with δ(π t ) = a t , i t ≡ i t [c] and i t+1 ≡ i t+1 [c].

Since R 1 (x 0 , . . . , x n ) holds, and for all t i t ≡ i t [c], then there exists a path π t from i t to i t with δ(π t ) = 0. Hence, we can define π as

π = π 0 • π 0 • π 1 . . . π η-2 • π η-2 π η-1 . π is a path from x i 0 to x i η with δ(π) = a t = a, i 0 ≡ i 0 [c] and i η ≡ i η [c].
Then Property 2 is true for all edges of G s+1 from i 0 to i η .

Since δ(π) = a, then δ(π) ≤ A. Hence |π| ≤ n + A. Hence, we can apply R 3 (x 0 , . . . , x n ) and get the other required paths. This ends the proof of the claim.

Finally, the claim applied for s = k proves that there exists L sets q k r of consecutive x i 's that satisfy property 1 and 2 for some G k ∈ G V . By hypothesis, there exists a path in G k from 0 to o of length at most L and of weight 0. We conclude by applying once more the reasoning in the proof of the claim. We deduce that there exists two nodes x i and x j such that there exists a path π in D with δ(π) = 0, i ≡ 0[c] and j ≡ o[c]. We complete π with a path π 1 from x 0 to x i and a path π 2 from x j to x n with δ(π 1 ) = δ(π 2 ) = 0 that are provided by R 1 (x 0 , . . . , x n ). Hence

π 1 • π • π 2 is a path from x 0 to x n with δ(π 1 • π • π 2 ) = 0. Thus, the length of π 1 • π • π 2 is n, and (x, y) ∈ Q(D).
This ends the proof of the proposition.

Decision Algorithm

In this section, we finally prove Proposition 1 by piecing together the tools from Section 4.1 and the results from Section 4.2 and Section 4.3. Recall the statement of Proposition 1: Proposition 1. Given a C-complete view V defined by unions of path queries, such that C ∈ V with C = {c} for some c ∈ N and a natural number o ∈ {0, . . . , c -1}, it is decidable in Π P 2 whether there exists a query Q = {n} such that n ≡ o[c] and V Q. If this is the case, such a query Q of size 2 O( V 4 ) and a first-order rewriting of Q with regards to V can be computed effectively.

Proof. Let V be a C-complete view defined by unions of path queries, such that C ∈ V with C = {c} for some c ∈ N. Let o ∈ {0, . . . , c -1}. Assume that there exists a behavior graph G ∈ G V such that G contains no path of weight 0 going from its 0 node to its o node. Then Proposition 2 proves that there exists no query Q = {n} with n ≡ o[c] such that V Q. Conversely, assume that all G ∈ G V do contain a path of weight 0 going from their 0 nodes to their o nodes. Then Proposition 3 effectively computes a query Q = {n} with n ≡ o[c] such that V Q and a first-order rewriting of Q using V. Thus, Proposition 1 reduces to the following claim: Claim 12. It is decidable in Π P 2 whether all behavior graphs G ∈ G V contain a path of weight 0 going from their 0 nodes to their o nodes.

The statement of the claim naively translates to a Π P 2 algorithm, whose universal part considers all graphs G of the correct form and size and whose existential part tests either that G / ∈ G V or that G contains a path of weight 0 from node 0 to node o. To ensure that it is correct, it remains to check that (1) all graphs in G V are of polynomial size in the size of the queries in V, (2) it can be checked in NP whether a graph does not belong to G V and (3) it can be checked in NP whether a graph contains a path of weight 0 from node 0 to node o.

We will actually substitute (2) with a weaker property (2'), that only tests whether a graph of the correct form and size does not satisfy the second bullet of Remark 2, instead of the whole construction of Definition 5. Indeed, since the proof of Proposition 2 does not actually rely on the exact construction of G V but only on the property stated in Remark 2, it is actually equivalent to prove the claim for any extension of choice graphs that contains G V and satisfies Remark 2.

Property ( 1) is a direct application of Lemma 5. It turns out that (2') and ( 3) are actually consequences of Lemma 4:

(2') Let G be a weighted graph of polynomial size in the size of the queries in V. Checking that G is an extension of a choice graph can be done in polynomial time by simply going through all edges of G and ensuring that all conditions of Definition 3 are satisfied. Then, checking that G does not satisfy Remark 2 is done by non deterministically guessing the existence of cycles of positive and negative weights (of polynomial size, as explained in the proof of Lemma 4), a pair of nodes i, j that are not linked by a path of weight (i -j)[c] and then guessing another pair of nodes i , j such that i -j ≡ i -j[c] and a path of weight (i -j)[c] going from i to j . This final path can correctly be assumed to be of polynomial size if it exists, thanks to Lemma 4.

(3) This is an immediate consequence of Lemma 4. Given a weighted graph G, we non deterministically guess a path of weight 0 going from node 0 to node o. This path can be assumed to be of polynomial size in the size of G if it exists, thanks to Lemma 4. This last item concludes the proof of the proposition.

Extensions

In this section, we discuss several possible extensions of the work presented here. More precisely, Section 5.1 shows the issue that remains to be solved in order to go from asymptotic determinacy to general determinacy, while Section 5.2 considers extensions to stronger view and query languages.

The Case of Small Queries

This section is devoted to producing the full determinacy picture for the view below. As the asymptotic determinacy picture of this view is already known thanks to Theorem 1, this should highlight what remains to be done in order to decide general determinacy. In all this section, we consider the following view:

• V = {C, V 1 , V 2 } • C = {2} • V 1 = {1, 2} • V 2 = {2, 5}
Claim 13. For all even n, V Q = {n}. This easily comes from C = {2}.

By applying Theorem 1 we can show that there exists some odd n such that V Q = {n}, hence V also determines all bigger queries. In order to get the full picture, we need to find the smallest odd n that is determined by V. Our work so far actually gives us: Claim 14. For all odd n ≤ 7, V Q = {n}.

To prove this claim, we use a technique that is very similar to Lemma 6. More precisely, the two databases in Figure 12 agree on V, but disagree on all Q = {n} when n is odd and not greater than 7.

x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7
Fig. 12: The two databases above are a proof that V Q = {n} for any odd n that is not greater than 7. Indeed, we can check that both databases agree on V. However, there is no path of length 1 (respectively 3, 5 and 7) from x 0 to x 1 (respectively x 3 , x 5 and x 7 ) in the bottom database.

Note that this technique does not work for n greater than 7. Indeed, in the case shown above, any path that goes from x 0 to x 7 in the bottom database has to cross from the top section to the bottom section. By doing so, it suffers a delay of either +1 or -3 compared to the expected value. It works here because 7 is "too small" and does not provide enough space to catch-up on this delay. Assume now that n = 9, then a delay of -3 can be mitigated by following a +1 path three times, and thus does not provide a counter-example.

Claim 15. For all n ≥ 11, V Q = {n}.

We show this by arguing that V Q = {11}. This is done by actually proving that the canonical rewriting R given in Section 4.3 works in this case. Although the proof given in Section 4.3 does not apply (because 11 is not "big enough" for all the combinatorial arguments to go through), a careful enumeration of all the possibilities for a database satisfying R actually shows that R(x, y) implies a path of length 11 from x to y, as was done in Example 3.

It is then straightforward to prove that V determines every odd query bigger than 11. Let n = 11 + 2k be such a query. Then a rewriting for n is simply R 11 • C k , as in Lemma 3. As we already know that V determines every even query, this end the proof of the claim.

The case of n = 9. There remains only a single unsolved case, which is n = 9. This qualifies as a "small query" for the view V: a query for which we are unable to either build a generic counter-example, as in Section 4.2, or provide a generic rewriting, as in Section 4.3. We actually proved that V Q = {9}. However, the smallest counter-example that we know is a pair of databases of 154 nodes each, that were built by hand through a very tedious trial and error process and checked by a computer program. At this time, we are unfortunately unable to provide any technique to generate such a counter-example for other views and queries. We conjecture that the combinatorial complexity of these "small queries" might be much higher than what we have dealt with so far.

Language Extensions

In this section, we show how to extend parts of our work to stronger query languages. We do so by extending the view and query languages in two directions: first, we allow the unions in the view to be arbitrary, that is, we allow the sets associated with the queries in the view to be infinite. Second, we allow the database schema to contain more than one symbol and adapt the query and view languages accordingly. To this end, a natural extension is to consider queries defined by chain queries and views defined by unions of chains queries. In [START_REF] Foto | Determinacy and query rewriting for conjunctive queries and views[END_REF], chain queries are defined as conjunctive queries whose underlying graph is a directed path. Here, we provide an equivalent definition that more closely resembles the way we defined path queries.

A chain query Q is defined by a single word w ∈ σ * . On a given database D, Q returns all pairs of nodes (x, y) in D such that there exists a path in D of the form xa 0 x 1 a 1 . . . x m-1 a m-1 y, with a 0 . . . a m-1 = w. The word a 0 . . . a m-1 is called the label of π and is denoted λ(π). Thus, Q(D) = {(x, y) ∈ D | ∃π, x π → y and λ(π) = w}. As with path queries, we will simply note Q = {w}.

Similarly, an arbitrary union of chain queries Q is defined by a (possibly infinite) set of words {w 1 , . . . , w n , . . .} of σ * . It returns all pairs of nodes connected by a path whose label falls into this set, that is, Q(D) = {(x, y) ∈ D | ∃π, x π → y and λ(π) ∈ Q}. As with unions of path queries, we can remark that unions of chain queries generalize chain queries, in the sense that a chain query is simply a union of chain queries whose associated set is of size 1.

Remark that arbitrary unions of chain queries correspond to "any language" path queries, in that they contain all query languages that select pairs of nodes based on the label of a path linking them, such as regular path queries, context-free path queries, and so on.

Remark also that we do not have any theoretical requirement on the way in which the infinite sets associated with these queries should be represented. Indeed, we will shortly see that when an arbitrary union-of-paths view determines a path query, then its finite component already determines the same query. However, for the following construction to be effective, we do require:

• the ability to decide, given a query, whether its associated set is infinite.

• the ability to effectively list all the elements in the associated set, when it is finite.

The following lemma gives a formal statement to the intuition that infinite unions cannot be used to determine a path query. Lemma 10. Let Q be a chain query and V be a view defined by arbitrary unions of chain queries. Let V = V f V ∞ , such that V f only contains queries defined by finite sets, and V ∞ only contains queries defined by infinite sets. Then V Q if and only if V f Q.

Proof. It is easy to see that if V f Q, then V Q. Conversely, assume that V f does not determine Q. Then there exists two databases D 1 and D 2 such that D 1 and D 2 agree on V f but not on Q. Let k be the length of the longest word that appears in Q ∪ V f . We transform D 1 into a new database D 1 as follows:

• We add to D 1 k + 1 new nodes x 0 ,. . . ,x k , as well as the following edges:

-For all i and for all a ∈ σ, a(x i , x i+1 ) holds in D 1 .

-For all a ∈ σ, a(x 0 , x 0 ) and a(x k , x k ) hold in D 1 .

• For each original node x of D 1 and all a ∈ σ, we add a(x, x 0 ) and a(x k , x) to D 1 .

We then apply the same steps to D 2 and get a new database D 2 . This construction has no effect on Q or V f for the original nodes of D 1 and D 2 . However, for each (x, y) ∈ D 1 (respectively D 2 ) and for each V ∈ V ∞ , V (x, y) holds in V ∞ (D 1 ) (respectively V ∞ (D 2 )). Thus, we can check that D 1 and D 2 agree on V but not on Q. Hence V Q, which concludes the proof.

In view of Lemma 10, we can restrict our attention to views defined by finite unions of chain queries. We now show how to translate the necessary conditions from Section 3.1 for a view V defined by finite unions of chain queries to determine a chain query Q. We start by giving an analogue to Lemma 1, by showing that if V Q, then V contains a chain query. We can say even more: each edge in the graph representation of Q must actually belong to a path that satisfies some chain query in V. While this was the case in the previous setting, it was also trivial then.

Lemma 11. Let Q = {w} be a chain query, and V be a view defined by unions of chain queries. Let D be the database consisting of a simple path π = x 0 a 0 x 1 . . . x n-1 a n-1 x n such that λ(π) = w. Assume that V Q. Then for each 0 ≤ i < n, there exists j ≤ i ≤ k such that C = {a j • . . .

• a k } ∈ V.
Proof. This proof is an extension of the proof of Lemma 1. Assume by contradiction that there exists 0 ≤ i < n such that the edge x i ai -→ x i+1 of D is not used to satisfy any chain query of V. In other words, there is no chain query C ∈ V such that (x j , x k ) ∈ C(D) for any j ≤ i and k > i.

We now build a database D 1 as follows:

• D 1 contains the simple path π.

• For each j ≤ i and k > i such that there exists V ∈ V with a j . . . a k ∈ V , we add to D 1 a simple path π j,k,V from x j to x k such that λ(π j,k,V ) ∈ V -{a j . . . a k }. Such a path exists because V is not a chain query, by our hypothesis.

We then build a database D 2 that is a copy of D 1 except that a i (x i , x i+1 ) does not hold in D 2 . Then, it remains to check that V(D 1 ) = V(D 2 ) as was the case in the proof of Lemma 1, and that Q(D 1 ) = Q(D 2 ). Thus V Q, which concludes the proof.

This lemma greatly restricts the form of chain queries Q that can possibly be determined by a given view V. Indeed, a chain query Q = {w} can only be determined by a view V if w consists of (possibly overlapping) words taken from the chain queries in V and stitched together. Remark that what makes the problem non-trivial is precisely this overlapping, in the same way that a view V defined by unions of path queries can determine a path query Q that is not a multiple of the necessary path query in V.

Next, we remark that Lemma 3 immediately applies in this setting. Indeed, if V Q, then V necessarily contains a chain query C. Then, we can deduce that V Q • C k , for any k. We still however have one major challenge to overcome in order to adapt the remainder of our proof to this extended setting comes from the fact that, when the alphabet is reduced to a single symbol, the resulting free monoid is commutative. This implicit argument is crucial both for the alternate definition of asymptotic determinacy of Section 3.2 and for the arithmetic proofs of Section 4. It is likely that the case of chain queries behaves differently and requires new techniques and ideas. We leave this interesting question for future work.

Conclusions

We have shown that, given a view V defined by unions of path queries, we can decide determinacy of almost all path queries Q. Although the smallest query that we can handle is of exponential size in the size of V, our decision procedure still works with Π P 2 complexity. Moreover, for the queries that are big enough to be handled by our algorithm, we also provide a first-order rewriting when they are determined, and a canonical counter-example otherwise.

A natural continuation of this work would be to try and solve the determinacy problem even for small queries. Another possible continuation stems from the following remark: on all examples where V determines Q that we are aware of, it also turns out that our rewriting is actually correct, even when the query is too small to be handled by our technique. Perhaps it so happens that this rewriting is always correct, as soon as we assume that V determines Q. Failing that, it might still be the case that a first-order rewriting can always be found.

Fig. 1 :

 1 Fig.1: A database (left) and its view image (right) through a view V. Here, σ = {a}, τ = {b, c}.V = {Q b , Q c }, with Q b = {2} and Q c = {3}.The names of the nodes are omitted for readability. Instead, the corresponding nodes are placed at the same relative position in the database and its view image.

Fig. 4 :

 4 Fig. 4: Illustration for the existence of the path µ of delay (v -u) + (v -u ) in the construction of H D . Full arrows represent paths in D and are labeled by their length. Dashed arrows represent edges in E. µ is the thick path, and q = c -v [c].

Fig. 5 :

 5 Fig. 5: Illustration of the intuition for the construction of a behavior graph. Assume that the x i 's form a path of length n from x 0 to x n . If x k and x are connected via a sequence of C's, represented by the dashed edges, then for all u < c, there exists some intermediate nodes such that x k-u and x +c-u are connected as shown in the picture.

Fig. 6 :Fig. 7 :Lemma 6 .

 676 Fig. 6: A behavior graph for the view defined in Example 1.

Fig. 8 :

 8 Fig. 8: Example of the construction in Lemma 6 for the view defined in Example 1, that is V = {C, V } with C = {2} and V = {1, 2}. For this example, d = 2, n = 5 and o = 1.Remark how the left and right databases agree on V, while there exists a path of length 5 going from x 0 to x 5 in the left database, but no such path in the right one.

3 .

 3 We first prove that w(0, 0 + c ∧ d) ≡ 0[c ∧ d]. This is a purely arithmetic consequence of Property 2, as explained in Lemma 8. We rewrite this equality as w(0, 0 + c ∧ d) ≡ -c ∧ d + kd[c]. Then, by following the same reasoning as in the proof for Property 2, we prove that there exists a path from 0 to c ∧ d of weight -c ∧ d[c]. Since this path satisfies the requirement in Definition 5, then there must exist some weight w ≡ -c ∧ d[c] such that, for all i ∈ {0, . . . , c -1}, there is an edge from i to i + c ∧ d of weight w, which we denote by π i,i+c∧d . Let c = c c∧d . Then π 0,c∧d • π c∧d,2(c∧d) • . . . • π (c -1)(c∧d),c (c∧d) is a cycle of 0 of weight c w. Thus, d divides c w. By construction, c ∧ d = 1, hence d divides w, that is, w ≡ 0[d]. This implies that for all i ∈ {0, . . . , c -1}, w(i, i + c ∧ d) ≡ 0[d].

Fig. 9 :

 9 Fig.9: Example of the construction in Lemma 9 for the view defined in Example 2, that is V = {C, V } with C = {3} and V = {1, 5}. Remark how the left and right databases agree on V, while they disagree on all queries that do not ask for paths of length 0[START_REF] Calvanese | Lossless regular views[END_REF].

  Given two integers n and d, n[d] represents the remainder in the division of n by d. We say that two integers n 1 and n 2 are equivalent modulo d, and we write n 1 ≡ n 2 [d] if they have the same remainder modulo d. We denote by gcd(A) the greatest common divisor of a set of integers A, and we use n 1 ∧ n 2 for gcd({n 1 , n 2 }).

If a i = d -1 for some i, then the property of the lemma is falsified by the subsequence a i obtained with j = i.

Acknowledgements I gratefully thank Luc Segoufin and Cristina Sirangelo for carefully proofreading this paper and providing many invaluable comments and advices. I also thank the anonymous reviewers for their painstaking and helpful reviews.

* Part of this work was done while the author was supported by EPSRC grant EP/M025268/1.