The Data Mapping Problem: Algorithmic and Logical Characterizations

Technologies for overcoming heterogeneities between autonomous data sources are key in the emerging networked world. Our doctoral research investigates technologies for alleviating structural heterogeneity between relational data sources. At the heart of structural heterogeneity is the data mapping problem. The data mapping problem is to discover effective mappings between structured data sources. These mappings are the basic "glue" for facilitating large-scale ad-hoc information sharing between autonomous peers in a dynamic environment. Automating their discovery is one of the fundamental unsolved challenges for data interoperability. Our research on solutions to the data mapping problem has two main components: (1) a general algorithmic approach to automating the discovery of mappings and (2) a general formal approach to understanding the data mapping problem. We outline our progress on each of these fronts and discuss directions for future research.