joint work with Claire David and Michał Pilipczuk

Speaker(s)

Piotr Hofman and Filip Murlak

Affiliation

Uniwersytet Warszawski

Date

Feb. 20, 2013, 2:15 p.m.

Room

room 5870

Title in Polish

Synthesizing transformations from XML schema mappings

Seminar

Seminar Automata Theory

---

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 set of source-to-target dependencies based on tree patterns. This set of dependencies is called a schema mapping.

The crucial problem here is to build a target document for a given source document and a mapping. This problem is known to have polynomial complexity for a fixed mapping, but is still intractable due to high combined complexity (i.e., when the mapping is part of the input).

We show how to solve this problem in time proportional to the evaluation time of the patterns involved in the mapping. If the number of variables in these patterns is considered fixed, we obtain a fixed-parameter tractable procedure with respect to the mapping size.

As an additional step towards real-life applications, our algorithm separates the static and data-dependent phases of the construction. First, without looking at the source tree, we turn the mapping into a transformation expressed in an XML-to-XML query language. Then, the transformation can be executed on the source tree by any standard query engine.

---