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 metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-01854501
Contributor : Admin Upem <>
Submitted on : Monday, August 6, 2018 - 5:36:54 PM
Last modification on : Friday, August 17, 2018 - 4:56:19 PM
Long-term archiving on : Wednesday, November 7, 2018 - 3:48:06 PM

File

ICDT2014-paper_55.pdf
Publisher files allowed on an open archive

Licence


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

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

192

Files downloads

16