Let's break down the problem and compute the **average cost** for each possible combination of indexes, using the assumptions given. ## 1. **Data and Probabilities** - **Ships(name, class, launched)** - 50 pages for the relation. - **name** is the key. - Clustered on **class** (all ships of a class together on a page). - 5 ships per class (on average). - 25 ships per launch year (on average). - **P1**: Probability of query `WHERE name = n` - **P2**: Probability of query `WHERE class = c` - **P3**: Probability of query `WHERE launched = y` - Probability of insertion: `1 - P1 - P2 - P3` We are to consider indexes on **name**, **class**, **launched**, and combinations thereof. --- ## 2. **Access Costs** ### **A. No Index** - **WHERE name = n**: Must scan all 50 pages (since name is not indexed and not clustered). **Cost: 50 I/Os** - **WHERE class = c**: Clustered on class; only 1 I/O needed (all ships of a class are together). **Cost: 1 I/O** - **WHERE launched = y**: Not clustered, not indexed. Must scan all 50 pages. **Cost: 50 I/Os** - **Insertion**: Write to appropriate spot; assuming 1 I/O. --- ### **B. Index on name (Assume B+ tree, unclustered)** - **WHERE name = n**: Since name is key and indexed, can access efficiently. - B+ tree over 50 pages = tree height ≈ 2-3. - Access index (2 I/Os), then data (1 I/O). **Total: 3 I/Os** - **class**: No change (still clustered): **1 I/O** - **launched**: No index: **50 I/Os** - **Insertion**: Must update both data and index: **2 I/Os** --- ### **C. Index on class (clustered)** - **WHERE name = n**: No index, must scan all pages: **50 I/Os** - **WHERE class = c**: Clustered index, can go directly to the page(s): **1 I/O** - **WHERE launched = y**: No index: **50 I/Os** - **Insertion**: Update data and index: **2 I/Os** --- ### **D. Index on launched (unclustered)** - **WHERE name = n**: No index: **50 I/Os** - **WHERE class = c**: Clustered, so 1 I/O - **WHERE launched = y**: Unclustered index. - Average 25 ships per year, so 25 index entries. - Index access (2 I/Os), then 25 data fetches (since unclustered): **27 I/Os** - **Insertion**: Update data and index: **2 I/Os** --- ### **E. Indexes on name & class** - **name**: 3 I/Os - **class**: 1 I/O - **launched**: 50 I/Os - **Insertion**: 3 I/Os --- ### **F. Indexes on name & launched** - **name**: 3 I/Os - **class**: 1 I/O - **launched**: 27 I/Os - **Insertion**: 3 I/Os --- ### **G. Indexes on class & launched** - **name**: 50 I/Os - **class**: 1 I/O - **launched**: 27 I/Os - **Insertion**: 3 I/Os --- ### **H. Indexes on name, class, and launched** - **name**: 3 I/Os - **class**: 1 I/O - **launched**: 27 I/Os - **Insertion**: 4 I/Os --- ## 3. **Average Cost of an Operation** Let’s define the average cost as: \[ \text{Average cost} = P_1 \cdot C_1 + P_2 \cdot C_2 + P_3 \cdot C_3 + (1 - P_1 - P_2 - P_3) \cdot C_{\text{ins}} \] Where \(C_1, C_2, C_3, C_{\text{ins}}\) are the costs (in I/Os) for each type of operation. --- ## 4. **Summary Table** | Indexes | name | class | launched | Insertion | Avg Cost Formula (I/Os) | |---------------------|------|-------|----------|-----------|-------------------------------------------------------------------------------------------------------------------------| | None | 50 | 1 | 50 | 1 | \( P_1 \cdot 50 + P_2 \cdot 1 + P_3 \cdot 50 + (1-P_1-P_2-P_3) \cdot 1 \) | | name | 3 | 1 | 50 | 2 | \( P_1 \cdot 3 + P_2 \cdot 1 + P_3 \cdot 50 + (1-P_1-P_2-P_3) \cdot 2 \) | | class | 50 | 1 | 50 | 2 | \( P_1 \cdot 50 + P_2 \cdot 1 + P_3 \cdot 50 + (1-P_1-P_2-P_3) \cdot 2 \) | | launched | 50 | 1 | 27 | 2 | \( P_1 \cdot 50 + P_2 \cdot 1 + P_3 \cdot 27 + (1-P_1-P_2-P_3) \cdot 2 \) | | name, class | 3 | 1 | 50 | 3 | \( P_1 \cdot 3 + P_2 \cdot 1 + P_3 \cdot 50 + (1-P_1-P_2-P_3) \cdot 3 \) | | name, launched | 3 | 1 | 27 | 3 | \( P_1 \cdot 3 + P_2 \cdot 1 + P_3 \cdot 27 + (1-P_1-P_2-P_3) \cdot 3 \) | | class, launched | 50 | 1 | 27 | 3 | \( P_1 \cdot 50 + P_2 \cdot 1 + P_3 \cdot 27 + (1-P_1-P_2-P_3) \cdot 3 \) | | name, class, launched| 3 | 1 | 27 | 4 | \( P_1 \cdot 3 + P_2 \cdot 1 + P_3 \cdot 27 + (1-P_1-P_2-P_3) \cdot 4 \) | --- ## 5. **Which Indexes Are Best?** - The best index combination **minimizes** the average cost formula above, depending on the values of \(P_1, P_2, P_3\). - If queries for **name** are most frequent (\(P_1\) large), you want an index on **name**. - If queries for **launched** are frequent (\(P_3\) large), you want an index on **launched** (since otherwise it's 50 I/Os vs 27 with index). - If insertions are frequent (\(1-P_1-P_2-P_3\) large), avoid extra indexes since they increase insertion cost. **In most practical cases:** - If \(P_1\) and/or \(P_3\) are significant, **having indexes on name and launched is optimal**. - If only \(P_1\) is significant, only index on **name**. - If only \(P_3\) is significant, only index on **launched**. - If all three query types are frequent, index on **name** and **launched** (index on class is less useful since clustered already). --- ### **General Recommendation** The best indexes as a function of \(P_1, P_2, P_3\) is the combination that minimizes \[ P_1 \cdot C_1 + P_2 \cdot C_2 + P_3 \cdot C_3 + (1 - P_1 - P_2 - P_3) \cdot C_{\text{ins}} \] where \(C_1, C_2, C_3, C_{\text{ins}}\) are as in the table above. - **If \(P_1, P_3\) are both substantial, index on both name and launched.** - **If only \(P_1\) is large, index on name.** - **If only \(P_3\) is large, index on launched.** - **If insertions dominate, use fewer indexes.** --- ## **Summary Table for Formula** **For any index set, plug in the corresponding costs and your values for \(P_1, P_2, P_3\). Choose the index set that gives the lowest average cost.** --- **If you want a concise answer:** > **The best choice of indexes is the one (from the table above) that minimizes** > > \[ > \text{Average cost} = P_1 \cdot C_1 + P_2 \cdot C_2 + P_3 \cdot C_3 + (1 - P_1 - P_2 - P_3) \cdot C_{\text{ins}} > \] > > **where the costs \(C_1, C_2, C_3, C_{\text{ins}}\) for each index combination are given in the table above.** > **Choose the combination with the lowest average cost for your specific values of \(P_1, P_2, P_3\).**