Discovering the Semantics of Relational Tablesthrough Mappings?Yuan An1, Alex Borgida2, and John Mylopoulos11Department of Computer Science, University of Toronto, Canada{yuana,jm}@cs.toronto.edu2Department of Computer Science, Rutgers University, [email protected]. Many problems in Information and Data Management require a se-mantic account of a database schema. At its best, such an account consists offormulas expressing the relationship (“mapping”) between the schema and a for-mal conceptual model or ontology (CM) of the domain. In this paper we describethe underlying principles, algorithms, and a prototype tool that finds such se-mantic mappings from relational tables to ontologies, when given as input simplecorrespondences from columns of the tables to datatype properties of classes inan ontology. Although the algorithm presented is necessarily heuristic, we offerformal results showing that the answers returned by the tool are “correct” for re-lational schemas designed according to standard Entity-Relationship techniques.To evaluate its usefulness and effectiveness, we have applied the tool to a numberof public domain schemas and ontologies. Our experience shows that significanteffort is saved when using it to build semantic mappings from relational tables toontologies.Keywords: Semantics, ontologies, mappings, semantic interoperability.1 Introduction and MotivationA number of important database problems have been shown to have improved solutionsby using a conceptual model or an ontology (CM) to provide precise semantics for adatabase schema. These3include federated databases, data warehousing [2], and infor-mation integration through mediated schemas [13, 8]. Since much information on theweb is generated from databases (the “deep web”), the recent call for a Semantic Web,which requires a connection between web content and ontologies, provides additionalmotivation for the problem of associating semantics with database-resident data (e.g.,[10]). In almost all of these cases, semantics of the data is captured by some kind ofsemantic mapping between the database schema and the CM. Although sometimes themapping is just a simple association from terms to terms, in other cases what is requiredis a complex formula, often expressed in logic or a query language [14].For example, in both the Information Manifold data integration system presented in[13] and the DWQ data warehousing system [2], formulas of the form T (X) :- Φ(X, Y )?This is an expanded and refined version of a research paper presented at ODBASE’05 [1]3For a survey, see [23].are used to connect a relational data source to a CM expressed in terms of a Descrip-tion Logic, where T (X) is a single predicate representing a table in the relational datasource, and Φ(X, Y ) is a conjunctive formula over the predicates representing the con-cepts and relationships in the CM. In the literature, such a formalism is called local-as-view (LAV), in contrast to global-as-view (GAV), where atomic ontology concepts andproperties are specified by queries over the database [14].In all previous work it has been assumed that humans specify the mapping formulas– a difficult, time-consuming and error-prone task, especially since the specifier mustbe familiar with both the semantics of the database schema and the contents of the on-tology. As the size and complexity of ontologies increase, it becomes desirable to havesome kind of computer tool to assist people in the task. Note that the problem of seman-tic mapping discovery is superficially similar to that of database schema mapping, how-ever the goal of the later is finding queries/rules for integrating/translating/exchangingthe underlying data. Mapping schemas to ontologies, on the other hand, is aimed at un-derstanding the semantics of a schema expressed in terms of a given semantic model.This requires paying special attentions to various semantic constructs in both schemaand ontology languages.We have proposed in [1] a tool that assists users in discovering mapping formulasbetween relational database schemas and ontologies, and presented the algorithms andthe formal results. In this paper, we provide, in addition to what appears in [1], more de-tailed examples for explaining the algorithms, and we also present proofs to the formalresults. Moreover, we show how to handle GAV formulas that are often useful for manypractical data integration systems. The heuristics that underlie the discovery processare based on a careful study of standard design process relating the constructs of therelational model with those of conceptual modeling languages. In order to improve theeffectiveness of our tool, we assume some user input in addition to the database schemaand the ontology. Specifically, inspired by the Clio project [17], we expect the tooluser to provide simple correspondences between atomic elements used in the databaseschema (e.g., column names of tables) and those in the ontology (e.g., attribute/”datatype property” names of concepts). Given the set of correspondences, the tool is ex-pected to reason about the database schema and the ontology, and to generate a listof candidate formulas for each table in the relational database. Ideally, one of the for-mulas is the correct one — capturing user intention underlying given correspondences.The claim is that, compared to composing logical formulas representing semantic map-pings, it is much easier for users to (i) draw simple correspondences/arrows from col-umn names of tables in the database to datatype properties of classes in the ontology4and then (ii) evaluate proposed formulas returned by the tool. The following exampleillustrates the input/output behavior of the tool proposed.Example 1.1 An ontology contains concepts (classes), attributes of concepts (datatypeproperties of classes), relationships between concepts (associations), and cardinalityconstraints on occurrences of the participating concepts in a relationship. Graphically,we use the UML notations to represent the above information. Figure 1 is an enter-4In fact, there exist already tools used in schema matching which help perform such tasks usinglinguistic, structural, and statistical information (e.g., [4,21]).prise ontology containing some basic concepts and relationships. (Recall that cardinal-ity constraints in UML are written at the opposite end of the association: a Departmenthas at least 4 Employees working for it, and an Employee works