Week 9 Flashcards
What is a Transaction?
An executing program that forsm a logical unit of database operations
- A transaction includes one or more database operations eg., insertion, deletion, updating, retrieval
What are the properties of ACID?
Atomicity: All or nothing
Shouldn’t take money from A without giving it to B
Consistency: transforms the database from one consistent state to another consistent state
money isn’t lost or gained
Isolation: partial effects of incomplete transactrions should not be visible to other transactions
other transactions shouldn’t see such a change until completion
Durability: successfully committed transactions are permanently recorded in the database, not list, even in the event of a system failure
After completion, such a change in A and B is saved in the database
What is a Schedule?
An ordering of operations for concurrent transactions
What are the 2 types of Schedules?
Serial Schedule: A schedule in which the operations for concurrent transactions are not interleaved
But unacceptable in practice
Non-serial schedule: A schedule in which the operations for concurrent transactions are interleaved
What are the 2 desired properites of a Schedule?
Serializability
Recoverability
What are Conflicting Operations?
If 2 operations belong to different transactions, access the same same database item, and at least one operation is a writing operation
Eg. R1(x) & W2(X), W1(Y), W2(Y)
How do you test for Conflict Serializability?
Step 1: build a precedence graph
-Each node corresponds to one transaction
- Each edge (Ti -> Tj): if one of the operations in Ti appears in the schedule before some conflicting operations in Tj
Step 2: check for cycles in the graph
-If yes, the schedule is not serializable
- If no, the schedule is serializable
What is a Recoverable Schedule?
A schedule, where, for each pair of transactions Ti and Tj, if Tj reads a data item previously written by Ti, then Ti should commit before Tj
“Write first then commit first” - lecturer
What is Concurrency Control?
The process of managing simultaneous operations on the database without having them interfere with another
Objectives:
- Schedule transactions to avoid intereference
- Guarantee serializability
What are the 2 Concurrency Control Techniques?
Pessimistic:
Assumes that conflict is likely and take steps to prevent it
eg. Locking, Timestamping
Optimistic:
Assumes that conflict is unlikely and only checks for it when transaction commits
What can Locks be applied to?
-The whole database
-A file
-A page/ a disk block
-A record
-A field value of a record
What is a Shared/Exclusive Locking Scheme?
A transaction must issue read_lock(X), or write_lock(X) before any read(X)
A transaction must issue write_lock(X) before any write(X)
A transaction must issue unlock(X) after read(X) and write(X)
What is a problem with Shared/Exclusive Locking?
It does not guarantee serializability
More strict protocols are required, eg. two-phase locking (2PL)
What is Basic Two-Phase Locking (2PL)?
All locking operations precede the first unlock operation in a transaction
Growing/Expanding phase: during which new locks on items can be acquired but none can be released
Shrinking phase: during which existing locks can be released but no new locks can be acquired
Advantage: It assures serializability
What is a problem with 2PL?
Deadlock: A circular situation where each of two (or more) transactions are waiting to acquire locks that are held by the other
What are the 3 techniques for handling Deadlock?
- Timeouts
- Deadlock detection and recovery
- Deadlock prevention
What is the Timeouts technique?
A transaction will wait for a (database defined) period to acquire a lock
If this time runs out then the whole transaction is rolled back and restarted
What is the Deadlock Detection and Recovery Technique?
A Wait-for Graph (WFG) is constructed
-node for each transaction
-directed edge from transaction T1 to transaction T2 if T1 is waiting to lock and item currently held in T2
A deadlock exists if the graph contains a cycle
What is the Deadlock Prevention technique?
Conservative 2PL algorithm
- prevents deadlock by locking all desired data items before transaction begins execution
Strict 2PL algorithm
-unlocking is performed after a transaction terminates (commits or aborts/rolled-back)
Each transaction is timestamped
Wait-die algorithm
-only older transactions can wait for younger ones
Wound-wait algorithm
-only younger transactions can wait for older ones
otherwise, younger transaction is rolled back and restarted with the same timestamp
What is Timestamping?
A concurrency control protocol that orders transactions in such a way that older transactions get priority in the event of conflict
What is a Timestamp?
A unique identifier created by the DBMS that indicates the relative starting time of a transaction
-Either a logical counter or the system clock
What is a Backup?
A copy of the database
taken periodically
Stored in safe place which enables database to be restored with an acceptable loss of data
What are the 3 types of Backup?
Full Backup
-The whole database
Differential Backup
-All changes made since the last full backup
Incremental
-All changes made since the last incremental backup
What is Recovery?
The process of restoring the database to a correct state in the event of failure
What are the 2 Recovery techniques?
Log-based
Shadow-paging
What is a Log?
A sequence of records, which maintains the records of actions performed by transactions
What is Checkpointing?
When a failure occurs,
The system checks the log file backwards from the end to the last checkpoint
- REDO all the transactions that commited since the last checkpoint
- UNDO all the transactions that were active at the time of the crash
What are the 2 types of DB updating schemes?
Deferred Update: Updates are not written to the database until after a transaction has reached its commit point
Immediate Update: Updates are applied to the database as they occur without waiting to reach the commit point
Write a card about “shadow paging”
What is a SBA/system/superuser account?
The central authority for managing a database system security
- Account creation
-Privilege granting
-Privilege revocation
-Security level assignment
What is Discretionary Access Control (DAC)?
The owner of the object specifies which subjects can access the object
Used by most commercial DBMs
Supported by SQL: GRANT and REVOKE
What are the 2 types of Access Control called?
Discretionary Access Control (DAC)?
What is Mandatory Access Control (MAC)?
The system (not the users) specifices which subjects can access specific data objects
Not supported by SQL
-Each database object is assigned a security class
-Each subjcet assigned a clearance for a security class
-Rules are imposed on reading and writing of database objects - Bell-Lapadula Model
What are the 4 security levels?
Top Secret (TS) > Secret (S) > Confidential (C) > Unclassified (U)
What is RAID?
Redundant Array of Independant Disks (RAID)
- A data storage technique that combines multiple physical disk drive components into one logical unit to:
- Improve reliability -> Parity (or error-correcting)
- Increase performance -> Striping
- Improve availability -> Mirroring
