Selection and Projection

If the Selection operator is a filter, then the predicate is the filter's specification—the precise description of what passes through and what doesn't. The expressiveness and correctness of your queries depend entirely on how well you can articulate predicates.

Predicates in relational algebra form a miniature formal language: a collection of comparison operators, logical connectives, and evaluation rules that together allow you to express arbitrarily complex conditions. Every SQL WHERE clause, every index lookup condition, every join predicate—all are built from this fundamental vocabulary.

Mastering predicates means mastering the precision with which you can describe data requirements. An imprecise predicate returns wrong data. An inefficient predicate causes slow queries. A correct, efficient predicate is the mark of expert database craftsmanship.

At the atomic level, predicates are built from comparison operators that compare two values and return a boolean result. Understanding these operators—their syntax, semantics, and behavior across data types—is fundamental.

The Six Fundamental Comparison Operators:

Operand Types:

Comparison operands can be:

1. Attribute references: Column names that resolve to the tuple's value for that attribute
2. Constants (literals): Fixed values like 100000, 'Engineering', DATE '2023-01-01'
3. Expressions: Computed values like salary * 1.1 or CONCAT(first_name, ' ', last_name)
4. Other attributes: Comparing two columns in the same tuple, like end_date > start_date

Type-Specific Comparison Semantics:

Different data types have different comparison rules:

Numeric Types (INTEGER, DECIMAL, FLOAT):

• Standard mathematical ordering
• Mixed type comparisons: implicit promotion (e.g., INT compared to FLOAT promotes INT to FLOAT)
• Precision considerations: floating-point comparison may have rounding issues

String Types (CHAR, VARCHAR, TEXT):

