Quizmaster

Section 01

Complex development and numerous function calls are both disadvantages of compilation-based query processing models. to The five base operators of the relational algebra are selection, projection, intersect, union, and cartesian product.

01

Complex development and numerous function calls are both disadvantages of compilation-based query processing models.

Die richtige Antwort ist 'Falsch'. In compilation-based execution, complex code generation is a disadvantage, but it reduces iterator-style per-tuple function-call overhead rather than increasing it.

02

Which of the following processing models has the largest intermediate result sizes for pipelining operators?

Die richtige Antwort ist: operator-at-a-time.

Guided checkpoint

Wählen Sie eine Antwort:

03

The five base operators of the relational algebra are selection, projection, intersect, union, and cartesian product.

Die richtige Antwort ist 'Falsch'. The five base operators are selection (σ), projection (π), union (∪), set difference (-), and cartesian product (×).

Section 02

The set difference of two relations can be expressed using only set intersection operators. to A join is the composition of a set intersection and a selection operator.

01

The set difference of two relations can be expressed using only set intersection operators.

Die richtige Antwort ist 'Falsch'. Set difference cannot be expressed with intersection alone; it requires difference directly (A - B) or intersection plus complement (A ∩ B^c).

02

The grouping operator γ is used to filter tuples based on a condition.

Die richtige Antwort ist 'Falsch'. The grouping operator γ forms groups and computes aggregates (e.g., COUNT, SUM, AVG); filtering tuples is done by selection σ.

03

A join is the composition of a set intersection and a selection operator.

Die richtige Antwort ist 'Falsch'. A (theta-)join is selection over cartesian product: R ⋈_θ S = σ_θ(R × S), not intersection plus selection.

Section 03

Selection in relational algebra is used to retrieve only certain attributes from a relation. to Operator invocations by processing model

01

Selection in relational algebra is used to retrieve only certain attributes from a relation.

The selection operator filters rows; the projection operator selects which attributes exist in the output relation. Die richtige Antwort ist 'Falsch'.

02

Grouping, sort and join are all pipelining operators.

Die richtige Antwort ist 'Falsch'. Grouping and sort are classic blocking operators (they need to see more input before producing full output), so not all three listed operators are pipelining.

03

Operator invocations by processing model

Volcano: one tuple at a time (Scan=500000, Filter=500000, Aggregate=250000). Materialization: each operator invoked once per full materialized result (1, 1, 1). Vectorization: 500000/2000=250 batches for scan/filter, and 250000/2000=125 batches for aggregate.

Guided checkpoint

Given the following SQL query and execution steps, calculate the number of invocations per operator for each processing model (Volcano, Materialization, Vectorization).

SQL

SELECT MIN(e.salary)
FROM employee e
WHERE e.age > 35;

Execution steps

Scan table employee e.
Filter results on e.age > 35.
Aggregate tuples on MIN(e.salary).

Important assumptions

Table employee consists of 500000 rows.
The predicate (e.age > 35) has a selectivity factor of 0.5 (50% pass this filter).
The vectorization model uses a batch size of 2000 tuples (processes 2000 tuples at a time).
For the materialization model, intermediate results are fully materialized.

Section 04

Is the following law valid? to Select the best join order (the one with the lowest cost).

01

Is the following law valid?

Die richtige Antwort ist 'Falsch'. The valid distributive law is σ_c(R ∪ S) = σ_c(R) ∪ σ_c(S). The given right side leaves S unfiltered, so it can include tuples that do not satisfy c.

Guided checkpoint

$σ_c(R ∪ S) = σ_c(R) ∪ S$

Assume relations R and S are sets.

02

Cross product detection in join order selection

(T ⋈ U) ⋈ R: False (T and U join on a; then result joins R on b, so no cross product) (T ⋈ S) ⋈ R: False (T and S join on d; then result joins R on c) (T ⋈ R) ⋈ S: True (T and R share no attribute, so first step is a cross product) (U ⋈ S) ⋈ T: True (U and S share no attribute, so first step is a cross product) (T ⋈ R) ⋈ U: True (T and R share no attribute, so first step is a cross product) (U ⋈ R) ⋈ S: False (U and R join on b; then result joins S on c)

Guided checkpoint

Consider four relations R(b, c), S(c, d), T(a, d), and U(a, b). Each relation has 1000 tuples. The relations have the following attribute domain cardinalities:

R(b, c)	S(c, d)	T(a, d)	U(a, b)
		V(T, a) = 250	V(U, a) = 100
V(R, b) = 40			V(U, b) = 20
V(R, c) = 100	V(S, c) = 200
	V(S, d) = 200	V(T, d) = 1000

For each join order: Can it be ignored because it contains a cross product when determining the optimal join order?

03

Select the best join order (the one with the lowest cost).

