Iovka Boneva

Lawek Staworko

Jose Lozano

Consistency and Certain Answers in Relational to RDF Data Exchange with Shape Constraints

We investigate the data exchange from relational databases to RDF graphs inspired by R2RML with the addition of target shape schemas capturing fragments of SHACL and ShEx. We study the problems of consistency i.e., checking that every source instance admits a solution, and certain query answering i.e., finding answers present in every solution. We identify the class of constructive relational to RDF data exchange that uses IRI constructors and full tgds (with no existential variables) in its source to target dependencies. We show that the consistency problem is coNP-complete. We introduce the notion of universal simulation solution that allows to compute certain query answers to any class of queries that is robust under simulation. One such class are nested regular expressions (NREs) that are forward i.e., do not use the inverse operation. Using universal simulation solution renders tractable the computation of certain answers to forward NREs (data-complexity).

Introduction

The recent decade has seen RDF raise to the task of interchanging data between Web applications [START_REF] Michel | A survey of RDB to RDF translation approaches and tools[END_REF]. In many applications the data is stored in a relational database and only exported as RDF, as evidenced by the proliferation of languages for mapping relational databases to RDF, such as R2RML [START_REF] Das | R2RML: RDB to RDF mapping language[END_REF], Direct Mapping [START_REF] Arenas | A Direct Mapping of relational data to RDF[END_REF] or YARRRML [START_REF] Heyvaert | Declarative rules for Linked Data generation at your fingertips![END_REF]. As an example, consider the following R2RML mapping, itself in RDF format presented in Turtle syntax It exports the join of two relations Emp(id , name) and Email (id , name) into a set of triples. For every employee it creates a dedicated Internationalized Resource Identifier (IRI) consisting of the prefix emp: and the employee identifier. More importantly, the class (rdf:type) of each employee IRI is declared as :TEmp. RDF has been originally proposed schema-less to promote its adoption but the need for schema languages for RDF has been since identified and deemed particularly important in the context of exchange of data between applications [START_REF] Labra Gayo | Validating RDF data[END_REF][START_REF] W3c | RDF validation workshop report: Practical assurances for quality RDF data[END_REF]. One family of proposed schema formalisms for RDF is based on shape constraints and this class includes shape constraint language (SHACL) [START_REF] Corman | Semantics and validation of recursive SHACL[END_REF][START_REF] Knublauch | Shapes constraint language (SHACL). W3C Recomm[END_REF] and shape expressions schemas (ShEx) [START_REF] Boneva | Semantics and validation of shapes schemas for RDF[END_REF][START_REF] Prud'hommeaux | Shape expressions language 2.1. W3C Draft[END_REF][START_REF] Staworko | Complexity and expressiveness of ShEx for RDF[END_REF]. The two languages allow to define a set of types that impose structural constraints on nodes and their immediate neighborhood in an RDF graph. For instance, the type :TEmp may be defined as :TEmp { :name xsd:string; :email xsd:string?; :works @:TDept+ } Essentially, an employee IRI must have a single :name property, an optional :email property that are both strings, and at least one :works property each leading to an IRI of type :TDept.

In the present paper we formalize the process of exporting a relational database to RDF as data exchange, and study two of its fundamental problems: consistency and certain query answering. In data exchange the mappings from the source database to the target database are modeled with source-to-target tuple-generating dependencies (st-tgds). For mappings defined with R2RML we propose a class of full constructive st-tgds, which use IRI constructors to map entities from the relational database to IRIs in the RDF. For instance, the R2RML mapping presented before can be expressed with the following st-tgd

Emp(id , name) ∧ Email (id , email ) ⇒ Triple(emp2iri (id), :name, name) ∧ Triple(emp2iri (id), :email, email ) ∧ TEmp(emp2iri (id)),
where emp2iri is an IRI constructor that generates an IRI for each employee. To isolate the concerns, in our analysis of the st-tgds we refrain form inspecting the definitions of IRI constructors and require only that they are non-overlapping, i.e. no two IRI constructors are allowed to output the same IRI. We call the above setting constructive relational to RDF data exchange. We report that in this setting all 4 use cases of R2RML [START_REF] Auer | Use cases and requirements for mapping relational databases to RDF[END_REF] can be expressed. Furthermore, we can cover 38 out of 54 test cases for R2RML implementations [START_REF] Villazón | R2RML and direct mapping test cases[END_REF]. Among the non-covered test cases, 9 use pattern-based function to transform data values and 7 use SQL statements with aggregation functions. In fact, our assessment is that the proposed framework allows to fully address all but one out of the 11 core functional requirements for R2RML [START_REF] Auer | Use cases and requirements for mapping relational databases to RDF[END_REF], namely the Apply a Function before Mapping. Finally, in our investigations we consider a class of shape schemas that are at the intersection of SHACL and ShEx. They are known to have desirable computational properties while remaining practical, and furthermore, they posses a sought-after feature of having an equivalent graphical representation (in the form of shape graphs) [START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF].

For a given source relational instance, a solution to data exchange is a target database (an RDF graph in our case) that satisfies the given set of st-tgds and the target schema (a shape schema in our case). The number of solutions may vary from none to infinitely many. The problem of consistency is motivated by the need for static verification tools that aim to identify potentially erroneous data exchange settings that are inconsistent i.e., admit no solution for some source database instance. In general, a consistent data exchange setting may yield many solutions to a given source instance and it is commonplace to apply the possible world semantics [START_REF] Imieliński | Incomplete information in relational databases[END_REF] to evaluate queries: a certain answer is an answer returned in every solution. It is standard practice to construct a solution that allows to easily compute certain answers. In the case of relational data exchange, universal solutions have been identified and allow to easily compute certain answers to conjunctive queries, or any class of queries preserved under homomorphism for that matter [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF]. Unfortunately, for relational to RDF data exchange with target shape schema, a finite universal solution might not exists, even if the setting is consistent and admits solutions. Also, the class of conjunctive queries, while adequate for expressing queries for relational databases, is less so for RDF. Query languages, like SPARQL, allowing regular path expressions with nesting have been proposed to better suit the needs of querying RDF [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF].

Our contributions are as follows. We formalize the framework of relational to RDF data exchange with target shape schema and IRI constructors, and we identify the class of constructive relational to RDF data exchange that uses shape schemas and full constructive source-to-target dependencies. We provide an effective characterization of consistency of constructive relational to RDF data exchange settings and show that the problem is coNP-complete. We propose a novel notion of universal simulation solution, that can be constructed for any consistent constructive relational to RDF data exchange setting, and use it to show tractability of computing certain answers to forward nested regular expressions. In an extended version of the present paper [START_REF] Boneva | Consistency and certain answers in relational to RDF data exchange with shape constraints[END_REF] we present full details and study further a number of extensions of our framework and show each time negative computational consequences.

Preliminaries

