multiuser databases Flashcards
concurrency
Interleaving the execution of the operations allowing multiple operations to run concurrently
interleaving
breaking down the operations into smaller steps and alternating between them
what does a transaction look like int eh view of the dbsm
a sequence of reads and writes performed as a single logical unit of work
schedule
a list of actions from a set of transactions
well formed schedule
where the actions of a transaction are in the same order that they happen in the transaction
complete schedule
a schedule contains an abort or commit action for every transaction that occurs in the schedule
serial schedule
a schedule where the actions of different transactions are not interleaved
conflicting operations
two operations that belong to different transactions, operate on the same data item and at least one of them is a write operation
how do we avoid conflicts (ACID)
atomicity
consistency
isolation
durability
atomicity of transactions
a transaction should always execute all of its actions in one step or shouldn’t execute them at all
so it should commit after completing all its actions or abort after executing some of them
consistency of transactions
any transaction should take the database from one consistent state to another
isolation of transactions
even though transactions may be interleaved, the net effect is identical to executing the transactions serially
durability of transactions
if the system crashed before changes made by a complete transaction are written to disk, the log issued to remember and restore these changes when the system is restarted
equivalent schedules
schedules involving the same set of operations on the same set of data objects and leave the database in the same state after being executed
serializable schedule
a schedule equivalent to some serial execution of the transactions
log
record of all operations performed during a transactions so the db can be recovered in a case of a crash or a failure
commit
reflected in the db
abort
not visible in the dbsm
prev changes in the transaction have been removed
what ensures durability in the dbms
the log
what are some anomalies with interleaved execution
reading uncommitted data
unrepeatable reads
overwriting uncommitted data
reading uncommitted data anomaly
dirty read; when a transaction reads data that has been modified by another transaction that hasn’t committed it yet leading to inconsistency
unrepeatable reads
when a transaction reads the same data twice but gets different results because another transaction modifies the data in between
overwriting uncommitted data
when two transactions modify the same data but one overwrites the changes made by another that hasn’t committed yet leading to the data from the first transaction being lost
in which two ways can we prevent anomalies
lock based concurrency
strict 2 phase locking protocol
how does lock based concurrency work
to read data you need to acquire a shared lock
to write data you need to acquire an exclusive lock
the lock is released once the transaction is complete or aborted
shared (s) lock
allows multiple transactions to read the same data concurrently but prevents any from writing to it
exclusive (x) lock
allows a transaction to write data while ensuring no other transaction can read or write to the same data
how does strict 2 phase locking work
transaction requests a lock and it is granted if no other conflicting locks are held by other transactions
transaction performs operations and no other transactions can use this lock
the transaction then commits or aborts and releases the lock
what is a negative of strict 2pl
you cannot use it with interleaving
conflict equivalent
they involve the same set of transactions and perform the same operations and the order of conflicting operations is the same
conflicting operations
when different transactions are operating on the same data and at least one of them is a w
conflict serializable schedules
if the schedule can be transformed into a serial schedule by swapping non-conflicting operations without changing the outcome of the schedule
conflict equivalent to some serial schedule
how do we check if a schedule is conflict serializable
analysing the conflicting operations and constructing a precedence graph
how do you create a precedence graph
identify all transactions and operations
find the conflicting operations
create nodes for each transaction
for every pair of conflicting operations create a directed edge between the two nodes
if the graph contains cycles then the schedule is not conflict serializable
deadlock
a cycle of transactions waiting for locks to be released by each other
in which two ways can we prevent deadlocks
deadlock prevention and detection
how does deadlock detection work
you create a wait-for-graph with each transaction represented as a node and a directed edge is added if one of them is waiting for the other to release a lock
you then periodically check for cycles
how does deadlock prevention work
you assign priorities based on timestamps and follow the two policies; wait-die and wound-wait
wait-die
if the transaction wanting the lock has higher priority then it waits for it or the other one aborts
wound-wait
if the transaction wanting the lock has higher priority then the other aborts or this transaction waits
recoverable schedule
where a transaction commits only after all transactions containing changes that it has read are committed
what do recoverable schedules prevent
dirty reads and cascading aborts
cascading aborts
when the abort of one transaction causes a chain reaction of others aborting
how do some systems avoid cascading aborts
only releasing locks at commit time; s2pl
