空间数据库系统中R树的并发控制设计与实现

R树是实现快速空间数据处理的重要索引结构之一，但由于其并发控制的复杂性，虽研究已久但仍然很少的真正地集成到商用数据库中。R-link树是为了实现并发控制而提出的一种R树结构的变化，但它仍然存在幻像等问题。文章分析了R－link树中存在的这一问题并通过设计一个基于内存的操作控制列表（Operation Control List.OCList）来预先避免可能造成幻像的并发操作，从而实现完全的并发控制，实验证明所提方案是正确的，低开支的，而且有利于提高系统性能。     

基于动态内存和状态管理的模型检测新方法

模型检测是并发系统验证的主要形式化方法之一,但其存在因状态空间爆炸而导致内存不够的问题,这也是大规模并发系统验证的瓶颈.很多研究人员尽管做了很多相关研究,但仍然没有很好地解决这个问题.在研究动态内存和状态管理的基础上,提出了一种新的模型检测方法,避免了因为内存不足而无法模型检测的问题.     

实时数据库系统中动态调整串行次序的乐观并发控制算法

尽管已证明在RTDBSs中乐观并发控制方法的性能要优于锁式并发控制,但乐观并发控制存在不必要的重新启动以及较高的重启动代价的问题。该文介绍一种新的乐观并发控制算法,它通过结合动态调整串行次序和使用时标间隔来达到减少重新启动事务的目的,因而其性能高于传统的乐观并发控制方法。     

基于多维粒度树的GIS空间数据并发控制

从空间数据之间的拓扑关系出发,提出了一种基于角色和权限的GIS并发控制体系,利用用户的权限解决空间数据的拓扑关系问题,将拓扑关系问题演变为不同类型的空间数据集合问题。针对不同类型的空间数据集合,采用了基于角色与权限的封锁粒度,来实现对空间数据及其拓扑关系的统一封锁。由于采用了基于角色与权限的封锁粒度,大大增加了并发控制的复杂性。该文应用多维粒度树,有效地解决了封锁粒度的复杂性问题。     

B树及其在文件组织中的应用

数据库的实现是以文件为基础的,B树因其平衡、高效、易变的特点而成为一种普遍采用的文件索引组织形式。本文介绍B树的基本概念;从文件索引的角度重点介绍了对B~ 树的基本操作,以及为了进一步提高B树效率而衍生出的B树变种——B~*树,前缀B树等。简单地讨论了在多用户环境下使用B树的并发控制。最后给出一个使用B~ 树的实例VSAM。     

模糊时间Petri网及其时间推理方法

Petri网是一种用网状图形表示系统模型的方法,它能够从组织结构、控制和管理的角度,精确描述系统中事件(变迁)之间的依赖(顺序)和不依赖(并发)关系。但传统的Petri网理论其不足之处在于:它的分析方法主要是可达树分析法和线性代数描述法。可达树分析法是针对某一个初始标识的,一个新的初始标识就意味着需要重新构造可达状态图;当系统存在较多     

数据库系统中动态调整串行次序的乐观并发控制算法

尽管已证明在RTDBSs中乐观并发控制方法的性能要优于锁式并发控制,但乐观并发控制存在不必要的重新启动以及较高的重启动代价的问题.该文介绍一种新的乐观并发控制算法,它通过结合动态调整串行次序和使用时标间隔来达到减少重新启动事务的目的,因而其性能高于传统的乐观并发控制方法.     

实时数据库系统中动态调整串行次序的乐观交发控制算法

尽管已证明在RTDBSs中乐观并发控制方法的性能要优于锁式并发控制，但乐观并发控制存在不必要的重新启动以及较高的重启动代价的问题。该文介绍一种新的乐观并发控制算法，它通过结合动态调整串行次序和使用时标间隔来达到减少重新启动事务的目的，因而其性能高于传统的乐观并发控制方法。     

空间数据库主动规则并发行为控制研究

网络环境下空间信息大规模应用中常常有大量的用户规则同时触发,这带来了规则并发行为的控制和效率问题．目前大多数方法难以满足大量用户同时操作时的频繁动态更新,因此提出标注事件图分析模型及并发规则集终止性分析算法,通过实例说明算法的有效性和通用性．在并发索引结构Rlink树基础上,提出一种支持空间数据库主动规则频繁更新的混合索引结构HRlink树及改进的自底向上更新算法IBUU．实验仿真表明,采用IBUU算法的HRlink树频繁更新性能大大高于Rlink树．     

