SQL Query Execution, Optimization, Relational Algebra, and Aggregation

Multi-Table Joins and Physical Execution Ordering

Declarative Query Formulation:
- To find the names of sailors who have reserved a red boat, data must be combined from three relations:
- Sailors ( $S$ ): Contains sailor identification ( $S.sid$ ) and names ( $S.sname$ ).
- Reserves ( $R$ ): Contains reservation records connecting sailors ( $R.sid$ ) and boats ( $R.bid$ ).
- Boats ( $B$ ): Contains boat identification ( $B.bid$ ) and attributes such as color ( $B.color$ ).
- SQL query formulation: sql SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red';     
- In declarative SQL, the syntactical order of relations in the FROM clause and the order of search conditions in the WHERE clause do not affect query semantics or the final result set.
- Essential join conditions ( $S.sid = R.sid$ and $R.bid = B.bid$ ) must be explicitly supplied to prevent accidental Cartesian cross-products.
Relational Algebra and Execution Order:
- While SQL is non-procedural and order-agnostic, the underlying relational algebra and physical execution order dramatically impact performance.
- Multiple operational sequences exist to execute the join query:
- Execution Plan 1: Join Sailors and Reserves, join the result with Boats, select tuples with color equal to red, and project names: $\pi_{\text{sname}}(\sigma_{\text{color}='\text{red}'}((S \bowtie R) \bowtie B))$
- Execution Plan 2: Join Reserves and Boats, join the result with Sailors, apply selection, and project names: $\pi_{\text{sname}}(\sigma_{\text{color}='\text{red}'}((R \bowtie B) \bowtie S))$
- Execution Plan 3 (Pushing Selection): Filter Boats on color first, join with Reserves, join with Sailors, and project names: $\pi_{\text{sname}}((S \bowtie R) \bowtie \sigma_{\text{color}='\text{red}'}(B))$
- Execution Plan 4: Join Sailors with Reserves, and join that intermediate result directly with filtered Boats: $\pi_{\text{sname}}((S \bowtie R) \bowtie \sigma_{\text{color}='\text{red}'}(B))$
- Invalid operational sequence:
- Attempting to join Sailors directly with Boats ( $S \bowtie B$ ) prior to Reserves is invalid because Sailors and Boats share no common foreign key attributes (Sailors lacks boat ID; Boats lacks sailor ID).
Cost and Selectivity Analysis:
- Joining unreduced tables ( $S \bowtie R$ followed by join with full $B$ ) requires processing all records in each table before filtering, which is computationally expensive.
- Pushing selection down—performing $\sigma_{\text{color}='\text{red}'}(B)$ first—generates a small intermediate relation. Joining this smaller table with Reserves immediately constrains the intermediate result size, significantly minimizing input sizes for subsequent joins and lowering overall disk I/O and CPU costs.

Query Plans and Pipelining versus Blocking Operators

Execution Trees and Physical Operators:
- Query optimizers evaluate SQL declarations and map them into physical relational algebra operator trees.
- The query executor processes this plan by directly invoking underlying physical algorithms (e.g., selection routines, hash joins, index nested-loop joins, projection algorithms) rather than running naive conceptual evaluations (computing exhaustive cross-products across all FROM tables, removing unqualified rows, and dropping unprojected columns).
Pipelined Evaluation (Bilineable Trees):
- In a pipelined query execution plan, operators act as stream processors that pass intermediate output tuples directly upward to the parent operator without materializing full intermediate states on disk.
- Pipelining operates like an assembly line: one operator yields a tuple and immediately hands it off to the next consumer, allowing the engine to return early results before upstream inputs are fully consumed.
Blocking Operators:
- Set operations like intersection ( $\cap$ ) and union ( $\cup$ ) often act as blocking operators in standard plans.
- A blocking operator cannot emit any output tuples until both left and right subtrees have completed execution and their entire outputs have been materialized.
- Blocking operators disrupt pipeline flow, consume intermediate memory and disk space, and increase total latency.
Optimizer Sophistication and Database Engines:
- High-end commercial database systems employ sophisticated cost-based optimizers that automatically recognize inefficient queries (such as blocking set operations) and transform them into optimal, pipelined multi-way join trees.
- Simpler or open-source database engines with less advanced optimizers frequently fail to discover these transformations on their own. Under such systems, developers must manually write structurally efficient SQL to help the engine construct an optimal plan.

