IPI:灵活高效的对象代理数据库索引结构*
2018-08-15李宇珺彭智勇彭煜玮
李宇珺,彭智勇,吴 瑕,兰 海,彭煜玮
武汉大学 计算机学院,武汉 430072
1 引言
面向对象模型解决了传统关系模型难以建模复杂数据的问题,但对象的封装性使得其对象难以分割和重组,从而不具有关系模型的柔软性。针对上述问题,对象代理模型(object deputy model,ODM)应运而生[1],它兼具关系模型的柔软性和面向对象模型的建模能力。近年来,ODM被广泛应用于数据仓库[2]、生物数据管理[3]、地理信息系统[4]、科学工作流[5]和不确定数据管理[6]等领域。对象代理数据库(object deputy database,ODDB)管理系统图腾[7](Totem)已基于ODM开发完成。它在继承了面向对象数据库诸多优点(如直接建模复杂对象等)的基础上,使用代理对象增强了对象的柔软性,允许对已有对象进行分解、组合和扩充,比面向对象数据库具有更柔软的建模能力。
ODDB中的每个对象和其每一个源对象或代理对象都被一个双向指针链接在一起,这类指针称为双向指针。跨类查询作为ODDB的主要查询功能之一,是指基于对象间的双向指针链接,从某个类的对象出发,沿着类路径到达另一个与其存在直接或间接代理关系的类,并对该类中关联对象进行的查询。跨类查询是由路径表达式(path expression,PE)实现的[8],因此优化PE的计算效率对提升ODDB的性能有重大影响。
本文针对ODDB的PE计算提出了一种索引结构——倒排路径索引(inverted path index,IPI),并基于IPI设计实现了计算PE的方法。IPI的核心思想是物化对象间的代理关系,并允许在谓词条件上建立索引以过滤不满足条件的对象。基于IPI的PE计算方法,能灵活用于任意PE,同时避免计算中冗余的对象遍历,有效地减少PE的计算开销。……