- Speaker(s)
- Filip Murlak
- Affiliation
- Uniwersytet Warszawski
- Date
- Oct. 27, 2010, 2:15 p.m.
- Room
-
room 5870
- Seminar
- Seminar Automata Theory
The task of XML data exchange is to restructure a document conforming to a source schema under a target schema according to certain mapping rules. The rules are typically expressed as source-to-target dependencies using various kinds of patterns, involving horizontal and vertical navigation, as well as data comparisons. The target schema imposes complex conditions on the structure of solutions, possibly inconsistent with the mapping rules. In consequence, for some source documents there may be no solutions. I will discuss three computational problems: deciding if all documents of the source schema can be mapped to a document of the target schema (absolute consistency), deciding if a given document of the source schema can be mapped (solution existence), and constructing a solution for a given source document (solution building). It turns out that the complexity of absolute consistency is rather high in general, but within the polynomial hierarchy for bounded depth schemas. The combined complexity of solution existence and solution building behaves similarly, but the data complexity is very low. In fact, even for very expressive mapping rules, based on MSO definable queries, absolute consistency is decidable and data complexity of solution existence is polynomial. This is joint work with Mikolaj Bojanczyk and Leszek Kolodziejczyk.
You are not logged in |
