DBMS

Question 1

DBMS Architecture

Answer 1

SQL commands
|
Optimizer
|
Access method manager
|
Buffer manager — Concurrency control, Reliability Manager
|
Database (Index files, Data files)

— Reliability Manager

Question 2

Optimizer

Answer 2

Generates execution strategy for a query

Question 3

Access Method Manager

Answer 3

Implements execution strategy by performing physical access to data

Question 4

Buffer Manager

Answer 4

Manages page/block transfer from disk to main memory and vice versa

Question 5

Concurrency Control

Answer 5

Manages concurrent access to data

Question 6

Reliability Manager

Answer 6

Guarantees content correctness after crashes

Question 7

Rollback

Answer 7

The database goes back to the state at the beginning of the transaction, before the error

Question 8

Commit

Answer 8

Correct end of a transaction

Question 9

ACID properties

Answer 9

Atomicity
Consistency
Isolation
Durability

Question 10

Atomicity

Answer 10

Transaction must be completed and not left at intermediate states of execution.
- Redo
- Undo

Question 11

Consistency

Answer 11

Transaction should not violate integrity constrains enforced by a database schema
- Rollback
- Automatically correct the violation

Question 12

Isolation

Answer 12

Transactions must not interfere.
- Concurrency control

Question 13

Durability

Answer 13

Data not lost on failures
- Reliability manager

Question 14

Fix primitive

Answer 14

Loads pages into the buffer.

If PAGE in buffer:
return Page Address
Else:
If free page available:
Store page in available space
Else:
Search for count=0
if dirty == 0: write on disk
else: store page in that space

Question 15

Force primitive

Answer 15

Write ops immediately propagated to disk

Question 16

Flush primitive

Answer 16

Write ops postponed until free buffer

Question 17

Heap File

Answer 17

New records are inserted at the end. All space is exploited.
Frequent for unclustered (secondary) indices

Question 18

Ordered Sequential Structures

Answer 18

Records inserted by sort key. Usually free space is left in every block to add transactions in an ordered way.
Frequent for clustered (primary) indices

Question 19

Primary (clustered) Indices

Answer 19

• Ordered Data structures
• Only one index of this type can be defined
• Clustered B Tree Index, Hash Index

Question 20

Secondary (Unclustered) Indices

Answer 20

• Unordered Hash data structures
• Multiple different indices can be defined
• B Tree, Bitmap, Hash

Question 21

B Tree Index Use Cases

Answer 21

Range Queries

Question 22

Hash Index Use Cases

Answer 22

Equality predicates

Question 23

Bitmap Index Use

Answer 23

Boolean expressions

Question 24

Access Paths

Answer 24

• Full table scans
• Index scans
• RowID scans

Question 25

Join Types

Answer 25

• Nested Loop
• Merge Scan Join
• Hash Join
• Bitmapped Join

Question 26

Nested Loop Use Cases

Answer 26

Small inner table (<10^3) + Big outer table

Question 27

Merge Scan Use Cases

Answer 27

Requires sorting.
Useful when we have a previous or following sort operation.

Question 28

Hash Join

Answer 28

Useful for large DS

Question 29

Bitmapped Join

Answer 29

Useful for joining multiple tables into a big central table.

Question 30

Group By Types

Answer 30

• Sort Based: GB sort, GB no sort
• Hash Based: GB hash, GB no hash

Question 31

Selectivity

Answer 31

Fractions of rows selected from the original dataset

Question 32

Cardinality

Answer 32

Number of rows

Question 33

Optimization Exercise Steps

Answer 33

1. Writing algebra tree
2. Compute cardinalities
3. Select access paths without indexes
4. Select Join and GB Types
5. Create Indexes and new access paths
6. Evaluate possible GB anticipations

Question 34

Big / Small table threshold

Answer 34

10^3

Question 35

Good / Bad selectivity threshold

Answer 35

1/10

Question 36

Full Table Scans Use Cases

Answer 36

• No index
• Retrieval of large portion of the original table
• Full table + Filter

Question 37

Index Scan Types

Answer 37

• Index Unique Scans: Return one rowID. Useful for unique values.
• Index Range Scans: Data returned in ascending order. Avoid sorting for GB with same attribute.
• Index Full Scans: Avoids sorting for GB with same attribute.
• Fast Full Index Scans: Data is not ordered.
• Bitmap Indexes

Question 38

Bitmap Indexes Use Cases

Answer 38

For queries containing multiple WHERE clauses

Question 39

RowID Scan Use Cases

Answer 39

Retrieving a single row

Question 40

Serial Schedule

Answer 40

The actions of each transaction appear in sequence (T0 -> T1 -> T2)

Question 41

Schedule Equivalence Types

Answer 41

• View Equivalence
• Conflict Equivalence
• 2 phase locking
• Timestamp equivalence

Question 42

Serializable Schedule

Answer 42

Schedule that is equivalent to an arbitrary SERIAL schedule of the same transactions

Question 43

View Equivalence / Serializable

Answer 43

Procedure:
1. Detect read-froms and final writes

Equivalence:
- Same reads-from set
- Same final write set

Question 44

Conflict Equivalent / Serializable

Answer 44

Procedure:
1. Aj(x) is in conflict with Ai(x) if
- (I!=j)
- (x==x)
- RW, WR or WW conflict
- No other W(x) between them

Equivalence:
- Same conflict set
- Each conflict pair is in the same order

Serializable:
1. Create node graph with a node for each transaction
2. Draw arrows for Actions (from first action to last one)
3. If the graph is not cyclic then the schedule is serializable.

Question 45

2 Phase Locking