On Rewriting XPath Queries Using Views
Foto Afrati, Rada Chirkova, Manolis Gergatsoulis, Benny Kimelfeld, Vassia
Pavlaki, Yehoshua Sagiv
Abstract: The problem of rewriting a query using a materialized view is
studied
for a well known fragment of XPath that includes the following three
constructs: wildcards, descendant edges and branches. In earlier work,
determining the existence of a rewriting was shown to be coNP-hard,
but no tight complexity bound was given. While it was argued that
$\Sigma_3^p$ is an upper bound, the proof was based on results that
have recently been refuted. Consequently, the exact complexity (and
even decidability) of this basic problem has been unknown, and there
have been no practical rewriting algorithms if the query and the view
use all the three constructs mentioned above.
It is shown that under fairly general conditions, there are only two
candidates for rewriting and hence, the problem can be practically
solved by two containment tests. In particular, under these
conditions, determining the existence of a rewriting is coNP-complete.
The proofs utilize various novel techniques for reasoning about XPath
patterns. For the general case, the exact complexity remains unknown,
but it is shown that the problem is decidable.