Rdbms4.1

Unit-I		Unit-II	Unit-III	Unit-IV	Unit-V
Part-I	Part-II	Part-I	Part-I	Part-I	Total
Part-III	Part-IV	Part-II	Part-II	Part-II
Part-V		Part-III

 1.What is transaction ? Explain properties of a transaction?

Transaction

An action, or series of actions, carried out by a single user or Application program, that reads or updates the contents of the database.

·        A transaction is a logical unit of work on the database.

·        It may be an entire program, a part of a program, or a single statement (for example, the SQL statement INSERT or UPDATE).

·        It may involve any   number of operations on the database.

Example:

This simple transaction of moving an amount of 5000 from A to B .

This very simple and small transaction includes several steps: decrease A bank account 5000:

Open_Acc (A)

OldBal = A.bal

NewBal = OldBal - 5000

A.bal = NewBal

CloseAccount(A)

Simply you can say, the transaction involves many tasks, such as opening the account of A, reading the old balance, decreasing the specific amount 5000 from that account, saving new balance to an account of A and finally closing the transaction session.

For adding amount 5000 in B account the same sort of tasks needs to be done:

OpenAccount(B)

Old_Bal = B.bal

NewBal = OldBal + 5000

B.bal = NewBal

CloseAccount(B)

Properties Of Transactions

 

There are properties that all transactions should possess. The four basic, called ACID, properties

 

• Atomicity. This property states that each transaction must be considered as a single unit and must be completed fully or not completed at all. Database should be in a state either before the transaction execution or after the transaction execution. It should not be in a state ‘executing’.

 

• Consistency. A transaction must transform the database from one consistent state to another consistent state. It is the responsibility of both the DBMS and the application developers to ensure consistency. The DBMS can ensure consistency by enforcing integrity constraints.

 

For example, suppose that we have a transaction that is intended to transfer money from one bank account to another and the programmer makes an error in the transaction logic and debits one account but credits the wrong account; then the database is in an inconsistent state. The DBMS doesn’t have ability to detect the error.

 

• Isolation In a database system where more than one transaction are being executed simultaneously and in parallel, the property of isolation states that all the transactions will be carried out and executed as if it is the only transaction in the system. No transaction will affect the existence other transaction.

 

• Durability. The effects of a successfully completed (committed) transaction are permanently recorded in the database and must not be lost because of a subsequent failure. It is the responsibility of the recovery subsystem to ensure durability.

2.What are the various types of locks?

Locking Methods

 Locking

 A procedure used to control concurrent access to data. When one transaction is accessing the database, a lock may deny access to other transactions to prevent incorrect results.

Locking methods are the most widely used approach to ensure serializability of concurrent transactions.

 Shared lock

If a transaction has a shared lock on a data item, it can read the item but not update it. The read operations cannot conflict, it is permissible  for more than one transaction to hold shared locks simultaneously on the same item.

 Exclusive lock

If a transaction has an exclusive lock on a data item, it can both read and update the item. On the other hand, an exclusive lock gives a transaction exclusive access to that item. Thus, as long as a transaction holds the exclusive lock on the item, no other transactions can read or update that data item.

Locks are used in the following way:

• Any transaction that needs to access a data item must first lock the item, requests a shared lock for read-only access or an exclusive lock for both read and write access.

• If the item is not already locked by another transaction, the lock will be granted.

• If the item is currently locked, the DBMS determines whether the request is compatible with the existing lock. If a shared lock is requested on an item that already has a shared lock on it, the request will be granted; otherwise, the transaction must wait until the existing lock is released.

• A transaction continues to hold a lock until it explicitly releases it either during execution or when it terminates (aborts or commits).

 

In addition to these rules, some systems permit a transaction to issue a shared lock on an item and then later to upgrade the lock to an exclusive lock.

Some systems also permit a transaction to issue an exclusive lock and then later to downgrade the lock to a shared lock.

3.Explain 2 phase locking protocol?

To guarantee serializability, we must follow a protocol concerning the positioning of the lock and unlock operations in every transaction. The best known protocol is two-phase locking (2PL).

Two-phase locking (2PL)

According to the rules of this protocol, every transaction can be divided into two phases: first a growing phase, in which it acquires all the locks needed but cannot release any locks, and then a shrinking phase, in which it releases its locks but cannot acquire any new locks.

Normally, the transaction acquires some locks, does some processing ,and goes on to acquire additional locks as needed. However, it never releases any lock until it has reached a stage where no new locks are needed.

 

The rules are:

A transaction must acquire a lock on an item before operating on the item. The lock may be read or write, depending on the type of access needed.

• Once the transaction releases a lock, it can never acquire any new locks.

If upgrading of locks is allowed, upgrading can take place only during the growing phase and may require that the transaction wait until another transaction releases a shared lock on the item. Downgrading can take place only during the shrinking phase.

4.What is deadlock ? Explain deadlock prevention techniques?

 

Figure 17 Deadlock between two transactions.

Deadlock occurs when two or more transactions are waiting to access data the other transaction has locked.

The only way to break deadlock once it has occurred is to abort one or more of the transactions.

 

Figure 17 shows  two transactions, T₁₇ and T₁₈, that are deadlocked because each is waiting for the other to release a lock on an item it holds. At time t₂, transaction T₁₇ requests and obtains an exclusive lock on item bal_x and at time t₃ transaction T₁₈ obtains an exclusive lock on item bal_y. Then at t₆, T₁₇ requests an exclusive lock on item bal_y. Because T₁₈ holds a lock on bal_y, transaction T₁₇ waits. Meanwhile, at time t₇, T₁₈ requests a lock on item bal_x, which is held by transaction T₁₇. Neither transaction can continue, because each is waiting for a lock it cannot obtain until the other completes. Once deadlock occurs, the applications involved cannot resolve the problem. Instead, the DBMS has to recognize that deadlock exists and break the deadlock in some way.

