Nadime Francis
email: nfranci2@inf.ed.ac.uk

Leonid Libkin
email: libkin@inf.ed.ac.uk

Schema Mappings for Data Graphs

Schema mappings are a fundamental concept in data integration and exchange, and they have been thoroughly studied in different data models. For graph data, however, mappings have been studied in a restricted context that, unlike real-life graph databases, completely disregards the data they store. Our main goal is to understand query answering under graph schema mappings -in particular, in exchange and integration of graph data -for graph databases that mix graph structure with data. We show that adding data querying alters the picture in a significant way.

As the model, we use data graphs: a theoretical abstraction of property graphs employed by graph database implementations. We start by showing a very strong negative result: using the simplest form of nontrivial navigation in mappings makes answering even simple queries that mix navigation and data undecidable. This result suggests that for the purposes of integration and exchange, schema mappings ought to exclude recursively defined navigation over target data. For such mappings and analogs of regular path queries that take data into account, query answering becomes decidable, although intractable. To restore tractability without imposing further restrictions on queries, we propose a new approach based on the use of null values that resemble usual nulls of relational DBMSs, as opposed to marked nulls one typically uses in integration and exchange tasks. If one moves away from path queries and considers more complex patterns, query answering becomes undecidable again, even for the simplest possible mappings.

INTRODUCTION

