Data migration: A theoretical perspective

In this paper we investigate data migration fundamentals from a theoretical perspective. Following the framework of abstract interpretation, we first discuss models and schemata at different levels of abstraction to establish a Galois connection between abstract and concrete models. A legacy kernel is discovered at a high-level abstraction which consolidates heterogeneous data sources in a legacy system. We then show that migration transformations can be specified via the composition of two subclasses of transformations: property-preserving transformations and property-enhancing transformations. By defining the notions of refinement correctness for property-preserving and property-enhancing transformations, we develop a formal framework for refining transformations occurring in the process of data migration. In order to improve efficiency of static analysis, we further introduce an approach of verifying transformations by approximating abstraction relative to properties of interest, meanwhile preserving the refinement correctness as accurately as possible. The results of this paper lay down a theoretical foundation for developing data migration tools and techniques.