01-Description of the Transport Layer.ppt

Description of the Transport layer and their protocols

1. 1
Unit –4
Transaction Processing System
Transaction processing systems are the systems, which includes large size
database and allows many users to use same database concurrently.
Atransaction processsystem (TPS) is an informationprocessingsystem
for businesstransactionsinvolving the collection, modification and retrieval of
alltransaction data. Characteristics of a TPS include performance, reliability
and consistency.
Examples:
1.Railway Reservation System
2.Banking System
3.User Database based website etc.

2. 2
Transaction System
Collection of operation that form of single logical unit of work are called
transaction.
A Transactionis a unit of program execution that accesses and possibly
updates various data items.
Transaction access data using two operations:
Read (X): Which transfers the data item (X) from the database to
local bufferbelong to the transaction that executed the read
operation.
Write (X) : Which transfers the data item (X) from the local buffer of
the transactionthat executed the write back to the database.

3. 3
Transaction System
Ex. transaction to transfer $50 from account A to account B:
1.read(A)
2.A:= A –50
3.write(A)
4.read(B)
5.B:= B + 50
6.write(B)
Two main issues to deal with:
Failures of various kinds, such as hardware failures and system crashes
Concurrent execution of multiple transactions

4. 4
Properties of Transaction
Transaction have four basic properties, which are called ACID properties.
These properties are closely related to each other.
AAtomicity: a transaction is an atomic unit of processing and it is either
performed entirely or not at all.
CConsistency: a transaction's correct execution must take the database from
one correct state to another
IIsolation/Independence:the updates of a transaction must not be made
visible to other transactions until it is committed (solves the temporary
update problem)
DDurability(or Permanency): if a transaction changes the database and is
committed, the changes must never be lost because of subsequent failure

5. 5
ACID Properties Examples
Transaction to transfer $50 from account A to account B:
1.read(A)
2.A:= A –50
3.write(A)
4.read(B)
5.B:= B + 50
6.write(B)
Atomicity requirement
if the transaction fails after step 3 and before step 6, money will be “lost” leading to an
inconsistent database state. Failure could be due to software or hardware.
the system should ensure that updates of a partially executed transaction are not
reflected in the database.
Durability requirement—once the user has been notified that the transaction has
completed (i.e., the transfer of the $50 has taken place), the updates to the database by the
transaction must carry on even if there are software or hardware failures.

6. 6
ACID Properties Examples
Consistency requirement:
In general, consistency requirements include integrity constraints such
as primary keys and foreign keys and sum of balances of all accounts
etc.
A transaction must be a consistent database.
During transaction execution the database may be temporarily
inconsistent.
When the transaction completes successfully the database must be
consistent
invalid transaction logic can lead to inconsistency

7. 7
ACID Properties Examples
Isolation requirement—if between steps 3 and 6, another transaction
T2 is allowed to access the partially updated database, it will see an
inconsistent database.
T1 T2
1.read(A)
2.A:= A –50
3.write(A)
read(A), read(B), print(A+B)
4.read(B)
5.B:= B + 50
6.write(B )
Isolation can be ensured trivially by running transactions serially
that is, one after the other.
However, executing multiple transactions concurrently has significant
benefits, as we will see later.

8. 8
Transaction State

9. 9
Transaction 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 restored to
its state prior to the start of the transaction. Two options after it has been aborted:
restart the transaction
can be done only if no internal logical error
kill the transaction
Committed–after successful completion.

10. 10
Recovery from Transaction Failures
A recovery process is an integral part of a database system, which is responsible
for system failure. The system failure may be several cause :
•Computer Failure (system crash)
•A transaction or system error
•Local errors or exception conditions detected by the transaction
•Concurrency control enforcement
•Disk failure and Physical component problems
There are various techniques of recovery:
•Cascading Rollback
•Recoverable Schedules
•Log Based Recovery
•Checkpoints
•Shadow Paging
•Backup Mechanism

11. 11
Cascading Rollback
The event, in which a single transaction failure leads to a series of transaction
rollback is known as Cascading Rollback.
Example: Transaction T
1, write a value of Z, that is read by transaction T
2.
Transaction T
2, write a value of Z, that is read by transaction T
3.
Suppose that, at this point T
1fails, T
1must be rolled back. Since T
2is dependent
on T
1.T
2 must be rollback. Since T
3 is dependent on T
2. T
3must also be rolled back.
T
1 T
2 T
3
Read (X)
Read (Y)
Z = X + Y
Write (Z)
Read (Z)
Write Z)
Read (Z)

