On the minimization of Xpath queries Sergio Flesca, Filippo Furfaro, and Elio Masciari   View Paper (PDF)   Return to XML Queries Processing I (Session A4) Abstract XML queries are usually expressed by means of XPath expressions identifying portions of the selected documents. An XPath expression defines a way of navigating an XML tree and returns the set of nodes which are reachable from one or more starting nodes through the paths specified by the expression. The prob- lem of efficiently answering XPath queries is very interesting and has recently received in- creasing attention by the research community. In particular, an increasing effort has been devoted to define effective optimization tech- niques for XPath queries. One of the main issues related to the optimization of XPath queries is their minimization. The minimiza- tion of XPath queries has been studied for lim- ited fragments of XPath, containing only the descendent, the child and the branch opera- tors. In this work, we address the problem of minimizing XPath queries for a more general fragment, containing also the wildcard oper- ator. We characterize the complexity of the minimization of XPath queries, stating that it is NP-hard, and propose an algorithm for computing minimum XPath queries. More- over, we identify an interesting tractable case and propose an ad hoc algorithm handling the minimization of this kind of queries in poly- nomial time. ©2004 Association for Computing Machinery