lec exam Flashcards

Question

What is the cost of the improved Block Nested Loop join algorithm?

Answer 1

``` best case: B(R)+B(S) general case (B(R) / (M-1)) * B(S) + B(R) ```

Answer 2

B(R) + T(R) * c | c~=T(s)/V(s,A)

Answer 3

cost of sorting + B(S) + B(R)

Answer 4

2*(B(R)+B(S)) + (BR()+B(S))

Answer 5

Materialization: one operation at a time, materialize intermediate results for subsequent use Pipeline: evaluate several operations simultaneously, no need to store temporary results

Answer 6

https://imgur.com/a/uFVDigk

Answer 7

A composite index is an index on multiple columns. ? ?

Answer 8

Table partitioning is a way to divide a large table into smaller, more manageable parts without having to create separate tables for each part.

Answer 9

Range, hash, list partitioning.

Answer 10

An IOT(index organized table) must contain a primary key. Rows are accessed via a logical rowid and not a physical rowid like in heap-organized tables. An IOT cannot be in a cluster. An IOT cannot contain a column of LONG data type. You cannot modify an IOT index property using ALTER INDEX (error ORA-25176), you must use an ALTER TABLE instead.

Answer 11

It specifies how many records that can be selected from a node.

Answer 12

``` Relational algebra level: transformations good transformations Detailed query plan level: estimate costs generate and compare plans ```

Answer 13

all_rows: first compute, then return first_rows: return while computing(if possible)

Answer 14

Stores plan in Plan_Table

Answer 15

row-sources and operations

Answer 16

- All blocks read sequentially into buffer cache | - Per block: extract + return all rows

Answer 17

Traverses the node blocks to locate correct leaf block Searches value in leaf block (if not found => done) Returns rowid to parent row-source

Answer 18

Traverses the node blocks to locate most left leaf block Searches 1st occurrence of value in leaf block Returns rowid to parent row-source Continues on to next occurrence of value in leaf block

Answer 19

Average number of blocks to access a single value | Used to rank multiple available range scans

Answer 20

Explain-plan: give insight before execution | Tracing: give insight in actual execution

Answer 21

Force optimizer to pick specific alternative

Answer 22

We can periodically generate statistics

Answer 23

Consistent state: satisfies all constraints | Consistent DB: DB in consistent state

Answer 24

collection of actions that preserve consistency

Answer 25

Transaction bug (incomplete transaction) DBMS bug (some process) Hardware failure Data sharing

Answer 26

System crash - memory lost - cpu halts, resets

Answer 27

1. The disk blocks 2. The shared main memory 3. The local address space of a Transaction

Answer 28

Input (x): block containing x -> memory Output (x): block containing x-> disk Read (x,t): do input(x) if necessary t

Answer 29

execute all actions of a transaction or none at all

Answer 30

1) For every action generate undo log record (containing old value) 2) Before x is modified on disk, log records belonging to x must be on disk (write ahead logging: WAL) 3) Before commit is flushed to log, all writes of transaction must be reflected on disk

Answer 31

1. The log records indicating changed database elements. 2. The changed database elements themselves. 3. The COMMIT log record.

Answer 32

``` 1) Let S = set of transactions with in log, but no (or ) record in log (2) For each in log, in reverse order (latest  earliest) do: - if Ti  S then - write (X, v) - output (X) (3) For each Ti  S do - write to log (plus FLUSH LOG) ```

Answer 33

We just have to undo idempotent

Answer 34

(1) Do not accept new transactions (2) Wait until all transactions finish (3) Flush all log records to disk (log) (4) Flush all buffers to disk (DB) (do not discard buffers) (5) Write “checkpoint” record on disk (log) (6) Resume transaction processing

Answer 35

1. Write log record T1 … Tk are active transactions, and flush log. 2. Wait until all Ti-s commit or abort, but don’t prohibit other transactions from starting. 3. When all Ti-s have completed, write a log record and flush the log.

Answer 36

If we first meet an record, then we know that all incomplete transactions began after the previous record. We may thus scan backwards as far as the next , and then stop; previous log is useless and may as well have been discarded. If we first meet a record < START CKPT (T1, ... , Tk)>, then the crash occurred during the checkpoint. We need scan no further back than the start of the earliest of these incomplete transactions.

Answer 37

(1) For every action, generate redo log record (containing new value) (2) Before X is modified on disk (DB), all log records for transaction that modified X (including commit) must be on disk (3) Flush log at commit (4) Write END record after DB updates flushed to disk

Answer 38

1. The log records indicating changed database elements. 2. The COMMIT log record. 3. The changed database elements themselves.

Answer 39

1) Let S = set of transactions with (and no ) in log (2) For each in log, in forward order (earliest  latest) do: - if Ti  S then Write(X, v) Output(X) (3) For each Ti  S, write to Log (plus FLUSH LOG)

Answer 40

1. Write log record T1 … Tk are active (uncommitted) transactions, and flush log. 2. Write to disk all database elements that were written to buffers but not yet to disk by transactions that had already committed when the record was written to the log. (dirty buffers) 3. When all Ti-s have completed, write a log record and flush the log.

Answer 41

If we first meet an record, we need to scan no further back than the earliest of records (among corresponding . If we first meet a record < START CKPT (T1, ... , Tk)>, then the crash occurred during the checkpoint. We cannot be sure that committed transactions prior to the start of this checkpoint had their changes written to disk. Thus, we must search back to the previous record, find its matching < START CKPT (T1, ... , Tk)>.

Answer 42

Undo logging: need frequent disk writes | Redo logging: need to keep all modified blocks in memory until commit

Answer 43

Page X can be flushed before or after Ti commit Log record flushed before corresponding updated page (WAL) Flush at commit (log only)

Answer 44

1. Redo all the committed transactions in the order earliest-first, and 2. Undo all the incomplete transactions in the order latest-first.

Answer 45

1. Write log record T1 … Tk are active (uncommitted) transactions, and flush log. 2. Write to disk all the buffers that are dirty; i.e., they contain one or more changed database elements. Unlike redo logging, we flush all dirty buffers, not just those written by committed transactions. 3. When all Ti-s have completed, write a log record and flush the log.

Answer 46

General process of assuring that transactions preserve consistency when executing simultaneously is called concurrency control.

Answer 47

A schedule is a sequence of the important actions taken by one or more transactions.

Answer 48

A schedule is serial if its actions consist of all the actions of one transaction, then all the actions of another transaction, and so on.

Answer 49

A schedule S is serializable if there is a serial | schedule S' such that for every initial database state, the effects of S and S‘ are the same.

Answer 50

S1, S2 are conflict equivalent schedules | if S1 can be transformed into S2 by a series of non-conflicting swaps of adjacent actions.

Answer 51

A schedule is conflict serializable if it is conflict equivalent to some serial schedule.

Answer 52

S1, S2 conflict equivalent -> P(S1)=P(S2)

Answer 53

P(S1)=P(S2) !-> S1, S2 conflict equivalent

Answer 54

1. A transaction can only read or write an element if it previously was granted a lock on that element and hasn’t yet released the lock. 2. If a transaction locks an element, it must later unlock that element.

Answer 55

Locks must have their intended meaning: no two transactions may have locked the same element without one having first released the lock.

Answer 56

It means a transaction hasn't been unlocked before its locked or locked after it is unlocked