Implementing Set Operations: Disjunction, Conjunction, and Difference

Disjunction (OR vs. UNION):
- Goal: Find names of sailors who have reserved a red boat or a green boat.
- Approach 1 (OR predicate within a single multi-table join):
```
SELECT S.sname
FROM Sailors S, Reserves R, Boats B
WHERE S.sid = R.sid 
  AND R.bid = B.bid 
  AND (B.color = 'red' OR B.color = 'green');
&nbsp;&nbsp;&nbsp;&nbsp;```
* Operational cost:  $2$  joins,  $1$  selection,  $1$  projection.
* Approach 2 (`UNION` of two distinct queries):
```
sql SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red' UNION SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'green'; ```
- Operational cost: $4$ joins, $2$ selections, $2$ projections, and $1$ set union operation.
- Efficiency comparison: The single-query OR approach requires less than half the operational workload of the UNION approach.
Conjunction (AND vs. INTERSECT vs. Multi-Table Self-Joins):
- Goal: Find sailor IDs and names of sailors who have reserved both a red boat and a green boat.
- Incorrect approach:
```
WHERE B.color = 'red' AND B.color = 'green'
&nbsp;&nbsp;&nbsp;&nbsp;```
* This fails because each individual boat tuple contains a single `color` attribute value; no single row can satisfy both `color = 'red'` and `color = 'green'` simultaneously, returning an empty set.
* Approach 1 (`INTERSECT` operator):
```
sql SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red' INTERSECT SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'green'; ```
- Requires $4$ joins, $2$ selections, $2$ projections, and $1$ blocking intersection operator.
- Approach 2 (5-Table Join with Aliasing / Pipelined Alternative):
- Conceptual model: Join the sailor table simultaneously to two separate instances of reservations and boats ( $R_1, B_1$ for red boats; $R_2, B_2$ for green boats). sql SELECT S.sid, S.sname FROM Sailors S, Reserves R1, Boats B1, Reserves R2, Boats B2 WHERE S.sid = R1.sid AND R1.bid = B1.bid AND S.sid = R2.sid AND R2.bid = B2.bid AND B1.color = 'red' AND B2.color = 'green';     
- Relational algebra structure: $\pi_{\text{sname}}(\sigma_{\text{color}='\text{red}'}(B_1) \bowtie R_1 \bowtie S \bowtie R_2 \bowtie \sigma_{\text{color}='\text{green}'}(B_2))$
- Total operational count: $4$ joins, $2$ selections, $1$ projection, and $0$ blocking set operators.
- Pipelining advantage: Avoids the blocking synchronization barrier imposed by INTERSECT, allowing continuous end-to-end tuple pipelining.
Set Difference (EXCEPT):
- Goal: Find sailor IDs and names of sailors who have reserved red boats but have not reserved green boats.
- Formulation uses EXCEPT to subtract the set of sailors reserving green boats from the set of sailors reserving red boats: sql SELECT S.sid, S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red' EXCEPT SELECT S.sid, S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'green';

Nested Subqueries: Uncorrelated, Multi-Level, and Correlated

Uncorrelated Subqueries:

Definition: Subqueries whose expressions do not reference variables or attributes from outer queries. The subquery can be evaluated independently once, producing an intermediate collection tested by the outer query using operators such as IN or NOT IN.
Example with IN: Sailors who reserved boat $103$ :

SELECT S.sname
FROM Sailors S
WHERE S.sid IN (
    SELECT R.sid
    FROM Reserves R
    WHERE R.bid = 103
);
&nbsp;&nbsp;&nbsp;&nbsp;```
* Execution logic: The inner query evaluates completely to produce a list of all  $sid$  values present in `Reserves` for  $bid = 103$ . The outer query scans `Sailors` and outputs tuples whose  $sid$  appears in that list.
* Example with `NOT IN`: Sailors who have not reserved boat  $103$ :

sql SELECT S.sname FROM Sailors S WHERE S.sid NOT IN ( SELECT R.sid FROM Reserves R WHERE R.bid = 103 ); ```

