一种支持对象代理数据库高效查询处理的索引结构

文中为对象代理数据库提出了一种新的索引结构--路径导航索引(Path Navigation Index,PNI),能够克服路径表达式计算开销大的缺点,使对象代理数据库跨类查询与代理对象查询具备高效的查询性能.PNI索引建立在代理层次的路径实例之上,包括Path-Instance-Table,Identity-Index和Attribute-Index 3个组成部分.Path-Instance-Table能够物化存储路径实例,避免查询处理过程中冗余的对象导航遍历.Identity-Index与Attribute-Index用于对路径实例进行关联检索,能够避免对象导航过程中的条件判断.通过实验分析了影响路径表达式计算的不同因素,实验结果表明,利用PNI索引计算路径表达式的方法在多数情况下性能要优于现有计算方法,尤其适用于带谓词的路径表达式计算.     

对象代理数据库的虚属性查询优化方法磁

为对象代理数据库的虚属性查询提出两种优化方法---表达式提升和虚属性合并。表达式提升将虚属性查询转换为对源类中实属性的查询;虚属性合并是对查询涉及的属于相同源对象的多个虚属性,一次性获取相应源对象的属性值用于虚属性值的计算,避免多次访问同一源对象。通过实验分析了这两种方案对虚属性查询的性能影响,实验结果表明,对于虚属性和代理层数较多的查询,表达式提升和虚属性合并的方法极大提升了查询效率。     

VPM:列存储系统中基于带值路径的物化技术

物化是列存储数据仓库查询中必不可少的操作,物化策略和物化技术直接影响到查询执行的性能,因此设计一种适应于列存储系统的物化策略和相关技术尤为重要.针对延迟物化可能重复读取数据块的缺陷,提出了基于带值路径的物化技术,简称VPM.首先,定义了一个描述物理执行中间结果的结构——传递块,该结构将用于重构的位置信息与实际列值相分离.在此基础上,对于给定的物理查询树,根据其操作节点是否需要某一列的值进行路径标记,生成自扫描节点或抽值节点到最终需要这些节点的引用列的祖先节点之间的路径,即带值路径.将起始节点引用列的列值保存在传递块的列值区中,并在向查询树的上层操作节点传输过程中不断对其过滤.对带值路径中的其他列仅保存其位置信息.在查询执行时,除了路径起始节点要从磁盘读取数据外,其他节点直接从传递块中获得相应的列值,有效地减少了查询处理过程的I/O开销,提高了查询的执行性能.最后在DWMS上使用TPC-H中针对数据仓库的基准数据集SSBM进行实验,验证了基于带值路径物化技术的有效性.     

XML数据库的索引技术研究

目前XML已经成为Internet以及电子商务中进行数据表示和数据交换事实上的标准.本文研究了XML的两种索引技术即结点记录类索引、结构摘要索引.深入分析了XML数据的区间编码技术,利用编码技术使孩子与双亲节点,兄弟节点可以通过编码值获取,降低节点对树型结构的依赖程度,使得查询在执行表达式时不必遍历整个结构树;同时引入基于后缀树的索引构造技术,尽可能地合并相同标签路径的节点.所以,周游一条路径即可得到该标签路径下的所有节点,避免了相同标签路径的重复访问的缺陷.     

传感器网络中多近似连续范围查询的处理技术

无线传感器网络为数据库研究开辟了新的研究领域,高效利用节点的有限能量是当前研究的主要目标.如果发布到网络中多个近似连续范围查询不经优化处理而独立执行,会造成节点为不同查询重复发送相同感知数据,从而降低网络寿命.针对近似连续范围查询研究了多查询优化技术,设计了一种索引多维范围查询的多叉树结构rq-kd-tree,通过获取多查询的公共查询部分(查询相交区域)以及基于查询相似度合并相交区域上的多个查询、重写查询.最后,实验证明了所提的算法可以实现能量有效的多查询处理过程.     

L(k)-index:一种支持标签路径的高效k双拟结构索引

针对基于k双拟的结构索引创建和更新低效问题、查询结果重复验证问题以及标签路径不可获得性问题,提出了一种新的结构索引L(k)-index.L(k)-index通过引入标签路径,在创建时无须k次遍历原数据,并采取批量更新策略,大大提高索引创建和更新的效率,而在空间上仅有很小增加.对于长度大于k+1的路径查询,L(k)-index无须访问原数据进行验证,并支持批量节点的标签路径获得.通过大量实验表明,同A(k)-index相比,L(k)-index创建时间平均提高66.7%,查询处理时间效率平均提高68.9%,批量更新效率平均每节点提高58.8%,而空间仅增加22.5%.     

对象代理数据库跨类查询与代理对象查询的索引结构分析

