Chapter 1: Basics, Transactions, Concurrency Control

Data

Facts and figures about an entity is called as Data (plural word, singular word is called Datum)

Data ≠ Information, Processed data is called information. Database is an organized collection of data.

DBMS

is the software that interacts with the end users, applications, and the database itself to capture and analyze the data. It encompasses the core facilities provided to the admin of the database. Sum total of this : DBMS

Problems with the file system

• Data Redundancy and inconsistency : Two spreadsheet containing the same data for example phone number. Change in one file will not change the value in the another file causing inconsistency.
• Data Isolation : Merging the order history and customer profile data can be troublesome.
• Atomicity : Not leaving the process in between, either 0 or 1.
• Concurrent Access Anomalies : IRCTC 🙂

Instance & Schemas

The collection of information stored in the database at a particular moment is called an instance of the database.

The overall design of the database is called the database schema.

Transaction

A transaction is a set of logically related instructions to perform a logical unit of work.

For preventing partial execution problem → Increase the level of atomicity and bundle all the instructions of operation into a unit called Transaction.

Desirable Properties of Transaction

• Atomicity → A transaction is an atomic unit of processing, either performed fully or not performed at all. 1 or 0. A transaction control manager / recovery control manager deals with it.
• Consistency → A transaction should be completely executed from beginning to end without interference from other transactions. It should take database from one consistent state to another. If A, I, D holds good, then this automatically holds good. So no separate manager that deals with it.
• Isolation → A transaction should appear as tho it is being executed in isolation even tho many transactions are executing concurrently. Concurrency Control Manager deals with it. Will only happen if one transaction does not impact other transaction.
• Durability → The changes made by the transaction must persist in the database. These changes must not be lost. Recovery control manager deals with it.

Transaction States

• Active State : Until the transaction is being executed.
• Partially Committed → Change is not directly to the “original database”, but a copy, data being flushed to the disk and → Committed.
• Failed State → During the execution, error occurs, so a “system failure” and transaction can no longer proceed. So Roll back the changes and → Aborted State reached.

In both the Aborted and Committed State, the data is always consistent.

Concurrent Execution

• Good database performance, less waiting time
• Overlapping I/O Activity

Problems

• Lost Update Problem → Two write operation on same value of different transactions. The second transaction commits early than the first so the first update gets lost. (Second transaction Blindly Writes)
• Dirty Read Problem → If the second transaction blindly reads before the first transaction updates or commits the value. The update gets lost and this is “Dirty Read”.
• Unrepeatable Read Problem → When a transaction tries to read a value of a data item twice and another transaction updates the value in between. The result of two reads will differ.
• Phantom Read Problem → If the second transaction deletes the value before the first transaction reads it again. Undefined variable name.

Schedules

When two or more transaction executed together or one after another then they can be bundled up into a higher unit of execution → Schedule

The order of instructions inside a transaction remains same.

Serial Schedule

One transaction runs full, then another, then another. No context switching. For a set of N transactions there are n! different serial schedules. Throughput of system is less in this case. Consistency Yes, Concurrency No.

Non-Serial Schedule

Sequence of transactions appear in the same order but individual instruction can be interleaved with the instructions of different transactions.

How many different combinations ?

• (N1 + N2)! → Total number of combination, but in this order is not maintained
• (N1 + N2)!/(N1! . N2!) → Total number of combinations in which order is also maintained

Deduct the N!…

Incomplete in the original notes: “Deduct the N!…” trails off here.

How to Swap / Interleave instructions ?

Finding Conflicting Group of instructions

• They must operate on the same data value
• Do not belong on the same transaction
• One of them must be a write operation

Just dont swap any conflicting group of instructions and you are good to go.

Conflict Serializability

If a non serializable schedule (which was interleaving instructions and context switching complex complex) can be configured in a way such that it becomes serializable (one by one) → Then it is called Conflict Serializability

Serializability brings in Consistency.

How To Find Conflict Serializability

First step is making that table out of the R4(x), R3(X) data. R4(X) → Read operation, transaction 4, on X.

Fill the table, then from that table, we have make the precedence graph, start with edges as transaction and check for conflicting pairs.

T4 has Read operation on 0second, T2 has write operation after it. Both on X, so these are conflicting pairs. Edge T4 → T2 added. Continue making this graph, if there is a cycle in this, then the schedule is not conflict serializable. Else find the topo sort of the graph.

Cycle detection is dfs so O(N**2)

View Serializable

skipped

Non-Recoverable Schedule

If a transaction reads a data which is prev written by another transaction and the commit operation of this read wala transaction comes before write wala transaction, then it can lead a non recoverable state. This will lead to Dirty Read and T2 (read wala) commits before T1 (write wala). So after T2 Commit agar error hua, T1 to rollback kardega, but T2 ? usne to commit kardiya.

But if the transaction that dirty reads commits after the T1, then it can also rollback in case T1 fails. In this case it is a Recoverable Schedule.

In this look the commit operation of each transaction and the dirty read of T2 and T3. So I case failure happends, T1 will rollback → then T2 will rollback → then T3 will rollback.

Data is consistent, every transaction is being rollbacked, but efficiency ?? A single Transaction failure leads to a series of transaction rollbacks also called, cascading rollback.

To avoid cascading rollback.

Strict Schedule

If write operation on X then no read or write operation will happen on X until the prev write operation is committed / abort.

Strict and Cascadeless focusses on the “Dirty Read Concept”

Concurrency Control

Time Stamp Order

Decide the order between the transaction before they enter in the system using a stamp (time stamp). No two processes can have the same time stamp.

No requirement of refreshing and starting with fresh value.

Time stamp of the transaction determines the serializability order, if TS of Ti < TS of Tj, then system must ensure that the produced schedule is equivalent to a serial schedule in which transaction Ti appears before the transaction Tj

Write/Read TimeStamp (Q) - The timestamp of the latest transaction which does the read/write operation on the data value Q. In other words; The largest timestamp of any transaction that execute read/write operation on the data value (Q) successfully. TS are updated when a new read / write instruction is executed.

If TS(Ti) Read < TS(Tj) Write, then Ti needs to read a value that will be overwritten by Tj. So Ti is rolled back. Inshort Read of Write ke baad mai aana hai.

If TS(Ti) ≥ TS(Tj), tab no problem. Read operation is executed and TS is set to max

THIS WAS READ - WRITE OPERATION ORDER

For Write Operation, This will collide with both Read and Write Both.

TimeStamp of mera Write operation > Another write and read operation, cuz im a senior operation

Lock Based Control

Do I need to explain this ? Nahhh

Two modes in this

• Shared Mode → If both the operations are read, and read read operation will never lead to clash. So both can read at the same time, hence shared mode.
• Exclusive Lock → No other transaction can read / write the value if there is an exclusive lock on the data value

Lock based protocol do not ensure the serializability,

• Two Phase Locking Protocol (2PL) - Each transaction issue locks and unlocks requests in two phases.
  • Growing Phase - in this phase the transaction may obtain locks, but will not release them.
  • Shrinking Phase - Release locks but no new lock will be obtained

Rigorous, Conservative, Strict 2PL dekh lena baad mai, I want to start the next topic now.

Not covered yet in the original notes: Rigorous, Conservative and Strict 2PL.