Core schema mappings: Scalable core computations in data exchange

Research has investigated mappings among data sources under two perspectives. On the one side, there are studies of practical tools for schema mapping generation; these focus on algorithms to generate mappings based on visual specifications provided by users. On the other side, we have theoretical researches about data exchange. These study how to generate a solution – i.e., a target instance – given a set of mappings usually specified as tuple generating dependencies. Since the notion of a core solution has been formally identified as an optimal solution, it is very important to efficiently support core computations in mapping systems. In this paper, we introduce several new algorithms that contribute to bridge the gap between the practice of mapping generation and the theory of data exchange. We show how, given a mapping scenario, it is possible to generate an executable script that computes core solutions for the corresponding data exchange problem. The algorithms have been implemented and tested using common runtime engines to show that they guarantee very good performances, orders of magnitudes better than those of known algorithms that compute the core as a post-processing step.

► We introduce a rewriting algorithm for data exchange scenarios made of s-t tgds.
► The algorithm allows a mapping system to generate optimal solutions in a scalable fashion.
► A prototype has been developed. Our experiments confirm the scalability of our technique.
► The rewriting algorithm is based on a new characterization of the core.
► The rewriting algorithm has been used as a building block for more complex forms of rewriting.