Composing Mappings Among Data Sources Jayant Madhavan and Alon Y. Halevy   View Paper (PDF)   Return to Managing derived Data (Session B6) Abstract Semantic mappings between data sources play a key role in several data sharing architectures. Mappings provide the relationships between data stored in dif- ferent sources, and therefore enable answering queries that require data from other nodes in a data shar- ing 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 fre- quently traversed paths and redundancy analysis. This paper investigates the theoretical underpin- nings 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 rst show that even when composing two simple GLAV mappings, the full composition may be an in nite 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 in finite set of GLAV for- mulas using a finite representation. Furthermore, we describe an algorithm that given a query and a nite encoding of an in nite 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 poten- tially offering significant savings in query processing. ©2004 Association for Computing Machinery