数据库技术的发展促使其在不同领域得到了广泛的应用。包括数字图书馆等在内的一些新的应用领域对数据库的应用提出了更高的要求。而在这些新的应用领域中,多会涉及到一些复杂的、非传统形式的数据。而对象代理数据库能较好地支持各种非传统形式的数据类型,可以对各种复杂的数据类型实施有效的管理,而且对象代理数据库引入的对象代理数据库跨类查询与代理对象查询的索引结构,现在提高了数据库跨类查询的效率。该文主要从对象代理数据库跨类查询索引结构的设计、对象代理数据库跨类查询索引机制的实现以及一种基于代理对象查询机制索引结构的说明这三个方面来对对象代理数据库跨类查询与代理对象查询的索引结构作详细的分析。     

OBB碰撞检测算法的改进与实现

为降低OBB碰撞检测算法的时间复杂度,提高运算效率,提出面向对象的碰撞检测算法以及基于相关性的遍历跟踪策略.改进的OBB碰撞检测算法当物体的位置或方向发生变化时,检测是否与场景中其它物体发生碰撞;基于相关性的遍历跟踪策略通过跟踪上一时刻活动模型在环境对象树中的遍历过程来确定当前的遍历路径,以滤除重复的遍历过程.实验结果表明,改进后的OBB碰撞检测算法降低了碰撞检测算法的复杂度,提高了运算效率,保证了仿真节点模型的自治性和互不干扰性.     

Java自动化基本路径测试研究

针对Java单元测试自动化程度和测试效率较低的问题,对基于Java程序的基本路径测试方法进行研究,提出了基于Java代码的基本路径生成方法和程序插桩方法,给出了插桩节点和控制流图节点的定义。首先,通过对Java源代码进行分析,构建程序的控制流图,进而对控制流图进行遍历生成基本路径集合;然后,对被测程序进行插桩,以获取程序的执行路径,插桩过程中保持节点和基本路径中的节点一致,使得插桩后的被测程序执行时得到的路径能够和基本路径集合进行自动化比对;最后,通过以测试数据为输入执行被测程序,对执行路径和基本路径进行比较,判断测试数据集对基本路径的覆盖度。通过实验,验证了所提出方法的有效性。     

对AGV路径规划A星算法的改进与验证

为了减少AGV（Automate Guide Vehicle,自动导引车）的运输路径长度和转折次数,提出了改进的A星算法,采用几何方法对传统A星算法规划出的路径进行进一步优化。首先遍历路径上的所有节点,剔除路径中冗余节点和不必要拐点,获取仅包含起点、必要拐点、终点的路径。最后计算AGV在拐点处的旋转角度及旋转方向,使AGV在拐点处能够调整自身姿态。并分别对传统A星算法、蚁群算法和改进A星算法进行了对比实验。实验结果表明该方法不仅保留了A星算法运算速度快的优点,还能够有效地规划出距离短且平滑的路径。提高了AGV的运行效率,降低了AGV的耗能。     

一个基于对象代理模型的多表现地理信息系统

文中提出了一种基于对象代理模型的实现多表现GIS的新方法。通过地理对象的代理对象来定义多表现，因此代理对象可以用来表示对象的视角多样性和角色多样性。通过对象更新迁移可以支持动态分类和系统一致性维护。另外，对象及其代理对象之间的双向指针使得跨类查询变得非常容易，从而可以扩展查询的范围。文中实现了一个基于对象代理模型的多表现GIS原型，性能测试表明该方法比传统的方法更加有效。     

异构数据源数据集成的研究

对象代理模型可以作为数据集成的一种通用数据模型。通过建立代理对象和源对象，查询处理的对应关系也能够较好地实现，应用可以将不同的、对于代理对象的查询处理翻译成对于局部数据源源对象的查询处理，也可以把对局部数据源的查询结果以用户应用想要的方式返回。对象代理模型可在Smalltalk环境中实现。本文讨论如何在Smalltalk
k环境中实现基于对象代理模型的异构信息源的集成。     

以目标节点为导向的XML路径查询处理

XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.     

An object deputy model for realization of flexible and powerful objectbases

In object-oriented databases, data and methods are combined by objects and their classes. Information redundancies are removed by the notions of class hierarchy and inheritance. This contributes the realization of high-performance systems. However, the flexibility of object structures still remains a problem due to its encapsulation feature. In this paper, we introduce an object deputy model which extends conventional object-oriented models with the concepts of deputy objects and deputy classes. A deputy object has its own identifier and may possess its own attributes and methods. It can also have attributes that are computed from values stored within its source object, and can be associated with methods generated from these of the source object. The inheritances are realized by switching operations, which make it possible to realize controllable, selective and dynamic inheritance structures. Schemata of deputy objects are defined by deputy classes which can be derived by an object deputy algebra. An object can have many deputy objects, and several objects can share a single deputy object. Thus, objects can be indirectly divided and combined through their deputy objects. We show that several difficult database problems, such as flexible views, objects with more than one role, object migration, and multiple inheritance become much easier in this model. The data-knowledge coordination model developed for the integration of distributed databases and knowledge-bases can also be realized easily by the object deputy model. Finally, we discuss several advanced database applications of this model, such as geographic databases, virtual office systems, and distant education systems.     

