How to Prove Serializability
As we covered in this earlier post , serializability means that the database should appear to run transactions in some sequential order. In other words, although we might run transactions concurrently, to the clients, it should appear we are running transactions one-at-a-time. This definition seems clear, but how can we precisely prove that a given transactional system is serializable? The problem is the word "appear" in this definition; what do we formally mean by that? In this post, we see how we can prove the serializability of a transactional system. After covering some definitions, we will see how we can prove serializability of one of the transactional databases that we covered in this blog-- FoundationDB . Serializability, Conflict-serializability, and Precedence Graph The following definitions and theorems are from [1-2]. Definition 1 (Schedule): a sequence of (important) steps taken by one or more transactions. In concurrency control, the important ste...