DBT: INDEXING

Consider relation students(studentID, degree, courseID) with bitmap indexes on degree and courseID:

Bitmap index on degree:
ISM:    010101
CS:     101010

Bitmap index on courseID:
DBT:    101000
DBTLAB: 010010
ROC:    000100
DW:     000001

Option A

Option B

Option C

Option D

Which table matches these bitmap indexes?

Given the following properties:

• Data file: 10 million tuples, each tuple requires 512 bytes
• Disk block size: 8192 bytes
• Index entry: search key 4 bytes + pointer 8 bytes
• Index entries do not span blocks

How many blocks are required to store this sparse index? (Give your answer as a single integer.)

Given the following properties:

• Data file: 10 million tuples, each tuple requires 512 bytes
• Disk block size: 8192 bytes
• Index entry: search key 4 bytes + pointer 8 bytes
• Index entries do not span blocks

How many blocks are required to store a second-level sparse index if the first-level index is also sparse?

Consider this extensible hash table:

• Bucket capacity: 4 records
• Current global depth i = 1
• Directory 0 -> bucket (local depth 1): 0010, 0101, 0011, 0110
• Directory 1 -> bucket (local depth 1): 1010, 1110, 1001, 1011

Insert key 1000. Which resulting configuration is correct?

Mark each statement as True or False.

Given the following properties of the data file, disk, and index structures:

• Data file: 10 million tuples, each tuple requires 2048 bytes
• Disk block size: 4096 bytes
• Index: search key size 8 bytes, pointer size 12 bytes
• Index entries do not span blocks

How many blocks are required to store this dense index? (single integer)

Given fact table Clicks(User, Session, Page, Position) with a grid file partitioned as:

• User: 4 partitions
• Session: 3 partitions
• Page: 9 partitions

After ingesting more data, one partition of the Page dimension is split. How many buckets now exist in total?

Select the type of queries efficiently supported by a hash index on attribute $a$.

(Note: Selectivity refers to the property of the index or query.)

Consider the B+ tree below with the following properties:

• Each node (except root) contains $2 \le k \le 4$ keys.
• Inner nodes: keys in subtree below pointer $p_i$ are less than key $k_i$; keys below pointer $p_{i+1}$ are greater or equal than key $k_i$.
• Delete operation first tries to steal from a direct sibling (first right sibling, then left sibling). If stealing is not possible, nodes merge (first with right sibling, then left sibling).
• Leaf pointers $p_1, \dots, p_4$ in leaves point to row IDs; pointer $p_5$ points to next leaf.

Which of the following choices represents the B+ tree after deletion of key 22?

Consider the B+ tree below with the following properties:

• Each node (except the root) contains $2 \le k \le 4$ keys.
• Inner nodes: keys in the subtree below pointer $p_i$ are less than key $k_i$; keys below pointer $p_{i+1}$ are greater or equal than key $k_i$.
• Insert operations may trigger node splits but no shifting of keys into neighboring leaves.
• When a node is split, the middle key is moved to the parent node.
• Pointers $p_1, \dots, p_4$ in leaves point to row IDs. Pointer $p_5$ points to the next leaf.

Which of the following choices represents the B+ tree after insertion of key 43?

Consider relation Customer(Age, Gender, PostalCode, City, TotalSpent).

The following query:

SELECT *
FROM Customer
WHERE PostalCode = 10629

is an example of:

Consider relation R(a, b, c, d) stored using partitioned hashing:

• Total buckets: 65536 (16-bit hash function)
• Bit allocation: 4 bits for a, 5 bits for b, 3 bits for c, 4 bits for d

How many buckets must be checked for a partial match query on a?

Example:

SELECT *
FROM R
WHERE a = 'y';

Given the following kd-tree, choose the corresponding partitions.