Die richtige Antwort ist: ((T ⋈ U) ⋈ S) ⋈ R. Fastest way: 1. Use |A ⋈ B| ≈ (|A|*|B|) / max(V(A,x), V(B,x)) for the join attribute x. 2. All base relations have 1000 tuples, so first-join estimates are quick: - |R ⋈ U| on a = 1,000,000 / max(50,20) = 20,000 - |S ⋈ T| on b = 1,000,000 / max(400,100) = 2,500 - |T ⋈ U| on c = 1,000,000 / max(1000,200) = 1,000 3. Eliminate options that start with large first intermediates (a and c start with R ⋈ U = 20,000). 4. Compare b vs d using only the first two intermediates (cost definition excludes base and final): - b: (S ⋈ T)=2,500, then ⋈U on c stays about 2,500 => cost ≈ 2,500 + 2,500 = 5,000 - d: (T ⋈ U)=1,000, then ⋈S on b gives about 2,500 => cost ≈ 1,000 + 2,500 = 3,500 5. Lower intermediate cost => choose d.

Guided checkpoint

Consider four relations R(a, d), S(b, d), T(b, c), and U(a, c). Each relation has 1000 tuples. The relations have the following attribute domain cardinalities:

R(a, d)	S(b, d)	T(b, c)	U(a, c)
V(R, a) = 50			V(U, a) = 20
	V(S, b) = 400	V(T, b) = 100
		V(T, c) = 1000	V(U, c) = 200
V(R, d) = 500	V(S, d) = 40

Note: Cost refers to the sum of all intermediate result sizes (excluding input relations and the final result).

Wählen Sie eine Antwort:

Section 05

Join-order cost to Join cardinality

01

Join-order cost

Die richtige Antwort ist: 14000

Guided checkpoint

Consider four relations R(b, c), S(a, b), T(c, d), and U(a, d). Each relation has 1000 tuples. The relations have the following attribute domain cardinalities:

R(b, c)	S(a, b)	T(c, d)	U(a, d)
	V(S, a) = 40		V(U, a) = 10
V(R, b) = 1000	V(S, b) = 200
V(R, c) = 400		V(T, c) = 40
		V(T, d) = 10	V(U, d) = 250

What is the cost of the following join order ((T ⋈ U) ⋈ R) ⋈ S?

Note: Cost refers to the sum of all intermediate result sizes (excluding input relations and the final result).

$Cost(((T ⋈ U) ⋈ R) ⋈ S) =$

02

Join with selection cardinality

Path of Calculation: 1. First apply the selection on S: |σ_{s2=89}(S)| = T(S) * (1 / (2 * V(S,s2))) = 450 * (1 / (2 * 10)) = 22.5. 2. Use the foreign-key join property (R.s1 references S.s1): the fraction of S rows kept by the selection is 22.5 / 450 = 0.05. 3. The same fraction of R tuples is expected to match after the join: |R ⋈ σ_{s2=89}(S)| = T(R) * 0.05 = 5000 * 0.05 = 250. Die richtige Antwort ist: 250

Guided checkpoint

Given are the tables R(r1, s1) and S(s1, s2). R.s1 is a foreign key to S.s1. The tables have the following tuple and attribute domain cardinalities:

T(R) = 5000
T(S) = 450
V(S, s2) = 10

Assume that 1 / (2 * V(R, f)) of the tuples satisfy the comparison when an attribute is equated to a constant (e.g., σ_{f=15}).

How many tuples are selected by the join R ⋈ σ_{s2=89}(S)?

03

Join cardinality

Path of Calculation: 1. In

U(b,c) \bowtie T(a,d)

there is no common attribute, so this step is a cross product:

T(U \bowtie T) = T(U) * T(T) = 1000 * 1000 = 1{,}000{,}000

. 2. Now join with

S(a,b)

on attributes

a

and

b

:

T((U \bowtie T) \bowtie S) = \frac{T(U \bowtie T) * T(S)}{\max(V(U\bowtie T,a),V(S,a)) * \max(V(U\bowtie T,b),V(S,b))}

. 3. Distinct values in

U\bowtie T

:

V(U\bowtie T,a)=V(T,a)=50

, and

V(U\bowtie T,b)=V(U,b)=50

. 4. Plug in values:

\frac{1{,}000{,}000 * 1000}{\max(50,10) * \max(50,250)} = \frac{1{,}000{,}000{,}000}{50 * 250} = \frac{1{,}000{,}000{,}000}{12{,}500} = 80{,}000

. Die richtige Antwort ist: 80000

Guided checkpoint

Consider four relations R(c, d), S(a, b), T(a, d), and U(b, c). Each relation has 1000 tuples. The relations have the following attribute domain cardinalities:

R(c, d)	S(a, b)	T(a, d)	U(b, c)
	V(S, a) = 10	V(T, a) = 50
	V(S, b) = 250		V(U, b) = 50
V(R, c) = 100			V(U, c) = 200
V(R, d) = 100		V(T, d) = 10

What is the cardinality of the following join (U ⋈ T) ⋈ S?

$T((U ⋈ T) ⋈ S) =$

Section 06

