• No results found

ACID PROPERTIES OF TRANSACTIONS

N/A
N/A
Protected

Academic year: 2022

Share "ACID PROPERTIES OF TRANSACTIONS"

Copied!
36
0
0

Loading.... (view fulltext now)

Full text

(1)

T RANSACTION

Faisal Anwer & Mohammad Nadeem

1

(2)

INTRODUCTION

A collection of several operations on the database appears to be a single unit from the point of view of the database user.

Transaction-

A single logical unit of work.

Example-

Transferring money

Many transactions can run simultaneously (concurrent transactions).

Concurrent transactions pose inconsistencies in the database if not handled properly.

2

(3)

ACID PROPERTIES OF TRANSACTIONS

To ensure integrity of data, database maintain following properties of a transaction:

Atomicity-

Either all operations of the transaction are reflected properly in the database, or none are.

Consistency-

A transaction should preserve the consistency of the database.

Isolation-

Each transaction should be unaware of other transactions executing concurrently in the system.

Durability –

After a transaction completes successfully, the changes it has made to the database persist, even if there are system failures.

3

(4)

E XAMPLE

Transactions access data using two operations:

read(X), which reads the data item X from the database.

write(X), which writes the data item X in the database.

Let Ti be a transaction that transfers Rs. 50 from account A to account B:

4

(5)

ACID PROPERTIES OF TRANSACTIONS

Consistency-

The consistency requirement here is that the sum of A and B be unchanged by the

execution of the transaction.

Atomicity-

Suppose that some failure happened after the write(A) operation but before the write(B)

operation.

It will lead database into a inconsistent state.

If the atomicity property is present, all

actions of the transaction are reflected in the database, or none are.

5

(6)

ACID PROPERTIES OF TRANSACTIONS

Durability:

Once the user is notified about the successful transfer of funds, no system failure should result in a loss of data, even if there is a

system failure after the transaction completes execution.

Difference between Atomicity and Durability?

Durability and Atomicity are ensured by recovery techniques.

6

(7)

ACID PROPERTIES OF TRANSACTIONS

Isolation:

Even if the consistency and atomicity properties are ensured, concurrent transactions may result in an inconsistent database state.

If a second concurrently running transaction

calculates A+B after write(A) but before write(B).

What would be the result?

Such transactions may left the database in an inconsistent state even after both transactions have completed.

Isolation is ensured by concurrency control techniques.

7

(8)

T RANSACTION STATE

8

(9)

T RANSACTION STATE

Active, the initial state; the transaction stays in this state while it is executing.

Partially committed, after the final statement has been executed.

Failed, after the discovery that normal execution can no longer proceed.

Aborted, after the transaction has been rolled back and the database has been restored to its state prior to the start of the transaction. (Roll back is done either by a restart or kill).

Committed, after successful completion. 9

(10)

C ONCURRENCY

Achieving consistency in a concurrent environment is a complicated task.

One way to achieve this is to execute transactions serially.

(But then transactions would not be concurrent.)

However, concurrency provide certain benefits:

Improved throughput (number of transactions executed in a given amount of time) and resource utilization.

Reduced waiting time

There is always a trade-off between degree of concurrency and

associated cost. 10

(11)

C ONCURRENT EXECUTION SCENARIOS

Let Transaction T1 transfers $50 from account A to account B.

Transaction T2 transfers 10 percent of the balance from account A to account B.

11

(12)

C ONCURRENT EXECUTION SCENARIOS

Schedule- When transactions are executing concurrently in an interleaved fashion, the order of execution of

operations from all the various transactions is known as a

schedule.

If A=1000 and B = 2000

Final A = 855

Final B = 2145

A+B = 3000

It is serial schedule.

12

(13)

C ONCURRENT EXECUTION SCENARIOS

If A=1000 and B = 2000

Final A = 850

Final B = 2150

A+B = 3000

Is it a serial schedule?

Executing transactions serially may also produce different

results.

13

(14)

C ONCURRENT EXECUTION SCENARIOS

If A=1000 and B = 2000

Final A = 855

Final B = 2145

A+B = 3000

Is it a serial schedule?

Is it behave like a serial schedule?

14

(15)

C ONCURRENT EXECUTION SCENARIOS

If A=1000 and B = 2000

Final A = 950

Final B = 2100

A+B = 3050

Concurrent execution of transactions may or may not equivalent to a serial schedule.

An acceptable schedule (serializable schedule) is one which is equivalent to a serial schedule.

15

(16)

S ERIALIZABILITY

Serial transactions result in consistent database state.

We are looking for schedules which are equivalent to a serial schedule.

Two ways to ensure serializability in schedules having concurrent instructions:

Conflict serializability.

View serializability.

16

(17)

C ONVENTION

17

(18)

CONFLICT SERIALIZABILITY

Schedule S has two consecutive instructions, I and J , of transactions Ti and Tj , respectively (i≠ j).

If I and J refer to different data items, then we can swap I and J without affecting the results.

if I and J refer to the same data item Q, then the order of the two steps may matter.

Possible cases, if I and J refer to the same data item Q :

1. I = read(Q), J = read(Q).

2. I = read(Q), J = write(Q).

3. I = write(Q), J = read(Q).

4. I = write(Q), J = write(Q).

18

(19)

CONFLICT SERIALIZABILITY

Case 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 Ti and Tj , regardless of the order.

Case 2:

