MostoDEx: A tool to exchange RDF data using exchange samples

MostoDEx: A tool to exchange RDF data using exchange samples Carlos R. Rivero, Inma Hernández, David Ruiz , Rafael Corchuelo a University of Idaho, 875 Perimeter Drive, MS 1010, Moscow, ID 83844-1010, United States b Universidad Autonoma de Chile, C/ Carlos Antunez, 1920 Santiago, Chile c University of Sevilla, ETSI Informática, Avda. Reina Mercedes s/n, Sevilla E-41012, Spain Keywords: Data exchange RDF Schema mappings a b s t r a c t The Web is evolving into a Web of Data in which RDF data are becoming pervasive, and it is organised into datasets that share a common purpose but have been developed in isolation. This motivates the need to devise complex integration tasks, which are usually performed using schema mappings; generating them automatically is appealing to relieve users from the burden of handcrafting them. Many tools are based on the data models to be integrated: classes, properties, and constraints. Unfortunately, many data models in the Web of Data comprise very few or no constraints at all, so relying on constraints to generate schema mappings is not appealing. Other tools rely on handcrafting the schema mappings, which is not appealing at all. A few other tools rely on exchange samples but require user intervention, or are hybrid and require constraints to be available. In this article, we present MostoDEx, a tool to generate schema mappings between two RDF datasets. It uses a single exchange sample and a set of correspondences, but does not require any constraints to be available or any user intervention. We validated and evaluated MostoDEx using many experiments that prove its effectiveness and efficiency in practice. 1. Introduction The current Web is progressively evolving into a Web of Data in which RDF (Resource Description Framework) data are becoming pervasive (Heath and Bizer, 2011). There are thousands of datasets available, many of which share a common purpose but have been developed by independent organisations in isolation (Bizer et al., 2009). There are many initiatives whose goal is to link these datasets, which is the first step to perform complex integration processes (Heath and Bizer, 2011). Integration usually refers to several crucial tasks, such as data integration (Lenzerini, 2002), data warehousing (Marileo et al., 2012), model evolution (Flouris et al., 2008), model matching (Shvaiko and Euzenat, 2013), record linkage (Wang et al., 2013), or data exchange (Fagin et al., 2005). In this article, we focus on the latter, whose goal is to populate a target dataset using data that come from one or more source datasets. Data exchange has been paid much attention in the database context, i.e., relational, nestedrelational, or XML (Arenas and Libkin, 2008; Fagin et al., 2005; Popa et al., 2002). Furthermore, the emergence of RDF is motivating some ∗Corresponding author. Tel.: +1 2088856592. authors to work on data exchange in the context of the Web of Data (Barceló et al., 2013; Parreiras et al., 2008; Rivero et al., 2013b). Data exchange is performed by means of schema mappings, which are declarative specifications of the relationships amongst a source and a target datasets (Alexe et al., 2011a). Generating schema mappings automatically is appealing because this relieves users from the burden of handcrafting them, so researchers have focused on helping users generate them (Qian et al., 2012). Many current tools are based on the data models to be integrated (Haas et al., 2005; Bonifati et al., 2005; Raffio et al., 2008; Mecca et al., 2009; Marnette et al., 2011; Rivero et al., 2013c). By data model, we refer to a sets of entities (that is, classes and properties) and a set of constraints that describe additional features of entities (for instance, class Ais a specialisation of class B, property Phas class Cas its domain, and so on). In the Web of Data, there are many data models that comprise very few or no constraints at all, which typically results in data models that merely specify set of entities (Lausen et al., 2008; Heath and Bizer, 2011). Therefore, relying on data models with constraints to generate schema mappings is not appealing in the general context of the Web of Data. There exist other tools that do not rely on data models. Unfortunately, they rely on handcrafting the schema mappings (Mocan and Cimpian, 2007; Maedche et al., 2002; Parreiras et al., 2008; Bizer and Schultz, 2010; Dou et al., 2005; Ressler et al., 2007), which is not appealing at all; and a few others rely on exchange samples (Alexe et al., 2008, 2006, 2011b; Qian et al., 2012), which make E-mail addresses: [email protected] (C.R. Rivero), [email protected] (I. Hernández), [email protected] (D. Ruiz), [email protected] (R. Corchuelo). them more appealing, but require user intervention, or are hybrid and require constraints to be available. Note that an exchange sample is an example of source data and how it is exchanged into target data. In this article, we present MostoDEx,1a tool to automatically generate schema mappings between two RDF datasets using a single exchange sample and a set of n:mcorrespondences. An exchange sample comprises a subset of source data and a subset of target data that is the expected result of exchanging the source data. Correspondences are hints that specify which entities in the source and target datasets correspond to each other, i.e., are somewhat related (Bellahsene et al., 2011). These schema mappings can be easily transformed into SPARQL queries. Our tool does not rely on constraints of the source and target data models and does not require any user intervention, not even to repair the input exchange sample. We have validated our tool using ten data exchange problems amongst various real-world datasets. In our validation, the execution time never exceeded one second, and the data exchanged were as expected by experts in every case, which suggests that it is very efficient in practice and that the generated schema mappings are appropriate. Additionally, we have evaluated the performance of our tool when data exchange problems scale. We used four synthetic data exchange patterns proposed by MostoBM (Rivero et al., 2013a), a benchmark for testing data exchange proposals in the context of the Web of Data. We instantiated the synthetic data exchange patterns into 2000 nontrivial data exchange problems that we used to evaluate our tool. Our evaluation results suggest that our tool works well as the data exchange problems scale. The rest of the article is organised as follows: Section 2presents thetoolsrelatedto MostoDExand itsmain contributionsto thestate of the art; Section 3presents some preliminaries that are necessary to understand the internal details of our tool; Section 4describes how our tool works; Section 5reports on the validity and scalability evaluation of MostoDEx; and, finally, Section 6recaps on our main conclusions. 2. Related work In this section, we present other existing tools that are related to MostoDEx. We present some tools that require the user to handcraft the schema mappings in Section 2.1, others are based on the constraints that comprise the source and target data models to be integrated in Section 2.2, and a last group of tools are based on samples of data to perform data exchange in Section 2.3. Finally, we analyse and discuss the drawbacks of these tools in Section 2.4, which motivated us to work on a new proposal. 2.1. Handcraft-based tools There are a number of tools that focus on handcrafting schema mappings, which are expressed as queries but can be viewed as implicitly generating schema mappings: WSEE (Mocan and Cimpian, 2007), which stands for the Web Services Execution Environment, builds on a formal framework to describe correspondences in terms of first-order logic formulae that are used to generate schema mappings using the Web Service Modeling Language (WSML). This tool focuses on the problem of data exchange in the context of semantic-web services, i.e., web services that are enriched with semantic annotations to improve their discovery and composition (Forte et al., 2008). This tool is similar in spirit to MAFRA (Maedche et al., 2002) (MApping FRAmework), whose 1Atechnicalreportand aresearch prototypeare availablesomewhere else(Rivero et al., 2013, 2013). focus is on modelling correspondences in a general-purpose setting. The main difference with the previous tool is that WSEE goes a step beyond formalising correspondences and executes them using aWSML reasoner to exchange data. MBOTL (Parreiras et al., 2008) (Model-Based Ontology Translation Language) builds on the framework of Model-Driven Engineering in which the ATL (ATLAS Transformation Language) metamodel is extended to support RDF data models, which allows to express constraints on them using OCL (Object Constraint Language). MBOTL comprises a mapping language by means of which users can express schema mappings that are later transformed into the SPARQL query language by means of a library of ATL transformations. This is similar in spirit to R2R (Bizer and Schultz, 2010) (RDF to RDF), OntoMerge (Dou et al., 2005), and Snoogle (Ressler et al., 2007), the difference is the language used to represent the schema mappings: R2R and Snoogle use SPARQL 1.0; whereas OntoMerge uses Web-PDDL schema mappings that are run by means of a firstorder logic reasoner. 2.2. Constraint-based tools They focus on generating schema mappings building on correspondences and constraints on the source and target data models. These tools are able to compute subsets of data in the source dataset that need to be exchanged as a whole, and subsets of data in the target dataset that need to be created as a whole (Rivero et al., 2013b). To compute them, they rely on user-defined constraints and the inherent constraints of certain data models, such as paths from the root to a leaf in a nested-relational data model, or hierarchy relations amongst classes in an RDF data model. Then, several combinations of these subsets of data are used to generate the final schema mappings (Popa et al., 2002). Clio (Haas et al., 2005) is the state-of-the-art tool in this field. It takes a source and a target nested-relational data models, a number of constraints of each data model, and a number of 1 : 1 correspondences between them as input, and it generates schema mappings that can be easily transformed into different query languages, such as XQuery, XSLT, or SQL. HePToX (Bonifati et al., 2005) is similar to Clio but it focuses on XML data models, which are a superset of nested-relational data models. Clip (Raffio et al., 2008) allows to generate schema mappings based on n:1 correspondences, and it uses a mapping visual language that was specifically designed for nested-relational data models, which includes grouping functions,aggregation functions, or dependent correspondences.+Spicy (Mecca et al., 2009) allows to compute core schema mappings that generate non-redundant target data when performing data exchange.++Spicy (Marnetteet al.,2011) improves+Spicy byallowing more expressive target constraints. MostoDE (Rivero et al., 2013c) is able to work with RDF data models whose constraints are interpreted as graphs that are traversed to compute source and target kernels. A kernel comprises a subset of the source data model that needs to be exchanged as a whole, and a subset of the target data model that needs to be created as a whole. Kernels are translated into schema mappings that are represented in SPARQL 1.1. 2.3. Sample-based tools These tools aim to generate schema mappings from a set of exchange samples. In the relational or nested-relational contexts, SPIDER (Alexe et al., 2006) helps users understand and maintain the schema mappings generated by Clio by extracting exchange samples from the source and target datasets, and it illustrates the following: (1) relationships in a specific schema mapping, (2) sample source data that this schema mapping would extract when performing data exchange, and (3) the target data generated by Table 1 Comparison of tools to generate schema mappings. F1F2F3F4F5F6 Handcraft-based tools Bizer and Schultz (2010) X√X X √X Dou et al. (2005) XXXX√X Maedche et al. (2002) X X √XXX Mocan and Cimpian (2007) XXXX√X Parreiras et al. (2008) X√X X √X Ressler et al. (2007) X√X X √X Constraint-based tools Bonifati et al. (2005) √XXX√X Haas et al. (2005) √XXX√ √ Marnette et al. (2011) √XXX√ √ Mecca et al. (2009) √XXX√X Raffio et al. (2008) XXXX√X Rivero et al. (2013c) √XXX√ √ Sample-based tools Alexe et al. (2011b) X√XXXX Alexe et al. (2008) √XXXXX Alexe et al. (2006) √XXXXX Qian et al. (2012) √XXXXX MostoDEx √√√√√√ those source data. Muse (Alexe et al., 2008) aids users in generating and understanding schema mappings building on exchange samples. It assumes that source and target data models, together with their constraints, exist, and it infers grouping functions by analysing the answers to some questions it poses to the users. EIRENE (Alexe et al., 2011b) generates a number of schema mappings by means of a finite set of exchange samples. This tool computes whether or not two input exchange samples have incoherences from a structural point of view, i.e., whether or not these two exchange samples generate schema mappings that will result in erroneous target data. If the input set of exchange samples does not have any incoherences, then it generates the schema mappings. MWeaver (Qian et al., 2012) is based on exchange samples and it focuses on target data only. Users are responsible for providing the target data that they wish to be created; then, every piece of data that appears in both source and target data represents a correspondence between two entities. Correspondences and source and target constraints are used to generate schema mappings. 2.4. Discussion Table 1 summarises the comparison of current tools to generate schema mappings. The √symbol denotes that the tool supports a feature, and symbol ×implies that the tool does not support a feature. The features we have analysed are the following: (1) F1 determines if a tool requires the intervention of the user during the generation of the schema mappings; (2) F2determines if a tool requires the existence of source and target constraints to generate the schema mappings; (3) F3determines if a tool allows n:m correspondences; (4) F4determines if a tool performs automatic completions when the same source data lead to different target data; (5) F5determines if a tool has been tested with real-world scenarios; (6) F6determines if the scalability of a tool has been tested. Regarding handcraft-based tools (Mocan and Cimpian, 2007; Maedche et al., 2002; Parreiras et al., 2008; Bizer and Schultz, 2010; Dou et al., 2005; Ressler et al., 2007), they focus on handcrafting schema mappings, which is not appealing since users have to write them, check whether they work as expected or not, make changes if necessary, and restart this cycle (Petropoulos et al., 2007). Contrarily, our tool automatically generates schema mappings without the intervention of the user, and it uses a single exchange sample and a number of correspondences as input. Regarding constraint-based tools (Haas et al., 2005; Bonifati et al., 2005; Raffio et al., 2008; Mecca et al., 2009; Marnette et al., 2011; Rivero et al., 2013c), they are not so appealing in the general context of the Web of Data because (Heath and Bizer, 2011): (1) the main difference between RDF and other data modelling languages is that it allows to represent data without an explicit data model; (2) it is not possible to model the whole Web of Data with a single data model, and several data models may exist for the same RDF dataset; (3) data models in this context usually comprise very few constraints or no constraints at all, which entails that they are only simple vocabularies to create web data. Contrarily, our tool does not rely on constraints but on a single exchange sample and a set of correspondences. Some sample-based tools assume that source and target data models exist, together with their constraints (Alexe et al., 2008, 2006; Qian et al., 2012). Therefore, their main drawback, as in the previous case, is that it is not appealing to rely on source and target data models, together with their constraints, in the general context of the Web of Data. Finally, EIRENE (Alexe et al., 2011b) does not have the previous drawback, but it requires the user to provide an exchange sample for each schema mapping to be automatically generated. Furthermore, if this tool finds the input exchange samples inappropriate to generate schema mappings, the user is responsiblefor repairingthem. Contrarily, our tool requires the user to provide a single exchange sample and a set of correspondences and finds repairs automatically. Finally, when dealing with large RDF datasets, a key feature of these tools is their scalability (Fernández et al., 2013). Testing the scalability of these tools is challenging since it requires to collect sufficiently large datasets, and to provide the input data of the tools and the expected output to validate them. Currently, this can be a daunting task since, to the best of our knowledge, there are not any tools to help users perform this validation. Furthermore, most of these tools are research prototypes, therefore, it is not likely that they take scalability issues into account. We have analysed the scalability of our tool using synthetic data exchange problems that are generated with the help of MostoBM (Rivero et al., 2013a), and we report on our results in Section 5.2. 3. Preliminaries In this section, we present some preliminaries that are necessary to understand our tool. We initially introduce our research methodology in Section 3.1. Afterwards, our tool relies on a conceptual model that is presented in Section 3.2. Furthermore, Section 3.3 describes the running example that we use to illustrate it throughout this article. 3.1. Research methodology Our research methodology is based on the Unified Process framework, aka UP (Kruchten, 2003). This choice is supported by the experience of our research group in applying it to research or technology transfer. The proposed life cycle in UP is iterative and incremental, which is suitable for the development of high dynamic software projects or scientific publications in this area. It comprises the following steps: 1. Identifying research context: previous to this piece of research work, we identified that exchanging data amongst RDF datasets was an interesting topic and decided to focus on the automatic generation of schema mappings. In MostoDE (Rivero et al., 2013c), we studied this automatic generation based on source and target constraints. In this article, our focus consists on generating them automatically using exchange samples. 2. Systematic review of the bibliography: we updated the references that we identified when analysing the bibliography for our MostoDE article. 3. Identifying comparison features: we identified those features that are common to existing tools in our research context. These features are described in Section 2.4. 4. Identifying drawbacks: using the previous features, we analysed existing tools in the bibliography regarding whether they have these features or not. The conclusion was that, to the best of our knowledge, no tool has all of the features. 5. Design and implementation of our tool: we devised MostoDEx to take all of the identified features into account. 6. Design of the experiments: every tool should be tested using real-world scenarios to evaluate its effectiveness and efficiency. Furthermore, it is mandatory to evaluate its scalability. We devised 10 real-world data exchange problems to test our tool (see Section 5.1), and 2000 synthetic data exchange problems to evaluate its scalability (see Section 5.2). 3.2. Conceptual model An RDF dataset comprises a set of triples, each of which is a three-tuple whose components, which are called subject, predicate, and object, can be URIs (Uniform Resource Identifier) and literals of simple types. A schema mapping is a two-tuple whose components are sets of triple patterns that are implicitly connected using logical ANDs. A triple pattern generalises the concept of triple by allowing the subject and/or the object to be variables or blank nodes. In this article, we refer to triple patterns as patterns for the sake of brevity. Schema mappings may be easily transformed into SPARQL queries in which the two sets of patterns form the WHERE and the CONSTRUCT clauses, respectively. Note that the set of triple patterns includes the set of triples; that is why we usually use the term pattern to refer to both triple patterns and triples. A homomorphism maps the constants, variables, or blank nodes of a set of patterns onto the constants, variables, or blank nodes of another set of patterns. Homomorphisms can be either replacements or substitutions: a replacement is a finite map from constants to constants and a substitution is a finite map from constants to variables or blank nodes. Regarding our tool, we restrict our attention to the triples that describe data, that is, triples of the form (c,rdf :type,C), in which cis a constant and Cis a class, or (c1,p,c2), in which c1and c2 are constants and pis a property. An exchange sample comprises a source dataset and a target dataset. An n:mcorrespondence relates a set of entities with a different set of entities. A data exchange problem comprises a single exchange sample and a set of correspondences that relate some of the source entities with some of the target entities. Our algorithms use the following projection functions: source to get the source dataset of an exchange sample, the source entities of a given correspondence, or the source triples of a given dataset; target to get the target dataset of an exchange sample, the target entities of a given correspondence, or the target triples of a given dataset; sample and correspondences to get the single exchange sample or the correspondences of a data exchange problem, respectively; and constants to get the constants in a set of patterns. Fig. 1 presents an UML-like conceptual model, in which a DataExchangeProblem comprises a source RDFDataset (the source exchange sample), a target RDFDataset (the target exchange sample), and a number of Correspondences. Each Correspondence has a number of source and target Entities, each of which is represented by a URI and can be either a Class,DataProperty or ObjectProperty. An RDFDataset comprises a set of Patterns, each of which is a triple that contains a subject, a predicate and an object Nodes. A Node can Fig. 1. Conceptual model. be either a URI, a Literal or a Variable. A SchemaMapping comprises a set of source and target Patterns. Finally, a Homomorphism can be either a Replacement or a Substitution that maps to a set of Nodes. 3.3. Running example Figs. 2 and 3 present a real-world data exchange problem that we use to illustrate our tool. Our goal is to generate a number of schema mappings to perform data exchange from a part of DBpedia 3.8 to a part of GovWILD. On the one hand, DBpedia (Bizer et al., 2009) is a community effort to annotate and make the data stored at Wikipedia accessible by means of RDF technologies. On the other hand, GovWILD (Böhm et al., 2012) is a public RDF dataset that comprises data from US and EU governments that are connected with financial data of governments or public funds. The exchange sample in Fig. 2 comprises a set of source triples regarding Angela Merkel and David Cameron, their names, and her date of birth; and a set of target triples that specify how these data are structured according to the target entities. This exchange sample is represented using a tree-based graphical notation in which each root node is the subject of a triple, and triples are grouped by subject. A URI or a blank node is represented using a diamond, a literal using a trapezium, a data property using a square, and an Fig. 2. Running example: exchange sample. Fig. 3. Running example: correspondences. Table 2 Summary of prefixes. Prefix URI :http://dbpedia.org/resource/ rdf http://www.w3.org/1999/02/22-rdf-syntax-ns# rdfs http://www.w3.org/2000/01/rdf-schema# foaf http://xmlns.com/foaf/0.1/ dpo http://dbpedia.org/ontology/ gw http://govwild.org/0.6/GWOntology.rdf# gwd http://govwild.org/id/date/ object property using a pentagon. We use the prefixes in Table 2, in which the first row specifies the default URI. Fig. 3 shows three correspondences, namely: v1relates a person in the DBpedia and the GovWILD datasets; v2states that the name of a person in DBpedia is related to the label in GovWILD; and v3 indicatesthat a person and her/hisdate ofbirth inDBpedia isrelated to a new URI of class gw:Date in GovWILD. Correspondences are represented using a tree-based graphical notation in which each root node is an entity, which is represented using a circle, a square, or a pentagon if it is a class, a data property, or an object property, respectively. 4. Generating schema mappings Our tool takes a data exchange problem as input, which comprises a single exchange sample and a set of correspondences. The single exchange sample is expected to be an equivalent sample of the source and target data that the user wishes to exchange. Furthermore, our tool takes a number of n:mcorrespondences over the source and target entities as input. This set indicates the relationships that exist amongst the source and target entities in the Fig. 5. Generating schema mappings. data exchange problem that we wish to solve. It is expected that the user has to relate the source entities that should be exchanged as a whole, and the target entities that need to be created as a whole. Our tool generates a number of schema mappings to exchange data between the source and target datasets. Fig. 4 presents an overview of our technique to generate schema mappings that comprises five steps, namely: (1) “Generate exchange samples” takes a single exchange sample and a number of correspondences as input, and automatically generates a set of candidate exchange samples. (2) “Discard exchange samples” discards previously generated candidate exchange samples that are not useful to generate the final set of schema mappings. (3) “Complete exchange samples” adds target data to the different exchange samples if the same source data can lead to different target data. (4) “Prune exchange samples” removes exchange samples that generate the same schema mappings. (5) “Create schema mappings” transforms each exchange sample into a schema mapping. Fig. 5 presents the main algorithm that implements such workflow. In our algorithms, we use the following control structures: for each,if, and while; the following logical connectives: negation (¬), and (∧), or (∨); the following set operators: constructor ({...}), union (∪), intersection (∩), a finite power set (F). Furthermore, we also use the count operator (|...|) and a mapping function (→). These steps are explained in the rest of this section. 4.1. First step This step automatically computes a number of candidate exchange samples, each of which comprises a subset of source data that need to be exchanged as a whole, and a subset of target data that need to be created as a whole. To compute them, for each correspondence in isolation, we combine all of the pieces of connected data that contain the entities in the correspondence. Fig. 4. Overview of our schema mapping generation process. Fig. 6. Generating candidate exchange samples. Fig. 6 shows our algorithm to generate candidate exchange samples from a given correspondence and a single exchange sample. First, we compute the triples related to correspondence vfor the single exchange sample d, i.e., the triples that comprise the entities related by v. They are stored in a set of datasets. Then, we compute the distributive cartesian product of both the triples related to source(v) and the triples related to target(v), which is denoted as . We iterate over each set of source and target datasets, and we transform them into exchange samples only if each dataset comprises a unique connected component. Example 1. To illustrate this step, we focus on correspondence v2in our running example. Its source entities are dpo: Person and foaf:name. The triples that comprise dpo:Person are the following: (t1) : Angela Merkel rdf :type dpo :Person (t2) : David Cameron rdf :type dpo :Person and the triples that comprise foaf:name are the following: (t3) : Angela Merkel foaf :name “Angela Merkel (t4) : David Cameron foaf :name “David Cameron The computeRelatedTriples algorithm outputs the following set inthis case:GS={{t1,t2},{t3,t4}}; the distributive cartesian product of GSis GS={{t1,t3},{t1,t4},{t2,t3},{t2,t4}}. The target entity of v2is rdfs:label, and the triples that comprise it are the following: (t5) : Angela Merkel rdfs :label “Angela Merkel (t6) : David Cameron rdfs :label “David Cameron (t7)gwd : 1954 −7−17 rdfs :label “1954 −07 −17 Note that GT={{t5,t6,t7}} =GT. Additionally, each of the subsets in {{t2,t3},{t1,t4}} ⊆GShas two connected components, since there is no triple that does not have any triple in common with at least another triple. Therefore, we discard these sets of triples. Candidate exchange samples are generated by combining the source triples in GSand the target triples in GT, namely: d21 = ({t1,t3},{t5}), d22 = ({t1,t3},{t6}), d23 = ({t1,t3},{t7}), d24 = ({t2,t4},{t5}), d25 = ({t2,t4},{t6}), d26 = ({t2,t4},{t7}), which are depicted in Fig. 7. Fig. 7. Exchange samples generated in the first step for correspondence v2. 4.2. Second step This step consists of discarding candidate exchange samples that arenot usefulto generatethe finalset of schemamappings. Wekeep candidate exchange samples in which there is, at least, a subset of target data that can be generated using the source data, and we minimise the target data that do not exist in the source. The intuition behind this step is that we keep only the exchange samples that provide the maximum information to generate the target data, i.e., when these exchange samples are transformed into schema mappings, they comprise as less blank nodes as possible. Fig. 8 shows our algorithm to discard candidate exchange samples. An exchange example is kept or discarded according to its Fig. 8. Discarding candidate exchange samples. number of covered and uncovered constants. A constant in the target is said to be covered if there is, at least, a triple in the source that involves that constant; otherwise, it is said to be uncovered. The algorithm first computes the minimum number of uncovered constants in the input set of exchange samples; it then iterates over this set and discards every exchange sample that does not have at least a covered constant or has more uncovered constants than the minimum. Example 2. Our tool generates six exchange samples for correspondence v2(see Fig. 7), and the minimum number of uncovered constants in these exchange samples is equal to zero, since every constant in d21 is covered; therefore, our tool discards exchange samples d22,d23,d24, and d26 in the second step because each of them has two uncovered constants::David Cameron and “David Cameron”, gwd:1954-7-17 and “1954-07-17”,:Angela Merkel and “Angela Merkel”, and gwd:1954-7-17 and “1954-07-17”, respectively. Furthermore, in Fig. 9, we present the schema mappings that our tool outputs for correspondence v3of our running example. Note that the minimum number of uncovered constants in these exchange samples is equal to one, since gwd:1954-7-17 is not present in the source in any exchange sample. Therefore, our tool discards d32 since it has two uncovered constants: gwd:1954-7-17 and “Angela Merkel”. 4.3. Third step The third step consists of completing exchange samples, i.e., if the same source data can lead to different data in different exchange samples, it is then necessary to complete those exchange samples by adding target data to them. Therefore, we identify the exchange samples that have the same source data but differ in the target data, and we complete them without the user intervention. The completion of exchange samples depends on the specification of the input exchange sample. Our completion process is similar to the process described in (Alexe et al., 2011a), which proves that it is a sound and complete process. The algorithm in Fig. 10 takes a set of exchange samples as input and outputs a number of complete exchange samples. It computes if the input set needs to be completed because the same source data generates different target data. To perform this, we compute the Fig. 9. Exchange samples generated in the first step for correspondence v3. Fig. 10. Completing exchange samples. Fig. 11. Exchange samples of correspondence v1after the second step. replacements between the exchange samples that have the same source data and, if they have some missing triples, we automatically add them to complete the target data. In this case, restart indicates if new triples have been added to the exchange samples, and we iterate until no new triple is added. We extract two different exchange samples from the input set d1and d2, respectively. We compute the replacements between their source triples, and we apply each replacement to the target triples of d1; if the resulting triples are not present in the target triples of d2, we have to add them. Example 3. To illustrate this step, we present the two exchange samples that resulted from correspondence v1after the second step (see Fig. 11). There exists a single replacement between source(d12) and source(d31) (see Fig. 9), which is the following: {:David Cameron →:Angela Merkel}. When we apply it to target(d12), it results in the following triple: :Angela Merkel rdf :type gw :Person. This triple is not included in target(d31), so it is necessary to add this triple to target(d31), and the exchange sample is completed as d 31, which is depicted in Fig. 12. The intuition behind this is that we have mapped an instance of dpo :Person as gw :Person in exchange sample d12; however, in exchange sample d31, an instance of dpo:Person is not mapped onto an instance of gw :Person. Note also that Fig. 12 presents d 21 and d 25, which result from completing exchange samples d21 and d25, respectively (see Fig. 7). Our tool automatically completes the input exchange samples, which is a clear advantage with respect to some of the existing tools in the bibliography that require the intervention of the user to complete them (Alexe et al., 2011b). 4.4. Fourth step In this step, our tool prunes redundant exchange samples, i.e., samples that generate the same schema mappings. Fig. 13 shows our algorithm to prune these exchange samples. Replacements are used to detect them, i.e., two exchange samples d1and d2are redundant if there exist, at least, four replacements from the source and target triples of d1to the source and target triples of d2, and from the source and target triples of d2to the source and target triples of d1. Example 4. In our running example, d11 and d12 (see Fig. 11) are redundant since there exist two replacements from source(d11) to source(d12) and vice versa, and two other replacements from target(d11) to target(d12) and vice versa. Therefore, our tool prunes one of them randomly, e.g., d11. The same happens with exchange samples d 21 and d 25 (see Fig. 12), our tool prunes one of them randomly, e.g., d 25. Fig. 12. Completed exchange samples. 4.5. Fifth step This final step transforms each exchange sample into a schema mapping, which is built by substituting the source and target constants by variables, or blank nodes to generate labelled nulls (Fagin et al., 2005; Mallea et al., 2011). These schema mappings may be Fig. 13. Pruning exchange samples. Fig. 14. Creating schema mappings. easily transformed into SPARQL queries to exchange data between the integrated datasets. Fig. 14 shows our algorithm to transform each exchange sample into a schema mapping, which is built by substituting source and target data by variables or blank nodes, depending on whether the target data is known or not. To perform this, for each exchange sample, we retrieve its source and target constants. Then, we compute a source and a target substitution as follows: for those constants in the source, we add a fresh variable to both substitutions. For those constants that are present in the target but not in the source, we add a fresh blank node to the target substitution. Finally, we apply both substitutions to the source and target triples to generate the source and target patterns of the schema mapping. Example 5. In our running example, our tool generates three schema mappings that result from transforming exchange samples d12, d 21, and d 31 (see Figs. 11 and 12, respectively). Our tool transforms exchange sample d12 into schema mapping m12 by using the following source and target substitution: {:David Cameron →?u2}. Both substitutions are the same because all of the target constants are already present in the source substitution; so no blank nodes are generated. Furthermore, our tool transforms exchange sample d 21 into schema mapping m21 by computing the following source and target substitutions: {:Angela Merkel →?u3, “Angela Merkel →?l4}. Note that both substitutions are also the same. Our tool also transforms exchange sample d 31 into schema mapping m31. It computes the following source substitution: {:Angela Merkel →?u1, “ 1954 −07 −17 →?l0}, and the following target substitution: {:Angela Merkel →?u1, “ 1954 −07 −17 →?l0, gwd : 1954 −7−17 → :bn0}. The latter Fig. 15. Final schema mappings. comprises a blank node since constant gwd : 1954 −7−17 is not present in the source. Fig. 15 depicts schema mappings m12,m21, and m31. 5. Evaluation Our tool is supported by a graphical interface that has been implemented using Java 1.6 and Jena TDB 0.9.3 (Carroll et al., 2004). Furthermore, we have used Guava 13.0.1 to implement ancillary set operations (Google, 2014), and JGraphT 0.8.3 to compute the connected components of a set of patterns (Naveh, 2014). Our tool has a Setup module and five additional modules, each of which implements a step of our proposal, namely: Generate, Discard, Complete, Prune, and Transform. In the Setup module, the user may select the files in which the source and target data for the single exchange sample are stored. When both files are selected, the user is responsible for providing a number of n:mcorrespondences between source and target entities. The Generate module is responsible for taking the single exchange sample and the correspondences of the previous module as input, and generating the whole set of candidate exchange samples. The Discard module takes the set of candidate exchange samples as input and discards exchange samples from this set. The Complete module is responsible for taking the previous samples as input and completing them, i.e., if the same source data generate different target data in different exchange samples, it is necessary to complete those samples by adding new triples to the target data. The Prune module is responsible for pruning exchange samples that are redundant, i.e., they are transformed into the same schema mappings. Finally, the Transform module takes the previous exchange samples and transforms them into a number of schema mappings. Our experiments were run on a virtual computer that was equipped with a four-threaded Intel Xeon 3.00 GHz CPU and 16 GiB RAM, running on Windows Server 2008 (64-bits). In the rest of this section, we present the validity evaluation in Section 5.1, the