Estimated natural join cardinality to Selection cardinality with independent predicates (OR)

01

Estimated natural join cardinality

Path of Calculation: 1. Compute the first join on common attribute

a

:

T(R \bowtie S) = \frac{T(R) * T(S)}{\max(V(R,a),V(S,a))} = \frac{72000 * 14400}{\max(400,90)} = \frac{1{,}036{,}800{,}000}{400} = 2{,}592{,}000

. 2. For the intermediate relation

(R\bowtie S)

use standard estimates:

V(R\bowtie S,a)=\min(V(R,a),V(S,a))=\min(400,90)=90

, and

V(R\bowtie S,e)=V(S,e)=80

(because

e

comes from

S

only in this step). Why min on

a

? In an equi-join, output

a

-values must exist on both sides, so the distinct count cannot exceed the smaller side. 3. Join

(R\bowtie S)

with

U(a,e)

on both common attributes

a

and

e

:

T((R\bowtie S)\bowtie U) = \frac{T(R\bowtie S)*T(U)}{\max(V(R\bowtie S,a),V(U,a)) * \max(V(R\bowtie S,e),V(U,e))}

= \frac{2{,}592{,}000 * 10{,}000}{\max(90,40) * \max(80,500)} = \frac{25{,}920{,}000{,}000}{90 * 500}

= \frac{25{,}920{,}000{,}000}{45{,}000} = 576{,}000

. Die richtige Antwort ist: 576000

Guided checkpoint

Consider the natural join R(a, c) ⋈ S(a, b, e) ⋈ U(a, e), and the following important statistics:

R(a, c)	S(a, b, e)	U(a, e)
T(R) = 72000	T(S) = 14400	T(U) = 10000
V(R, a) = 400	V(S, a) = 90	V(U, a) = 40
	V(S, b) = 40
V(R, c) = 450
	V(S, e) = 80	V(U, e) = 500

What is the estimated cardinality of the natural join (the join on all common attributes)?

02

Selection cardinality with independent predicates (AND)

Path of Calculation: 1. For not-equals, the failed fraction is

5 / V(R,f)

. 2. Predicate

a \neq 50

: pass fraction

= 1 - 5/80 = 75/80 = 0.9375

. 3. Predicate

b \neq 37

: pass fraction

= 1 - 5/100 = 95/100 = 0.95

. 4. Predicates are independent and combined with AND: combined pass fraction

= 0.9375 * 0.95 = 0.890625

. 5. Apply to table cardinality:

T(\sigma_{a\neq50 \land b\neq37}(R)) = 128000 * 0.890625 = 114000

. Die richtige Antwort ist: 114000

Guided checkpoint

Given is the table R(a, b) with the following tuple and attribute domain cardinalities:

T(R) = 128000
V(R, a) = 80
V(R, b) = 100

Assume that:

1 / (3 * V(R, f)) of the tuples satisfy the comparison when an attribute is equated to a constant (e.g., σ_{f=15})
Inequality (e.g., σ_{f<90}) tends to retrieve one-third of the tuples
For not equals (e.g., σ_{f≠90}), a fraction of 5 / V(R, f) number of the tuples will fail to meet the condition
Predicates are independent

Note, single assumptions may deviate from the ones discussed during the lecture.

How many tuples are selected by the selection $σ_{a≠50 \text{ AND } b≠37}(R)$ ?

03

Selection cardinality with independent predicates (OR)

Path of Calculation: 1. For not-equals, failed fraction is

6 / V(R,f)

, so for

a \neq 19

:

p(A)=1-6/70=64/70=0.9142857

. 2. For equals, pass fraction is

1 / V(R,f)

, so for

b = 28

:

p(B)=1/30=0.0333333

. 3. Predicates are independent and connected with OR:

p(A \lor B)=p(A)+p(B)-p(A)p(B)

=0.9142857+0.0333333-(0.9142857*0.0333333)=0.917142857

. 4. Apply to base cardinality:

T(\sigma_{a\neq19 \lor b=28}(R))=37800*0.917142857=34668

. Die richtige Antwort ist: 34668

Guided checkpoint

Given is the table R(a, b) with the following tuple and attribute domain cardinalities:

T(R) = 37800
V(R, a) = 70
V(R, b) = 30

Assume that:

1 / V(R, f) of the tuples satisfy the comparison when an attribute is equated to a constant (e.g., σ_{f=15})
Inequality (e.g., σ_{f<90}) tends to retrieve half of the tuples
For not equals (e.g., σ_{f≠90}), a fraction of 6 / V(R, f) number of the tuples will fail to meet the condition
Predicates are independent

Note, single assumptions may deviate from the ones discussed during the lecture.

How many tuples are selected by the selection $σ_{a≠19 \text{ OR } b=28}(R)$ ?

Section 07

Which of the following is a valid Condition Rule in the grammar for simple subset of SQL? to A schedule with interleaved operations from different transactions can have multiple conflict-equivalent serial schedules.

