Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Database Systems > L9: Transactions > Flashcards

L9: Transactions Flashcards

1
Q

Transactions in SQL:

Basic Structure

A
  • Transactions are typically “ad-hoc”
    • Each statement is treated as one transaction
    • But in a program, multiple statements can be grouped as a single transaction
  • Must begin with START TRANSACTION
  • Can have multiple UPDATE calls
  • End with COMMIT

START TRANSACTION

UPDATE table_name

SET field = new_value

WHERE

COMMIT

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

Two Schemes/Approaches

for preventing

Deadlock

A

Wait-Die Scheme

Wound-Wait Scheme

*These schemes prevent deadlock and “starvation”

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

Preventing Deadlock:

Wait-Die Scheme

A

Wait-Die Scheme

  • Non-preemptive
  • Older transaction waits for the younger transaction to release lock
  • Younger transactions never wait, they are rolled back instead
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Preventing Deadlock:

Wound-Wait Scheme

A

Wound-Wait Scheme

  • Preemptive
  • Older Transaction “wounds” younger transaction
    • Forces rollback instead of waiting
  • Younger transactions wait for older transactions
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Log Based Recover:

Basic Idea

A
  • Keep a “log” of every operation on stable storage
    • _​_Maintains a record of update activities on database
  • When a transaction( T ) starts, it registers itself in the log
    • <t></t>
  • Before executing a write, noted in log
    • <t></t>
  • Whe T is done, commits the change
    • <t></t>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Log Based Recovery:

Concepts/Points covered

A
  • Basic Idea
  • Checkpointing
  • Modification Variants:
    • Deferred Modification
    • Immediate Modification
  • Recovery Operations
    • Undo
    • Redo
  • How disk is shared
  • Locking Assumption
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Log Based Recovery:

Checkpointing

A
  • During recovery, only need to consider the most recent transaction that started before the checkpoint
    • And consider all transactions after the most recent transaction (what?)
  • Scan backwards from end of log to find checkpoint
  • Only transactions that are in L, or started after the checkpoint need to be recovered
  • Continue scanning back to find the start of all transactions in L
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Log Based Recovery:

Recovery Operations

A

Undo( T )

Writes old value to X: <t></t>

Log updated with <t> and</t>

ended with <t> after transaction is finished</t>

Redo( T )

Writes new value to X: <t></t>

No log output for Redo

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

Log Based Recovery:

When to use

Undo

A

Undo needs to be performed IF:

  • T contains the record <t></t>
  • But does not contain <t> or <t></t></t>

Basically, the transaction was started but not finalized or aborted

Sometimes, if multiple failures occur,

then the actions of undoing operations may need to be performed AGAIN.

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

Log Based Recovery:

When to use

Redo

A

Redo needs to be performed IF:

  • T contains the record <t></t>
  • AND either <t> or <t></t></t>

basically, the Transaction was Started and Finished,

but is wrong.

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

Log Based Recovery:

Types of Modification

A
  • Immediate Modification
    • Updates written to disk before transaction commits
  • Deferred Modification
    • Updates written to disk when transaction is committed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Log Based Recovery:

Types of Modification:

Deferred Modification

A

Deferred Modification

  • Only performs updates to buffer and disk at the time of the transaction commit
  • Simplifies some of the recovery aspects
  • Needs to store more local copies in the transactions
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Log Based Recovery:

Types of Modification:

Immediate Modification

A

Immediate Modification

  • Allows updates of uncommitted transaction to be made to buffer or disk before transaction commits
  • Update log must be written before Database item written
    • Assume log record is output directly to stable storage
    • In reality, output to stable storage can take place at any time
  • Order in which blocks are output can be different from the order in which they are written to the buffer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Log Based Recovery:

How disk and log access is allotted

A

All transactions share disk and the log

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

Log Based Recovery:

Multiple Transactions attempting modification

A

Assume that if

some transaction has modified an item,

no other transaction can modify the item

until

the original transaction has committed or aborted.

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

Log Based Recovery:

Log Update Visibility

A

Updates of other transactions should not be visible

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

Transactions:

Topics/Concepts

