Tuple Relational Calculus

In the grand architecture of Tuple Relational Calculus, atomic formulas (or simply atoms) are the irreducible primitives—the fundamental assertions that cannot be broken down further. They are the base cases of the recursive formula grammar, the foundation upon which all complex expressions are built.

Understanding atoms with precision is essential because:

1. Every TRC query ultimately reduces to atoms: Complex formulas with nested quantifiers and multiple connectives eventually bottom out at atomic comparisons and range predicates

2. Atoms determine computational cost: Query execution translates atoms into table scans, index lookups, and comparisons—understanding atoms helps predict performance

3. Atoms bridge theory and practice: Each SQL WHERE clause condition corresponds to an atomic formula; mastering atoms means mastering the WHERE clause

4. Type systems operate at the atom level: Schema validation, domain checking, and NULL handling are all atomic-level concerns

This page provides comprehensive coverage of both types of atoms in TRC: range predicates and comparison atoms.

The range predicate is the first type of atomic formula. It asserts that a tuple variable is bound to (i.e., is a member of) a specific relation.

Formal Definition:

R(t) ≡ "tuple variable t is a member of relation R"

Semantics:

Given a database instance D, the range predicate R(t) evaluates as:

• TRUE if the current binding of t is a tuple that exists in R within D
• FALSE if the current binding of t is not in R

Range predicates are membership tests—they answer "Is this tuple in this relation?"

Role in Queries:

Range predicates serve dual purposes:

1. Domain Declaration: They specify which tuples a variable can bind to
2. Filtering: They constrain results to tuples actually in the database

Schema Constraints:

A range predicate R(t) implicitly constrains t to have the same schema as R. If R has schema (A₁: D₁, A₂: D₂, ..., Aₙ: Dₙ), then t must also have these attributes with compatible types.

This enables attribute references in subsequent conditions:

Employee(e) ∧ e.salary > 50000
                ↑
        Valid because Employee schema includes 'salary'

Multiple Range Predicates:

Queries often include multiple range predicates:

{ e, d | Employee(e) ∧ Department(d) ∧ e.dept_id = d.dept_id }

Here, Employee(e) and Department(d) are separate atoms. Both must be TRUE (conjunction) for the formula to be satisfied.

Negative Range Tests:

Negated range predicates test non-membership:

¬Employee(t)  ≡  "t is NOT in Employee"

This is conceptually problematic for free variables (infinite complement), but valid for bound variables in specific contexts.

The comparison atom is the second type of atomic formula. It asserts a relationship between two values using a comparison operator.

Formal Definition:

term₁ θ term₂

Where:

• term₁ and term₂ are terms (attribute references or constants)
• θ is a comparison operator from {=, ≠, <, >, ≤, ≥}

Term Types:

1. Attribute Term: t.A — the value of attribute A in tuple variable t
2. Constant Term: 42, 'Alice', DATE '2024-01-15', NULL

Comparison Patterns:

Type Requirements:

Comparison atoms require type compatibility between operands:

• Numeric types: INTEGER, DECIMAL, FLOAT can be compared freely
• String types: VARCHAR, CHAR use lexicographic ordering
• Date/Time types: Temporal comparison (earlier/later)
• Boolean: Only equality/inequality typically meaningful

Mismatched types are generally errors:

✗ e.name > 50000      -- String vs. Number: Type error
✓ e.salary > 50000    -- Number vs. Number: Valid
✓ e.name > 'M'        -- String vs. String: Valid (lexicographic)

Join Atoms:

Attribute-to-attribute comparisons often express joins:

e.dept_id = d.dept_id    -- Equijoin condition
e.salary > m.salary      -- Theta-join (inequality)
e₁.manager_id = e₂.emp_id -- Self-join

These atoms connect tuples across (or within) relations, enabling relational combination.

Real databases contain NULL values—markers for missing, unknown, or inapplicable data. NULLs introduce three-valued logic (3VL) into atomic formula evaluation.

