Main memory database systems: an overview

Main memory database systems (MMDBs) store their data in main physical memory and provide very high-speed access. Conventional database systems are optimized for the particular characteristics of disk storage mechanisms. Memory resident systems, on the other hand, use different optimizations to structure and organize data, as well as to make it reliable. The authors survey the major memory residence optimizations and briefly discuss some of the MMDBs that have been designed or implemented     

面向更新密集型应用的内存数据库高效检查点技术

面向更新密集型应用的内存数据库系统,其检查点技术应符合几个关键的要求,包括检查点操作对正常事务处理的干扰尽可能小、能够处理存取倾斜状况、支持数据库系统的快速恢复、提供恢复过程中的系统可用性等.该文提出一种事务一致的分区检查点技术,采用基于元组的动态多版本并发控制机制,避免了读写事务的加锁冲突,提高系统吞吐能力;检查点操作以只读事务形式实现,存多版本并发控制下,避免检查点操作对正常事务处理的堵塞;由于检查点文件是事务一致的,只需要记录事务的Redo 日志信息,在系统恢复过程中,只需要对日志文件进行一遍扫描处理,加快恢复过程;基于优先级的数据分区装载和恢复,使得恢复过程中新事务的数据存取请求迅速得到满足,保证了恢复过程中的系统可用性.由于采用两级版本管理机制以及动态版本共享技术,多版本管理的空间开销降低到可以接受的水平.实验结果表明,文中提出的检查点技术方案获得比模糊检查点技术高27%的系统吞吐量,同时版本管理的空间开销在可接受的范围之内,满足高性能应用的要求.     

内存数据库中一种改进的图论存取方法及其性能分析

内存数据库是支持高性能信息处理的一种方法，对于内存数据库而言，数据库的存储结构与存取方法是关键。本文给出了一种内存数据库组织与存取的改进图论方法，并对该方法给几个基本的查询处理操作所能带来的优势进行了探讨，最后从存储空间和操作执行时间两方面进行了性能分析，结果显示改进的图论方法能提供很好的性能。     

内存数据库在TPC-H负载下的处理器性能

Ailamaki等人1999年研究了数据库管理系统(database management system,简称DBMS)在处理器上的时间开销分解.此后,相关研究集中在分析DBMS在处理器上的瓶颈.但这些研究工作均是在磁盘数据库DRDBs(disk resident databases)上开展的,而且都是分析DBMS上的TPC-C类负载.然而,随着硬件技术的进步,现代计算机的多级缓存结构(memory hierarchy)在逐渐地"上移".例如,容量越来越大的芯片内缓存(on-chip caches)和芯片外缓存(off-chip caches),容量越来越大的RAM,Flash Memory等等.为此,处理器负载分析的研究工作也应随之"上移".研究内存数据MMDBs(mainmemory resident databases)在计算密集型负载下的处理器行为特性.由于磁盘数据库的主要性能瓶颈是磁盘I/O,因而可以用索引、压缩等技术进行优化;然而,内存数据库的性能瓶颈却在于处理器和内存之间的数据交换.针对这一问题,首先分析了磁盘数据库和内存数据库在TPC-H负载下处理器性能瓶颈的差异,并给出了一些优化建议,提出了通过预取的优化方法.其次,通过实验比较了不同存储体系结构(行存储与列存储)对处理器利用率的差异,并探索了下一代内存数据库体系结构方面的解决方案.此外,还研究了索引结构对处理器多级缓存的影响,并给出了索引的优化建议.最后,提出一个微测试集用于评估内存数据库在DSS(decision support system)负载下处理器的性能及行为特性.研究结果会对运行于下一代处理器上的内存数据库体系结构设计和性能优化提供一定的实验依据.     

实时数据库事务的正确性及实现算法

实时数据库系统中事务可以有定时限制（典型地为截止期）,事务超过截止期可能给系统带来灾难性后果,事务不光要满足数据库的完整性与一致性,而且要满足在时间上的正确性以及事务之间在结构上的正确性,传统的事务处理方法仅着眼于事务存取数据库的正确性,对于时间正确性与结构正确性无能为力,详细讲座了实时事务的正确性,包含结果正确性、时间正确性、行为正确性及结构正确性,已有的研究成果中大多用不央的算法及策略来保证不同的正确性要求;给出了保证实时事务正确性的一个统一的图论算法。     