A
  • Transaction syntax
  • Granularity
  • Disk Access
  • Lock Compatibility Table
  • Deadlock and deadlock prevention
  • Log Based Recovery
  • Recover Algorithm
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Granularity:

Overview

A
  • Can increase Concurrency by providing levels of granularity to the access
    • Coarse or Fine granularity
  • Accomplished with Hierarchical, lockable units
    • Examples:
      • Database, Relations/Files, Pages, Tuples, Attributes, etc
  • Need to create a collision path:
    • Locks different levels of access
      • Intention Locks
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Accessing Data on Disk:

Components

A

Components:

  • Physical Blocks:
    • Blocks of data on Disk
  • Buffer Blocks:
    • Blocks of data residing in memory

*We assume that each data item fits into a single block

20
Q

Accessing Data on Disk:

Commands

A

Commands

  • Input
    • Get data from disk, into buffer
  • Output
    • Get data from buffer, onto disk
21
Q

Locks:

Possible Lock Statuses

A
  • NL : Not Locked
  • S : Shared
  • X : Exclusive
  • IS : Intentional Shared
  • IX : Intentional Exclusive
  • SIX : Intentional Shared and Exclusive
22
Q

Lock Status:

NL

A

Not Locked (NL)

Compatibilities:

Compatible with all other Lock Statuses

23
Q

Lock Status:

IS

A

Intentional Shared

Compatibilities:

Compatible with all other Lock Statuses, except for

Exclusive (X)

24
Q

Lock Status:

IX

A

Intentional Exlusive

Compatible with:

  • Not Locked (NL)
  • Intentional Shared (IS)
  • Intentional Exlusive( IX)
25
Q

Lock Status:

S

A

Shared(S)

Compatible With:

  • Not Locked (NL)
  • Intentional Shared (IS)
26
Q

Lock Status:

SIX

A

Intentional Shared and Exlusive (SIX)

Compatibilities:

  • Not Locked (NL)
  • Inentional Shared (IS)
27
Q

Lock Status:

X

A

Exclusive (X)

Compatibilities:

  • Only compatible with Not Locked(NL)
28
Q

Recover Algorithm:

Two Phases

A
  • Redo Phase:
    • Replay all transactions
    • Whether they committed, aborted or were incomplete
  • Undo Phase:
    • Undo all incomplete transactions
29
Q

Recover Algorithm:

Redo Phase

A

Idea:

Replay all transactions, whether they committed, aborted or are incomplete

  • Find last checkpoint <checkpoint></checkpoint>
  • Set Undo List to L
  • Scan forward from above <checkpoint></checkpoint>
  • When a write record is found, redo it
  • When a start record is found, add T to Undo LIst
  • When a commit or abort record found, remove T from Undo List
30
Q

Recover Algorithm:

Undo Phase

A

Idea:

Undo all incomplete Transactions

  • Scan Log backwards from the end
  • When write record found
    • where T is on the Undo List, perform Undo and write to Log
  • When start record found
    • where T is in Undo List,
    • write abort to Log and remove T from the Undo List
31
Q

Transactions:

Definition

A

Transactions

are a programming abstraction that enables the DBMS to handle recovery and concurrency for users.

A Transaction(TXN) is a sequence of one or more operations(reads or writes)

which reflects a single real-world transaction

32
Q

Problems with Transactions

A
  • Failures can occur during the transaction
    • hardware, software crash for example
  • Need to handle concurrent execution of multiple actions
  • To preserve data, a DBMS must adhere to a set of rules
33
Q

Transaction

Properties

A

Acronym: ACID

  • Atomic
    • State shows either all the effects of a TXN, or none of them
  • Consistent
    • TXN moves from a state where integrity holds to another where integrity holds
  • Isolated
    • Effect of TXNs doesn’t change depending on the order they are completed
  • Durable
    • Once a TXN has committed its effects, those effects remain in the database
34
Q

Transaction Rules:

Consistency Requirements

A

Consistency Requirements include:

  • Explicit Integrity Restraints(constraints?)
    • e.g. Primary and Foreign Keys
  • Implicit Integrity Restraints
    • e.g. Sum of balances on all accounts, etc

Generally:

  • TXN must start with consistent database
  • During TXN, database may be inconsistent
  • After TXN, database MUST be consistent again
