Query Processing and Optimization – Advanced Database Systems

Master Query Processing and Optimization in Advanced Database Systems. Learn Relational Algebra operations, Query Decomposition steps, and Optimization techniques with simple examples.

1. Translating SQL Queries into Relational Algebra

1.1 Introduction to Relational Algebra

Detailed Explanation:

Before a computer can understand and execute an SQL query written by a human, it needs to translate it into a lower-level language. This language is called Relational Algebra.

Think of Relational Algebra as the “machine language” for databases. While SQL is like English (easy for humans), Relational Algebra is like instructions (easy for the database engine to follow).

Key Characteristics:

• Procedural: It tells the system how to get the data, step-by-step.
• Closed System: The output of every operation is a “relation” (a table). This means the output of one operation can become the input for another.

   SQL Query (Human Language)
          |
          v
   [Translation]
          |
          v
   Relational Algebra (Machine Language)
          |
          v
   Execution & Result

Types of Operations:

• Basic Operations: Selection, Projection, Cross Product, Set Difference, Union.
• Additional Operations: Intersection, Join, Division, Renaming.

1.2 Selection Operation (σ)

Detailed Explanation:

The Selection operation is like using a filter. Imagine you have a table of all students in a university. If you only want to see students from the “CS” department, you apply a Selection operation.

Key Rules:

• The condition uses Comparison Operators (=, ≠, <, >, ≤, ≥).
• The condition can use Logical Operators (AND ∧, OR ∨, NOT ¬).
• The output table looks the same structure-wise, but only contains the rows that match the condition.

Example 1:

Consider the EMP table below:

Query: Display only those Employees in the CS department.

• SQL: SELECT * FROM EMP WHERE Dept = ‘CS’
• Relational Algebra: σ_{Dept = ‘CS’}(EMP)

Resulting Relation:

Example 2:

Query: Select only those Employees with the name Smith who are Assistant professors.

• SQL: SELECT * FROM EMP WHERE Name=’Smith’ AND Rank=’Assistant’
• Relational Algebra: σ_{Name = ‘Smith’ ∧ Rank = ‘Assistant’}(EMP)

Resulting Relation:

1.3 Projection Operation (π)

Detailed Explanation:

While Selection cuts the table horizontally (rows), Projection cuts the table vertically (columns). If you only need the “Name” and “Department” from a large employee table, you use Projection.

Key Rules:

• You list the specific column names you want to keep inside the subscript.
• Duplicate Elimination: If the resulting table has duplicate rows (e.g., two people named “Smith” in the same Dept), Projection automatically removes the duplicates.

Example 1:

Using the EMP table again:

Query: Project only the names and departments of the employees.

• SQL: SELECT name, dept FROM EMP
• Relational Algebra: π_{name, dept}(EMP)

Resulting Relation:

Example 2:

Consider the Sailor table:

Query: Select Sname and Rating from Sailor.

• Relational Algebra: π_{Sname, Rating}(Sailor)

Resulting Relation:

1.4 Combining Selection and Projection

Detailed Explanation:

In real-world scenarios, we often want specific columns from specific rows. To do this, we nest the operations.

Example 1:

Query: Show the names of all employees working in the CS department.

Logic: First, find the CS employees (Selection). Then, take only their names (Projection).

• Relational Algebra: π_name(σ_{Dept = ‘CS’}(EMP))

Step 1: Selection
σ (Dept = 'CS') (EMP)
+-------+--------+-----+-----------+
| Name  | Office | Dept| Rank      |
+-------+--------+-----+-----------+
| Smith | 400    | CS  | Assistant |
| Brown | 420    | CS  | Associate |
+-------+--------+-----+-----------+

Step 2: Projection
π (name)
+-------+
| Name  |
+-------+
| Smith |
| Brown |
+-------+

Example 2:

Query: Show the name and rank of those Employees who are not in the CS department or Adjuncts.

• Relational Algebra: π_{name, rank}(σ_{¬(Rank = ‘Adjunct’ ∨ Dept = ‘CS’)}(EMP))

Resulting Relation:

1.5 Cartesian Product (X)

Detailed Explanation:

The Cartesian Product is a brute-force combination. It pairs every possible combination of rows from two tables. This often produces very large tables and is rarely used alone in practical queries, but it forms the basis for Join operations.

Example:

Relation R (People):

Relation S (Menu):

Result (R × S):

1.6 Set Operations (Union, Intersection, Difference)

Detailed Explanation:

These operations work just like sets in mathematics.

Conditions for Union Compatibility:

1. Both tables must have the same number of columns.
2. The first column of Table R and the first column of Table S must have the same data type (e.g., both are Strings), and so on for the second column, third column, etc.

Example Tables:

1. Union (R ∪ S):

Combines all unique rows from both tables.

(Note: Sally Green appears only once because duplicates are removed).

2. Intersection (R ∩ S):

Only the rows that appear in BOTH tables.

3. Set Difference (R – S):

Rows that are in R but NOT in S.

1.7 Join Operations

Detailed Explanation:

The Cartesian Product combines everything. Usually, we only want combinations that make sense (match). This is a Join.