Incorporating load factor into the scheduling of soft real-time transactions for main memory databases

Many real-time applications have very tight time constraints which couldn't be met by disk resident databases. For those applications, main memory database where entire database is stored in main memory is the proper choice. It has been shown that coarse-granule locking is better than fine-granule locking for main-memory databases. Coarse-granule locking makes it easy to extract data access patterns correctly from canned transactions of main memory real-time database systems. In this paper, we propose two real-time transaction scheduling algorithms — CCA-ALF (Cost Conscious Approach with Average Load Factor) and EDF-CR-ALF (Earliest Deadline First-Conditional Restart with ALF) — which use both static (e.g., deadline) and dynamic information (e.g., system load) for main memory databases by utilizing data access patterns of transactions. We compare the performance of those algorithms with CCA and EDF-HP which do not use system load information at all. Our simulations on main memory databases indicate that: i) CCA-ALF is better than EDF-HP, CCA, and EDF-CR-ALF in terms of miss percent and mean lateness, and ii) CCA-ALF adapts well to the changes in the system load.     

Batch incremental processing for FP-tree construction using FP-Growth algorithm

In the present scenario of global economy and World Wide Web, large sets of evolving and distributed data can be handled efficiently by incremental data mining. Frequent patterns are very important in knowledge discovery and data mining process, such as mining of association rules, correlations. FP-tree is a very versatile data structure used for mining of frequent patterns in knowledge discovery and data mining process. FP-tree is a compact representation of transaction database that contains frequency information of all relevant frequent patterns (FP) of the database. All of the existing incremental frequent pattern mining algorithms, such as AFPIM, CATS, CanTree, CP-tree, and SPO-tree, perform incremental mining by processing one transaction of the incremental part of database at a time and updating it to the FP-tree of initial (original) database. Here, in this paper, we propose a novel method that takes advantage of FP-tree representation of incremental transaction database for incremental mining. We propose a batch incremental processing algorithm BIT_FPGrowth that restructures and merges two small consecutive duration FP-trees to obtain a FP-tree of the FP-Growth algorithm. Our BIT_FPGrowth uses FP-tree as preprocessed data repository to get transactions (i.e., item-sets), unlike other sequential incremental algorithms that read transactions from database. BIT_FPGrowth algorithm takes less time for constructing FP-tree. Our experimental results show that, as the size of the database increases, increase in runtime of BIT_FPGrowth is much less and is least of all the other algorithms.     

移动数据库系统乐观事务处理策略

在移动数据库系统中，计算平台的移动性，频繁的断接性以及长事务等特性使得传统的事务处理模式不再适用，为了解决移动数据中的事处处理问题，提出了一种新的移动事务处理模型－乐观两阶段提交移动事务模型（O2PC－MT），该模型采用乐观并发控制与两阶段提交协议相结合的方法，对移动事务的长事务特性提供了灵活与有效的支持，此外，该模型允许移动计算机分多发送中务操作，且在事务执行过程中可以任意移动，从而提供了对交互式事务及随意移动性的支持，实验结果表明，与基于两段锁协议及其变形的其它移动事务处理模型相比，O2PC－MT提高了系统的事务吞吐率并改善了系统的总体性能。     

Priority assignment in real-time active databases

Active databases and real-time databases have been important areas of research in the recent past. It has been recognized that many benefits can be gained by integrating real-time and active database technologies. However, not much work has been done in the area of transaction processing in real-time active databases. This paper deals with an important aspect of transaction processing in real-time active databases, namely the problem of assigning priorities to transactions. In these systems, time-constrained transactions trigger other transactions during their execution. We present three policies for assigning priorities to parent, immediate and deferred transactions executing on a multiprocessor system and then evaluate the policies through simulation. The policies use different amounts of semantic information about transactions to assign the priorities. The simulator has been validated against the results of earlier published studies. We conducted experiments in three settings: a task setting, a main memory database setting and a disk-resident database setting. Our results demonstrate that dynamically changing the priorities of transactions, depending on their behavior (triggering rules), yields a substantial improvement in the number of triggering transactions that meet their deadline in all three settings. Edited by Henry F. Korth and Amith Sheth. Received November 1994 / Accepted March 20, 1995     

基于影子页面和混合日志的MMDB恢复方法

