3rd International ICST Conference on Scalable Information Systems

Research Article

Data Exchange: Query Answering for Incomplete Data Sources

Download667 downloads
  • @INPROCEEDINGS{10.4108/ICST.INFOSCALE2008.3476,
        author={Foto Afrati and Chen Li and Vassia Pavlaki},
        title={Data Exchange: Query Answering for Incomplete Data Sources},
        proceedings={3rd International ICST Conference on Scalable Information Systems},
        publisher={ICST},
        proceedings_a={INFOSCALE},
        year={2010},
        month={5},
        keywords={data exchange incomplete information query answering},
        doi={10.4108/ICST.INFOSCALE2008.3476}
    }
    
  • Foto Afrati
    Chen Li
    Vassia Pavlaki
    Year: 2010
    Data Exchange: Query Answering for Incomplete Data Sources
    INFOSCALE
    ICST
    DOI: 10.4108/ICST.INFOSCALE2008.3476
Foto Afrati1,*, Chen Li2,*, Vassia Pavlaki1,*
  • 1: National Technical University of Athens
  • 2: University of California, Irvine
*Contact email: afrati@softlab.ntua.gr, chenli@ics.uci.edu, vpavlaki@softlab.ntua.gr

Abstract

Data exchange is the problem of transforming data structured under a schema, called the source schema, into data structured under another schema, called the target schema. Existing work on data exchange considers settings where the source instance does not contain incomplete information. In this paper we study semantics and address algorithmic issues for data exchange settings where the source instance may contain incomplete data. We investigate the query answering problem in such data exchange settings. First we give two different meaningful semantics to {em certain answers}: One via the certain answers in the corresponding complete data exchange problems and the other via the set of all solutions of the corresponding complete data exchange problems. We use the chase to compute a universal instance which is materialized over the target schema and is used to compute the certain answers to unions of conjunctive queries. We prove that computing certain answers (under both semantics) for unions of conjunctive queries can be done in polynomial time when the schema mapping contains constraints that consist of a weakly acyclic set of tuple-generating dependencies and equality-generating dependencies.