| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427550 | Information Processing Letters | 2010 | 4 Pages |
Abstract
We consider answering queries over incomplete XML trees. Barceló et al. identified a class of shallow queries for which the problem is efficiently solvable with node ids on trees while it is coNP-complete without them. We show that their result is essentially tight. In other words, we provide a slightly extended class of queries where node ids help no more.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
