XML data exchange: Consistency and query answering

Arenas, M; Libkin, L

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 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. © 2008 ACM.

Más información

Título según WOS: XML data exchange: Consistency and query answering
Título según SCOPUS: XML data exchange: Consistency and query answering
Título de la Revista: JOURNAL OF THE ACM
Volumen: 55
Número: 2
Editorial: ASSOC COMPUTING MACHINERY
Fecha de publicación: 2008
Idioma: English
URL: http://portal.acm.org/citation.cfm?doid=1346330.1346332
DOI:

10.1145/1346330.1346332

Notas: ISI, SCOPUS