Mapping RDF knowledge bases using exchange samples

Mapping RDF knowledge bases using exchange samples Carlos R. Riveroa,∗, Inma Hernández b, David Ruiz b, Rafael Corchuelob a Rochester Institute of Technology, Department of Computer Science, 102 Lomb Memorial Dr., Rochester, NY 14623, USA b University of Seville, ETSI Informática, Avda. Reina Mercedes s/n, Sevilla E-41012, Spain Keywords: Web of Data RDF Schema mapping Data exchange abstract Nowadays, the Web of Data is in its earliest stages; it is currently organised into a variety of linked knowledge bases that have been developed independently by different organisations. RDF is one of the most popular languages to represent data in this context, which motivates the need to perform complex integration tasks amongst RDF knowledge bases. These tasks are performed using schema mappings, which are declarative specifications of the relationships amongst a source and a target knowledge base. Generating schema mappings automatically is appealing because this relieves users from the burden of handcrafting them. In the literature, the vast majority of proposals are based on the data models of the knowledge bases to be integrated, that is, on classes, properties, and constraints. In the Web of Data, there exist many data models that comprise very few constraints or no constraints at all, which has motivated some researchers to work on an alternate paradigm that does not rely on constraints. Unfortunately, the current proposals that fit this paradigm are not completely automatic. In this article, we present our proposal to automatically generate schema mappings amongst RDF knowledge bases. Its salient features are that it uses a single input exchange sample and a set of input correspondences, but does not require any constraints to be available or any user intervention; it has been validated and evaluated using many experiments that prove that it is effective and efficient in practice; the schema mappings that it produces are GLAV. Other researchers can reproduce our experiments since all of our implementations and repositories are publicly available. 1. Introduction Currently, there is an increasing interest in publishing, sharing, and exposing data on the Web, so as to evolve it into a Web of Data in which RDF is becoming pervasive [10,16,36]. There are thousands of knowledge bases available, many of which share a common purpose but have been developed by independent organisations in isolation [15,16]. Government, life sciences, geography, media, education, libraries, or scholarly publications range amongst the most popular current information domains [37]. There are many initiatives whose goal is to link these knowledge bases, which is the first step to perform complex integration processes [36]. Integration usually refers to several crucial tasks, such as data integration [68], virtual integration [38], data warehousing [32],model evolution [29], model matching [26], record linkage [42,53],ordata exchange [28]. In this article, we focus on data exchange, whose goal is to populate a target knowledge base using data that come from one or more source knowledge bases. Data exchange has been paid much attention in the database context, i.e., relational, nested-relational, or ∗Corresponding author. fax.: +1 585 475 2979. E-mail addresses: [email protected] (C.R. Rivero), [email protected] (I. Hernández), XML [8,9,28,54]. Furthermore, the emergence of RDF is motivating some authors to work on data exchange in the context of the Web of Data [11,51,62,63]. Data exchange is performed by means of schema mappings, which are declarative specifications of the relationships amongst a source and a target knowledge bases [4,5]. A schema mapping can be of the following types [44]: (1) GAV (Global-As-View), which relates one single target entity to many source entities; (2) LAV (Local-As-View), which relates one single source entity to many target entities; and (3) GLAV, which relates many source and target entities. 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 [56].Inthe literature, many proposals are based on the data models to be integrated [35,47,48,54,57,61,62]. By data model, we refer to a set of entities (that is, classes and properties) and a set of constraints that establish relationships between some entities (for instance, class Ais a specialisation of class B,propertyPhas 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 a set of entities [21,36,37,43,66]. Therefore, relying on data models with constraints to generate schema mappings is not appealing in the general context of the Web of Data. [email protected] (D. Ruiz), [email protected] (R. Corchuelo). The literature provides a variety of techniques to generate schema mappings that do not focus on data models. Unfortunately, some of them rely on handcrafting the schema mappings [15,27,45,49–51,58], which is not appealing at all; and a few others rely on exchange samples [1,2,4,56], which make them more appealing, but require user intervention, or are hybrid and require constraints to be available. In this article, we present a proposal to automatically generate schema mappings between two RDF knowledge bases using a single input exchange sample and a set of input 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 knowledge bases correspond to each other, i.e., are somewhat related [12,67,69]. These schema mappings can be easily transformed into SPARQL queries. Our proposal does not rely on constraints of the source and target data models and does not require any user intervention, not even to adapt the input exchange example so that it is feasible to generate the schema mappings. We have validated our proposal using ten data exchange problems amongst various knowledge bases. In our validation, the execution time never exceeded one second, and the data exchanged were as expected 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 proposal when data exchange problems scale. We used four synthetic data exchange patterns proposed by MostoBM [63], a benchmark for testing data exchange proposals in the context of the Web of Data. We instantiated the synthetic data exchange patterns into 2000 non-trivial data exchange problems that we used to evaluate our proposal. Our evaluation results suggest that our proposal works well as the data exchange problems scale. We also prove that the schema mappings our proposal generates are GLAV. Furthermore, we prove that the schema mappings output by our proposal fit the input correspondences, i.e., they do not lose any information and take all of the input correspondences into account. Our proposal also uses a best-effort strategy that allows the user to freely define the input exchange sample, so it is not mandatory that this exchange sample fits the output schema mappings. We implemented a research prototype that is publicly available [60], together with our repository of data exchange problems, the scripts to validate and evaluate the performance of our proposal, and our experimental results. Our goal was twofold: on the one hand, this allows other researchers to faithfully reproduce our experiments, which is crucial for the advance of science [30]; on the other hand, our implementation and our repository can be extended to cope with future requirements. Preliminary results were presented elsewhere [64].Wehaveimproved on them as follows: we present an overall picture to use our proposal; we formalise a conceptual framework that accommodates it; we describe our algorithms within the previous framework; we analyse a number of desired properties, its theoretical complexity, and make its limitations explicit; we have also validated it and evaluated how scalable it is. The rest of the article is organised as follows: in Section 2, we report on several related proposals and compare them with ours; Section 3 presents a general overview to use our proposal; Section 4 introduces our conceptual framework; Section 5 presents the algorithms of our proposal; Section 6 analyses some desired properties of our proposal and its theoretical complexity; Sections 7 and 8present our validation and scalability evaluation; and Section 9 recaps on our main conclusions. Finally, Appendix A presents some ancillary propositions that we used to support our theorems. 2. Related work In this article, our focus is on GLAV schema mappings, so we restrict our attention to proposals that generate such mappings. Our brief survey completes the picture that [65] presented elsewhere regarding proposals that generate GAV mappings. Unfortunately, we are not aware of a similar survey regarding LAV proposals. We have classified the proposals that generate GLAV schema mappings into three groups, namely: (1) handcraft-based proposals, (2) constraint-based proposals, and (3) sample-based proposals. The proposals in the first group require the user to handcraft schema mappings. In the following sections, we first survey the proposals in each group and then discuss on them. 2.1. Handcraft-based proposals There are a number of proposals that focus on handcrafting schema mappings, which are expressed as queries but can be viewed as implicitly generating schema mappings: in the proposal by Dou et al. [27], queries are represented using Web-PDDL, an ad-hoc language that was designed by the authors; then, a reasoner takes these queries as input to perform data exchange. This is similar in spirit to the proposals by Bizer and Schultz [15], Parreiras et al. [51] and Ressler et al. [58], the difference being the language used to represent the queries: Bizer and Schultz [15], and Ressler et al. [58] use SPARQL, whereas Parreiras et al. [51] use an extension of the Object Constraint Language (OCL) that supports RDF knowledge bases. Mocan and Cimpian [49] presented a framework to describe schema mappings in terms of first-order logic formulae that can be mapped onto WSML rules very easily. Their proposal is similar in spirit to the one by Omelayenko [50], whose focus was on B2B applications, and the one by Maedche et al. [45], whose focus was on modelling schema mappings in a general-purpose setting. 2.2. Constraint-based proposals These proposals focus on generating schema mappings building on correspondences and constraints on the source and target data models. These proposals are able to compute subsets of data in the source knowledge base that need to be exchanged as a whole, and subsets of data in the target knowledge base that need to be created as a whole [62]. 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 [54]. Popa et al. [54] presented a seminar proposal regarding the generation of schema mappings amongst nested-relational data models, which was later incorporated into IBM’s Clio [35]. This proposal works with 1:1 correspondences, i.e., they only relate one entity in the source with one entity in the target, and was later extended to work with n:1 correspondences by Raffio et al. [57], who used a visual mapping language to represent complex correspondences, including grouping functions, aggregation functions, or dependent correspondences. Mecca et al. [47] extended the previous proposals by computing core schema mappings, a type of schema mapping that generates non-redundant target data when performing data exchange. In the context of RDF data models, Mergen and Heuser [48] devised an automated proposal that works with a subset of taxonomies. Their algorithm tries to find subsets of correspondences that are involved in the taxonomies, and they are translated into executable scripts that are represented in an ad-hoc script language. The proposals by Rivero et al. [61,62] are able to work with RDF data models whose constraints are interpreted as graphs that are traversed to compute source and target kernels, each of which 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 automatically translated into SPARQL queries. Note that both the executable scripts by Mergen and Heuser [48], and the SPARQL queries by Rivero et al. [61,62] can be seen as representations of schema mappings in specific-purpose languages. 2.3. Sample-based proposals These proposals aim to generate schema mappings from a set of exchange samples. In the relational or nested-relational contexts, Alexe et al. [1] devised a proposal that helps users understand and maintain generated schema mappings by extracting exchange samples from the source and target knowledge bases. This proposal uses Clio to generate schema mappings based on constraints of the data models, 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 those source data. Alexe et al. [2] presented Muse, which aims to help users generate and understand schema mappings building on exchange samples. Muse assumes that source and target data models, together with their constraints, exist, and it is able to infer grouping functions by analysing the answers to a number of questions it poses to the users. Alexe et al. [4] devised a proposal to generate a number of schema mappings by means of a finite set of exchange samples. This proposal is able to compute 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 shall result in erroneous target data. If the input set of exchange samples have not any incoherences, then it generates the schema mappings. These authors developed a conceptual framework to conduct systematic research on exchange samples in the database context [6]. Furthermore, Qian et al. [56] presented a proposal that is based on exchange samples of target data only. The 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 knowledge bases represents a correspondence between two entities. Finally, schema mappings are generated by means of these correspondences and the constraints of the source and target data models. 2.4. Discussion After surveying current proposals to generate schema mappings, we conclude that some of them focus on handcrafting them [15,27,45,49–51,58], 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 [52]. Contrarily, our proposal 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 proposals [35,47,48,54,57,61,62],they are not so appealing in the general context of the Web of Data because RDF allows to represent data building solely on entities, i.e., without any constraints, which is very common in this context [21,36,37,43]. Contrarily to the constraint-based proposals, ours does not rely on constraints of the data models that are integrated to generate schema mappings, but on a single exchange sample and a set of correspondences, which fits perfectly in the general context of the Web of Data. Regarding sample-based proposals, some of them assume that source and target data models exist, together with their constraints [1,2,56]. Therefore, they rely on a hypothesis that, as was the case for the constraint-based proposals, does not generally hold in the Web of Data. The proposal by Alexe et al. [4] 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 proposal finds the input exchange samples inappropriate to generate schema mappings, the user is responsible for adapting them. Contrarily, our proposal requires the user to provide a single exchange sample and a set of correspondences and adapts it automatically, if necessary. Finally, to the best of our knowledge, our proposal is the first one that is able to work with n:mcorrespondences that generalise 1:1 and n:1 correspondences in other proposals. 3. Overview Fig. 1 presents a real-world data exchange problem that we use to illustrate our proposal. In this problem, our goal is to generate a number of schema mappings to perform data exchange from a part of DBpedia 3.8 [17] to a part of Freebase [19]. On one hand, DBpedia is a community effort to annotate and make the data stored at Wikipedia accessible by means of RDF technologies. On the other hand, Freebase is a knowledge base that models general human knowledge in which the data is collaboratively created and maintained. The initial step of our proposal consists of specifying the input data, i.e., a single exchange sample and a set of correspondences. The single exchange sample is expected to be an exact sample of the source and target data that the user wishes to exchange. For instance, the exchange sample in Fig. 1 (see dEX in Step 0) comprises a set of source triples regarding Clint Eastwood and one of his marriages, and a set of target triples that specify how these data are structured according to the target entities. For the sake of brevity, we have simplified Clint_Eastwood to CEastwood,Dina_Eastwood to DEastwood, and Clint Eastwood to Clint East. This exchange sample is represented using the N3 notation [13], which is a non-XML serialisation of RDF that has been designed for aiding human-readability. We use the prefixes in Table 1, in which the first row specifies the default URI. Ourproposaltakesanumberofn:mcorrespondences over the source and target entities as input. This set indicates the relationships that exist amongst the source and target entities in the 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. Note that it is possible to automatically discover these correspondences [12];however, finding them is orthogonal to the problem of generating schema mappings, which is the reason why we do not discuss this problem further. Fig. 1 (see the right side of Step 0) shows three correspondences, namely: v1indicates that there exists a relation between a person in both the DBpedia and Freebase knowledge bases; v2states that the name of a person in DBpedia is related to the alias of a common topic in Freebase; and v3indicates that a person and her/his spouse in DB- pedia are related to a marriage in Freebase. In the first step, our proposal 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, we combine all of the pieces of connected data that involve the entities in every correspondence. For instance, Fig. 1 (see Steps 1 and 2) shows some of the candidate exchange samples that result from correspondence v1,namely:d11 ,d12,andd13. Note that we group exchange samples by correspondence. These candidate exchange samples are generated by performing the Cartesian product of the following data: {CEastwood rdf :type dp:Person, DEastwood rdf :type dp:Person} × {CEastwood rdf :type fp:person, DEastwood rdf :type fp:person} The second step consists of discarding candidate exchange samples that are not useful to generate the final set of schema mappings. We keep candidate exchange samples in which there is, at least, a subset of target data that can be generated using the source data, and Fig. 1. A running example to illustrate our proposal. we minimise the target data that do not exist in the source. For instance, in Fig. 1 (See Steps 1 and 2), we discard d11 because constant DEastwood in the target triple does not appear in the source triples; similarly, we discard d22 because constant “Clint East.” does not appear in any source triple. Note, however, that exchange samples d31 and d32 are kept, even though identifier fb:m.02kkj5 is not present in any source triple; we do not require every identifier or literal in the target to be present in the source because we can complete the exchange samples automatically, but require that at least a minimum number of constants are present in both the source and the target so that our procedure can work. 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. For instance, in Fig. 1 (see Steps 3 and 4), we complete d21 by adding CEastwood rdf:type fp:person. This is due to the fact that exchange sample d13 indicates that CEastwood rdf:type Person can be exchanged as CEastwood rdf:type fp:person. Unless otherwise stated, our proposal interprets that every constant can be generalised to a variable, which Table 1 Summary of prefixes. means that d13 is interpreted as every identifier of type Person can be exchanged as an identifier of type fp:person. In the fourth step, we prune redundant exchange samples, i.e., samples that shall generate the same schema mappings. For instance, in Fig. 1 (see Steps 3 and 4), we prune d13 since it shall generate the same schema mapping as exchange sample d12. The same occurs with d 31 and d 32. Finally, the fifth 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 [28,46]. These schema mappings may be easily transformed into SPARQL queries to exchange data between the integrated knowledge bases. For instance, in Fig. 1 (see Step 5), m12 is generated by means of d12,m21 results from d 21,and m31 results from d 31.Notethatwehave also used the N3 notation to represent both left and right components of schema mappings. 4. Conceptual framework In this section, we present the conceptual framework that we use to describe our proposal. We define its foundations, triples, schema mappings, homomorphisms, exchange samples, correspondences, and data exchange problems. 4.1. Foundations The data model of a knowledge base is composed of entities, which are denoted by means of URIs. Entities can be classified into classes and properties, which can be further classified into data and object properties. We denote the sets of classes, data properties, and object properties as follows: [Class,DataProperty,ObjectProperty] and define the set of entities and properties as follows: Entity == Class ∪Property Property == DataProperty ∪ObjectProperty Class, DataProperty,andObjectProperty are pairwise disjoint sets, that is: |(Class ∩DataProperty =∅)∧(Class ∩ObjectProperty =∅)∧ (DataProperty ∩ObjectProperty =∅) In addition to a data model, a knowledge base also comprises a set of constants to describe the data. A constant can be an identifier, which refers to a piece of data that can be modelled by means of a URI, or a literal, which denotes a value of a simple data type. Furthermore, it is possible to define blank nodes, which denote anonymous data. We denote these sets as follows: [Identifier,Literal,BlankNode] and define the set of constants as follows: Constant == Identi f ier ∪Literal Identifier, Literal,andBlankNode are pairwise disjoint sets [41],that is: |(Identi f ier ∩Literal =∅)∧(Identi f ier ∩BlankNode =∅) ∧(Literal ∩BlankNode =∅) Example 1. Fig. 1 (see the left side of Step 0) shows that dp:Person is a class, foaf:name is a data property, dp:spouse is an object property, and they are represented by means of URIs. Furthermore, CEastwood is an identifier, and “Clint East.” is a literal. _:Xis an example of a blank node (see m31 in Step 5). 4.2. Triples and schema mappings A knowledge base comprises a set of triples, each of which is a three tuple in which the first element is called subject, the second predicate, and the third object. Triple == Subject ×Predicate ×Object Subject == Constant Predicate == Property ∪{rdf:type} Object == Constant ∪Class In our framework, it is mandatory for all triples to be ground, i.e., to not comprise any blank nodes. This is not a shortcoming since blank nodes in a knowledge base can be very easily preprocessed and transformed into regular identifiers. Note that there is a contradiction between the RDF and the SPARQL recommendations. On the one hand, the RDF recommendation does not allow to use literals in the subject of a triple [41];onthe other hand, the SPARQL recommendation actually allows to use literals in the subject of a triple [55]. Since our goal is to generate schema mappings that may be easily transformed into SPARQL queries, we decided to include literals in the subject of triples. Note, too, that a predicate can be a property or rdf:type, which is a predefined RDF construct that is not included in set Property. In our proposal, schema mappings are conjunctive queries [44]. Such queries consist of a target part that specifies which triples need to be constructed, and a source part that specifies which triples need to be retrieved. These parts can then be represented as sets of triple patterns that are implicitly connected by means of 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 the rest of this article, we refer to triple patterns as patterns for the sake of brevity. We denote the set of all variables as follows: [Variable] and define the set of all patterns as follows: Pattern == Subject?×Predicate ×Object? Subject?== Subject ∪Variable ∪BlankNode Object?== Object ∪Variable ∪BlankNode A schema mapping can thus be represented as a two tuple in which the first part corresponds to the set of source patterns, and the second part corresponds to the set of target patterns. We then define the set of all schema mappings as the inner Cartesian product of the power set of patterns, that is: SchemaMapping == PPattern ×PPattern Note that these schema mappings may be easily transformed into SPARQL queries. For the sake of convenience, we define an instance of a class as a pattern of the form (s, rdf:type, c), in which s∈Subject?, and c∈Class; and an instance of a property as a pattern of the form (s, p, o), in which s∈Subject?,p∈Property,ando∈Object?.Furthermore, we define the following projection functions: subject :Pattern →Subject? predicate :Pattern →Predicate ob ject :Pattern →Object? ------------------------------ ∀s:Subject?;p:Predicate;o:Object?;t:Pattern |t=(s,p,o)• subject(t)=s∧ predicate(t)=p∧ ob ject(t)=o Note that Triple ⊆Pattern, which implies that the previous projection functions can be applied to both triples and patterns. We also define the following ancillary functions: constants :PPattern →PConstant entities :PPattern →PEntity classes :PPattern →PClass properties :PPattern →PProperty ------------------------------ ∀T:PPattern• constants(T)={c:Constant |∃t:Pattern |t∈T• c=subject(t)∨c=ob ject (t)}∧ entities(T)={e:Entity |∃t:Pattern |t∈T• e=predicate(t)∨e=ob ject (t)}∧ classes(T)={c:Class |∃t:Pattern |t∈T• predicate(t)=rdf:type ⇒c=ob ject(t)}∧ properties(T)={p:Property |∃t:Pattern |t∈T• predicate(t)= rdf:type ⇒p=predicate(t)} Example 2. Fig. 1 (see the left side of Step 0) shows two sample sets of triples. In the left set, triples assert that CEastwood and DEastwood are instances of the dp:Person class. Furthermore, they assert that CEastwood has “Clint East.” and “Clint” as names by means of the foaf:name property, and that CEastwood is married to DEastwood by means of property dp:spouse. Fig. 1 (see Step 5) shows three sample schema mappings in which the left side stands for the set of source patterns and the right side stands for the set of target patterns. Furthermore, ?p,?p1,and?p2 are variables, and _:Xis a blank node. m12 reclassifies instances of class dp:Person into instances of class fp:person; m21 exchanges instances of class dp:Person together with their names (property foaf:name) as instances of class fp:person and their names by means of property ft:alias; finally, m31 translates property dp:spouse into a more complex structure that comprises properties fpp:spouse_sand fpm:spouse, and a new instance of the fp:marriage class that is generated using a blank node, since this information is not present in the source. 4.3. Homomorphisms and exchange samples 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. We formally define a homomorphism as a finite map from subjects or variables onto themselves, namely: Homomorphisms specialise into replacements and substitutions. On the one hand, a replacement is a finite map from constants onto constants; on the other hand, a substitution is a finite map from constants onto variables or blank nodes. We formally define them as follows: Generally speaking, a knowledge base is a set of triples. Regarding our proposal, we restrict our attention to the triples that are of the form (c, rdf:type, C), in which cis a constant and Cis a class, or (c1,p, c2), in which c1and c2are constants and pis a property. Therefore, we define the set of knowledge bases as follows: KnowledgeBase == {T:PTriple | ∀t:Triple;c,c1,c2:Constant;C:Class;p:Property |t∈T• (t=(c,rdf:type,C)⇒c∈constants(T)∧C∈classes(T)) ∨ (t=(c1,p,c2)⇒{c1,c2}⊆constants(T)∧p∈properties(T)) Note that the previous definition is not a shortcoming since we are able to model the most common triples in the general context of the Web of Data [31]. An exchange sample comprises a source knowledge base and a target knowledge base. We define the set of exchange samples as follows: ExchangeSample == KnowledgeBase ×KnowledgeBase For the sake of convenience, we define the following projection functions: source :ExchangeSample →KnowledgeBase target :ExchangeSample →KnowledgeBase ------------------------------ ∀d:ExchangeSample;TS,TT:KnowledgeBase |d=(TS,TT)• source(d)=TS∧ target(d)=TT Example 3. Fig. 1 (see the left side of Step 0) presents an exchange sample that comprises a set of source triples and another set of target triples. Furthermore, {CEastwood→CEastwood,“Clint East.”→“Clint”} is a sample replacement that maps CEastwood to CEastwood,and “Clint East.” to “Clint”. Finally, {CEastwood→?p,“Clint East.”→?n}isa sample substitution that maps CEastwood to ?p,and“Clint East.to?n. 4.4. Correspondences and data exchange problems A correspondence is a hint that relates two sets of entities, i.e., they are defined at the data model level of a knowledge base. Note Fig. 2. Algorithm to generate schema mappings. that this entails that the correspondences with which we can deal are n:mcorrespondences. We define the set of correspondences as follows: Correspondence == PEntity ×PEntity For the sake of convenience, we define the following projection functions: source :Correspondence →PEntity target :Correspondence →PEntity ------------------------------ ∀c:Correspondence;ES,ET:PEntity |c=(ES,ET)• source(c)=ES∧ target(c)=ET A data exchange problem comprises a single exchange sample and a number of correspondences that relate entities in this exchange sample. We define the set of all data exchange problems as follows: DataExchangeProblem == {d:ExchangeSample;V: PCorrespondence |∀v:Correspondence |v∈V• source(v)⊆entities(source(d)) ∧ target(v)⊆entities(target(d))} For the sake of convenience, we define the following projection functions: sample :DataExchangeProblem →ExchangeSample correspondences :DataExchangeProblem →PCorrespondence ------------------------------ ∀d:ExchangeSample;V:PCorrespondence;p:DataExchangeProblem |p=(d,V)• sample(p)=d∧ correspondences(p)=V Example 4. Fig. 1 (see the right side of Step 0) presents three sample correspondences that relate the entities that appear in the exchange sample, namely: v1relates a source entity with a target entity, v2re- lates two source entities with one target entity, and v3relates two source entities with three target entities. Both the single exchange sample and the correspondences form the data exchange problem that we use to illustrate our proposal (see Section 3). 5. Generating schema mappings Our proposal takes a data exchange problem as input and generates a number of schema mappings to solve that problem without the intervention of a user. Fig. 2 presents the main algorithm of our proposal, which comprises five steps. The first step takes a correspondence and a single exchange sample as input, and it is responsible for Fig. 3. Algorithm to create candidate exchange samples. generating a number of candidate exchange samples as output, 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. In the second step, our proposal ensures that for every candidate exchange sample there is, at least, a subset of target data that can be generated using the source data, and it minimises the target data that do not exist in the source. The third step takes the previous set of exchange samples as input and completes them, i.e., it ensures that it is possible to generate schema mappings using them. To perform this, our proposal adds new triples to the input exchange samples to guarantee that the same target data is generated by means of the same source data. The fourth step prunes those exchange samples that are redundant and, therefore, it is expected that they generate the same schema mappings. Finally, the fifth step takes the final set of exchange samples as input, and it transforms them into schema mappings by substituting source and target constants by fresh variables and/or blank nodes. 5.1. First step: create candidate exchange samples Fig. 3 shows our algorithm to create candidate exchange samples from a given correspondence and a single exchange sample. Each candidate exchange sample 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, we combine all connected triples that comprise the entities in the correspondence. First, we compute the triples that are related to correspondence vfor the single exchange sample d, i.e., those triples that comprise the entities related by v. The results are stored in a set of knowledge bases. Then, we compute the distributive Cartesian product over the triples that are related to source(v), and over the triples that are related to target(v). This Cartesian product, which we denote as , comprises all of the possible combinations in the set of knowledge bases, and it results in another set of knowledge bases. For instance, for the following set of knowledge bases {{a, b, c}, {d, e}, {f}}, where a, b, c, d, e,andfdenote triples, the distributive Cartesian product is {{a, d, f}, {a, e, f}, {b, d, f}, {b, e, f}, {c, d, f}, {c, e, f}}. We iterate over each set of source and target knowledge bases, and we transform them into exchange samples only if each knowledge base comprises a single connected component, i.e., every triple is related to every other triple, directly or indirectly. We present the algorithm to compute the triples that are related to a set of entities in Fig. 4. It works on an input set of entities Eand an input knowledge base T, and returns a set of knowledge bases that Fig. 4. Algorithm to compute the triples that are related to a set of entities. Fig. 5. Algorithm to compute the connected components of a knowledge base. has all of the triples in Twhose entities are in E. To perform this, we iterate over Eand, for each entity, we iterate over Tand check whether or not each triple is related to the current entity, i.e., if the entity is a class, it must be the object of the triple, whereas if it is a property, it must be the predicate of the triple. This set of triples is added to the final set. The algorithm to compute the connected components of a set of triples is presented in Fig. 5. In the first part of the algorithm, we create an undirected graph in which set Nstores the vertices, and set A stores the arcs of the graph. For each class instance, we add a vertex with the subject of the triple, and for each property instance, we add two vertices (the subject and the object), and an arc between them both. In the end, we use the findConnectedComponents algorithm to compute the connected components of this graph. We do not provide any additional details on this algorithm since it is well-known in the literature [40]. Example 5. To illustrate the generation of candidate exchange samples, we focus on correspondence v2in our running example. Its source entities are dp:Person and foaf:name. The triples that comprise dp:Person are the following: (t1)CEastwood rdf :type dp:Person Fig. 6. Algorithm to discard candidate exchange samples. (t2)DEastwood rdf :type dp:Person Furthermore, the triples that comprise foaf:name are the following: (t3)CEastwood f oa f :name “Clint East.” (t4)CEastwood f oa f :name “Clint” Algorithm computeRelatedTriples outputs the following set in this case: GS={{t1,t2},{t3,t4}}; the distributive Cartesian product of this set is GS={{t1,t3},{t1,t4},{t2,t3},{t2,t4}}. The target entity of v2 is ft:alias, and the triples that comprise it are the following: (t6)CEastwood f t:alias “Clint East.” (t7)CEastwood f t:alias “Clint” Note that GT={{t6,t7}},and GT={{t6},{t7}}. Additionally, in sets {{t2,t3}, {t2,t4}} ⊆GS, each set has 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. Finally, candidate exchange samples are generated by combining the source triples in GSand the target triples in GT.Someof them are depicted in our running example, e.g., d21 =({t1,t3},{t6}), or d22 =({t1,t4},{t6}). 5.2. Second step: discard candidate exchange samples Fig. 6 shows our algorithm to discard candidate exchange samples. An exchange example is kept or discarded according to its 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. 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 shall comprise as less blank nodes as possible. Furthermore, this step allows us to disambiguate schema mappings, i.e., if several schema mappings may be generated for the same correspondence, we only generate those schema mappings that give us the maximum information to generate the target. Schema mapping disambiguation is a well-known issue when generating schema mappings [2], and we have devised the previously described simple, yet effective technique to solve it. Fig. 7. Algorithm to compute the replacements between two knowledge bases. Example 6. In our running example, we discard exchange sample d11 , which results from correspondence v1, since it has zero covered constants. Furthermore, the minimum number of uncovered constants in the exchange samples of v2is equal to zero, since every constant in d21 is covered; therefore, we discard exchange sample d22 because it has one uncovered constant: “Clint East.”. Furthermore, the minimum number of uncovered constants in the exchange samples that result from correspondence v3is equal to one, since fb:m.02kklj5is not present in the source of any exchange sample. 5.3. Third step: complete exchange samples This step consists of completing exchange samples, i.e., if the same source data generate different target data in different exchange samples, it is necessary to complete those samples by adding target data. Therefore, we identify those exchange samples that have the same source data but differ in the target data, and we complete them. Replacements lie at the heart of this step, so we present how we compute replacements in Fig. 7. This algorithm takes knowledge bases T1and T2as input and it first computes the candidate equivalences between them. Each candidate equivalence stands for a constant in T1that is related to another constant in T2,andweformally define them as the following set of pairs: Equivalence == Constant ×Constant After computing these equivalences, we compute their distributive Cartesian product. If every candidate equivalence relates a given constant in T1to the same constant in T2, we then transform the set of candidate equivalences into a candidate replacement h. Finally, if the triples that result from applying hto T1are included in T2,wethen add hto the output set, since this means that it is actually a replacement from T1to T2. Fig. 8 shows the algorithm to compute the candidate equivalences between two input knowledge bases T1and T2. We iterate over the whole set of triples in T1and, for each triple t1in T1, we use two different sets: in the first set, ES, we store the candidate equivalences that relate the subject of t1to another constant in T2;inthesecond Fig. 8. Algorithm to compute the candidate equivalences between two knowledge bases. set, EO, we store those candidate equivalences that relate the object of t1to another constant in T2. Then, for each triple t2in T2that has the same predicate as t1, we update both sets of candidate equivalences if t2is a property instance, but only the first set if t2is a class instance. Finally, we update the output set with one or both sets. We apply a homomorphism to a knowledge base using the algorithm in Fig. 9, in which, for every triple, we transform its subject if it belongs to the domain of the homomorphism, we keep the predicate as is, and we transform the object if it belongs to the domain of the homomorphism. Note that this algorithm can be applied to both replacements and substitutions (see Section 4.3). Example 7. To illustrate the computation of replacements, we first compute the candidate equivalences between source(d12) and source(d21) in our running example, which is the following set: Q1={{(DEastwood,CEastwood)}}. Furthermore, Q1= {{(DEastwood,CEastwood)}} is the resulting distributive Cartesian product, which is automatically transformed into a candidate replacement since it relates the same source constant to the same target constant. This candidate replacement is: {DEastwood→CEastwood}. To illustrate the application of replacements, we apply the previous candidate replacement to source(d12) in our running example, and we get the following triple: CEastwood rdf:type dp:Person, which is present in source(d21); therefore, we conclude that {DEastwood→CEastwood} is a replacement between source(d12)and source(d21). 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 Fig. 15. Process to evaluate the scalability of our proposal. Fig. 16. Scalability results of two data exchange patterns. the source or target knowledge bases. Lallows to scale the structure of these knowledge bases in depth. •Number of related classes (C): Number of classes related to each class by specialisation or object properties. Callows to scale the structure of these knowledge bases in breadth. •Number of data properties (D) of the source and target knowledge bases. In our experiments, we used the following values for the previous parameters to instantiate our data exchange problems: L={1,2,3,4,5},C={1,2,3,4,5},and D={250,500,750, 1000,1250,1500,1750,2000,2250,2500,2750,3000,3250,3500, 3750,4000,4250,4500,4750,5000}.Wesettherestoftheparameters that deal with the scaling of the data to the following values: I=5000,IT=5,ID=5,and IO=5. As a conclusion, we instantiated 500 data exchange problems for each data exchange pattern. Each of these data exchange problems comprise a number of schema mappings to perform data exchange, a number of correspondences, and a populated source knowledge base with synthetic data. Therefore, we added a new functionality to MostoBM to generate a source and a target exchange sample to evaluate our proposal. To perform this, we generate the source exchange sample by generating a single instance for each source entity and, using the schema mappings generated by MostoBM, we get the target exchange sample by exchanging the source data. To provide an overall idea of the size of these data exchange problems, the number of source and target classes ranges between 3 and 7812, the number of source and target data properties ranges between 250 and 5000, and the number of source and target object properties ranges between 2 and 7811. The conclusion is that these problems are synthetic but not trivial in general. 8.2. Evaluation process Fig. 15 presents the evaluation process of the scalability of our proposal, which comprises three steps, namely: 1. We use MostoBM to generate the repository of data exchange problems, which results from instantiating a set of data exchange patterns with several values of the input parameters. 2. After generating the repository, it is necessary to run the data exchange problems that it comprises. Running a single data exchange problem may take hours or even days to complete, since it is executed 25 times (see below). This makes it necessary to use the Monte Carlo method to select a subset of data exchange problems to execute randomly. The issue that remains is to determine the size of this subset. To provide a precise figure on the number of data exchange problems to run, we rely on Cochran’s formula [24], which is based on the variance of the performance variable, i.e., the time that our proposal takes to output schema mappings. In the worst case, when the variance being studied is very high, this number is equal to |P|/2, in which |P| is the total number of data exchange problems for a given data exchange pattern. Therefore, we execute 250 =500/2 problems for each data exchange pattern. 3. Finally, we perform the evaluation process of our validation to actually run the data exchange problems (see Section 7.2). We have implemented this evaluation process in a script that uses Java 1.6, and Jena TDB 0.9.3, which is documented by means of a user manual. Our experiments were run on a virtual computer that was equipped with a four-threaded Intel Xeon 3.00 GHz CPU and 16GB RAM, running on Windows Server 2008 (64-bits). 8.3. Evaluation results Figs. 16 and 17 present our evaluation results, in which we compare the time our proposal took to generate the schema mappings in the data exchange problems to the number of correspondences in each data exchange problem. Note that, in these problems, the number of source and target triples of the single exchange sample are equal to the number of source and target entities, and they are also equal to the number of correspondences, which are the variables in Fig. 17. Scalability results of two data exchange patterns. our theoretical complexity study (see Section 6.3). Since the number is the same, we only focus on correspondences in this evaluation. Note also that the scaling of correspondences is not linear since the correspondences in the data exchange problems that MostoBM generates are not linear regarding the parameters. Since timings are imprecise in nature, we repeated each experiment 25 times and averaged the results after discarding roughly 0.01% outliers using the well-known Chevischev’s inequality. For each data exchange problem, we checked that the target data that result from exchanging data using the schema mappings of MostoBM were equivalent to exchanging data with our automatically generated schema mappings. From our experimental results we can draw the following conclusions: •The behaviour of Lift Properties and Sink Properties is similar, as it was also the case for Extract Subclasses and Extract Superclasses. •We also computed the minimum squared error tendency line, that is, the one that maximises the R2coefficient, and found out that the behaviour is nearly quadratic in every case. 9. Conclusions In the literature, there are a number of proposals to generate schema mappings that rely on data models that must provide entities and constraints. They are not appealing in the general context of the Web of Data because some of them rely on handcrafting the mappings; some others rely on exploiting the constraints in the data models and the usual knowledge bases in this context have a few or no constraints at all; and a few others rely on exchange samples but require user intervention, or are hybrid and require constraints to be available. In this article, we present a proposal to automatically generate schema mappings amongst RDF knowledge bases using a single exchange sample and a set of n:mcorrespondences. It does not rely on constraints of the source and target data models and does not require any user intervention. We have validated our proposal using ten data exchange problems amongst the DBpedia, Freebase, and Gov- WILD knowledge bases. The time to execute this validation never exceeded one second, and the data exchanged were as expected in every case, which suggest that it is very efficient in practice and that the generated schema mappings are appropriate. We have also evaluated the performance of our proposal when data exchange problems scale. To perform this, we have used four synthetic data exchange patterns proposed by MostoBM, a benchmark for testing data exchange proposals in the context of the Web of Data. Synthetic data exchange patterns are instantiated into 2 000 data exchange problems that we have used to evaluate our proposal. Our evaluation results suggest that it works quite well as the data exchange problems it faces scale. We have proved that the schema mappings we produce are GLAV. Furthermore, we have proved that the schema mappings output by our proposal fit the input correspondences. We have implemented a research prototype that is publicly available, together with our repository of data exchange problems, the scripts to validate and evaluate the scalability of our proposal, and all of the experimental data regarding the validation and the performance presented in this article. Our goal is twofold: on the one hand, it allows other researchers to faithfully reproduce our experiments, which is crucial for the advance of science; on the other hand, our implementation, repository, and experimental data can be extended to cope with future requirements. Acknowledgements The work that we present in this article was supported by the European Commission (FEDER), the Spanish and the Andalusian R&D&I programmes with the following Grants: TIN2007-64119,P07- TIC-2602,P08-TIC-4100,TIN2008-04718-E,TIN2010-21744,TIN2010- 09809-E,TIN2010-10811-E,TIN2010-09988-E,TIN2011-15497-E,and TIN2013-40848-R. Appendix A. Ancillary propositions In this section we present some ancillary propositions that we used to support our theorems. A1. Generation of GLAV schema mappings Proposition 1 (Types of source patterns).A source pattern output by Algorithm createSchemaMappings can only be of the following forms: •?xrdf:type C, where ?x denotes a variable, and C denotes a source class. •?xp?y, where ?xand?y denote variables, and p denotes a source property. Proof. Lines 15 and 19 in Algorithm createSchemaMappings create a substitution for each constant in the source input triples that transforms it into a fresh variable. Then, in line 24, this substitution is applied to the source triples. Our proposal only works with two types of triples (see Section 4.3), which are the following: •crdf:type C,wherecdenotes a constant, and Cdenotes a source class. This triple is substituted by ?xrdf:type C,where?xdenotes a variable. •c1pc 2,wherec1and c2denote constants, and pdenotes a source property. This triple is substituted by ?xp?y,where?xand ?ydenote variables.  Proposition 2 (Types of target patterns).A target pattern output by Algorithm createSchemaMappings can only be of the following forms: •μrdf:type C, where μdenotes a variable or a blank node, and C denotes a source class. •μpν,whereμand νdenote variables or blank nodes, and p denotes asourceproperty. Proof. Lines 15 and 19 in Algorithm createSchemaMappings create a substitution for constants that are shared by the source and target triples, which are substituted by the same fresh variables. Furthermore, lines 20 and 22 create a substitution for target constants that are not present in the source, which are substituted by the same blank nodes. Our proposal only works with two types of triples (see Section 4.3), which are the following: •crdf:type C,wherecdenotes a constant, and Cdenotes a source class. This triple is substituted by μrdf:type C,whereμdenotes a variable if cis present in the source, or a blank node if it is not present. •c1pc 2,wherec1and c2denote constants, and pdenotes a source property. This triple is substituted by μpν,whereμand νdenote variables if c1and c2are present in the source, or blank nodes if they are not present.  A2. Fitting correspondences Proposition 3 (Source connected components).A schema mapping output by Algorithm generateSchemaMappings comprises a unique connected component in the source. Proof. Algorithm createCandidateExchangeSamples generates a number of exchange samples, each of which comprises a unique connected component in the source, which is guaranteed by enforcing this condition (see Line 14).  Proposition 4 (Target connected components).A schema mapping output by Algorithm generateSchemaMappings comprises a unique connected component in the target. Proof. Algorithm createCandidateExchangeSamples generates a number of exchange samples, each of which comprises a unique connected component in the target, which is guaranteed by enforcing this condition (see Line 16).  A3. Analysis of complexity Proposition 5 (Create candidate exchange samples, see Fig. 3).Let v and d be a correspondence and an exchange sample, respectively. An upper bound to the time a call to createCandidateExchangeSamples(v, d) requires to terminate is O(ests+ettt+tes s+tes stet t),where tsdenotes the number of source triples in d, ttdenotes the number of target triples in d, esdenotes the number of source entities in v, and etdenotes the number of target entities in v. In the worst case, the number of exchange samples that this algorithm computes is equal to tes stet t. Proof. Algorithm createCandidateExchangeSamples performs two calls to Algorithm computeRelatedTriples, which, according to Proposition 6, terminates in O(et) time, where edenotes the number of entities and tdenotes the number of triples. Therefore, these two calls terminate in O(ests+ettt)time. Then, it iterates tes stimes over the distributive Cartesian product of GS.Ineachiteration,we check if the set of triples has a single connected component, which, according to Proposition 7, terminates in O(ts) time. Additionally, this algorithm iterates over the distributive Cartesian product of GT and, in each iteration, it checks if the set of triples has a single connected component. As a conclusion, O(ests+ettt+tes s(ts+tet ttt)) = O(ests+ettt+tes s+tes stet t)is an upper bound to the time a call to this algorithm requires to terminate. In the worst case, we add a new exchange sample in each iteration of the two loops, therefore, we add tes stet texchange samples to the output set.  Proposition 6 (Compute related triples, see Fig. 4).Let E be a set of entities, and T be a knowledge base. A call to computeRelatedTriples(E, T)terminates in O(et)time, where e denotes the number of entities in E, and t denotes the number of triples in T. In the worst case, this algorithm outputs a set of knowledge bases in which the principal set contains e sets, and the internal knowledge bases contain t triples each. Proof. Algorithm computeRelatedTriples iterates over the whole set of entities and, for each entity, it iterates over the triples of the input knowledge base. As a conclusion, it terminates in O(et)time. In the worst case, for each entity in E, it adds a new knowledge base to the final set. Additionally, in the worst case, every triple in Tis related to each entity in E, which adds every triple in Tto the internal knowledge base. Therefore, the principal set that Algorithm computeRelatedTriples outputs contains esets, and the internal knowledge bases contain ttriples in the worst case.  Proposition 7 (Compute connected components, see Fig. 5).Let T be a knowledge base. O(t), where t denotes the number of triples in T, is an upper bound to the time a call to computeConnectedComponents(T) requires to terminate. Proof. Algorithm computeConnectedComponents iterates over the whole set of input triples, and it creates a graph in which, in the worst case, the number of vertices is equal to 2t,andthenumberofarcs is equal to t. According to Hopcroft and Tarjan [40],Algorithmfind- ConnectedComponents terminates in O(max{n, a}) time, where nand aare the number of nodes and arcs of the input graph, respectively. In our case, ais equal to 2tand nis equal to t; therefore, Algorithm findConnectedComponents terminates in O(2t)time. As a conclusion, O(t+2t)=O(t)is an upper bound to the time a call to computeConnectedComponents requires to terminate.  Proposition 8 (Discard candidate exchange samples, see Fig. 6).Let D be a set of exchange samples. Algorithm discardCandidateExchangeSamples(D)terminates in O(d)time, where d denotes the number of exchange samples in D. Proof. Algorithm discardCandidateExchangeSamples iterates two times over the whole input set of exchange samples, and the operations performed can be safely assumed to terminate in O(1) time. As a conclusion, it terminates in O(d)time.  Proposition 9 (Compute replacements, see Fig. 7).Let T1and T2be two knowledge bases. O(t4 1(2t2)t1)is an upper bound to the time a call to computeReplacements(T1,T2)requires to terminate, where t1and t2 denote the number of triples in T1and T2,respectively. In the worst case, this algorithm outputs (2t2)2t1replacements. Proof. The computeReplacements algorithm performs a unique call to Algorithm computeCandidateEquivalences for which, according to Proposition 10,O(t1t2) is an upper bound of its worst-case complexity. It iterates over the distributive Cartesian product of the set outputbyAlgorithmcomputeCandidateEquivalences, in which, according to Proposition 10, the principal set contains 2t1sets, and the internal knowledge bases contain 2t2equivalences; therefore, an upper bound tothenumberofiterationsis(2t2)2t1. Additionally, in each iteration, it iterates four times over the equivalences in the internal knowledge bases to check if every candidate equivalence relates a given constant in T1to the same constant in T2(see lines 12–14); note that each set in Ghas 2t1elements, therefore, lines 12–14 require (2t1)4iterations. The second iteration (see lines 18–20) iterates a maximum of (2t1)2 times. Finally, this Algorithm calls Algorithm applyHomomorphism once, which, according to Proposition 11, terminates in O(t1)time.Weget the following expression: O(t1t2+(2t2)2t1((2t1)4+(2t1)2+t1)), which can be simplified as follows: O(t4 1(2t2)t1). Furthermore, if every candidate replacement is transformed into a replacement, we add one replacement in every iteration of the main loop, which generates (2t2)2t1replacements in the worst case.  Proposition 10 (Compute candidate equivalences, see Fig. 8).Let T1 and T2be two knowledge bases. O(t1t2)is an upper bound to the time a call to computeCandidateEquivalences(T1,T2)requires to terminate, where t1and t2denotes the number of triples in T1and T2,respectively. In the worst case, this algorithm outputs a set of equivalences in which the principal set contains 2t1sets, and the internal sets contain 2t2equivalences. Proof. Algorithm computeCandidateEquivalences has to iterate over knowledge base T1. In the worst case, the predicates in the triples of T1are the same as the predicates in the triples of T2, which entails that it is necessary to iterate over the whole knowledge base T2.Asa conclusion, O(t1t2) is an upper bound to the time a call to compute- CandidateEquivalences requires to terminate. In the worst case, for each triple in T1,weaddtwosetstothe final set. Furthermore, in the worst case, every triple in T1has the same predicate as every triple in T2, which adds two equivalences to the internal set. Therefore, the set that Algorithm computeCandidateEquivalences outputs contains 2t1sets, and the internal sets contain 2t2equivalences in the worst case.  Proposition 11 (Applying homomorphisms, see Fig. 9).Let h be a homomorphism, and T a knowledge base. Algorithm applyHomomorphism(h, T)terminates in O(t)time, where t denotes the number of triples in T. Proof. Algorithm applyHomomorphism has to iterate through the whole set of triples T. As a conclusion, Algorithm applyHomomorphism(h, T) terminates in O(t)time.  Proposition 12 (Complete exchange samples, see Fig. 10).Let D be a set of exchange samples. O(d4(2ts)ts(t4 s+tt)) is an upper bound to the time a call to Algorithm completeExchangeSamples(D)requires to terminate, where d denotes the number of exchange samples in D, and ts and ttdenote the maximum number of source and target triples in the exchange samples of D, respectively. Proof. Algorithm completeExchangeSamples iterates over the whole set of input exchange samples (see lines 12–30). Then, in the worst case, in which we have to compare every input exchange sample, it iterates again over the exchange samples except for one (see lines 14–29). The while loop, in the worst case, iterates the same number of times, so the first three loops iterate (d(d−1))2<d4times in the worst case. According to Proposition 9,O(t4 1(2t2)t1)is an upper bound to the time a call to Algorithm computeReplacements requires to terminate, where t1and t2denotes the number of triples in the input knowledge bases. Assume that tsand ttdenote the maximum number of source and target triples in the exchange samples of D; so this call to computeReplacements terminates in O(t4 s(2ts)ts). According to Proposition 9, Algorithm computeReplacements outputs (2t2)2t1replacements in the worst case; therefore, this call generates (2ts)2tsreplacements through which the next loop has to iterate (see lines 18–28). In each iteration, we call Algorithm applyHomomorphism, which terminates in O(tt) time according to Proposition 11. As a conclusion, O(d4(t4 s(2ts)ts+(2ts)2tstt)) =O(d4(2ts)ts(t4 s+tt)) is an upper bound to the time a call to this algorithm requires to terminate.  Proposition 13 (Prune exchange samples, see Fig. 11).Let D be a set of exchange samples. An upper bound to the time a call to pruneExchange- Samples(D)requires to terminate is O(d2(t4 s(2ts)ts+t4 t(2tt)tt)),where d denotes the number of input exchange samples, and tsand ttdenote the maximum number of source and target triples in the exchange samples of D, respectively. Proof. Algorithm pruneExchangeSamples iterates over the whole set of input exchange samples. Then, it iterates again to filter some of them out. In each iteration, in the worst case, we call Algorithm computeReplacements four times, which terminates in O(t4 1(2t2)t1)time in the worst case according to Proposition 9,wheret1and t2de- note the number of triples in the input knowledge bases. Assume that tsand ttdenote the maximum number of source and target triples in the exchange samples of D, therefore, these four calls terminates in O(2t4 s(2ts)ts+2t4 t(2tt)tt). As a conclusion, O(d2(t4 s(2ts)ts+ t4 t(2tt)tt)) is an upper bound to the time a call to this algorithm requires to terminate.  Proposition 14 (Create schema mappings, see Fig. 12).Let D be a set of exchange samples. O(d(ts+tt)) is an upper bound to the time a call to createSchemaMappings(D)requires to terminate, where d denotes the number of input exchange samples, and tsand ttdenote the maximum number of source and target triples in the exchange samples of D, respectively. Proof. Algorithm createSchemaMappings iterates over the whole set of input exchange samples. Then, it iterates over the whole set of source constants, which is, in the worst case, double the maximum number of source triples in the input exchange samples, i.e., every triple comprises two constants. Additionally, it iterates over the whole set of target constants that are not present in the source, which is, in the worst case, double the maximum number of target triples in the input exchange samples, i.e., every triple comprises two constants that are not present in the source. Finally, the source and target substitutions that this algorithm computes are applied to generate the final schema mappings. According to Proposition 11, applying a substitution terminates in O(t) time. As a conclusion, O(d(3ts+3tt)) =O(d(ts+tt)) is an upper bound to the time a call to createSchemaMappings requires to terminate.  References [1] B. Alexe, L. Chiticariu, W.C. Tan, SPIDER: a schema mapping debugger, in: Proceedings of International Conference on Very Large Data Bases, VLDB, 2006, pp. 1179– 1182. [2] B. Alexe, L. Chiticariu, R.J. Miller, W.C. Tan, Muse: mapping understanding and design by example, in: Proceedings of IEEE International Conference on Data Engineering, ICDE, 2008, pp. 10–19. [3] B. Alexe, W.C. Tan, Y. Velegrakis, STBenchmark: towards a benchmark for mapping systems, PVLDB 1 (1) (2008) 230–244. [4] B. Alexe, B.t. Cate, P.G. Kolaitis, W.C. Tan, Designing and refining schema mappings via data examples, in: Proceedings of SIGMOD Conference, 2011, pp. 133–144. [5] B. Alexe, B.t. Cate, P.G. Kolaitis, W.C. Tan, EIRENE: interactive design and refinement of schema mappings via data examples, PVLDB 4 (12) (2011) 1414–1417. [6] B. Alexe, B.t. Cate, P.G. Kolaitis, W.C. Tan, Characterizing schema mappings via data examples, ACM Transactions on Database Systems 36 (4) (2011) 23. [7] F. Alkhateeb, J.-F. Baget, J. Euzenat, Extending SPARQL with regular expression patterns (for querying RDF), Journal of Web Semantics 7 (2) (2009) 57–73. [8] S. Amano, L. Libkin, F. Murlak, XML schema mappings, in: Proceedings of ACM Symposium on Principles of Database Systems, PODS, 2009, pp. 33–42. [9] M. Arenas, L. Libkin, XML data exchange: consistency and query answering, The Journal of the ACM 55 (2) (2008) Article 7. [10] J. Ashraf, E. Chang, O.K. Hussain, F.K. Hussain, Ontology usage analysis in the ontology lifecycle: a state-of-the-art review, Knowledge-Based Syst. 80 (2015) 34– 47. [11] P. Barceló, J. Pérez, J.L. Reutter, Schema mappings and data exchange for graph databases, in: Proceedings of International Conference on Database Theory, ICDT, 2013, pp. 189–200. [12] Z. Bellahsene, A. Bonifati, E. Rahm (Eds.), Schema Matching and Mapping, Springer, 2011. [13] T. Berners-Lee, D. Connolly, Notation3 (N3): a readable RDF syntax, W3C, 2011 Technical report.URL: http://www.w3.org/TeamSubmission/n3/ (accessed 09/2015). [14] B. Bishop, A. Kiryakov, D. Ognyanoff, I. Peikov, Z. Tashev, R. Velkov, OWLIM: a family of scalable semantic repositories, Journal of Web Semantic 2 (1) (2011) 33–42. [15] C. Bizer, A. Schultz, The R2R framework: publishing and discovering mappings on the Web, in: Proceedings of International Workshop on Consuming Linked Data, COLD, 2010. [16] C. Bizer, T. Heath, T. Berners-Lee, Linked data: the story so far, International Journal on Semantic Web and Information Systems 5 (3) (2009) 1–22. [17] C. Bizer, J. Lehmann, G. Kobilarov, S. Auer, C. Becker, R. Cyganiak, S. Hellmann, DBpedia: a crystallization point for the Web of Data, Journal of Web Semantics 7 (3) (2009) 154–165. [18] C.Böhm,M.Freitag,A.Heise,C.Lehmann,A.Mascher,F.Naumann,V.Ercegovac, M.A. Hernández, P. Haase, M. Schmidt, GovWILD: integrating open government data for transparency, in: Proceedings of the 21st International Conference Companion on World Wide Web, WWW, 2012, pp. 321–324. [19] K.D. Bollacker, C. Evans, P. Paritosh, T. Sturge, J. Taylor, Freebase: a collaboratively created graph database for structuring human knowledge, in: Proceedings of SIGMOD Conference, 2008, pp. 1247–1250. [20] J. Broekstra, A. Kampman, F. van Harmelen, Sesame: a generic architecture for storing and querying RDF and RDF Schema, in: Proceedings of International Semantic Web Conference, ISWC, 2002, pp. 54–68. [21] S. Campinas, T. Perry, D. Ceccarelli, R. Delbru, G. Tummarello, Introducing RDF graph summary with application to assisted SPARQL formulation, in: Proceedings of International Conference on Database and Expert Systems, DEXA Workshops, 2012, pp. 261–266. [22] J.J. Carroll, Matching RDF graphs, in: Proceedings of International Semantic Web Conference, ISWC, 2002, pp. 5–15. [23] J.J. Carroll, I. Dickinson, C. Dollin, D. Reynolds, A. Seaborne, K. Wilkinson, Jena: Implementing the Semantic Web recommendations, in: Proceedings of the 21st International Conference Companion on World Wide Web, WWW, 2004, pp. 74– 83. [24] W.G. Cochran, Sampling Techniques, John Wiley & Sons, 1977. [25] DBpedia 3.8. DBpedia downloads, 2012. URL: http://wiki.dbpedia.org/ Downloads38 (accessed 09/2015). [26] M.G. de Carvalho, A.H.F. Laender, M.A. Gonçalves, A.S.d. Silva, An evolutionary approach to complex schema matching, Information Systems 38 (3) (2013) 302– 316. [27] D. Dou, D.V. McDermott, P. Qi, Ontology translation on the semantic web, Journal on Data Semantics 2 (2005) 35–57. [28] R. Fagin, P.G. Kolaitis, R.J. Miller, L. Popa, Data exchange: semantics and query answering, Theoretical Computer Science 336 (1) (2005) 89–124. [29] G. Flouris, D. Manakanatas, H. Kondylakis, D. Plexousakis, G. Antoniou, Ontology change: classification and survey, Knowledge Engineering Review 23 (2) (2008) 117–152. [30] J. Freire, P. Bonnet, D. Shasha, Computational reproducibility: state-of-the-art, challenges, and database research opportunities, in: Proceedings of SIGMOD Conference, 2012, pp. 593–596. [31] B. Glimm, A. Hogan, M. Krötzsch, A. Polleres, OWL: yet to arrive on the Web of Data? in: Proceedings of the Workshop on Linked Data on the Web, LDOW, 2012. [32] M. Golfarelli, F. Mandreoli, W. Penzo, S. Rizzi, E. Turricchia, OLAP query reformulation in peer-to-peer data warehousing, Information Systems 37 (5) (2012) 393– 411. [33] Google, Freebase data dumps. URL http://download.freebase.com/datadumps/ (accessed 02.12.12). [34] GovWILD. GovWILD dumps. URL http://govwild.hpi-web.de/project/ govwild-data.html (accessed 23.03.12). [35] L.M. Haas, M.A. Hernández, H. Ho, L. Popa, M. Roth, Clio grows up: from research prototype to industrial tool, in: Proceedings of SIGMOD Conference, 2005, pp. 805–810. [36] T. Heath, How will we interact with the Web of Data? IEEE Internet Computing 12 (5) (2008) 88–91. [37] T. Heath, C. Bizer, Linked Data: Evolving the Web into a Global Data Space, Morgan & Claypool, 2011. [38] I. Hernández, C.R. Rivero, D. Ruiz, R. Corchuelo, CALA: an unsupervised URL-based web page classification system, Knowledge-Based Systems 57 (2014) 168–180. [39] A. Hogan, J. Umbrich, A. Harth, R. Cyganiak, A. Polleres, S. Decker, An empirical survey of linked data conformance, Journal of Web Semantics 14 (2012) 14–44. [40] J.E. Hopcroft, R.E. Tarjan, Efficient algorithms for graph manipulation [H] (Algorithm 447), Communications of the ACM 16 (6) (1973) 372–378. [41] G. Klyne, J.J. Carroll, Resource description framework (RDF): concepts and abstract syntax, W3C, 2004 Technical report.URL http://www.w3.org/TR/rdf-concepts/ [42] H. Köpcke, E. Rahm, Frameworks for entity matching: a comparison, Data & Knowledge Engineering 69 (2) (2010) 197–210. [43] G. Lausen, M. Meier, M. Schmidt, SPARQLing constraints for RDF, EDBT (2008) 499–509. [44] M. Lenzerini, Data integration: a theoretical perspective, in: Proceedings of ACM Symposium on Principles, 2002, pp. 233–246. [45] A. Maedche, B. Motik, N. Silva, R. Volz, MAFRA: a mapping framework for distributed ontologies, in: Proceedings of Conference on Knowledge Engineering and Knowledge Management, EKAW, 2002, pp. 235–250. [46] A. Mallea, M. Arenas, A. Hogan, A. Polleres, On blank nodes, in: Proceedings of International Semantic Web Conference, ISWC, 2011, pp. 421–437. [47] G. Mecca, P. Papotti, S. Raunich, Core schema mappings, in: Proceedings of SIGMOD Conference, 2009, pp. 655–668. [48] S.L.S. Mergen, C.A. Heuser, Data translation between taxonomies, in: Proceedings of International Conference on Advanced Information Systems Engineering, CAiSE, 2006, pp. 111–124. [49] A. Mocan, E. Cimpian, An ontology-based data mediation framework for semantic environments, International Journal on Semantic Web & Information Systems 3 (2) (2007) 69–98. [50] B. Omelayenko, Integrating vocabularies: discovering and representing vocabulary maps, in: Proceedings of International Semantic Web Conference, ISWC, 2002, pp. 206–220. [51] F.S. Parreiras, S. Staab, S. Schenk, A. Winter, Model driven specification of ontology translations, in: Proceedings of International Conference on Conceptual Modeling – ER, 2008, pp. 484–497. [52] M. Petropoulos, A. Deutsch, Y. Papakonstantinou, Y. Katsis, Exporting and interactively querying web service-accessed sources: the CLIDE system, ACM Transactions on Database Systems 32 (4) (2007) Article 22. [53] X.H. Pham, J.J. Jung, Recommendation system based on multilingual entity matching on linked open data, Journal of Intelligent and Fuzzy Systems 27 (2) (2014) 589–599. [54] L. Popa, Y. Velegrakis, R.J. Miller, M.A. Hernández, R. Fagin, Translating web data, in: Proceedings of International Conference on Very Large Data Bases, VLDB, 2002, pp. 598–609. [55] E. Prud’hommeaux, A. Seaborne, SPARQL query language for RDF, W3C, 2008 Technical report.URL http://www.w3.org/TR/rdf-sparql-query/ [56] L. Qian, M.J. Cafarella, H.V. Jagadish, Sample-driven schema mapping, in: Proceedings of SIGMOD Conference, 2012, pp. 73–84. [57] A. Raffio, D. Braga, S. Ceri, P. Papotti, M.A. Hernández, Clip: a visual language for explicit schema mappings, in: Proceedings of IEEE International Conference on Data Engineering, ICDE, 2008, pp. 30–39. [58] J. Ressler, M. Dean, E. Benson, E. Dorner, C. Morris, Application of ontology translation, in: Proceedings of International Semantic Web Conference, ISWC, 2007, pp. 830–842. [59] C.R. Rivero, A. Schultz, C. Bizer, D. Ruiz, Benchmarking the performance of linked data translation systems, in: Proceedings of Linked Data on the Web Workshop, LDOW, 2012. [60] C.R. Rivero, I. Hernández, D. Ruiz, R. Corchuelo, Research prototype, repositories, scripts, and experimental results. URL: http://tdg-seville.info/carlosrivero/ MostoDEx (accessed 09/2015). [61] C.R. Rivero, I. Hernández, D. Ruiz, R. Corchuelo, MostoDE: a tool to exchange data amongst semantic-web ontologies, Journal of Systems and Software 86 (6) (2013) 1517–1529. [62] C.R. Rivero, I. Hernández, D. Ruiz, R. Corchuelo, Exchanging data amongst linked data applications, Knowledge and Information Systems 37 (3) (2013) 693–729. [63] C.R. Rivero, I. Hernández, D. Ruiz, R. Corchuelo, Benchmarking data exchange among semantic-web ontologies, IEEE Transactions on Knowledge and Data Engineering 25 (9) (2013) 1997–2009. [64] C.R. Rivero, I. Hernández, D. Ruiz, R. Corchuelo, MostoDEx: a tool to exchange RDF data using exchange samples, Journal of Systems and Software 100 (2015) 67–79. [65] B.t. Cate, V. Dalmau, P.G. Kolaitis, Learning schema mappings, in: Proceedings of International Conference on Database Theory, ICDT, 2012, pp. 182–195. [66] J. Völker, M. Niepert, Statistical schema induction, in: Proceedings of European Semantic Web Conference, ESWC, 2011, pp. 124–138. [67] J. Wang, H. Liu, H. Wang, A mapping-based tree similarity algorithm and its application to ontology alignment, Knowledge-Based Systems 56 (2014) 97–107. [68] J. Xu, R. Pottinger, Integrating domain heterogeneous data sources using decomposition aggregation queries, Information Systems 39 (1) (2014) 80–107. [69] N. Zong, S. Nam, J. Eom, J. Ahn, H. Joe, H. Kim, Aligning ontologies with subsumption and equivalence relations in linked data, Knowledge-Based Systems 76 (2015) 30–41.