Transaction Management/transactSQL Flashcards
What are transactions and what causes complications to arise?
A series of queries. The complication arises from that many might happen at the same time (concurrency) and that computers can fail (partial execution)
What can concurrency lead to?
- Inconsistent data in the database
- (for example two people being able to book the same seat in a cinema or the following person overriding the first person’s booking)
What are transactions?
- They state that a group of SQL statements must be executed together so that no conflicts arise
- Transactions mean that specific events have to happen before another event
- meaning that we can’t for example have two people book the same seat as we’ll have a transaction that means once the seat has been picked, another person can’t pick it.
how do we ensure serialisable behaviour?
- By telling a DBMS that a sequence of SQL statements forms a transaction.
- It then knows that the transaction is to be executed as if in isolation from all other transactions
What is partial execution?
- Partial execution is when only part of a transaction gets carried out
- This could happen due to a failure or a power outage
How do DBMSs deal with partial execution?
- Transactions make sure that the whole set of instructions in a transaction is carried out otherwise the actions done are dropped/not permanently implemented. Either none or all of the commands are done.
How do we state in SQL that a transaction should be executed as a whole or not at all?
Using the keywords ‘START TRANSACTION’ and ‘COMMIT’
What do we do if we have to abort a transaction due to partial execution due to a failure?
Use the keyword ROLLBACK - if something fails and you don’t want any of the transaction to happen.
Why can we ignore operations such a calculations when looking at transactions?
- Because the OS does those operations
What does read(X) do?
- reads a database item X into a program variable (also named x for simplicity)
- finds address of disk block that contains item x
- copies that disk block into a buffer in main memory
- copy item x from buffer to program variable
What does write(x)
- finds address of disk block that contains item x
- copies that disk block into a buffer in main memory
- the program copies the new value into the correct location of item x in the buffer
- either immediately or some time after it writes the item in the bugger to the correct disk block
What is a schedule?
- a bunch of transactions in a specific order
What are the two main types of schedules?
- Serial schedules: executes transactions one after another
- Concurrent schedules: interleaves operations from different transactions, while still preserving that the operation in each transaction happen in the right order
What do each of the symbols represent?
Sn = id of the schedule
ri(x) = read(x) in transaction i
wi(x) = write(x) in transaction i
ci = commit in transaction i
ai = abort (“rollback”) in transaction i
Does order matter in serial schedules?
Yes because the data stored in shared variables between transactions can be different depending on transaction order
what is true about serial and concurrent schedules?
- All serial schedules are concurrent schedules
- But not all concurrent schedules are serial schedules
When is something not a concurrent schedule?
- When the order of the SQL statements inside the same transaction are executed out of order
Why can it be a problem that two transactions are not isolated from each other?
How can we solve this?
- issue of concurrent access
- if two transaction are accessing the same item then the outcome can be inconsistent with the real world.
- can solve this by undoing the second transaction
What does it mean for a transaction should be atomic?
the transaction is indivisible
Why can it be a problem if there’s a failure in the middle of a transaction?
How can we solve this?
- issue of partial execution
- leads to inconsistencies in the real world
- can solve by just undoing the transaction when the computer comes back online
What is durability?
That any later changes did not disappear after having finished based on something someone else did in the database
- so one transaction did not incorrectly overwrite an item that another one wrote to previously
What do we use to make ensure that we’re never in the situation of having errors made due to a failure (partial execution) and concurrent access?
ACID
What are the properties of ACID?
- A: Atomicity C: Consistency I: Isolation D: Durability
What is atomicity?
A transaction is an atomic unit of processing
- an indivisible unit of execution
- executed in it’s entirety or not at all
Deals with failure by aborting a transaction
- we undo the word done up to the error point
- system recreates state of database before start of aborted transaction
Commit - no errors, entire transaction is executed, system is updated appropriately
What is consistency?
- correct execution of a transaction takes the database from one consistent state to another
- when transactions don’t violate any constraints
- database accurately reflects state of real world
- if we have to abort then the database is not in a consistent state and we have to recreate the consistent state (which is the state of the database before the aborted transaction started)
Why are serial schedules consistent?
- A serializable schedule always leaves the database in a consistent state. A serial schedule is always a serializable schedule because, in a serial Schedule, a transaction only starts when the other transaction has finished execution
What are serialisable schedules?
schedules that are equivalent to serial schedules
(though there are multiple definitions of serialisability)
What is isolation?
- a particular transaction should see itself as the only transaction in the database
- the levels of isolation refer to how isolated a transaction should be from other transactions operations (such as modifying items used in both)
What are the levels of isolation
- Read uncommitted
- read committed
- Repeatable read
- serialisable
What is the read uncommitted isolation level?
- No isolation at all, you can read data which has not been committed
What is the read committed isolation level?
- every item you read must have been committed before you can see it
What is the repeatable read isolation level?
- every item you read must have been committed before you can see it
- if you read the same thing twice in a transaction, you must get the same return value
What is the serialisable isolation level?
- Has all the levels above
What is a serialisable schedule
- A non-serial schedule is called a serializable schedule if it can be converted to its equivalent serial schedule
- You have serial schedule TA then TB, and item X = 15 after both transactions have run
- if you have some of TA then TB then TA then TB and item X still = 15, this schedule is not serial but it serialisable
What is durability?
- Once a transaction commits and changes the database, then these changes cannot be lost because of failure
- the effect of a transaction on the database should not be lost after the commit point
- we REDO the transaction if there are any problems after the update
- durability means we can deal with media failure
What are some relational DBMS Components
- User/application
- transaction manager
- logging and recovery
- concurrency control
- Buffers
- Storage
What is transaction management formed of?
- Concurrency control
- Logging and recovery
Which components of transaction management satisfy ACID?
A - via recovery control (logging and recovery)
C - via scheduler - concurrency control
I - via scheduler - concurrency control
D - via recovery control (logging and recovery)
Advantages of serial schedules?
- maintains consistency
- maintains isolation
Advantages of concurrent schedules (non serial)?
- more efficient in multi-user environments (transactions don’t have to wait for others to finish before starting)
What do concurrent schedules not guarantee?
Consistency or isolation
How come concurrent schedules don’t guarantee consistency or isolation?
- Because they can accidentally overwrite values in the buffer
How much concurrency can we allow while satisfying Isolation and Consistency?
A schedule S is serializable if there is a serial schedule S’ that has the same effect as S on every initial database state.
What do seralisable schedules guarantee?
- consistency and correctness
Why is serialisability hard to test?
- because it depends on reads, writes, commits and non-database operations
- non-database operations can be complex
How much concurrency can we allow while satisfying Isolation and Consistency … while being able to check it fast?
by having conflict seralisability
What is a conflict in a schedule?
- a pair of operations from different transactions that cannot be swapped without changing the behavior of at least one transaction
What can be defined as a conflict in a schedule?
A pair of operations from different transactions that access the same item and at least one of them is a write operation
How can we tell if a schedule is conflict serialisable?
- If it is conflict equivalent to a serial schedule
How can we tell if a schedule is conflict-equivalent?
- two schedules S and S’ are conflict-equivalent if S can be obtained from S’ by swapping any number of (1) consecutive (2) non conflicting operations from (3) different transactions
Describe which schedules fit into other schedules
- All serial, conflict-serialised and serialised schedules are concurrent schedules
- All serial and conflict-serialised schedules are serialisable
- all serial schedules are conflict serialisable
How do we quickly show that something is not conflict-serialisable
- we create a precedence graph with each transaction as a node and each conflict as a link between nodes
- if there is a cycle within this graph then the schedule is not conflict-serialisable
How do we quickly show that something is not conflict-serialisable
- we create a precedence graph with each transaction as a node and each conflict is a link between nodes (only if op1 appears before op2) and we set the nodes out in order T1,T2,T3
- if there is a cycle within this graph then the schedule is not conflict-serialisable
why are cycles in the precedence graph bad?
- They means that a contradiction has arisen (which could cause a deadlock)
What are the steps of finding a serial schedule from a precedence graph?
- Find a transaction with only outgoing edges
- you put that first in the schedule and remove the transaction from the graph
- you repeat this process until there’s no nodes left.
How does transaction scheduling work in a DBMS?
- The scheduler gets fed operations and it can either execute them or delay them happening.
How can we enforce conflict serialisability?
Using locks with a simple locking mechanism
- a transaction has to lock an item before it accesses it
- locks are requested from and granted by the scheduler
- each item is locked by at most one transaction
- each lock must eventually be released
What are the symbols for locking and unlocking an item(x)
l1(X) for locking
u1(x) for unlocking
What are the rules for locking in a schedule
Every lock must be followed by an unlock
An item(x) must be unlocked by a transaction before being locked again by a different transaction
Why may not every schedule with simple locking may be serialisable?
There’s only one lock so other transactions have to wait to run whilst the first transaction has locked an item it wants to use
What is 2PL?
- 2 Phase Locking is where we follow the pattern, all locks then unlocks, then the schedule is serialisable
When are the two phases in 2PL?
- Phase one is until the first unlock, phase 2 is from that unlock to the last unlock
Why does 2 phase locking work?
- Because before T1 unlocks the first item that T2 needs T1 locks the next item it needs so that T2 can do all the operations up until it needs the item that T1 is currently using
- It ensures that T1’s transactions all occur first!
what does two phase locking ensure?
Conflict serialisability
What is an issue caused by 2PL?
Deadlocking because two transactions may be stuck waiting for the lock that the other transaction has.
How can we make 2PL more flexible to avoid deadlocks?
Solution: Different lock modes
- use shared and exclusive locks
What is a shared lock?
- multiple transactions can have this at the same time
- it means the transaction has access to read the item only
What is a exclusive lock?
- only one transaction can have this at a time
- allows transaction to read and write to an item
What are the rules regarding accessing locks
- a shared lock is granted if no other transactions hold an exclusive lock on the item
- an exclusive lock is granted if no other transaction holds a lock of any kind on the item.
What are the symbols for shared and exclusive locks with item X and transaction 1
sl1(X) - shared lock
xl1(X) - exclusive lock
What happens when a transaction has a shared lock on an item and requests to get an exclusive lock (being it is the only transaction w a lock of any kind on the item)?
The shared lock gets updated to an exclusive lock
When is there a risk of deadlock with shared & exclusive locks?
- if a shared lock on an item X can be upgraded later to an exclusive lock on X in order to be friendly to other transactions
What are update locks?
- they are requested by items to read (not write) an item
- may be upgraded later to an exclusive lock (at that point then no other shared locks can be upgraded)
- This is granted to at most one transaction at a time
- Helps to avoid deadlocking
Why would T3’s request for a shared lock be denied?
Because another transaction holds an update lock
What are the 3 levels of using locks with multiple granularity?
- May lock relations (whole table)
- May lock disk blocks
- May lock tuples (couple of rows/row)
What is the problem with having too coarse granularity?
- less concurrency which may cause unnecessary delays
What is the problem with having too fine granularity?
- high overhead (need to keep track of all the locked items)
Need to prevent issues such as the following to guarantee conflict serialisability
- one transaction having a shared lock on a tuple
- another transaction having an exclusive lock for the relation
What are Intention Locks (a.k.a. Warning Locks)
If a transaction wants to lock something it has to put intention locks on super items (higher levels that contain item x) so conflict serialisability is ensured
-to get access to an item you need to have the intention locks on the levels above
What is the notation for the two intention locks?
- IS1(x) = intention to request a shared lock on a sub item
- IX1(x) = intention to request an exclusive lock on a sub item
Why might a transaction abort?
- Errors whilst executing transactions
- deadlocking
- Explicit request
What events are beyond the DBMS’s Control?
- Media failures: A crash is caused if the rotating head in a Hard disk drive crashes
- Catastrophic events: need to store databases/copies of it in a physically different location and hope that not all of the locations get physically damaged.
- System failures: power failures etc, information about the active state of the database is lost
What is logging in DBMSs?
- writing activities into a log so that a desired database state can be recovered later
What are important activities that commonly feature in a log?
- starts of transactions, commits, aborts
- modification of database items
What techniques can be use to do logging in DBMSs?
- REDO logging
- UNDO logging
- Combinations of the two REDO/UNDO logging
Where are the database and log stored?
On the hard disk = secondary storage
What does stored locally mean?
It means stored in RAM
Where is the buffer?
In main memory = RAM
What is UNDO logging?
- logs activities with the goal of restoring a previous consistent database state
- maintains atomicity
What are typical entries stored in an UNDO log?
- <START>: Transaction T has started
</START> - <COMMIT>: Transaction T has committed
</COMMIT> - <ABORT>: Transaction T was aborted
</ABORT> - <T, X, v>: Transaction T has updated the value of database item X, the old value of X was v
Describe the UNDO logging procedure?
1: if T1 updates database item X and old value = v then <T,X,v> must be written to log on disk before X is written to disk
2: If T1 commits, then <COMMIT> must be written to disk as soon as all database elements changed by T have been written to disk</COMMIT>
What is the simplified version of the UNDO logging procedure?
- read/write/lock/unlock operations
- write values to go into log in buffer
- flush pervious values of items to log file on disk
- write changes of item values to disk
- once done, write COMMIT T to buffer in main memory
- flush COMMIT T to log file on disk
What if a system failure occurs? (The Recovery Manager)
- If T has committed successfully then no recovery process is needed
- if T has not committed before the failure then we must undo all the updates to the database items that were written to disk (we can do this by looking at what the old value of the item was in the log), we undo up to the last START T or COMMIT T
Describe recovery with Undo logging?
- if an error occurs, the recovery manager restores the last consistent database state
- it traverses the log backward to do this.
When do we write <ABORT> in the log file?</ABORT>
- We replace each <T,X,v> statement with <ABORT> for each uncommitted transaction T that was not previously aborted and call flush log</ABORT>
If a schedule has 3 transactions in it, how many <COMMIT> statements should there be in the Log file if all of the transactions successfully wrote all their item updates to the disk and there was no failures?</COMMIT>
There should be 3 <COMMIT> statements</COMMIT>
What if a transaction aborts in UNDO logging?
- Use the UNDO log like before to recover all the changes that were made
- but we only change the values for one specific transaction not all of them.
What is REDO logging?
- logs activities with the goal of restoring committed transactions
- it ignores incomplete transactions
- maintains durability
- log stores same commands except <T, X, v>: stores the new value of the item not the old one
What are typical entries stored in an REDO log?
- <START>: Transaction T has started
</START> - <COMMIT>: Transaction T has committed
</COMMIT> - <ABORT>: Transaction T was aborted
</ABORT> - <T, X, v>: Transaction T has updated the value of database item X, the new value of X was v
What is the aim of REDO logging
To restore things for transactions that have finished, even if they haven’t been changed on the disk yet
Describe the REDO logging procedure?
- T1 writes all log records for all updates of items to log on disk
- T1 writes <COMMIT> to log on disk</COMMIT>
- T1 writes all committed updates to database on disk
When are we allowed to output things during UNDO logging as opposed to REDO
- In UNDO logging we can output items values before they have been committed
- In REDO logging items have to have been committed before we can output them
What is the simplified version of the REDO logging procedure?
- read/write/lock/unlock operations
- write new values to go into log in buffer
- once done, write COMMIT T to buffer in main memory
- flush new values of items stored in buffer to log file on disk
- flush COMMIT T to log file on disk
- write changes of item values to disk for committed items only
Describe recovery with Redo logging?
- Need to check whether <COMMIT> has been written to the log file on disk or if it's only in the log in the buffer in main memory</COMMIT>
- if <COMMIT> has been written to the log file on disk then we know all the transactions have been written to the disk</COMMIT>
- if <COMMIT> is only in the log in the buffer then T hasn't written anything to the disk</COMMIT>
Describe the recovery procedure with Redo logging?
- traverse the log from first to last item
- if we see <T,X,v> and T has a <COMMIT> log record then change the value of X on the disk to v</COMMIT>
- for each incomplete transaction T, write <ABORT> into the log on disk</ABORT>
What if a transaction aborts in REDO logging?
- So we write <ABORT> at the end of a transaction that hasn't committed</ABORT>
- we don’t need to take any further actions since none of the changes were written to the disk yet.
What is Undo/Redo logging?
- does a combination of undo and redo logging
- this way it maintains atomicity and durability
- instead of writing <T,X,v> to the log file it writes <T,X,v,w> where v is the old value and w is the new value of X
Why does Undo/Redo logging provide more flexibility?
- Because it stores enough information that we can do undo logging and redo logging and therefore we can do both things when we need to
- so it doesn’t matter what order you do the COMMIT T command now. This means you’re more free to do things in the order that you like.
- Say one that makes it faster because it’s better to make bigger updates on the disk and by doing this you’re allowed to do it whenever you want and therefore you can make bigger updates.
Which logging process is it better to do big updates to the disk with?
- Redo logging, but we need to be careful only to use the last committed value instead of the last value
- because we can do these updates to the disk whenever and not have to worry about
- advantage of doing this later is that you can do bigger updates at the same time which is faster on a real hard disk.
Describe the UNDO/REDO logging procedure?
- write all log records for all updates of item values to buffer in main memory
- write all updates to disk
- <COMMIT> can be written to disk before or after all the changes to the database have been written to the disk depending on what the DBMS prioritises
</COMMIT>
What is No Steal with Redo logging?
- It ensures atomicity (as well as durability)
- it means that uncommitted data may not overwrite committed data on disk
In practice if you want Steal/No force what logging procedure should you use?
Undo/Redo
What is simple checkpointing for undo logging?
- the log is periodically checkpointed
- so every t mins we put a checkpoint in the log
- we don’t need to undo transactions before the checkpoint
What is the procedure for simple checkpointing for undo logging?
- Stop accepting new transactions
- wait until all active transactions finish and have written <COMMIT> or <ABORT> record to log in buffer</ABORT></COMMIT>
- flush log updates to hard disk
- write a log record <CHECKPOINT></CHECKPOINT>
- Flush the log to disk again (with checkpoint command)
- Resume accepting transactions
What is ARIES checkpointing?
does undo/redo logging but transactions do not write to buffers until they are sure they want to commit
What is the procedure for ARIES checkpointing?
- write <CHECKPOINT(T1, T2…) in log and flush it
- T1,T2,… are the transactions in progress so they haven’t committed or aborted yet
- write the content of the buffer to hard disk
- write <END> to the log in the buffer and then flush it to the hard disk</END>
How is recovery carried out with ARIES checkpointing?
- process the undo/redo log as before
- only redo (part of) the committed transactions in T1,T2… after <CHECKPOINT(T1,T2,…)>
- undo all of the uncommitted transactions that come before <CHECKPOINT(T1,T2,…)>
- as the ones before will have been written to the disk and the ones after won’t have
What are the properties of Conflict-Serialisability
and how can they be enforced?
- equivalent to serial schedules
- ensures consistency and correctness
- enforced by 2PL
What are the properties of recovery and how can they be enforced?
- ensure consistency as we can recover data base states
- robust, works even after system failures
- enforced using undo logging or redo logging or undo/redo logging or simple checking pointing with undo logs or aries checkpointing with undo/redo logs
What are dirty reads?
- when the isolation property is not fully enforced by setting isolation level to READ UNCOMMITTED
- gains more parallelism by executing some transactions that would have to wait to prevent dirty reads
- however dirty reads can slow down the system when transactions have to abort
What is a cascading rollback?
- if transaction T aborts, find all the transactions that have read items that were written by T
- recursively abort all transactions that have read items written by an aborted transaction
What can we break if we do a cascading rollback and abort transactions?
- if we do not abort all the transactions that interacted with aborted transaction T, then we can risk breaking consistency and isolation
- if we do abort them all we can break durability
When is a schedule recoverable?
- if a transaction T1 commits and has read an item X that was written before a different transaction T2
- then T1 must commit before T2 commits (T2 must delay it’s commit)
Which transactions will be included in a cascading rollback if a transaction aborts but the schedule is recoverable?
- Only active transactions can be forced to commit
- so transactions that have committed before T1 aborts won’t have to abort
Why are non-recoverable schedules serialisable and recoverable schedules are non-serialisable?
recoverable schedules have to be in a specific order - that specifies R2(X), C1, C2 meaning that this is not serialisable because it’s not equivalent to a serial schedule
What is an implicit assumption about Recoverable Schedules?
that all log records have to reach the hard disk in the order in which they were written (if they don’t this could mean a recoverable schedule becomes non-recoverable)
What is a cascadeless schedule?
- If each transaction in it reads only values that were written by transactions that have already committed
What do cascadeless schedules ensure?
- No reading of dirty data
- no cascading rollbacks
What are cascadeless schedules?
- non-serialisable, because they have to be in a certain order, the reads of other transactions have to be after others commit, so the order matters so they’re not serialisable
- they are recoverable because the item doing a dirty read is doing it from a transaction that has already committed, therefore it commits after the first transaction
What is a strict schedule?
A schedule where each transaction in it reads and writes only values that were written by transactions that have already committed
What do strict schedules achieve?
- Cascadeless
- serialisability
- recoverable
What is Strict Two-Phase Locking (Strict 2PL)
- variant of 2PL
- a transaction T must release any lock (that allows T to write data) until T has committed or aborted and the commit/abort log record had been written to disk
What does Strict Two-Phase Locking (Strict 2PL) ensure?
- conflict serialisability
- strict schedules
How is 2PL and strict 2PL different?
- in 2PL the commit command comes after the unlocks
- in 2PL the commit comes before the unlocks
- this is so that no other transactions can read/write to uncommitted data
How the Types of Schedules are Related?
- All strict and 2PL strict schedules are serialisable and conflict serialisable
- some cascadeless and recoverable schedules are serialisable and conflict serialisable
What problem is still not solved with strict 2PL?
Deadlocking
What are two approaches to deadlock prevention?
- Detect deadlocks and fix them (rollback/ restart transactions)
- Enforce deadlock-free schedules
What are the deadlock detection approaches?
- Timeouts: assume a transaction is in deadlock if it exceeds a given time limit
- waits-for-graphs: shows transactions and dependencies, cycles mean deadlocks
- Timestamp-based
Describe timestamping for deadlock detection
- each transaction T is assigned a unique integer TS(T) upon arrival at the scheduler
- if T1 arrived earlier than T2, we require the TS(T1) < TS(T2)
- Time stamps do not change even after restart
- if transactions arrive at the same time they still get different timestamps
How Are Timestamps Used?
- we use time stamps to decide which transactions can wait longer (for a lock/or to start)
- we want to prevent cyclic dependencies because as we saw before this creates deadlocking
What is the wait to die scheme?
(“older transactions always wait for unlocks”)
- If T1 is older than T2, and requests an item then it waits for T2 to be finished with it
- If T2 is younger than T1 and requests an item, it dies (rollsback and starts again)
- this makes sense because if a transaction is younger it means it’s done less work, so it less of a waste to restart
What is the wound-wait scheme?
(“older transactions never wait for unlocks”)
- if T1 is older than T2 and requests an item from T2, T2 is immediately rolled back unless it has committed
- if T2 is younger than T1 and requests an item from T1, it’s allowed to wait for T1 to unlock the item
What is the same for wait-to-die and wound wait time stamping?
In both methods, the older transaction never dies or rollsback
Why does Wound-Wait Work?
- At all times the oldest transaction keeps running
- hence when that finishes the same occurs for the transaction that arrives directly before it
Why does the younger transaction die in wait-to-die and wound-wait?
wait-to-die: dies of timeout
wound-wait: dies because it’s holding a lock the older one needs
how can we use time stamping to enforce deadlock free schedules?
- schedule transactions as if they are executing each transaction instantly
- we should think of transactions as being completely isolated so each transaction starts and finishes before the next
- if two arrive at the scheduler at the same time we just randomly pick one to start first
- equivalent to serial schedules
What is different in timestamping to create deadlock free schedules?
- Here each transaction is assigned a new time stamp number whenever it restarts
- this means transactions only go in reverse consecutive order
- holds information about the last transaction to read from and write to an item
What are the advantages and disadvantages of time based scheduling?
advantages: conflict-serialisable schedules, no deadlocks
disadvantages: cascading roll backs, starvation, many restarts
How do we ensure strictness and not get deadlocks with timestamping?
- we delay read or write requests until the youngest transaction who wrote X has committed or aborted
- Just lock the transaction until the earlier one has finished
- So we won’t get deadlocks because the oldest one can always move forwards using this principal
What is Multiversion concurrency control
- A more advanced version of timestamping
- just have multiple versions of each item in your database
- So you don’t overwrite the values in an item, you just write a new item for each new timestamp.
- you can just discard the old items when they stop being relevant
-we only need to restart transactions if you try to write and the RT is later than the write time stamp - Before we had to restart if either the read or write stamp was too young, now we only have to restart if the read timestamp is too young.
