XML data exchange: Consistency and query answering

Marcelo Arenas, Leonid Libkin

Research output: Contribution to journalArticlepeer-review


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 article, 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 source-to-target dependencies refer to the hierarchical structure of the data. Combining DTDs and dependencies makes 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 coNP-complete, depending on classes of regular expressions used in DTDs. Furthermore, for all tractable cases we give polynomial-time algorithms that compute target XML documents over which queries can be answered.
Original languageEnglish
Article number7
Pages (from-to)1-72
Number of pages72
JournalJournal of the ACM
Issue number2
Publication statusPublished - 1 May 2008


  • Data exchange
  • XML
  • computing certain answers
  • consistency


Dive into the research topics of 'XML data exchange: Consistency and query answering'. Together they form a unique fingerprint.

Cite this