Schema design for XML repositories: complexity and tractability
Schema design for XML repositories: complexity and tractability
复制标题
XML 存储库的模式设计：复杂性和易处理性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
T. Schwentick
中科院分区：
文献类型：
--
作者：
W. Martens;Matthias Niewerth;T. Schwentick
Abiteboul等人发起了对分布式XML文档的系统研究，这些文档由几个逻辑部分组成，可能位于不同的机器上。这种文档的物理分布立即引起了以下问题：如何将分布式文档的全局模式分解为不同逻辑部分的局部模式？所需的本地模式集应该保证，如果每个逻辑部分满足其本地模式，则分布式文档满足全局模式。Abiteboul等人提出了局部模式的三个期望层次：局部类型化、最大局部类型化和完美局部类型化。直接算法问题是：（i）给定一个类型，确定它是局部的、最大局部的还是完美的，（ii）给定一个文档和一个模式，确定是否存在（最大）局部或完美的类型。本文改进了他们工作中的开放复杂性结果，并开始了对（i）和（ii）模式限制的研究，这些模式限制来自当前标准：具有确定性内容模型的DTD和XML模式。最引人注目的结果是，这些限制为完美类型问题带来了易于处理的复杂性。进一步解决了形式语言理论中的一个公开问题：确定性有限自动机的语言素性是p空间完全的。
Abiteboul et al. initiated the systematic study of distributed XML documents consisting of several logical parts, possibly located on different machines. The physical distribution of such documents immediately raises the following question: how can a global schema for the distributed document be broken up into local schemas for the different logical parts? The desired set of local schemas should guarantee that, if each logical part satisfies its local schema, then the distributed document satisfies the global schema. Abiteboul et al. proposed three levels of desirability for local schemas: local typing, maximal local typing, and perfect local typing. Immediate algorithmic questions are: (i) given a typing, determine whether it is local, maximal local, or perfect, and (ii) given a document and a schema, establish whether a (maximal) local or perfect typing exists. This paper improves the open complexity results in their work and initiates the study of (i) and (ii) for schema restrictions arising from the current standards: DTDs and XML Schemas with deterministic content models. The most striking result is that these restrictions yield tractable complexities for the perfect typing problem. Furthermore, an open problem in Formal Language Theory is settled: deciding language primality for deterministic finite automata is pspace-complete.
分布式XML设计
DOI：
10.1145/1559795.1559833
发表时间：
2009
期刊：
--
影响因子：
--
作者：
Abiteboul S
通讯作者：
Abiteboul S