UNIT – 4

TOPIC

Unit-04/Lecture-01

TRANSACTION MANAGEMENT

Transactions is A sequence of many actions which are considered to be one atomic unit of work. Transacttion in DBMS uses following operations:

– Read, write, commit, abort

Each transaction has a unique starting point, some actions and one end point.A transaction is a unit of work which completes as a unit or fails as a unit.

Properties of transactions(ACID)

· Atomicity: All actions in the transaction happen, or none happen . in other words, An event either happens and is committed or fails and is rolled back. e.g. in a money transfer, debit one account, credit the other. Either both debiting and crediting operations succeed, or neither of them do. Transaction failure is called Abort. Commit and abort are irrevocable actions. There is no undo for these actions. An Abort undoes operations that have already been executed. For database operations, restore the data’s previous value from before the transaction (Rollback-it); a Rollback command will undo all actions taken since the last commit for that user. But some real world operations are not undoable. Examples - transfer money, print ticket, fire missile

· Consistency: If each transaction is consistent, and the DB starts consistent, it ends up consistent.Consistency preservation is a property of a transaction, not of the database mechanisms for controlling it (unlike the A, I, and D of ACID). If each transaction maintains consistency, then a serial execution of transactions does also. A database state consists of the complete set of data values in the database. A database state is consistent if the database obeys all the integrity constraint. A transaction brings the database from one consistent state to another consistent state.

· Isolation: Execution of one transaction is isolated from that of other transactions

· Durability: If a transaction commits, its effects persist.When a transaction commits, its results will survive failures (e.g. of the application, OS, DB system … even of the disk). Durability makes it possible for a transaction to be a legal contract. Implementation is usually via a log

– DB system writes all transaction updates to a log file. To commit, it adds a record “commit(Ti)” to the log.When the commit record is on disk, the transaction is committed.
Then system waits for disk acknowledgement before acknowledging to user. There can be five state of transactions:

1. Active: transaction is started and is issuing reads and writes to the database.

2. Partially committed: operations are done and values are ready to be written to the database.

3. Committed: writing to the database is permitted and successfully completed.

4. Abort: the transaction or the system detects a fatal error.

5. Terminated: transaction leaves the system.

A transaction reaches its commit point when all operations accessing the database are completed and the result has been recorded in the log. It then writes a [commit, ] and terminates
When a system failure occurs, search the log file for entries [start, ] and if there are no logged entries [commit, ]then undo all operations that have logged entries [write, , X, old_value, new_value]

Durability is hardware aspect while consistency programming aspect(programmer should design tables and write queries in such a way that consistency of database is maintained).

To guarantee ACID property following test are performed in DBMS. E.g.

Concurrency Control – Guarantees Consistency and Isolation, given Atomicity.
Logging and Recovery – Guarantees Atomicity and Durability.

Concurrency Control: concurrent transaction causes various problems if they run in uncontrolled manner. Consider two transactions T1 and T2 running concurrently then following problems may occur:

• Lost update

– Two transactions simultaneously update the same files

• Uncommitted update

– Transaction 2 uses the result updated by transaction 1

– Transaction 1 aborts and rolls back

– Transaction 2 commits

• Inconsistent Analysis

– Transaction 1 reads

– Transaction 2 reads and uses for calculation

– Transaction 1 updates and commits

Transaction 2 updates and commits

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	WHAT PROBLEMS OCCUR IN THE DATABASE WHEN TRANSACTIONS DO NOT SATISFY ACID PROPERTIES? EXPLAIN EXPLICITLY USING SUITABLE EXAMPLES.	DEC 2015	7

Unit-4/Lecture-02

Consider following two transactions on Bank Table:

T1	T2
Update bank set bal=3000 where accountno=10	Update bank set bal=4000 where accountno=10

If two transaction are valid and they executed serially(eighther<T1,T2> or <T2,T1> in above case) then system will always move from one valid state to another valid state. This type of execution is called serial execution and schedule is serial schedule.

A concurrent schedule is called serializable if it behaves like(or equivalent) serial schedule.

Consider following transaction T1 and T2

Read A

A=A+30

Write A

Read B

B=B-30

Write B

Read A

A=A*5

Write A

Read B

B=B/5

Write B

There are two possible serial schedule for above two transactions:

S1:<T1 ,T2> execute T1 first then T2

S1:<T2 ,T1> execute T2 first then T1

