XML with data values: typechecking revisited
XML with data values: typechecking revisited
复制标题
带有数据值的 XML：重新审视类型检查
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
V. Vianu
中科院分区：
文献类型：
--
作者：
N. Alon;Tova Milo;F. Neven;Dan Suciu;V. Vianu
我们调查的XML查询的类型检查问题：静态验证每个查询的答案符合一个给定的输出DTD，输入满足一个给定的输入DTD。这个问题已经由一部分作者在一个简化的框架中进行了研究，该框架捕获了XML文档的结构，但忽略了数据值。我们在这里重新审视的类型检查问题，在更现实的情况下，数据值存在于文档中，并测试查询。在这个扩展的框架中，类型检查很快变得不可判定。但是，对于大类查询和实际感兴趣的DTD，它仍然是可判定的。本文的主要贡献是跟踪一个相当紧密的边界的可判定性类型检查与数据值。在可判定的情况下，类型检查的复杂性也被考虑。
We investigate the type checking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had been studied by a subset of the authors in a simplified framework that captured the structure of XML documents but ignored data values. We revisit here the type checking problem in the more realistic case when data values are present in documents and tested by queries. In this extended framework, type checking quickly becomes undecidable. However, it remains decidable for large classes of queries and DTDs of practical interest. The main contribution of the present paper is to trace a fairly tight boundary of decidability for type checking with data values. The complexity of type checking in the decidable cases is also considered.