PowerBuilder数据库中并发控制的实现

网络新时代的数据库应用系统中,并发控制是要解决的主要问题。本文首先介绍PowerBuilder数据库系统的并发控制机制,并介绍了其在实现数据库多用户并发控制、分布式事务并发控制及其嵌入SQL语句并发控制的原理及其部分技术案例。     

GLIP: A Concurrency Control Protocol for Clipping Indexing

Multidimensional databases are now beginning to be used in a wide range of applications. To meet this fast-growing demand, the R-tree family is being applied to support fast access to multidimensional data, for which the R+-tree exhibits outstanding search performance. In order to support efficient concurrent access in multi-user environments, concurrency control mechanisms for multidimensional indexing have been proposed. However, these mechanisms cannot be directly applied to the R+-tree because an object in the R+-tree may be indexed in multiple leaves. This paper proposes a concurrency control protocol for R-tree variants with object clipping, namely, Granular Locking for clIPping indexing (GLIP), dubbed an R+-tree variant, the Zero-overlap R+-tree (ZR+-tree). To the best of our knowledge, GLIP is the first concurrency control approach designed specifically for the R+-tree and its variants. The proposed GLIP supports efficient concurrent operations on R+-trees with serializable isolation, consistency, and deadlock-free. Experiment results on both real and synthetic data sets validated the effectiveness and efficiency of the proposed concurrent access framework.     

The RUM-tree: supporting frequent updates in R-trees using memos

The problem of frequently updating multi-dimensional indexes arises in many location-dependent applications. While the R-tree and its variants are the dominant choices for indexing multi-dimensional objects, the R-tree exhibits inferior performance in the presence of frequent updates. In this paper, we present an R-tree variant, termed the RUM-tree (which stands for R-tree with update memo) that reduces the cost of object updates. The RUM-tree processes updates in a memo-based approach that avoids disk accesses for purging old entries during an update process. Therefore, the cost of an update operation in the RUM-tree is reduced to the cost of only an insert operation. The removal of old object entries is carried out by a garbage cleaner inside the RUM-tree. In this paper, we present the details of the RUM-tree and study its properties. We also address the issues of crash recovery and concurrency control for the RUM-tree. Theoretical analysis and comprehensive experimental evaluation demonstrate that the RUM-tree outperforms other R-tree variants by up to one order of magnitude in scenarios with frequent updates.     

R树家族的演变和发展

近年来,针对空间数据库索引的研究引起了人们越来越多的兴趣和关注．为了快速、有效地处理存储于空间数据库中的海量空间数据,专家学者提出了大量的基于磁盘的空间索引方法．其中,1984年由Guttman提出的R树是目前最流行的动态空间索引结构,广泛应用于原型研究和商业应用中．其后,人们在此基础上针对不同空间运算提出了不同改进,经过20年的发展,不断产生的R树变体逐渐形成了一个枝繁叶茂的空间索引R树家族．该文回顾了R树及其各种主要变体;描述了基于R树的各种批量操作、空间查询处理算法、查询代价模型及查询优化过程;介绍了基于R树的并行处理、并发控制与锁定策略等方面的进展;并且分析了R树的未来研究方向．     

Performance Evaluation of Lazy Deletion Methods in R-trees

Motivated by the way R-trees are implemented in commercial databases systems, in this paper we examine several deletion techniques for R-trees. In particular, in commercial systems R-tree entries are mapped onto relational tables, which implement their own concurrency protocols on top of existing table-level concurrency mechanisms. In analogy, the actual industrial implementations of B-trees do not apply the well-known merging procedure from textbooks in case of node underflows, but rather they apply the free-at-empty technique. This way, space is sacrificed for the benefit of faster deletions and less locking operations, whereas the search performance practically remains unaffected. In this context, we examine the efficiency of modifications to the original R-tree deletion algorithm, which relax certain constraints of this algorithm and perform a controlled reorganization procedure according to a specified criterion. We present the modified algorithms and experimental results about the impact of these modifications on the tree quality, the execution time for the deletion operation and the processing time of search queries, considering several parameters. The experimental results indicate that the modified algorithms improve the efficiency of the deletion operation, while they do not affect the quality of the R-tree and its performance with respect to search operations.     

