An important problem in modern information systems and e-commerce
applications is inter-operability between independent data sources
(relational, XML, etc.). This often requires the ability to translate
between various formats (or schemas). To shield users from writing
complex queries or programs for every translation problem at hand, we
advocate the use of high-level schema mapping tools in which value
correspondences are used to map individual attributes of the source
schema to individual attributes of the target schema.

We present a novel framework for mapping between XML or relational
schemas in which value correspondences are translated into
semantically meaningful queries that transform data conforming to the
source schema into data conforming to the target schema. Our approach
works in two phases. The first one is the semantic translation phase
in which value correspondences are expressed as inter-schema
dependencies. This translation uses the chase with schema constraints
in order to discover conceptual associations that exist in each of the
two schemas. Associations are groups of attributes, not necessarily in
the same table or set of a nested schema, that conceptually describe
the same real-world entity. Inter-schema dependencies specify then the
mapping at an association level rather than attribute level.

The second phase translates inter-schema dependencies into
queries that perform the required join, unnest and nest
operations, in order to retrieve source associations and materialize
corresponding target associations. One novelty of our query generation
algorithm is the way in which Skolem functions are used to create
non-null values (ids) for target attributes that are not determined by
value correspondences but are essential for preserving the consistency of
the target data. An added feature of our
approach is that any referential integrity constraints in the target
schema are automatically satisfied when one runs the generated
queries.

The framework is based on a nested relational model able to express
relations, the core of XML Schema, and their referential integrity
constraints. We have implemented the framework in CLIO, a
semi-automatic tool for schema mapping. CLIO demonstrates how our
approach can be used to easily map from and into complex XML or
relational schemas, without loss of information.