一种最优的静态路径编码存储策略

路径编码方案通过记录从XML文档根结点到当前结点的路径信息,可以快速判断结点间的各种位置关系.高效的编码存储策略可以在提高存储空间利用率的同时,减少系统的IO开销,从而进一步提升系统的整体性能.提出一种最优的静态路径编码存储策略,其基本思想是在存储编码中的数字时,每个编码中数字对应的前缀并非提前给定,而是根据其所在数字区间中数字的使用频率之和给定相应的前缀,因此可以充分利用每个不同数字的频率信息来降低所需的存储空间.最后通过实验结果验证了该方法的可行性及有效性.     

Optimizing top-k selection queries over multimedia repositories

Repositories of multimedia objects having multiple types of attributes (e.g., image, text) are becoming increasingly common. A query on these attributes will typically, request not just a set of objects, as in the traditional relational query model (filtering), but also a grade of match associated with each object, which indicates how well the object matches the selection condition (ranking). Furthermore, unlike in the relational model, users may just want the k top-ranked objects for their selection queries for a relatively small k. In addition to the differences in the query model, another peculiarity of multimedia repositories is that they may allow access to the attributes of each object only through indexes. We investigate how to optimize the processing of top-k selection queries over multimedia repositories. The access characteristics of the repositories and the above query model lead to novel issues in query optimization. In particular, the choice of the indexes used to search the repository strongly influences the cost of processing the filtering condition. We define an execution space that is search-minimal, i.e., the set of indexes searched is minimal. Although the general problem of picking an optimal plan in the search-minimal execution space is NP-hard, we present an efficient algorithm that solves the problem optimally with respect to our cost model and execution space when the predicates in the query are independent. We also show that the problem of optimizing top-k selection queries can be viewed, in many cases, as that of evaluating more traditional selection conditions. Thus, both problems can be viewed together as an extended filtering problem to which techniques of query processing and optimization may be adapted.     

最佳路径的层次编码及查询算法

有效的路径查询处理是地理信息系统、系统及计算机网络等高级应用中的一个关键需求,文研究如交通网络和通信网络等节点发大的网络中的最佳路径查询算法,为了保证最佳路径查询的响应时间,采用定例化最佳路径视图的熏 预先计算和存储最佳路径,文中提出了ＨＥＰＶ（Ｈｉｅｒａｒｃｈｉｃａｌ Ｅｎｃｏｄｅｄ Ｐａｔｈ Ｖｉｗｅ）结构,证明在ＨＦＥＰＶ上进行路径查询最佳性,同时给出了相庆的最佳路径查询算法。     

移动Sink的传感器网络路径优化策略

在无线传感器网络（WSNs）中引入移动 Sink 可以避免网络拥塞和能量空洞并降低网络能耗,但由于移动速度的限制导致时延较大。针对这一问题,提出了时延约束下的移动 Sink 路径优化策略,根据时延和网络能耗之间的关系设计了可调节的节点权重,通过模拟退火遗传算法得到最优节点权重,并依据此权重通过迭代得到汇聚节点和最佳移动路径。仿真结果表明：该策略能保证在满足时延约束的前提下降低网络能耗,且收敛速度快。     

有向无环图上k步可达查询优化算法

k步可达查询用于在给定的有向无环图（DAG）中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出一种基于部分点的双向最短路径索引来提升索引的可达信息覆盖率,并提出一组优化规则来减小索引规模;然后提出基于简化图的正反互逆拓扑索引来加速回答不可达查询;最后提出远距离优先的双向遍历策略来提高查询处理的效率。基于21个真实数据集（如引用网络、社交网络等）的实验结果表明,相比已有的高效方法PLL及BFSI-B,所提出的算法具有更小的索引规模和更快的查询响应速度。     

基于复杂模式索引的XML查询优化*

分析了XML模式与XML文档之间的关系以及XML查询的特点,提出了一种基于复杂模式索引的XML查询优化方法.该方法对XML模式中的节点建立索引,查询时考虑XML模式中带有环的情况.首先对查询树进行去除重复元素的预处理,并将查询树分解成主路径和分支路径;然后利用索引查找潜在目标节点的XML模式编号;最后在XML文档中对对应节点进行筛选,找到目标节点.该方法可以减少连接操作的次数,提高查询操作的效率,能处理较复杂的XML模式.