Unfortunately, there is only one way to break deadlock: abort one or more of the transactions. In Figure we may decide to abort  transaction T₁₈. Once this is complete, the locks held by transaction T₁₈ are released and T₁₇ is able to continue again. Deadlock should be transparent to the user, so the DBMS should automatically restart the aborted transaction(s).

 

There are three general techniques for handling Deadlock:

1.     Timeouts

2.     Deadlock prevention

3.     Deadlock detection and recovery.

 

Timeouts

In this approach, a transaction that requests a lock will wait for only a system-defined period of time. If the lock has not been granted within this period, the lock request times out. In this case, the DBMS assumes that the transaction may be deadlocked, even though it may not be, and it aborts and automatically restarts the transaction.

 

Deadlock prevention

Two algorithms have been proposed by Rosenkrantz et al. (1978).

 

Wait-Die

If the transaction requesting the lock is the older of the two transactions, it will wait until the other transaction is completed and the locks are released.

 

• If the transaction requesting the lock is the younger of the two transactions, it will die (roll back) and is rescheduled using the same time stamp.

 In short, in the wait/die scheme, the older transaction waits for the younger to complete and release its locks

 

Wound-Wait

If the transaction requesting the lock is the older of the two transactions, it will preempt (wound) the younger transaction (by rolling it back). T1 preempts T2 when T1 rolls back T2. The younger, preempted transaction is rescheduled using the same time stamp.

 

• If the transaction requesting the lock is the younger of the two transactions, it will wait until the other transaction is completed and the locks are released.

 

In short, in the wound/wait scheme, the older transaction rolls back the younger transaction and reschedules it.

 

A variant of  2PL, called conservative 2PL, can also be used to prevent deadlock.

 

Deadlock detection

 

Deadlock detection is usually handled by the construction of a wait-for graph (WFG) that shows the transaction dependencies; that is, transaction T_i is dependent on T_j if transaction T_j holds the lock on a data item that T_i is waiting for.

The WFG is a directed graph G = (N, E) that consists of a set of nodes N and a set of directed edges E, which is constructed as follows:

 

• Create a node for each transaction.

• Create a directed edge T_i → T_j, if transaction T_i is waiting to lock an item that is currently locked by T_j.

Deadlock exists if and only if the WFG contains a cycle . In Figure Clearly, the graph has a cycle in it (T₁₇ → T₁₈ → T₁₇), so we can conclude that the system is in deadlock.

 

Frequency of deadlock detection

Because a cycle in the wait-for graph is a necessary and sufficient consdition for deadlock to exist, the deadlock detection algorithm generates the WFG at regular intervals and examines it for a cycle. The choice of time interval between executions of the algorithm is important. If the interval chosen is too small, deadlock detection will add considerable overhead; if the interval is too large, deadlock may not be detected for a long period. Alternatively, a dynamic deadlock detection algorithm could start with an initial interval size. Each time no deadlock is detected, the detection interval could be increased, for example, to twice the previous interval, and each time deadlock is detected, the interval could be  reduced, for example, to half the previous interval, subject to some upper and lower limits.

 

Recovery from deadlock detection

There are several issues that need to be considered:

 

(1) Choice of deadlock victim.

In some circumstances, the choice of transactions to abort may be obvious. However, in other situations, the choice may not be so clear.

In such cases this may take into consideration:

(a) How long the transaction has been running

(b) How many data items have been updated by the transaction

(c) How many data items the transaction is still to update

 

(2) How far to roll a transaction back.

It may be possible to resolve the deadlock by rolling back only part of the transaction.

(3) Avoiding starvation.

Starvation occurs when the same transaction is always chosen as the victim, and the transaction can never complete. The DBMS can avoid starvation by storing a count of the number of times a transaction has been selected as the victim and using a different selection criterion once this count reaches some upper limit.

5.Explain Optimistic concurrency control Techniques?

The optimistic approach is based on the assumption that the majority of the database operations do not conflict.

There are two or three phases to an optimistic concurrency control protocol, depending on whether it is a read-only or an update transaction:

 

Read phase:

The transaction reads the values of all data items it needs from the database and stores them in local variables. Updates are applied to a local copy of the data, not to the database itself.

 

Validation phase:

This follows the read phase. Checks are performed to ensure that serializability is not violated if the transaction updates are applied to the database.

For a read-only transaction, this consists of checking whether the data values read are still the current values for the corresponding data items. If no interference occurred, the transaction is committed. If interference occurred, the transaction is aborted and restarted.

For a transaction that has updates, validation consists of determining whether the current transaction leaves the database in a consistent state, with serializability maintained. If not, the transaction is aborted and needs to be restarted.

 

Write phase:

This follows the successful validation phase for update transactions. During this phase, the updates made to the local copy are applied to the database.

 

The validation phase examines the reads and writes of transactions that may cause interference. Each transaction  T is assigned a timestamp at the start of its execution, start(T); one at the start of its validation phase, validation(T); and one at its finish time, finish(T), including its write phase, if any.

To pass the validation test, one of the following must be true:

(1) All transactions S with earlier timestamps must have finished before transaction T started; that is, finish(S) < start(T).

(2) If transaction T starts before an earlier one S finishes, then:

(a) the set of data items written by the earlier transaction are not the ones read by the current transaction; and

(b) the earlier transaction completes its write phase before the current transaction enters its validation phase, that is, start(T) < finish(S)< validation(T).

Rule 2(a) guarantees that the writes of an earlier transaction are not read by the current transaction; rule 2(b) guarantees that the writes are done serially, ensuring no conflict.