35
Q

5 Possible

States of a Transaction

A
  • Active
    • Initial State, TX stays here while executing
  • Partially Committed
    • After final statement executed
  • Committed
    • After successful completion of transaction
  • Failed
    • After discovering that normal execution cannot proceed
  • Aborted
    • After DB has been rolled back and restored to prior state
36
Q

Transaction States:

Possible “Travel” from each state

A
  • Active, can go to:
    • Partially Committed
    • Failed
  • Partially Committed can go to:
    • Committed
    • Failed
  • Committed
    • Nowhere, is a final state
  • Failed, can go to
    • Aborted
  • Aborted
    • Nowhere, is a final state
37
Q

Two Possible Outcomes

for a Transaction

A

Transaction Commits:

all the changes are made

or

Transaction Aborts:

no changes are made

Note: TXN activities are Atomic; all or nothing

38
Q

Concurrent Executions

A

Multiple transactions are allowed to run concurrently on the system

Benefits:

  • Increased processor and disk utilization
  • Reduced average response time
39
Q

Concurrency Control Schemes

A

Concurrency Control Schemes

  • used to achieve isolation of transactions
  • Controls interaction between transactions to protect the integrity and consistency of database
  • Major CCS: Schedules
40
Q

Concurrent Transactions:

Schedule

A

Schedule:

A sequence of instructions that specify chronological order of instructions from concurrent transactions

  • Must consist of all instructions in the transactions
  • Must preserve order of instructions in original transactions
41
Q

Concurrent Transactions:

Schedule Assumptions

A
  • Each transaction preserves consistency
    • All serializable transactions do preserve database consistency
  • A (possibly concurrent) schedule is serializable if it is equivalent to a serial schedule
  • Simplicity:
    • Ignore other operations besides reads and writes
42
Q

Concurrent Transactions:

Schedule Conflicts

A

Conflicts can occur between two operations

*Only read-read concurrencies do not conflict

Conflicts:

  • read-write
    • X=read(Q) , Y=write(Q)
  • write-read
    • X=write(Q) , Y=read(Q)
    • write-read
      • X=write(Q) , Y=read(Q)
43
Q

Concurrent Transactions:

Conflict Serializability

A

Assume we have a schedule S.

If S can be transformed into schedule S’

by a series of non-conflicting swaps of operations,

then S and S’ are Conflict Equivalent.

S is Conflict Serializable

if it is Conflict Equivalent to a serial schedule.

44
Q

Locking Instructions

Basic Overview

A
  • Use locking mechanisms to control access to data item
  • Two Modes:
    • Exclusive, Lock-X Instruction
      • Can be read or write
    • Shared, Lock-S Instruction
      • Can only be read
  • A transaction can only proceed if a lock is granted
  • Infinite shared locks available, only one exclusive lock
  • If lock cannot be granted, transaction waits until a lock is granted
45
Q

What are

Deadlocks?

A

Deadlocks

When two or more transactions block each other by having exclusive locks on data that the other needs

Example:

T1 gets lock on item B

T2 gets lock on item A

T2 tries to get lock on item B, but needs to wait for T1 to release lock

But T1 has a schedule instruction to get a lock on item A, before it releases B.

Each transaction is waiting on the other.

In this event, the Database must be rolled back

46
Q

Concurrent Transactions:

Two Phase Locking (2PL)

A

Ensures conflict-serializable schedules, but does not prevent deadlocks

Phase 1: Growing Phase

  • Transaction may obtain locks
  • Transaction may not release locks
  • May upgrade Locks (S to X)

Phase 2: Shrinking Phase

  • Transaction may not obtain locks
  • Transaction may release locks
  • May downgrade Locks(X to S)
47
Q

Concurrent Transactions:

Two Phase Locking:

Strict 2PL

Rigorous 2PL

A

Strict 2PL

  • Transaction must hold all of its locks until it commits or aborts
  • Prevents cascading rollbacks

Rigorous 2PL

  • Even more strict
  • All locks must be held until transaction commits/aborts
  • Can be conflict serializable schedules that cannot be obtained if two-phase locking is used

Database Systems (18 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions