Relational Model & DBMS

disk capacity=tracks*blocks*sectors*bytes

2^30=1tb

circle pi*diameters, bytes/(90%*diameters*pi), inner and outer are different, everage inner+outer/2

maxseek=d1+maxtrack/trackpersec,averageseek=d1+1/3(maxtrack/trackpersec)

T_fullrotation=time/rpm,T_averagerot=T_fullrotation/2

two pass:RX2+SX2+R+S,$\frac{block}{M}$ < M-1

$\frac{k}{k+1}$

Serverbreak_p:percent_break x recover_hour/8760 hour

raid0: 0 fault tolerance,raid1:mirror,raid3:1diskfail byte level xor,raid4,large read slow writer block level xor, raid5:1 disk can fail distributed parity balance performance,raid6:2disk can fail

raid4:XOR:00:0,01:1,10:1,11:0

number of track to move: left+right, left/total*left_avg+right/total*right_avg

seek=seek_overhead+track_avg/trackpersec

Record_per_block=$\frac{kb*1024}{record_bytes}$

Require_blocks=record_num/Record_per_block

Trand=Tseek+Trot_avg+Trans

Tscan < Trand*Tuple_num

dense Index Block:total_block=$\frac{index entries}{Record_per_block}+\frac{index entries}{Index_per_block}$

Sparse Index Block:total_block=$\frac{index entries}{Record_per_block}+\frac{index entries/Record_per_block}{Index_per_block}$

$RPM=\frac{600000}{avg_dalay*2}

read whole tracks=Tseek+avg_dalay*2*track_number

seek time=overhead+(time per cylinder)*N/3,random accesses distance = N/3.

The first-level index (on data) is typically dense, not sparse. The second-level index (on the first-level index) is sparse, not dense.

Clustering Index Built on a non-key attribute of an ordered data file where records with the same value are stored together (clustered).

Secondary Index on Key Attribute A secondary index built on an attribute that is also a key

Sparse Primary Index is is the usual case for a primary index. order file One entry per data block (not every record).

Dense Secondary Index One entry for every record in the data file. Built on a non-ordering attribute

RA & SQL mapping

• \(\sigma\) (selection) ↔ WHERE
• \(\pi\) (projection) ↔ SELECT
• \(\times\) (product) ↔ FROM cross product
• Joins ↔ JOIN, NATURAL JOIN, etc.
• \(\delta\) ↔ DISTINCT
• \(\gamma\) ↔ GROUP BY
• \(\tau\) ↔ ORDER BY

3. Basic RA Operators

• Selection \(\sigma_C(R)\): filters rows satisfying condition \(C\); attributes unchanged.
• Projection \(\pi_L(R)\): keeps attribute list \(L\), may create duplicates (in bags).
• Product \(R \times S\): all combinations of tuples from \(R\) and \(S\).
• Natural join \(R \bowtie S\): equijoin on common attributes; remove duplicate join columns.
• Theta-join \(R \bowtie_\theta S\): join with arbitrary condition \(\theta\).
• Sorting \(\tau_L(R)\): sort on attributes \(L\).
• Duplicate elimination \(\delta(R)\).
• Grouping \(\gamma_{L, \text{aggs}}(R)\): group on \(L\), compute aggregates.

1. Bag Semantics

\(\mathrm{Card}(t, R \cup S) = \mathrm{Card}(t, R) + \mathrm{Card}(t, S)\)

\(\mathrm{Card}(t, R \cap S) = \min(\mathrm{Card}(t, R), \mathrm{Card}(t, S))\)

\(\mathrm{Card}(t, R - S) = \max(\mathrm{Card}(t, R) - \mathrm{Card}(t, S), 0)\)

2. Parameters & Simple Costs

\(M\) = #memory blocks

\(B(R)\) = #blocks of relation \(R\)

\(T(R)\) = #tuples of relation \(R\)

\(V(R,a)\) = #distinct values of attribute \(a\) in \(R\)

\(V(R,L)\) = #distinct combinations of attributes in list \(L\)

Clustered scan cost: \(\approx B(R)\)

Completely unclustered scan cost: \(\approx T(R)\)

One-pass binary operator (join / union / etc.):
$ \min\big(B(R), B(S)\big) \le M $

4. Block Nested-Loop Join

Assume \(B(S) \le B(R)\) and \(B(S) > M\).

Exact cost: $ \text{Cost} = \frac{B(S)}{M-1} \cdot \big((M-1) + B(R)\big) = B(S) + \frac{B(S)B(R)}{M-1} $