01

Which of the following is a valid Condition Rule in the grammar for simple subset of SQL?

<Condition> ::= <Attribute> = <Attribute>: True (equality comparison is a standard condition form) <Condition> ::= <Attribute> PROCEEDS <Pattern>: False (PROCEEDS is not a valid SQL condition keyword) <Condition> ::= <Attribute> LIKE <PATTERN>: True (LIKE is a standard pattern-matching predicate) <Condition> ::= <Attribute> AVAILABLE <Pattern>: False (AVAILABLE is not a valid SQL condition keyword)

02

A transaction is a single unit of work which should be executed fully or not at all.

Die richtige Antwort ist 'Wahr'. This is exactly the atomicity property: a transaction is an all-or-nothing unit of work.

03

A schedule with interleaved operations from different transactions can have multiple conflict-equivalent serial schedules.

Die richtige Antwort ist 'Wahr'. If the precedence graph has more than one valid topological order, the same interleaved schedule is conflict-equivalent to multiple serial schedules.

Section 08

Complete precedence graph by choosing correct entries from dropdowns. to The following schedule is conflict-serializable:

01

Complete precedence graph by choosing correct entries from dropdowns.

Correct assignment: A=3, B=2, C=4, D=1. Build precedence-graph edges from conflicts (same item, different transactions, at least one write): - W2(A) before R1(A) => T2 -> T1 - W2(A) (and also R2(A)) before W4(A) => T2 -> T4 - R1(A) before W4(A) => T1 -> T4 - R3(B) before W4(B) => T3 -> T4 So the graph edges are: 2 -> 1, 2 -> 4, 1 -> 4, 3 -> 4. The fixed drawing has edges: top-left -> bottom-left, top-right -> bottom-right, top-right -> bottom-left, bottom-right -> bottom-left. Matching these gives: top-left=3, top-right=2, bottom-right=1, bottom-left=4. Equivalent node labels: A=3, B=2, C=4, D=1.

Guided checkpoint

Consider the following schedule: W2(A), R1(A), W3(C), R2(A), R3(B), W4(A), W4(B)

Precedence graph layout with four labeled node positions and fixed directed edges

02

Do the following operations conflict or not?

W1(A) and W2(B): Do not conflict. Conflict requires same data item and at least one write; here both operations write different items (A vs. B).

Guided checkpoint

Let T1 and T2 be two transactions that are contained in an interleaved schedule.

Let A and B be two different database elements.

Select the appropriate option for each operation pair.

03

The following schedule is conflict-serializable:

Die richtige Antwort ist 'Falsch'. The precedence graph contains a cycle (e.g., T2 -> T3 from C-conflicts and T3 -> T2 from B-conflicts), so the schedule is not conflict-serializable.

Guided checkpoint

W2(C), W1(A), R3(B), W4(B), R2(C), W3(C), R3(A), W2(B)

Section 09

Strict two-phase locking (2PL) leads to lower parallelization and lower throughput (compared to normal 2PL). to The following schedule is possible under strict two-phase locking (S2PL): R3(C), W3(B), R3(D), R3(D), R1(D), R2(C), R1(A), W1(C)

01

Strict two-phase locking (2PL) leads to lower parallelization and lower throughput (compared to normal 2PL).

Die richtige Antwort ist 'Wahr'. Strict 2PL keeps exclusive locks until commit/abort, which reduces lock release opportunities and therefore lowers concurrency and throughput versus basic 2PL.

02

Lock compatibility matrix with Increment (I) and Multiplication (M)

Both graded entries are No: - Increment (I) with Multiplication (M): No - Multiplication (M) with Increment (I): No Reason: Applying increment and multiplication concurrently to the same item is not commutative in general: -

(x + c) * k = xk + ck

-

(x * k) + c = xk + c

These are equal only in special cases, so the lock modes are incompatible.

Guided checkpoint

Consider that in addition to the shared (S) and exclusive (X) locks, your database system has two more locks:

Increment (I) - increments a database element by a constant.
Multiplication (M) - multiplies a database element by a constant.

Fill in the appropriate value for the drop-downs in the compatibility matrix (N.A. stands for not applicable).

	Shared (S)	Exclusive (X)	Increment (I)	Multiplication (M)
Shared (S)	Yes	No	N.A.	N.A.
Exclusive (X)	No	No	N.A.	N.A.
Increment (I)	N.A.	N.A.	N.A.	?
Multiplication (M)	N.A.	N.A.	?	N.A.

03

The following schedule is possible under strict two-phase locking (S2PL): R3(C), W3(B), R3(D), R3(D), R1(D), R2(C), R1(A), W1(C)

Die richtige Antwort ist 'Wahr'. The schedule can be produced under S2PL if transactions commit after their last operation and release locks then; no lock request in the sequence requires an impossible early release. Fast hint (quickest method): 1. Track only writes first (they force X-locks held until commit in S2PL). 2. Mark items currently X-locked and the owning transaction. 3. Scan left to right: if another transaction needs R/W on an X-locked item before owner's last action, schedule would be impossible. 4. If no such blocking conflict appears, assume commit at each transaction's last occurrence and the schedule is feasible.

