Milan automatically generates R2RML mappings between a source relational database and a target ontology, using novel multi-level algorithms. It address real world inter-model semantic gap by resolving naming con icts, structural and semantic heterogeneity, thus enabling high delity mapping generation for realistic databases. Despite the importance of mappings for interoperability across relational databases and ontologies, a labour and expertise-intensive task, the current state of the art has achieved only limited automation. The paper describes an experimental evaluation of Milan with respect to the state of the art systems using the RODI benchmarking tool which shows that Milan outperforms all systems in all categories.
The Semantic Web promises easy data integration but in practice, this depends
on the availability of detailed mappings, especially when converting from other
data models like the relational model to RDFs data model [
The research question studied in this paper is To what extent can an automatic RDB to RDF mapping generation technique, Milan, based on semantic, lexical and structural analysis of both a source relational database and a target ontology create complete and accurate R2RML mappings?
Milan creates correspondences based on heuristic RDB to RDF mapping patterns we have observed in real databases. It uses a multi-level algorithm to detect class-table, object property-referential integrity and data property-column correspondences for realistic, complex relational databases. In order to minimise human intervention, these correspondences use Levenstein distance-based fuzzy label matching and identify optimal matches using combinatorial optimization. R2RML mappings are then generated to express these correspondences.
The contributions of this paper are as follows: (1) Milan, a novel method for
detection of correspondences between relational databases and semantic web
ontologies or vocabularies; and (2) an evaluation of the performance Milan against
the Relational-to-Ontology Data Integration (RODI) benchmark [
This section brie y discusses di erent state of the art systems. Pinkel et al [
BootOx [
IncMap [
Automap4OBDA (A4MO) [
The following lists the gaps in the current state of the art systems. They all fail to detect n : m due to junction table and n : 1 class-table relationships due to column splitting. They also miss out on many properties matching for tables that have 1 : 1 relationship with other tables. They don't utilize annotation properties, resolve datatype property-column label collisions. They also underperform at addressing semantic heterogeneity. They don't use the expressivity of OWL such as InverseOf, unionOf to enrich the relational-ontology relationship. 3
As mentioned above, most real-world relational schema and corresponding ontologies cannot be related using nave direct mappings as there are vast di erences in the ways which same concepts are modelled. This section references examples of di erent data modelling techniques discussed in state of the art. Based on such observations, literature also provides a comprehensive set of requirements for automatic mapping systems. These are brie y discussed below.
C.Pinkel et al[
Challenge Type
Input-Output
Relational-to-ontology systems requirement
Milan has been developed to ll the gaps identi ed by the requirements and in the state of the art mapping generation systems. Milan comprises of three main processes and 6 supporting processes that are invoked by the main processes as needed (Fig. 2). The source relational database and target ontology act as inputs to Milan and it produces a set of R2RML mappings as an output.
Label Matching : Milan uses a variant of FuzzyWuzzy5, uses Levenshtein Distance, producing scores in the range [0; 1]. Milan modi ed FuzzyWuzzy to add camelCase and special character based tokenization. Label matching addresses the naming heterogeneity patterns involving token re-ordering using sort token ratio which reorders the tokens based on lengths. Label matching uses
a speci c variant for Column Splitting (Sec. 4.1), where it lters out the
superclass label token from its subclass or sibling label, thereby improving matching
scores. Combinatorial Optimization: Milan uses the Hungarian algorithm [
The Class-Table Relationship process detects 1 : 1, n : 1, and some 1 : n classtable relationships using Label Matching, Column Splitting and Combinatorial Optimization. Column Splitting detects categorical values in columns, thereby splitting the table based on these values. These values are matched to sub-classes and sibling classes.
The class-table matching result is input to the Object Property Foreign Key/Primary Key process to discover links using Referential Integrity, Label Matching, Junction Table Detection and Combinatorial Optimization. Referential Integrity discovers the keys linking two pairs of matching class-tables and the object properties across the two classes. Junction Table Detection enriches existing relationships with the inclusion of implicit many-to-many relations across two or more tables.
The algorithm rst detects 1:1 followed n : 1 class-table relationships. Algorithm 1 takes class and table rdfs:label as input. Label matching is used over the two lists producing a three column matching table Oa b;3. Oa b;3 is then post-processed by ltering out results with low string match scores based on a threshold, which is determined experimentally ( = 0:7). This is followed by ltering out lower match scores due to duplicate occurrences of any class or table label, represented as uniqueCriteria in Algorithm 1.
The result of this is a one-one match table. Each 1:1 class-table pair is considered for column splitting by considering unique elements of all non-key columns. This is done by gathering all non-key columns (Wm;1) along with sub-classes and sibling classes(Vn;1) for the given table-class pair. Then, for each column, the unique element values and their columns are stored in a two column table (Ta;2). In order to maximize computation e ciency and matching accuracy, columns having a very large number of unique elements are removed from consideration. This is done using a threshold which is experimentally determined to be = 1:2 n. A modi ed variant of Label Matching is then run over this list of unique values with sub-classes and siblings of a target class against all labels of unique column values, using score threshold . Data diversity is enhanced by the overlooking label of target class when considering the sub/sibling class labels.
Using the Hungarian algorithm over the resultant label match table provides 1:1 column value-class matches, which are optimized by maximizing the sum of scores. 4.2
Algorithm 2 uses rdfs:domain, rdfs:range, owl:UnionOf and owl:inverseOf of object property 0, Alg. 2,3 along with FK/PK relationship R using primaryforeign key pairs represented by foreign column names R ( Alg. 2,2). Using the class-table pair from Sec. 4.1, it obtains the corresponding two pairs of classes and tables. Algorithm 2 matches the obtained list of object properties with keys of the relational database using label matching. However, a nave approach will miss out on detecting complex relationships 3 such as junction tables, one-to-one table relations, and inverse relationships.
Alg.2 detects junction tables via pattern mentioned patterns 3 and infers a many-to-many relationship across the table pair. The label used to describe this relationship is the junction table's name. Alg.2 also detects 1:1 table-table mappings and inherits all columns of parent table to the child tables. Lastly, while relationships in relational databases have a clear sense of directionality, relationship across the class may not always be uni-directional. Sometimes they also have a pair of properties which are inverse of each other. This is represented using rdfs:InverseOf predicate. Milan overcomes this impedance mismatch by dropping directionality (Alg.2,6) and prioritizing direction (Alg.2,10) in the presence of alternates.
Table 2 lists the challenges that Alg.2 resolves by reasoning over rdfs:InverseOf. Consider case(a) of Table 2, both object property present (OP) and FK/PK relation (Col) are present for relation C1=T1 ! C2=T2 (1). However in relation (2), the rdfs:InverseOf(A), X is present, but FK/RK relation is not present. Hence a has to be inferred, which will be matched to X. In case(b)2, single object property and FK/PK relations are present in opposite direction. The FK/PK relation is therefore inferred to match the object property. Case (c)2 is a speci c case of junction table relationships, where more than one relation exists across two tables. It could occur that both the object property A & B have inverses. And corresponding FK/PK relations are divided across di erent directions. Inferences are made to include missing FK/PK relations for each relation. The nal matching is performed by label matching and then performing Hungarian algorithm with labelM atch(P roperty; F K=P Ka) labelM atch(inv : P roperty; F K=P Kb) an additional constraint for every property and its inverse pair. This is to prevent a property and its inverse, both to occur as a result of the Hungarian algorithm. 4.3
The Datatype of data property is retrieved by querying its rdfs:label, rdfs:range and if present its owl:UnionOf. Milan performs label matching across all data properties and nonkey columns for each class-table pair. In addition to this, Milan addresses label collisions by segregating datatypes based on W3C datatype mapping6. The rationale behind this segregation is likes match. i.e a column having varchar datatype cannot possibly match to a datatype property having xsd:date as its range. Hence o ering greater accuracy in cases of string ambiguity. For a given pair of class-table, each segregation of a datatype group e.g V archar xsd : string, Milan uses Hungarian algorithm to obtain a 1:1 match based on label matching scores. It is important to note that this algorithm is also capable of detecting 1 : n relationship for a property-column pair.This is done in three ways. One, when multiple properties related to each other by ow:sameAs. Second, owl:UnionOf contains multiple classes for a given datatype property, hence mapping the same property to multiple tables. Lastly, when detecting 1:1 table-table relationships in 4.2, child tables inherit all columns of the main table, allowing possible matches to data property. 6 www.w3.org/TR/r2rml/
Many papers such as [
The purpose of the evaluation is to test the quality of mappings generated by
Milan in realistic deployment scenarios. Several papers such as Tarasowa et al
[
The RODI suite 7 includes a wide range of relational-to-ontology scenarios, each based on mapping challenges similar to Sec. 3. Each scenario provides an input database and a target ontology. It requests from systems a complete set of mappings that enable to execute queries over the target ontology (T-Box). Each scenario contains a list of SPARQL-SQL query pairs, which are categorized under various mapping challenges such as class-table, attributes, links. These query pairs are executed to evaluate if the results from the SQL queries match the SPARQL queries to the ontology constructed using the mappings provided. It then calculates the averages of precision and recall of all queries in each scenario, thereby calculating a tness function for mapping quality. In addition to total scores, RODI also provides aggregated scores for each category of the query pairs.
This paper evaluates Milan based on 4 scenarios provided by RODI. The
RODI authors have already performed ontology alignment of output ontologies
with the target ontology for systems like MIRROR and -ontop-, which dont
produce mappings. They have also provided mapping translation for systems
like D2QRQ and COMA++, by translating system speci c mapping language
to R2RML. The hypothesis is that Milan's approach performs better than the
current state of the art in terms of the mapping quality metric used by RODI.
Benchmark Datasets This section describes the four scenarios used to
evaluate Milan. These scenarios are based on real open data such as Conference,
Norwegian Petroleum Directorate [
Each scenario has varied di culty levels. For instance, the relational schemata of cmt renamed closely follows modeling patterns from their corresponding ontologies. cmt structured additionally introduces 1 : n class hierarchy mapping challenge (R3a,4). conference nofk is void of primary key-foreign key relations making it tough to detect object property mappings (R3b). npd atomic, which is based on the NPD dataset is the most challenging scenario of all. 1 : n matches
(R3a,4), for both classes and properties are present. 1:n matches as a structural
feature can therefore best be tested in the npd atomic tests scenario [
B.OX IncM. Ontop MIRR. COMA D2RQ A4MO Milan cmt renamed 0.76 cmt structured 0.41 conference nofk 0.33 npd atomic 0.14 breakdown of the agregated score for cmt renamed, where Milan performs better across queries under class, data property and object property.
Milan correctly detected 75/134 class-table, 42/213 data properties-column and 15/92 object property-FK/PK matches in the npd atomic.
The impact of Algorithm 1 is evident in the npd atomic dataset. It correctly detects 56% of the total class-table mappings. The outcome of this algorithm also detected 12 out of 45 of the 1 : n class-table match is present. Although cmt structured had many patterns re ecting column splitting, Algorithm 1 was not so successful here. Additionally, there are cases of column splits which detected categorical values such "1" and "2", which were either foreign or non-key column. These were true matches to separate classes but label matching failed to match these cases.
The relatively high scores achieved in the object property-referential integrity relationship are credited to junction table detection, 1:1 relationship matching followed by property inheritance and inverse property inferencing. It also detected 1:1 table-table relationships, which comprises of 34% of the primaryforeign key relations. This increased object property mappings, caused due to inheritance. However Milan couldn't capture object property mappings when object properties don't have explicit rdfs:range/domain or owl:unionOf.
Better results with detecting data property are credited to the use of datatype partitioning and the Hungarian algorithm with Label Matching for the classtable pair. In addition to this, the algorithm uses annotation properties such as rdfs:label and rdfs:comment to match to the column. Additionally, the performance is enhanced by the inheritance of properties due to 1:1 table-table detection. However, the strategy of datatype partitioning had its compromises. The tables of conference nofk scenario has columns which have boolean datatype while the matching data property is a string. Milan is unable to match these cases, thereby missing on some of the data properties. 6
Milan has been demonstrated to automatically generate R2RML mappings between a relational database and target ontology with an overall f-measure of between 0.86 and 0.3 under the RODI benchmark conditions. This measure is an indicator of the accuracy and completeness of the mappings generated. Milan has out-performed all the other automatic mapping generation systems that have been tested to date with RODI. The relative performance of Milan improves in more complex scenarios like npd atomic, where it performed 30.4% better than the next best system,A4MO. Similarly, the performance pf Milan was 26.8% better than the next leading system, IncMap, in the cmt structured scenario. This demonstrates the relative e ectiveness of a direct mapping generation approach, as implemented by Milan, compared to the more popular putative ontology-based mapping generation methods.
Further work is required to broaden our con dence in this work by evaluating Milan over additional datasets. In addition this evaluation has helped us to identify the following potential RDB-RDF mapping patterns or improvements to Milan: Detecting class-table mappings where multiple tables form one class in the target ontology; extending the column-based table splitting pattern to account account for foreign key columns ; and inferring implicit links between tables based on undeclared foreign keys whose use is observed in the database. Acknowledgments. This research has received funding from the ADAPT Centre for Digital Content Technology, funded under the SFI Research Centres Programme (Grant 13/RC/2106) and co-funded by the European Regional Development Fund.