• Lexicographic (dictionary) ordering based on character encoding
• Case sensitivity depends on collation setting
• Trailing space handling varies by database and type (CHAR pads, VARCHAR doesn't)
• Collation determines ordering (e.g., 'ä' before or after 'b'?)

Date/Time Types (DATE, TIME, TIMESTAMP):

• Chronological ordering
• Time zone considerations for TIMESTAMP WITH TIME ZONE
• Comparison across date and timestamp types requires care

Boolean Types:

• FALSE < TRUE in ordering (by convention)
• Direct equality comparison most common

Atomic comparisons combine using logical connectives to form complex predicates. The three fundamental connectives—AND, OR, and NOT—provide the full expressiveness of propositional logic.

Conjunction (AND, ∧):

The conjunction of P₁ and P₂ is true if and only if both P₁ and P₂ are true.

$$P_1 ∧ P_2 = \begin{cases} TRUE & \text{if } P_1 = TRUE \text{ and } P_2 = TRUE \ FALSE & \text{if } P_1 = FALSE \text{ or } P_2 = FALSE \ UNKNOWN & \text{otherwise (NULL involvement)} \end{cases}$$

Disjunction (OR, ∨):

The disjunction of P₁ and P₂ is true if at least one of P₁ or P₂ is true.

$$P_1 ∨ P_2 = \begin{cases} TRUE & \text{if } P_1 = TRUE \text{ or } P_2 = TRUE \ FALSE & \text{if } P_1 = FALSE \text{ and } P_2 = FALSE \ UNKNOWN & \text{otherwise (NULL involvement)} \end{cases}$$

Negation (NOT, ¬):

Negation inverts the truth value of a predicate.

$$¬P = \begin{cases} TRUE & \text{if } P = FALSE \ FALSE & \text{if } P = TRUE \ UNKNOWN & \text{if } P = UNKNOWN \end{cases}$$

Key Observations from Three-Valued Logic:

1. TRUE dominates OR: If either operand is TRUE, the OR is TRUE regardless of the other operand (even if UNKNOWN).

2. FALSE dominates AND: If either operand is FALSE, the AND is FALSE regardless of the other operand (even if UNKNOWN).

3. UNKNOWN propagates: When the dominant value isn't present, UNKNOWN 'infects' the result.

4. NOT UNKNOWN = UNKNOWN: Negating an unknown value doesn't suddenly make it known.

Short-Circuit Evaluation:

Most database systems use short-circuit evaluation for efficiency:

• P₁ AND P₂: If P₁ is FALSE, P₂ is not evaluated
• P₁ OR P₂: If P₁ is TRUE, P₂ is not evaluated

However, relational algebra is declarative, and the optimizer may reorder predicates. Don't rely on evaluation order for correctness.

When multiple operators appear in a predicate, operator precedence determines the order of evaluation. Misunderstanding precedence is a common source of query bugs.

Standard Precedence (Highest to Lowest):

Critical Implication:

Because AND has higher precedence than OR, the expression:

A OR B AND C

is interpreted as:

A OR (B AND C)

not as:

(A OR B) AND C

These can produce very different results!

Beyond simple comparisons, relational systems support convenient syntactic forms for common predicate patterns: range queries and set membership.

BETWEEN: Closed Range Queries

The BETWEEN predicate tests whether a value falls within an inclusive range:

attribute BETWEEN low AND high ≡ attribute >= low AND attribute <= high

Key Characteristics:

• Inclusive at both ends
• Both endpoints must be specified
• Works with any comparable type (numbers, dates, strings)
• BETWEEN high AND low may return empty result if high < low (behavior varies by DBMS)

NOT BETWEEN:

attribute NOT BETWEEN low AND high ≡ attribute < low OR attribute > high

IN: Set Membership Testing

The IN predicate tests whether a value belongs to a specified set:

attribute IN (value1, value2, ..., valueN)

is equivalent to:

attribute = value1 OR attribute = value2 OR ... OR attribute = valueN

Key Characteristics:

• More readable than multiple OR conditions
• Order of values in the set doesn't matter
• Works with any data type that supports equality comparison
• Often optimized by database engines (hash-based lookup for large sets)

NOT IN:

attribute NOT IN (v1, v2, ..., vN) ≡ attribute ≠ v1 AND attribute ≠ v2 AND ... AND attribute ≠ vN

While pure relational algebra doesn't include pattern matching, practical database systems (and SQL) provide powerful string matching capabilities. Understanding these is essential for working with real-world data.

LIKE: SQL Pattern Matching

The LIKE predicate matches strings against a pattern containing wildcards:

• % (percent): Matches zero or more characters
• _ (underscore): Matches exactly one character

Pattern Examples:

Escape Characters:

To match literal % or _ characters, use an escape character:

SELECT * FROM Products WHERE name LIKE '%50\%%' ESCAPE '\'
-- Matches: '50% off', 'Get 50% discount'

Regular Expressions:

Many databases support full regular expression matching:

• PostgreSQL: column ~ 'pattern' or SIMILAR TO
• MySQL: column REGEXP 'pattern'
• Oracle: REGEXP_LIKE(column, 'pattern')
• SQL Server: No native regex (use LIKE or CLR functions)

Performance Considerations:

Pattern matching predicates have significant performance implications:

1. Prefix patterns ('John%'): Can use B-tree indexes efficiently - O(log n) to find start point
2. Suffix patterns ('%son'): Cannot use standard indexes - requires full scan
3. Infix patterns ('%oh%'): Cannot use standard indexes - requires full scan
4. Full-text search: For efficient substring searching, consider full-text indexes (GIN, inverted indexes)

The order in which predicates are evaluated can dramatically affect query performance. While the logical result doesn't depend on evaluation order (commutativity), the computational cost certainly does.

Evaluation Cost Factors:

1. Selectivity: More selective predicates eliminate more tuples early
2. Computational complexity: Some predicates are cheap (attribute comparison), others expensive (subquery, function call)
3. Index availability: Indexed predicates can be evaluated without full scan
4. Short-circuit opportunity: Earlier FALSE in AND, earlier TRUE in OR saves work

Optimal Evaluation Strategy:

For AND-connected predicates, evaluate in this order:

1. Most selective predicates first (eliminate tuples early)
2. Cheapest predicates first (if selectivity similar)
3. Indexed predicates first (if they dominate selectivity)

For OR-connected predicates:

1. Least selective predicates last (any TRUE satisfies)
2. Cheapest predicates first

Query Optimizer's Role:

Modern query optimizers automatically determine predicate evaluation order based on:

1. Cost-based optimization: Using statistics to estimate selectivity and cost
2. Index awareness: Pushing indexed predicates to access methods
3. Predicate pushdown: Evaluating predicates as early as possible in the plan
4. Predicate simplification: Combining or eliminating redundant predicates

When Optimizer Chooses Wrong:

Optimizers rely on statistics which can be outdated or inaccurate:

• Correlated columns violate independence assumptions
• Unusual data distributions not captured by histograms
• Parameter binding hides actual values at plan time

Manual Intervention:

When optimizer chooses poorly, you can sometimes help:

• Update statistics (ANALYZE / UPDATE STATISTICS)
• Use optimizer hints (database-specific)
• Rewrite predicates to expose optimization opportunities
• Create appropriate indexes for selective predicates

Real-world queries often require sophisticated predicate patterns. Recognizing these patterns helps you structure queries correctly and enables the optimizer to choose efficient execution strategies.

Pattern 1: Multi-Column Equality (Composite Key Lookup)

σ_{department = 'Eng' ∧ role = 'Senior' ∧ location = 'NYC'}(Employee)

This pattern benefits from composite indexes on (department, role, location).

Pattern 2: Range with Equality (Prefix + Range)

σ_{department = 'Eng' ∧ salary BETWEEN 100000 AND 150000}(Employee)

Optimal index: (department, salary) - equality column first, range column second.

Pattern 3: OR with Common Prefix

σ_{department = 'Eng' ∧ (role = 'Senior' ∨ role = 'Lead')}(Employee)

Equivalent to: department = 'Eng' AND role IN ('Senior', 'Lead')

Pattern 4: NOT with Complex Subexpression

σ_{¬(department = 'HR' ∧ salary < 50000)}(Employee)

Using De Morgan: department ≠ 'HR' OR salary >= 50000

Predicate conditions are the precise language for expressing data requirements. Mastering predicates enables you to write correct, efficient, and maintainable queries.

What's Next:

Having thoroughly explored Selection and its predicates, we turn to the complementary operation: Projection. While Selection filters rows (horizontal), Projection selects columns (vertical). Together, they form the foundation for extracting precisely the data you need from any relation.