1. Inner Join (Equi Join)

Returns records that have matching values in both tables.

Example: Join S1 and R1 where S1.sid = R1.sid.

Result (S1 ⋈ R1):

2. Left Outer Join

Returns all records from the left table, and matched records from the right table. If no match, the right side contains NULL.

3. Right Outer Join

Returns all records from the right table, and matched records from the left table.

4. Full Outer Join

Returns all records when there is a match in either left or right table.

    Table A           Table B
  [ 1, A ]          [ 1, X ]
  [ 2, B ]          [ 3, Y ]

  INNER JOIN:       LEFT JOIN:        RIGHT JOIN:       FULL JOIN:
  [1, A, X]         [1, A, X]         [1, A, X]         [1, A, X]
                    [2, B, NULL]      [3, NULL, Y]      [2, B, NULL]
                                                         [3, NULL, Y]

1.8 Division Operation (÷)

Detailed Explanation:

The Division operation is useful for finding rows in one table that are associated with all rows in another table.

Example:

Relation A (Supplier-Product): Lists which suppliers supply which products.

Relation B (Products): Lists all products.

Query (A ÷ B): Find suppliers who supply ALL products listed in B.

Relation A (Sales)       Relation B (Products)
Sno | Pno                Pno
----+----               ----
S1  | P1                 P2
S1  | P2                 P4
S2  | P1
S3  | P2
S4  | P2
S4  | P4

Query: Find suppliers who supply ALL products in B (P2 AND P4).

Result (A / B):
Sno
----
S4  (Supplies P2 and P4 - Matches All)

2. Overview of Query Processing

2.1 Definition and Goals

Detailed Explanation:

When you write an SQL query, you are telling the database what you want. You are not telling it how to find it. The database must figure out the best path to retrieve the data. This entire process is called Query Processing.

2.2 Phases of Query Processing

Detailed Explanation:

      [ High-Level SQL Query ]
               |
               v
+-------------------------------------+
|  1. Query Decomposition             |
|  (Parse, Check Syntax/Semantics)    |
+-------------------------------------+
               |
               v
      [ Relational Algebra Expression ]
               |
               v
+-------------------------------------+
|  2. Query Optimization              |
|  (Find the best strategy)           |
+-------------------------------------+
               |
               v
        [ Execution Plan ]
               |
               v
+-------------------------------------+
|  3. Code Generation                 |
+-------------------------------------+
               |
               v
+-------------------------------------+
|  4. Runtime Database Processor      |
|  (Execute the plan)                 |
+-------------------------------------+
               |
               v
        [ Query Output ]

3. Query Decomposition

3.1 Steps in Query Decomposition

Detailed Explanation:

This phase takes your SQL and turns it into an internal format (Relational Algebra) while checking for errors.

1. Analysis

• Checks if the query words are correct (Lexical analysis).
• Checks if the query grammar is correct (Syntactic analysis).
• Verifies table and column names against the System Catalog.
• Checks if operations make sense (e.g., you cannot multiply a String by a Number).

2. Normalization

Converts the query conditions (WHERE clause) into a standard form.

• Conjunctive Normal Form: Conditions connected by AND. (e.g., A AND B AND C).
• Disjunctive Normal Form: Conditions connected by OR. (e.g., (A AND B) OR (C AND D)).

3. Semantic Analysis

Checks if the query makes logical sense.

• Incorrect: Parts of the query don’t contribute to the result (e.g., missing join conditions).
• Contradictory: The conditions cannot be satisfied.
  Example: (position='Manager' AND position='Assistant'). A person cannot be both at the same time. This query simplifies to “False”.

4. Simplification

Removes unnecessary redundancy.

• Eliminates duplicate conditions.
• Applies logical rules (Idempotent rules):
  • p ∧ p = p
  • p ∧ True = p
  • p ∧ False = False
• Checks Access Rights: Does the user have permission to see these tables?

5. Query Restructuring

Converts the query into a more efficient Relational Algebra form using heuristic rules.

• Heuristic: A “rule of thumb” or best practice.
• Common Rule: Perform Selection (filtering) as early as possible to reduce table size before joins.

Example of Restructuring:

Original: Join two huge tables first, then filter by city.

Restructured: Filter each table by city first, then join the smaller results.

4. Query Optimization

4.1 Definition and Goals

Detailed Explanation:

There are usually many ways to execute the same query. The Query Optimizer explores these options and picks the cheapest one.

Example: To find a student by ID:

• Option 1: Scan the table row by row until you find the ID (Slow).
• Option 2: Use an Index (like a book index) to jump directly to the ID (Fast).

The Optimizer chooses Option 2.

4.2 Cost Estimation

Detailed Explanation:

The database keeps statistics about your data, such as:

• Number of rows in each table.
• Number of distinct values in a column.
• Size of the table in bytes.

The optimizer uses these numbers to estimate how many disk reads (I/O) a query will need. Lower I/O = Better Query.

Exam Tips

Practice Challenge Questions for Exam Preparation

This completes Chapter Two: Query Processing and Optimization. Review the Relational Algebra symbols and the phases of query processing carefully. Good luck with your studies!