Letsanalyze these schedule, assume initially A is 100 and B is 200

S1:<T1 ,T2>	Initially	After T1	T2
Value of A	100	130	650
Value of B	200	170	34

S2:<T2 ,T1>	Initially	After T2	T1
Value of A	100	500	530
Value of B	200	40	10

These two schedules are not equivalent because T1 and T2 reads different value of A and B(in S1 ,transaction T1 reads value of A=100 and B=200, while in S2 it reads value of A=500 and B=40).

But these schedules are valid because they are serial. They always returns to a consistent state.

Now consider concurrent schedule S3 for transaction T1 and t2 in above example:

Read A

A=A+30

Write A

Read B

B=B-50

Write B

Read A

A=A*5

Write A

Read B

B=B / 5

Write B

Now analyze this using same initial values

S3	initially	After first half of T1	After first half of T2	After second half of T2	After second half of T2
Value of A	100	130	650
Value of B	200			170	34

This schedule is equivalent to the serial schedule S1( values of A and B read by T1 and T2 is same as in S1).

A schedule is called serializable if it is equivalent to a serial schedule. So S3 is serializable.

In other words ,if change in order of instruction in a serial schedule results in a concurrent schedule that exihibit same behavior as that serial schedule then concurrent schedule is serializable schedule.

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO	RGPV QUESTIONS	Year	Marks
Q.1

Unit-04/Lecture-03

Testing for serializability: There are two type of serializability.

1. Conflict serializability

2. View Serializability

Conflict Serializable: Conflict actions are the sequence of actions which should not be changed to maintain serializability for every data item. As in above example two transaction is concurrent and they are executing by interleaving there action but for data item A sequence T1--->T2 is maintained ,similarly for data item B sequence T1--->T2 is maintained. So all actions on data items are executing in sequence same as a serializable schedule. This schedule is conflict serializable.

There are two type of conflict that can occur in a schedule.

i. Read-Write conflict : A transaction T1 reads a data item (Let data item is A) then other transaction T2 write data item A (before data item A is written by T1) . So these two read-write actions are in conflict.

ii. write-read conflict : A transaction T1 writes a data item (Let data item is A) then other transaction T2 read data item A (before data item A is read by T1) . So these two write-read actions are in conflict

iii. Write-write conflict: A transaction T1 writes a data item (Let data item is A) then other transaction T2 write data item A (before data item A is read by T1) or vice versa. So these two read-write actions are in conflict.

Example: consider the following schedule S4

Read A

A=A+30

Write A

Read B

B=B-50

Write B

Read A

A=A*5

Write A

Read B

B=B / 5

Write B

In this schedule there are two conflicts only shown by arrows. Arrow indicate sequence in which actions are conflicting.

To find conflict we have to check from starting of schedule. pick a read/write action from the beginning of schedule then find write instruction next to it on that data item. If conflicting actions are in same transaction then do nothing (1 and 5 , 6 and 8). If conflicting actions are in different transactions then make an arrow from earlier to later action(3-5 and 8-10).

In this example(8-12) can be pair of conflict action but we have made arrow (8-10) where 10 is before 12 and in same transaction T2 so need not to make arrow for(8-12).

Conflict actions shows that if you make new schedule S5 swapping to actions of transactions in a schedule S4 but order of conflicting action(3-5, 5-9 and 8-10) remains same then new schedule S5 will be equivalent to S4.

Consider new S5 created by swapping some instructions in

Read A

A=A+30

Write A

Read B

B=B-50

Write B

Read A

A=A*5

Write A

Read B

B=B / 5

Write B

This schedule is equivalent to S4 since order of conflicting actions is same as S4.

To find whether a schedule is conflict serializable or not draw dependency graph. This graph is directed contains transactions as node and conflicting actions as edges(lables on edges can be given, label contains name off data item for which conflict occur). For S4 and S5 dependency graph would be:

If dependency graph contains cycle then schedule is not conflict serializable. This graph contains cycle so S4 and S5 is not conflict serializable.

If dependency graph does not contain cycle then we can find that schedule is equivalent to which serial schedule by using topological sort of dependency graph.

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

Unit-04/Lecture-04

Q33. Consider three data items D1, D2, and D3, and the following execution schedule of transactions T1,T2,and T3. In the diagram, R(D) and W(D) denotes the actions reading and writing the data item D respectively.