In this section we recall the standard notions of logic and databases [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Libkin | Elements of Finite Model Theory[END_REF].

Relational databases A relational schema is a pair R = (R, Σ fd ) where R is a set of relation names and Σ fd is a set of functional dependencies. Each relation name has a fixed arity and a set of attribute names. A functional dependency is written as usual R : X → Y where R is a relation name and X and Y are two sets of attributes of R. An instance I of R is a function that maps every relation name of R to a set of tuples over a set Lit of constants (also called literal values). The instance I is consistent if it satisfies all functional dependencies Σ fd . In the sequel, we often view an instance as a relational structure over the signature R.

Graphs An RDF graph G is a labeled graph whose nodes are divided into two kinds: literal nodes (Lit) and non-literal (Iri) nodes with only the latter allowed to have outgoing edges. Every node is labeled and we adopt the unique name assumption (UNA) i.e., no two node have the same label. Consequently, we equate nodes with their labels and by nodes(G) we denote the set of labels of nodes of G. Also, each edge is labeled with a predicate name, which is a non-null resource name Pred. As a result of using chase some nodes may be labeled with names nulls.

Shape Schemas A shapes schema is a pair S = (T , δ), where T is a finite set of type names and δ : T × Pred → (T ∪ {Literal }) × {1, ?, *, +} defines shape constraints. A shape constraint δ(T, p) = (S, µ), often presented as δ(T, p) = S µ , reads as follows: if a node has type T , then every neighbor reached with an outgoing p-edge must have type S and the number of such neighbors must be within the bounds of µ: precisely one if µ = 1, at most one if µ = ?, at least one if µ = +, and arbitrarily many if µ = *. Whenever µ = 1 or µ = ? we say that the predicate p is functional for type T .

Dependencies We employ the standard syntax of first-order logic (cf. [START_REF] Libkin | Elements of Finite Model Theory[END_REF]). In the sequel, we shall view graphs as relational structures using the ternary predicate Triple and monadic predicates in T ∪ {Literal } to indicate the types of nodes. Furthermore, in formulas we use the edge labels Pred as constant symbols. Later on, we additionally introduce functions that allow to map the values in relational databases to resource names used in RDF graphs, and we allow the use of function names in formulas but without nesting. Now, a dependency is a formula of the form ∀x.ϕ ⇒ ∃ȳ.ψ, where ϕ is called the body and ψ the head of the dependency, and we typically omit the universally quantified variables and write simply ϕ ⇒ ∃ȳ.ψ. A dependency is equalitygenerating (egd) if its body is a clause and its head consists of an equality condition x = y on a pair of variables. A tuple-generating dependency (tgd) uses clauses in both its head and its body. A tgd is full if it has no existentially quantified variables.

A number of previously introduced concepts can be expressed with dependencies. Any functional dependency is in fact an equality-generating dependency. Interestingly, any deterministic shape schema S can be expressed with a set Σ S of equality-and tuple-generating dependencies. More precisely, whenever δ(T, p) = S µ the set Σ S contains:

(TP) the type propagation rule: T (x) ∧ Triple(x, p, y) ⇒ S(y), (PF) the predicate functionality rule if µ = 1 or µ = ?:

T (x) ∧ Triple(x, p, y 1 ) ∧ Triple(x, p, y 2 ) ⇒ y 1 = y 2 , (PE) the predicate existence rule if µ = 1 or µ = +: T (x) ⇒ ∃y. Triple(x, p, y).

Constructive Relational to RDF Data Exchange

An n-ary IRI constructor is a function f : Lit n → Iri that maps an n-tuple of database constants to an RDF resource name. A IRI constructor library is a pair F = (F , F ), where F is a set of IRI constructor names and F is their interpretation. F is non-overlapping if all its IRI constructors have pairwise disjoint ranges. Definition 1. A relational to RDF data exchange setting with fixed IRI constructors is a tuple E = (R, S, Σ st , F), where R = (R, Σ fd ) is a source relational schema, S = (T , δ) is a target shape constraint schema, F = (F , F ) is an IRI constructor library, and Σ st is a set of source-to-target tuple generating dependencies ( st-tgds) whose bodies are formulas over R and heads are formulas over F ∪ T ∪ {Literal } without nesting of function symbols in F . E is constructive if the library of IRI constructors is non-overlapping and the st-tgds Σ st are full tgds. A typed graph J is a solution to E for a source instance I of R, iff J satisfies S and I ∪ J ∪ F |= Σ st . By sol E (I) we denote the set of all solutions for I to E .

In the reminder we fix a constructive data exchange setting E , and in particular, we assume a fixed library of IRI constructors F. Since we work only with constructive data exchange settings, w.l.o.g. we can assume that the heads of all st-tgds consist of one atom only. We point out that while a constructive data exchange setting does not use egds, our constructions need to accommodate egds and tgds coming from the shapes schema.

The standard chase procedure allows to construct a solution to E for a source instance I. However, such solution might not exist either because the chase fails due to an unsatisfiable egd, or because it never terminates. The core pre-solution for I to E is the result J 0 of chase on I with the st-tgds Σ st and all TP rules of S. In essence J 0 is obtained by exporting the relational data to RDF triples with Σ st and then propagating any missing types according to S but without creating any new nodes with PE rules. This process does not introduce any null values and always terminates yielding a unique result. Naturally, J 0 is included in any solution J ∈ sol E (I).

Consistency

Recall that a data exchange setting E is consistent if every consistent source instance I of R admits a solution to E . 1 Throughout this section we fix a data exchange setting E = (R, S, Σ st , F) and study its consistency.

Note that only predicate functionality egds can bring inconsistency. We show that E is inconsistent if and only if there is a source instance I and a predicate functionality egd T (x) ∧ Triple(x, p, y) ∧ Triple(x, p, y ) ⇒ y = y in E such that all solutions to E for I need to satisfy the body of the above rule but y and y are not equatable. We distinguish two situations, that together provide a necessary and sufficient condition for E to be (in-)consistent.

value inconsistency when y and y are different constants (see Section 4), node kind inconsistency when one among y, y is a literal and the other is not (see Section 4).

Value Consistency Let Σ PF S be the set of predicate functionality rules from Σ S as defined in Section 3.

An instance

I of R is called value inconsistent if J |= Σ PF S ,
where J is the core pre-solution for I to E . The data exchange setting E is called value inconsistent if there exists a consistent instance I of R that is value inconsistent.

We now sketch a decision procedure value-inconsistent(E ) that tests whether E is value inconsistent by constructing a value inconsistent source instance whenever such exists. It is illustrated on the following example data exchange setting. The relational signature contains symbols R, S both of arity two, and the IRI constructors are {g 0 , g, f } all of arity one. The shapes schema S is given by δ(U 0 , r) = U * , δ(U, q) = T * , δ(T, p) = Literal 1 , and the st-tgds are:

(σ1) R(x 0 , x 1 ) ⇒ U 0 (g 0 (x 1 )) R(x, z) ∧ S(x, y ) ⇒ Triple(f (x ), p, y ) (σ) (σ2) R(x 1 , x 2 ) ⇒ Triple(g 0 (x 1 ), r, g(x 2 )) S(x, y) ⇒ Triple(f (x), p, y) (σ ) (σ3) R(x 2 , x) ⇒ Triple(g(x 2 ), q, f (x))
Using that IRI constructors have pairwise disjoint ranges, it follows from the definition that a source instance is value inconsistent iff its core pre-solution contains a triple of facts of the form {T (f (x)), Triple(f (x), p, b), Triple(f (x), p, b )} for some function symbol f , and such that x and y = y are constants and the predicate p is functional for type T in S. We call such triple of facts a violation and (T, p, f ) its sort. There is a finite number of possible violation sorts for E . On the example, the possible violation sorts are (T, p, f ), (T, p, g 0 ) and (T, p, g), as the unique functional predicate rule is for type T and predicate p. The procedure value-inconsistent(E ) enumerates all violation sorts and for each of them tries to build a value inconsistent instance.

So consider the violation sort (T, p, f ). Although none of the st-tgds heads contains a fact of the form T (f ( )), we remark that such fact can be obtained using type propagation rules. Indeed, consider the source instance I = {R(x 0 , x 1 ), R(x 1 , x 2 ), R(x 2 , x)} obtained as the union of the bodies of st-tgds (σ 1 ), (σ 2 ) and (σ 3 ), where variables are used as constants. Applying on I the st-tgds (σ 1 ), (σ 2 ) and (σ 3 ) together with the type propagation rules for U 0 , r and U, q yields the target instance J = I ∪ {U 0 (g 0 (x 1 )), Triple(g 0 (x 1 ), r, g(x 2 )), U (g(x 2 )), Triple(g(x 2 ), q, f (x)), T (f (x))} which does contain a fact T (f (x)) as required. We show that for given T and f , a fact of the form T (f ( )) exists in some core pre-solution w.r.t. E if and only if E contains an appropriate finite and elementary (i.e. without repetitions) sequence of st-tgds such as (σ 1 ), (σ 2 ),(σ 3 ) above that, combined with type propagation rules, allows to obtain T (f ( )). Now we need to add facts of the forms Triple(f (x), p, y) and Triple(f (x), p, y ). This is done using the st-tgds (σ) and (σ ), called contentious for f and p. So consider I = I ∪ {S(x, y), R(x, z), S(x, y )} obtained by adding the bodies of (σ) and (σ ) to I . Its core pre-solution is J = J ∪ {Triple(f (x), p, y), Triple(f (x ), p, y ), Literal (y), Literal (y )} and it contains a violation of sort (T, p, f ) whenever y = y . Thus, I is an instance over the source signature that is value inconsistent. This does not imply yet that E is inconsistent, as I might not be consistent w.r.t the source functional dependencies. If the first attribute of S is a primary key, then y = y , I is not value inconsistent and we can actually show that the example data exchange setting E is consistent. Otherwise, I is value inconsistent, and so is E .

Here is a NP procedure that checks value inconsistency by guessing an inconsistent source instance:

guess a violation sort (T, p, f ) of E , guess an elementary sequence of st-tgds σ 1 , . . . , σ n that allows to generate a fact T (f ( )), guess two st-tgds σ, σ contentious for f and p, construct in PTIME a source instance I as the union of the bodies of σ 1 , . . . , σ n , σ, σ (after appropriate renaming of variables), show in PTIME that I satisfies the source functional dependencies.

Theorem 1. Value consistency of a data exchange setting is in coNP.

Node Kind Consistency Node kind inconsistency is specific to relational to RDF data exchange due to the presence of two types of values, namely IRIs and literals. It corresponds to situations in which two values are equated by a predicate functionality rule while one of them is a literal (that is, has type Literal ) but the other is not (that is, has a type T ∈ T ). Therefore we identify node kind inconsistency with the fact that a node has both types Literal and T = Literal .

For a typed graph J and a node n ∈ nodes(J), let types

J (n) = {T ∈ T ∪ {Literal } | T (n) ∈ J}.
For a source instance I, define its sets of co-occurring types as

CoTypes(I) = {types J (n) | J ∈ sol E (I), n ∈ nodes(J)}. Let CoTypes(E ) = I instance of R CoTypes(I). A source instance I is called node kind inconsistent if CoTypes(I) contains a set X s.t. {Literal , T } ⊆ X for some T in T . The data exchange setting E is called node kind inconsistent if there is a node kind inconsistent instance I of R.
We show that E is node kind inconsistent iff CoTypes(E ) contains a set X such that {Literal , T } ⊆ X for some T in T . Furthermore, for any X ⊆ T ∪ {Literal }, we can test in PTIME whether X belongs to CoTypes(E ). Therefore, Proposition 1. Checking node kind inconsistency of E is in NP.

The central claim of this section is Theorems 2 below. The lower bound is shown using a reduction to the complement of SAT. Theorem 2. A constructive relational to RDF data exchange setting E is consistent iff it is value consistent and node kind consistent. Checking consistency of a constructive relational to data exchange setting is decidable and coNP-complete.

Certain Query Answering

In this section we investigate computing certain answers to Boolean queries focusing on a subclass of nested regular expressions (NREs). In [START_REF] Boneva | Consistency and certain answers in relational to RDF data exchange with shape constraints[END_REF] we show that our results extend to non-Boolean queries but also that handling the full class of NREs leads to an increase in computational complexity.

Throughout this section we fix a constructive data exchange setting E = (R, S, Σ st , F) and assume E is consistent. We recall that for a Boolean graph query Q, true is the certain answer to Q in I w.r.t. E iff true is the answer to Q in every solution to E for I.

The standard approach to computing certain answers is to construct a universal solution with the chase and evaluate the query against it (and to drop any answers with null values) [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF]. However, in our case a finite universal solution may not exist because the chase may enter an infinite loop due to PE rules when the shape schema is strongly-recursive i.e., it has a cycle with multiplicities of 1 and +. Infinite chase corresponds to an attempt to unravel such cycles by inventing new nodes ad infinitum. Instead, we construct a solution where a new node is invented only if one satisfying precisely the same types has not been invented before. Such a solution is not universal, but interestingly, it has a different flavor of universality, one that can be captured with the standard notion of graph simulation: any solution can be simulated in it. We also show that this notion of universality is good enough for classes of queries that are robust under simulation, and we identify a practical class of forward nested regular expressions with this property. This yields a practical class of queries with tractable certain answers.

Nested regular expressions

In this paper we work with the class of nested regular expressions (NREs) that have been proposed as the navigational core of SPARQL [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF]. In essence, NREs are regular expressions that use concatenation •, union +, Kleene's closure * , inverse -, and permit nesting and testing node and edge labels. We refer the reader to [START_REF] Boneva | Consistency and certain answers in relational to RDF data exchange with shape constraints[END_REF] for detailed definition. We point out that NREs are incompatible with conjunctive queries but even forward NREs capture the subclass of acyclic conjunctive queries. Also, forward NREs properly capture regular path queries.

Graph simulation and robust query classes

We adapt the classic notion of graph simulation to account for null values. Formally, a simulation of a graph G by a graph H is a relation R ⊆ nodes(G)×nodes(H) such that for any (n, m) ∈ R, we have 1) n is a literal node if and only if m is a literal node, 2) if n is not null, then m is not null and n = m, and 3) for any outgoing edge from n with label p that leads to n there is a corresponding outgoing edge from m with label p that leads to m such that (n , m ) ∈ R. The set of simulations is closed under union, and consequently, there is always one maximal simulation, and if (n, m) is contained in it, we say that n is simulated by m. Also, we say that G is simulated by H if every node of G is simulated by a node of H. We are interested in simulations because they capture the essence of exploring a graph by means of following outgoing edges only. Definition 2. A class Q of Boolean queries on graphs is robust under simulation iff for any query Q ∈ Q and any two graph G and

