A systematic approach for the design of post-transaction input error handling

Most of the errors that occur in the input of a program cannot be automatically detected through input validation. As a result, most of such errors made in the input of a database transaction are discovered only after the completion of the transaction. Therefore, the provision of error correction transactions for correcting such error is essential in any database application. Current system development methodologies do not provide much detail for this important design task. The task is left to the designer's experience to carry out in an ad hoc way. This paper formalizes the common design knowledge in designing these transactions. It proposes a novel approach for the systematic design of post-transaction input error handling in a database application.     

Application Specific Transaction Management in Multidatabase Systems

We present a transaction model for multidatabase systems with autonomous component systems, coined heterogeneous 3-level transactions. It has become evident that in such a system the requirements of guaranteeing full ACID properties and full local autonomy can not be reconciled. In the heterogeneous 3-level transaction model, semantics of actions and specific properties of the architecture of multidatabase systems and of applications are utilized to define application specific compromises between these competing goals. We consider different definitions of conflicts between actions together with application specific sets of allowed (autonomous) local transactions and global subtransactions. A formal model for serializability is given. It is proven that heterogeneous 3-level transactions guarantee all consistency constraints that are ensured in serial executions. In contrast to most other models, we do not require data to be partitioned into global and local data. In particular, heterogeneous 3-level transactions even allow the same data to be updated by local and global transactions in parallel, if these updates are found to be semantically non-conflicting. Recovery is handled by inverse actions. We present a formal framework for this approach which is fully integrated into serializability theory by considering inverse actions as ordinary actions. This has an important impact on the relationship of concurrency control and recovery in our model: By changing the definition of conflicts between actions in order to tailor the model according to application needs, recovery is implicitly affected and no further explicit adaptation of recovery algorithms is necessary. The heterogeneous 3-level transaction model assumes component database systems to support ACID transaction properties. Further properties of local transactions or interfaces of the component database systems are not required. We describe a prototype implementation of heterogeneous 3-level transactions in the object-oriented database system VODAK.     

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 scheduling for flexible transactions in heterogeneousdistributed database systems

A heterogeneous distributed database environment integrates a set of autonomous database systems to provide global database functions. A flexible transaction approach has been proposed for the heterogeneous distributed database environments. In such an environment, flexible transactions can increase the failure resilience of global transactions by allowing alternate (but in some sense equivalent) executions to be attempted when a local database system fails or some subtransactions of the global transaction abort. We study the impact of compensation, retry, and switching to alternative executions on global concurrency control for the execution of flexible transactions. We propose a new concurrency control criterion for the execution of flexible and local transactions, termed F-serializability, in the error-prone heterogeneous distributed database environments. We then present a scheduling protocol that ensures F-serializability on global schedules. We also demonstrate that this scheduler avoids unnecessary aborts and compensation     

Incremental recovery in main memory database systems

Recovery activities, like checkpointing and restart, in traditional database management systems are performed in a quiescent state where no transactions are active. This approach impairs the performance of online transaction processing systems, especially when a large volatile memory is used. An incremental scheme for performing recovery in main memory database systems (MMDBs), in parallel with transaction execution, is presented. A page-based incremental restart algorithm that enables the resumption of transaction processing as soon as the system is up is proposed. Pages are recovered individually and according to the demands of the post-crash transactions. A method for propagating updates from main memory to the backup database on disk is also provided. The emphasis is on decoupling the I/O activities related to the propagation to disk from the forward transaction execution in memory. The authors also construct a high-level recovery manager based on operation logging on top of the page-based algorithms. The proposed algorithms are motivated by the characteristics of large MMDBs, and exploit the technology of nonvolatile RAM     

基于多数法的分布式并发控制的实现及改善

对分布式事务采用多副本并发控制的多数法,实现了一个多层分布式数据库应用系统的模型设计;引入了协调对象并使用COM＋技术,在实现分布式事务执行无阻塞、数据正确恢复的前提下,对模型进行了改善,提高了数据库模型执行的效率。     

Modeling and analysis of transaction execution in database systems

The controlled-generator model of P.J. Ramadge and W.M. Wonham (1988) is used to formulate the concurrent execution of transactions in database systems as a control problem for a partially observed discrete-event dynamical system. The control objectives of this problem (for concurrency control and recovery) and the properties of some important transaction scheduling techniques are characterized in terms of the language generated by the controlled process and in terms of the stage of an ideal complete-information scheduler. Results about the performance of these techniques are presented     

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

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

Improving Predictability of Transaction Execution Times in Real-time Databases

