On the Complexity of Verifying Consistency of XML Specifications
On the Complexity of Verifying Consistency of XML Specifications
复制标题
DOI：
10.1137/050646895
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Marcelo Arenas;Wenfei Fan;Leonid Libkin
中科院分区：
文献类型：
--
作者：
Marcelo Arenas;Wenfei Fan;Leonid Libkin
XML规范通常由类型定义（通常是文档类型定义（DTD））和一组完整性约束组成。前面已经说明，这些规范可能不一致，因此通常需要在编译时检查一致性。它是已知的[W。Fan和L. Libkin， J. ACM, 49 (2002), pp. 368-406]认为对于通用键、外键和dtd，一致性问题是不可确定的；但是，当所有键都是单属性（一元）且可处理（如果不使用外键）时，它就成为np完备的。在本文中，我们考虑了以前研究过的各种XML数据约束，并研究了一致性问题的复杂性。我们的主要结论是，在存在外键约束的情况下，编译时的一致性验证是不可行的。我们查看保存在整个文档中的绝对约束和仅保存在文档的一部分中的相对约束。对于绝对约束，我们证明了主多属性键和一元外键的可判定性，建立了复杂度界，并研究了正则表达式中的一元约束。对于相对约束，我们证明了即使对于一元约束，一致性问题也是不可判定的。我们还展示了扩展dtd（一种更具表现力的XML类型机制）的结果仍然成立。
XML specifications often consist of a type definition (typically, a document type definition (DTD)) and a set of integrity constraints. It has been shown previously that such specifications can be inconsistent, and thus it is often desirable to check consistency at compile time. It is known [W. Fan and L. Libkin, J. ACM, 49 (2002), pp. 368-406] that for general keys, foreign keys, and DTDs the consistency problem is undecidable; however, it becomes NP-complete when all keys are one-attribute (unary) and tractable, if no foreign keys are used. In this paper, we consider a variety of previously studied constraints for XML data and investigate the complexity of the consistency problem. Our main conclusion is that, in the presence of foreign key constraints, compile-time verification of consistency is infeasible. We look at absolute constraints that hold in the entire document and relative constraints that hold only in a part of the document. For absolute constraints, we prove decidability and establish complexity bounds for primary multiattribute keys and unary foreign keys and study unary constraints that involve regular expressions. For relative constraints, we prove that even for unary constraints the consistency problem is undecidable. We also show that results continue to hold for extended DTDs, a more expressive typing mechanism for XML.