Translation - From Parse Tree to Relational Algebra

The parse tree tells us the structure of the SQL statement—which keywords appear where, how expressions nest, what identifiers are referenced. But structure alone isn't enough. The database must now understand what this query means and how to compute its result.

This is the job of the translation phase (also called semantic analysis or query translation). It transforms the syntactic parse tree into a logical query plan expressed in relational algebra—the mathematical foundation of relational databases.

Translation is where SQL meets database theory. The declarative "what I want" becomes a precise specification of "what operations produce it."

The parser verifies that SQL is syntactically valid—tokens appear in legal sequences. Semantic analysis verifies that SQL is semantically valid—it makes sense in the context of the database schema.

Syntax vs. Semantics:

-- Syntactically valid, semantically invalid:
SELECT unicorn_column FROM nonexistent_table WHERE 'hello' > 42;

This query parses successfully—the structure is correct. But semantic analysis will reject it:

• Table nonexistent_table doesn't exist
• Column unicorn_column is unknown
• Comparing string to integer is a type error (in strict SQL)

Core Semantic Analysis Tasks:

The first semantic task is name resolution: connecting identifiers in the query to actual database objects. This requires consulting the system catalog (also called data dictionary or metadata repository).

The System Catalog:

Every relational database maintains metadata tables describing all objects:

• Tables and Views — Name, schema, owner, columns, storage parameters
• Columns — Name, data type, nullability, default values, constraints
• Indexes — Name, indexed columns, type (B-tree, hash, etc.)
• Functions — Name, arguments, return type, implementation
• Users and Roles — Permissions, grants, ownership
• Constraints — Primary keys, foreign keys, check constraints

Resolution Process:

Schema Search Path:

When a table name isn't schema-qualified (e.g., orders not sales.orders), the database searches schemas in a configured order:

-- PostgreSQL search path
SHOW search_path;
-- Result: "$user", public

-- Table 'orders' will be resolved by checking:
-- 1. schema = current_user (e.g., 'john')
-- 2. schema = 'public'
-- First match wins; if no match, error

-- Explicitly set search path
SET search_path = sales, inventory, public;

Alias Handling:

Aliases create temporary names within query scope. The resolver maintains a scope stack tracking which aliases are valid at each nesting level.

After resolving names, the analyzer must verify that operations are type-safe. This involves checking that operators and functions receive compatible argument types.

Type Checking Rules:

1. Comparison Operations — Operands must be of compatible types (both numeric, both strings, etc.)
2. Arithmetic Operations — Operands must be numeric (integer, float, decimal)
3. Function Calls — Arguments must match the function's parameter types
4. Assignment — Values must be compatible with target column types
5. Aggregate Functions — Input types must match function expectations

Type Coercion:

When types don't exactly match but are compatible, the database applies implicit type coercion (also called type casting or type promotion):

Type Inference:

For expressions and subqueries, the analyzer infers result types by examining the operations:

-- Inferred types for SELECT expressions
SELECT 
    order_id,                    -- Type: from catalog (INTEGER)
    quantity * price AS total,   -- Type: numeric (from * operator)
    UPPER(customer_name),        -- Type: TEXT (from function signature)
    order_date + INTERVAL '7 days' -- Type: TIMESTAMP (date + interval)
FROM orders;

Type information propagates through the query tree, ensuring every expression has a known type before execution planning begins.

With semantic analysis complete, the parse tree transforms into a logical query plan expressed in relational algebra. Relational algebra is the mathematical foundation of relational databases, providing a formal language for expressing data manipulation operations.

Why Relational Algebra?

1. Mathematical Precision — Each operation has rigorous semantics
2. Closure Property — Operations on relations produce relations (enabling composition)
3. Equivalence Rules — Algebraic laws enable query optimization
4. Implementation Independence — Logical operators abstract away physical details

Core Relational Algebra Operators:

Extended Operators for SQL Features:

Standard relational algebra is extended to support SQL's full feature set:

The translator systematically converts SQL constructs into relational algebra operators. Each SQL clause maps to specific algebra operations.

Translation Rules:

Translation Rules for Common SQL Clauses:

Subqueries add complexity to translation. Different subquery types require different handling strategies.

Subquery Types:

Subquery Decorrelation:

Correlated subqueries execute once per outer row—potentially very expensive. The optimizer often "decorrelates" them into equivalent join expressions:

-- Correlated (slow: one subquery execution per customer)
SELECT c.name,
       (SELECT SUM(total) FROM orders WHERE customer_id = c.id) AS total
FROM   customers c;

-- Decorrelated (fast: single join operation)
SELECT c.name, COALESCE(o.total_sum, 0) AS total
FROM   customers c
       LEFT JOIN (
           SELECT customer_id, SUM(total) AS total_sum
           FROM orders
           GROUP BY customer_id
       ) o ON c.id = o.customer_id;

Decorrelation is a key optimization performed during or after translation.

When a query references a view, the translator must expand the view definition into the logical plan. Views are essentially named, stored queries that appear as virtual tables.

View Expansion Process:

1. Detect view reference during name resolution
2. Retrieve view definition from system catalog
3. Parse the view's query (if not already cached)
4. Substitute the view's algebra tree wherever the view is referenced
5. Merge/simplify the resulting tree during optimization

Materialized View Handling:

Unlike regular views, materialized views store computed results. Translation differs:

Some databases perform query rewriting to use materialized views even when the original query doesn't reference them—if the materialized view can answer the query more efficiently.