Synthesizing transformations from XML schema mappings

Claire David (1) , Piotr Hofman (2) , Filip Murlak (2) , Michal Pilipczuk (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 UW - University of Warsaw
3 UiB - University of Bergen

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.

Mots clés: data exchange; building solutions; document transformations; queries returning trees

Domaines: Algorithme et structure de données [cs.DS]; Complexité [cs.CC]

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⟩