Section 10

Timestamp-based scheduling table completion to Match the failure below to the type of failure

01

Timestamp-based scheduling table completion

Correct missing entries: - W1(B): WT(B)=250, C(B)=FALSE - W1(A): WT(A)=250, C(B)=TRUE Conclusive reasoning: 1.

R1(B)

sets

RT(B)=250

,

R2(A)

sets

RT(A)=225

,

R3(C)

sets

RT(C)=150

. 2.

W1(B)

is allowed (timestamp 250 is not older than current timestamps), so

WT(B)=250

. T1 has not committed yet at this row, therefore

C(B)=FALSE

. 3.

W1(A)

is also allowed, so

WT(A)=250

. By assumption, T1's last occurrence includes commit, thus after this step T1 is committed and its written items become committed ->

C(B)=TRUE

(and

C(A)=TRUE

as shown in the table text). 4.

W2(C)

sets

WT(C)=225

,

C(C)=TRUE

(T2 commits at last occurrence). 5.

W3(A)

must rollback because T3 (timestamp 150) tries to write an item with newer write timestamp (

WT(A)=250

). Fast hint (quickest method): 1. Process schedule left-to-right and maintain only three values per item:

RT

,

WT

, and

C

. 2. For each read: update

RT(item)=\max(RT(item),TS(T_i))

. 3. For each write: do a quick timestamp check first (if too old vs current timestamps -> rollback), otherwise set

WT(item)=TS(T_i)

and keep/flip commit bits as commits occur. 4. Use the exam assumption "last occurrence includes commit" immediately when a transaction appears for the last time.

Guided checkpoint

Consider that you have three transactions, T1, T2, and T3 that operate on three database elements A, B, and C. The timestamps of the transactions are as follows: T1 = 250, T2 = 225, T3 = 150, while the initial values of the read and write timestamps of the three database elements is 0.

Consider the following schedule: R1(B), R2(A), R3(C), W1(B), W1(A), W2(C), W3(A)

Fill out the missing values in the table below following the algorithm in the Complete Book (Section 18.8.4 The Rules for Timestamp-Based Scheduling).

Assumptions

The last occurrence of a transaction in the schedule also includes the commit request to the scheduler.
RT(X) refers to the read timestamp of a database element X.
WT(X) refers to the write timestamp of a database element X.
C(X) refers to the commit bit of a database element X.

02

Multi-version Concurrency Control (MVCC) keeps only a single version of all data items.

Die richtige Antwort ist 'Falsch'. MVCC explicitly maintains multiple versions of data items so readers can access a consistent snapshot while writers create new versions.

03

Match the failure below to the type of failure

Integrity Constraint Violation -> Transaction Failure. Reason: A constraint violation invalidates the current transaction's effects and causes that transaction to abort. It does not by itself imply a system crash, media failure, or communication failure.

Section 11

Force policy means that the database system imposes a condition that all updates by the transaction should be written to disk just before the transaction commits. to The analysis phase in recovery starts from the last checkpoint in the log.

01

Force policy means that the database system imposes a condition that all updates by the transaction should be written to disk just before the transaction commits.

Die richtige Antwort ist 'Wahr'. Under a force policy, all pages modified by a committing transaction are forced to disk at commit time.

02

Write-Ahead Logging (WAL) ensures atomicity but not integrity.

Die richtige Antwort ist 'Wahr'. ACID recap: - Atomicity: all operations of a transaction happen or none happen. - Consistency: every committed transaction leaves the database in a valid state w.r.t. rules/constraints. - Isolation: concurrent transactions should not interfere as if executed serially. - Durability: once committed, changes survive crashes. Why this statement is True: WAL primarily enforces recovery ordering (log record before data page write), which supports Atomicity (via undo/redo) and Durability. It does not by itself guarantee Integrity/Consistency rules such as key constraints, business rules, or semantic correctness. What "integrity" implies here: Integrity means the data still satisfies defined correctness constraints after execution (e.g., PK/FK, CHECK, domain rules). WAL alone cannot guarantee that; constraints, transaction logic, and concurrency control are also needed.

03

The analysis phase in recovery starts from the last checkpoint in the log.

Die richtige Antwort ist 'Wahr'. In ARIES-style recovery, analysis begins from the most recent checkpoint context and scans forward to reconstruct transaction and dirty-page state.

Section 12

ARIES analysis pass: fill transaction table and dirty page table entries to ARIES undo pass actions for UPDATE log records

01

ARIES analysis pass: fill transaction table and dirty page table entries