Multi-Level Nested Subqueries (Three-Tier Nesting):
- Goal: Find names of sailors who have not reserved a red boat. sql SELECT S.sname FROM Sailors S WHERE S.sid NOT IN ( SELECT R.sid FROM Reserves R WHERE R.bid IN ( SELECT B.bid FROM Boats B WHERE B.color = 'red' ) );     
- Execution trace (inside-out):
- Level 3 (Innermost query): Computes the set of all boat IDs ( $bid$ ) where $B.color = '\text{red}'$ .
- Level 2 (Middle query): Computes the set of all sailor IDs ( $sid$ ) in Reserves whose reserved $bid$ belongs to the Level 3 set (sailors who reserved a red boat).
- Level 1 (Outer query): Scans Sailors and projects the names ( $sname$ ) of sailors whose $sid$ does not appear in the Level 2 set.
Correlated Subqueries:
- Definition: Subqueries containing references to attributes of an outer query relation (e.g., $S.sid$ ), making independent inner execution impossible.
- Evaluation Mechanism: Operates conceptually as a nested-loop join over the outer table.
- For each row of the outer query, the outer attribute value is bound to the inner subquery.
- The inner subquery is executed using that bound parameter.
- The condition evaluates (e.g., via EXISTS or NOT EXISTS) to determine whether the outer row qualifies.
- Correlated query using EXISTS: Sailors who reserved boat $103$ : sql SELECT S.sname FROM Sailors S WHERE EXISTS ( SELECT * FROM Reserves R WHERE R.bid = 103 AND R.sid = S.sid );     
- Step-by-step trace:
  - Outer row $1$ has $S.sid = 1$ . The inner query evaluates SELECT * FROM Reserves R WHERE R.bid = 103 AND R.sid = 1. If at least one row returns, EXISTS evaluates to true, and sailor $1$ 's name is emitted.
  - Outer row $2$ has $S.sid = 2$ . Inner query checks for $R.bid = 103$ and $R.sid = 2$ . If empty, EXISTS is false, and the row is excluded.
  - Repeated iteratively for all rows in Sailors.
- Comparison operators with subqueries:
- ANY: Returns true if the outer attribute satisfies the comparison condition against at least one value returned by the inner query (e.g., WHERE S.rating > ANY (SELECT S2.rating FROM Sailors S2 WHERE S2.sname = 'HAJO')).
- Set intersection alternative using IN: sql SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red' AND S.sid IN ( SELECT R2.sid FROM Reserves R2, Boats B2 WHERE R2.bid = B2.bid AND B2.color = 'green' );

Relational Division in SQL

Relational Division ( $A / B$ ):
- Represents queries requiring universal quantification ("find entities associated with all entities of another set"), such as finding sailors who have reserved all boats.
- Relational algebra expresses division through basic operators: projection, Cartesian product, and set difference: $R / S = \pi_X(R) - \pi_X((\pi_X(R) \times S) - R)$
Expressing Relational Division in SQL Using EXCEPT and NOT EXISTS:
- SQL lacks an explicit DIVIDE BY operator, requiring logical formulation via double negation: "Find sailors such that there does not exist any boat that was not reserved by this sailor."
- SQL formulation: sql SELECT S.sname FROM Sailors S WHERE NOT EXISTS ( (SELECT B.bid FROM Boats B) EXCEPT (SELECT R.bid FROM Reserves R WHERE R.sid = S.sid) );     
- Logical decomposition:
- (SELECT B.bid FROM Boats B): Evaluates to the universal set of all boats.
- (SELECT R.bid FROM Reserves R WHERE R.sid = S.sid): For a given sailor $S.sid$ , evaluates to the set of boats reserved by that sailor.
- (All Boats) EXCEPT (Boats reserved by S.sid): Produces the set of boats that $S.sid$ did not reserve.
- NOT EXISTS (...): Evaluates to true if and only if the set difference is empty (meaning there are zero boats that the sailor failed to reserve).
- Trace across records:
- For $S.sid = 1$ : If the unreserved boat set has tuples, NOT EXISTS is false (sailor $1$ did not reserve all boats).
- For $S.sid = 2$ : If the unreserved boat set is empty ( $\emptyset$ ), NOT EXISTS is true (sailor $2$ reserved all boats, qualifying for output).

Aggregate Functions and Target List Validity

Aggregate Operators:
- Core SQL aggregates include: COUNT(*), COUNT([DISTINCT] A), SUM([DISTINCT] A), AVG([DISTINCT] A), MAX(A), MIN(A).
- COUNT(*) returns the total number of rows meeting row-level qualifications.
Evaluation Scenarios on Sample Sailors Data:
- Example dataset assumptions: Sailors contains tuples with ratings and ages (e.g., three sailors with $rating = 10$ having ages $35$ , $20$ , and $35$ ; multiple sailors named 'Bob').
- Standard Average:
```
SELECT AVG(S.age) FROM Sailors S WHERE S.rating = 10;
&nbsp;&nbsp;&nbsp;&nbsp;```
* Computes average over all qualifying tuples:  $\frac{35 + 20 + 35}{3} = \frac{90}{3} = 30$ .
* Distinct Average:
```
sql SELECT AVG(DISTINCT S.age) FROM Sailors S WHERE S.rating = 10; ```
- Eliminates duplicates before aggregating: distinct ages are $35$ and $20$ .
- Result: $\frac{35 + 20}{2} = \frac{55}{2} = 27.5$ .
- Distinct Count: sql SELECT COUNT(DISTINCT S.rating) FROM Sailors S WHERE S.sname = 'Bob';     
- If two sailors named 'Bob' share the same rating, COUNT(DISTINCT) returns $1$ .
Structural Syntax Rules and Common Errors:
- Querying individual attributes alongside ungrouped aggregates is invalid: sql -- INVALID QUERY SELECT S.sname, MAX(S.age) FROM Sailors S;     
- Explanation: MAX(S.age) computes a single scalar across all rows in the relation, whereas S.sname represents a row-level column. Relational tables cannot produce an output row containing a single aggregate value alongside an unaggregated attribute unless a GROUP BY clause is present.
- Correct nested query formulation to find the name and age of the oldest sailor: sql SELECT S.sname, S.age FROM Sailors S WHERE S.age = ( SELECT MAX(S2.age) FROM Sailors S2 );     
- The inner subquery computes the scalar maximum age ( $\max(age)$ ), and the outer query selects all sailor rows whose age matches that maximum value.

Grouped Aggregation: Conceptual Evaluation and Constraints

Query Syntax:sql SELECT [DISTINCT] target-list FROM relation-list WHERE qualification GROUP BY grouping-list HAVING group-qualification;   
Conceptual Evaluation Algorithm:
- Step 1: Compute the Cartesian cross-product of all relations specified in the FROM relation list.
- Step 2: Discard all rows that fail to satisfy the search conditions in the WHERE clause.
- Step 3: Discard all attributes not present in the SELECT target list, GROUP BY grouping list, or HAVING clause.
- Step 4: Partition remaining tuples into distinct groups matching unique combinations of values in the GROUP BY grouping list (conceptually equivalent to sorting rows by grouping attributes).
- Step 5: Evaluate the HAVING group qualification against each group individually; discard groups that do not satisfy the predicate.
- Step 6: Generate one output row per qualifying group containing values from the target list (evaluating group aggregate functions). If DISTINCT is specified in SELECT, remove duplicate output rows.
Target List Constraint Rule:
- In queries containing a GROUP BY clause, any bare attribute present in the SELECT target list must appear in the GROUP BY list.
- Aggregates compute a single value per group. If an unaggregated attribute is not part of the GROUP BY criteria, it may hold multiple distinct values within the group, making it indeterminate which value to display.
Detailed Execution Walkthrough:
- Query: Find the rating and the minimum age of the youngest sailor with age greater than $18$ for each rating level having at least two such sailors. sql SELECT S.rating, MIN(S.age) FROM Sailors S WHERE S.age > 18 GROUP BY S.rating HAVING COUNT(*) > 1;     
- Execution trace on sample dataset:
- Step 1 (FROM): Read Sailors relation (single table, no cross-product).
- Step 2 (WHERE S.age > 18): Discard sailors aged $\le 18$ (e.g., an individual sailor aged $16$ is removed).
- Step 3 (Projection): Restrict active columns to rating and age.
- Step 4 (GROUP BY S.rating): Partition remaining rows by rating. Groups formed: rating $3$ , rating $7$ , rating $8$ , rating $9$ , rating $10$ .
- Step 5 (HAVING COUNT(*) > 1):
  - Group $9$ contains only $1$ sailor: Discarded.
  - Group $10$ contains only $1$ sailor (after the sailor aged $16$ was removed): Discarded.
  - Group $1$ (if single tuple): Discarded.
  - Groups $3$ , $7$ , and $8$ each contain $\ge 2$ sailors: Retained.