We present a design for multi-versionconcurrency control and recovery in a main memory database, anddescribe logical and physical versioning schemes that allowread-only transactions to execute without obtaining data itemlocks or system latches. Our schemes enable a system to providethe guarantee that updaters will never interfere with read-onlytransactions, and read-only transactions will not be delayeddue to data contention. Consequently, transaction executionsbecome more predictable—this partially alleviates a majorproblem in real-time database system (RTDBS) scheduling, namely,significant unpredictability in transaction execution times.As a result, in addition to a transaction's deadline, a moreaccurate estimate of its execution time can also be taken intoaccount, thus facilitating better scheduling decisions. Our contributionsinclude several space saving techniques for the main-memory implementation,including improved methods for logical aging of data items andthe introduction of physical aging for low-level structures.Some of these schemes have been implemented on a widely-usedsoftware platform within Lucent, and the full scheme is implementedin the Dalí main-memory storage manager.     

MDARTS: a multiprocessor database architecture for hard real-timesystems

Complex real time systems need databases to support concurrent data access and provide well defined interfaces between software modules. However, conventional database systems and prior real time database systems do not provide the performance or predictability needed by high speed, hard real time applications. The authors designed, implemented, and evaluated an object oriented database system called MDARTS (Multiprocessor Database Architecture for Real Time Systems). MDARTS avoids the client server overhead of most prior real time database systems and object oriented, real time systems by moving transaction execution into application tasks. By eliminating these sources of overhead and focusing on basic data management services for control systems (data sharing, serializable transactions, and multiprocessor support), the MDARTS prototype provides hard real time transaction times approximately three orders of magnitude faster than prior real time database systems. MDARTS ensures bounded locking delay by disabling preemption when a transaction is waiting for a lock, and hence, allows for the estimation of worst case transaction execution times. Another contribution of MDARTS is that it supports explicit declarations of real time requirements and semantic constraints within application code. The MDARTS library examines these declarations at application initialization time and attempts to construct objects that are compatible with the requirements. Besides local shared memory transactions with hard real time response time guarantees, MDARTS also supports remote transactions that use remote procedure calls for data access with less stringent timing constraints. The MDARTS prototype is implemented in C++ and it runs on VME based multiprocessors and Sun workstations     

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.     

Transaction decomposition using transaction semantics

Serializability has been widely accepted as the correctness criterion for databases subject to concurrent access. However, in a number of the newer and most challenging application areas, serializable execution may not be feasible.

? Serializable execution is generally implemented using a two-phase locking algorithm that locks items in the database to delay transactions that are in danger of performing in a non-serializable fashion. Such delays are unacceptable in high performance database systems that must process hundreds, and perhaps thousands, of transactions per second and in systems supporting long-running transactions.

? In systems in which data is distributed across a federated database, a global transaction is decomposed into a set of local subtransactions executed at a subset of the sites. Serializable execution in such systems not only incurs a performance penalty, but also requires the component systems to cooperate (for example in a two phase commit protocol), with a resulting loss of site autonomy. In many applications, the component systems either can not or will not agree to the required cooperation.

A number of models have recently been proposed in which transactions are decomposed into smaller, atomic, interleavable steps. These models have the potential for improving performance since locks are released at the end of each step. Models of distributed transactions have also been proposed with the similarity that subtransactions correspond to steps. In most of this work serializability is no longer guaranteed. In this paper we propose a new, application-oriented, correctness criterion that utilizes transaction semantics. We treat transactions as programs whose semantics can be analyzed at design time. The effect of each transaction is specified using pre- and postconditions, and any schedule that preserves these conditions is permissible. Such schedules can produce database states that could not be reached by any serial execution. In addressing the issue of performance, we use transaction semantics to decompose transactions into steps and describe a concurrency control that controls step interleaving in such a way that assertions are preserved. The same model can be used to study the interleaving of subtransactions of concurrent distributed transactions.     

A proof technique for concurrency control and recovery algorithms for replicated databases