为了提升内存数据库从各种故障中恢复的速度,提出了基于影子页面技术、混合日志策略以及模糊检查点思想的内存数据库恢复方法。在分析内存数据库运行过程中主要的时间消耗点的基础上建立了内存数据库的系统模型,通过分析事务过程和检查点过程,讨论了该恢复策略的执行过程以及优点,讲述了内存数据库在此系统模型和恢复策略下的事务故障和系统故障的恢复过程以及系统的性能分析。     

A neural-based concurrency control algorithm for database systems

Concurrency control (CC) algorithms guarantee the correctness and consistency criteria for concurrent execution of a set of transactions in a database. A precondition that is seen in many CC algorithms is that the writeset (WS) and readset (RS) of transactions should be known before the transaction execution. However, in real operational environments, we know the WS and RS only for a fraction of transaction set before execution. However, optional knowledge about WS and RS of transactions is one of the advantages of the proposed CC algorithm in this paper. If the WS and RS are known before the transaction execution, the proposed algorithm will use them to improve the concurrency and performance. On the other hand, the concurrency control algorithms often use a specific static or dynamic equation in making decision about granting a lock or detection of the winner transaction. The proposed algorithm in this paper uses an adaptive resonance theory (ART)-based neural network for such a decision making. In this way, a parameter called health factor (HF) is defined for transactions that is used for comparing the transactions and detecting the winner one in accessing the database objects. HF is calculated using ART2 neural network. Experimental results show that the proposed neural-based CC (NCC) algorithm increases the level of concurrency by decreasing the number of aborts. The performance of proposed algorithm is compared with strict two-phase locking (S2PL) algorithm, which has been used in most commercial database systems. Simulation results show that the performance of proposed NCC algorithm, in terms of number of aborts, is better than S2PL algorithm in different transaction rates.     

实时内存数据库的装入

实时数据库(real-time database,简称RTDB)要求以内存数据库(main memory database,简称MMDB)作为其底层支持.内存数据库的脆弱性使得数据库的装入(包括初装和重装)极为频繁,对系统性能影响极大,而传统的装入算法对实时内存数据库不适用.为此给出影响数据装入的实时数据及事务特征,并提出一种数据装入策略与算法.     

实时主动数据库有效性检查并发控制协议

在实时主动数据库中,事务不仅有时间约束,而且事务执行可能触发其它事务执行。传统并发控制协议不适应于实时主动数据库系统。该文研究了实时主动数据库事务执行模式,提出了有效性检查并发控制协议。协议使用动态调整串行次序策略,避免不必要的事务重启动。通过仿真模拟与HP2PL协议和OCC-TI-WAIT-50协议进行了比较。结果表明,该协议能有效地降低事务延误截止时间率和事务重启动率,性能优于HP2PL和OCC-TI-WAIT-50协议。     

基于预分析的实时事务处理

实时数据库系统中事务可能有实时限制（典型地为截止期），事务超过截止期可能给系统带来灾难性后果，这就要求系统能对事务的执行进行预分析与预安排，传统事务处理由于事务执行过程中的多种不确定因素（数据I／O，页面缺失，事务之间的各种相关性等），事务执行具有动态不可预报性，提出了一种事务预分析处理的三段法，数据说明阶段的静态预分析提取事务静态信息；初始动态预分析阶段构造事务的“影了事务”，并在适当的时机调度影子事务执行，以保证事务操作之前所需数据已在内存，事务执行时动态预分析阶段构造事务的相关性，为事务执行的结构，行为及时间正确性提供统一的实现机制，事务执行具有更好的可预报性，从而事务能更好地满足截止期。     

Effects of update techniques on main memory database systemperformance

Update technique is an important issue related to database recovery. In a main memory database environment, transaction execution can be processed without any I/O, and all I/O operations involved are for recovery purposes. The efficiency of update techniques therefore has an important impact on the performance of main memory database systems. We compared the techniques of immediate and deferred update based on a database machine, MARS. The simulation results showed that immediate update outperforms deferred update unless system failure is a frequent occurrence     

Applying semantic knowledge to real-time update of access control policies