I = read(Q), J = write(Q).

If I comes before J , then Ti does not read the value of Q that is written by Tj in instruction J.

If J comes before I, then Ti reads the value of Q that is written by Tj.

Order matters.

19

(20)

CONFLICT SERIALIZABILITY

Case 3:

I = write(Q), J = read(Q).

The order of I and J matters for reasons similar as in Case 2.

Case 4:

I = write(Q), J = write(Q).

One write instruction will overwrite the other write instruction.

Only the latter of the two write instructions is preserved in the database and is used by next read instruction.

Order matters.

Take Away: write operation  Order is important. 20

(21)

CONFLICT SERIALIZABILITY

If either of I and J, from different transactions operating on same data set, is a write operation- order of I and J is important.

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.

If there is no conflict among I and J, we can achieve serializability.

A schedule is called conflict serializable if it can be

transformed into a serial schedule by swapping non-conflicting

operations. 21

(22)

E XAMPLE

22

A serial execution of transactions

(23)

CONFLICT SERIALIZABILITY

If a schedule S1 can be transformed into a schedule S2 by a series of swaps of non-conflicting instructions, we say that S1 and S2 are conflict equivalent.

23

(24)

CONFLICT SERIALIZABILITY

A schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

24

(25)

T ESTING OF CONFLICT SERIALIZABILITY

We need some method for determining conflict serializability of a schedule.

Precedence graph: A directed graph G = (V, E) where V denotes transactions in a schedule and set E has an edge between Ti →Tj if:

1. Ti executes write(Q) before Tj executes read(Q).

2. Ti executes read(Q) before Tj executes write(Q).

3. Ti executes write(Q) before Tj executes write(Q).

If there is a cycle in precedence graph, then that schedule is not conflict serializable.

25

(26)

E XAMPLE

26

(27)

E XAMPLE

27

(28)

EXAMPLE

28

(29)

TOPOLOGICAL SORTING

A serializability order of the transactions can be obtained by finding a linear order consistent with the precedence graph. This process is called topological sorting.

29

(30)

CONFLICT SERIALIZABILITY

A schedule might have a serial schedule which can not be identified by conflict serializability.

30

(31)

V IEW SERIALIZABILITY

Less stringent than conflict serializability.

Every conflict serializable schedule is also view serializable but the reverse is not true.

Two schedules S1 and S2 are view equivalent if:

For each data item Q, if Ti reads the initial value of Q in schedule S1, then transaction Ti must also read the initial value of Q in schedule S2.

For each data item Q, the transaction (if any) that performs the final write(Q) operation in schedule S1 must perform the final write(Q) operation in schedule S2.

For each data item Q, if Ti executes read(Q) in schedule S1, and if that value was produced by a write(Q) executed by transaction Tj, then the read(Q) of Ti must also read the value of Q that was

produced by the same write(Q) operation of Tj in schedule S2.

31

(32)

E XAMPLE

32

These schedules are not conflict equivalent but view equivalent.

A schedule S is view serializable if it is view equivalent to a serial schedule.

(33)

R ECOVERABILITY

So far, we have studied schedules while assuming there are no transaction failures.

If a transaction Ti fails, we need to undo the effect of this transaction to ensure the atomicity property of the

transaction.

Any transaction Tj that is dependent on Ti (i.e., Tj has read data written by Ti) is also aborted.

33

(34)

R ECOVERABLE AND IRRECOVERABLE SCHEDULES

If T6 fails before it commits, T7 must be

aborted. However, T7 has already committed and cannot be aborted.

This is an irrecoverable schedule.

If we commit T7 after T6 then it would be a recoverable schedule.

For each pair of transactions Ti and Tj, if Tj reads a data item previously written by Ti , the commit operation of Ti appears before the commit operation of Tj , then such a schedule is recoverable otherwise irrecoverable.

34

(35)

C ASCADING ROLLBACK

Even if a schedule is recoverable, a transaction failure may lead to roll back of several transactions.

Such a series of transaction rollbacks, is called cascading rollback.

Cascading rollback is undesirable.

35

(36)

C ASCADELESS S CHEDULE

Cascading rollback is undesirable.

Schedule that restrict cascading rollback is called Cascadeless Schedule.

For each pair of transactions Ti and Tj such that Tj reads a data item

previously written by Ti , the commit operation of Ti appears before the read operation of Tj.

36

References

Related documents

● Generalization Property : Let T be a relation, and P and Q be sets of  attributes in T such that D P  < D Q. 

Find the sending end voltage, current, power , power factor, efficiency and voltage regulation using exact transmission line

We seek an assignment such that (a) if the value of each data item is within its data accuracy bound at a coordinator then the value of each query is also within its accuracy bound,

On the right hand side of the ORS, using ONLY a black ink ballpoint pen, (i) darken the appropriate bubble under each digit of your registration number and (ii) write your

On the right hand side of the ORS, using ONLY a black ink ballpoint pen, (i) darken the appropriate bubble under each digit of your registration number and (ii) write your

However, in the case of the linked answer question pair, there will be negative marks only for wrong answer to the first question and no negative marks for wrong answer to the

q  Observations made some distance down the waveguide from the point source will see an oscillatory fringe pattern produced by this interference. q  As time passes the waves

In the theoretical framework that we use to understand the evolution of so- ciality, three factors, namely, genetic relatedness, ecological productivity and demographic population