A replicated database is a distributed database in which copies of some data items are stored redundantly at multiple sites. In such a system, an execution of transactions iscorrect if it is equivalent to a serial execution of those transactions on a one copy database. We show that in any serializable execution, if all transactions see the failures and recoveries of data item copies in a consistent order, then the execution is correct. We model this condition using a modified type of serialization graph, and show that if this graph is acyclic then the corresponding execution is correct. We demonstrate the value of this model by using it to prove the correctness of an algorithm for synchronizing access to a replicated database. Philip A. Bernstein is Professor of Information Technology at the Wang Institute of Graduate Studies. Previously, he was Vice President Software at Sequoia Systems, Associate at Harvard University, and a researcher at Computer Corporation of America, where he was codesigner of four distributed database systems. Professor Bernstein's research focuses on the theory and implementation of database systems and transaction processing systems. He is an Associate Editor of ACM Transactions on Database Systems, and on the editorial board of this journal. Nathan Goodman is a senior consulting engineer at Encore Computer Corporation. Previously he was with Sequoia Systems, where he developed a transaction processing system for a fault-tolerant multiprocessor computer. Prior to that he was with Computer Corporation of America, where he participated in the design of three distributed systems: SDD-1, the first relational distributed DBMS; Multibase, a system for querying relational and nonrelational distributed databases; and DDM, a distributed DBMS based on ADA. Dr. Goodman was a professor Computer Science at Harvard University and Boston University. He has done research on query optimization, concurrency control, and failure recovery.Research supported by the National Science Foundation, grant number MCS79-07762, and by the Office of Naval Research, contract number N00014-80-C-674.     

Planning and Implementing Kerberos for Large Distributed Systems Part 1

ABSTRACT

For maintaining the consistency of database, the recovery algorithms traditionally depend on complete rollback to a consistent checkpoint. The recovery problem from committed malicious transactions can be solved by determining the dependencies between the transactions in window of vulnerability. Since the size of transactional log may grow very large, recovery becomes a complex and time-consuming process. In this paper, we propose an approach which incorporates application specific information to determine transactional dependencies. The approach is applied to column based transaction dependency to obtain better performance. The system is implemented at application layer where SQL queries are generated. In recovery phase, we consider only affected and malicious transactions for rollback and skip the good transactions.     

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     

Efficient execution of read-only transactions in replicatedmultiversion databases

Multiple versions of data are used in database systems to increase concurrency. The higher concurrency results since read-only transactions can be executed without any concurrency control overhead and, therefore, read-only transactions do not interfere with the execution of update transactions. Availability of data in a distributed environment is improved by data replication. We propose a protocol for managing data in a replicated multiversion environment, where execution of read-only transactions or queries becomes completely independent of the underlying concurrency control and replica control mechanisms, and the data availability for read-only transactions increases significantly since they can be executed as long as any one copy of the object is available in the system. In order to validate the feasibility of our approach, we developed a simple prototype to measure the performance improvement in the response times of queries. The results clearly establish the viability of the approach as a useful paradigm for the design of efficient and fault-tolerant distributed database systems     

大型实时数据库系统设计及并发控制调度

系统地分析了大型实时数据库系统的应用环境和功能需求，提出了企业大型实时数据库的体系结构、设计思路和实现方法，研究了实时主动数据库事务执行模式，提出了有效性检查并发控制协议。协议使用动态调整串行次序策略，避免不必要的事务重启动，并能有效降低事务延误截止时间。该实现方法在工程应用中取得了良好的效果。     

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.     

A column dependency-based approach for static and dynamic recovery of databases from malicious transactions

Even state of the art database protection mechanisms often fail to prevent occurrence of malicious attacks. Since in a database environment, the modifications made by one transaction may affect the execution of some of the later transactions, it leads to spreading of the damage caused by malicious (bad) transactions. Following traditional log-based recovery schemes, one can rollback (undo) the effect of all the transactions, both malicious as well as non-malicious. In such a scenario, even the unaffected transactions are also rolled back. In this paper, we propose a column dependency-based approach to identify the affected transactions which need to be compensated along with the malicious transactions. To ensure durability, committed non-malicious transactions are then re-executed in a manner that retains database consistency. We present a static recovery algorithm as well as an on-line version of the same and prove their correctness. A detailed performance evaluation of the proposed scheme with TPC-C benchmark suite is also presented.     

基于级联深度的主动实时乐观并发控制协议

主动实时数据库因结合了时间限制与主动机制而使系统事务的并发控制变得更为复杂。主动规则的引入使事务触发新的事务且在执行上具有多种耦合方式,传统的实时并发控制策略无法对具有复杂执行模式的事务进行有效调度,而基于主动数据库的并发控制机制也没有考虑事务的实时性问题。通过对事务不同耦合方式的实时要求及事务间冲突关系进行分析,提出了新的主动实时数据库乐观并发控制方法,对不同事务级联深度进行评估,结合事务执行的时间信息对冲突事务进行动态调整串行化顺序。理论分析与实验证明,能在保证事务可串行性的同时降低了不必要事务重启个数,更好地满足系统的实时性。