Containment, Equivalence, and Related Problems for XPath Expressions

。一大类应用程序通过XPath表达式访问XML数据，并且需要根据一个简单的测试做出例行决策：一个XPath表达式是否包含在另一个XPath表达式中，这意味着第一个的答案始终是第二个的答案的子集。这些应用的例子包括查询优化、查询重写、语义缓存、基于XML的内容路由。尽管表面上看起来很简单，但当XPath表达式包括通配符、子代轴和谓词时，容器问题却难以分析，这一点令人惊讶。以前的工作只关注在ptime中存在包容问题的XPath的玩具片段，但这些简单的结果不适用于更真实的片段。这个项目研究了XPath的大片段的包容问题。在该项目的初步调查中，发现包含通配符、子代轴和过滤器的XPath表达式的包容问题是co-NP困难的，这表明不可能找到完整而有效的包容算法。鉴于此，将设计几个算法来探索效率和完备性之间的权衡。该项目的一个目标是设计一个完整的算法，该算法总是返回正确的答案，通常以指数时间运行，但在XPath表达式的特殊实例上高效运行。另一个目标是设计一种始终高效运行的启发式算法，但在某些情况下可能会返回假阴性。将对这两种算法进行正式分析，以便全面了解它们提供的性能或精度保证。最有希望的算法将被实施，并在公共领域可用。

. 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.