Exam 2

Question 1

Database file index

Answer 1

similar in theme to an index in a textbook

data structure allowing fast lookups for data

Question 2

Types of indexes

Answer 2

Ordered Indexes

Hash Indexes

Question 3

ordered indexes

Answer 3

values are stored sequentially within the file

Question 4

Hash indexes

Answer 4

values uniformly distributed across a range of buckets (blocks) by a hash function

Question 5

Why is the word values used instead of records when talking about ordered and hash indexes

Answer 5

because it is the values which determine the location of the records

Question 6

What is an index

Answer 6

metadata that helps access record data

stored in blocks. The blocks contain pointers into other blocks ( which contain records)

Question 7

what are the 2 orderings of indexes

Answer 7

primary and secondary

Question 8

primary index

Answer 8

for a sequentially ordered file, the index whose search key specifies record order

also called clustering index
the search index is usually the primary key

Question 9

secondary index

Answer 9

an index whose search key specifies an order different than the file order

records are not sorted by the search key

also called non-clustering index

Question 10

what are the 2 Formats for indexes

Answer 10

Dense and sparse

Question 11

Dense indexes

Answer 11

the index points to sequential records stored within a file.

one index entry per search key

Question 12

Sparse index

Answer 12

contains index records for only some of the search-key values

only applicable when records are sequentially ordered by the search key (clustering indexes)

Question 13

pros and cons for dense and sparse indexes

Answer 13

dense
-entry per key value
-faster lookup time
-more space required
-more maintenance

sparse
-fewer entries
-slower lookup time
-less space required
-less maintenance

good tradeoff is one sparse index entry per block

Question 14

B+ Tree

Answer 14

Multilevel index structure

A balanced, tree-based data structure
High fanout

automatically reorganizes itself on inserts/deletions

reorganizations of the entire file is not needed to maintain performance

Question 15

structure of B+ Trees

Answer 15

n pointers
n-1 search keys

search keys are organized such that
if i < j then Ki < Kj

internal nodes - an internal level of nodes provide a sparse index on the level of nodes below it

leaf nodes - leaf nodes provide a dense index on the file

Question 16

what are the rules for internal nodes in a B+ Tree

Answer 16

may hold up to n pointers

must hold at least n/2 pointers (round up)

Question 17

what are the rules for leaf nodes in a B+ Tree

Answer 17

may hold up to n-1 pointers

must hold at least (n-1) / 2 values (round up)

Question 18

what happens when a node is at capacity when trying to insert

Answer 18

split up the node

Question 19

what happens when a leaf node falls below the (n-1)/2 (round up) values

Answer 19

we coalesce nodes by either

merging the node with a sibling node

redistribute the entries between the nodes to ensure that each is half full

Question 20

cost of select - full file scan - no index, a heap

Answer 20

cost = br * tT + tS

br denoting all block in relation r

Question 21

cost of select - linear search on a sorted file

Answer 21

cost = br/2 * tT + tS

read half the blocks on average (br/2)

Question 22

cost of lookups on B+ Tree indexes

Answer 22

hi + 1

hi defines the tree height
+1 for the data block beyond the leaf node

Question 23

cost of select on a B+ Tree ordered by search key

Answer 23

cost = (hi + 1) * (tT + tS)

Question 24

what are the steps of query processing

Answer 24

1 parsing & translation
2 optimization
3 evaluation

Question 25

in what order are sql queries expressed in relational algebra

Answer 25

1 cross product of relations 2 selection 3 projection

Question 26

what is the generic query plan cost

Answer 26

cost = b * tT + s * tS tT time to transfer a block from disk tS time to perform a seek (access time) b number of blocks to transfer from disk s number for seeks that must occur

Question 27

what are the 2 methods of query evaluation

Answer 27

materialized and pipelined

Question 28

materialized query eval

Answer 28

In materialized evaluation (materialization), each operator reads data page-at-a-timeand then writes each producedpage to a temporary file. The next operator can read from thatfile (intermediate data) and produce its own materialized output fileand so on.

Question 29

Pipelined query eval

Answer 29

In pipelined evaluation, each operator will read a single block at a time and deliver its result directly to the operator above it.

Question 30

what are the operator interface methods

Answer 30

void open(datasource, args) page next() void close()

Question 31

what is the pseudo code for project

Answer 31

For each record in table Keep certain attr Return record

Question 32

what is the pseudo code for select

Answer 32

For each record in table Test predicate If true Return record

Question 33

what is the pseudo code for join

Answer 33

Simple nested loop For each record Rs in Table S For each Record Rt in Table T If predicate on Rs and Rt is true Return Record(Rs + Rt) Block Nested loop join For each block Bs in Table S For each block Bt in Table T For each Rs in Block Bs For each Rt in block Bt If predicate on Rs and Rt is true Return Rs + Rt

Question 34

how does the System Catalog plays into cost analysis

Answer 34

the system catalog contains statistics about the database that is used to calculate the cost of a query plan.

Question 35

what is a transaction

Answer 35

a transaction is a unit of execution in which data is read and modified. The steps within it appear to the user as indivisible a transaction will execute entirely or not at all. If failure is imminent, changes due to partial execution will be rolled back

Question 36

what does A.C.I.D stand for

Answer 36

atomicity consistency isolation durability

Question 37

atomicity

Answer 37

either all operations of the transaction are applied to the data or none are

Question 38

consistency

Answer 38

execution results in the data staying consistent/valid as relating to integrity constraints on the data

Question 39

isolaiton

Answer 39

transactions don't "appear" to run concurrently. Any other transaction runs "before" or "after" the current transaction Isolation guarantees that the intermediate states of a transaction are not visible to other transactions until the transaction is complete.

Question 40

durability

Answer 40

a completed transaction persists even if there are system failures

Question 41

explain Concurrent Query Execution

Answer 41

Concurrent Query Execution refers to the ability of a database system to execute multiple queries simultaneously Concurrency: In multi-user environments, many transactions may be processed simultaneously. Isolation ensures correctness even when transactions overlap.