Tractable XML data exchange via relations

Rada Chirkova, Leonid Libkin, Juan Reutter

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider data exchange for XML documents: given source and target schemas, a mapping between them, and a document conforming to the source schema, construct a target document and answer target queries in a way that is consistent with source information. The problem has primarily been studied in the relational context, in which data-exchange systems have also been built. Since many XML documents are stored in relations, it is natural to consider using a relational system for XML data exchange. However, there is a complexity mismatch between query answering in relational and XML data exchange, which indicates that restrictions have to be imposed on XML schemas and mappings, and on XML shredding schemes, to make the use of relational systems possible. We isolate a set of five requirements that must be fulfilled in order to have a faithful representation of the XML data-exchange problem by a relational translation. We then demonstrate that these requirements naturally suggest the inlining technique for dataexchange tasks. Our key contribution is to provide shredding algorithms for schemas, documents, mappings and queries, and demonstrate that they enable us to correctly perform XML data-exchange tasks using a relational system.
Original languageEnglish
Title of host publicationProceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011
Number of pages10
ISBN (Print)978-1-4503-0717-8
Publication statusPublished - 2011


Dive into the research topics of 'Tractable XML data exchange via relations'. Together they form a unique fingerprint.

Cite this