Complexity of Data Tree Patterns over XML Documents
Complexity of Data Tree Patterns over XML Documents
复制标题
DOI：
10.1007/978-3-540-85238-4_22
复制
发表时间：
2008-08
期刊：
影响因子：
--
通讯作者：
C. David
中科院分区：
文献类型：
--
作者：
C. David
我们认为数据树模式的布尔组合作为XML文档的规范和查询语言。数据树模式是树模式加上表示属性值之间连接的变量（不）等式。数据树模式是表示XML文档属性的一种简单而自然的形式。我们首先考虑的模型检测问题（查询评估），我们表明，它是DP-完全的一般和alreadyNP-完全的，当我们考虑一个单一的模式。然后，我们考虑的可满足性问题，在存在的DTD。我们表明，它是在一般不可判定的，我们确定了几个可判定的片段。
We consider Boolean combinations of data tree patterns as a specification and query language for XML documents. Data tree patterns are tree patterns plus variable (in)equalities which express joins between attribute values. Data tree patterns are a simple and natural formalism for expressing properties of XML documents. We consider first the model checking problem (query evaluation), we show that it is DP-complete in general and alreadyNP-complete when we consider a single pattern. We then consider the satisfiability problem in the presence of a DTD. We show that it is in general undecidable and we identify several decidable fragments.