On the coNP hardness of computing certain answers over locally specified incomplete DOM-trees

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.