XML Data Exchange: Consistency and Query Answering Marcelo Arenas and Leonid Libkin   View Paper (PDF)   Return to Research Session 1: Querying XML and Semistructured Data / Query Languages Abstract Data exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target. Theoretical foundations of data exchange have recently been investigated for relational data. In this paper, we start looking into the basic properties of XML data exchange, that is, restructuring of XML documents that conform to a source DTD under a target DTD, and answering queries written over the target schema. We define XML data exchange settings in which sourcetotarget dependencies refer to the hierarchical structure of the data. CombiningDTDs and dependenciesmakes some XML data exchange settings inconsistent. We investigate the consistency problem and determine its exact complexity. We then move to query answering, and prove a dichotomy theorem that classifies data exchange settings into those over which query answering is tractable, and those over which it is coNPcomplete, depending on classes of regular expressions used in DTDs. Furthermore, for all tractable cases we give polynomialtime algorithms that compute target XML documents over which queries can be answered. ©2006 Association for Computing Machinery