We study the relational to RDF data exchange problem, where the target constraints are specified using Shape Expression schema (ShEx). We investigate two fundamental problems: 1) consistency which is checking for a given data exchange setting whether there always exists a solution for any source instance, and 2) constructing a universal solution which is a solution that represents the space of all solutions. We propose to use typed IRI constructors in source-totarget tuple generating dependencies to create the IRIs of the RDF graph from the values in the relational instance, and we translate ShEx into a set of target dependencies. We also identify data exchange settings that are key-covered, a property that is decidable and guarantees consistency. Furthermore, we show that this property is a sufficient and necessary condition for the existence of universal solutions for a practical subclass of weakly-recursive ShEx.
Data exchange can be seen as a process of transforming an instance of one schema,
called the source schema, to an instance of another schema, called the target schema,
according to a set of rules, called source-to-target tuple generating dependencies
(sttgds). But more generally, for a given source schema, any instance of the target schema
that satisfies the dependencies is a solution to the data exchange problem. Naturally,
there might be no solution, and then we say that the setting is inconsistent. Conversely,
there might be a possibly infinite number of solutions, and a considerable amount of
work has been focused on finding a universal solution, which is an instance (potentially
with incomplete information) that represents the entire space of solutions. Another
fundamental and well-studied problem is checking consistency of a data exchange setting
i.e., given the source and target schemas and the st-tgds, does a solution exist for any
source instance. For relational databases the consistency problem is in general known
to be undecidable [
Resource Description Framework (RDF) [
In the present paper, we study the problem of data exchange where the source is
a relational database and the target is an RDF graph constrained with a ShEx schema.
Although an RDF graph can be seen as a relational database with a single ternary
relation Triple, RDF graphs require using Internationalized Resource Identifiers (IRIs)
as global identifiers for entities. Consequently, the framework for data exchange for
relational databases cannot be directly applied as is and we adapt it with the help of
IRI constructors, functions that assign IRIs to identifiers from a relational database
instance. Their precise implementation is out of the scope of this paper and belongs to the
vast domain of entity matching [
Example 1. Consider the relational database of bug reports in Figure 1, where the relation Bug stores a list of bugs with their description and ID of the user who reported the bug, the name of each user is stored in the relation User and her email in the relation Email. Additionally, the relation Rel identifies related bug reports for any bug report.
1 Boom! 1 2 Kaboom! 2 3 Kabang! 1 4 Bang! 3 1 Jose 2 Edith 3 Steve89 The above schema defines two types of (non-literal) nodes: TBug for describing bugs and TUser for describing users. Every bug has a description, a user who reported it, and a number of related bugs. Every user has a name, an email, and an optional phone number. The reserved symbol Lit indicates that the corresponding value is a literal.
The mapping of the contents of the relational database to RDF is defined with the following logical rules (the free variables are implicitly universally quantified).
Bug(b; d; u) ) Triple(bug2iri(b);:descr; d) ^ TBug(bug2iri(b)) ^
Triple(bug2iri(b);:rep; pers2iri(u)) Rel(b1; b2) ) Triple(bug2iri(b1);:related; bug2iri(b2))
User(u; n) ) Triple(pers2iri(u);:name; n) ^ TUser(pers2iri(u))
User(u; n) ^ Email(u; e) ) Triple(pers2iri(u);:email; e) ^ Lit (e) On the left-hand-side of each rule we employ queries over the source relational database, while on the right-hand-side we make corresponding assertions about the triples in the target RDF graph and the types of the nodes connected by the triples. The atomic values used in relational tables need to be carefully converted to IRIs with the help of IRI constructors pers2iri and bug2iri. The constructors can be typed i.e., the IRI they introduce are assigned a unique type in the same st-tgd.
We point out that in general, IRI constructors may use external data sources to properly assign to the identifiers from the relational database unique IRIs that identify the object in the RDF domain. For instance, the user Jose is our employee and is assigned the corresponding IRI emp:jose, the user Edith is not an employee but a registered user of our bug reporting tool and consequently is assigned the IRI user:edith, and finally, the user Steve89 is an anonymous user and is assigned a special IRI indicating it anon:3.
Figure 2 presents an RDF instance that is a solution to the problem at hand. We point out that the instance uses a (labeled) null literal ?1 for the email of Steve89 that is required by the ShEx schema but is missing in our database. tu “Kabang!” r c s e d : bug:3 : “Boom!” r c s e d : bug:1 :related rep
:rep emp:jose :name :email “Jose” “j@ex.com” “Bang!” r c s e d : bug:4 :related
:related p e r : anon:3 :name :email “Steve89” ?1 “Kaboom!” r c s e d : bug:2 p e r : user:edith :name :email “Edith”
Fig. 2: Target RDF graph (solution) The presence of target schema raises the question of consistency. On the one hand, we can prove that for any instance of the relational database in Example 1 there exists a target solution that satisfies the schema and the set of source-to-target tuple generating dependencies. On the other hand, suppose we allow a user to have multiple email addresses, by changing the key of Email to both uid and email . Then, the setting would not be consistent as one could construct an instance of the relational database, with multiple email addresses for a single user, for which there would be no solution.
Our investigation provides a preliminary analysis of the consistency problem for relational to RDF data exchange with target ShEx schema. Our contribution can be summarized as follows: – a formalization of relational to RDF data exchange with target ShEx schema and typed IRI constructors. – a decidable characterization of a fully-typed key-covered data exchange setting that is a sufficient and necessary condition for consistency. – an additional restriction of weak-recursion on ShEx schemas that ensures the existence of universal solution.
Related Work. Relational Data Exchange, Consistency. The theoretical foundations of
data exchange for relational databases are laid in [
Organization. In Section 2 we present basic notions. In Section 3 we show how ShEx
schemas can be encoded using target dependencies. In Section 4 we formalize relational
to RDF data exchange. In Section 5 we study the problem of consistency. And finally, in
Section 6 we investigate the existence of universal solutions. Conclusions and directions
of future work are in Section 7. The missing proofs can be found in the full version [
First-order logic. A relational signature R (resp. functional signature F ) is a finite set of relational symbols (resp. functional symbols), each with fixed arity. A type symbol is a relational symbol with arity one. A signature is a set of functional and relational symbols. In the sequel we use R, resp. F , resp. T for sets of relational, resp. functional, resp. type symbols.
We fix an infinite and enumerable domain Dom partitioned into three infinite subsets Dom = Iri [ Lit [ Blank of IRIs, literals, and blank nodes respectively. Also, we assume an infinite subset NullLit Lit of null literals. In general, by null values we understand both null literals and blank nodes and we denote them by Null = NullLit [ Blank.
Given a signature W = R [ F , a model (or a structure) of W is a mapping M that with any symbol S in W associates its interpretation SM s.t.: – RM Domn for any relational symbol R 2 R of arity n; – f M : Domn ! Dom, which is a total function for any function symbol f 2 F of arity n.
We fix a countable set V of variables and reserve the symbols x; y; z for variables, and the symbols x, y, z for vectors of variables. We assume that the reader is familiar with the syntax of first-order logic with equality and here only recall some basic notions. A term over F is either a variable in V , or a constant in Dom, or is of the form f (x) where f 2 F and the length of x is equal to the arity of f ; we remark that we do not allow nesting of function symbols in terms. A dependency is a formula of the form 8x:' ) 9y: and in the sequel, we often drop the universal quantifier, write simply ' ) 9y: , and assume that implicitly all free variables are universally quantified.
The semantics of first-order logic formulas is captured with the entailment relation M; j= defined in the standard fashion for a model M , a first-order logic formula with free variables x and a valuation : x ! Dom. The entailment relation is extended to sets of formulas in the canonical fashion: M j= f'1; : : : ; 'ng iff M j= 'i for every i 2 f1; : : : ; kg.
Relational Databases. We model relational databases using relational structures in the standard fashion. For our purposes we are only concerned with functional dependencies, which include key constraints. Other types of constraints, such as inclusion dependencies and foreign key constraints, are omitted in our abstraction.
A relational schema is a pair R = (R; fd) where R is a relational signature and fd is a set of functional dependencies (fds) of the form R : X ! Y , where R 2 R is a relational symbol of arity n, and X; Y f1; : : : ; kg. An fd R : X ! Y is a short for the following formula 8x; y: R(x) ^ R(y) ^ Vi2X (xi = yi) ) Vj2Y (xj = yj ). An instance of R is a model I of R and we say that I is valid if I j= fd. The active domain dom (I ) of the instance I is the set of values from Dom that appear in RI for some relational symbol R in R. Unless we state otherwise, in the sequel we consider only instances that use only constants from Lit n NullLit.
RDF Graphs and Shape Expressions Schemas. Recall that an RDF graph, or graph for short, is a set of triples in (Iri [ Blank) Iri (Iri [ Blank [ Lit). The set of nodes of the graph G is the set of elements of Iri [ Blank [ Lit that appear on first or third position of a triple in G.
We next define the fragment of shape expression schemas that we consider, and
that was called RBE0 in [
Formally, a multiplicity is an element of f1; ?; *; +g with the natural interpretation: 1 is exactly one occurrence, ? stands for none or one occurrence, * stands for an arbitrary number of occurrences, and + stands for a positive number of occurrences. A triple constraint over a finite set of shape names T is an element of Iri (T [ fLit g) f1; ?; *; +g, where Lit is an additional symbol used to indicate that a node is to be a literal. Typically, we shall write a triple constraint (p; T; ) as p :: T . Now, a shape expressions schema, or ShEx schema for short, is a couple S = (T ; ) where T is a finite set of shape names, and is shape definition function that maps every symbol T 2 T to a finite set of triple constraints over T such that for every shape name T and for every IRI p, (T ) contains at most one triple constraint using p.
For a finite set T of shape names, a T -typed graph is a couple (G; typing ) where G is a graph and typing is a mapping from the nodes of G into 2T [fLitg that with every node of G associates a (possibly empty) set of types. Let S = (T ; ) be a ShEx schema. The T -typed graph (G; typing ) is correctly typed w.r.t. S if it satisfies the constraints defined by i.e., for any node n of G: – if Lit 2 typing (n), then n 2 Lit; – if T 2 typing (n) then n 2 Iri and for every p :: S in (T ) we have that (1) for any triple (n; p; m) in G, S belongs to typing (m), and (2) if K is the set of triples in G whose first element is n and second element is p, then the cardinality of K is bounded by i.e., jKj = 1 if = 1, jKj 1 if = ?, and jKj 1 if = + (there is no constraint if = *).
For instance, a correct typing for the graph in Figure 2 assigns the type TBug to the nodes bug:1, bug:2, bug:3, and bug:4; the type TUser to the nodes emp:jose, user:edith, and anon:3; and Lit to every literal node.
In this section we show how to express a ShEx schema S = (T ; ) using dependencies.
First, we observe that any T -typed graph can be easily converted to a relational structure over the relational signature GT = fTripleg [ T [ fLit g, where Triple is a ternary relation symbol for encoding triples, and T [ fLit g are monadic relation symbols indicating node types (details in Appendix ??). Consequently, in the sequel, we may view a T -typed graph as the corresponding relational structure (or even a relational database over the schema (GT ; ;)).
Next, we define auxiliary dependencies for any two T; S 2 T and any p 2 Iri tc(T; S; p) := T (x) ^ Triple(x; p; y) ) S(y) mult 1 (T; p) := T (x) ) 9y:Triple(x; p; y) mult 1 (T; p) := T (x) ^ Triple(x; p; y) ^ Triple(x; p; z) ) y = z We point out that in terms of the classical relational data exchange, tc and mult 1 are tuple generating dependencies (tgds), and mult 1 is an equality generating dependency (egd). We capture the ShEx schema S with the following set of dependencies: S = ftc(T; S; p) j T 2 T ; p :: S
2 (T )g [ fmult 1 (T; p) j T 2 T ; p :: S fmult 1 (T; p) j T 2 T ; p :: S 2 (T ); 2 (T ); 2 f1; +gg [ Lemma 1. For every ShEx schema S = (T ; ) and every T -typed RDF graph (G; typing ), (G; typing ) is correctly typed w.r.t. S iff (G; typing ) j= S.
In this section, we present the main definitions for data exchange.
Definition 1 (Data exchange setting). A relational to RDF data exchange setting is a tuple E = (R; S; st; F ; Fint) where R = (R; fd) is a source relational schema, S = (T ; ) is a target ShEx schema, F is a function signature, Fint as an interpretation for F that with every function symbol f in F of arity n associates a function from Domn to Iri, and st is a set of source-to-target tuple generating dependencies, clauses of the form 8x:' ) , where ' is a conjunction of atomic formulas over the source signature R and is a conjunction of atomic formulas over the target signature GT [F . Furthermore, we assume that all functions in Fint have disjoint ranges i.e., for f1; f2 2 Fint if f1 6= f2, then ran(f1) \ ran(f2) = ;.
Definition 2 (Solution). Take a data exchange setting E = (R; S; st; F ; Fint), and let I be a valid instance of R. Then, a solution for I w.r.t. E is any T -typed graph J such that I [ J [ Fint j= st and J j= S.
A homomorphism h : I1 ! I2 between two relational structures I1; I2 of the same relational signature R is a mapping from dom(I1) to dom(I2) that 1) preserves the values of non-null elements i.e., h(a) = a whenever a 2 dom(I1) n Null, and 2) for every R 2 R and every a 2 RI1 we have h(a) 2 RI2 , where h(a) = (h(a1); : : : ; h(an)) and n is the arity of R.
Definition 3 (Universal Solution). Given a data exchange setting E and a valid source instance I, a solution J for I w.r.t. E is universal, if for any solution J 0 for I w.r.t. E there exists a homomorphism h : J ! J 0.
As usual, a solution is computed using the chase. We use a slight extension of the
standard chase (explained in [
Definition 4 (Consistency). A data exchange setting E is consistent if every valid source instance admits a solution.
We fix a relational to RDF data exchange setting E = (R; S; st; F ; Fint) and let S = (T ; ). We normalize source-to-target tuple generating dependencies so that their right-hand-sides use exactly one Triple atom and at most two type assertions on the subject and the object of the triple; such normalization is possible as our st-tgds do not use existential quantification. In this paper, we restrict our investigation to completely typed st-tgds having both type assertions, and therefore being of the following form 8x: ' ) Triple(s; p; o) ^ Ts(s) ^ To(o); where s is the subject term, Ts is the subject type, p 2 Iri is the predicate, o is the object term, and To is the object type. Because the subject of a triple cannot be a literal, we assume that s = f (y) for f 2 F and for y x, and Ts 2 T . As for the object, we have two cases: 1) the object is an IRI and then o = g(z) for g 2 F and for z x, and To 2 T , or 2) the object is literal o = z for z 2 x and To = Lit . Moreover, we assume consistency with the target ShEx schema S i.e., for any st-tgd in st with source type Ts, predicate p, and object type To we have p :: To 2 (Ts) for some multiplicity . Finally, we assume that every IRI constructor in F is used with a unique type in T . When all these assumptions are satisfied, we say that the source-to-target tuple generating dependencies are fully-typed.
While the st-tgds in Example 1 are not fully-typed, an equivalent set of fully-typed dependencies can be easily produced if additionally appropriate foreign keys are given. For instance, assuming the foreign key constraint Bug[uid ] User[uid ], the first rule with Bug on the left-hand-side is equivalent to Bug(b; d; u) ) Triple(bug2iri(b);:descr; d) ^ TBug(bug2iri(b)) ^ Lit (d) Bug(b; d; u) ) Triple(bug2iri(b);:rep; pers2iri(u)) ^ TBug(bug2iri(b)) ^ TUser(pers2iri(u))
Now, two st-tgds are contentious if both use the same IRI constructor f for their subjects and have the same predicate, hence the same subject type Ts and object type To, and p :: To 2 (Ts) with = 1 or = ?. We do not want two contentious sttgds to produce two triples with the same subject and different objects. Formally, take two contentious st-tgds 1 and 2 and assume they have the form (for i 2 f1; 2g, and assuming x1; x2; y1; y2 are pairwise disjoint)
i = 8xi; yi: 'i(xi; yi) ) Triple(f (xi); p; oi) ^ Ts(f (xi)) ^ To(oi): The st-tgds 1 and 2 are functionally overlapping if for every valid instance I of R
I [ Fint j= 8x1; y1; x2; y2: '1(x1; y1) ^ '2(x2; y2) ^ x1 = x2 ) o1 = o2: Finally, a data-exchange setting is key-covered if every pair of its contentious st-tgds is functionally overlapping. Note that any single st-tgd may be contentious with itself. Theorem 1. A fully-typed data exchange setting is consistent if and only if it is keycovered.
The sole reason for the non-existence of a solution for a source instance I is a violation
of some egd in S. The key-covered property ensures that such egd would never be
applicable. Intuitively, two egd-conflicting objects o1 and o2 are necessarily generated by
two contentious st-tgds. The functional-overlapping criterion guarantees that the terms
o1 and o2 are “guarded” by a primary key in the source schema, thus cannot be different.
Theorem 2. It is decidable whether a fully-typed data exchange setting is key-covered.
The proof uses a reduction to the problem of functional dependency propagation [
In this section, we identify conditions that guarantee the existence of a universal solution. Our results rely on the existence of a universal solution for sets of weakly-acyclic
sets of dependencies for relational data exchange [
The dependency graph of a ShEx schema S = (T ; ) is the directed graph whose set of nodes is T and has an edge (T; T 0) if T 0 appears in some triple constraint p :: T 0 of (T ). There are two kinds of edges: strong edge, when the multiplicity 2 f1; +g, and weak edge, when 2 f*; ?g. The schema S is strongly-recursive if its dependency graph contains a cycle of strong edges only, and is weakly-recursive otherwise. Take for instance the following extension of the ShEx schema from Example 1: TUser ! f:name :: Lit 1;:email :: Lit 1;:phone :: Lit ?g TBug ! f:rep :: TUser1;:descr :: Lit 1;:related :: TBug*;:repro :: TEmp?g TTest ! f:covers :: TBug+g
TEmp ! f:name :: Lit 1;:prepare :: TTest+g The dependency graph of this schema, presented in Figure 3. contains two cycles but neither of them is strong. Consequently, the schema is weakly-recursive (and naturally so is the ShEx schema in Example 1).
As stated above, a weakly-recursive ShEx schema guarantees a weakly-acyclic set
of dependencies and using results from [
S is finite, and either every chase sequence of I with st fails, or every such chase sequence computes a universal solution of I for E . 7
We presented a preliminary study of the consistency problem for relational to RDF data exchange in which the target schema is ShEx. Consistency is achieved by fully-typed and key-covered syntactic restriction of st-tgds. An open problem that we plan to investigate is consistency when the fully-typed restriction is relaxed; we believe that it is achievable if we extend the definition of contentious st-tgds. Another direction of research is to consider a larger subset of ShEx. Finally, we plan to extend our framework to typed literals which are not expected to bring fundamental difficulties but are essential for practical applications.
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.