Schema Evolution publication categorizer

Semantic mappings between data sources play a key
role in several data sharing architectures. Mappings
provide the relationships between data stored in different sources, and therefore enable answering queries
that require data from other nodes in a data sharing network. Composing mappings is one of the core
problems that lies at the heart of several optimization
methods in data sharing networks, such as caching frequently traversed paths and redundancy analysis.
This paper investigates the theoretical underpinnings of mapping composition. We study the problem
for a rich mapping language, GLAV, that combines the
advantages of the known mapping formalisms global-as-view and local-as-view. We first show that even
when composing two simple GLAV mappings, the full
composition may be an infinite set of GLAV formulas.
Second, we show that if we restrict the set of queries
to be in CQk (a common restriction in practice), then
we can always encode the infinite set of GLAV formulas using a finite representation. Furthermore, we
describe an algorithm that given a query and a finite
encoding of an infinite set of GLAV formulas, finds all
the certain answers to the query. Consequently, we
show that for a commonly occuring class of queries it
is possible to pre-compose mappings, thereby potentially offering significant savings in query processing.