Debugging schema mappings with routes

A schema mapping is a high-level declarative specification of the relationship between two schemas; it specifies how data structured under one schema, called the source schema, is to be converted into data structured under a possibly different schema, called the target schema. Schema mappings are fundamental components for both data exchange and data integration. To date, a language for specifying (or programming) schema mappings exists. However, developmental support for programming schema mappings is still lacking. In particular, a tool for debugging schema mappings has not yet been developed. In this paper, we propose to build a debugger for understanding and exploring schema mappings. We present a primary feature of our debugger, called routes, that describes the relationship between source and target data with the schema mapping. We present two algorithms for computing all routes or one route for selected target data. Both algorithms execute in polynomial time in the size of the input. In computing all routes, our algorithm produces a concise representation that factors common steps in the routes. Furthermore, every minimal route for the selected data can, essentially, be found in this representation. Our second algorithm is able to produce one route fast, if there is one, and alternative routes as needed. We demonstrate the feasibility of our route algorithms through a set of experimental results on both synthetic and real datasets.