After analysis (starting at LSN 7): Transaction table -> T1: No Entry, T2: 14, T3: 9. Dirty page table -> P1: 4, P2: 5, P3: 8. How to fill the Dirty Page Table (important rule): - recLSN(page) = LSN of the FIRST log record that made that page dirty. - If a page is already in DPT, later updates do NOT change its recLSN. Step-by-step for this log: 1. Initial DPT from checkpoint state is given as: P1->4, P2->5. 2. LSN 8 updates page 3. Page 3 is not yet in DPT -> add P3 with recLSN=8. 3. LSN 9 updates page 2. Page 2 already in DPT -> keep recLSN(P2)=5. 4. LSN 13 updates page 3 again. Page 3 already in DPT -> keep recLSN(P3)=8. 5. LSN 14 updates page 1. Page 1 already in DPT -> keep recLSN(P1)=4. That is why the final DPT is exactly: P1=4, P2=5, P3=8.

Guided checkpoint

Consider the following log records. The table contains the log sequence number (LSN), the transaction ID (TID), the previous log sequence number of the transaction (prevLSN), and the action of the log entry. The format of the UPDATE action is: (Page ID, Element ID, Old value, New value).

LSN	TID	prevLSN	ACTION
1	1		BEGIN_TRANSACTION
2	2		BEGIN_TRANSACTION
3	3		BEGIN_TRANSACTION
4	1	1	UPDATE (1, 1, "a", "A")
5	2	2	UPDATE (2, 2, "b", "B")
6	1	4	UPDATE (2, 3, "c", "C")
7			BEGIN_CHECKPOINT
8	1	6	UPDATE (3, 4, "d", "D")
9	3	3	UPDATE (2, 5, "e", "E")
10	1	8	COMMIT
11	1	10	END_TRANSACTION
12			END_CHECKPOINT
13	2	5	UPDATE (3, 6, "f", "F")
14	2	13	UPDATE (1, 7, "g", "G")

The recovery process starts at LSN 7 with the following transaction table and dirty page table.

Transaction table (initial)

TID	lastLSN
1	6
2	5
3	3

Dirty page table (initial)

PID	recLSN
1	4
2	5

In the transaction and dirty page tables below, enter the LSN for each transaction/page after the analysis pass. Select "No Entry" if a transaction/page is not in the transaction/dirty page table.

02

Loser transactions refer to uncommitted transactions.

Die richtige Antwort ist 'Wahr'. In recovery terminology, loser transactions are those active at crash time without a commit record, i.e., uncommitted transactions that must be undone.

03

ARIES undo pass actions for UPDATE log records

Correct undo-pass actions: - LSN 6 -> Undo - LSN 8 -> Undo - LSN 9 -> Ignore - LSN 13 -> Undo - LSN 14 -> Undo Conclusive reasoning: 1. From analysis, T2 commits (LSN 10/11) and is a winner; T1 and T3 are losers. 2. Undo processes loser transactions backward along prevLSN chains. 3. For T1, relevant UPDATEs in the asked rows are LSN 8 and LSN 6 -> both must be undone. 4. For T3, asked UPDATEs are LSN 14 and LSN 13 -> both must be undone. 5. LSN 9 belongs to committed T2 -> ignore in undo.

Guided checkpoint

Consider the following log records. The table contains the log sequence number (LSN), the transaction ID (TID), the previous log sequence number of the transaction (prevLSN), and the action of the log entry. The format of the UPDATE action is: (Page ID, Element ID, Old value, New value).

The recovery process starts at LSN 7 with the following transaction table and dirty pages table.

Transaction table

TID	lastLSN
1	6
2	5
3	3

Dirty page table

PID	recLSN
1	4
2	5

Select the action taken during the undo passes for the UPDATE actions in the drop-down menus in the log table below.

Section 13

The redo pass in recovery goes forward in the log from the last checkpoint (or the first relevant log sequence number identified during the analysis pass). to What is the purpose of checkpoints for logging?

01

The redo pass in recovery goes forward in the log from the last checkpoint (or the first relevant log sequence number identified during the analysis pass).

Die richtige Antwort ist 'Wahr'. Redo scans forward from the restart point (typically derived from checkpoint analysis, often recLSN-based) to reapply needed updates.

02

ARIES redo pass actions for UPDATE log records

Correct redo-pass actions: - LSN 4 -> Ignore - LSN 5 -> Ignore - LSN 6 -> Redo - LSN 8 -> Redo - LSN 9 -> Redo What DPT means: - DPT = Dirty Page Table. - For each dirty page it stores recLSN = first LSN that made that page dirty. Redo criteria (ARIES) for an UPDATE at LSN i: 1. If i is before redo start -> Ignore. 2. If page is not in DPT -> Ignore. 3. If recLSN(page) > i -> Ignore. 4. If pageLSN(page) >= i -> Ignore. 5. Otherwise -> Redo. Applied here: - DPT has P1 with recLSN=6, so redo starts at LSN 6. - Therefore LSN 4 and 5 are ignored. - LSN 6, 8, 9 are in redo range and pass checks. - Given assumption pageLSN < LSN, those three are redone. Checkpoint note: - BEGIN/END_CHECKPOINT marks checkpoint boundaries, but redo start is determined by DPT recLSN (so work can include records before BEGIN_CHECKPOINT if needed).