Approximate: $ \text{Cost} \approx \frac{B(S)B(R)}{M} $

5. Two-Pass Sort (TPMMS)

2-pass sort condition: $ \frac{B(R)}{M} \le M-1 \;\Rightarrow\; B(R) \le M(M-1) \approx M^2 $

Sort-based duplicate elimination cost: \(\text{Cost} = 3B(R)\)

Sort-based set ops (e.g., union) on \(R,S\): $ \text{Cost} \approx 3\big(B(R) + B(S)\big) $

Simple sort-merge join: $ \text{Cost} \approx 5\big(B(R) + B(S)\big) $

Improved sort-join (using runs, best-case): $ \text{Cost} \approx 3\big(B(R) + B(S)\big), \quad B(R) + B(S) \le M^2 $

Typical 2-pass condition: \(B(R) \le M^2\) or \(\min(B(R),B(S)) \le M^2\)

Hash-based duplicate elimination: \(\text{Cost} = 3B(R)\)

Hash-based grouping: \(\text{Cost} = 3B(R)\)

Partitioned hash-join: $ \text{Cost} = 3\big(B(R) + B(S)\big) $

7. Index-Based Selection

After index lookup, \(\sigma_{a=c}(R)\):
Clustering index on \(a\): $ \#\text{blocks} \approx \frac{B(R)}{V(R,a)} $ Non-clustering index on \(a\): $ \#\text{I/Os} \approx \frac{T(R)}{V(R,a)} $

8. Index Nested-Loop Join (Approx)

For join \(R(X,Y) \bowtie S(Y,Z)\), index on \(S.Y\):
Expected matches per \(r\): $ \text{matches per } r \approx \frac{T(S)}{V(S,Y)} $ Extra I/Os, non-clustering (rough): $ \approx T(R)\cdot \frac{T(S)}{V(S,Y)} $ Extra I/Os, clustering (rough): $ \approx T(R)\cdot \frac{B(S)}{V(S,Y)} $

Memory, Storage & Disks

Files, Blocks & Records

Phase1 runs=$\frac{diskblock}{Memorysize}$

Mergesort $\frac{diskblock}{M} <= M-1, \sqrt{diskblock}+1$

Mergesort (M-1)*M=Block size

Sortest distance first, elevator: move up then down

Primary Index Built on a sorted (ordered) data file. The index key is the primary key (ordering key) of the data file. There is one index entry per data block (not per record). Points to the first record in each block.

Secondary Index Built on a non-ordering field (not the primary key). The data file itself may be unordered or ordered on another field. There can be multiple secondary indexes on the same file. Typically has one index entry per record, because data are not ordered on this field.

Secondary Level Index (or Multi-Level Index) This is not a different kind of index (primary or secondary) — it’s about the structure of the index. When an index (primary or secondary) is too large to fit in memory, we build another index on top of it — a second-level index. This creates a hierarchy (multi-level index) that speeds up lookups.

Search Key A field or combination of fields used to look up records in an index. It is a physical access concept, used in file organization and indexing. Does not have to be unique — multiple records can have the same search key value.

    
        run-length encoding
    
01100000001000001000000
drop trailing 0’s → 01100000001000001
 Run lengths: [1, 0, 7, 5]
  i=1: binary 1 (j=1) → unary for j: 0 → 01
  i=0: binary 0 (j=1) → unary: 0 → 00
  i=7: binary 111 (j=3) → unary: 110 → 110111
  i=5: binary 101 (j=3) → unary: 110 → 110101
01 00 110111 110101
i = number of 0s in the run
j = number of bits needed to write i in binary
Unary(j) = (j − 1) ones, then a 0
    j = 1 → (1 − 1) = 0 ones, then 0 → 0
    j = 2 → 1 one, then 0 → 10
    j = 3 → 2 ones, then 0 → 110
    j = 4 → 3 ones, then 0 → 1110
        

1.With run-length encoding, not every bit string is a valid encoded form. Some bit strings might not follow the encoding rules or might decode to the wrong total length (not matching the number of records), so they can’t be decoded into a valid bitmap for a value.
2.For a correct bitmap index on an attribute with k values: For each record, exactly one of the k bit vectors should have a 1 in that position. But the statement says “any collection of k bit vectors” → in general, they might overlap (multiple 1s in a position) or miss (all 0s in a position). So you cannot always determine A for every record.
3.only bitstrings that follow the run-length encoding format are valid compressed encodings. A random bit vector will usually not be a valid encoding.