12. 12
Log Based Recovery
To keep track of the database transactions, the DBMS maintains special file called
log files that contain information about all updates.
The log file contains information like Transaction Identifier, Data Item Identifier,
Old Value and New Value etc.
The information contained in the log files are critical for the database recovery, two
separate copies are maintained.
In the past the log files were stored on magnetic tape. But nowadays, DBMS are
expected to recover from minor failures very quickly so that log files are stored
online on a fast Direct Access Storage Devices (DASD).
The log file are periodically archived and are stored in off-line storage. These log
files are called “Archive Log File”

13. 13
Checkpoints
A checkpoints is a point of synchronization between the database and the
transaction log file. All buffers are force written to secondary storage at
the checkpoint.
Checkpoints are also called save points .
Checkpoints are schedules at pre determined interval and involves
operation like writing all log records in main memory to secondary storage.
If the transaction are executed serially, when a failure occurs, we check
the log file to find the transaction that started before the last checkpoint.

14. 14
Backup Mechanism
The backup copy of the database can be used to recover the
database in the event that the database has been damaged or
destroyed.
A backup can be a complete copy of the entire database or an
incremental copy.
An incremental backup consists only of modifications made
since the last complete transaction.

15. 15
Shadow Paging
The shadow paging scheme does not require the use of log file in a single user
environment, though a log is needed in multi users environment for concurrency
control.
Shadow paging considers the database to be made up of a number of fixed size
disk pages or disk blocks for recovery purposes.
The shadow paging technique maintain two directories during the transaction
current directory and shadow directory.
When the transaction starts, the two directories are the same. The shadow
directory is saved to the disk and the current directory is used by the transaction.
The shadow directory is never changed and is used to restore the database in case
of a failure. During the transaction execution, the shadow directory is never
modified.

16. 16
Distributed Database System (DDBMS) is a collection of data with
different parts under the control of separate DBMSs running on
different computers.
These computers are connected together and communicate with
one another through various communication techniques.
DDBMS can handle both local and global transactions.
The main difference between centralized and distributed database
system is that, in the former, the data exist in single location, but in
the later, the data exist in various locations.
Distributed Database

17. 17
Fig. Distributed Database between MFG./Sales/HQ

18. 18
DDBMS allows each client/ site to store and maintain its own database,
causing immediate and efficient access to data.
It allows to access the data stored at remote sites. At the same time
users can retain the control to its own client/ site to access the local data.
If one site is not working due to any reason, the system will not be down
because other client/ site of the network can possible continue
functioning.
New client/ site can be added to the system any time.
If a user need to access the data from multiple clients/sites then the
desired query can be subdivided into sub queries.
Advantage of Distributed Database

19. 19
Complex software is required for a Distributed Database
System (DDBMS)
Distributed Database System (DDBMS) technology are s
expensive.
DDBMS based on communication and server-client
technology.
At the same time multiple queries from one client to another
clients may be slow.
Disadvantage of Distributed Database

20. 20
Data Fragmentation is method in which different relations of a
relational database system can be sub-divided and distributed
among network sites/clients.
For example, suppose we have a relation S and it is fragmented, it
means it is divided sub into-sets S1,S2,…..Sn
There are three type fragmentation:
1. Horizontal Fragmentation
2. Vertical Fragmentation
3. Mixed Fragmentation
Data Fragmentation

21. 21
In Horizontal fragmentation records of a relation are divided into number of
subsets.
For example, consider a relation Packing as shown in figure below. This
relation can be divided into n different fragments, each of which records
belong to a particular Packing house no. If above relation has two packing
house no 1 and 2, then there may be two fragments.
Horizontal Fragmentation
Date CartoonNo. Make/Type Weight
(Kg.)
Packing
House no
18/04/2104123 BCF 95 1
18/04/2104124 FDY 98 1
18/04/2104125 POY 102 2
18/04/2104126 POY 103 2
18/04/2104127 BCF 110 2
18/04/2104128 FDY 112 2
Table :Packing

22. 22
These two fragments are shown below in pack1 and pack2 and can now be stored in
different networks.
Pack1 = σ
Packing_house_no= “1” (packing)
Horizontal Fragmentation
Table :Pack1
Date CartoonNo. Make/Type Weight
(Kg.)
Packing
House no
18/04/2014125 POY 102 2
18/04/2014126 POY 103 2
18/04/2014127 BCF 110 2
18/04/2014128 FDY 112 2
Pack2 = σ
Packing_house_no= “2” (packing)
Table :Pack2
The reconstruction of relation packing can be obtained by taking the union of all
fragmentation i.e, Packing = Pack1 UPack2
Date CartoonNo. Make/Type Weight
(Kg.)
Packing
House no
18/04/2014123 BCF 95 1
18/04/2014124 FDY 98 1

