TIME STAMP BASED PROTOCOL
THE TIMESTAMP ORDERING PROTOCOL IS A PROTOCOL USED TO SEQUENCE THE
TRANSACTIONS BASED ON THEIR TIMESTAMPS. THE SEQUENCE OF THE TRANSACTION
IS ALL ABOUT THE ARISING SEQUENCE OF THE TRANSACTION GENERATION. THE
TRANSACTIONS TAKE PART IN A SCHEDULE IS SUBSEQUENTLY SERIALIZABLE AND THE
TRANSACTIONS WHICH ARE IN THE ONLY CORRESPONDING SERIAL SCHEDULE
ALLOWED IN THE SEQUENCE OF THEIR TIMESTAMP VALUES. THE SCHEDULE IS
CORRESPONDING TO THE PARTICULAR SERIAL ORDER EQUIVALENT TO THE SEQUENCE
OF THE TRANSACTION TIMESTAMPS.
EXAMPLE
• THE OLDER TRANSACTION IS ALWAYS GIVEN PRIORITY IN THIS METHOD. IT USES
SYSTEM TIME TO DETERMINE THE TIME STAMP OF THE TRANSACTION. THIS IS THE
MOST COMMONLY USED CONCURRENCY PROTOCOL.
• LOCK-BASED PROTOCOLS HELP YOU TO MANAGE THE ORDER BETWEEN THE
CONFLICTING TRANSACTIONS WHEN THEY WILL EXECUTE. TIMESTAMP-BASED
PROTOCOLS MANAGE CONFLICTS AS SOON AS AN OPERATION IS CREATED.
• 1. CHECK THE FOLLOWING CONDITION WHENEVER A TRANSACTION TI ISSUES A READ (X) OPERATION:
• IF W_TS(X) >TS(TI) THEN THE OPERATION IS REJECTED.
• IF W_TS(X) <= TS(TI) THEN THE OPERATION IS EXECUTED.
• TIMESTAMPS OF ALL THE DATA ITEMS ARE UPDATED.
• 2. CHECK THE FOLLOWING CONDITION WHENEVER A TRANSACTION TI ISSUES A WRITE(X) OPERATION:
• IF TS(TI) < R_TS(X) THEN THE OPERATION IS REJECTED.
• IF TS(TI) < W_TS(X) THEN THE OPERATION IS REJECTED AND TI IS ROLLED BACK OTHERWISE THE OPERATION IS EXECUTED.
• WHERE, TS(TI) DENOTES THE TIMESTAMP OF THE TRANSACTION TI.
• R_TS(X) DENOTES THE READ TIME-STAMP OF DATA-ITEM X./LATEST READ STAMP
• W_TS(X) DENOTES THE WRITE TIME-STAMP OF DATA-ITEM X./LATEST WRITE STAMP
ADVANTAGES
SERIALIZABLE
DEADLOCK FREE
STARVATION MAY OCCUR
RECOVERY ALGORITHM
THE ENTIRE DBMS IS A VERY COMPLEX STRUCTURE WITH MULTIPLE TRANSACTIONS BEING
PERFORMED AND CARRIED OUT EVERY SECOND. THE TOUGHNESS AND STRENGTH OF A SYSTEM
DEPEND NOT ONLY ON THE COMPLEX AND SECURED ARCHITECTURE OF A SYSTEM BUT ALSO IN THE
WAY HOW DATA ARE MANAGED AND MAINTAINED IN THE WORST CASES. IF THE UNDERLYING
ARCHITECTURE FAILS OR CRASHES, THEN THERE MUST BE SOME TECHNIQUES AND PROCEDURES
BY WHICH THE LOST DATA DURING A TRANSACTION GETS RECOVERED.
IT IS THE METHOD OF RESTORING THE DATABASE TO ITS CORRECT STATE IN THE EVENT
OF A FAILURE AT THE TIME OF THE TRANSACTION OR AFTER THE END OF A PROCESS.
EARLIER, YOU HAVE BEEN GIVEN THE CONCEPT OF DATABASE RECOVERY AS A SERVICE
THAT SHOULD BE PROVIDED BY ALL THE DBMS FOR ENSURING THAT THE DATABASE IS
DEPENDABLE AND REMAINS IN A CONSISTENT STATE IN THE PRESENCE OF FAILURES.
REASONS OF DATA LOSS
FAILURE OF MAIN MEMORY, INCLUDING THAT DATABASE BUFFERS.
DUE TO HARDWARE OR SOFTWARE ERRORS, THE SYSTEM CRASHES
• NATURAL PHYSICAL DISASTERS CAN ALSO OCCUR, SUCH AS FIRES, FLOODS,
EARTHQUAKES, OR POWER FAILURES.
• CARELESSNESS OR UNINTENTIONAL DESTRUCTION OF DATA OR DIRECTORIES BY
OPERATORS OR USERS.
TYPES OF FAILURES
LOG BASED RECOVERY
THE LOG IS A SEQUENCE OF LOG RECORDS, RECORDING ALL THE UPDATE ACTIVITIES IN THE DATABASE. IN A STABLE
STORAGE, LOGS FOR EACH TRANSACTION ARE MAINTAINED. ANY OPERATION WHICH IS PERFORMED ON THE DATABASE IS
RECORDED IS ON THE LOG.
• AN UPDATE LOG RECORD REPRESENTED AS: <TI, XJ, V1, V2> HAS THESE FIELDS:
[Link] IDENTIFIER: UNIQUE IDENTIFIER OF THE TRANSACTION THAT PERFORMED THE WRITE OPERATION.
[Link] ITEM: UNIQUE IDENTIFIER OF THE DATA ITEM WRITTEN.
[Link] VALUE: VALUE OF DATA ITEM PRIOR TO WRITE.
[Link] VALUE: VALUE OF DATA ITEM AFTER WRITE OPERATION.
• WHEN THE TRANSACTION IS INITIATED, THEN IT WRITES 'START' LOG.
1.<TN, START>
• WHEN THE TRANSACTION MODIFIES THE CITY FROM 'NOIDA' TO 'BANGALORE', THEN
ANOTHER LOG IS WRITTEN TO THE FILE.
1.<TN, CITY, 'NOIDA', 'BANGALORE' >
• WHEN THE TRANSACTION IS FINISHED, THEN IT WRITES ANOTHER LOG TO INDICATE
THE END OF THE TRANSACTION.
1.<TN, COMMIT>
DEFERRED DATABASE MODIFICATION:
• THE DEFERRED MODIFICATION TECHNIQUE OCCURS IF THE TRANSACTION DOES
NOT MODIFY THE DATABASE UNTIL IT HAS COMMITTED.
• IN THIS
METHOD, ALL THE LOGS ARE CREATED AND STORED IN THE STABLE
STORAGE, AND THE DATABASE IS UPDATED WHEN A TRANSACTION COMMITS.
• R(A) <T1,START>
• A=A+100 <T1,A,200> RECOVERY MANAGER CHECKS LOG TO
CHECK IF COMMIT THEN REDO
• W(A)
• R(B) <T1,B,400>
• B=B+200 <T1,COMMIT>
• W(B)
INITIAL VALUES A =100
B =100
RECOVERY MANAGER CHECKS COMMIT IF COMMIT IS NOT THERE THEN IT WILL BE ROLLED BACK TO
PREVOIUS ROLLBACK OPERATION <REDO>
IMMEDIATE DATABASE MODIFICATION:
• THE IMMEDIATE MODIFICATION TECHNIQUE OCCURS IF DATABASE
MODIFICATION OCCURS WHILE THE TRANSACTION IS STILL ACTIVE.
• IN THIS TECHNIQUE, THE DATABASE IS MODIFIED IMMEDIATELY AFTER EVERY
OPERATION. IT FOLLOWS AN ACTUAL DATABASE MODIFICATION.
A=A+10 <T1, START>
W(A)…200…IMMEDIATE SAVING IN H/D NOT WAITING FOR COMMIT TO CHANGE
THE DATABASE <T1,A 100(OLD), 200(NEW)
R(B)
B=B+20 <T1,B.20.200>
W(B) <T1,COMMIT>
COMMIT
RECOVERY MANGER CHECKS LOG IF START AND COMMIT ARE THERE THEN
CORRESPONDING VALUES IN LOG WILL BE SAVED IN DATABASE IF VALUES ARE
THERE THEN SAME VALUES WILL BE OVER WRITTEN… REDO
IF COMMIT HAS NOT OCCURRED IN LOG ONLY START THEN UNDO ….ALSO CALLED
UNDO AND REDO
CHECKPOINT
• THE CHECKPOINT IS LIKE A BOOKMARK. WHILE THE EXECUTION OF THE TRANSACTION,
SUCH CHECKPOINTS ARE MARKED, AND THE TRANSACTION IS EXECUTED THEN USING THE
STEPS OF THE TRANSACTION, THE LOG FILES WILL BE CREATED.
• WHEN IT REACHES TO THE CHECKPOINT, THEN THE TRANSACTION WILL BE UPDATED INTO
THE DATABASE, AND TILL THAT POINT, THE ENTIRE LOG FILE WILL BE REMOVED FROM
THE FILE. THEN THE LOG FILE IS UPDATED WITH THE NEW STEP OF TRANSACTION TILL
NEXT CHECKPOINT AND SO ON.
• THE CHECKPOINT IS USED TO DECLARE A POINT BEFORE WHICH THE DBMS WAS IN THE
CONSISTENT STATE, AND ALL TRANSACTIONS WERE COMMITTED.
RECOVERY USING CHECKPOINT
• THE RECOVERY SYSTEM READS LOG FILES FROM THE END TO START. IT READS LOG FILES FROM T4 TO T1.
• RECOVERY SYSTEM MAINTAINS TWO LISTS, A REDO-LIST, AND AN UNDO-LIST.
• THE TRANSACTION IS PUT INTO REDO STATE IF THE RECOVERY SYSTEM SEES A LOG WITH <TN, START> AND <TN, COMMIT> OR
JUST <TN, COMMIT>. IN THE REDO-LIST AND THEIR PREVIOUS LIST, ALL THE TRANSACTIONS ARE REMOVED AND THEN REDONE
BEFORE SAVING THEIR LOGS.
• FOR EXAMPLE: IN THE LOG FILE, TRANSACTION T2 AND T3 WILL HAVE <TN, START> AND <TN, COMMIT>. THE T1 TRANSACTION
WILL HAVE ONLY <TN, COMMIT> IN THE LOG FILE. THAT'S WHY THE TRANSACTION IS COMMITTED AFTER THE CHECKPOINT IS
CROSSED. HENCE IT PUTS T1, T2 AND T3 TRANSACTION INTO REDO LIST.
• THE TRANSACTION IS PUT INTO UNDO STATE IF THE RECOVERY SYSTEM SEES A LOG WITH <TN, START> BUT NO COMMIT OR
ABORT LOG FOUND. IN THE UNDO-LIST, ALL THE TRANSACTIONS ARE UNDONE, AND THEIR LOGS ARE REMOVED.
• FOR EXAMPLE: TRANSACTION T4 WILL HAVE <TN, START>. SO T4 WILL BE PUT INTO UNDO LIST SINCE THIS TRANSACTION IS
NOT YET COMPLETE AND FAILED AMID.