Propagating Dependencies under Schema Mappings: A Graph-based Approach

Abstract

Schema mapping plays an important role in many database-related transformation tasks, such as data exchange, data integration and data migration. In this paper, we study the dependency propagation problem in the context of schema mappings. This allows us to understand and discover logical consequences among source constraints, target constraints and mapping constraints of a schema mapping. In order to precisely characterize the relationships between source and target schemas, we consider mapping constraints as being bipartite TGDs, i.e., a class of tuple-generating dependencies (TGDs) that include both source-to-target dependencies and target-to-source dependencies. We then develop propagation graphs to represent the relationships among the attributes of different relations and, based on such propagation graphs, we propose algorithms to propagate inclusion and functional dependencies between source and target schemas. We have also designed a schema mapping reasoning tool to implement and evaluate our proposed approach