Abstract

Information integration provides users with a uniform interface to multiple (possibly heterogeneous) data sources. Two main approaches to information integration are data warehousing and mediator-based. The problem of providing explanation for a query answer is referred to as lineage tracing. This problem has been studied extensively in the context of data warehouse systems, however, for mediator-based systems, this is identified as a research problem [HC'03]. In such a system, the mediator does not store data. This means for query processing as well as for tracing, the mediator has to "communicate" with the data sources. While this communication could be expensive, the real issue is that after a query is being processed, lineage tracing could be more difficult or even impossible, if the structure of some contributing sources changes, or if the content of such sources change or a source become unavailable. This means, to support lineage tracing, we need to collect "enough" data and metadata information during query processing. In this work, we study this problem, and introduce data structures and algorithms to support lineage tracing in two modes: batch and interactive. We have successfully developed a prototype, called ELIT , for Exploration and LIneage Tracing . We also study query optimization in the content of ELIT and implemented some basic optimization techniques. While more sophisticated techniques are required in this context, we believe the ideas proposed in this work lend themselves to useful analysis and tracing tools in mediator-based systems.