The Problem with NULL:

Consider: Is NULL = 5 true or false?

• We don't know what NULL represents
• It could be 5, so we can't say FALSE
• It could be something else, so we can't say TRUE
• The only honest answer is: UNKNOWN

Three-Valued Logic:

TRC (and SQL) use three truth values:

3VL Truth Tables:

Logical connectives extend to three values:

Negation (¬):

Conjunction (∧):

Disjunction (∨):

Key Insight: FALSE dominates AND (F ∧ anything = F), TRUE dominates OR (T ∨ anything = T). UNKNOWN propagates otherwise.

Effect on Query Results:

TRC (and SQL) include a tuple in the result only when the formula evaluates to TRUE. UNKNOWN is treated like FALSE for inclusion purposes.

Employee(e) ∧ e.commission > 0

If e.commission is NULL for some employee, this evaluates to UNKNOWN, and that employee is excluded from results.

Pure TRC limits atoms to range predicates and simple comparisons. Extended TRC (and SQL) add richer atomic predicates to handle real-world needs.

IS NULL / IS NOT NULL:

Explicit NULL testing:

t.A IS NULL       -- TRUE iff t.A is NULL
t.A IS NOT NULL   -- TRUE iff t.A has a non-NULL value

These are the only way to definitively test for NULL. The atom t.A = NULL is always UNKNOWN!

BETWEEN:

Range inclusion (syntactic sugar):

t.A BETWEEN x AND y  ≡  t.A >= x ∧ t.A <= y

IN (Set Membership):

Value in a set:

t.A IN (v₁, v₂, ..., vₙ)  ≡  t.A = v₁ ∨ t.A = v₂ ∨ ... ∨ t.A = vₙ

LIKE (Pattern Matching):

String pattern matching:

t.name LIKE 'A%'     -- Names starting with 'A'
t.email LIKE '%@%'   -- Contains '@'
t.code LIKE 'AB_C'   -- 'AB' + any char + 'C'

Patterns: % = any sequence, _ = any single character

Computed Terms (Extended):

Some TRC extensions allow computations within atoms:

e.salary * 1.1 > 60000          -- Computed value comparison
e.first_name || ' ' || e.last_name = 'John Doe'  -- String concatenation
YEAR(e.hire_date) = 2024        -- Function application

These extend the term grammar from simple attribute references to expressions.

Type Casts:

CAST(t.quantity AS DECIMAL) > 10.5
t.date_string::DATE = DATE '2024-01-15'

Aggregate-Based Atoms (Advanced):

While aggregates are typically handled separately, some extended formalisms allow:

e.salary > AVG(SELECT salary FROM Employee)  -- Scalar subquery comparison

This conceptually treats the aggregate as a computed constant for comparison.

Understanding precisely how atoms are evaluated illuminates query execution and optimization.

Range Predicate Evaluation:

To evaluate R(t) given binding of t to tuple τ:

1. Look up relation R in the current database instance D
2. Check if τ ∈ R (membership test)
3. Return TRUE if yes, FALSE if no

Implementation: This might involve:

• Full table scan (worst case)
• Index lookup if τ's key is indexed
• Hash probe if hash index exists

Comparison Atom Evaluation:

To evaluate term₁ θ term₂:

1. Resolve term₁:

   • If attribute (t.A): Look up attribute A in tuple bound to t
   • If constant: Use the constant value directly

2. Resolve term₂: Same process

3. Check NULL:

   • If either value is NULL, result is typically UNKNOWN
   • Exception: IS NULL tests

4. Apply comparison:

   • Execute the comparison operator on the two values
   • Return TRUE, FALSE, or UNKNOWN

Optimization at the Atom Level:

Query optimizers focus heavily on atoms because they determine physical operations:

Selectivity Estimation:

Optimizers estimate selectivity—the fraction of tuples satisfying an atom:

