Week 9

Question 1

What is a Transaction?

Answer 1

An executing program that forsm a logical unit of database operations

• A transaction includes one or more database operations eg., insertion, deletion, updating, retrieval

Question 2

What are the properties of ACID?

Answer 2

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

Question 3

What is a Schedule?

Answer 3

An ordering of operations for concurrent transactions

Question 4

What are the 2 types of Schedules?

Answer 4

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

Question 5

What are the 2 desired properites of a Schedule?

Answer 5

Serializability

Recoverability

Question 6

What are Conflicting Operations?

Answer 6

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)

Question 7

How do you test for Conflict Serializability?

Answer 7

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

Question 8

What is a Recoverable Schedule?

Answer 8

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

Question 9

What is Concurrency Control?

Answer 9

The process of managing simultaneous operations on the database without having them interfere with another

Objectives:

• Schedule transactions to avoid intereference
• Guarantee serializability

Question 10

What are the 2 Concurrency Control Techniques?

Answer 10

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

Question 11

What can Locks be applied to?

Answer 11

-The whole database

-A file

-A page/ a disk block

-A record

-A field value of a record

Question 12

What is a Shared/Exclusive Locking Scheme?

Answer 12

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)

Question 13

What is a problem with Shared/Exclusive Locking?

Answer 13

It does not guarantee serializability

More strict protocols are required, eg. two-phase locking (2PL)

Question 14

What is Basic Two-Phase Locking (2PL)?

Answer 14

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

Question 15

What is a problem with 2PL?

Answer 15

Deadlock: A circular situation where each of two (or more) transactions are waiting to acquire locks that are held by the other

Question 16

What are the 3 techniques for handling Deadlock?

Answer 16

1. Timeouts
2. Deadlock detection and recovery
3. Deadlock prevention

Question 17

What is the Timeouts technique?

Answer 17

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

Question 18

What is the Deadlock Detection and Recovery Technique?

Answer 18

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

Question 19

What is the Deadlock Prevention technique?

Answer 19

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

Question 20

What is Timestamping?

Answer 20

A concurrency control protocol that orders transactions in such a way that older transactions get priority in the event of conflict

Question 21

What is a Timestamp?

Answer 21

A unique identifier created by the DBMS that indicates the relative starting time of a transaction

-Either a logical counter or the system clock

Question 22

What is a Backup?

Answer 22

A copy of the database

taken periodically

Stored in safe place which enables database to be restored with an acceptable loss of data

Question 23

What are the 3 types of Backup?

Answer 23

Full Backup

-The whole database

Differential Backup

-All changes made since the last full backup

Incremental

-All changes made since the last incremental backup

Question 24

What is Recovery?

Answer 24

The process of restoring the database to a correct state in the event of failure

Question 25

What are the 2 Recovery techniques?

Answer 25

Log-based

Shadow-paging

Question 26

What is a Log?

Answer 26

A sequence of records, which maintains the records of actions performed by transactions

Question 27

What is Checkpointing?

Answer 27

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

Question 28

What are the 2 types of DB updating schemes?

Answer 28

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

Question 29

Write a card about “shadow paging”

Question 30

What is a SBA/system/superuser account?

Answer 30

The central authority for managing a database system security

• Account creation

-Privilege granting

-Privilege revocation

-Security level assignment

Question 31

What is Discretionary Access Control (DAC)?

Answer 31

The owner of the object specifies which subjects can access the object

Used by most commercial DBMs

Supported by SQL: GRANT and REVOKE

Question 32

What are the 2 types of Access Control called?

Answer 32

Discretionary Access Control (DAC)?

Question 33

What is Mandatory Access Control (MAC)?

Answer 33

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

Question 34

What are the 4 security levels?

Answer 34

Top Secret (TS) > Secret (S) > Confidential (C) > Unclassified (U)

Question 35

What is RAID?

Answer 35

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