Real-time update of access control policies, that is, updating policies while they are in effect and enforcing the changes immediately, is necessary for many security-critical applications. In this paper, we consider real-time update of access control policies in a database system. Updating policies while they are in effect can lead to potential security problems, such as, access to database objects by unauthorized users. In this paper, we propose several algorithms that not only prevent such security breaches but also ensure the correctness of execution. The algorithms differ from each other in the degree of concurrency provided and the semantic knowledge used. Of the algorithms presented, the most concurrency is achieved when transactions are decomposed into atomic steps. Once transactions are decomposed, the atomicity, consistency, and isolation properties no longer hold. Since the traditional transaction processing model can no longer be used to ensure the correctness of the execution, we use an alternate semantic-based transaction processing model. To ensure correct behavior, our model requires an application to satisfy a set of necessary properties, namely, semantic atomicity, consistent execution, sensitive transaction isolation, and policy-compliant. We show how one can verify an application statically to check for the existence of these properties.     

Global committability in multidatabase systems

Develops a formal basis for research into the reliability aspects of transaction processing in multidatabase systems (MDBSs). We define a new correctness notion called `global committability' for the correct unilateral commit and the retry recovery of global transactions in an autonomous MDBS environment. This notion makes it easier to ensure the isolation property of global transactions when the retry approach is applied. The formalization work illustrates that the conventional serializability and recoverability notions are not sufficient to specify the correct execution (i.e. isolated execution and recovery) of global transactions when the unilateral commit and the retry recovery are used to ensure the atomicity of global transactions. This work is significant because the unilateral commit and the retry recovery are an attractive complementary means to the undo recovery (whose correct schedule is specified by the conventional recoverability notion) for advanced transaction applications with the characteristics of site autonomy and long-lived execution     

实时Client/Server数据库并发控制和恢复机制研究

该文提出了实时Client／Server数据库系统多版本两阶段封锁并发控制协议和有效的恢复机制。协议区分只读事务和更新事务。只读事务在执行读操作时遵从多版本时间排序协议,更新事务执行强两阶段封锁协议,即持有全部锁直到事务结束。只读事务读请求从不失败,不必等待等特性。在典型数据库系统中,读操作比写操作频繁。这个特性对于实践来说至关重要。为了提高只读事务的响应时间,协议让每个客户端与一个一致数据库影子相联,只读事务在客户端处理。更新事务提交到服务端运行。服务端每个事务Ti在提交时系统必须向所有客户端广播信息。客户端根据得到的广播信息自动构造一致数据库影子。一致数据库影子还将用于系统恢复。通过仿真模拟。与2V2PL和OCC-TI-WAIT-50协议进行比较,结果表明：该并发控制协议不仅能有效降低事务延误截止时间率和重起动率,而且能改善只读事务的响应时间,减少优先级高事务的锁等待时间。协议性能优于2V2PL协议和OCC-TI-WAIT-50协议。     

Transaction processing in a peer to peer database network

This paper investigates a transaction processing mechanism in a peer to peer database network. A peer to peer database network is a collection of autonomous data sources, called peers, where each peer augments a conventional database management system with an inter-operability layer (i.e. mappings) for sharing data. In this network, each peer independently manages its database and executes queries as well as updates over the related data in other peers. In this paper, we consider a peer to peer database network where mappings between peers are established through data-level mappings for sharing data and resolving data heterogeneity. With regards to transaction processing in a peer to peer database network, we mainly focus on how to maintain a consistent execution view of concurrent transactions in peers without a global transaction coordinator. Since there is no global transaction coordinator and each peer executes concurrent transactions independently, different peers may produce different execution views for the same set of transactions. For this purpose, we investigate potential problems that arise when maintaining a consistent execution of concurrent transactions. In order to guarantee consistent execution, we introduce a correctness criteria and propose two approaches, namely Merged Transactions and OTM based propagation. We assume that one single peer initiates the concurrent transactions. We also present a solution for ensuring the consistent execution view of concurrent transactions considering the failures of transactions.     

支持分布式合作实时事务处理的协同检验点方法

在实时事务执行时，事务故障或数据竞争会导致事务重启，为减少事务重启损失的工作量，可以采用检验点技术保证事务的时间正确性．在一类分布式实时数据库应用中，不同结点的事务通过消息交换形成合作关系，为保证合作事务间的全局一致性，当某一事务记检验点时，相关事务也要记检验点．传统协同检验点方法没有考虑应用的定时约束，不能很好地支持分布式合作实时事务处理．该文提出了一种基于图论的协同检验点方法，利用在每个计算结点上为每个合作事务集维护的局部有向图，使用一个基于图论的计算过程标识出应记检验点的事务，该方法既具有最小协同检验点特性，又使全局检验点的时延最小．实验表明该算法减少了全局检验点时延，有利于实时事务截止期的满足．