multiuser databases Flashcards

1
Q

concurrency

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

interleaving

A

breaking down the operations into smaller steps and alternating between them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

schedule

A

a list of actions from a set of transactions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

well formed schedule

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

complete schedule

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

serial schedule

A

a schedule where the actions of different transactions are not interleaved

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

conflicting operations

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

how do we avoid conflicts (ACID)

A

atomicity
consistency
isolation
durability

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

atomicity of transactions

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

consistency of transactions

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

isolation of transactions

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

durability of transactions

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

equivalent schedules

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

serializable schedule

A

a schedule equivalent to some serial execution of the transactions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

log

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

commit

A

reflected in the db

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

abort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

what ensures durability in the dbms

20
Q

what are some anomalies with interleaved execution

A

reading uncommitted data
unrepeatable reads
overwriting uncommitted data

21
Q

reading uncommitted data anomaly

A

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

22
Q

unrepeatable reads

A

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

23
Q

overwriting uncommitted data

A

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

24
Q

in which two ways can we prevent anomalies

A

lock based concurrency
strict 2 phase locking protocol

25
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
26
shared (s) lock
allows multiple transactions to read the same data concurrently but prevents any from writing to it
27
exclusive (x) lock
allows a transaction to write data while ensuring no other transaction can read or write to the same data
28
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
29
what is a negative of strict 2pl
you cannot use it with interleaving
30
conflict equivalent
they involve the same set of transactions and perform the same operations and the order of conflicting operations is the same
31
conflicting operations
when different transactions are operating on the same data and at least one of them is a w
32
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
33
how do we check if a schedule is conflict serializable
analysing the conflicting operations and constructing a precedence graph
34
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
35
deadlock
a cycle of transactions waiting for locks to be released by each other
36
in which two ways can we prevent deadlocks
deadlock prevention and detection
37
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
38
how does deadlock prevention work
you assign priorities based on timestamps and follow the two policies; wait-die and wound-wait
39
wait-die
if the transaction wanting the lock has higher priority then it waits for it or the other one aborts
40
wound-wait
if the transaction wanting the lock has higher priority then the other aborts or this transaction waits
41
recoverable schedule
where a transaction commits only after all transactions containing changes that it has read are committed
42
what do recoverable schedules prevent
dirty reads and cascading aborts
43
cascading aborts
when the abort of one transaction causes a chain reaction of others aborting
44
how do some systems avoid cascading aborts
only releasing locks at commit time; s2pl
45