1What is disk based hash indexing?
an adaptation of main memory hash tables for databases
2What type of queries do hash indexes support?
equality searches
3Do hash indexes support range queries?
no
4What is static hashing?
hashing where number of buckets n is fixed
5What does each bucket represent in static hashing?
one disk page
6What does a hash function do?
maps a key to a bucket
7What is a common hash function?
h key mod n
8What is required of a good hash function?
uniform distribution of keys
9What must a hash function be?
deterministic
10What is stored in a hash bucket entry?
key and rid
11What is a rid?
record id consisting of block id and slot number
12Should entries in a bucket be sorted?
yes for faster search
13What is the tradeoff of sorting bucket entries?
slower insert and delete
14How does lookup in hashing work?
apply hash function then search bucket
15What extra step is needed during lookup?
check overflow buckets if they exist
16What happens when a bucket is full?
create overflow bucket
17What is an overflow bucket?
an additional disk block linked to a bucket
18What is a drawback of overflow buckets?
long chains slow search
19What is deletion in static hashing?
remove key and possibly remove overflow bucket
20What is a major limitation of static hashing?
number of buckets cannot change
21What is dynamic hashing?
hashing where number of buckets can grow
22What problem does dynamic hashing solve?
avoids overflow buckets
23What is extensible hashing?
a dynamic hashing method using a directory
24What is a directory in extensible hashing?
array of pointers to buckets
25What determines directory size?
global depth
26What is global depth?
number of bits used for indexing
27What is local depth?
number of bits used by a bucket
28What must be true about local depth?
less than or equal to global depth
29How do you determine a bucket in extensible hashing?
use least significant bits of hash
30What happens if a bucket is full and local depth equals global depth?
double directory and split bucket
31What happens if local depth is less than global depth?
split bucket only
32What happens after splitting a bucket?
redistribute keys based on bits
33Why is extensible hashing efficient?
can achieve about one i/o per lookup
34What is relational algebra?
a formal query language using operations on relations
35What is the difference between relational algebra and calculus?
algebra is operational calculus is declarative
36What are unary operators?
operators with one input relation
37What are binary operators?
operators with two input relations
38What is selection σ?
filters rows based on condition
39What is projection π?
selects specific columns
40What is extended projection?
projection with computed attributes
41What is union ∪?
combines tuples from two relations
42What is intersection ∩?
tuples common to both relations
43What is difference −?
tuples in one relation but not the other
44What condition is required for union intersection and difference?
relations must be union compatible
45What is Cartesian product ×?
pairs every tuple in r with every tuple in s
46What is natural join ⋈?
join on common attributes automatically
47What is theta join?
join based on arbitrary condition
48What is duplicate elimination δ?
removes duplicate tuples
49What is grouping and aggregation γ?
groups tuples and applies functions like sum count avg
50What are common aggregation functions?
sum avg min max count
51What is assignment operator ← used for?
store intermediate query results