Bit map: 2+2+2sum(1-0)log i

static hash structure: N mod k,min =0, max= (total-primary)/datablock: all data in first line

9. Multipass Sort Formulas

Let \(s(M,k)\) = max #blocks sortable in \(k\) passes.

\(s(M,1) = M\)

\(s(M,k+1) = M \cdot s(M,k)\)

Closed form: $ s(M,k) = M^k $

Condition to sort \(R\) in \(k\) passes: $ B(R) \le M^k $

Cost: $ \text{Cost} = 2k \cdot B(R) $

Multipass Sort-Based Join

Let \(j(M,k)\) = max \((B(R)+B(S))\) joinable in \(k\) passes.

\(j(M,k) \approx M^k\)

Condition: \[ B(R) + B(S) \le M^k \]

Cost: \[ \text{Cost} = (2k - 1)\big(B(R) + B(S)\big) \]

10. Multipass Hash Formulas

Unary Hash-Based Ops

Let \(u(M,k)\) = max #blocks we can handle in \(k\) passes.

\(u(M,1) = M\)

Recurrence: \[ u(M,k) = (M-1)\,u(M,k-1) \]

Closed form: \[ u(M,k) = M(M-1)^{k-1} \approx M^k \]

Condition: \[ B(R) \le u(M,k) \]

Binary Hash-Based Ops (Smaller Relation)

Let \(j(M,k)\) = max #blocks of smaller relation in \(k\) passes.

\(j(M,1) = M-1\)

Recurrence: \[ j(M,k) = (M-1)\,j(M,k-1) \]

Closed form: \[ j(M,k) = (M-1)^k \]

Condition: \[ \min\big(B(R), B(S)\big) \le (M-1)^k \]

4. Multiple-Key Indexes (Tree on Composite Key) Idea: Build a tree index on (A, then B), but leaf entries point to another index (on B). Example: Index on (Dept, Salary) with nested indexes. Good for queries where leading attribute is constrained Dept = 'Sales' AND Sal = 20k → follow Dept='Sales' branch, then search Sal index. Dept = 'Sales' AND Sal > 20k. Dept = 'Sales' (can scan all salaries under Sales). Bad for queries only on non-leading attribute Sal = 20k with no Dept: Index on (Dept,Sal) alone not efficient. May need to scan all Dept branches. Key exam point Order matters: index on (A,B) helps when A is specified. If query only constrains B, multiple-key index is usually not helpful.

