Synthesizing transformations from XML schema mappings

Prelegent(ci)

Piotr Hofman and Filip Murlak

Afiliacja

Uniwersytet Warszawski

Termin

20 lutego 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Claire David and Michał Pilipczuk

Seminarium

Seminarium „Teoria automatów”

---

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.

---