On Testing Satisfiability of Tree Pattern Queries

This chapter presents a systematic analysis of satisfiability of tree pattern queries that capture a useful fragment of XPath together with additional constraints, with or without a schema. XPath and XQuery are the two major query languages for XML. An important issue arising in an efficient evaluation of queries expressed in these languages is satisfiability. The satisfiability check can affect substantial savings in query evaluation. The chapter also investigates cases in which the problem can be solved in polynomial time and develops novel efficient algorithms for this purpose. In several cases, the problem is NP-complete. A comprehensive set of investigations to verify the utility of satisfiability check as a preprocessing step in query processing were carried out. The results show that this check takes a negligible fraction of the time needed for processing the query while often yielding substantial savings.