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.