tailieunhanh - Database Management systems phần 7

hoạt động mà không làm thay đổi tác động của lịch trình trên cơ sở dữ liệu. Nếu hai lịch trình là tương đương xung đột, nó rất dễ dàng để thấy rằng họ có tác dụng tương tự trên một cơ sở dữ liệu. Thật vậy, bởi vì họ đặt hàng tất cả các cặp của các hoạt động trái ngược nhau trong cùng một cách, | Concurrency Control 541 operations without altering the effect of the schedule on the database. If two schedules are conflict equivalent it is easy to see that they have the same effect on a database. Indeed because they order all pairs of conflicting operations in the same way we can obtain one of them from the other by repeatedly swapping pairs of nonconflicting actions that is by swapping pairs of actions whose relative order does not alter the outcome. A schedule is conflict serializable if it is conflict equivalent to some serial schedule. Every conflict serializable schedule is serializable if we assume that the set of items in the database does not grow or shrink that is values can be modified but items are not added or deleted. We will make this assumption for now and consider its consequences in Section . However some serializable schedules are not conflict serializable as illustrated in Figure . This schedule is equivalent to executing the transactions T1 T 2 T 3 fi A W A Commit W A Commit W A Commit Figure Serializable Schedule That Is Not Conflict Serializable serially in the order T1 T2 T3 but it is not conflict equivalent to this serial schedule because the writes of T1 and T2 are ordered differently. It is useful to capture all potential conflicts between the transactions in a schedule in a precedence graph also called a serializability graph. The precedence graph for a schedule S contains A node for each committed transaction in S. An arc from Ti to Tj if an action of Ti precedes and conflicts with one of Tj s actions. The precedence graphs for the schedules shown in Figures and are shown in Figure parts a b and c respectively . The Strict 2PL protocol introduced in Section allows only serializable schedules as is seen from the following two results 542 Chapter 19 Figure Examples of Precedence Graphs 1. A schedule S is conflict serializable if and only if its precedence graph is acyclic. An equivalent .