Paper Info
Title
Designing and refining schema mappings via data examples
Abstract
A schema mapping is a specification of the relationship between a source schema and a target schema. Schema mappings are fundamental building blocks in data integration and data exchange and, as such, obtaining the right schema mapping constitutes a major step towards the integration or exchange of data. Up to now, schema mappings have typically been specified manually or have been derived using mapping-design systems that automatically generate a schema mapping from a visual specification of the relationship between two schemas. We present a novel paradigm and develop a system for the interactive design of schema mappings via data examples. Each data example represents a partial specification of the semantics of the desired schema mapping. At the core of our system lies a sound and complete algorithm that, given a finite set of data examples, decides whether or not there exists a GLAV schema mapping (i.e., a schema mapping specified by Global-and-Local-As-View constraints) that "fits" these data examples. If such a fitting GLAV schema mapping exists, then our system constructs the "most general" one. We give a rigorous computational complexity analysis of the underlying decision problem concerning the existence of a fitting GLAV schema mapping, given a set of data examples. Specifically, we prove that this problem is complete for the second level of the polynomial hierarchy, hence, in a precise sense, harder than NP-complete. This worst-case complexity analysis notwithstanding, we conduct an experimental evaluation of our prototype implementation that demonstrates the feasibility of interactively designing schema mappings using data examples. In particular, our experiments show that our system achieves very good performance in real-life scenarios.
Year
DOI
Venue
2011
10.1145/1989323.1989338
SIGMOD Conference
Keywords
Field
DocType
fitting glav schema mapping,target schema,glav schema mapping,source schema,right schema mapping,data integration,refining schema mapping,data example,schema mapping,mapping-design system,data exchange,decision problem,computational complexity,data integrity,interaction design
Data mining,Conceptual schema,Star schema,Schema migration,Semi-structured model,Computer science,Document Structure Description,Database schema,Theoretical computer science,Information schema,Database,Schema (genetic algorithms)
Conference
Citations 
PageRank 
References 
39
1.39
19
Authors
4
Name
Order
Citations
PageRank
Bogdan Alexe1170678.66
Balder Ten Cate263051.21
Phokion G. Kolaitis32733514.37
WC Tan42529198.85