The complexity of XPath query evaluation and XML typing
The complexity of XPath query evaluation and XML typing
复制标题
XPath 查询评估和 XML 类型化的复杂性
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
L. Segoufin
中科院分区：
文献类型：
--
作者：
G. Gottlob;Christoph E. Koch;R. Pichler;L. Segoufin
我们研究了两个核心的XML处理问题的复杂性。第一个是XPath 1.0查询处理，这在以前的工作中已经被证明是快速的。我们证明了XPath 1.0的数据复杂性和查询复杂性都属于较低(高度可并行化)的复杂性类别，而两者的组合复杂性是ptime-hard。随后，我们研究了这种困难的来源，并确定了XPath 1.0的一个大的和实际重要的片段，对于它，组合的复杂性是LOGCFL-完全的，因此，在高度可并行化的复杂性类NC2中。第二个问题是根据各种类型模式(如文档类型定义(DTD)、XML模式定义(XSD)和树自动机)验证XML文档的复杂性，这既涉及数据，也涉及组合复杂性。对于数据复杂性，我们证明了验证是在LOGSPACE中进行的，并且关键取决于如何表示XML数据。对于组合的复杂性，我们表明，根据输入方案的不同，复杂度从LOGSPACE到LOGCFL。
We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTIME in previous work. We prove that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, while the combined complexity is PTIME-hard. Subsequently, we study the sources of this hardness and identify a large and practically important fragment of XPath 1.0 for which the combined complexity is LOGCFL-complete and, therefore, in the highly parallelizable complexity class NC2. The second problem is the complexity of validating XML documents against various typing schemes like Document Type Definitions (DTDs), XML Schema Definitions (XSDs), and tree automata, both with respect to data and to combined complexity. For data complexity, we prove that validation is in LOGSPACE and depends crucially on how XML data is represented. For the combined complexity, we show that the complexity ranges from LOGSPACE to LOGCFL, depending on the typing scheme.