- Step 6 (Final aggregation): For each retained rating group ( $3, 7, 8$ ), compute MIN(S.age) and output one tuple containing (rating, MIN(age)).
- Impact of filtering predicates:
- If WHERE S.age > 18 were omitted, the sailor with rating $10$ and age $16$ would remain in group $10$ . Group $10$ would then have $2$ members, satisfy HAVING COUNT(*) > 1, and appear in the final output.
Compound Group Criteria and Joins:
- Compound group conditions using HAVING: sql SELECT S.rating, MIN(S.age) FROM Sailors S WHERE S.age > 18 GROUP BY S.rating HAVING COUNT(*) > 1 AND EVERY(S.age < 60);     
- Aggregations over multi-table joins:
- Goal: For each red boat, find the total number of reservations. sql SELECT B.bid, COUNT(*) FROM Boats B, Reserves R WHERE B.bid = R.bid AND B.color = 'red' GROUP BY B.bid;     
- The join and selection precede grouping, grouping by B.bid partitions reservations per red boat, and COUNT(*) counts reservations for each boat.

Questions & Discussion

Question: Does the order of relations in the SQL FROM clause or conditions in the WHERE clause matter?
- Answer: In declarative SQL, ordering does not matter. However, in procedural relational algebra and physical query execution, the order of operations matters significantly for execution time and resource consumption.
Question: Why is joining Sailors directly with Boats ( $S \bowtie B$ ) considered invalid?
- Answer: Sailors and Boats share no common schema attributes (Boats lacks sailor ID; Sailors lacks boat ID). Joining them directly without Reserves results in an unintentional Cartesian product.
Question: Between an algebra plan that performs all joins first and one that filters red boats before joining with Reserves, which is better?
- Answer: Filtering boats first ( $\sigma_{\text{color}='\text{red}'}(B)$ ) is significantly better. It produces a small intermediate relation, substantially reducing intermediate join sizes and computing costs compared to joining unreduced relations.
Question: Can a single query find sailors who reserved red and green boats by writing WHERE B.color = 'red' AND B.color = 'green'?
- Answer: No. Each tuple in the Boats table has only one color value. A single row cannot simultaneously have its color equal both red and green; this predicate evaluates to empty/null.
Question: Why is a 5-table join tree preferred over an INTERSECT operator by the query optimizer?
- Answer: The 5-table join creates a fully pipelined (bilineable) tree where intermediate tuples flow continuously between operators. In contrast, INTERSECT acts as a blocking operator that must materialize both input subtrees completely before emitting results.
Question: Will students be required to write complex SQL queries on the exam?
- Answer: No. SQL queries on the exam will be straightforward, and GROUP BY queries will not appear on the exam. However, writing complex relational algebra expressions will be tested.
Question: Is there a practice exam available for the course?
- Answer: No practice exams are provided. Students should prepare using assigned homework and additional relational algebra exercise questions with solutions provided by the teaching assistants.
Question: What is the policy regarding exam materials and course grading?
- Answer: The exam is open-book and open-notes; students may bring any printed materials, but no digital devices or internet access are permitted. The course is graded on a curve: historically, the top $\frac{1}{3}$ of students receive a grade between $A$ and $A-$ . In a previous class of $150$ students, more than $50$ students received between $A$ and $A-$ .
Question: How are Entity-Relationship (ER) diagrams on the homework evaluated?
- Answer: Homework grading standards are handled entirely by the teaching assistants, and questions regarding homework evaluation criteria should be directed to them.