T1	T2	T3
	R(D3)
	R(D2)
	W(D2)
		R(D2)
		R(D3)
R(D1)
W(D1)
		W(D2)
		W(D3)
	R(D1)
R(D2)
W(D2)
	W(D1)

Which of the following statements is correct?

(A) The schedule is serializable as T2;T3;T1

(B) The schedule is serializable as T2;T1;T3

(D) The schedule is not serializable. CS2003

Ans. A

Explanation: If a schedule is conflict serializable then schedule is serializable. So first we apply conflict serializability test on schedule.

Step 1. Find all conflicts

T1	T2	T3
	R(D3)
	R(D2)
	W(D2)
		R(D2)
		R(D3)
R(D1)
W(D1)
		W(D2)
		W(D3)
	R(D1)
R(D2)
W(D2)
	W(D1)

Now draw dependency graph using these conflicts

T2

T3

T1

There is no cycle in dependency graph, so schedule is conflict serializable and order of serialization can be found using topological sort of graph which is T2;T3;T1;

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO	RGPV QUESTIONS	Year	Marks
Q.1

Unit-04/Lecture-05

DBMS - Concurrency Control

Locking-used to implement serialization and concurrently control practically.

there are two types of lock

(1) shared lock- it is applied when a transaction wants to only read data item. Multiple transaction can acquire shared lock simultaneously on same data item.

(2) exclusive lock- when transaction want to manipulate data it put exclusive lock. it can be acquired by single transaction at a time on a data item.

There are locking protocol which guide when to lock or unlock

2PL- 2 phase lock- transaction is divided in two phase.

(1) Growing phase-a transaction can acquire lock only when it is in this phase

àat start up transaction is in growing phase

(2) Shrinking phase- transaction cannot acquire lock in this phase.

àit start as soon as transaction unlock any data item

X(A)

A=A+30 growing phase

write(A)

X(B)

unlock(A)

read(B) Shrinking phase

B=B+30

write(B)