更新分发环境下移动事务处理的节能策略设计

能量的损耗和事务的一致性是更新分发环境下移动应用所需要考虑的两个主要问题,但传统的节能技术并不支持对移动客户端移动事务的并发控制,而现有的基于数据广播的移动事务处理方法主要针对保持数据一致性而设计,并未考虑事务处理过程中的节能问题.将分布式索引技术应用于移动事务处理,提出一种在更新分发环境下同时实现移动事务并发控制和节能处理的有效方法.实验结果表明使用该方法比未应用索引技术前节能84.5%.     

一种支持工程设计事务的乐观并发控制方法

传统乐观并发控制方法对工程设计事务支持较弱。该文以嵌套事务模型为基础并结合检入＝检出机制,提出一种改进的乐观并发控制方法,能够较好地解决传统乐观并发控制方法在工程设计务应用上存在的问题并提高了事务的并发度。     

Hybrid protocols using dynamic adjustment of serialization order for real-time concurrency control

Conclusions Time-critical scheduling in real-time database systems has two components: real-time scheduling and concurrency control. While both concurrency control and real-time scheduling are well-developed and well-understood, there is only limited knowledge about the integration of concurrency control and real-time scheduling. Though recently the problem has been studied actively, the proposed solutions are still at an initial stage. A major source of problems in integrating the two is the lack of coordination in the development. They are developed on different objectives and incompatible assumptions (Buchmann 1989).Most of the proposed work for real-time concurrency control employ a simple method to utilize one concurrency control scheme such as 2PL, TO and OCC, and to consider the priority of operations inherited from the timing constraints of transactions in operation scheduling. This method has an inherent disadvantage of being limited by the concurrency control method used as the base. Since neither of pessimistic nor optimistic concurrency control is satisfactory by itself for real-time scheduling, this simple method using only one control can hardly satisfy the timing requirements of RTDBS. Problems such as excessive blocking, wasted restarts, and priority inversion are serious in RTDBS.In this paper, we proposed two real-time transaction scheduling protocols which employ a hybrid approach, i.e., a combination of both pessimistic and optimistic approaches. These protocols make use of a new conflict resolution scheme called dynamic adjustment of serialization order, which supports priority-driven scheduling, and avoids unnecessary aborts.This work was supported in part by ONR, by NRaD, by DOE, and by IBM.     

并发对象的一种描述机制

面向对象模型潜在的并发计算能力为并发程序设计提供了更高层次的解决方案。为了充分利用这种潜在的并发招行能力,必须在对象模型中显式地给出并发控制。本文给出了一种描述并发对象的机制,即：把对象的并发控制作为对象的单独属性进行描述,在定义子类时,把对象的并发描述与对象的方法分开进行继承。我们的目标是使得引进的并发机制尽量少地与对象模型的各个重要特性相冲突,减轻继承异常。另外,我们提出的并发模型允许对象内部的并发。     

Formal aspects of optimistic concurrency control in a multiple version database system

Formal aspects of optimistic concurrency control in a multiple version database system are discussed. It is distinguished between element-optimistic and set-optimistic methods. In an element-optimistic method the unit of scheduling for the concurrency control is one action/transaction, while in a set-optimistic method a set of transactions is scheduled. The underlying decision problems of serializability are defined and shown to be NP-complete in a model, which is typical for most modern transaction oriented database management systems. Therefore it is most probable, that both optimistic concurrency control types cannot be implemented efficiently in the general case.     

同步协同设计中并发控制的研究

为解决协同设计过程中存在的数据一致性不高、数据传输量大、实时性差等问题,通过分析分布式CSCW环境中并发控制的各种方法,并根据同步协同设计特点和用户操作意愿,设计了并发控制网络模型.在该模型中,计算数据传输的最小延时确定主控站点,提出了基于事务优先权的混合并发控制策略,以保证协同用户在操作过程中的并发率.实例证明,以上措施的实现保证用户自由共享资源,提高了并发控制的实时性和数据的一致性.