The data mapping problem: Algorithmic and logical characterizations

Technologies for overcoming heterogeneities be-tween autonomous data sources are key in the emerging networked world. Our doctoral research investigates tech-nologies for alleviating structural heterogeneity between relational data sources. At the heart of structural hetero-geneity is the data mapping problem. The data mapping problem is to discover effective mappings between struc-tured data sources. These mappings are the basic “glue” for facilitating large-scale ad-hoc information shar-ing between autonomous peers in a dynamic environment. Automating their discovery is one of the fundamental un-solved challenges for data interoperability. Our research on solutions to the data mapping problem has two main com-ponents: (1) a general algorithmic approach to automating the discovery of mappings and (2) a general formal ap-proach to understanding the data mapping problem. We outline our progress on each of these fronts and discuss di-rections for future research. 1