Skip to Main content Skip to Navigation
Conference papers

Synthesizing transformations from XML schema mappings

Abstract : XML schema mappings have been developed and studied in the context of XML data exchange, where a source document has to be restructured under the target schema according to certain rules. The rules are specified with a mapping, which consists of a set of source-to-target dependencies based on tree patterns. The problem of building a target document for a given source document and a mapping has polynomial data complexity, but is still intractable due to high combined complexity. We consider a two layer architecture for building target instances, inspired by the Church synthesis problem. We view the mapping as a specification of a document transformation, for which an implementation must be found. The static layer inputs a mapping and synthesizes a single XML-to-XML query implementing a valid transformation. The data layer amounts to evaluating this query on a given source document, which can be done by a specialized query engine, optimized to handle large documents. We show that for a given mapping one can synthesize a query expressed in an XQuery-like language, which can be evaluated in time proportional to the evaluation time of the patterns used in the mapping. In general the involved constant is high, but it can be improved under additional assumptions. In terms of overall complexity, if the arity of patterns is considered constant, we obtain a fixed-parameter tractable procedure with respect to the mapping size, which improves previously known upper bounds.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Admin Upem Connect in order to contact the contributor
Submitted on : Monday, August 6, 2018 - 5:36:54 PM
Last modification on : Saturday, January 15, 2022 - 3:57:56 AM
Long-term archiving on: : Wednesday, November 7, 2018 - 3:48:06 PM


Publisher files allowed on an open archive


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License




Claire David, Piotr Hofman, Filip Murlak, Michal Pilipczuk. Synthesizing transformations from XML schema mappings. 17th International Conference on Database Theory (ICDT 2014), Mar 2014, Athènes, Greece. pp.61-71, ⟨10.5441/002/icdt.2014.10⟩. ⟨hal-01854501⟩



Record views


Files downloads