unlock(B

X(A)

A=A+30

Write A

X(B)

Unlock A

Read B

If(B<60)

rollback

X(A)

Read A

A=A+50

Write A

X(B)

Unlock(A)

Read B

B=B / 5

Write B

Unlock(B)

In this schedule if T1 is rollback(12) then T2 will be affected since it have read value of A written by T1. So T1 should also be rollbacked.

When one transaction causes other to rollback then this is called cascade rollback

Problems in 2PL

To avoid cascade rollback there is some modification done in 2PL and modified 2PL is called Strict 2PL.

All data item can be unlock at the end of transaction, so that interleaving of transaction are minimum(restrict concurrent execution to certain limit). This increases waiting time of other transactions.

In 2PL there is possibility of unrecoverable schedules in which one transaction read value of data item from an uncommitted transaction, manipulate the value and then commit itself. If that uncommitted transaction is rollbacked then value of data item written by transaction become invalid, but transaction have committed and value is stored on disk so no rollback can be performed on committed transaction. This type of transaction are called unrecoverable transaction.

In Strict 2PL there is no problem of unrecoverable transactions.

Note: Schedule in 2PL always satisfy conflict serializability, but there is problem of deadlock in both Simple 2Pl and Strict 2PL.

Deadlock: Consider following situation for two transaction T1 and T2

T1 T2

X(A)

X(B)

X(A)

. .

In this case T1 will wait for B and T2 will wait for A and this situation is called deadlock when two or more transaction are waiting for other transaction to unlock data item but no transaction can make any progress.

2PL is a pessimistic approach.

Optimistic approach- according to this approach do not lock any data item, since generally 99% transaction are on different data item. It allows all transaction to read and manipulate data but it has mechanism to detect inconsistencies. If inconsistencies occurred then rollback transactions. Example of optimistic approach is timestamp protocol.

UNIT 4/LECTURE 6

DBMS - Concurrency Control

Time stamp based protocols

The most commonly used concurrency protocol is time-stamp based protocol. This protocol uses either system time or logical counter to be used as a time-stamp.

Lock based protocols manage the order between conflicting pairs among transaction at the time of execution whereas time-stamp based protocols start working as soon as transaction is created.

Every transaction has a time-stamp associated with it and the ordering is determined by the age of the transaction. A transaction created at 0002 clock time would be older than all other transaction, which come after it. For example, any transaction 'y' entering the system at 0004 is two seconds younger and priority may be given to the older one.

In addition, every data item is given the latest read and write-timestamp. This lets the system know, when was last read and write operation made on the data item.

Time-stamp ordering protocol

The timestamp-ordering protocol ensures serializability among transaction in their conflicting read and write operations. This is the responsibility of the protocol system that the conflicting pair of tasks should be executed according to the timestamp values of the transactions.

· Time-stamp of Transaction Ti is denoted as TS(T_i).

· Read time-stamp of data-item X is denoted by R-timestamp(X).

· Write time-stamp of data-item X is denoted by W-timestamp(X).

Timestamp ordering protocol works as follows:

· If a transaction Ti issues read(X) operation:

o If TS(Ti) < W-timestamp(X)

§ Operation rejected.

o If TS(Ti) >= W-timestamp(X)

§ Operation executed.

o All data-item Timestamps updated.

· If a transaction Ti issues write(X) operation:

o If TS(Ti) < R-timestamp(X)

§ Operation rejected.

o If TS(Ti) < W-timestamp(X)

§ Operation rejected and Ti rolled back.

o Otherwise, operation executed.

Thomas' Write rule:

This rule states that in case of:

· If TS(Ti) < W-timestamp(X)

Operation rejected and Ti rolled back. Timestamp ordering rules can be
modified to make the schedule view serializable. Instead of making Ti rolled back, the 'write' operation itself is ignored.

UNIT 4/LECTURE 7

DBMS - Deadlock

in a multi-process system, deadlock is a situation, which arises in shared resource environment where a process indefinitely waits for a resource, which is held by some other process, which in turn waiting for a resource held by some other process.

For example, assume a set of transactions {T₀, T₁, T₂, ...,T_n}. T₀ needs a resource X to complete its task. Resource X is held by T₁ and T₁ is waiting for a resource Y, which is held by T₂. T₂ is waiting for resource Z, which is held by T₀. Thus, all processes wait for each other to release resources. In this situation, none of processes can finish their task. This situation is known as 'deadlock'.

Deadlock is not a good phenomenon for a healthy system. To keep system deadlock free few methods can be used. In case the system is stuck because of deadlock, either the transactions involved in deadlock are rolled back and restarted.

Deadlock Prevention

To prevent any deadlock situation in the system, the DBMS aggressively inspects all the operations which transactions are about to execute. DBMS inspects operations and analyze if they can create a deadlock situation. If it finds that a deadlock situation might occur then that transaction is never allowed to be executed.

There are deadlock prevention schemes, which uses time-stamp ordering mechanism of transactions in order to pre-decide a deadlock situation.

Wait-Die Scheme:

In this scheme, if a transaction request to lock a resource (data item), which is already held with conflicting lock by some other transaction, one of the two possibilities may occur:

· If TS(T_i) < TS(T_j), that is T_i, which is requesting a conflicting lock, is older than T_j, T_i is allowed to wait until the data-item is available.

· If TS(T_i) > TS(t_j), that is T_i is younger than T_j, T_i dies. T_i is restarted later with random delay but with same timestamp.

This scheme allows the older transaction to wait but kills the younger one.

Wound-Wait Scheme:

In this scheme, if a transaction request to lock a resource (data item), which is already held with conflicting lock by some other transaction, one of the two possibilities may occur:

· If TS(T_i) < TS(T_j), that is T_i, which is requesting a conflicting lock, is older than T_j, T_i forces T_j to be rolled back, that is T_i wounds T_j. T_j is restarted later with random delay but with same timestamp.

· If TS(T_i) > TS(T_j), that is T_i is younger than T_j, T_i is forced to wait until the resource is available.

This scheme, allows the younger transaction to wait but when an older transaction request an item held by younger one, the older transaction forces the younger one to abort and release the item.In both cases, transaction, which enters late in the system, is aborted.

Deadlock Avoidance

Aborting a transaction is not always a practical approach. Instead deadlock avoidance mechanisms can be used to detect any deadlock situation in advance. Methods like "wait-for graph" are available but for the system where transactions are light in weight and have hold on fewer instances of resource. In a bulky system deadlock prevention techniques may work well.

Wait-for Graph

This is a simple method available to track if any deadlock situation may arise. For each transaction entering in the system, a node is created. When transaction T_i requests for a lock on item, say X, which is held by some other transaction T_j, a directed edge is created from T_i to T_j. If T_j releases item X, the edge between them is dropped and T_i locks the data item.

The system maintains this wait-for graph for every transaction waiting for some data items held by others. System keeps checking if there's any cycle in the graph.

[Image: Wait-for Graph]

Two approaches can be used, first not to allow any request for an item, which is already locked by some other transaction. This is not always feasible and may cause starvation, where a transaction indefinitely waits for data item and can never acquire it. Second option is to roll back one of the transactions.

It is not feasible to always roll back the younger transaction, as it may be important than the older one. With help of some relative algorithm a transaction is chosen, which is to be aborted, this transaction is called victim and the process is known as victim selection.

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO	RGPV QUESTION	YEAR	MARKS

UNIT 4/LECTURE 8

DBMS - Data Backup

Failure with loss of Non-Volatile storage

What would happen if the non-volatile storage like RAM abruptly crashes? All transaction, which are being executed are kept in main memory. All active logs, disk buffers and related data is stored in non-volatile storage.

When storage like RAM fails, it takes away all the logs and active copy of database. It makes recovery almost impossible as everything to help recover is also lost. Following techniques may be adopted in case of loss of non-volatile storage.

· A mechanism like checkpoint can be adopted which makes the entire content of database be saved periodically.

· State of active database in non-volatile memory can be dumped onto stable storage periodically, which may also contain logs and active transactions and buffer blocks.

· <dump> can be marked on log file whenever the database contents are dumped from non-volatile memory to a stable one.

Recovery:

· When the system recovers from failure, it can restore the latest dump.

· It can maintain redo-list and undo-list as in checkpoints.

· It can recover the system by consulting undo-redo lists to restore the state of all transaction up to last checkpoint.

Database backup & recovery from catastrophic failure

So far we have not discovered any other planet in our solar system, which may have life on it, and our own earth is not that safe. In case of catastrophic failure like alien attack, the database administrator may still be forced to recover the database.

Remote backup, described next, is one of the solutions to save life. Alternatively, whole database backups can be taken on magnetic tapes and stored at a safer place. This backup can later be restored on a freshly installed database and bring it to the state at least at the point of backup.

Grown up databases are too large to be frequently backed-up. Instead, we are aware of techniques where we can restore a database by just looking at logs. So backup of logs at frequent rate is more feasible than the entire database. Database can be backed-up once a week and logs, being very small can be backed-up every day or as frequent as every hour

Remote Backup

Remote backup provides a sense of security and safety in case the primary location where the database is located gets destroyed. Remote backup can be offline or real-time and online. In case it is offline it is maintained manually.

[Image: Remote Data Backup]

Online backup systems are more real-time and lifesavers for database administrators and investors. An online backup system is a mechanism where every bit of real-time data is backed-up simultaneously at two distant place. One of them is directly connected to system and other one is kept at remote place as backup.

As soon as the primary database storage fails, the backup system sense the failure and switch the user system to the remote storage. Sometimes this is so instant the users even can't realize a failure.

UNIT 4/LECTURE 9

DBMS - Data Backup

Failure with loss of Non-Volatile storage

· A mechanism like checkpoint can be adopted which makes the entire content of database be saved periodically.

· State of active database in non-volatile memory can be dumped onto stable storage periodically, which may also contain logs and active transactions and buffer blocks.

· <dump> can be marked on log file whenever the database contents are dumped from non-volatile memory to a stable one.

Recovery:

· When the system recovers from failure, it can restore the latest dump.

· It can maintain redo-list and undo-list as in checkpoints.

· It can recover the system by consulting undo-redo lists to restore the state of all transaction up to last checkpoint.

Database backup & recovery from catastrophic failure

Remote Backup

[Image: Remote Data Backup]

DBMS - Data Recovery

Crash Recovery

Though we are living in highly technologically advanced era where hundreds of satellite monitor the earth and at every second billions of people are connected through information technology, failure is expected but not every time acceptable.

DBMS is highly complex system with hundreds of transactions being executed every second. Availability of DBMS depends on its complex architecture and underlying hardware or system software. If it fails or crashes amid transactions being executed, it is expected that the system would follow some sort of algorithm or techniques to recover from crashes or failures.

Failure Classification

To see where the problem has occurred we generalize the failure into various categories, as follows:

Transaction failure

When a transaction is failed to execute or it reaches a point after which it cannot be completed successfully it has to abort. This is called transaction failure. Where only few transaction or process are hurt.

Reason for transaction failure could be:

· Logical errors: where a transaction cannot complete because of it has some code error or any internal error condition

· System errors: where the database system itself terminates an active transaction because DBMS is not able to execute it or it has to stop because of some system condition. For example, in case of deadlock or resource unavailability systems aborts an active transaction.

System crash

There are problems, which are external to the system, which may cause the system to stop abruptly and cause the system to crash. For example interruption in power supply, failure of underlying hardware or software failure.

Examples may include operating system errors.

Disk failure:

In early days of technology evolution, it was a common problem where hard disk drives or storage drives used to fail frequently.

Disk failures include formation of bad sectors, unreachability to the disk, disk head crash or any other failure, which destroys all or part of disk storage

Storage Structure

We have already described storage system here. In brief, the storage structure can be divided in various categories:

· Volatile storage: As name suggests, this storage does not survive system crashes and mostly placed very closed to CPU by embedding them onto the chipset itself for examples: main memory, cache memory. They are fast but can store a small amount of information.

· Nonvolatile storage: These memories are made to survive system crashes. They are huge in data storage capacity but slower in accessibility. Examples may include, hard disks, magnetic tapes, flash memory, non-volatile (battery backed up) RAM.

Recovery and Atomicity

When a system crashes, it many have several transactions being executed and various files opened for them to modifying data items. As we know that transactions are made of various operations, which are atomic in nature. But according to ACID properties of DBMS, atomicity of transactions as a whole must be maintained that is, either all operations are executed or none.

When DBMS recovers from a crash it should maintain the following:

· It should check the states of all transactions, which were being executed.

· A transaction may be in the middle of some operation; DBMS must ensure the atomicity of transaction in this case.

· It should check whether the transaction can be completed now or needs to be rolled back.

· No transactions would be allowed to left DBMS in inconsistent state.

There are two types of techniques, which can help DBMS in recovering as well as maintaining the atomicity of transaction:

· Maintaining the logs of each transaction, and writing them onto some stable storage before actually modifying the database.

· Maintaining shadow paging, where are the changes are done on a volatile memory and later the actual database is updated.

Log-Based Recovery

Log is a sequence of records, which maintains the records of actions performed by a transaction. It is important that the logs are written prior to actual modification and stored on a stable storage media, which is failsafe.

Log based recovery works as follows:

· The log file is kept on stable storage media

· When a transaction enters the system and starts execution, it writes a log about it

<T_n, Start>

· When the transaction modifies an item X, it write logs as follows:

<T_n, X, V₁, V₂>

It reads Tn has changed the value of X, from V1 to V2.

· When transaction finishes, it logs:

<T_n, commit>

Database can be modified using two approaches:

1. Deferred database modification: All logs are written on to the stable storage and database is updated when transaction commits.

2. Immediate database modification: Each log follows an actual database modification. That is, database is modified immediately after every operation.

Recovery with concurrent transactions

When more than one transactions are being executed in parallel, the logs are interleaved. At the time of recovery it would become hard for recovery system to backtrack all logs, and then start recovering. To ease this situation most modern DBMS use the concept of 'checkpoints'.

Checkpoint

Keeping and maintaining logs in real time and in real environment may fill out all the memory space available in the system. At time passes log file may be too big to be handled at all. Checkpoint is a mechanism where all the previous logs are removed from the system and stored permanently in storage disk. Checkpoint declares a point before which the DBMS was in consistent state and all the transactions were committed.

Recovery

When system with concurrent transaction crashes and recovers, it does behave in the following manner:

[Image: Recovery with concurrent transactions]

· The recovery system reads the logs backwards from the end to the last Checkpoint.

· It maintains two lists, undo-list and redo-list.

· If the recovery system sees a log with <T_n, Start> and <T_n, Commit> or just <T_n, Commit>, it puts the transaction in redo-list.

· If the recovery system sees a log with <T_n, Start> but no commit or abort log found, it puts the transaction in undo-list.

All transactions in undo-list are then undone and their logs are removed. All transaction in redo-list, their previous logs are removed and then redone again and log saved.

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1.

Setting of page

1. Page no. at top in the center.

2. Theme font -Calibri

3. Main text font size-12

4. All headings in bold (12)

5. Top centre headings font size-14

6. Page A-4 size

7. Header and footer -0

8. margin -left (1.25), right (1)

9. Line spacing-1.00