XQL is one of the query languages proposed for querying XML documents on the world wide web. In this paper, we consider the
logical rewriting of XQL query expressions in order to improve the efficiency of query evaluation when XML document type definitions
(DTDs) are present. We first define three classes of constraint which can be derived from a given DTD. With a suitable representation
of an XML repository
R as a relational database
D, it turns out that these DTD constraints correspond to tuple- and equality-generating dependencies which must hold on
D.
Next, we identify a subset of XQL queries on R which is equivalent to a class of conjunctive queries on D. Given a conjunctive query C equivalent to an XQL query Q, we then apply techniques from relational dependency theory to reduce the number of conjuncts in C, yielding query C′. Conjunctive query C′ can then be mapped back to an XQL query Q′ in which redundant filter subexpressions and unnecessary selections have been removed.
Whether Q′ can be evaluated more efficiently than Q depends on whether or not appropriate indices exist in R. However, the techniques presented in this paper can provide a query optimizer with a set of equivalent XQL expressions from
which to select the best. The representation of queries in relational form and of constraints as dependencies should also
permit the application of these results to other XML query languages.