Inverting schema mappings

TLDR

Schema mappings describe how data under one schema is transformed into another, but defining an inverse is difficult because mappings can be many‑to‑many. The authors formally define an inverse mapping M′ for a class S of source instances by requiring that the composition of M and M′ be the identity. They develop a theory for source‑to‑target tuple‑generating dependencies, showing how to construct an S‑inverse when the chase is finite, and how to identify the largest class S for which a given M′ is an inverse. When S is the class of all source instances, the theory yields a global inverse, and the authors provide a constructive method for obtaining it whenever it exists.

Abstract

A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). Although the notion of an inverse of a schema mapping is important, the exact definition of an inverse mapping is somewhat elusive. This is because a schema mapping may associate many target instances with each source instance, and many source instances with each target instance. Based on the notion that the composition of a mapping and its inverse is the identity, we give a formal definition for what it means for a schema mapping M′ to be an inverse of a schema mapping M for a class S of source instances. We call such an inverse an S- inverse . A particular case of interest arises when S is the class of all source instances, in which case an S-inverse is a global inverse. We focus on the important and practical case of schema mappings specified by source-to-target tuple-generating dependencies, and uncover a rich theory. When S is specified by a set of dependencies with a finite chase, we show how to construct an S-inverse when one exists. In particular, we show how to construct a global inverse when one exists. Given M and M′, we show how to define the largest class S such that M′ is an S-inverse of M.