H such that G is simulated by H, if Q is true in G, then Q is true in H.
Naturally, the class of forward NREs has this very property.

Lemma 1. The class of forward nested regular expressions is robust under simulation.

Universal simulation solution When dealing with classes of queries that are robust under simulation we employ simulation instead of homomorphism to define a solution that allows to find all certain answers. Definition 3. A typed graph U is a universal simulation solution to E for I iff U is simulated by every solution J to E for I.

And indeed, a universal simulation solution does allow us to capture certain answers for queries from classes robust under simulation. Theorem 3. Let Q be a class of Boolean graph queries robust under simulation. For any query Q ∈ Q and any consistent instance I of R, true is the certain answer to Q in I w.r.t. E if and only if true is the answer to Q in a universal simulation solution to E for I.

The main challenge is in constructing a universal simulation solution. The precise construction is presented in [START_REF] Boneva | Consistency and certain answers in relational to RDF data exchange with shape constraints[END_REF] and we outline it roughly. First we begin with the core pre-solution that is obtained from the source instance I with the the st-tgds Σ st and the TP rules for S that propagate the types according to the shape schema. Then, we add fresh null values that ensure satisfaction of the schema, as required by the PE rules for S. We point out that each null node corresponds to a subset of types of S that it needs to satisfy, which bounds their number by 2 |Γ | , and furthermore, using the Chinese reminder theorem we show that this bound is tight. To ensure that the produced universal simulation solution has the smallest size, we employ the standard technique of quotient by bisimulation of the obtained graph [START_REF] Tzitzikas | Blank node matching and RDF/S comparison functions[END_REF]. Complexity We can now characterize the data complexity of certain query answering. Recall that data complexity assumes the query and the data exchange setting to be fixed, and thus of fixed size, and only the source instance is given on the input. Consequently, the size of universal simulation solution U 0 is polynomially-bounded by the size of I. Since the data complexity of evaluating NREs is know to be PTIME [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF], we get the following result.

