Ontology Based Data Access (OBDA) enables access to relational data with a complex structure through ontologies as conceptual domain models. A key component of an OBDA system are mappings between the schematic elements in the ontology and their correspondences in the relational schema. Today, in existing OBDA systems these mappings typically need to be compiled by hand, which is a complex and labor intensive task. In this paper we address the problem of creating such mappings and present IncMap, a system that supports a semi-automatic approach for matching relational schemata and ontologies. Our approach is based on a novel matching technique that represents the schematic elements of an ontology and a relational schema in a uni ed way. IncMap is designed to work in a query-driven, pay as you go fashion and leverages partial, user-veri ed mappings to improve subsequent mapping suggestions. This e ectively reduces the overall e ort compared to compiling a mappings in one step. Moreover, IncMap can incorporate knowledge from user queries to enhance suggestion quality.
E ective understanding of complex data is a crucial task for enterprises to
support decision making and retain competitiveness on the market. This task is not
trivial especially since the data volume and complexity keep growing fast in the
light of Big Data [
Today, enterprise information systems of large companies store petabytes of
data distributed across multiple { typically relational { databases, each with
hundreds or sometimes even thousands of tables (e.g., [
Ontology-based data access (OBDA) [
Today, most approaches for ontology-based data access focus on the de nition
of mapping languages and the e cient translation of high-level user queries over
an ontology into executable queries over relational data [
To overcome this limitation we propose a novel semi-automatic schema matching approach and a system called IncMap to support the creation of mappings directly from relational schemata to ontologies.
We focus on nding one-to-one (direct) correspondences of ontological and relational schema elements, while we also work on extensions for nding more complex correspondences. In order to compute mapping suggestions IncMap uses a relational schema, an OWL ontology, a set of user conjunctive queries over the ontology, and user feedback as basic input.
The matching approach of IncMap is inspired by the Similarity Flooding
algorithm of Melnik et al. [
The contributions of the paper are the following: { In Section 3, we propose a novel graph structure called IncGraph to represent schema elements from both ontologies and relational schemata in a uni ed way. Therefore, we devise algorithms to convert an ontology as well as a relational schema into their uni ed IncGraph representation. We also brie y discuss techniques to further improve IncGraph. { In Section 4, we present our matching algorithm that we use for matching IncGraphs. Its most prominent feature is that IncMap can produce the mapping incrementally, query by query. While the original Similarity Flooding algorithm generates correspondences for all schema elements, IncMap supports a pay as you go matching strategy. For each query we produce only required mappings. IncMap leverages the structure of mappings from previous queries to improve suggestion quality. This e ectively reduces the total e ort for the user to verify mapping suggestions. { Section 5 presents an experimental evaluation using di erent (real-world) relational schemata and ontologies. We see that even in the basic version of IncMap, the e ort for creating a mapping is up to 20% less than using the Similarity Flooding algorithm in a naive way. In addition, the incremental version of IncMap can reduce the total e ort by another 50% 70%. 2
In this section we brie y introduce ontologies [
Ontologies. An ontology O speci es a conceptualization of a domain in terms of classes and properties and consists of a set of axioms. Without explanation, ontologies in this paper are OWL ontologies and we will use the following OWL constructs: object and data properties P , and domains Domain(P ) and ranges Range(P ) of properties. We denote with Class(O) and Property(O) the sets of class and property names, respectively, occurring in the ontology O. For a given ontology O, with C 2 Domain(P ) we denote the fact that one can derive from O that the class name C is a domain of the property P . Also, C0 2 Range(P ) denotes the fact that C0 is a range of P and it is derivable from O. Relational Schemata. A relational schema R de nes a set of relations (tables) T , where each table de nes a set of columns c. We also assume that a schema contains foreign keys k that de ne references between tables.
Similarity Flooding Algorithm. The Similarity Flooding algorithm matches a
given schema S with a schema S0. In the rst step, directed labeled graphs
G(S) and G(S0) are constructed from S and S0, where the nodes represent the
schema elements, and the edges with labels de ne relationships between the
schema elements. There is no exact procedure to construct the graphs from
the schemata given in [
Algorithm 1: IncGraph for constructing graphs from ontologies INPUT : OWL ontology O
OUTPUT: Graph G = (V; LblV ; E; LblE ) 1 Let G = (V; LblV ; E; LblE ), V = fn>g, LblV = f(n>; >)g, E = ;, LblE = ;; 2 foreach C 2 Class(O) do V := V [ fnCg and LblE (nC) := C 3 foreach P 2 Property(O) do 4 V := V [ fnP g and LblV (nP ) := P ; Let C 2 Domain(P ); 5 if P is an object property then 6 E := E [ f(nC; nP )g and LblV ((nC; nP )) := `ref'; 7 Let C0 2 Range(P ); 8 E := E [ f(nP ; nC0 )g and LblV ((nP ; nC0 )) := `ref'; 9 else if P is a data property then 10 E := E [ f(nC; nP )g and LblE ((nC; nP )) := `value' 11 return G.
Algorithm 2: IncGraph for constructing graphs from relational schemata INPUT : Relational Schema R
OUTPUT: Graph G = (V; LblV ; E; LblE ) 1 Let V = ;, LblV = ;, E = ;, LblE = ;; 2 foreach table T in R do 3 V := V [ fnT g and LblV (nT ) := T ; 4 foreach column c in R do 5 V := V [ fncg and LblV (nc) := c; 6 E := E [ f(nT ; nc)g and LblE ((nT ; nc)) := `value' 7 if c has a foreign key k to some table T 0 then 8 V := V [ fnkg and LblV (nk) := k; 9 E := E [ f(nT ; nk)g and LblE ((nT ; nk)) := `ref' 10 E := E [ f(nk; nT 0 )g and LblE ((nk; nT 0 )) := `ref' 11 return G. 3
In this section, we describe the IncGraph model used by IncMap to represent schema elements of an OWL ontology O and a relational schema R in a uni ed way.
An IncGraph model is de ned as directed labeled graph G = (V; LblV ; E ; LblE ). It can be used as input by the original Similarity Flooding algorithm (Section 2) or IncMap. V represents a set of vertices, E a set of directed edges, LblV a set of labels for vertices (i.e., one label for each vertex) and LblE a set of labels for edges (i.e., one label for each edge). A label lV 2 LblV represents a name of a schema element whereas a label lE 2 LblE is either \ref" representing a so called ref-edge or \value" representing a so called val-edge.
The goal of the procedures for the basic construction is to incorporate explicit schema information from O and R into the IncGraph model. Incorporating implicit schema information is discussed in the next section.
Algorithm 1 creates an IncGraph model G for a given ontology O. The algorithm constructs a vertex nC for each class name C 2 Class(O) and a vertex !"#$%&!!'() *+,-$./,) 0/1&+2) +,&'-'./(+! 6%&!!) '#7-$.) 8,/9-,.:)
!"#$%&!!'() 0+,-$.!) ,&25-) !"#$%&!!'() 3/4+-) *&.&) 8,/9-,.:) !"#$%&!!'()
;&!<+.%-) 0/1&+2) *+,-$./,) ,-() 0+,-$.!) ,-() 3/4+-)
4&%) ;&!<+.%-) 6,%7#1849+:! !"#$%&'#( 0+,-$./,) 8=) >>>) )'*"$( ?.%-) 0+,-$./,) @=) >>>) *+,-$./,) ,-() 0+,-@=$.)/,) ,-() 3/4+-)
4&%) 4&%) 4&%) *+,8-=$.)/,) ;&!<+.%-) 0+,-$./,)
@=) 6,%.#18490:! 0$-12',1-(3%4$51(0! nP for each property name P 2 Property(O) using the names of these ontology elements as label in LblV . Directed edges in the IncGraph model are created for each domain and range de nition in O. The labels LblE for edges are either \ref" in case of an object property or \value" in case of a data property. For a domain de nition in O the direction of the edge in G is from the node nC representing the domain of P to the node nP representing the property P . For a range de nition the direction of the edge in G is from the node nP representing object property to the node nC0 representing the range of P (i.e., another class). If an object property in O has no range (respectively, domain) de nition, then a directed labeled edge to a node n> is added to explicitly model the most general range (respectively, domain), i.e., a top-level concept > like Thing.
Algorithm 2 creates a IncGraph model G for a given relational schema R: The algorithm constructs a vertex nT for each table and a vertex nc for each column using the names of these schema elements as labels LblV . Directed edges with the label \value" are created from a node nT representing a table to a node nc representing a columns of that table. For columns with a foreign key k an additional node nk is created. Moreover, two directed edges with the label \ref" are added, which represent a path from node nT to a node nT 0 representing the referenced table via node nk.
Figure 1 shows the result of applying these two algorithms to the ontology O and the relational schema R in this gure. Both O and R describe the same entities Directors and Movies using di erent schema elements. The resulting IncGraph models of O and R represent the schema structure in a uni ed way. IncGraph is designed to represent both relational schemata and ontologies in a structurally similar fashion because matching approaches such as ours work best when the graph representations on both the source and target side are as similar as possible. However, even in IncGraph structural di erences remain due to the impedance mismatch and di erent design patterns used in ontologies and relational schemata, respectively.
We consider this issue by supporting annotations in IncGraph. Annotations basically are additional ref-edges in either the source or target model that can be designed to bridge structural gaps for di erent design patterns or levels of granularity. For instance, shortcut edges in the relational IncGraph model could represent a multi-hop join over a chain of relationship relations. Annotations can be constructed by plug-ins during IncGraph construction.
We plan to evaluate the opportunities of di erent kinds of annotations in future work. 4
In this section, we present our matching approach and system called IncMap. IncMap takes a source and target IncGraph as input, i.e., the IncGraphs produced for a relational schema and for an ontology as described in Section 3.
In its basic version, IncMap applies the original Similarity Flooding algorithm (with minor adaptions) and thus creates initial mapping suggestions for the IncGraph of an ontology O and a relational schema R. In its extended version, IncMap activates inactive ref-edges before executing the Similarity Flooding algorithm to achieve better mapping suggestions.
Another extension is the incremental version of IncMap. In this version the initial mapping suggestions are re-ranked by IncMap in a semi-automatic approach by including user feedback. Re-ranking works iteratively in a query-driven fashion thus increasing the quality of the suggested mappings. In each iteration, IncMap applies a version of the Similarity Flooding algorithm (as described before). However, in addition between each iteration user feedback is incorporated.
The idea of user feedback is that the user con rms those mapping suggestions of the previous iteration, which are required to answer a given user query over ontology O. Con rmed suggestions are used as input for the next iteration to produce better suggestions for follow-up queries. This is in contrast to many other existing approaches (including the original Similarity Flooding algorithm) that return a mapping for the complete source and target schema only once.
IncMap is designed as a framework and provides di erent knobs to control which extensions to use and within each extension which concrete variants to choose (e.g., to select a concrete strategy for activating inactive edges). The goal of this section is to present IncMap with all its variants and to show their bene ts for di erent real-world data sets in our experimental evaluation in Section 5. A major avenue of future work is to apply optimization algorithms to nd the best con gurations of IncMap for a given ontology O and schema R automatically by searching the con guration space based on the knobs presented before.
As already mentioned, in the basic version of IncMap, we simply apply the Similarity Flooding algorithm for the two IncGraphs produced for a relational schema R and for an ontology O similar to the process as described in Section 2.
As a rst step, IncMap generates the PCG (i.e., a combined graph which pairs similar nodes of both input IncGraphs) using an initial lexical matching, which supports interchangeable matchers as one knob for con guration. One di erence is the handling of inactive ref-edges in the input IncGraphs. For inactive refedges, which are not handled in the original Similarity Flooding, we apply the following rule when building the PCG: if an edge in the PCG refers to at least one inactive ref-edge in one of the IncGraph models, it also becomes inactive in the PCG.
In addition, other than in the original Similarity Flooding approach, where
propagation coe cients for the IPG are ultimately determined during graph
construction, our propagation coe cients can be calculated several times when the
graph changes with the activation and deactivation of edges. Also, propagation
coe cients in IncMap are modular and can be changed. In particular, a new
weighting formula supported by IncMap considers the similarity scores on both
ends of an edge in the IPG. The intuition behind this is that a higher score
indicates better chances of the match being correct. Thus, an edge between two
matches with relatively high scores is more relevant for the structure than an
edge between one isolated well-scored match and another with a poor score. For
calculating the weight w(e) of a directed edge e = (n1; n2) from n1 to n2 in the
IPG where l is the label of the edge, we currently use two alternatives:
{ Original Weight as in [
Query-driven incremental mappings allow to leverage necessary user feedback after each iteration to improve the quality of mapping suggestions in subsequent iterations. One of the reasons why we have chosen Similarity Flooding as a basis for IncMap is the fact that user feedback can be integrated by adopting the initial match scores in an IPG before the x-point computation starts.
Though the possibility of an incremental approach has been mentioned
already in the Similarity Flooding paper [
First, as a con rmed match corresponds to a certain score of 1:0, while a rejected match corresponds to a score of 0:0, we could simply re-run the x-point computation with adjusted initial scores of con rmed and/or rejected matches. We consequently name this rst method Initializer. However, there is a clear risk that the in uence of such a simple initialization on the resulting mapping is too small as scores tend to change rapidly during the rst steps of the x-point computation.
To tackle this potential problem, our second method guarantees maximum in uence of feedback throughout the x-point computation. Instead of just initializing a con rmed or rejected match with their nal score once, we could repeat the initialization at the end of each step of the x-point computation after normalization. This way, nodes with de nite user feedback in uence their neighborhood with their full score during each step of the computation. We therefore call this method Self-Con dence Nodes. However, as scores generally decrease in most parts of the graph during the x-point computation and high scores become more important for the ranking of matches in later x-point computation steps, this method implies the risk of over-in uencing parts of the graph. For example, one con rmed match in a partially incorrect graph neighborhood would almost certainly move all of its neighbors to the top of their respective suggestion lists.
Finally, with our third method, we attempt to balance the e ects of the previous two methods. We therefore do not change a con rmed match directly but include an additional node in IPG that can indirectly in uence the match score during the x-point computation. We name this method In uence Nodes. By keeping the scores of those additional in uence nodes invariant we ensure permanent in uence throughout all steps of the x-point computation. Yet, the inuence node only indirectly a ects the neighborhood of con rmed nodes through the same propagation mechanism that generally distributes scores through the graph. 5
The main goal of IncMap is to reduce the human e ort for constructing mappings between existing relational database schemata and ontologies. Mapping suggestions are intended to be used only after they have been validated by a user. Thus, there are two relevant evaluation measures: rst, the percentage of the mappings in the reference mappings that can be represented by IncMap. We specify this percentage for all reference mappings when introducing them. Certain complex mappings (e.g., mappings performing data transformations) cannot be represented by IncMap. These complex mappings are rare in all realworld reference mappings we used in this paper. The second and most important measure is the amount of work that a user needs to invest to transform a set of mapping suggestions into the correct (intended) mappings. As the latter is the most crucial aspect, we evaluate our approach by measuring the work time required to transform our suggestions into the existing reference mappings. 5.1
To show the general viability of our approach, we evaluate IncMap in two
scenarios with fairly di erent schematic properties. In addition to showing the key
bene ts of the approach under di erent conditions, this also demonstrates how
the impact of modular parameters varies for di erent scenarios.
IMDB and Movie Ontology. As a rst scenario, we evaluate a mapping from the
schema of well known movie database IMDB4 to the Movie Ontology [
MusicBrainz and Music Ontology. The second scenario is a mapping from the
MusicBrainz database6 to the Music Ontology [
For these reference mappings, two out of 48 correspondences cannot be represented as mapping suggestions by IncMap as they require data transformations. This corresponds to 95:8% of the mappings that could be represented in IncMap.
We evaluate our algorithms w.r.t. reducing work time (human e ort). As the user feedback process always needs to transform mapping suggestions generated by IncMap into the correct mappings (i.e. to achieve a precision and recall of 100%), the involved e ort is the one distinctive quality measure. To this end, we have devised a simple and straightforward work time cost model as follows: we assume that users validate mappings one by one, either accepting or rejecting them. We further assume that each validation, on average, takes a user the same amount of time tvalidate. The costs for nding the correct correspondence for any concept in this case is identical with the rank of the correct mapping suggestion in the ranked list of mapping suggestions for the concept times tvalidate.
As IncMap is interactive by design and would propose the user one mapping suggestion after another, this model closely corresponds to end user reality. We are aware that this process represents a simpli cation of mapping reality where users may compile some of the mappings by other means for various reasons. Nevertheless, this happens in the same way for any suggestion system and therefore does not impact the validity of our model for the purpose of comparison.
Experiment 1 { Naive vs. IncGraph. In our rst experiment we compare the e ort required to correct the mapping suggestions when the schema and ontol5 https://babbage.inf.unibz.it/trac/obdapublic/wiki/Example MovieOntology 6 http://musicbrainz.org/doc/MusicBrainz Database 7 http://euclid-project.eu
IMDB: Naive Similarity Flooding vs. IncGraph
IncGNraaipveh [[iinniittiiaall]]
Naive [final]
IncGraph [final] 1400 1300 1200 1100 1000 ] 900 s ion 800 t [ca 700 ftE 500 fro 600 400 300 200 100 0 800 700 600 ]s500 n o it [ca400 tr o ffE300 200 100 0
Random
IMDB: Incremental Runs
Non-Incremental
Initializer Self-Confidence Nodes
Influence Nodes LS Similarity Inverse LS Dist. Random LS Similarity Inverse LS Dist.
(a) Naive vs. IncGraph 6000 Music Ontology: IncrementaNloRn-uInncsremental
Initializer 5000 Self-CoInnffliudeennccee NNooddeess ogy are represented naively, or as IncGraphs. Additionally, we vary the lexical matcher used for the initial mapping between randomly assigned scores (minimal base line), Levenshtein similarity and inverse Levenshtein distance. Figure 2(a) shows that IncGraph in all cases works better than the naive approach. As IncMap reliably improves the mapping for all con gurations, it also underlines the ability of IncMap to operate in a stable manner with di erent initial matchers. Experiment 2 { Incremental Mapping Generation. Finally, we evaluated the best previous con gurations incrementally, i.e., leveraging partial mappings. Figure 2(b) illustrates the e ects on the total e ort. We show total e ort for all three incremental methods, for di erent propagation coe cients. Most signi cantly, incremental evaluation reduces the overall e ort by up to 50% 70%. More speci cally, Self-Con dence Nodes and In uence nodes work much better than the naive Initializer approach.
Many existing mapping systems rely on two-step mapping procedures: They
employ lexical similarity of terms together with structural similarity of the
structures ([
We presented IncMap, a novel semi-automatic matching approach for generating relational schema-to-ontology mappings. Our approach is based on a novel uni ed graph model called IncGraph for ontologies and relational schemata. IncMap implements a semi-automatic matching approach to derive mappings from IncGraphs using both lexical and structural similarities between ontologies and relational schemata. In order to nd structural similarities IncMap exploits both explicit and implicit schema information. Moreover, IncMap allows to incorporate user queries and user feedback in an incremental way, thus, enabling a pay as you go fashion of the mapping generation. Our experiments with IncMap on di erent real-world relational schemata and ontologies showed that the e ort for creating a mapping with IncMap is up to 20% less than using the Similarity Flooding algorithm in a naive way. The incremental version of IncMap reduces the total e ort of mapping creation by another 50% 70%. As future work we plan to follow three lines: (1) add more implicit schema information (annotations) to the IncGraphs, (2) support more complex mappings in IncMap, and (3) devise a search strategy over the con guration space to auto-tune IncMap. 8
This work was supported by the Seventh Framework Program (FP7) of the European Commission under Grant Agreement 318338, the Optique project.