Achieving stricter correctness requirements in multilevel secure database management systems

Although high assurance multilevel secure database management systems (DBMSs) are slowly becoming commercially available, these systems have yet to offer a concurrency control protocol that is free of signaling channels and produces serializable (one-copy serializable when multiple versions of data are maintained) histories. In this paper, we consider the multiversion concurrency control algorithm that has been implemented in the Trusted Oracle DBMS. It guarantees levelwise serializability, which is a weaker notion of correctness than one-copy serializability. While levelwise serializability has many desirable properties, it suffers from the inconsistent retrieval problems that may seriously harm database integrity. In this paper, we demonstrate how pairwise serializability and one-copy serializability, stricter correctness criteria than levelwise serializability, can be achieved, using the Trusted Oracle scheduler. It is important to note that rather than taking the usual approach of modifying the underlying concurrency control protocol such that it meets the stricter correctness requirements, we achieve our goal without modifying the Trusted Oracle concurrency control algorithm in any way. In other words, in this paper, we do not propose a new scheduler for concurrency control, but propose algorithms, if used with the Trusted Oracle scheduler, to generate pairwise or one-copy serializable histories. Our approach is based on the assumption that all transactions that are running during a certain interval are known in advance. We perform a static analysis of the read- and write-sets of these transactions to recognize conflicts among transactions. The results of the analysis are used to control the order of submission of the transactions in such a way that stricter correctness requirements are met. All the algorithms proposed in this paper are implementable with untrusted code.