Schema mappings are a fundamental notion in data interoperability tasks such as data integration and exchange. They prescribe a virtual or physical transformation of one database into another, and guide notions of query answering over integrated or exchanged data. They have been thoroughly investigated over relational data (see recent books [START_REF] Arenas | Foundations of Data Exchange[END_REF][START_REF]Schema Matching and Mapping[END_REF][START_REF] Doan | Principles of Data Integration[END_REF] reporting on the developments of the last two Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. PODS'17, May 14 -19, 2017, Chicago, IL, USA c 2017 Copyright held by the owner/author(s). Publication rights licensed to ACM. ISBN 978-1-4503-4198-1/17/05. . . $15.00 DOI: http://dx.doi.org/10.1145/3034786.3056113 decades). Schema mappings are specified by queries over source and target schemas and some relationship between them, typically containment. For relational mappings, we understand how to build database instances based on them, how to query such instances, and where tractability boundaries lie.

While relational data continues to dominate, there are many other models around, and it is thus natural that efforts have been made to understand schema mappings for other data formats. Notably there were both theoretical investigations and practical implementations of schema mappings for XML, see, e.g., [START_REF] Amano | XML schema mappings: data exchange and metadata management[END_REF][START_REF] Haas | Clio grows up: from research prototype to industrial tool[END_REF][START_REF] Marnette | ++Spicy: an opensource tool for second-generation schema mapping and data exchange[END_REF]. While they addressed the same questions as in the relational world, the techniques involved were quite different, as one had to reconcile navigational queries and querying data stored in XML documents.

Another popular data model is graph data. It shows up in many modern applications such as social networks and the Semantic Web, that are naturally modeled as graphs, and where querying graph topology is important. Several industrial strength implementations of graph databases are available, such as Neo4j, Virtuoso, AllegroGraph and others. We refer to [START_REF] Angles | Survey of graph database models[END_REF][START_REF] Angles | Foundations of modern graph query languages[END_REF] for surveys of graph data models, languages for them, and implementations. Typical queries for graph data are based on paths or patterns in graphs. In database theory, the most commonly studied classes of queries are based on regular path queries, or (RPQs) [START_REF] Cruz | A graphical query language supporting recursion[END_REF].

When it comes to schema mappings on graph databases, we have much less knowledge compared to relational or XML mappings. Mappings based on containment of path queries were studied in [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF][START_REF] Calvanese | Rewriting of regular expressions and regular path queries[END_REF][START_REF] Calvanese | On simplification of schema mappings[END_REF]. These papers looked into both static analysis questions and answering RPQs and their extensions under such mappings, but the setting as described there falls short of modeling graph databases that occur in practice.

Real-world graph databases mix graph structure with data that resides in nodes and edges. These are referred to as property graphs [START_REF] Robinson | Graph Databases[END_REF]; they form the basic data model of Neo4j and are now advocated by LDBC [START_REF] Ldbc | Linked Data Benchmark Council[END_REF] as the standard model to be adopted by graph database implementations. A theoretical abstraction of property graphs is data graphs [START_REF] Libkin | Querying graphs with data[END_REF], an analog of data trees that have been actively studied as a similar abstraction of XML documents, cf. [START_REF] Bojanczyk | Automata for data words and data trees[END_REF][START_REF] Segoufin | Static analysis of XML processing with data values[END_REF]. In property graphs, each node and each edge can carry a record of values, while in a data graph, just as in data trees, each node contains a single data value. From the point of view of theoretical investigation whose goal is to understand the complexity of the main computational tasks associated with a data model, this abstraction suffices, as property graphs can be modeled by data graphs, by pushing data from edges to nodes and by creating additional nodes to store multiple data values.

Our main goal is to understand the behavior of schema mappings on data graphs where both navigation and data are taken into account, much as was done for relational and XML data in the past, and to go beyond [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF][START_REF] Calvanese | Rewriting of regular expressions and regular path queries[END_REF][START_REF] Calvanese | On simplification of schema mappings[END_REF] where only navigational aspects have been considered. In doing so, we discover that adding data alters the picture dramatically: some basic tasks quickly become undecidable, and recovering decidability, and especially tractability, requires new techniques that do not mimic those for other data models.

As in [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF][START_REF] Calvanese | Rewriting of regular expressions and regular path queries[END_REF][START_REF] Calvanese | On simplification of schema mappings[END_REF], our schema mappings are based on RPQs, but RPQs are applied to data graphs. For such mappings and purely navigational queries based on RPQs and some extensions, query answering is decidable, with coNP data complexity [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF]; to achieve tractability, regular expressions need to be severely restricted [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF]. Answering queries refers to finding certain answers that are true in all instances satisfying the conditions of a schema mapping for given source data. This is the standard approach in data exchange and virtual data integration [START_REF] Arenas | Foundations of Data Exchange[END_REF][START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF].

If graphs contain data, the ability to query it makes a strong impact. For very simple mappings based on RPQs, and very simple queries that combine navigation and data querying, the query answering problem becomes undecidable. Even if RPQs used in mappings do not allow any recursion (in essence, we deal with the usual relational schema mappings), answering queries that combine navigation and data is intractable, although decidable.

The undecidability result is rather strong and leaves essentially no hope of having any kind of navigation in mappings except what can be expressed by standard relational schema mappings. It applies to schema mappings whose rules are very simple: they are both local-as-view (LAV) and global-as-view [START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF] at the same time, except just one rule which involves the simplest unconstrained reachability query. Moreover the query to be answered is given by a regular expression with equality, which is the simplest kind of regular expressions on paths with data [START_REF] Libkin | Regular expressions for data words[END_REF].

Thus, either in graph data exchange, or in virtual integration of graph databases, answering queries that refer to data stored in graph nodes is impossible without a dramatic restriction on schema mappings. Such a restriction tells us to forget that we are dealing with a graph database (at least on the target side) and treat it as a relational database instead; then many queries can be answered, albeit with a high complexity.

Having shown these negative results, we need to see what can be recovered. It turns out that we can have efficient query answering for a large class of queries (e.g., all RPQs based on the strongest known class of regular expressions that use data [START_REF] Libkin | Regular expressions for data words[END_REF]), and do it using the standard route: find a universal solution (cf. [START_REF] Arenas | Foundations of Data Exchange[END_REF]) and evaluate the query on it. This works for relational mappings under the additional assumption that the domain of data values contains a special null value that behaves as in SQL [START_REF] Date | A Guide to the SQL Standard[END_REF]: no comparison involving a null can be true. This differs from the more common assumption of labeled or marked nulls [START_REF] Arenas | Foundations of Data Exchange[END_REF][START_REF] Doan | Principles of Data Integration[END_REF] but is actually more in line with storing graphs in a relational DBMS and uses it for querying.

For the last question addressed in the paper, we look at query languages for graphs that combine navigation and data querying, but are not path-based. In particular, we look at the adaptation of XML language XPath [START_REF]XML Path Language (XPath[END_REF] to graphs, as was investigated in [START_REF] Cassidy | Generalizing XPath for directed graphs[END_REF][START_REF] Libkin | Querying graphs with data[END_REF]. Here we show a strong negative result: even if mappings treat graph databases as relational, query answering for graph XPath queries under such mappings is undecidable. To summarize, our results have the following implications.

1. For the model underlying real-life graph database applications, such as property graphs of Neo4j, schema mappings have to treat graphs as if they were relational databases, i.e., no recursively defined navigational properties are allowed in mappings.

2. Even under such mappings, to achieve tractability of answering path queries in exchange/integration scenarios, one has to populate target instances with null values interpreted as SQL nulls, when it comes to querying them.

3.

Moving from RPQs that use data to more general patterns is problematic even for the simplest mappings, as query answering becomes undecidable already for simple fragments of Graph XPath.

Organization Section 2 defines data graph and navigational queries; in Section 3 we describe queries that combine navigation and data querying. Section 4 defines graph schema mappings and querying under them. In Section 5 we prove the main undecidability result for querying under graph schema mappings. Section 6 looks at the restriction of schema mappings that does not allow recursion over targets, and proves decidability and intractability of query answering. Section 7 shows how to restore tractability via null values. Section 8 looks at queries with restricted comparisons, and Section 9 shows undecidability of query answering for Graph XPath. Conclusions are in Section 10. Due to space limitations, we are only able to give sketches and ideas of the proofs.

PRELIMINARIES

Graph databases and data graphs For the purposes of navigational querying, graph databases are usually abstracted as labeled directed graphs, i.e., their edges are of the form (v, a, v ), where v, v are two nodes and a is a label. For data graphs, we follow exactly the same approach except that a node now consists of a node id and a data value. More precisely, let Σ be a finite set of edge labels, N a countably infinite set of node ids, and D be a countably infinite set of data values. A pair v = (n, d) where n ∈ N and d ∈ D is a node. A data graph is G = V, E where V is a finite set of nodes (i.e., V ⊂ N × D) such that no two nodes have the same node id, and E ⊆ V × Σ × V is a set of labeled edges. For a node v = (n, d), we let δ(v) refer to the data value d.

A data graph G can also be seen as a relational structure V, (Ea)a∈Σ where each Ea is the binary relation {(v, v ) ∈ V | (v, a, v ) ∈ E}. We will freely move back and forth between these two representations of data graphs.

A path π in a data graph G from a node v1 to a node vn+1 is a finite sequence π = v1a1v2 . . . vnanvn+1, where each vi is a node of G, each ai is a symbol of Σ, and (vi, ai, vi+1) is an edge of G for each i ≤ n. We use λ(π) to refer to the word a1 . . . an, called the label of π. The length of π, denoted by |π|, is the length of the word λ(π) = a1 . . . an, in this case n. To denote the fact that π is a path from v1 to vn+1, we will write v1 π → vn+1. Similarly, for a word w ∈ Σ * , we will write v1 w → vn+1 to say that there exists a path going from v1 to vn+1 of label w.

A data path is a sequence d1a1d2 . . . dnandn+1 where all the dis are elements of D and all the ajs are labels from Σ. Given a path π = v1a1v2 . . . vnanvn+1 in a data graph G = V, E , the corresponding data path is defined as δ(π) = δ(v1)a1δ(v2) . . . δ(xn)anδ(vn+1). That is, each node in π is replaced by its data value. Note that data paths are very similar to data words [START_REF] Bojanczyk | Automata for data words and data trees[END_REF][START_REF] Segoufin | Static analysis of XML processing with data values[END_REF] which are words over Σ × D; data paths are data words with one extra data value.

Navigational queries A k-ary query q (over Σ) is a mapping that associates with each Σ-labeled data graph G = V, E a set of k-tuples of nodes q(G) ⊆ V k . We refer to k as the arity of q. We mainly deal with binary queries, i.e., k = 2.

The basic queries we consider are regular path queries (RPQs). An RPQ over Σ is just a regular expression e over Σ. Over a (data) graph G, it outputs pairs of nodes connected by a path whose label is in e:

e(G) = {(v, v ) | ∃π : v π → v and λ(π) ∈ e}
A word RPQ is an RPQ where e is a word w ∈ Σ * . A reachability RPQ is simply e = Σ * .

A special case of a word RPQ is an atomic RPQ a, where a ∈ Σ. Such a query returns the binary relation

Ea = {(v, v ) | (v, a, v ) ∈ E}.

DATA RPQS S S ON DATA GRAPHS

In this section we review queries on data graphs that combine navigation and data querying. In general, there are three main approaches to such queries. Data RPQs are extensions of RPQs with regular expressions that mix alphabet letters and data values [START_REF] Libkin | Querying graphs with data[END_REF][START_REF] Libkin | Regular expressions for data words[END_REF]; these are the queries we mainly concentrate on as they are natural analogs of navigational queries most commonly studied in graph databases. A different approach is that of walk logic [START_REF] Hellings | Walk logic as a framework for path query languages on graph databases[END_REF], initially defined for a slightly different model and then extended to data graphs in [START_REF] Barceló | Expressive path queries on graphs with data[END_REF]. The language is elegant and very expressive, but it was shown to have non-elementary complexity, ruling out its practical applications [START_REF] Barceló | Expressive path queries on graphs with data[END_REF]. Finally, one can have pattern-based languages, like Cypher of Neo4j [START_REF] Robinson | Graph Databases[END_REF] or analogs of XPath for graphs [START_REF] Cassidy | Generalizing XPath for directed graphs[END_REF][START_REF] Libkin | Querying graphs with data[END_REF][START_REF] Robinson | Graph Databases[END_REF]. We look at those in Section 9.

We now define data RPQs that mix navigation and data. They work on data paths, which are essentially data words; thus, data RPQs will be based on regular languages for data words/paths. The most common automata model that provides the notion of regularity for them is register automata [START_REF] Kaminski | Finite memory automata[END_REF]. Of course queries are not specified by automata but rather by more declarative regular expressions. While register automata have been around for a while, the study of regular expressions for them is more recent [START_REF] Libkin | Regular expressions for data words[END_REF], and we shall look at two types of them: expressions with memory, that capture register automata, and weaker expressions with equality that have attractive computational properties. We now define those, specifically for data paths. In all definitions below, we assume a countably infinite set X of variables (registers).

Regular expressions with memory [START_REF] Libkin | Querying graphs with data[END_REF]. These expressions use conditions on variables from X defined by

c := x = | x = | c ∧ c | c ∨ c
with x ranging over X . Their satisfaction is defined with respect to a pair (σ, d), where σ is a partial map from X to D with finite support (i.e., σ : X → D ∪ {⊥} where ⊥ stands for undefined, and σ(x) = ⊥ only for finitely many x ∈ X ), and d ∈ D. The rules are:

• σ, d |= x = iff σ(x) = d; • σ, d |= x = iff σ(x) = d.
and we use the standard rules for ∧ and ∨. Note that conditions are closed under negation; in order to express ¬c, we can propagate ¬ through ∧ and ∨ all the way to basic comparisons and then swap x = with x = .

The class REM(Σ, X ) of regular expressions with memory over alphabet Σ and variables X is defined by the grammar:

e := ε | a | e + e | e • e | e + | e[c] | ↓ x.e
where a ranges over Σ, c over conditions, and x over tuples of variables from X . They extend the usual regular expressions with two features: e[c] checks if condition c is satisfied after matching e, and ↓ x.e assigns the current data value to variables in x before matching e. To give a couple of examples, the expression ↓ x.(a[x = ]) + defines data paths labeled a along which all data values are different from the first one, i.e., data paths of the form dad1a • • • adn-1adn where di = d for every i ≤ n. It binds the first data value d, and then checks after reading each letter that the letter was a, and the following data value was different from d. As another example, the expression Σ * • ↓ x.Σ + [x = ] • Σ * defines data paths in which the same data value occurs more than once: it skips up to that data value, binds it to x, moves one or more labels forward, and checks if the same data value occurs. As usual, Σ * is ε + Σ + .

The semantics is defined by means of a relation (e, w, σ) σ , where e ∈ REM(Σ, X ), w is a data path, and σ, σ are variable assignments. Intuitively, it says that if one starts with assignment σ and parses w according to e, then one ends up with σ . The language of e is then defined as:

L(e) = {w | ∃σ : (e, w, ⊥ ⊥ ⊥) σ}
where ⊥ ⊥ ⊥ is the initial empty assignment (i.e., each variable is undefined). That is, L(e) gives all the data paths that can be parsed according to e without any prior variable binding.

Relation is defined inductively on the structure of expressions. It uses the notion of concatenation of two data paths w = d1a1 . . . an-1dn and w = dnan . . . am-1dm that share the last and the first data value, defined as w • w = d1a1 . . . an-1dnan . . . am-1dm.

• (ε, w, σ) σ iff w = d for some d ∈ D and σ = σ.

• (a, w, σ) σ iff w = d1ad2 and σ = σ.

• (e1 • e2, w, σ) σ iff w = w1 • w2 for some data paths and there exists σ such that (e1, w1, σ) σ and (e2, w2, σ ) σ .

• (e1 + e2, w, σ) σ iff (e1, w, σ) σ or (e2, w, σ) σ .

• (e + , w, σ) σ iff w = w1 • • • wm for some w1, . . . , wm and there exist σ = σ0, σ1, . . . , σm = σ such that (w, wi, σi-1) σi for all i ≤ m.

• (↓ x.e, w, σ) σ iff (e, w, σ x=d ) σ , where d is the first data value of w and σ x=d modifies σ by assigning value d to all variables in x.

• (e[c], w, σ) σ iff (e, w, σ) σ and σ , d |= c, where d is the last data value of w.

Regular expressions with memory have the same expressiveness as register automata and share many computational properties with them: for example, their nonemptiness problem is Pspace-complete, and membership problem is NPcomplete [START_REF] Demri | LTL with the freeze quantifier and register automata[END_REF][START_REF] Libkin | Regular expressions for data words[END_REF]. They are closed under union, intersection, concatenation, Kleene star, but not under complement.

Remark The definition of REM needs to exclude pathological cases e[c] where either c uses a variable that has not been bound to a value, or e is equivalent to ε. This is a small technicality that does not affect us at all as we shall never encounter such expressions. We refer to [START_REF] Libkin | Querying graphs with data[END_REF] for details.

Regular expressions with equality This particularly simple class of expressions allows us to capture many useful properties expressed by register automata. The class REE(Σ) of regular expressions with equality is defined by:

e := ε | a | e + e | e • e | e + | e= | e =
where a ranges over alphabet letters. The language L(e) of data paths denoted e is given as follows:

• L(ε) = {d | d ∈ D}. • L(a) = {dad | d, d ∈ D}. • L(e • e ) = L(e) • L(e ).
• L(e + e ) = L(e) ∪ L(e ).

• L(e

+ ) = {w1 • • • w k | k ≥ 1 and each wi ∈ L(e)}. • L(e=) = {d1a1 . . . an-1dn ∈ L(e) | d1 = dn}. • L(e = ) = {d1a1 . . . an-1dn ∈ L(e) | d1 = dn}.
For example, the language of data paths on which the same data value occurs more than once is given by Σ

* • (Σ + )= • Σ * .
While these expressions are strictly weaker than register automata, they have attractive computational properties: for example, both nonemptiness and membership are solvable in Ptime. They have the same closure properties as expressions with memory except they are not closed under intersection [START_REF] Libkin | Querying graphs with data[END_REF][START_REF] Libkin | Regular expressions for data words[END_REF].

We shall also look at particularly simple expressions, called path with tests, defined by e := a | e • e | e= | e = . These are just words, where some subwords carry an annotation indicating whether data values at the beginning and the end of the subword are the same. For example, (a(bc)=) = matches data paths d1ad2bd3cd2 with d1 = d2.

Queries. As queries, we consider RPQs given by regular expressions of one of the above classes. The output e(G) is the set of pairs (v, v ) of nodes such that there is a path π in G going from v to v and with δ(π) ∈ L(e).

If it is not important which class the expression comes from (with memory or with equality), we use a generic term data RPQs. When we want to be more specific, for REMs we refer to memory RPQs, for REEs to equality RPQ, and for paths with tests, to data path queries.

SCHEMA MAPPINGS AND QUERY AN-SWERING

We now define schema mappings for graph databases, query answering based on them, and explain how standard data exchange and virtual data integration scenarios for graph data are captured.

From now on, we adopt the convention that queries used in mappings will be denoted by lower case letters q, q etc., and queries that one needs to answer will be denoted by upper case letters Q, Q etc.

Schema mappings for data graphs As in [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF][START_REF] Calvanese | On simplification of schema mappings[END_REF][START_REF] Francis | Datalog rewritings of regular path queries using views[END_REF], we define mappings based on RPQs. Assume that we are given two sets of edge labels Σs and Σt, called source and target alphabets respectively. Definition 1. A graph schema mapping (GSM) M is a set of pairs of RPQs (q, q ), where q is an RPQ over Σs and q is an RPQ over Σt.

If Gs = Vs, Es and Gt = Vt, Et are data graphs over Σs and Σt respectively, we write (Gs, Gt) |= M if q(Gs) ⊆ q (Gt) for every (q, q ) ∈ M, and call Gt a solution for Gs under M. This looks just like the standard definition of schema mappings for graph databases [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Calvanese | On simplification of schema mappings[END_REF]; the difference is that now we deal with data graphs, whose nodes are pairs

v = (n, d) ∈ N × D. Thus, if (n, d), (n , d ) ∈ q(Gs), we require that (n, d), (n , d ) ∈ q(Gt).
Hence it is not just node ids that must appear in the target graph but also data values that they carry. A GSM M is called LAV, or local-as-view, if for every pair (q, q ) ∈ M, query q is atomic, i.e., just a letter a ∈ Σs. These mappings are most commonly used in virtual data integration, and we shall see that most negative results are already true under the LAV restriction. When we say that a LAV mapping is defined using a certain query language, it means that it consists of pairs (a, q ) where a ∈ Σs and q belongs to this language. Similarly, a GSM M is called GAV, or global-as-view, if for every pair (q, q ) ∈ M, query q is atomic.

Query answering As is standard [START_REF] Arenas | Foundations of Data Exchange[END_REF][START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF], we shall adopt the certain answers semantics for query answering under schema mappings.

Definition 2. Given a data graph Gs over Σs, a GSM M over Σs, Σt, and a query Q over Σt, the set of certain answers to Q on Gs under M is defined as:

2M(Q, Gs) = {Q(Gt) | (Gs, Gt) |= M}
In other words, we look at answers true in all Σt data graphs Gt that, together with the source Gs, satisfy conditions of mapping M.

This gives us the main computational problem we study, query answering under graph schema mappings. We look primarily at data complexity of the problem when the mapping M and the query Q are fixed.

Problem : QueryAnswering GSM(M, Q) Input :
A data graph Gs over Σs a tuple v of nodes of Gs. Question : Is v in 2M(Q, Gs)?

When M and Q are clear from the context or not important, we simply refer to data complexity of QueryAnswering GSM. When we speak of combined complexity, we assume that Q and M are part of the input.

Data exchange and virtual data integration

We now explain how the setting described earlier subsumes graph data exchange and virtual data integration.

In relational data exchange, one has source and target schemas σ and τ , and schema mappings M are typically specified by source-to-target tgds (st-tgds) ∀x (ϕσ(x) → ∃z ψτ (x, z)), where ϕσ(x) is a query over σ and ψτ (x, z) is a query over τ (usually both are conjunctive). In this case if q is given by ϕσ and q by ∃z ψτ (x, z), the above sttgd just says that for source and target instances S and T satisfying the mapping we must have q(S) ⊆ q (T ). For answering queries Q over the target for a given source database Ds, one defines certain answers as 2M(Q, Ds) = {Q(Dt) | (Ds, Dt) |= M}, cf. [START_REF] Arenas | Foundations of Data Exchange[END_REF]. Thus, for graph schema mappings, we mimic the relational case: graph databases are viewed as relational structures, but we use RPQs instead of conjunctive queries.

Under LAV, the setting also subsumes virtual data integration of graph databases [START_REF] Calvanese | Rewriting of regular expressions and regular path queries[END_REF][START_REF] Calvanese | On simplification of schema mappings[END_REF][START_REF] Francis | Datalog rewritings of regular path queries using views[END_REF]. In general, in data integration, we have sources S1, . . . , Sn, and a global schema γ; the mapping M is given by queries q1, . . . , qn over γ which is satisfied by an instance D of γ, written as ((S1, . . . , Sn), D) |= M, if Si ⊆ qi(D) for all i ≤ n. For a query Q posed against a database of schema γ, virtual data integration defines answers as 2M(Q, (S1, . . . , Sn)) = {Q(D) | ((S1, . . . , Sn), D) |= M}, see [START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF]. Query answering over LAV GSMs corresponds precisely to virtual integration of several graph databases. Indeed, we can view these source graphs as relations Ea for a virtual graph database G. Then our setting -that is, the notions of LAV schema mappings and query answering -is precisely the same as the virtual data integration scenario described above.

UNDECIDABILITY OF DATA RPQS S S

The problem of query answering under graph schema mappings has been studied for purely navigational queries. For mappings given by RPQs, finding 2M(Q, G) can be done in coNP if Q is an RPQ, or belongs to one of several navigational languages that extend RPQs (conjunctive RPQs, nested regular expressions, or conjunctive nested regular expressions); the problem is coNP-hard even when Q is an RPQ [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF].

We show here that the situation is completely different for queries that combine data and navigation: query answering under schema mappings becomes undecidable for data RPQs. In fact we show that undecidability holds under three strong restrictions:

• queries are equality RPQs, i.e., are based on the simplest class of data RPQs;

• mappings are local-as-view; and

• queries in mappings are either atomic or the simplest reachability queries Σ * t .

We start by introducing a new concept that will help us describe the class of mappings for which the query answering answering problem is undecidable, and will also be will be important for restrictions that let us regain decidability. Definition 3. We call a mapping M relational if for each (q, q ) ∈ M, the query q is a word RPQ, i.e., is given by a word wt ∈ Σ * t .

The reason for the name is that queries over Σt in these mappings are relational conjunctive queries. A LAV relational mapping consists of pairs (a, wt) with a ∈ Σs and wt ∈ Σ * t . LAV relational mappings eliminate all recursion in queries that define them, and for such mappings, based on what we know from relational data exchange [START_REF] Arenas | Foundations of Data Exchange[END_REF], we would expect many query answering tasks to be decidable (more on that in the next section). So what is the smallest addition to such mappings that cannot be expressed with first-order relational queries? Such an addition is the simplest form of reachability, namely reachability by an arbitrary path, in which we do not impose any restriction at all on label use.

To capture this, we define relational/reachability mappings M as those where in all pairs (q, q ) ∈ M, either q is a word RPQ, as in relational mappings, or the simplest reachability query Σ * t . In particular, in a LAV relational/reachability mapping, pairs of queries are of two kinds: either (a, wt), with a ∈ Σs and wt ∈ Σ * t , or (a, Σ * t ). We can make it even simpler and impose the restriction that every rule in a mapping, except for reachability, be both LAV and GAV (global-as-view [START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF]). In such a LAV/GAV relational/reachability mappings, pairs of queries are of two kinds:

• (a, b) with a ∈ Σs and b ∈ Σt, and

• (a, Σ * t ) with a ∈ Σs.
Already for these very simple mappings, answering the simplest data RPQs is undecidable.

Theorem 1. QueryAnswering GSM is undecidable in data complexity for data RPQs.

In fact, there exists a LAV/GAV relational/reachability mapping M, and an equality RPQ Q such that QueryAnswering GSM(M, Q) is undecidable.

Proof idea. The proof is rather involved; we now explain the key idea of the encoding and illustrate the main gadgets used in the proof. We reduce from the Post Correspondence Problem (PCP), by building a GSM M and a query Q from the alphabet such that for each PCP instance, there exist a source database Gs and a pair of nodes (start, end) of Gs such that (start, end) / ∈ 2M(Q, Gs) if and only if the PCP instance is satisfiable. We assume that PCP instances are sets of n pairs of nonempty words (referred to as tiles) (ur, vr) 1≤r≤n over Σ = {a, b}. Both alphabets Σs and Σt are {a, b, i, t, m, m, id, s, v, ↔, #}. Symbols other than a and b are separators: i, s and v mark what we call the input, solution and verification parts of the encoding; t marks the start of the encoding of a tile and ↔ marks the separation between words ur and vr of a given tile (ur, vr); m and m designate a specific tile in a list of tiles; id will be used to insert additional data values along paths; and # marks the end of the encoding.

The source database Gs built from the PCP instance is shown below.

start input i c 0 1 t c 1 1 u 1 1 . . . u 2 1 c i 1 1 u i 1 1 d 0 1 ↔ d 1 1 v 1 1 . . . v 2 1 d j 1 1 v j 1 1 . . . t . . . c 0 n t c 1 n u 1 n . . . u 2 n c in n u in n d 0 n ↔ d 1 n v 1 n . . . v 2 n d jn n v jn n end s #
In the figure, the u j i s and v j i s are letters of ui, vi, and all data values c j i and d j i are distinct. The mapping M has rules ( , ) for = a, b, t, i, s, ↔ and (#, Σ * t ). Under this mapping, Gs will be copied into a target graph Gt, but some path can be inserted in place of the # edge of the input. Now our query will ensure that this path is of a special shape. It will start with an s-edge and then have an encoding of the paths πr 1 , . . . , πr m corresponding to the solution of the PCP instance, i.e., a sequence r1, . . . , rm of indexes from {1, . . . , n} (if a solution exists). Then, after a v separator, there is a verification section with labels forming the path ur 1 . . . ur m (which is the same as vr 1 . . . vr m ).

For each r among r1, . . . , rm, the path πr looks as follows.

c 0 n t c 0 n-1 t . . . t c 0 r+1 t d jr r m γ id d j r-1 r v jr r δ id . . . v j r-1 r η id d 0 r v 0 r c ir r ↔ ζ id c i r-1 r u ir r ι id . . . u i r-1 r κ id c 0 r u 0 r c 0 r-1 m c 0 r-2 t . . . t c 0 1 t s
The path πr starts and ends with the encoding of r split into paths of n -r and r nodes carrying distinct data values, and connected with t-edges. In between, we have encodings of vr and ur in reverse order, with extra nodes inserted as additional ids for the purpose of verifying that the solution is correct. These are the nodes connected with id edges, and whose data values are shown as Greek letters in the picture. These four sections of the encoding of πr are separated with m, ↔, and m letters.

The intuition behind the query Q is that it works on a target instance described above and checks for errors, that is, properties that tell us that it is not a correct encoding of a PCP instance and its solution. Then having (start, end) ∈ 2M(Q, Gs) implies that there exists a target instance in which none of the errors occur, and thus implies satisfiability of the PCP instance.

There are several kinds of errors, and to ensure that we do have an encoding of PCP, we need to eliminate all of them.

For this, the query Q will be a disjunction of several expressions. One of them, that does not have any references to data values (and thus is an ordinary regular expression) ensures that the path from start to end is shaped as explained above (rather, it needs to check for errors, i.e., that the path is not shaped as described above, but in this case we have a usual regular expression and can take complement).

Next one can show how to write REE expressions whose negation ensures the following. First, each subpath between two s labels is the encoding of some pair (ui, vi) from the input. Thus, the subpath between the first and last s labels is the encoding of a sequence of tiles of the PCP instance.

Next, we use REE expressions to deduce that the subpath that starts after label v only contains pairwise distinct data values, and that the sequence of data values that occur after each label id in the encoding of the solution on the left-hand (resp. right-hand) side of each tile is a copy, in the reverse order, of the sequence of data values in the verification path.

Finally, we use another REE expression whose negation ensures that these data values correspond to the same letter, i.e. it is satisfied if it can find a mismatch. Thus, the sequence of letters on the right-hand side of the tiles in the solution path is the same as the sequence of letters on the left-hand side of the tiles. Thus, the subpath between the first and last s labels is indeed the encoding of a solution to the PCP instance, from which we deduce that it is satisfiable if (start, end) ∈ 2M(Q, Gs).

For the other direction, if there is a PCP solution, we build a single-path instance Gt as described above, and then it is a simple matter of checking that (start, end) ∈ Q(Gs).

Since LAV/GAV relational/reachability mappings represent the simplest possible non-relational addition to the simplest imaginable mappings, this result strongly suggests that for data exchange and integration tasks, target graph databases ought to be viewed as relational databases, and mappings ought to exclude any form of recursive navigation over target data.

RELATIONAL MAPPINGS FOR DATA GRAPHS

Given the conclusion of the previous section, we now restrict our attention to relational graph schema mappings in which no recursion over the target schema is allowed. These are GSMs M (see Definition 3) in which for all (q, q ) ∈ M, the query q is a word RPQ.

One might be tempted to think that these can be cast as the usual relational mappings over relational representations of graphs, and then results about them can be obtained from what we know in the relational case. While the premise is true, the conclusion is not: we cannot obtain results for such mappings simply by appealing to the relational case. We first explain why this is so, and then present our results about relational GSMs. Do relational results suffice? Relational GSMs can be easily modeled by the usual relational mappings on graphs viewed as relational databases. A standard representation of a data graph G over Σs as a relational database DG uses binary relations N s and E s a for each a ∈ Σs (and likewise N t and E t a for Σt). Each node (n, d) is a tuple in N s , and for each edge (n, d), a, (n , d ) , we have the pair (n, n ) in E s a . Note that since such databases are over disjoint domains N and D, we assume that in addition predicates N (x) and D(x) are available to distinguish them.

A relational GSM M between Σs and Σt data graph can be expressed by means of the relational schema mapping M rel defined as shown below.

• For each pair (q, w) ∈ M with w ∈ Σt, we have an sttgds ∀x, y q(x, y) → qw(x, y), where, for a word w = a1 . . . an, the query qw(x, y) is the conjunctive query ∃x1 . . . xn-1 E t a 1 (x, x1)∧E t a 2 (x1, x2) • • •∧E t an (xn-1, y). Note that query q itself need not be conjunctive or even first-order, as in relational st-tgds.

• For each (q, q ) ∈ M, add an st-tgd ∀x, y N s (x, y) ∧ ∃z q(x, z) → N t (x, y) and symmetrically with ∃z q(z, x). They say that every node that occurs in the result of a source query must be moved to the target.

• Add a key constraint ∀x, y, y (N t (x, y) ∧ N t (x, y ) → y = y ) (i.e., each node id has one data value), and target tgds ∀x, y N t (x, y) → N (x) ∧ D(y) as well as ∀x, y E t a (x, y) → ∃z, z (N t (x, z) ∧ N t (y, z )) for each a ∈ Σt, saying that every node in the target graph must have a data value.

Such a mapping M rel precisely describes the action of M on relational representations of graphs, as the following straightforward result shows. Proposition 1. If M is a relational GSM and Gs is a Σs data graph, then solutions for DG s under M rel are exactly the structures of the form DG t where Gt is a solution for Gs under M.

Despite this close connection, we cannot directly derive the complexity of query answering from known relational results. To start with, relational mappings can contain pairs (q, w) where q is a complex reachability query, and thus relational results do not apply to it. Even when all such queries q are conjunctive, we still cannot easily apply known results to M rel . The reason is that answering first-order relational queries under mappings of relational databases, even without target constraints, is already undecidable, cf. [START_REF] Arenas | Foundations of Data Exchange[END_REF]. Data RPQs, on the other hand, go beyond first-order queries. Trying to encode data RPQs in a language for which the complexity of query answering in data exchange is known is also problematic, given the scarcity of such languages. For example, [START_REF] Arenas | Query languages for data exchange: beyond unions of conjunctive queries[END_REF] looked at a well behaved (in data exchange) fragment of datalog with negation, but the natural coding of equality RPQs in datalog with inequalities over databases DG does not fall into that fragment. And for memory RPQs, it is not even clear what fragment of a natural relational language they correspond to (e.g., coding of regular expressions into datalog breaks for them).

When it comes to lower bounds, we cannot directly take advantage of existing techniques such as [START_REF] Fagin | Data exchange: semantics and query answering[END_REF][START_REF] Madry | Data exchange: On the complexity of answering queries with inequalities[END_REF] as they use queries that cannot be expressed with RPQs.

Upper and lower bounds for relational mappings Despite the difficulties with the naive approach to reducing to relational results, we can establish both upper and lower bounds on the complexity of query answering. We start with the upper bound.

Theorem 2. For relational GSMs, data complexity of QueryAnswering GSM for data RPQs is in coNP, and its combined complexity is in Pspace.

In fact this follows from a more general result. A homomorphism between two data graphs G = V, E and G = V , E is a map h : N → N such that for each edge (v1, a, v2) in E, the edge (h(v1), a, h(v2)) is in E , where h is extended to nodes by h (n, d) = h(n), d . A query Q is closed under homomorphisms if, whenever we have a homomorphism h : G → G and v ∈ Q(G), then h(v) ∈ Q(G ). It can be readily checked that under this definition, data RPQs are closed under homomorphisms (in fact, a more general result will be shown in Section 7, Proposition 6). The result then follows from the proposition below.

Proposition 2. Let C be a class of queries on data graphs that has Ptime data complexity and Pspace combined complexity. Assume that every query q ∈ C is closed under homomorphisms. Then, for relational GSMs and queries in C, the problem QueryAnswering GSM is in coNP in data complexity and in Pspace in combined complexity.

Proof sketch. We first prove an auxiliary result. Assume that M is a GSM and Gs is a source graph database such that there exists a number k > 0 such that, for every rule (q, q ) ∈ M, the language L(q ) is contained in Σ k t . If Gt is a solution for Gs, we can show that there is another solution G t ⊆ Gt whose size is bounded by (2k + 1)

• |M| • |Gs| 2 .
With this, the proposition follows, since deciding whether (x, y) ∈ 2M(Q, Gs) can be done with the following nondeterministic algorithm: first nondeterministically guess a target database G t of size at most (2|M| 2 + |M|) • |Gs| 2 , then check whether (Gs, G t ) |= M and (x, y) / ∈ Q(G t ). Correctness follows from the fact that the mapping is relational, and thus words in L(q ) for each (q, q ) ∈ M have bounded length, which is ≤ |M|. It is easy to check that the algorithm has the required complexity under the assumptions.

In fact, the proof shows a slightly stronger result: the right-hand side queries in mappings need not be single words but could also be regular expressions of the form w1 + • • • + wm, where each wi ∈ Σ * t for i ≤ m. For query answering under mappings of relational databases, coNP-hardness is already known for unions of conjunctive queries with inequalities [START_REF] Fagin | Data exchange: semantics and query answering[END_REF][START_REF] Madry | Data exchange: On the complexity of answering queries with inequalities[END_REF]. However, as we noticed earlier, reductions used queries that do not correspond to data path queries (non-recursive data RPQs). Nonetheless, it is not hard to come up with a direct reduction to show the following. Proposition 3. There exists a data path query Q and a LAV relational mapping M such that the problem QueryAnswering GSM(M, Q) is coNP-complete.

For the proof, we use a reduction from 3-colorability; there are some technicalities involved, compared to the relational case, due to a very restricted type of query Q.

The query in Proposition 3 uses three inequalities. A similar relational result in [START_REF] Fagin | Data exchange: semantics and query answering[END_REF] uses three inequalities as well, although it also showed that for unions of conjunctive queries with at most one inequality per disjunct, query answering under mappings based on st-tgds is in Ptime. We can adapt the proof and further lower the complexity guarantee for data path queries. Proposition 4. For relational GSMs M and data path queries that have at most one subexpression of the form e = , data complexity of QueryAnswering GSM is in NLogspace.

As a final remark, we note that for data path queries, query answering is decidable for arbitrary GSMs, not just relational mappings. Proposition 5. If Q is a data path query and M is an arbitrary GSM, then the problem QueryAnswering GSM(M, Q) is in coNP.

The idea of the proof is that mapping rules that can produce words of length greater than the length of Q are of no use in detecting whether a tuple is a certain answer, and thus one can cut the mapping to a simpler one that essentially resembles the relational case.

TRACTABLE QUERY ANSWERING VIA SQL NULLS

Our next question is how to achieve tractability of query answering under graph schema mappings. A standard solution in the case of relations and XML documents is to find a universal solution such that running a query over it gives us certain answers, cf. [START_REF] Arenas | Foundations of Data Exchange[END_REF]. The coNP-hardness result of the previous section shows that this approach cannot be used directly even with simple equality RPQs. Nonetheless, we show that under some assumptions on data values in target graphs, it can be recovered.

To explain this approach, we recall that when target instances are built in relational data exchange, they are populated either by constants or marked nulls [START_REF] Arenas | Foundations of Data Exchange[END_REF]. For instance, if we have a relational st-tgd ∀x, y S(x, y) → ∃z T (x, z) ∧ T (z, y), and a source {S(a, b), S(c, d)}, then the common way is to construct a target instance with tuples T (a, n n n1), T (n n n1, b), T (c, n n n2), T (n n n2, d), where n n n1, n n n2 are marked nulls. That is, for each tuple satisfying S(x, y), a new marked null z is invented, and tuples (x, z), (z, y) are put in T .

Such marked nulls are really nothing but constants that did not occur in the source instance: they are new values for which equality is purely syntactic, i.e., n n n1 = n n n1 but n n n1 = n n n2, n n n1 = a, etc. Thus we can simply view them as elements of the set D of data values.

In real-life implementations of SQL relational databases, nulls behave differently: there is just one null value n n n, and no comparison involving n n n can evaluate to true. We now show that with nulls behaving like SQL nulls, tractability of query answering can be restored using universal solutions.

Formally, we expand the domain D of data values with a single null value n n n, writing Dn n n for D∪{n n n}. A node v = (n, n n n) is called a null node. Following SQL's rule for nulls, we do not let any comparisons involving nulls evaluate to true. That is, we modify the evaluation of conditions of memory RPQs over Dn n n by:

• σ, d |= x = iff σ(x) = d and σ(x), d = n n n; • σ, d |= x = iff σ(x) = d and σ(x), d = n n n,
and for equality RPQs, we allow equalities and inequalities to be true only when both arguments are different from n n n. Note that we do not use SQL's three-valued logic; at the end of the section we explain why we can use the simpler approach without any loss of generality.

With this, for a GSM M and a Σs data graph Gs with data values in D, we define certain answers over graphs with null nodes as:

2 n n n M (Q, Gs) = Q(Gt) (Gs, Gt) |= M and Gt over Dn n n
This corresponds to the standard data exchange setting [START_REF] Arenas | Foundations of Data Exchange[END_REF][START_REF] Fagin | Data exchange: semantics and query answering[END_REF]: source instances do not have nulls, while nulls can appear in the targets.

How does this notion relate to certain answers 2M(Q, Gs)? Since we increase the domain of values, it is immediate that

2 n n n M (Q, Gs) ⊆ 2M(Q, Gs) .
Thus, our approach can be seen as providing an underapproximation of query answering in the general case. What makes it attractive is that such an underapproximation can be found efficiently for data RPQs.

Theorem 3. If the domain of data values contains the null value n n n, then data complexity of answering data RPQs under relational graph schema mappings (i.e., checking if v ∈ 2 n n n M (Q, Gs)) is in NLogspace. Its combined complexity is in Pspace for memory RPQs and in Ptime for equality RPQs.

One has matching NLogspace and Pspace lower bounds as well, as evaluation of data RPQs is NLogspace-hard in data complexity and Pspace-hard in combined complexity. This theorem will follow from a more general result that provides an algorithm for query answering, even for a larger class of queries.

Recall that a relational GSM M over Σs and Σt consists of pairs (q, w) where q is an RPQ over Σs and w ∈ Σ * t . Given such a mapping and a Σs data graph Gs, a Σt data graph Gt is a universal solution for Gs under M if it is constructed by the following procedure:

1. compute dom(M, Gs) which is the set of all nodes appearing in query results q(Gs), for (q, w) ∈ M, and add all nodes of dom(M, Gs) to Gt;

2. then, for each pair (q, a1 . . . , a k ) in M, and each pair of nodes (v, v ) ∈ q(Gs), create fresh null nodes v1, . . . , v k and add the path va1v1a2 . . . v k-1 a k v to Gt.

Note that all universal solutions are actually unique up to a renaming of node ids. Indeed, the only source of nondeterminism in the procedure is the choice of node ids for the newly created null nodes.

Just like the usual universal solutions in relational or XML data exchange, these solutions have homomorphisms into all other solutions. To show this, we first need to extend homomorphisms to data graphs with null nodes. Recall that a homomorphism between data graphs G and G without null nodes was defined as a map h : N → N such that for each edge (n1, d1), a, (n2, d2) of G, the edge (h(n1), d1), a, (h(n2), d2) is in G . We now say that a map h : N → N is a homomorphism between graphs with nulls nodes if for each edge (n1, d1), a, (n2, d2) of G, there is an edge (h(n1), d 1 ), a, (h(n2), d 2 ) in G such that either di = d i or di = n n n, for i = 1, 2. That is, non-null data values are preserved, but a homomorphism has the freedom to replace n n n with another data value. The lemma below justifies the name universal.

Lemma 1. If M is a relational mapping, Gs is a Σs data graph, Gt is a universal solution for Gs under M and G t is an arbitrary solution over Dn n n for Gs under M, then there is a homomorphism from Gt to G t that is the identity on dom(M, Gs).

Our goal is to compute certain answers 2 n n n M (Q, Gs) by evaluating a query Q over a universal solution Gt. This strategy works for queries that are preserved under homomorphisms. As before, Q is preserved under homomorphisms if, whenever we have two data graphs G and G with null nodes and a homomorphism h from G to G , then for a tuple (n1, d1), . . . ,

(n k , d k ) ∈ Q(G), there is a tuple (h(n1), d 1 ), . . . , (h(n k ), d k ) ∈ Q(G ), where di = d i when- ever di = n n n.
The following is a standard observation that is often made in data exchange scenarios to enable efficient computation of certain answers. Theorem 4. Let M be a relational GSM, Gs a Σs data graph over D, and let Gt be a universal solution for it under M. If Q is a query preserved under homomorphisms, then 2 n n n M (Q, Gs) is the restriction of Q(Gt) to tuples that do not contain any null nodes.

Proof. If (x, y) is a pair of constant nodes such that (x, y) ∈ Q(Gt), then the definition of Gt implies that x and y are nodes of Gs. If G t is an arbitrary solution for Gs under M, by Lemma 1, there is a homomorphism from Gt to G t such that h(x) = x and h(y) = y. Since Q is closed under homomorphism, this implies that (x, y) ∈ Q(G t ). Thus, (x, y) ∈ 2 n n n M (Q, Gs). Conversely, if (x, y) ∈ 2 n n n M (Q, Gs), then x and y are nodes of Gs, and thus are constant nodes. Furthermore, since Gt is a solution, we conclude that (x, y) ∈ Q(Gt), by the definition of certain answers.

Theorem 4 gives us an algorithm for finding answers to queries preserved under homomorphism. First we construct a universal solution; for relational mappings, this can be done in NLogspace. Then we evaluate Q on it, and then again in NLogspace eliminate null nodes from the result. Thus, it is the data complexity of Q (as long as it is above NLogspace) that determines the complexity of finding certain answers; for instance, if data complexity of Q is NLogspace (or Ptime), then so is the data complexity of QueryAnswering GSM over data domains containing null value n n n.

Since the data complexity of data RPQs is in NLogspace [START_REF] Libkin | Querying graphs with data[END_REF], the last bit that we need to finish the proof of Theorem 3 is the proposition below. Proposition 6. Data RPQs are closed under homomorphisms on data graphs with null nodes.

Proof sketch. It suffices to show that for a REM e, if we have a data path π and its homomorphic image π = h(π), then if δ(π) is in L(e), then so is δ(π ). This is done by induction on the clauses of the definition of L(e), using the following claim. For any two data paths w = d0a1d1 . . . dn-1andn and w = d 0 a1d 1 . . . d n-1 and n such that di = d i whenever di = n n n, for all REMs e , and for all valuations σ0, σ 0 , σ such that σ0(x) = σ 0 (x) whenever σ0(x) = n n n and (e, w, σ0) σ, there exists a valuation σ such that (e, w , σ 0 ) σ and σ(x) = σ (x) whenever σ(x) = n n n. Remark 1. We know that 2 n n n M (Q, Gs) provides an approximation to 2M(Q, Gs), i.e., 2 n n n M (Q, Gs) ⊆ 2M(Q, Gs). But how good is such an approximation? The question is akin to those asked about approximations of certain answers over incomplete databases [START_REF] Guagliardo | Making SQL queries correct on incomplete databases: A feasibility study[END_REF][START_REF] Libkin | SQL's three-valued logic and certain answers[END_REF] and, just like in those cases, precise theoretical answers are hard to obtain. For example, in the case of Boolean queries, whenever 2 n n n M (Q, Gs) = 2M(Q, Gs) -which is bound to happen due to the complexity mismatch -the approximation misses all the correct answers (since false is represented as ∅ and true as the singleton empty tuple {()}). To see how well such schemes actually perform the best one can do is an experimental study, as for instance was done in [START_REF] Guagliardo | Making SQL queries correct on incomplete databases: A feasibility study[END_REF]. For now we have only studied theoretical aspects of such mappings, but the hope is for good quality approximations, given the fact that we have a minimal extension of the domain of values, with just one element.

Remark 2. SQL nulls use three-valued logic, with truth values true, false, and unknown, and conditions d = n n n and d = n n n evaluate to unknown. Here we did not use the threevalued logic and instead made them evaluate to false. While this modification could make difference for some queries, for the language of data RPQs there is no change; this is why we chose the simpler way of handling nulls.

Indeed, let eval(c, σ) be the evaluation of condition c as we defined it (i.e., with both d = n n n and d = n n n being false). Let evalsql(c, σ) be the three-valued SQL evaluation of conditions. Under this evaluation, both d = n n n and d = n n n are unknown, and then unknown is propagated through ∧ and ∨ by unknown ∧ true = unknown ∨ false = unknown; unknown ∨ true = true; unknown ∧ false = false. Then it is straightforward to see that eval(c, σ) = true iff evalsql(c, σ) = true.

QUERIES WITHOUT INEQUALITIES

We now look at the behavior of two different languages for data graphs. First, in this section we look at restriction of data RPQs that forbids inequalities, and show that for them, query answering behaves better, at least for relational GSMs. In the next section we show that in contrast, the language that permits non-path patterns behaves rather badly with respect to query answering.

By REM= and REE= we mean restrictions of data RPQs based on regular expressions with memory and equality that only use equality comparisons and disallow inequality comparisons. That is, REM= queries are the same as memory RPQs, but x = is not allowed in conditions, and REE= queries are the same as equality RPQs, but expressions e = are not allowed.

Results of Section 6 tell us that data complexity of answering REM= and REE= queries under relational GSMs is in coNP. A better NLogspace bound was given for data path queries in REE= (see Proposition 4), but not for queries outside this narrow class. We now show that tractable bounds can be obtained for all queries in REM= and REE= under relational mappings.

The idea here follows along the lines of the ideas of Section 7. We define a new kind of canonical solutions, which bear close resemblance to the universal solutions of Section 7 and play a very similar role. Formally, given a relational GSM M over Σs and Σt and a Σs data graph Gs, a Σt data graph Gt is a least informative solution for Gs under M if it is constructed by the following procedure:

1. compute dom(M, Gs) and add all nodes of dom(M, Gs) to Gt;

2. then, for each pair (q, a1 . . . , a k ) in M, and each pair of nodes (v, v ) ∈ q(Gs), create fresh nodes v1, . . . , v k , with respective fresh data values d1, . . . , d k and add the path va1v1a2 . . . v k-1 a k v to Gt.

The main point of this definition is that the new nodes that are created during the procedure are populated with fresh and distinct data values instead of nulls as in the case for the universal solutions. Then we can prove an analog of Theorem 4: Theorem 5. Let M be a relational GSM, Gs a Σs data graph and let Gt be a least informative solution for Gs under M. Let Q be an REM= or an REE= query. Then 2M(Q, Gs) is the restriction of Q(Gt) to tuples with values in dom(M, Gs).

As before, this leads to an algorithm for computing certain answers. We first construct a least informative solution, which can be done in NLogspace for relational mappings. Then we run the query on it, and remove from the output the tuples that use values outside of dom(M, Gs). This yields the following corollary: Corollary 1. For relational GSMs, data complexity of QueryAnswering GSM is in NLogspace for both REM= and REE= queries, and its combined complexity is in Pspace for REM= queries and in Ptime for REE= queries.

For arbitrary mappings, query answering of RPQs could be coNP-hard even without data values [START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF], so eliminating inequality would not give us tractability as in Theorem 1. It is still a valid question whether such restriction gives us decidability, in contrast with Theorem 1. This question appears to be quite hard, and we only have a result for REE=. Proposition 7. For arbitrary graph schema mappings, the problem QueryAnswering GSM for REE= queries is in coNP for data complexity, and has elementary combined complexity.

This result already requires an involved proof which establishes a small model property based on Ramsey theorem. This in particular accounts for the high combined complexity bound (which is quadruple exponential, due to Ramsey bounds). Full details are omitted here due to space constraints.

GRAPH XPATH

We now look at a different language for expressing queries on data graphs, that is not restricted to path patterns such as data RPQs. In fact languages for graph data such as Cypher of Neo4j [START_REF] Robinson | Graph Databases[END_REF] or navigational SPARQL [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF] do allow non-path patterns.

As a concrete language to work with, we take Graph XPath (GXPath), that adapts the standard XML path language XPath [START_REF]XML Path Language (XPath[END_REF] to work on graphs. This language is rather natural for expressing navigational properties that go beyond path patterns, and we have a good understanding of the expressive power of its fragments [START_REF] Libkin | Querying graphs with data[END_REF] and their static analysis [START_REF] Kostylev | Containment of data graph queries[END_REF]. GXPath has also been implemented and tested in a distributed environment [START_REF] Nolé | A distributed implementation of GXPath[END_REF].

There are several variations of GXPath, and we use a minimalistic one, as we prove an undecidability result: a fragment of core GXPath with data value comparisons, denoted by GXPath core ∼ (following the convention in the literature on data trees, we use ∼ to denote data value comparisons).

In defining the language, we assume that for every label a ∈ Σ, the alphabet also contains a label a -which defines the inverse:

E a -= {(v, v ) | (v , v) ∈ Ea}.
That is, each edge can be traversed in either direction. As usual for XPath, expressions include node expressions (denoted by ϕ, ψ) that select nodes, and path expressions (denoted by α, β) that select pairs of nodes. These are given by mutually recursive definitions below: Note that this fragment excludes many features of full GXPath, such as negation of path expressions ¬α, arbitrary transitive closure α * , and even simpler features such as checking for a constant data value and intersection of paths. But even for this simple fragment of GXPath, query answering is undecidable in data complexity for the simplest possible mappings. Theorem 6. There is a relational GSM M that is both LAV and GAV and a GXPath core ∼ node expression ϕ so that the problem QueryAnswering GSM(M, ϕ) is undecidable.

α, β := ε | a | a * | α • β | α ∪ β | α= | α = | [ϕ] ϕ, ψ := ¬ϕ | ϕ ∧ ψ | ϕ ∨ ψ | α Given a data graph G = V, E , the semantics of a path expression is [[α]] G ⊆ V × V ,
The problem is undecidable for path expressions as well, since v ∈ 2M(ϕ, G) iff (v, v) ∈ 2M([ϕ], G). The proof of Theorem 6 is based on the following. Lemma 2. There is a fixed labeling alphabet Σ and a GXPath core ∼ node expression ϕ such that the following problem is undecidable: given a data graph G over Σ and a node v, is there a data graph

G ⊇ G such that v ∈ [[ϕ]] G .
Theorem 6 is an immediate consequence of Lemma 2: take M to be {(a, a) | a ∈ Σ} (i.e., the source and target alphabets are the same). Then

v ∈ 2M(ϕ, G) iff v ∈ [[ϕ]] G for some G ⊇ G.
Proof idea (Lemma 2). We prove a stronger statement. A labeled tree is said to have the non-repeating property if no Path expressions Node expression

[[ε]] G = {(v, v) | v ∈ V } [[a]] G = {(v, v ) | (v, a, v ) ∈ E} [[a * ]] G = {(v, v ) | ∃ v π → v with λ(π) ∈ a * } [[α • β]] G = [[α]] G • [[β]] G [[α ∪ β]] G = [[α]] G ∪ [[β]] G [[[ϕ]]] G = {(v, v) ∈ G | v ∈ [[ϕ]] G } [[α=]] G = {(v, v ) ∈ [[α]] G | δ(v) = δ(v )} [[α = ]] G = {(v, v ) ∈ [[α]] G | δ(v) = δ(v )} [[ α ]] G = {v | ∃v (v, v ) ∈ [[α]] G } [[¬ϕ]] G = V -[[ϕ]] G [[ϕ ∧ ψ]] G = [[ϕ]] G ∩ [[ψ]] G [[ϕ ∨ ψ]] G = [[ϕ]] G ∪ [[ψ]] G
G ⊇ G satisfying v ∈ [[ϕ]] G ,
then such a G can be chosen to be a tree with the non-repeating property and the same root v.

To show this, as in Theorem 1, we use reduction from PCP. We assume that PCP instances {(ur, vr) | 1 ≤ r ≤ n} are over the alphabet {a, b}, and in the encoding we use additional separator labels t, t # , s, v, #, ←, →, ← # , → # , m, id. Some of them have the same meaning as in the proof of Theorem 1, but new ones are needed to encode the instance in a tree structure: t # marks the end of the encoding of a list of pairs from the instance; ← and → mark tree branches that encode uis and vis, and ← # and → # respectively terminate these branches. The PCP instance is encoded as a source tree: In the encoding of the entire PCP instance, the "horizontal" path from the start node goes via roots of trees Ir. Additionally, data values of all the nodes are pairwise distinct.

The idea is then to construct a node expression ϕ such that the PCP instance is satisfiable iff there exists a data tree G ⊇ G rooted at start with the non-repeating property satisfying start / ∈ [[ϕ]] G . The construction uses the idea of attaching the solution and the verification sections to G: the solution section codes a possible solution to the PCP instance and the verification section verifies that it is a solution. The query ϕ essentially looks for "errors" in the construction of these additional sections. If start / ∈ [[ϕ]] G , it means there are no errors, and thus a solution was found. The construction is somewhat lengthy and involved, and is given in the appendix.

Static analysis of GXPath

In addition to applications in query answering under GSMs, we can use Lemma 2 to answer some open questions on static analysis of GXPath expressions. Typical static analysis problems are: These problems have been studied in depth for XPath on trees, and more recently they were looked at in the context of GXPath, with [START_REF] Kostylev | Containment of data graph queries[END_REF] showing several undecidability results for regular GXPath. This more expressive language allows path expressions α * , i.e., transitive closure of arbitrary path expressions. In our case of core GXPath, transitive closure only applies to alphabet labels. For core GXPath, decidability of containment and satisfiability was not known.

We can now use techniques of Lemma 2 to strengthen results of [START_REF] Kostylev | Containment of data graph queries[END_REF] and prove undecidability of static analysis of core GXPath with data value comparisons. Theorem 7. Both satisfiability and containment problems are undecidable for GXPath core ∼ .

Proof sketch. We give a proof for the satisfiability problem; undecidability of containment easily follows from it. We use the strong version of Lemma 2 described in the sketch of the proof of Theorem 6. Let Σ and ϕ be the schema and query fixed by the statement of the lemma. Let G be a data tree with the non-repeating property, all distinct data values, and root v such that if there exists a data graph G ⊇ G such that v / ∈ [[ϕ]] G , then such a G can be chosen to be a tree with the non-repeating property whose root is also v. To prove the theorem, we define a new GXPath core ∼ formula ϕ that depends on ϕ and G such that ϕ is satisfiable iff there exists a data graph G ⊇ G such that v / ∈ [[ϕ]] G .

For this, we define two queries, ϕG and ϕ δ , that will ensure that any witness for ϕ is a data graph that contains G. The goal for ϕG is to ensure that any data graph satisfying it contains the topological structure of G. The formula ϕG is defined inductively: for a single-node tree it is ε , and for a tree with children of the root labeled a1, . . . , an and having subtrees G1, . . . , Gn, we define ϕG as a1 • [ϕG 1 ] ∧ . . . ∧ an • [ϕG n ] .

For ϕ δ , let wx, for a node x of G, be the label of the unique path from the root to x in G. We define ϕ δ = {¬ wy • (w - y • wz)= | y, z nodes of G and y = z}. Then one can show that G embeds homomorphically into any graph G that satisfies ϕG and, if ϕ δ in addition holds in G , then G is contained in G , up to a renaming of data values and nodes ids.

With this, we define ϕ as ϕG ∧ ϕ δ ∧ ¬ϕ. It is then routine to verify that ϕ is satisfiable iff there exists a data graph

G ⊇ G such that v / ∈ [[ϕ]] G .

CONCLUSIONS

Our main conclusion is that under graph schema mappings, answering queries that combine navigation and data is very different from answering purely navigational queries. Undecidability arises very easily; even under strong restrictions one has intractability of query answering; and achieving tractability requires new techniques that do not mirror those known for relational and XML data.

There are several directions in which we would like to extend this work. First of all, now that we understand what is needed to achieve tractability for the abstraction of data graph, we would like to see how these restrictions look in the case of property graphs of Neo4j [START_REF] Robinson | Graph Databases[END_REF] and language and constraint formalisms advocated by LDBC [START_REF] Ldbc | Linked Data Benchmark Council[END_REF]. The eventual goal of such a project is to build an integration/exchange system on top of a commercial graph database.

Our results suggest viewing target databases as relational, at least from the point of view of mappings. An alternative of going from relations to graphs has been explored in [START_REF] Boneva | Graph data exchange with target constraints[END_REF], although mainly intractability results were shown. It would be interesting to see if useful restrictions on relational-tograph mappings can be found, perhaps using techniques developed here.

We would also like to investigate the use of SQL nulls, as exploited here, in relational data exchange systems. Such systems normally use marked nulls, which need to be implemented on top of relational DBMSs. The advantage of using SQL nulls is that no additional implementation of relational database features is needed, and they appear to allow efficient answering of a rather large class of queries in integration and exchange scenarios.

  and the semantics of a node expression expression is[[ϕ]] G ⊆ V . Precise definitions of those are in Figure1. Intuitively, ε defines the set of pairs (v, v), while a defines Ea and a * defines its transitive closure. Expressions α • β and α ∪ β define composition and union, and α= (or α = ) gives pairs of nodes defined by α that carry the same (or different) data value. Two types of expressions connect path and node expressions: α is the first projection of the semantics of α (i.e., nodes from which a path satisfying α can start), and [ϕ] gives pairs of nodes (v, v) satisfying ϕ. Node expressions are closed under Boolean operations.

Figure 1 :

 1 Figure 1: Semantics of GXPath core ∼ with respect to G = V, E

  Ir encodes the pair (ur, vr) as follows:

•

  satisfiability: given an expression ϕ, is there a data graph G such that [[ϕ]] G = ∅?, and • containment: given two expressions ϕ and ψ, is it true that [[ϕ]] G ⊆ [[ψ]] G for every G?

Acknowledgments We thank referees for their comments. This work was supported by EPSRC grants M025268 and N023056.