5. KD-Trees (k-dimensional search trees) Idea: Binary tree where splitting attribute rotates among dimensions. Structure Each node: Attribute A (e.g., Age or Salary). Split value V. Left subtree: A < V, right subtree: A ≥ V. Leaves hold blocks of points. Operations Lookup: traverse like a BST, following comparisons on rotating attributes. Partial match: If querying attribute ≠ node’s split attribute, might need to explore both subtrees at that node → possible exponential in worst case. Range queries: At a node, compare query range vs splitting plane: If entire left/right side outside range → prune that subtree. Otherwise, must explore relevant subtrees. Insertion: navigate to leaf by splits, insert in leaf block; may need to split leaf. Secondary storage issues Many leaves: ~log₂(#leaves) disk I/Os for search. Internal nodes often have little info → wasted space. Adaptation: B-tree-style kd-trees (multi-way splits, nodes grouped into disk blocks). Pros Works for PM and range in low to moderate dimensions. Cons Performance degrades as dimensions grow (curse of dimensionality).

Primary Index Ordering (primary) key Yes Block Sparse 1 entry/block
Sparse Primary Index Ordering key Yes Block Sparse Common primary index
Dense Primary Index Primary key No Record Dense Used if file unordered
Secondary Index Non-ordering field No Record Dense One per record
Sparse Secondary Index Non-ordering field No – ❌ Not practical
Secondary Index on Key Attribute Non-ordering unique field No Record Dense Each record unique
Clustering Index Non-key attribute (with duplicates) Yes Distinct value Spar

$R \cup R = 2R$

$ m_{R \cap R}(x) = \min(m_R(x), m_R(x)) = m_R(x). $

$ m_{R - R}(x) = \max(m_R(x) - m_R(x), 0) $

$ R \cup (S \cap T) = (R \cup S) \cap (R \cup T) $

a=1,2,2;b=5,1,1

$\gamma_{a,\,\mathrm{SUM}(b)\rightarrow x}(R)$

• \(a=1\): \(b\) values \(5 \Rightarrow x = 5 = 5\)
• \(a=2\): \(b\) value \(5,1 \Rightarrow x = 6\)

• \(x=5\): \(a=1 \Rightarrow y=5\)
• \(x=6\): \(a=2 \Rightarrow y=6\)

• \(b=5\): tuples \((1,5),(2,5)\Rightarrow y=1\)
• \(b=1\): tuple \((2,1)\Rightarrow y=2\)

• \(y=1\): \(b\) values \(5 \Rightarrow x = 5\)
• \(y=2\): \(b\) values \(1 \Rightarrow x = 5\)

linear hashing

a dynamic hashing scheme that grows gradually by splitting buckets one by one in a fixed order, avoiding a full rehash of all keys.

• At level $i = 1$: split buckets $0, 1$
• At level $i = 2$: split buckets $0, 1, 2, 3$
• At level $i = 3$: split buckets $0, 1, 2, 3, 4, 5, 6, 7$
• Global occupancy: $ \text{occ} = \frac{\text{\#records}}{\text{\#buckets} \times C} $
• Threshold $\alpha$ (e.g. $\alpha = 0.75$ or $\alpha = 1.0$).
• $h_i(k)$ for unsplit buckets,
• $h_{i+1}(k)$ for buckets that have already been split in the current round.

1. Let $s = n$ be the bucket to split.
2. Create a new bucket with index: $ s' = s + 2^i $
3. Collect all records (primary + overflow) from bucket $s$.
4. Rehash each record using: $ b = h_{i+1}(k) = h(k) \bmod 2^{i+1} $ and put it into bucket $b$ (which is either $s$ or $s'$).
5. Increment split pointer: $n \leftarrow n + 1$.
6. If $n = 2^i$:
   • Increment level: $i \leftarrow i + 1$
   • Reset split pointer: $n \leftarrow 0$

B+ tree: Insertion, n=3 min=1, max=3
Find leaf → insert key.
If overflow → split.
Promote smallest key of right leaf to parent.
If parent overflows → split & promote middle key.
If root overflows → new root.
Deletion
Find leaf → delete key.
If underflow:
Try borrow from left sibling (if > min keys).
Else borrow from right sibling (if > min keys).
Else merge with sibling and remove separator from parent.
(sibling: must share parents)
If parent underflows → do same thing (borrow/merge) up to root.
If root has 1 child and is underflowing → shrink height.

when n=4,
   Root: min = 1, max = 4 
    Internal: min = 2, max = 4
        Leaf: min = 2, max = 4 
when n=3,
    Root: Min keys = 1 Max keys = 3
        Internal: Min keys = 1 Max keys = 3
            Leaf: Min keys = 2 Max keys = 3
Linear hashing
Search / Insert addressing :
b = hᵢ(k) mod N
If b < n → bucket index = hᵢ₊₁(k) mod (2N)
Else → bucket index = b
Split:
Split bucket n:
New bucket index: N + n
Re-hash all entries in bucket n with hᵢ₊₁ and send to n or N + n
n = n + 1
If n == N:
i = i + 1
n = 0
N = 2ᶦ * N₀

Totalbucket= record_number/bucketperblock:ceil
Total buckets = primary + overflow
Extensible Hashing:
When inserting: Left bits 
Compute hash, go to bucket.
If bucket not full: insert.
If full:
If LD < GD: split bucket.
If LD == GD: double directory, then split bucket.
Reinsert keys into correct bucket after split.

1. Multidimensional (MD) Data & Query Types MD data examples GIS: points/rectangles in 2D/3D. Data cubes: facts with dimensions like (day, store, item, color, size). Common MD queries Partial match (PM): fix some attributes, others free e.g., Dept = 'toy' (Sal free). Range query (RQ): intervals per attribute e.g., 450 ≤ x ≤ 550 AND 450 ≤ y ≤ 550. Nearest neighbor (NN): closest object to query point. Where-am-I: find region containing a given point (e.g., which polygon/rectangle). Naive B-tree approach Separate B-tree index on each dimension. For 2D range query: Get pointer list from index on X. Get pointer list from index on Y. Intersect pointer lists. Can be worse than table scan: Example in slides: ~11,002 I/Os vs ~10,000 I/Os for full scan. NN via B-trees Convert NN around point (x₀, y₀) into range query on a square: {(x, y) : x₀ − d ≤ x ≤ x₀ + d, y₀ − d ≤ y ≤ y₀ + d}. Problems: If no point in range → must increase d and re-run. Closest point in that square may still not be true global NN (but often is if d chosen well). 2. Grid Files Idea: Partition each dimension into stripes (ranges). Cross product of stripes = grid cells. Each cell → bucket (on disk). Directory (grid) kept in main memory. Structure Dimension 1: ranges V₁, V₂, … Dimension 2: ranges X₁, X₂, … Directory entry [i,j] → pointer to bucket. Lookup Use key values to find stripe in each dimension. Identify grid cell. Follow pointer to bucket → scan bucket. Supports Exact match: key1 = Vi AND key2 = Xj → single cell. Partial match: key1 = Vi → scan entire row of cells. key2 = Xj → scan entire column. Range queries: rectangle region → scan covered cells (submatrix). NN: treat as range query, expand search rectangle gradually. Insertion If bucket overflows: Use overflow buckets OR Split stripe(s) in one dimension → refine partition. Pros Good for multiple-key search. Supports PM, range, NN. Cons Directory size can explode for many dimensions → many empty cells. Need good partition ranges to balance load. Still can get overflow buckets. 3. Partitioned Hashing Idea: Use hash bits per dimension, then concatenate to form bucket address. Example: h₁(Dept) → first bit. h₂(Sal) → next 2 bits. Address = h₁(Dept) · h₂(Sal) (total 3 bits → 8 buckets). Supports Exact match: E.g., Dept = 'Sales' AND Sal = 40k → one bucket. Partial match (some dims unspecified): e.g., Sal = 30k → look at all buckets whose h₂(Sal) = given pattern, regardless of h₁. Dept = 'Sales' → all buckets where h₁(Sales) is fixed bit. Bad for Range queries (e.g., 20k ≤ Sal ≤ 50k) → values hashed, not ordered. NN queries → hash destroys proximity. Pros vs Grid Files For high number of dimensions, grid files → too many empty cells. Partitioned hashing uses fixed number of buckets, still okay. Summary Good: Exact + partial match. Bad: Range + NN. 6. Quad Trees Idea: Like kd-trees, but split all dimensions at once. For k dimensions: Each internal node has 2ᵏ children. 2D → 4 children (quadrants). Splits are fixed (midpoints, etc.), not data-dependent → tree not balanced by data. Operations Lookup / insertion: Go down appropriate child at each level (based on coordinate region). Insert into leaf, split region if needed. Range query: recursively visit children whose region intersects the query rectangle. Pros For modest k, children of a node (2ᵏ) can fit in one disk block. Cons For high k, 2ᵏ huge → not suitable. Fixed splitting may lead to unbalanced occupancy. 7. R-Trees Idea: Generalization of B-tree to multidimensional rectangles. Entries in nodes: (MBR, pointer) pairs, where: MBR = Minimum Bounding Rectangle of objects in subtree. Pointer → child node or data.Uses Spatial data: rectangles, polygons, points (as tiny rectangles). Supports:Range queries (which regions intersect query region). NN queries (search nodes whose MBRs are close). Where-am-I (which region encloses given point). Insertion strategy Choose leaf whose MBR needs minimum area enlargement to include the new object. Insert object. If overflow: Split node into two nodes. Choose split that minimizes total area / overlap of resulting MBRs. Example details in slides If new region does not fit inside existing MBR: Must expand MBR (compare area increase for each candidate). Pros Balanced like B-tree. Good for disk-based spatial search. Key exam keywords MBR, area enlargement, overlap minimization, (region,pointer) pairs. 8. Bitmap Indexes Idea: For each distinct value v of an attribute, store a bit vector of length n (n = #records). Position i is 1 if tuple i has value v, else 0. Example Records (ID: (Age, Name)) with n = 6: 1:(30,foo), 2:(30,bar), 3:(40,baz), 4:(50,foo), 5:(40,bar), 6:(30,baz) Bitmap on second field: key vector foo 100100 bar 010010 baz 001001 Gender + Rating example Gender bitmap: 2 bit-vectors (M, F) Rating bitmap: 5 bit-vectors (1–5). Query gender = 'M' AND (rating = 3 OR rating = 5): rating=3 vector OR rating=5 vector. AND result with gender='M' vector. Positions with 1 → matching tuples. Why useful? Partial match & range queries: For multiple values on same attribute: OR. Across attributes: AND of each attribute’s combined vector. Bitwise operations are very fast and CPU-native. Space n records, m distinct values → n × m bits. But often sparse and compressible.