23. 23
Vertical fragmentation is very similar to horizontal fragmentation. In vertical
fragmentation attributes/ fields are divided into numbers of subsets.
Vertical fragmentation is accomplished by adding a special attribute called
Desp. A despis a logical value for every record.
Vertical Fragmentation
Date Cartoon
No.
Make/Type Weight (Kg.)Packing
House no
Desp
18/04/2014 123 BCF 95 1 T
18/04/2014 124 FDY 98 1 F
18/04/2014 125 POY 102 2 F
18/04/2014 126 POY 103 2 T
18/04/2014 127 BCF 110 2 T
18/04/2014 128 FDY 112 2 F
Table :Packing

24. 24
These two vertical fragments are shown below in pack1 and pack2 and can
now be stored in different networks.
Pack1 = Π
date,cartoon_no, make, weight(packing)
Vertical Fragmentation
Table :Pack1
Date Cartoon
No.
Make/Type Weight (Kg.)
18/04/2014 123 BCF 95
18/04/2014 124 FDY 98
18/04/2014 125 POY 102
18/04/2014 126 POY 103
18/04/2014 127 BCF 110
18/04/2014 128 FDY 112

25. 25
Pack2 = Π
date,cartoon,desp(packing)
Vertical Fragmentation
Table :Pack2
Date Cartoon
No.
Desp
18/04/2014 123 T
18/04/2014 124 F
18/04/2014 125 F
18/04/2014 126 T
18/04/2014 127 T
18/04/2014 128 F
To reconstruct the original packing relation from the fragments, we join
different individual fragments i.e. Packing = Pack1 X Pack2

26. 26
It is the combination of both horizontal and vertical fragmentation
For example, mixed fragmentation is:
Π
date,packing_house_no(σ
weight > 100(packing))
Mixed Fragmentation
Table :Mix_PackDate Packing
House no
18/04/2014 2
18/04/2014 2
18/04/2014 2
18/04/2014 2

27. 27
Weknowthattransactionsaresetofinstructionsandtheseinstructions
performoperationsondatabase.Whenmultipletransactionsare
runningconcurrentlythenthereneedstobeasequenceinwhichthe
operationsareperformedbecauseatatimeonlyoneoperationcanbe
performedonthedatabase.Thissequenceofoperationsisknown
asSchedule.Bankingtransactionsystemisthebestexampleof
scheduling.ThevarioustypeofSchedulesare:
1.SerialSchedules
2.NonSerialSchedules
3.ConflictSchedules
4.ViewSchedules
Schedules

28. Types of Schedules
28

29. 29
TwoschedulesAandBarecalledserialscheduleiftheoperationsofeach
transactionareexecutedconsecutively,withoutanyinterleavedoperationfrom
theothertransaction.
Inaserialschedule,entiretransactionreperformedinserialorderT1andthen
T2orT2andthenT1.
Serial SchedulesT1: T2:
read_item(X);
X:= X - N;
write_item(X);
read_item(Y);
Y:=Y + N;
write_item(Y);
read_item(X);
X:= X + M;
write_item(X); T1: T2:
read_item(X);
X:= X + M;
write_item(X);
read_item(X);
X:= X - N;
write_item(X);
read_item(Y);
Y:=Y + N;
write_item(Y);
Schedule A Schedule B

30. 30
TwoschedulesCandDarecallednon-serialscheduleiftheoperationsofeach
transactionareexecutednon-consecutivelywithinterleavedoperationfromthe
othertransaction.
Non-Serial SchedulesT1: T2:
read_item(X);
X:= X - N;
read_item(X);
X:= X + M;
write_item(X);
read_item(Y);
write_item(X);
Y:=Y + N;
write_item(Y); T1: T2:
read_item(X);
X:= X - N;
write_item(X);
read_item(X);
X:= X + M;
write_item(X);
read_item(Y);
Y:=Y + N;
write_item(Y);
Schedule C Schedule D

31. 31
ConsiderascheduleSinwhichtherearetwoconsecutiveinstructionsI
iandI
j
ofthetransactionsT
iandT
jrespectively.
Nowweidentifiedthreerulesthatshowthatiftwooperationsinaschedule
satisfyallthesethreeconditionthenoperationsaresaidtoconflict.
1.Theybelongtodifferenttransactions.
2.Theyaccessthesamedataitem.
3.Atleastoneoftheoperationsisawrite-item.
Ifgraphcontainsacycle,henceitisnotconflictserializable
Conflict Schedules

32. 32
A schedule is called conflict serializability if after swapping of non-conflicting operations,
it can transform into a serial schedule. The schedule will be a conflict serializable if it is
conflict equivalent to a serial schedule.
Conflicting Operations : The two operations become conflicting if all conditions satisfy:
•Both belong to separate transactions.
•They have the same data item.
•They contain at least one write operation
Example: Swapping is possible only if S1 and S2 are logically equal.
Conflict Serializable Schedule
Here, S1 = S2. That means it is non-conflict.

