multiuser databases

Question 1

concurrency

Answer 1

Interleaving the execution of the operations allowing multiple operations to run concurrently

Question 2

interleaving

Answer 2

breaking down the operations into smaller steps and alternating between them

Question 3

what does a transaction look like int eh view of the dbsm

Answer 3

a sequence of reads and writes performed as a single logical unit of work

Question 4

schedule

Answer 4

a list of actions from a set of transactions

Question 5

well formed schedule

Answer 5

where the actions of a transaction are in the same order that they happen in the transaction

Question 6

complete schedule

Answer 6

a schedule contains an abort or commit action for every transaction that occurs in the schedule

Question 7

serial schedule

Answer 7

a schedule where the actions of different transactions are not interleaved

Question 8

conflicting operations

Answer 8

two operations that belong to different transactions, operate on the same data item and at least one of them is a write operation

Question 9

how do we avoid conflicts (ACID)

Answer 9

atomicity
consistency
isolation
durability

Question 10

atomicity of transactions

Answer 10

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

Question 11

consistency of transactions

Answer 11

any transaction should take the database from one consistent state to another

Question 12

isolation of transactions

Answer 12

even though transactions may be interleaved, the net effect is identical to executing the transactions serially

Question 13

durability of transactions

Answer 13

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

Question 14

equivalent schedules

Answer 14

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

Question 15

serializable schedule

Answer 15

a schedule equivalent to some serial execution of the transactions

Question 16

log

Answer 16

record of all operations performed during a transactions so the db can be recovered in a case of a crash or a failure

Question 17

commit

Answer 17

reflected in the db

Question 18

abort

Answer 18

not visible in the dbsm
prev changes in the transaction have been removed

Question 19

what ensures durability in the dbms

Answer 19

the log

Question 20

what are some anomalies with interleaved execution

Answer 20

reading uncommitted data
unrepeatable reads
overwriting uncommitted data

Question 21

reading uncommitted data anomaly

Answer 21

dirty read; when a transaction reads data that has been modified by another transaction that hasn’t committed it yet leading to inconsistency

Question 22

unrepeatable reads

Answer 22

when a transaction reads the same data twice but gets different results because another transaction modifies the data in between

Question 23

overwriting uncommitted data

Answer 23

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

Question 24

in which two ways can we prevent anomalies

Answer 24

lock based concurrency
strict 2 phase locking protocol

Question 25

how does lock based concurrency work

Answer 25

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

Question 26

shared (s) lock

Answer 26

allows multiple transactions to read the same data concurrently but prevents any from writing to it

Question 27

exclusive (x) lock

Answer 27

allows a transaction to write data while ensuring no other transaction can read or write to the same data

Question 28

how does strict 2 phase locking work

Answer 28

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

Question 29

what is a negative of strict 2pl

Answer 29

you cannot use it with interleaving

Question 30

conflict equivalent

Answer 30

they involve the same set of transactions and perform the same operations and the order of conflicting operations is the same

Question 31

conflicting operations

Answer 31

when different transactions are operating on the same data and at least one of them is a w

Question 32

conflict serializable schedules

Answer 32

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

Question 33

how do we check if a schedule is conflict serializable

Answer 33

analysing the conflicting operations and constructing a precedence graph

Question 34

how do you create a precedence graph

Answer 34

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

Question 35

deadlock

Answer 35

a cycle of transactions waiting for locks to be released by each other

Question 36

in which two ways can we prevent deadlocks

Answer 36

deadlock prevention and detection

Question 37

how does deadlock detection work

Answer 37

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

Question 38

how does deadlock prevention work

Answer 38

you assign priorities based on timestamps and follow the two policies; wait-die and wound-wait

Question 39

wait-die

Answer 39

if the transaction wanting the lock has higher priority then it waits for it or the other one aborts

Question 40

wound-wait

Answer 40

if the transaction wanting the lock has higher priority then the other aborts or this transaction waits

Question 41

recoverable schedule

Answer 41

where a transaction commits only after all transactions containing changes that it has read are committed

Question 42

what do recoverable schedules prevent

Answer 42

dirty reads and cascading aborts

Question 43

cascading aborts

Answer 43

when the abort of one transaction causes a chain reaction of others aborting

Question 44

how do some systems avoid cascading aborts

Answer 44

only releasing locks at commit time; s2pl