Lazy Transaction Execution Models

Transactions are the fundamental unit of change as perceived by the database. In Online Transaction Processing (OLTP) applications, transaction behavior is often insensitive to the intial database state. For example, in a flight booking application, a user may not care what exact seat is booked as long as it is a window seat. Similarly, in an online shopping application, the exact value of the stock level of an item is irrelevant for a purchase transaction as long as there is enough stock to fulfill an order. Such insensitivity of transactions towards the initial database state presents opportunities for optimizing system performance. In this dissertation, we present two systems which exploit such insensitivity in transactions by deferring the execution of certain operations until the effect of such operations are externally perceivable. First we present Quantum Databases - a lazy transaction processing system that defers the making of choices in transactions until an application or user forces the choice by observation. Conceptually, the database is in a quantum state - in one of many possible worlds, exactly which one is unknown - until fixed by observation. Next, we present Homeostasis - a lazy transaction processing system for distributed or replicated databases which automatically identifies insensitivity of a set of transactions towards the database state and exploits it to minimize the amount of inter-node communication required to guarantee consistency. The key insight is to defer the synchronization of distributed state until such laziness affects the behavior of transactions