基于以太坊的宠物领养平台外文翻译资料

英语原文共 1 页，剩余内容已隐藏，支付完成后下载完整资料

毕业设计(论文)外文翻译

2019年 2 月 23 日

Database System Concepts

Abraham Silberschatzbull;Henry E Korthbull; S.Sudarshan

14.6 Serializability

Before we can consider how the concurrency-control component of the database system can ensure serializability, we consider how to determine when a schedule is serializable. Certainly, serial schedules are serializable, but if steps of multiple transactions are interleaved, it is harder to determine whether a schedule is serializable. Since transactions are programs, it is difficult to determine exactly what operations a transaction performs and how operations of various transactions interact. For this reason, we shall not consider the various types of operations that a transaction can perform on a data item, but instead consider only two operations: read and write. We assume that, between a read(Q) instruction and a write(Q) instruction on a data item Q, a transaction may perform an arbitrary sequence of operations on the copy of Q that is residing in the local buffer of the transaction. In this model, the only significant operations of a transaction, from a scheduling point of view, are its read and write instructions. Commit operations, though relevant, are not considered until Section 14.7. We therefore may show only read and write instructions in schedules, as we do for schedule 3 in Figure 14.6.

In this section, we discuss different forms of schedule equivalence, but focus on a particular form called conflict serializability.

Let us consider a schedule S in which there are two consecutive instructions, I and J , of transactions T_i and T_j , respectively (i ne; j). If I and J refer to different data items, then we can swap I and J without affecting the results of any instruction in the schedule. However, if I and J refer to the same data item Q, then the order of the two steps may matter. Since we are dealing with only read and write instructions, there are four cases that we need to consider:

1. I = read(Q), J = read(Q). The order of I and J does not matter, since the same value of Q is read by T_i and T_j , regardless of the order.

2. I = read(Q), J = write(Q). If I comes before J , then T_i does not read the value of Q that is written by T_j in instruction J . If J comes before I, then T_i reads the value of Q that is written by T_j . Thus, the order of I and J matters.

3. I = write(Q), J = read(Q). The order of I and J matters for reasons similar to those of the previous case.

4. I = write(Q), J = write(Q). Since both instructions are write operations, the order of these instructions does not affect either T_i or T_j . However, the value obtained by the next read(Q) instruction of S is affected, since the result of only the latter of the two write instructions is preserved in the database. If there is no other write(Q) instruction after I and J in S, then the order of I and J directly affects the final value of Q in the database state that results from schedule S.

Thus, only in the case where both I and J are read instructions does the relative order of their execution not matter.

We say that I and J conflict if they are operations by different transactions on the same data item, and at least one of these instructions is a write operation.

To illustrate the concept of conflicting instructions, we consider schedule 3 in Figure 14.6. The write(A) instruction of T₁ conflicts with the read(A) instruction of T₂. However, the write(A) instruction of T₂ does not conflict with the read(B) instruction of T₁, because the two instructions access different data items.

Let I and J be consecutive instructions of a schedule S. If I and J are instructions of different transactions and I and J do not conflict, then we can swap the order of I and J to produce a new schedule Srsquo; . S is equivalent to Srsquo; , since all instructions appear in the same order in both schedules except for I and J , whose order does not matter.

Since the write(A) instruction of T₂ in schedule 3 of Figure 14.6 does not conflict with the read(B) instruction of T₁, we can swap these instructions to generate an equivalent schedule, schedule 5, in Figure 14.7. Regardless of the initial system state, schedules 3 and 5 both produce the same final system state.

We continue to swap nonconflicting instructions:

bull; Swap the read(B) instruction of T₁ with the read(A) instruction of T₂.

bull; Swap the write(B) instruction of T₁ with the write(A) instruction of T₂.

bull; Swap the write(B) instruction of T₁ with the read(A) instruction of T₂.

The final result of these swaps, schedule 6 of Figure 14.8, is a serial schedule. Note that schedule 6 is exactly the same as schedule 1, but it shows only the read and write instructions. Thus, we have shown that schedule 3 is equivalent to a serial schedule. This equivalence implies that, regardless of the initial system state, schedule 3 will produce the same final state as will some serial schedule.

If a schedule S can be transformed into a schedule Srsquo; by a series of swaps of nonconflicting i

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[253969]，资料为PDF文档或Word文档，PDF文档可免费转换为Word