Guided checkpoint

Consider the following log records. The table contains the log sequence number (LSN), the transaction ID (TID), the previous log sequence number of the transaction (prevLSN), and the action of the log entry. The format of the UPDATE action is: (Page ID, Element ID, Old value, New value).

The recovery process starts at LSN 7 with the following transaction table and dirty pages table.

Transaction table

TID	lastLSN
1	4
2	6
3	3

Dirty page table

PID	recLSN
1	6

Select the action taken during the redo passes for the UPDATE actions in the log table below. Assume that pageLSN is always less than LSN.

03

What is the purpose of checkpoints for logging?

Die richtige Antwort ist: Reduce the number of log-records to process during recovery. Reason: A checkpoint stores recovery state so restart can begin from a later point instead of scanning the entire log history. It does not directly provide isolation guarantees.

Guided checkpoint

Wählen Sie eine Antwort:

Section 14

Amdahl's Law is more optimistic than Gustafson's Law when predicting speedup in parallel computing. to Which parallel architecture does a multiprocessor laptop use?

01

Amdahl's Law is more optimistic than Gustafson's Law when predicting speedup in parallel computing.

Die richtige Antwort ist 'Falsch'. Amdahl assumes fixed problem size and is typically more pessimistic; Gustafson assumes scaled workload and is usually more optimistic.

02

According to Amdahl's Law, in a best-case scenario, the theoretical speedup of a program is equal to the number of processors available.

Die richtige Antwort ist 'Wahr'. In the best case the serial fraction is 0, so Amdahl gives speedup S = 1 / ((1-p)+p/n) = n (equal to processor count).

03

Which parallel architecture does a multiprocessor laptop use?

Die richtige Antwort ist: Shared-memory. Reason: A multiprocessor laptop has CPUs/cores that share the same physical main memory and cache-coherent address space, which matches the shared-memory architecture model.

Guided checkpoint

Wählen Sie eine Antwort:

Section 15

Besides round robin, hash-based partitioning also guarantees an equal amount of tuples per partition. to Vertical partitioning is most useful when the full table is frequently used in queries.

01

Besides round robin, hash-based partitioning also guarantees an equal amount of tuples per partition.

Die richtige Antwort ist 'Falsch'. Hash partitioning balances data only statistically; skewed key distributions can still create uneven partition sizes.

02

If a table is range-partitioned based on a subset of its attributes, range queries involving those attributes can be optimized by processing only the relevant partitions.

Die richtige Antwort ist 'Wahr'. When predicates align with range-partition keys, partition pruning allows scanning only matching partitions.

03

Vertical partitioning is most useful when the full table is frequently used in queries.

Die richtige Antwort ist 'Falsch'. Vertical partitioning helps when queries touch only subsets of columns; if full rows are frequently needed, extra reconstruction joins make it less useful.

Section 16

Which of the following correctly describes a scenario where both replication and fragmentation are used? to Inter-query parallelism is more suited for analytical workloads (OLAP) than transactional workloads (OLTP).

01

Which of the following correctly describes a scenario where both replication and fragmentation are used?

Die richtige Antwort ist: A relation is partitioned into multiple fragments, and identical replicas of each fragment are stored at different sites. Reason: Fragmentation splits data into pieces, while replication keeps multiple copies for availability/performance. The correct combined scenario must include both properties simultaneously.

Guided checkpoint

Wählen Sie eine Antwort:

02

Inter-operator parallelism allows multiple operators to run concurrently.

Die richtige Antwort ist 'Wahr'. Inter-operator parallelism runs different operators (e.g., scan and join stages) at the same time on separate resources.

03

Inter-query parallelism is more suited for analytical workloads (OLAP) than transactional workloads (OLTP).

Die richtige Antwort ist 'Falsch'. Inter-query parallelism is typically strongest for OLTP-style workloads with many independent queries; OLAP usually relies more on intra-query/operator parallelism.

Section 17

The transaction coordinator manages the start, execution, and termination of transactions originating from a particular site.

01

The transaction coordinator manages the start, execution, and termination of transactions originating from a particular site.

Die richtige Antwort ist 'Wahr'. In distributed DBMS architecture, the transaction coordinator at a site is responsible for transactions initiated at that site, including lifecycle management and coordination.

What you will be able to explain

Complex development and numerous function calls are both disadvantages of compilation-based query processing models. to The five base operators of the relational algebra are selection, projection, intersect, union, and cartesian product.

Complex development and numerous function calls are both disadvantages of compilation-based query processing models.

Which of the following processing models has the largest intermediate result sizes for pipelining operators?

The five base operators of the relational algebra are selection, projection, intersect, union, and cartesian product.

The set difference of two relations can be expressed using only set intersection operators. to A join is the composition of a set intersection and a selection operator.

The set difference of two relations can be expressed using only set intersection operators.