• e.dept_id = 5: If 10 departments with uniform distribution, ~10% selectivity
• e.salary > 100000: Depends on salary distribution, maybe 5%
• e.name LIKE 'A%': ~1/26 ≈ 4% if uniform first-letter distribution

Higher selectivity (fewer matching rows) atoms are often evaluated first.

Every SQL WHERE clause condition is an atomic formula (or combination thereof). Understanding this connection makes SQL natural.

Direct Mappings:

SQL Condition Composition:

SQL's WHERE clause is a conjunction of atoms (or compound conditions):

WHERE atom1 AND atom2 AND atom3 ...

This corresponds to TRC's:

R(t) ∧ atom1 ∧ atom2 ∧ atom3 ...

Disjunctions and negations work similarly:

WHERE (e.dept_id = 5 OR e.dept_id = 7) AND NOT e.status = 'Inactive'

Corresponds to TRC:

Employee(e) ∧ (e.dept_id = 5 ∨ e.dept_id = 7) ∧ ¬(e.status = 'Inactive')

Certain atom patterns recur frequently across queries. Recognizing these idioms accelerates query development.

Pattern 1: Primary Key Lookup

R(t) ∧ t.pk = specific_value

Selects at most one tuple. Highly efficient with B-tree index.

Pattern 2: Foreign Key Join

R(t₁) ∧ S(t₂) ∧ t₁.fk = t₂.pk

Classic equijoin linking related tables.

Pattern 3: Range Filter

R(t) ∧ t.date >= start_date ∧ t.date < end_date

Bounded range, often on indexed date columns.

Pattern 4: Set Membership

R(t) ∧ (t.category = 'A' ∨ t.category = 'B' ∨ t.category = 'C')

Multiple alternatives (IN-list equivalent).

Pattern 5: Optional Value (NULL handling)

R(t) ∧ (t.optional_field = value ∨ t.optional_field IS NULL)

Handles NULLs explicitly when needed.

Pattern 6: Self-Join Comparison

R(t₁) ∧ R(t₂) ∧ t₁.pk ≠ t₂.pk ∧ t₁.attr = t₂.attr

Finds different tuples with matching attributes.

Understanding which atom formulations are equivalent (produce identical results) enables query optimization and simplification.

Basic Equivalences:

t.A > 5 ∧ t.A > 10  ≡  t.A > 10      -- Subsumption
t.A = 5 ∧ t.A = 10  ≡  FALSE          -- Contradiction
t.A = 5 ∨ t.A = 10  ≡  t.A IN (5,10)  -- OR to IN
t.A >= 5 ∧ t.A <= 10 ≡  t.A BETWEEN 5 AND 10

De Morgan with Atoms:

¬(t.A = 5 ∧ t.B = 10)  ≡  t.A ≠ 5 ∨ t.B ≠ 10
¬(t.A = 5 ∨ t.B = 10)  ≡  t.A ≠ 5 ∧ t.B ≠ 10

NULL-aware Equivalences:

t.A = t.A  -- NOT always TRUE! UNKNOWN if t.A is NULL
¬(t.A IS NULL)  ≡  t.A IS NOT NULL

Range Predicate Optimizations:

t.A >= 5 ∧ t.A > 3  ≡  t.A >= 5      -- The >= 5 is stronger
t.A < 10 ∧ t.A <= 10  ≡  t.A < 10    -- The < 10 is stronger

Query Optimizer Transformations:

Optimizers apply these equivalences automatically:

1. Constant Folding: t.A > 3+2 → t.A > 5
2. Contradiction Detection: t.A = 5 AND t.A = 10 → return empty immediately
3. Subsumption Elimination: Remove redundant weaker conditions
4. IN-list Conversion: Multiple ORs on same column → IN
5. Range Consolidation: Multiple range conditions → single range

These transformations preserve semantics while improving execution efficiency.

What's Next:

With atomic formulas thoroughly covered, we'll now explore Complex Formulas—how atoms combine through connectives and quantifiers to express sophisticated queries. We'll see the full power of TRC emerge from these primitive building blocks.