Containment, Equivalence, and Related Problems for XPath Expressions

点击翻译按钮获取中文摘要

. A large class of applications access XML data through XPath expressions and need to make routine decisions based on a simple test: whether one XPath expressions is contained in another, meaning that the answer to the first is always is subset of the answer to the second. Examples of such applications include query optimization, query rewriting, semantic caching, XML-based content routing. Despite its apparent simplicity, the containment problem turns out to be surprisingly difficult to analyze when XPath expressions include wild-cards, descendant axes, and predicates. Previous work has focused on only toy fragments of XPath for which the containment problem is in PTIME, but these simple results fail for more realistic fragments. This project studies the containment problem for a large fragment of XPath. During initial investigations for the project it was established that the containment problem for XPath expressions that contain wild-cards, descendant axes, and filters is co-NP hard, suggesting that a complete and efficient containment algorithm is impossible to find. In light of that, several algorithms will be designed in order to explore the tradeoff between efficiency and completeness. One goal of the project is to design a complete algorithm that always returns the correct answer, runs in exponential time in general, but runs efficiently on special instances of XPath expressions. Another goal is to design a heuristic algorithm that always runs efficiently, but that may return false negatives in certain cases. Both algorithms will be analyzed formally, in order to provide a full insight into what performance or precision guarantees they offer. The most promising algorithm will be implemented and made available in the public domain.