Solutions in XML data exchange
Solutions in XML data exchange
复制标题
XML数据交换解决方案
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Filip Murlak
中科院分区：
文献类型：
--
作者：
Mikolaj Bojanczyk;L. Kolodziejczyk;Filip Murlak
XML数据交换的任务是将符合源模式的文档按照一定的映射规则重新构造到目标模式下。这些规则通常使用各种模式表示为源到目标的依赖关系，包括水平和垂直导航以及数据比较。目标模式对解决方案的结构施加了复杂的条件，可能与映射规则不一致。因此，对于某些源文件，可能没有解决方案。
我们研究三个问题：决定源模式的所有文档是否可以被映射到目标模式的文档（绝对一致性），决定源模式的给定文档是否可以被映射（解决方案存在），以及为给定源文档构造解决方案（解决方案构建）。
我们表明，绝对一致性的复杂性是相当高的一般情况下，但在有限深度模式的多项式层次结构。解的存在性和解的构建的组合复杂度表现类似，但数据复杂度非常低。
除此之外，我们表明，即使是更有表现力的映射规则，基于MSO可定义的查询，绝对一致性是可判定的，解决方案存在的数据复杂性是多项式的。
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.
We investigate three 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).
We show 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 turns out to be very low.
In addition to this we show that even for much more expressive mapping rules, based on MSO definable queries, absolute consistency is decidable and data complexity of solution existence is polynomial.
XML 模式映射
DOI：
10.1145/1559795.1559801
发表时间：
2009
期刊：
--
影响因子：
--
作者：
Amano S
通讯作者：
Amano S