Theorem 5. The data complexity of computing certain answers to forward nested regular expressions w.r.t. constructive relational to RDF data exchange setting is in PTIME.

Related Work and Conclusions

R2RML is a W3C standard language for defining custom relational to RDF mappings [START_REF] Das | R2RML: RDB to RDF mapping language[END_REF], other languages such as YARRRML [START_REF] Heyvaert | Declarative rules for Linked Data generation at your fingertips![END_REF] are compiled to R2RML but they do not consider target constraints. Data exchange has been considered for graph databases with varying expressive power of mapping formalisms such as nested regular expressions [START_REF] Barceló | Schema mappings and data exchange for graph databases[END_REF][START_REF] Boneva | Graph data exchange with target constraints[END_REF], which is however incomparable with shape schemas. In [START_REF] Boneva | ShERML: Mapping relational data to RDF[END_REF] we have demonstrated a graphical tool for defining constructive relational to RDF mappings. Our results do not follow from the exists results on the standard relational data exchange [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF], which are either too limited in their expressive power [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Fagin | Data exchange: Semantics and query answering[END_REF] or come with a significant complexity penalty [START_REF] Amano | XML schema mappings: Data exchange and metadata management[END_REF][START_REF] Bojańczyk | Solutions in XML data exchange[END_REF][START_REF] Arenas | Query languages for data exchange: Beyond unions of conjunctive queries[END_REF][START_REF] Arenas | XML data exchange: Consistency and query answering[END_REF][START_REF] Bienvenu | Regular path queries in lightweight description logics: Complexity and algorithms[END_REF][START_REF] Calvanese | Answering regular path queries in expressive description logics via alternating tree-automata[END_REF] We have presented a data exchange framework for modeling R2RML scripts, we have studied the problems of consistency and certain query answering, and characterized their complexity. In [START_REF] Boneva | Consistency and certain answers in relational to RDF data exchange with shape constraints[END_REF] we also show that extending the framework in a number of natural directions generally leads to an increase of complexity.

Theorem 4 .

 4 For an instance I of R, we can construct a size-minimal universal simulation solution U 0 in time polynomial in the size of I and exponential in the size of S. The size of U is bounded by a polynomial in the size of I and an exponential function in the size of S.

This was called absolute consistency in[START_REF] Bojańczyk | Solutions in XML data exchange[END_REF].


Wei Li

Olaf J Borkiewicz

Matthieu Saubanère

#,∆ Marie-Liesse Doublet

Delphine Flahaut

Peter J Chupas

Karena W Chapman

Damien Dambournet

Atomic Structure of 2 nm Size Metallic Cobalt Prepared by Electrochemical Conversion: An in Situ Pair Distribution Function Study

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Metallic cobalt displays numerous properties in the field of catalysis, magnetism and biomedicine that largely depend on the size/shape and structural features. [START_REF] Price | Cobalt-Based Anisotropic Particles Prepared by the Polyol Process[END_REF][2][START_REF] Jun | Nanoscaling Laws of Magnetic Nanoparticles and Their Applicabilities in Biomedical Sciences[END_REF] The latter point is not trivial as metallic Co presents several polymorphs including the face-centered-pack (fcc) and hexagonal-close-pack (hcp) arrangements which have close formation energies, i.e., hcp is only 20 meV more stable than fcc. [START_REF] Jain | Commentary: The Materials Project: A Materials Genome Approach to Accelerating Materials Innovation[END_REF] Both polymorphs are structurally related, built from a closepacking of atoms and differing from the stacking sequence of this common plane, i.e., the stacking sequences ABA and ABC produce the hcp and fcc crystal structures (Figure S1), respectively. Downsizing the particle size can lead to the hcp-fcc intergrowth resulting in a disordered structure featuring stacking faults. [START_REF] Longo | Crossing the Boundary between Face-Centred Cubic and Hexagonal Close Packed: The Structure of Nanosized Cobalt Is Unraveled by a Model Accounting for Shape, Size Distribution and Stacking Faults, Allowing Simulation of XRD, XANES and EXAFS[END_REF] Typically, such a disordered structure arises from the fact that the two layers A-B can be followed by either C (to form fcc structure) or A (hcp structure). The level of stacking faults can be quantified by a probability of stacking faults. For example, a 50% probability of stacking faults implies that there is an equal proportion of hcp and fcc sequences, a situation referring to a randomly stacked layers. [START_REF] Sławiński | Structural Arrangement in Close-Packed Cobalt Polytypes[END_REF] As a technological relevant material, significant works were performed to describe the atomic structure of Co nanoparticles including the simulation of X-ray diffraction powder pattern by the Debbye equation, 5,6 59 Co solid-state NMR, [START_REF] Speight | ^{59}\text{C}\text{o}$ NMR Study of the Allotropic Phase Transformation in Small Ferromagnetic Cobalt Particles[END_REF] and X-ray absorption spectroscopy [START_REF] Longo | Crossing the Boundary between Face-Centred Cubic and Hexagonal Close Packed: The Structure of Nanosized Cobalt Is Unraveled by a Model Accounting for Shape, Size Distribution and Stacking Faults, Allowing Simulation of XRD, XANES and EXAFS[END_REF][START_REF] Sprouster | Fcc-Hcp Phase Transformation in Co Nanoparticles Induced by Swift Heavy-Ion Irradiation[END_REF][START_REF] Sciortino | Structural Characterization of Surfactant-Coated Bimetallic Cobalt/Nickel Nanoclusters by XPS, EXAFS, WAXS, and SAXS[END_REF] .

Solving the atomic structure of disordered and ultra-small particles was called the "nanostructure problem". [START_REF] Billinge | The Problem with Determining Atomic Structure at the Nanoscale[END_REF] The reason is that both finite size and disorder effects contribute to the loss of long-range order, which precludes the use of conventional x-ray diffraction. The pair distribution function (PDF) obtained by Fourier Transform of the so-called correlation function, [START_REF] Keen | A Comparison of Various Commonly Used Correlation Functions for Describing Total Scattering[END_REF] represents the probability of finding a pair of atoms separated from a distance r. The pair distribution function technique as total scattering analysis can probe the short to long-range order and can therefore be used whatever the crystalline state of the material. It is, therefore, one of the most suited technique to study the atomic structure of ultra-small objects. [START_REF] Masadeh | Quantitative Size-Dependent Structure and Strain Determination of CdSe Nanoparticles Using Atomic Pair Distribution Function Analysis[END_REF][START_REF] Shyam | Structural and Mechanistic Revelations on an Iron Conversion Reaction from Pair Distribution Function Analysis[END_REF][START_REF] Jensen | Polymorphism in Magic-Sized Au144(SR)60 Clusters[END_REF] Solution-based synthesis has been largely used to control the size and shape of metallic Co nanoparticles. [START_REF] Puntes | Colloidal Nanocrystal Shape and Size Control: The Case of Cobalt[END_REF][START_REF] Lu | Magnetic Nanoparticles: Synthesis, Protection, Functionalization, and Application[END_REF] Another approach that allows synthetizing ultra-small, i.e., < 5 nm, and monodisperse nanoparticles relies on alkaline-ion driven electrochemical conversion. [START_REF] Poizot | Nano-Sized Transition-Metal Oxides as Negative-Electrode Materials for Lithium-Ion Batteries[END_REF] In such reactions, a multi-electron process occurs leading to the reduction of the transition metal to form metal M 0 and lithiated nano-composite according to: M z+ Xy + zLi + + ze -↔ M 0 + yLiz/yX, where X comprised O, N, S, P, F, and H. [START_REF] Poizot | Nano-Sized Transition-Metal Oxides as Negative-Electrode Materials for Lithium-Ion Batteries[END_REF][START_REF] Cabana | Beyond Intercalation-Based Li-Ion Batteries: The State of the Art and Challenges of Electrode Materials Reacting Through Conversion Reactions[END_REF][START_REF] Li | Reversible Formation and Decomposition of LiF Clusters Using Transition Metal Fluorides as Precursors and Their Application in Rechargeable Li Batteries[END_REF][START_REF] Badway | Carbon Metal Fluoride Nanocomposites High-Capacity Reversible Metal Fluoride Conversion Materials as Rechargeable Positive Electrodes for Li Batteries[END_REF][START_REF] Oumellal | Metal Hydrides for Lithium-Ion Batteries[END_REF] One of the particularity of this process is the disintegration of the parent particle upon reduction, leading to ultra-small M/LiX composite with typical metallic cluster sizes ranging from 1 to 3 nm. [START_REF] Cabana | Beyond Intercalation-Based Li-Ion Batteries: The State of the Art and Challenges of Electrode Materials Reacting Through Conversion Reactions[END_REF] During the formation of the metal nanoparticles, their structure evolves and adapts to the close environment which is related to interfaces with LiX and MX and the passivating film arising from the electrolyte decomposition and MX/LiX. [START_REF] Shyam | Structural and Mechanistic Revelations on an Iron Conversion Reaction from Pair Distribution Function Analysis[END_REF][START_REF] Dalverny | Interface Electrochemistry in Conversion Materials for Li-Ion Batteries[END_REF] Much progresses have been made toward the fundamental understanding of the conversion-based mechanisms. [START_REF] Dalverny | Interface Electrochemistry in Conversion Materials for Li-Ion Batteries[END_REF][START_REF] Wang | Tracking Lithium Transport and Electrochemical Reactions in Nanoparticles[END_REF][START_REF] Hu | Origin of Additional Capacities in Metal Oxide Lithium-Ion Battery Electrodes[END_REF][START_REF] Abraham | Investigating the Complex Chemistry of Functional Energy Storage Systems: The Need for an Integrative, Multiscale (Molecular to Mesoscale) Perspective[END_REF][START_REF] Wiaderek | Comprehensive Insights into the Structural and Chemical Changes in Mixed-Anion FeOF Electrodes by Using Operando PDF and NMR Spectroscopy[END_REF][START_REF] Wiaderek | Mesoscale Effects in Electrochemical Conversion: Coupling of Chemistry to Atomic-and Nanoscale Structure in Iron-Based Electrodes[END_REF][START_REF] Ma | Atomistic Insights into the Conversion Reaction in Iron Fluoride: A Dynamically Adaptive Force Field Approach[END_REF] Moreover, these reactions provide also unique opportunities to design ultra-small objects with unique structural and physico-chemical properties. [START_REF] Hu | Electrochemical Lithiation Synthesis of Nanoporous Materials with Superior Catalytic and Capacitive Activity[END_REF] In the present work, we investigated the lithium electrochemical conversion reaction occurring in CoF2, a potential high capacity electrode. We undertook to investigate the atomic structure of metallic cobalt formed upon Li-driven electrochemical reaction. By using in-situ pair distribution function, we concluded on the formation of 2-nm size of Co featuring hcp-fcc intergrowth. Our study further supports the suitability of the PDF method to solve complex nanostructure and provides novel insight into the complexity of conversion reactions.

RESULTS and DISCUSSION

The electrochemical reduction of CoF2 vs. Li + /Li is characterized by a single plateau region typical of a phase transition as observed for conversion processes (Figure 1). A voltage plateau at 1.2 V leads to a capacity of ca. 800 mAh/g. According to the conversion reaction: CoF2 + 2Li = Co 0 + 2 LiF, the theoretical capacity is 553 mAh g -1 which indicates the completion of the reaction along with extra capacities arising from the decomposition of the electrolyte (Figure S2). During the charge process, a plateau region is observed at ca. 3 V highlighting voltage hysteresis in agreement with literature data. [START_REF] Teng | Investigation of the Conversion Mechanism of Nanosized CoF2[END_REF] Moreover, the reaction is not completely reversible as the charge capacity reaches around 400 mAh g -1 , equivalent to 1.5 exchanged electrons. High-resolution transmission electron microscopy was performed on a fully reduced CoF2 electrode. Figure 2 shows TEM images before and after the discharge. It reveals that the conversion process induces the pulverization of the pristine CoF2 particles into ca. 2 nm size of metal cobalt characterized by a darker image contrast. Lattice fringes indicated that the particles are crystallized. Moreover, the particles appear agglomerated but not interconnected as found in metallic Fe formed by electrochemical conversion of FeF2. [START_REF] Wang | Conversion Reaction Mechanisms in Lithium Ion Batteries: Study of the Binary Metal Fluoride Electrodes[END_REF] Fast Fourier Transformation (FFT) was performed on a large number of nanoparticles. The analysis revealed inter-reticular distances that are characteristics of both hcp and fcc polymorphs (Table S1). Although both polymorphs feature close inter-reticular distances, we clearly distinguished both polymorphs signatures with distances at ca. To capture the real atomic changes occurring during the electrochemical reaction, we turned to in-situ experiments. [START_REF] Luo | Atomic Resolution Study of Reversible Conversion Reaction in Metal Oxide Electrodes for Lithium-Ion Battery[END_REF][START_REF] Chapman | Emerging Operando and X-Ray Pair Distribution Function Methods for Energy Materials Development[END_REF][START_REF] Yu | Understanding Conversion-Type Electrodes for Lithium Rechargeable Batteries[END_REF] We used in-situ high energy X-rays (λ = 0.2128 Å) data obtained with the AMPIX (Argonne's Multi-Purpose In situ X-ray) electrochemical cell (see experimental section). [START_REF] Borkiewicz | The AMPIX Electrochemical Cell: A Versatile Apparatus for in Situ X-Ray Scattering and Spectroscopic Measurements[END_REF] The typical x-ray diffraction powder pattern of a fully discharged electrode is shown in Figure 3. For the sake of clarity, the data were re-scaled in two-theta at the wavelength of copper λCu=1.54 Å. Besides the expected Bragg peaks of LiF phase, we observed broad peaks belonging to metallic cobalt. The significant peak broadening is typical of ultra-small nanoparticles. Moreover, hcp-fcc intergrowth can also contribute to the Bragg peaks broadening. [START_REF] Sławiński | Structural Arrangement in Close-Packed Cobalt Polytypes[END_REF] Based on this pattern, it is again difficult to distinct whether the stabilized phase is made of hcpfcc intergrowth or physical mixture. A broad peak located at ca. 51.5° (2θ), however, allows to identify the presence of the fcc form. The presence of the hcp signature observed by TEM, however, cannot be clearly identified on this XRD pattern. To further support the description of the atomic structure of metallic Co prepared by electrochemical reaction, a principal component analysis (PCA) of the operando PDF data were undertaken to assess the number of independently varying components involved in the reaction. [START_REF] Chapman | Applications of Principal Component Analysis to Pair Distribution Function Data[END_REF] This multivariable statistical method allows to treat a large set of volume data without any prior consideration of structural models. The scree plot that represents the fraction of total variance To understand the atomic structure of electrochemically formed metallic Co, we first attempt to refine the PDF data after completion of the discharge process (Figure 5). Using the hcp structure does not lead to a satisfying refinement, i.e., Rw = 36.4 %. The quality of the fit significantly improved when modelling the PDF with the fcc polymorph (Rw = 24.4 %). In the difference curve, however, a peak located at 4.8 Å is not captured by the model. This peak is characteristic of Co-Co distance found in the ABA sequence of hcp structure (Figures S1,S4) which further attests for the formation of hcp-fcc intergrowth. The accurate description of stacking faulted structure implies to build model systems that can be refined over the experimental data using programs such as Discus, FAULTS or DIFFAX. [START_REF] Proffen | DISCUS: A Program for Diffuse Scattering and Defect-Structure Simulation[END_REF][START_REF] Casas-Cabanas | A Program for Refinement of Structures with Extended Defects[END_REF][START_REF] Treacy | A General Recursion Method for Calculating Diffracted Intensities from Crystals Containing Planar Faults[END_REF] Another approach to describe the stacking faulted structure consists of using a mixed-phase model. [START_REF] Yang | Confirmation of Disordered Structure of Ultrasmall CdSe Nanoparticles from X-Ray Atomic Pair Distribution Function Analysis[END_REF] Although this method is less accurate, it is less time-consuming and was shown to be suited for nanoparticles size of 2-nm. [START_REF] Yang | Confirmation of Disordered Structure of Ultrasmall CdSe Nanoparticles from X-Ray Atomic Pair Distribution Function Analysis[END_REF] Using the mixed-phase model, the final refinement was good with a further improvement of the fit to Rw = 19.3 % (Figure 5). The refined parameter values were gathered in Table 1. The quantitative phase analysis showed a slightly larger proportion of the fcc phase which seems to agree with literature suggesting that the fcc structure is more stable than the hcp for small particles. [START_REF] Kitakami | Size Effect on the Crystal Phase of Cobalt Fine Particles[END_REF] Moreover, the refined unit cell parameter of the fcc phase was a = 3.538 Å, a value close to that reported for bulk fcc. [START_REF] Owen | Effect of Grain Size on the Crystal Structure of Cobalt[END_REF] The lattice parameters of the hcp phase, however, are strikingly different from the bulk values (a = 2.506 Å and c = 4.069 Å), particularly along the c-axis. [START_REF] Owen | Effect of Grain Size on the Crystal Structure of Cobalt[END_REF][START_REF] Feygenson | Implications of Room Temperature Oxidation on Crystal Structure and Exchange Bias Effect in Co/CoO Nanoparticles[END_REF] This might be due to a slightly larger interlayer in the fcc stacking as compared to hcp stacking. Hence, the presence of hcp stacking should have a slightly larger interlayer to match those of the fcc structure. Finally, the refined scattering domain was around 2-nm which is in good agreement with the particle sizes observed by TEM. To monitor structural changes occurring during electrochemical reactions, we refined the PDF data recorded during the first cycle. Upon discharge, the analysis shows the progressive conversion of CoF2 into metallic Co occurring within the plateau region (Figure 7). We note that the unit cell parameters of CoF2 did not vary upon reduction suggesting the absence of any insertion reaction prior to the conversion process (Figure S5). We used the mixed-phase modelling to detect the formation of disordered structure made of hcp-fcc intergrowth along the course of the discharge reaction. The results showed the phase's content remains constant during the discharge reaction suggesting that disordered nanoparticles made of hcp-fcc intergrowth are continuously generated by the electrochemical reduction of CoF2. This is good agreement with the PCA that revealed only one Co-based conversion product. We note that the estimated standard deviation obtained on the metallic Co phase fractions decreases as the reaction progresses. Moreover, we monitored the changes in the unit cell parameters of the two-phase (Figure S6) with similar unit cell parameters for both phases.

Upon charge, the voltage plateau located at 3 V was associated with the reformation of CoF2 as confirmed by PDF refinement (Figure 7, Figure S7). Similarly, to other conversion-based electrodes, the re-oxidized phase features short-range ordering (denoted as amorphous) with a scattering domain of 14 Å. At the end of the charge, the ratio between the fcc and hcp remains almost constant again supporting the mechanism based on the stabilization of nanoparticles made of hcp-fcc intergrowth.

CONCLUSION

In summary, we investigated the structural evolution of CoF2 during the Li-driven electrochemical conversion by means of in-situ PDF method. We found that CoF2 is converted to 2-nm size metallic cobalt whose atomic structure consists of nanoparticles made of hcp-fcc intergrowth. Upon charging, a highly disordered CoF2 phase is formed back proving the reversibility of the reaction. This study provides unique insights into the atomic structural description of conversion-based products and shows that efforts on understanding conversion processes should be pursued to fully describe these complex reactions and enabled practical applications.

EXPERIMENTAL SECTION PDF analysis. For in-situ PDF analysis, electrodes were made by mixing active material CoF2 (51 wt%), carbon ("super P", Alfa Aesar), carbon black and PTFE binder (Sigma-Aldrich) into pellet with total mass of 21.7 mg, 10 mm diameter and 120-180 µm thickness. Electrode pellet, fiber separator (Whatman GF/A), electrolyte (1 M LiPF6 in 3:7 v:v ethylene carbonate: dimethylcarbonate (EC:DMC) from Tomiyama Pure Chemical Industries) and lithium foil as counter electrode were assembled into the AMPIX [START_REF] Borkiewicz | The AMPIX Electrochemical Cell: A Versatile Apparatus for in Situ X-Ray Scattering and Spectroscopic Measurements[END_REF] electrochemical cell under Ar atmosphere in a glovebox. Cell was cycled galvanostatically against lithium at a C/20 rate (27.74 mA/g) within the voltage window 1-4.3 V (see Figure 1). X-ray total scattering data were collected every 30 min.

X-ray total scattering data were collected at the 11-ID-B beamline at the Advanced Photon Source, Argonne National Laboratory, using high energy X-rays (λ = 0.2128 Å) to high values of momentum transfer Qmax = 18 Å -1 . [START_REF] Chupas | Rapid-Acquisition Pair Distribution Function (RA-PDF) Analysis[END_REF][START_REF] Chupas | Applications of an Amorphous Silicon-Based Area Detector for High-Resolution, High-Sensitivity and Fast Time-Resolved Pair Distribution Function Measurements[END_REF] The raw total scattering data were integrated in Fit2D. [START_REF] Hammersley | Two-Dimensional Detector Software: From Real Detector to Idealised Image or Two-Theta Scan[END_REF] PDFs, G(r) were obtained by Fourier transform after eliminating Kapton and background contributions within PDFgetX2. [START_REF] Qiu | PDFgetX2: A GUI-Driven Program to Obtain the Pair Distribution Function from X-Ray Powder Diffraction Data[END_REF] The refinement of the PDF data was performed using PDFgui. [START_REF] Farrow | PDFfit2 and PDFgui: Computer Programs for Studying Nanostructure in Crystals[END_REF] The Qdamp was fixed to 0.04. The structural models used were CoF2, graphite (to account for the large amount of carbon within the electrode), LiF, Co hcp, Co fcc. The refined parameters includes lattice parameters, scale factor, sratio (i.e. low-r to high-r PDF peak ratio correction due to the correlated motion of bonded atoms [START_REF] Egami | Underneath the Bragg Peaks: Structural Analysis of Complex Materials[END_REF] ), spdiameter (i.e. particle diameter), and isotropic atomic displacement factors (ADPs). For the twophase refinement including fcc and hcp structural models, ADP for Co, sratio and spdiameter were refined and constrained to an identical value for both polymorphs. The phase fraction obtained for the fully discharged electrode gave 25 wt.% of metallic Co, 28 wt.% of LiF and 46 wt.% of carbon. These proportions are close to those expected based on the electrode composition and completion of the conversion reaction. The purity of the pristine CoF2 was confirmed by PDF refinement (Figure S8).

The quality of the refinement is quantified by the reliability factor weighted R-value, denoted as Rw. The R-value describes the difference between the experimental observation (data)

and the calculated value (fit) for a single data point. The Rw is the R-value weighted for data point i, and is given by the formula: with and being the observed (data) and calculated (fit) PDF and w(ri) the weight for each data point.

TEM analysis. To perform TEM analysis, coin cells were disassembled in a glove box. The discharged electrodes were washed with DMC to remove LiPF6 and EC. After evaporating DMC, the electrodes were analyzed by TEM using a JEOL 2010 UHR microscope operating at 200 kV equipped with a TCD camera.

X-ray Photoelectron Spectroscopy (XPS). XPS analyses were performed on a Kratos Axis

Ultra spectrometer with a focused monochromatized Al Kα radiation (1486.6 eV). The analysis chamber was in a 5x10 -9 mbar vacuum. The applied current was 10 mA and the voltage 10 kV.

The spectrometer pass energy was set to 20 eV to record the core peaks. The size of the excitation beam was 700x400 µm 2 . Surface charging was minimized using a neutralizer gun which sprays low energy electrons over the sample surface. The samples were prepared in a glove box under Ar and transferred to the XPS analyzer under a controlled atmosphere to prevent any surface contamination with ambient atmosphere. The samples were fixed on the sample holder with a Cu double tape. All the binding energy (B.E.) scale was calibrated from the adventitious carbon C 1s peak set at 285.0 eV. We performed at least three analyses for each sample. The quantification of atoms for surface composition was based on Scofield's relative sensitivity factors. [START_REF] Scofield | Hartree-Slater Subshell Photoionization Cross-Sections at 1254 and 1487 eV[END_REF] ASSOCIATED CONTENT Supporting Information. XPS analysis, crystallographic data of Co hcp and Co fcc, structural parameters obtained from PDF refinement, scree plot, PDF refinement of the charged electrode.

This material is available free of charge via the Internet at http://pubs.acs.org.

Figure 1 .

 1 Figure 1. Galvanostatic discharge-charge curves of CoF2 vs. Li + /Li. Cells were cycled under 27.74 mA.g -1 within 1-4.3 V voltage range. The curves correspond to the ones recorded during

  1.92 Å characteristic of the (101) plane of the hcp structure (Figure 2, inset), and at ca. 1.8 Å characteristic of the (200) plane of the fcc structure. The smallest size of the particles, however, prevents to discern whether these particles are made of hcp-fcc intergrowth or physical mixture.

Figure 2 .

 2 Figure 2. TEM images of the pristine CoF2 and the CoF2 electrode discharged to 1 V.

Figure 3 . 4 .

 34 Figure 3. X-ray diffraction patterns of CoF2 electrode before and after the first discharge. The

Figure 4 .

 4 Figure 4. Selected PDFs of cycled CoF2 electrode vs. Li + /Li.

(

  Figure S3) indicates that there are only two significant components. The two main components along with their weighting during the discharge reaction are shown in Figure 5. The first component includes features related to the CoF2 precursor and has a decreasing contribution during the reaction. The second component includes features related to metallic Co and increases in contribution during the reaction. The absence of a significant third component ruled out the formation of a mixture of hcp and fcc phases, suggesting the formation of hcp-fcc intergrowth.

Figure 5 .

 5 Figure 5. The first two components obtained by the PCA analysis of PDF data obtained during

Figure 5 .

 5 Figure 5. Fits to the experimental PDFs with hcp, fcc and fcc-hcp models. The orange arrow

Table 1 .

 1 Refined parameter values obtained from PDF refinement of the fully discharged electrode using a mixed-phase modelling to account for hcp-fcc intergrowth.

Figure 7 .

 7 Figure 7. Quantitative phase analysis obtained by PDF refinements during the first cycle.

ACKNOWLEDGMENT

This research used resources of the Advanced Photon Source, a U.S. Department of Energy (DOE) Office of Science User Facility operated for the DOE Office of Science by Argonne National Laboratory under Contract No. DE-AC02-06CH11357. We thanks A. Demourgues and C. Pepin for providing CoF2 samples and S. Casale for TEM analysis. D.D thanks the French network on fluorine chemistry (GIS-FLUOR) for support. Catalysts under Operating Conditions. Sci. Adv. 2017, 3 (3).

AUTHOR INFORMATION

Corresponding Author * damien.dambournet@sorbonne-universite.fr


Iovka Boneva

Jose Lozano

S Lawek Staworko

ShERML: Mapping Relational Data to RDF *

Keywords: RDF, ShEx, SHACL, Graphical Mapping Language, R2RML

We present ShERML, a tool for facilitating the data exchange from relational data to RDF. The main feature of the tool is a graphical user interface for designing a relational-to-RDF mapping by drawing arrows between schematic representations of the relational schema on the one hand, and a SHACL or ShEx schema on the other hand. The mapping thus constructed can be used directly by the tool for materializing the RDF graph, or be exported as an R2RML mapping.

Introduction

RDF and Semantic Web data often originate from pre-existing relational databases. The problem to export relational data to RDF is known as relational to RDF data exchange, and can be solved either by writing ad-hoc export scripts, or more recently by using dedicated declarative languages such as the W3C standard R2RML. The latter allows to define mappings that use logical tables (typically SQL queries) and how each row of such table is used to construct a number of RDF triples. There exist a number of mapping editors to facilitate the creation of R2RML mappings [START_REF] Sengupta | Editing R2RML mappings made easy[END_REF][START_REF] Heyvaert | RMLEditor: a graph-based mapping editor for Linked Data mappings[END_REF][START_REF]Rml.x visual editor[END_REF][START_REF] Crotti Junior | Juma: An editor that uses a block metaphor to facilitate the creation and editing of R2RML mappings[END_REF].

ShERML is inspired by the well known relational-to-relational data exchange tool Clio [START_REF] Fagin | Clio: Schema Mapping Creation and Data Exchange[END_REF], in which mappings are defined by drawing arrows between the source and the target schema, as shown in Fig. 1. In ShERML we use Shape Constraint Languge (SHACL) or Shape Expressions Language (ShEx) as target schemas. Both languages were specifically designed to describe the vocabulary and the desired structure of an RDF graph. They use shapes to describe how a particular piece of information should be structured. Collections of shapes with references to each other are called shapes schemas. Using a shapes schema for relational to RDF mappings presents several advantages. On the one hand, fixing the target vocabulary prior to the design of the mapping allows to separate concerns. On the other hand, compared to ontologies, shapes schemas are more flexible as they allow to define (1) a target vocabulary mixing terms from different ontologies, and (2) structural requirements on the graph fitted for a particular existing application. Additionally, ShERML checks whether the mapping defined by the user would generate an RDF graph compliant with the given shapes schema.

Architecture and Implementation

The architecture of ShERML is presented in Fig. 2. The core element of ShERML is the Graphical Mapping Language (GML), which allows to define mappings from relational databases to RDF while specifying how the results of SQL queries should be organized to fit the shapes of a shapes schema. ShERML provides a Graphical Mapping Language Editor that allows to define GML mappings while allowing a high degree of customization of the defined mapping. A GML mapping can be fed into the Materializer that executes it by running SQL queries on the relational database and constructing the desired RDF graph. Additionally, the GML script can be translated to a corresponding R2RML script with the help of the Converter. The online video demo, source code and installation instructions are available on this repository https://github.com/josemachino/ShERML.

Demo Scenario

We demonstrate the principal functionality of ShERML with the following use case. We shall export the contents of a relational database with products and their suppliers as seen on the left side in Fig. 1. The database consists of three tables: Product with the information on products, Supplier with the information on suppliers, and ProdSupp with information on what supplier provides which product. The data is to be exported to RDF whose structure is defined with the schema present on the right side in Fig. 1. In essence, it defines two types of RDF nodes: TProduct for products and TSupplier for suppliers. The type TProduct requires a node to have a single name, a single price, and an optional origin information. Additionally, a product node must have one or more suppliers. A supplier node must have a name, a phone number, and an arbitrary number of email addresses. During the demonstration, we shall construct the desired GML mapping, in Fig. 1, with the following steps:

Loading schema. Before defining the mapping, both schemas need to be loaded from their source files. Each table and each shape are represented with a single box, each containing the list of attributes/property names. Each element of the list has a dedicated circular anchor, for creating connections later on. Anchors use two colors: orange anchors identify elements that reference other elements i.e., foreign keys in the relational schema and shape references in shapes schema; green anchors identify remaining elements that store values.

Defining mapping. The mapping is defined with the convenience of drawing arrows from the elements of relational schema to the elements of the shape schema. There are three kinds of arrows:

IRI arrow

connects relation to the corresponding shape (it does not use anchors). It defines how rows from a table are to be mapped to IRI nodes satisfying a given shape constraint. For instance, table Product is mapped to the shape TProduct and for every row in Product a corresponding IRI is created in the output RDF using a specified IRI constructor TPr2iri applied to the key attribute PID (more details on IRI constructors below).

Property arrow

connects relation attributes to literal properties of the shapes; it can only connect two green anchors. It defines how table rows are mapped to triples. A property arrow is dependent on an IRI arrow that defines the IRI nodes for which the property values are generated. For instance, the arrow from Product.Name to TProduct.name maps every row in Product to a triple whose subject is TPr2iri(PID), the predicate is name, and the object is the value of the Name attribute in the row. Reference arrow connects a foreign key of a table to a reference property in the shape schema; it can only connect two orange anchors. Similarly to a property arrow, a reference arrow is dependent on an IRI arrow and yields RDF triples, but this time the object is also an IRI rather than a literal. For instance, the arrow from ProdSupp.SID to TProduct.suppliedBy generates the triples that connect every product with each of its suppliers.

Both property and reference arrows are dependent on an IRI arrow that specifies the subject of the generated triples. The IRI arrow does not need to originate from the same table, and those arrows are annotated with the join expressions needed to reach the relevant IRI arrow cf., the expression ProdSupp ⋊ ⋉ Product on the arrow from ProdSupp.SID to TProduct.suppliedBy.

Both IRI and reference arrows are annotated with IRI constructors that specify how the IRI nodes are to be obtained. By default when loading a shape schema, the system constructs default IRI constructors for every shape in a manner consistent with how IRIs are constructed in R2RML. For instance, for the TProduct shape, whose full IRI is http://inria.fr/TProduct, the default IRI constructor TPr2iri basically appends the given value to this IRI e.g., TPr2iri(P1) returns http://inria.fr/TProduct/P1.

Refining GML mapping. The mapping can then be closely inspected and refined further. For this purpose ShERML offers a visual inspector that reorganizes the GML by grouping the arrows by the target shapes. It allows adding filter conditions and, in our demonstration we shall add a condition to the TProduct IRI arrow to export only products whose stock is lower than 1000.

RDF materialization and R2RML export. Once the GML mapping is defined, ShERML can export the contents of the relational database to RDF in a chosen format (Turtle, N-triples, or RDF/JSON). Finally, the system allows us to convert the GML mapping to an R2RML mapping that can then be used by third-party applications.

During the demonstration we shall also present static and runtime consistency checking and property value transformations.

Conclusions

We have presented a demo of ShERML, a versatile system for defining mappings from relational databases to RDF with target shape schema using an intuitive and powerful graphical mapping language. As next step we plan to use the tool for expressing existing relational to RDF data exchange scenarios currently written as python programs. This will allow to prioritise the future extensions of ShERML such as extending its mapping language or its GUI.

Fig. 1 .

 1 Fig. 1. A mapping from a relational database to shapes schema defined with ShERML.

Fig. 2 .

 2 Fig. 2. ShERML Architecture and Workflow.

Acknowledgments This work was partially supported by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020 and by the ANR project DataCert ANR-15-CE39-0009.