Abstract: Existing index structures for evaluating path expression in object deputy database all have an obvious disadvantage which is lack of flexibility. To solve this problem, this paper proposes an index structure: inverted path index (IPI), which can not only be used flexibly for any path expression, but also effectively reduce the cost of evaluation. IPI consists of Inverted-Object-Index and Predicate-Index, the former uses inverted index to store the deputy relationship between objects, and the latter facilitates the associative search of objects. Based on IPI index structure, IPI index method is designed and implemented to evaluate path expression. The experiments are taken on various influential factors of path expression evaluation, and the experimental results show that IPI index method can evaluate path expression efficiently, and its flexibility outperforms the other methods in most cases.

Key words: object deputy database, inverted path index, path expression, query optimization, flexibility

摘要： 目前对象代理数据库中路径表达式计算的索引结构都存在一个严重问题：缺乏灵活性。针对该问题提出了一种索引结构——倒排路径索引（inverted path index，IPI），包括Inverted-Object-Index和Predicate-Index。前者利用倒排索引存储对象间的代理关系，后者则辅助进行对象关联检索，不仅能灵活用于任意路径表达式，还能有效减少计算开销。基于IPI索引结构设计实现了计算路径表达式的IPI索引方法。通过实验分析了影响路径表达式计算效率的各种因素，实验结果表明，IPI索引方法能高效地计算路径表达式，且灵活性在多数情况要优于现有方法。

关键词: 对象代理数据库, 倒排路径索引, 路径表达式, 查询优化, 灵活性