33. 33
Conflict Serializable Schedule
Here, S1 ≠ S2. That means it is conflict.

34. 34
Conflict Equivalent
In the conflict equivalent, one can be transformed to another by swapping non-conflicting
operations. In the given example, S2 is conflict equivalent to S1 (S1 can be converted to S2 by
swapping non-conflicting operations).
Two schedules are said to be conflict equivalent if and only if:
1.They contain the same set of the transaction.
2.If each pair of conflict operations are ordered in the same way
Example:
Schedule S2 is a serial schedule because, in this, all operations of T1 are performed before starting
any operation of T2. Schedule S1 can be transformed into a serial schedule by swapping non-
conflicting operations of S1.

35. 35
Conflict Equivalent
T1 T2
Read(A)
Write(A)
Read(B)
Write(B)
Read(A)
Write(A)
Read(B)
Write(B)
After swapping of non-conflict operations, the schedule S1 becomes:
Since, S1 is conflict serializable.

36. 36
Fortestingofserializabilitythesimpleandefficientmethodisto
constructagraph,calledprecedencegraphG.
G=(V,E)
Thesetofverticesconsistsofallthetransactionparticipatingin
theschedule.ThesetofedgesconsistsofalledgesT
i>T
jfor
whichoneofthreeconditionholds:
1.T
iexecuteswrite(Q)beforeT
jexecutesread(Q)
2.T
iexecutesread(Q)beforeT
jexecuteswrite(Q)
3.T
iexecuteswrite(Q)beforeT
jexecuteswrite(Q)
Testing of Serializability

37. 37
Example:
Testing of Serializability
T1
Read (A)
A : A -50
T2
Read (A)
Temp : A * 0.1
A : A-temp
Write (A)
Read (B)
Write (A)
Read (B)
B : B + 50
Write (B)
B : B + temp
Write (B)
Precedence graph for above schedule and graph contains a cycle,
hence it is not conflict serializable.

38. Check whether the given schedule S is conflict serializable or not. If yes, then
determine all the possible serialized schedules
38

39. Step-01:
List all the conflicting operations and determine the dependency between
the transactions-
• R4(A) , W2(A) (T4 → T2)
• R3(A) , W2(A) (T3 → T2)
• W1(B) , R3(B) (T1 → T3)
• W1(B) , W2(B) (T1 → T2)
• R3(B) , W2(B) (T3 → T2)
Step-02:
Draw the precedence graph-
39

40. 40
View Schedules
View Serializability is a process to find out that a givenscheduleis view serializable
or not. To check whether a given schedule is view serializable, we need to check
whether the given schedule isView Equivalentto its serial schedule.
If a schedule is view equivalent to its serial schedule then the given schedule is
said to be View Serializable. Lets take an example.

41. 41
View Schedules
Lets check the three conditions of view serializability:
Initial Read
In schedule S1, transaction T1 first reads the data item X. In S2 also transaction T1 first reads the data item X.
Lets check for Y. In schedule S1, transaction T1 first reads the data item Y. In S2 also the first read operation on Y
is performed by T1.
We checked for both data items X & Y and theinitial readcondition is satisfied in S1 & S2.
Final Write
In schedule S1, the final write operation on X is done by transaction T2. In S2 also transaction T2 performs the
final write on X.
Lets check for Y. In schedule S1, the final write operation on Y is done by transaction T2. In schedule S2, final
write on Y is done by T2.
We checked for both data items X & Y and thefinal writecondition is satisfied in S1 & S2.
Update Read
In S1, transaction T2 reads the value of X, written by T1. In S2, the same transaction T2 reads the X after it is
written by T1.
In S1, transaction T2 reads the value of Y, written by T1. In S2, the same transaction T2 reads the value of Y after
it is updated by T1.
The update read condition is also satisfied for both the schedules.
Result:Since all the three conditions that checks whether the two schedules are view equivalent are satisfied in
this example, which means S1 and S2 are view equivalent. Also, as we know that the schedule S2 is the serial
schedule of S1, thus we can say that the schedule S1 is view serializable schedule.

42. View Serializable
View Equivalent Schedules-
Consider two schedules S1 and S2 each consisting of two transactions T1 and
T2.
Condition-01:
For each data item X, if transaction T
ireads X from the database initially in
schedule S1, then in schedule S2 also,T
imust perform the initial read of X
from the database.
Condition-02:
If transactionT
ireads a data item that has been updated by the transaction
T
jin schedule S1, then in schedule S2 also, transaction T
imust read the same
data item that has been updated by the transaction T
j.
Condition-03:
For each data item X, if X has been updated at last by transactionT
iin
schedule S1, then in schedule S2 also, X must be updated at last by
transactionT
i.
42

43. View Serializable
43