The grouping operator γ is used to filter tuples based on a condition.

A join is the composition of a set intersection and a selection operator.

Selection in relational algebra is used to retrieve only certain attributes from a relation. to Operator invocations by processing model

Selection in relational algebra is used to retrieve only certain attributes from a relation.

Grouping, sort and join are all pipelining operators.

Operator invocations by processing model

SQL

Execution steps

Important assumptions

Is the following law valid? to Select the best join order (the one with the lowest cost).

Is the following law valid?

Cross product detection in join order selection

Select the best join order (the one with the lowest cost).

Join-order cost to Join cardinality

Join-order cost

Join with selection cardinality

Join cardinality

Estimated natural join cardinality to Selection cardinality with independent predicates (OR)

Estimated natural join cardinality

Selection cardinality with independent predicates (AND)

Assume that:

Selection cardinality with independent predicates (OR)

Assume that:

Which of the following is a valid Condition Rule in the grammar for simple subset of SQL? to A schedule with interleaved operations from different transactions can have multiple conflict-equivalent serial schedules.

Which of the following is a valid Condition Rule in the grammar for simple subset of SQL?

A transaction is a single unit of work which should be executed fully or not at all.

A schedule with interleaved operations from different transactions can have multiple conflict-equivalent serial schedules.

Complete precedence graph by choosing correct entries from dropdowns. to The following schedule is conflict-serializable:

Complete precedence graph by choosing correct entries from dropdowns.

Do the following operations conflict or not?

The following schedule is conflict-serializable:

Strict two-phase locking (2PL) leads to lower parallelization and lower throughput (compared to normal 2PL). to The following schedule is possible under strict two-phase locking (S2PL): R3(C), W3(B), R3(D), R3(D), R1(D), R2(C), R1(A), W1(C)

Strict two-phase locking (2PL) leads to lower parallelization and lower throughput (compared to normal 2PL).

Lock compatibility matrix with Increment (I) and Multiplication (M)

The following schedule is possible under strict two-phase locking (S2PL): R3(C), W3(B), R3(D), R3(D), R1(D), R2(C), R1(A), W1(C)

Timestamp-based scheduling table completion to Match the failure below to the type of failure

Timestamp-based scheduling table completion

Assumptions

Multi-version Concurrency Control (MVCC) keeps only a single version of all data items.

Match the failure below to the type of failure

Force policy means that the database system imposes a condition that all updates by the transaction should be written to disk just before the transaction commits. to The analysis phase in recovery starts from the last checkpoint in the log.

Force policy means that the database system imposes a condition that all updates by the transaction should be written to disk just before the transaction commits.

Write-Ahead Logging (WAL) ensures atomicity but not integrity.

The analysis phase in recovery starts from the last checkpoint in the log.

ARIES analysis pass: fill transaction table and dirty page table entries to ARIES undo pass actions for UPDATE log records

ARIES analysis pass: fill transaction table and dirty page table entries

Transaction table (initial)

Dirty page table (initial)

Loser transactions refer to uncommitted transactions.

ARIES undo pass actions for UPDATE log records

Transaction table

Dirty page table

The redo pass in recovery goes forward in the log from the last checkpoint (or the first relevant log sequence number identified during the analysis pass). to What is the purpose of checkpoints for logging?

The redo pass in recovery goes forward in the log from the last checkpoint (or the first relevant log sequence number identified during the analysis pass).

ARIES redo pass actions for UPDATE log records

Transaction table

Dirty page table

What is the purpose of checkpoints for logging?

Amdahl's Law is more optimistic than Gustafson's Law when predicting speedup in parallel computing. to Which parallel architecture does a multiprocessor laptop use?

Amdahl's Law is more optimistic than Gustafson's Law when predicting speedup in parallel computing.

According to Amdahl's Law, in a best-case scenario, the theoretical speedup of a program is equal to the number of processors available.

Which parallel architecture does a multiprocessor laptop use?

Besides round robin, hash-based partitioning also guarantees an equal amount of tuples per partition. to Vertical partitioning is most useful when the full table is frequently used in queries.

Besides round robin, hash-based partitioning also guarantees an equal amount of tuples per partition.

If a table is range-partitioned based on a subset of its attributes, range queries involving those attributes can be optimized by processing only the relevant partitions.

Vertical partitioning is most useful when the full table is frequently used in queries.

Which of the following correctly describes a scenario where both replication and fragmentation are used? to Inter-query parallelism is more suited for analytical workloads (OLAP) than transactional workloads (OLTP).

Which of the following correctly describes a scenario where both replication and fragmentation are used?

Inter-operator parallelism allows multiple operators to run concurrently.

Inter-query parallelism is more suited for analytical workloads (OLAP) than transactional workloads (OLTP).

The transaction coordinator manages the start, execution, and termination of transactions originating from a particular site.

The transaction coordinator manages the start, execution, and termination of transactions originating from a particular site.

Turn understanding into recall.