Database Management SystemsTuple Relational Calculus

Tuple Relational Calculus

LevelIntermediate

Duration75 mins

TopicTuple Relational Calculus

3 / 5

Formula Syntax

The Language of Tuple Relational Calculus

Having established tuple variables (our "nouns") and range expressions (their "domains"), we now turn to the formula syntax—the complete grammar that allows us to express arbitrarily complex conditions in Tuple Relational Calculus.

A TRC formula is a well-formed logical expression that evaluates to either TRUE or FALSE for each possible binding of its free variables. The power of TRC lies in this formula language: it can express selection, projection, joins, set operations, and complex nested conditions—all through logical predicates.

This page provides the complete formal grammar of TRC formulas, establishing the precise rules for what constitutes a valid expression. Understanding this grammar is essential for:

Writing correct queries: Knowing what constructs are legal
Reading formal specifications: Parsing TRC expressions in literature
Understanding SQL's foundations: Recognizing SQL clauses as formula components
Debugging queries: Identifying malformed expressions

What You Will Learn

By the end of this page, you will understand the complete BNF grammar of TRC formulas, master logical connectives and their semantics, understand operator precedence, and be able to construct and parse complex TRC expressions with precision.

Formal Grammar of TRC Formulas

The formula language of TRC can be defined precisely using Backus-Naur Form (BNF). This grammar specifies exactly which expressions are syntactically valid.

Complete TRC Grammar:

query       ::= '{' target '|' formula '}'

target      ::= tuple-var 
              | tuple-var '.' attr-name
              | target ',' target

formula     ::= atom
              | '(' formula ')'
              | '¬' formula
              | formula '∧' formula
              | formula '∨' formula
              | formula '→' formula
              | '∃' tuple-var '(' formula ')'
              | '∀' tuple-var '(' formula ')'

atom        ::= rel-name '(' tuple-var ')'
              | tuple-var '.' attr-name  op  tuple-var '.' attr-name
              | tuple-var '.' attr-name  op  constant
              | constant  op  tuple-var '.' attr-name

op          ::= '=' | '≠' | '<' | '>' | '≤' | '≥'

tuple-var   ::= identifier
rel-name    ::= identifier
attr-name   ::= identifier
constant    ::= string | number | date | null

Reading the Grammar

In BNF, ::= means 'is defined as', | means 'or' (alternatives), and quoted symbols are terminals. So a formula can be an atom, a parenthesized formula, a negation, a conjunction, etc. This recursive definition allows formulas of arbitrary complexity.

Grammar Components Explained:

Query Structure: A complete query has a target list (what to return) and a formula (conditions), separated by |.

Target Expression: The target can be:

A whole tuple variable: e (returns complete Employee tuples)
A specific attribute: e.name (returns just names)
A comma-separated list: e.name, e.salary (returns projections)

Formula Categories: Formulas are built from:

Atoms: Primitive building blocks (range predicates, comparisons)
Compound Formulas: Combinations using logical operators
Quantified Formulas: Existential (∃) and universal (∀) expressions

Operators: Comparison operators (=, ≠, <, >, ≤, ≥) create atomic conditions by comparing:

Two tuple variable attributes: e.salary > m.salary
An attribute to a constant: e.salary > 50000

TRC Grammar Elements
Element	Productions	Purpose
Query	`{ target \| formula }`	Complete TRC expression
Target	Variable, attribute, or list	Specifies result structure
Formula	Atom or compound	Specifies conditions
Atom	Range or comparison	Primitive conditions
Connective	`¬`, `∧`, `∨`, `→`	Combine formulas logically
Quantifier	`∃`, `∀`	Existential/universal assertions

Logical Connectives in Detail

TRC uses first-order predicate logic connectives to combine atomic formulas into complex expressions. Each connective has precise semantics.

Negation (¬ or NOT):

¬P is TRUE if and only if P is FALSE

Examples:

¬(e.dept_id = 5) — department is not 5
¬∃d(Department(d) ∧ ...) — no such department exists

Conjunction (∧ or AND):

P ∧ Q is TRUE if and only if both P and Q are TRUE

Examples:

e.salary > 50000 ∧ e.dept_id = 5 — both conditions must hold
Employee(e) ∧ e.age > 30 ∧ e.tenure > 5 — all three required

Disjunction (∨ or OR):

P ∨ Q is TRUE if and only if P is TRUE, Q is TRUE, or both are TRUE

Examples:

e.dept_id = 5 ∨ e.dept_id = 7 — either department
e.title = 'Manager' ∨ e.salary > 100000 — managers or high earners

Implication (→ or IMPLIES):

P → Q is TRUE if and only if P is FALSE or Q is TRUE (equivalent to ¬P ∨ Q)

Examples:

Employee(e) → e.salary > 0 — if e is an employee, salary must be positive
Crucial for safe universal quantification

Truth Tables for Logical Connectives
P	Q	¬P	P ∧ Q	P ∨ Q	P → Q
T	T	F	T	T	T
T	F	F	F	T	F
F	T	T	F	T	T
F	F	T	F	F	T

Implication Intuition

The implication P → Q might seem counterintuitive when P is false. The key insight: P → Q only makes a claim about cases where P is true. When P is false, the implication is 'vacuously true'—it doesn't apply. This is essential for the universal quantifier pattern: ∀t(R(t) → condition) says 'for tuples in R, condition holds' and ignores non-R tuples.

Equivalences for Query Transformation:

Understanding logical equivalences helps simplify and transform queries:

Equivalence	Name
`¬(¬P) ≡ P`	Double Negation
`¬(P ∧ Q) ≡ ¬P ∨ ¬Q`	De Morgan's Law
`¬(P ∨ Q) ≡ ¬P ∧ ¬Q`	De Morgan's Law
`P → Q ≡ ¬P ∨ Q`	Implication as Disjunction
`P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)`	Distribution
`P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)`	Distribution
`∀t(P(t)) ≡ ¬∃t(¬P(t))`	Quantifier Duality
`∃t(P(t)) ≡ ¬∀t(¬P(t))`	Quantifier Duality

These equivalences are the foundation for query optimization—rewriting queries into more efficient forms while preserving semantics.

Quantifiers in TRC Grammar

Quantifiers extend TRC beyond simple selection to express conditions involving the existence or absence of tuples, enabling queries that relational algebra cannot express as directly.

Existential Quantifier (∃):

Syntax: ∃t(formula)

Semantics: True if there exists at least one tuple binding for t that makes the formula true.

∃t(R(t) ∧ condition(t))

This is true if at least one tuple in R satisfies the condition.

Universal Quantifier (∀):

Syntax: ∀t(formula)

Semantics: True if every possible tuple binding for t makes the formula true.

∀t(R(t) → condition(t))

This is true if every tuple in R satisfies the condition (the implication handles non-R tuples).

quantifier-examples.trc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- EXISTENTIAL: Departments with at least one high earner
{ d | Department(d) ∧ 
      ∃e(Employee(e) ∧ e.dept_id = d.dept_id ∧ e.salary > 100000) }
 
-- UNIVERSAL: Departments where everyone earns > 50000
{ d | Department(d) ∧ 
      ∀e(Employee(e) ∧ e.dept_id = d.dept_id → e.salary > 50000) }
 
-- NEGATED EXISTENTIAL (equivalent to universal complement):
-- Departments with no low earners (same as above)
{ d | Department(d) ∧ 
      ¬∃e(Employee(e) ∧ e.dept_id = d.dept_id ∧ e.salary ≤ 50000) }
 
-- NESTED QUANTIFIERS: Employees managing someone who manages someone
{ e | Employee(e) ∧ 
      ∃m(Employee(m) ∧ m.manager_id = e.emp_id ∧
         ∃s(Employee(s) ∧ s.manager_id = m.emp_id)) }

Quantifier Scope:

Scope determines where a quantified variable is valid:

∃e(Employee(e) ∧ e.salary > 50000) ∧ e.name = 'Alice'
                                       ↑ ERROR: e is out of scope!

The variable e is bound within the parentheses of ∃e(...). Referencing it outside is a scope error.

Correct:

∃e(Employee(e) ∧ e.salary > 50000 ∧ e.name = 'Alice')

All references to e are within the quantifier's scope.

Quantifier Nesting:

Quantifiers can nest arbitrarily deep:

{ x | ∃y(∀z(condition(x, y, z))) }

The evaluation order is outside-in:

For each binding of x (free variable)
Check if there exists a y such that
For all z, the condition holds

Bound Variable Naming:

Bound variable names are arbitrary—they're placeholders:

∃e(Employee(e) ∧ e.salary > 50000)
∃x(Employee(x) ∧ x.salary > 50000)

These are semantically identical (α-equivalence). The name doesn't matter as long as it's consistent within its scope and doesn't shadow an outer variable unintentionally.

Variable Shadowing

If an outer variable has the same name as an inner bound variable, the inner one 'shadows' the outer in its scope. This creates confusing queries. Best practice: use distinct names. For example, don't use e as both a free variable and inside ∃e(...).

Operator Precedence and Associativity

Like arithmetic expressions, logical formulas have operator precedence rules that determine how expressions are parsed when parentheses are omitted.

Standard TRC Precedence (highest to lowest):

Parentheses ( ) — highest, explicit grouping
Comparison operators =, ≠, <, >, ≤, ≥ — form atoms
Negation ¬ — unary, right-associative
Conjunction ∧ — binary, left-associative
Disjunction ∨ — binary, left-associative
Implication → — binary, right-associative
Quantifiers ∃, ∀ — extend to the right as far as possible

Precedence Examples
Expression	Parsed As	Explanation
`P ∧ Q ∨ R`	`(P ∧ Q) ∨ R`	∧ binds tighter than ∨
`¬P ∧ Q`	`(¬P) ∧ Q`	¬ binds tightest
`P ∨ Q ∧ R`	`P ∨ (Q ∧ R)`	∧ binds tighter than ∨
`P → Q → R`	`P → (Q → R)`	→ is right-associative
`¬P ∨ Q`	`(¬P) ∨ Q`	Not `¬(P ∨ Q)`
`∃t P(t) ∧ Q`	`(∃t P(t)) ∧ Q`	Quantifier scope defined by parens

When in Doubt, Parenthesize

While precedence rules exist, complex expressions are clearer with explicit parentheses. Write (P ∧ Q) ∨ (R ∧ S) rather than relying on readers to remember that ∧ binds tighter than ∨. Clarity beats brevity in formal specifications.

Quantifier Scope Conventions:

Quantifiers typically extend to the right as far as syntax allows, but conventions vary:

Convention 1 (Minimal Scope):

∃e Employee(e) ∧ e.salary > 50000

Means: (∃e Employee(e)) ∧ e.salary > 50000 — ERROR, e out of scope!

Convention 2 (Maximal Scope):

∃e Employee(e) ∧ e.salary > 50000

Means: ∃e(Employee(e) ∧ e.salary > 50000) — e in scope throughout.

Best Practice: Always use parentheses with quantifiers:

∃e(Employee(e) ∧ e.salary > 50000)

This removes all ambiguity about scope.

Associativity Details:

∧ and ∨ are left-associative: P ∧ Q ∧ R = ((P ∧ Q) ∧ R)
Since ∧ and ∨ are associative operations, this doesn't change results
→ is right-associative: P → Q → R = P → (Q → R)
This matches mathematical convention for chained implications

Well-Formedness Rules

Not every string matching the grammar is a valid TRC query. Additional well-formedness rules ensure semantic correctness.

Rule 1: Variable Declaration

Every tuple variable must be declared (given a range) before use:

✗ { e.name | e.salary > 50000 }           -- e has no range
✓ { e.name | Employee(e) ∧ e.salary > 50000 }  -- e ranges over Employee

Rule 2: Attribute Existence

Attribute references must match the variable's range schema:

✗ { e | Employee(e) ∧ e.budget > 1000000 }  -- Employee has no 'budget'
✓ { d | Department(d) ∧ d.budget > 1000000 } -- Department has 'budget'

Rule 3: Type Compatibility

Comparisons must involve type-compatible operands:

✗ { e | Employee(e) ∧ e.name > 50000 }      -- string vs number
✓ { e | Employee(e) ∧ e.salary > 50000 }    -- number vs number

Rule 4: Free Variable Requirement

The target list must include exactly the free variables of the formula (in some formulations):

✗ { e, d | Employee(e) ∧ e.salary > 50000 } -- d is not declared
✓ { e | Employee(e) ∧ e.salary > 50000 }    -- e is properly declared

Common Well-Formedness Errors

•Unbound Variable: Using a variable without declaring its range
•Scope Escape: Referencing a bound variable outside its quantifier scope
•Schema Mismatch: Accessing an attribute that doesn't exist in the range relation
•Type Error: Comparing incompatible types (string = integer)
•Shadowing Confusion: Reusing a variable name in nested scopes
•Missing Target: Empty target list or target variables not in formula

well-formedness-examples.trc
1
2
3
4
5
6
7
8
9
10
11
12
13
-- INCORRECT: Multiple well-formedness violations
{ x | y.salary > 50000 }                    -- x unused, y undeclared
 
-- INCORRECT: Scope escape
{ e | Employee(e) ∧ ∃d(Department(d) ∧ d.dept_id = 5) ∧ d.name = 'HR' }
--    d is bound inside ∃, but referenced outside                    ↑ ERROR
 
-- INCORRECT: Schema mismatch  
{ e | Employee(e) ∧ e.budget > 1000000 }    -- Employee has no 'budget' attribute
 
-- CORRECT: Properly formed query
{ e | Employee(e) ∧ 
      ∃d(Department(d) ∧ e.dept_id = d.dept_id ∧ d.budget > 1000000) }

Static Checking

Well-formedness can be checked statically (before execution) by analyzing the query structure against the database schema. SQL parsers and optimizers perform this checking—syntax errors and unknown column references are caught at parse time, not runtime.

Comparison Operators and Atomic Formulas

Atomic formulas are the primitive building blocks that compare values and assert range membership. All complex formulas are built from atoms.

Types of Atoms:

Range Predicate: R(t) — asserts that tuple variable t is in relation R
Attribute Comparison: t₁.A op t₂.B — compares attributes of two tuple variables
Constant Comparison: t.A op constant — compares an attribute to a literal value

Comparison Operators:

TRC Comparison Operators
Operator	Symbol(s)	Meaning	SQL Equivalent
Equality	`=`	Values are equal	`=`
Inequality	`≠`, `<>`, `!=`	Values are not equal	`<>` or `!=`
Less Than	`<`	Left is strictly less than right	`<`
Greater Than	`>`	Left is strictly greater than right	`>`
Less or Equal	`≤`, `<=`	Left is at most right	`<=`
Greater or Equal	`≥`, `>=`	Left is at least right	`>=`

Operand Types:

Comparison operands can be:

Tuple Variable Attributes: e.salary, d.budget
Constants: 50000, 'Alice', DATE '2024-01-15'
Computed Values (in extended TRC): e.salary * 1.1

NULL Handling:

NULL values require special consideration:

NULL = NULL is unknown (not TRUE) in three-valued logic
NULL > 50000 is unknown
Any comparison involving NULL typically evaluates to unknown

TRC (and SQL) adopt three-valued logic: TRUE, FALSE, UNKNOWN. Rows are included in results only when conditions evaluate to TRUE (not UNKNOWN).

Pattern Matching (Extended):

Pure TRC supports exact comparisons. Extended versions may include:

LIKE patterns: e.name LIKE 'A%'
Regular expressions: e.email MATCHES '.*@gmail\.com'
Substring tests: CONTAINS(e.description, 'urgent')

These are handled by extending the atom grammar.

atomic-formulas.trc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-- RANGE ATOMS
Employee(e)                              -- e is in Employee
Department(d)                            -- d is in Department
 
-- ATTRIBUTE-TO-ATTRIBUTE COMPARISONS
e.dept_id = d.dept_id                    -- Foreign key match
e₁.salary > e₂.salary                    -- Self-join comparison
p.start_date < p.end_date                -- Within-tuple comparison
 
-- ATTRIBUTE-TO-CONSTANT COMPARISONS
e.salary > 50000                         -- Threshold filter
e.name = 'Alice'                         -- Exact match
e.hire_date >= DATE '2020-01-01'         -- Date comparison
d.budget ≤ 1000000                       -- Upper bound
 
-- COMBINED IN FORMULAS
{ e | Employee(e) ∧ 
      e.salary > 50000 ∧ 
      e.dept_id = 5 ∧
      ∃m(Employee(m) ∧ e.manager_id = m.emp_id ∧ m.title = 'Director') }

Building Complex Formulas

With atoms and connectives established, we can construct formulas of arbitrary complexity. This section demonstrates the compositional building of expressive queries.

Level 1: Simple Selection

Single relation, single condition:

{ e | Employee(e) ∧ e.salary > 50000 }

Level 2: Multiple Conditions

Conjunctions and disjunctions:

{ e | Employee(e) ∧ e.salary > 50000 ∧ (e.dept_id = 5 ∨ e.dept_id = 7) }

Level 3: Multi-Relation Joins

Free variables from multiple relations:

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

Level 4: Existential Subqueries

Conditions depending on the existence of related data:

{ e | Employee(e) ∧ ∃p(Project(p) ∧ p.lead_id = e.emp_id) }

Level 5: Universal Conditions

Conditions that must hold for all related tuples:

{ d | Department(d) ∧ ∀e(Employee(e) ∧ e.dept_id = d.dept_id → e.salary > 50000) }

Level 6: Nested Quantification

Multiple layers of quantifiers:

{ d | Department(d) ∧ 
      ∃e(Employee(e) ∧ e.dept_id = d.dept_id ∧
         ∀p(Project(p) ∧ p.dept_id = d.dept_id → 
            ∃a(Assignment(a) ∧ a.emp_id = e.emp_id ∧ a.proj_id = p.proj_id))) }

This finds departments where at least one employee works on ALL department projects.

Complex Query ConstructionFind employees who earn more than everyone in the Sales department

Input

Step-by-step construction:

1. Base: Employee(e)
2. Add quantifier: ∀s(...)
3. Quantifier body: Employee(s) ∧ s.dept_id = (Sales dept_id) → e.salary > s.salary
4. Complete: { e | Employee(e) ∧ ∀s(Employee(s) ∧ s.dept_id = 1 → e.salary > s.salary) }

Output

Employees earning more than all Sales department members

Explanation

The universal quantifier asserts that for every Sales employee s, our candidate e earns more. This includes e themselves if in Sales (requiring e.salary > e.salary which is false), so the result may exclude Sales employees.

Build Incrementally

Construct complex formulas incrementally: start with the simplest version, verify it works, then add conditions one by one. This approach makes debugging easier and helps ensure each component is correct before combining.

SQL Translation of Formula Syntax

Understanding how TRC formula syntax maps to SQL reinforces comprehension and provides practical applicability.

Formula to SQL Mappings:

TRC to SQL Translation
TRC Construct	SQL Equivalent
`R(t)`	`FROM R AS t`
`t.A = value`	`t.A = value` in WHERE
`P ∧ Q`	`P AND Q`
`P ∨ Q`	`P OR Q`
`¬P`	`NOT P`
`∃t(R(t) ∧ P(t))`	`EXISTS (SELECT 1 FROM R t WHERE P)`
`∀t(R(t) → P(t))`	`NOT EXISTS (SELECT 1 FROM R t WHERE NOT P)`

trc-to-sql-translation.sql

-- TRC: Find employees in high-budget departments with at least one project
-- { e | Employee(e) ∧ 
--       ∃d(Department(d) ∧ e.dept_id = d.dept_id ∧ d.budget > 1000000) ∧
--       ∃p(Project(p) ∧ p.lead_id = e.emp_id) }
 
-- SQL Translation:
SELECT e.*
FROM Employee AS e
WHERE EXISTS (
    SELECT 1 
    FROM Department AS d 
    WHERE e.dept_id = d.dept_id 
      AND d.budget > 1000000
)
AND EXISTS (
    SELECT 1 
    FROM Project AS p 
    WHERE p.lead_id = e.emp_id
);
 
-- TRC: Find departments where ALL employees earn > 50000
-- { d | Department(d) ∧ 
--       ∀e(Employee(e) ∧ e.dept_id = d.dept_id → e.salary > 50000) }
 
-- SQL Translation (using double negation):
SELECT d.*
FROM Department AS d
WHERE NOT EXISTS (
    SELECT 1 
    FROM Employee AS e 
    WHERE e.dept_id = d.dept_id 
      AND e.salary <= 50000  -- Negation of the consequent
);

The Power of EXISTS

SQL's EXISTS clause is the direct implementation of TRC's existential quantifier. Mastering EXISTS (and NOT EXISTS for universals) gives you the full expressive power of TRC in practical SQL queries. This is often more efficient than alternatives like IN subqueries or joins.

Summary: Mastering Formula Syntax

Key Takeaways

•Grammar Foundation: TRC formulas follow a recursive BNF grammar with atoms, connectives, and quantifiers as building blocks
•Logical Connectives: ¬ (NOT), ∧ (AND), ∨ (OR), → (IMPLIES) combine formulas with precise truth-table semantics
•Quantifiers: ∃ (exists) and ∀ (for all) enable conditions over sets of tuples, with ∀ requiring implication for safety
•Operator Precedence: Standard precedence (¬ > ∧ > ∨ > →) governs parsing; parentheses provide clarity
•Well-Formedness: Queries must satisfy rules: variable declaration, attribute existence, type compatibility, scope correctness
•Atomic Formulas: Range predicates R(t) and comparisons (=, ≠, <, >, ≤, ≥) are the primitive conditions
•Compositional Building: Complex queries are built incrementally from simple formulas using logical combination

What's Next:

Having mastered the formula syntax, we'll now dive deeper into Atomic Formulas—the primitive building blocks of all TRC expressions. We'll explore the precise semantics of range predicates and comparison atoms in exhaustive detail.

Page Complete

You now command the complete grammar of TRC formulas—from the formal BNF specification to practical SQL translation. This syntactic mastery enables you to read, write, and debug TRC expressions with precision.

3 / 5

Loading learning content...

Database Management SystemsTuple Relational Calculus

Tuple Relational Calculus

LevelIntermediate

Duration75 mins

TopicTuple Relational Calculus

3 / 5

Formula Syntax

The Language of Tuple Relational Calculus

This page provides the complete formal grammar of TRC formulas, establishing the precise rules for what constitutes a valid expression. Understanding this grammar is essential for:

Writing correct queries: Knowing what constructs are legal
Reading formal specifications: Parsing TRC expressions in literature
Understanding SQL's foundations: Recognizing SQL clauses as formula components
Debugging queries: Identifying malformed expressions

What You Will Learn

Formal Grammar of TRC Formulas

The formula language of TRC can be defined precisely using Backus-Naur Form (BNF). This grammar specifies exactly which expressions are syntactically valid.

Complete TRC Grammar:

query       ::= '{' target '|' formula '}'

target      ::= tuple-var 
              | tuple-var '.' attr-name
              | target ',' target

formula     ::= atom
              | '(' formula ')'
              | '¬' formula
              | formula '∧' formula
              | formula '∨' formula
              | formula '→' formula
              | '∃' tuple-var '(' formula ')'
              | '∀' tuple-var '(' formula ')'

atom        ::= rel-name '(' tuple-var ')'
              | tuple-var '.' attr-name  op  tuple-var '.' attr-name
              | tuple-var '.' attr-name  op  constant
              | constant  op  tuple-var '.' attr-name

op          ::= '=' | '≠' | '<' | '>' | '≤' | '≥'

tuple-var   ::= identifier
rel-name    ::= identifier
attr-name   ::= identifier
constant    ::= string | number | date | null

Reading the Grammar

Grammar Components Explained:

Query Structure: A complete query has a target list (what to return) and a formula (conditions), separated by |.

Target Expression: The target can be:

A whole tuple variable: e (returns complete Employee tuples)
A specific attribute: e.name (returns just names)
A comma-separated list: e.name, e.salary (returns projections)

Formula Categories: Formulas are built from:

Atoms: Primitive building blocks (range predicates, comparisons)
Compound Formulas: Combinations using logical operators
Quantified Formulas: Existential (∃) and universal (∀) expressions

Operators: Comparison operators (=, ≠, <, >, ≤, ≥) create atomic conditions by comparing:

Two tuple variable attributes: e.salary > m.salary
An attribute to a constant: e.salary > 50000

TRC Grammar Elements
Element	Productions	Purpose
Query	`{ target \| formula }`	Complete TRC expression
Target	Variable, attribute, or list	Specifies result structure
Formula	Atom or compound	Specifies conditions
Atom	Range or comparison	Primitive conditions
Connective	`¬`, `∧`, `∨`, `→`	Combine formulas logically
Quantifier	`∃`, `∀`	Existential/universal assertions

Logical Connectives in Detail

TRC uses first-order predicate logic connectives to combine atomic formulas into complex expressions. Each connective has precise semantics.

Negation (¬ or NOT):

¬P is TRUE if and only if P is FALSE

Examples:

¬(e.dept_id = 5) — department is not 5
¬∃d(Department(d) ∧ ...) — no such department exists

Conjunction (∧ or AND):

P ∧ Q is TRUE if and only if both P and Q are TRUE

Examples:

e.salary > 50000 ∧ e.dept_id = 5 — both conditions must hold
Employee(e) ∧ e.age > 30 ∧ e.tenure > 5 — all three required

Disjunction (∨ or OR):

P ∨ Q is TRUE if and only if P is TRUE, Q is TRUE, or both are TRUE

Examples:

e.dept_id = 5 ∨ e.dept_id = 7 — either department
e.title = 'Manager' ∨ e.salary > 100000 — managers or high earners

Implication (→ or IMPLIES):

P → Q is TRUE if and only if P is FALSE or Q is TRUE (equivalent to ¬P ∨ Q)

Examples:

Employee(e) → e.salary > 0 — if e is an employee, salary must be positive
Crucial for safe universal quantification

Truth Tables for Logical Connectives
P	Q	¬P	P ∧ Q	P ∨ Q	P → Q
T	T	F	T	T	T
T	F	F	F	T	F
F	T	T	F	T	T
F	F	T	F	F	T

Implication Intuition

Equivalences for Query Transformation:

Understanding logical equivalences helps simplify and transform queries:

Equivalence	Name
`¬(¬P) ≡ P`	Double Negation
`¬(P ∧ Q) ≡ ¬P ∨ ¬Q`	De Morgan's Law
`¬(P ∨ Q) ≡ ¬P ∧ ¬Q`	De Morgan's Law
`P → Q ≡ ¬P ∨ Q`	Implication as Disjunction
`P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)`	Distribution
`P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)`	Distribution
`∀t(P(t)) ≡ ¬∃t(¬P(t))`	Quantifier Duality
`∃t(P(t)) ≡ ¬∀t(¬P(t))`	Quantifier Duality

These equivalences are the foundation for query optimization—rewriting queries into more efficient forms while preserving semantics.

Quantifiers in TRC Grammar

Quantifiers extend TRC beyond simple selection to express conditions involving the existence or absence of tuples, enabling queries that relational algebra cannot express as directly.

Existential Quantifier (∃):

Syntax: ∃t(formula)

Semantics: True if there exists at least one tuple binding for t that makes the formula true.

∃t(R(t) ∧ condition(t))

This is true if at least one tuple in R satisfies the condition.

Universal Quantifier (∀):

Syntax: ∀t(formula)

Semantics: True if every possible tuple binding for t makes the formula true.

∀t(R(t) → condition(t))

This is true if every tuple in R satisfies the condition (the implication handles non-R tuples).

quantifier-examples.trc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- EXISTENTIAL: Departments with at least one high earner
{ d | Department(d) ∧ 
      ∃e(Employee(e) ∧ e.dept_id = d.dept_id ∧ e.salary > 100000) }
 
-- UNIVERSAL: Departments where everyone earns > 50000
{ d | Department(d) ∧ 
      ∀e(Employee(e) ∧ e.dept_id = d.dept_id → e.salary > 50000) }
 
-- NEGATED EXISTENTIAL (equivalent to universal complement):
-- Departments with no low earners (same as above)
{ d | Department(d) ∧ 
      ¬∃e(Employee(e) ∧ e.dept_id = d.dept_id ∧ e.salary ≤ 50000) }
 
-- NESTED QUANTIFIERS: Employees managing someone who manages someone
{ e | Employee(e) ∧ 
      ∃m(Employee(m) ∧ m.manager_id = e.emp_id ∧
         ∃s(Employee(s) ∧ s.manager_id = m.emp_id)) }

Quantifier Scope:

Scope determines where a quantified variable is valid:

∃e(Employee(e) ∧ e.salary > 50000) ∧ e.name = 'Alice'
                                       ↑ ERROR: e is out of scope!

The variable e is bound within the parentheses of ∃e(...). Referencing it outside is a scope error.

Correct:

∃e(Employee(e) ∧ e.salary > 50000 ∧ e.name = 'Alice')

All references to e are within the quantifier's scope.

Quantifier Nesting:

Quantifiers can nest arbitrarily deep:

{ x | ∃y(∀z(condition(x, y, z))) }

The evaluation order is outside-in:

For each binding of x (free variable)
Check if there exists a y such that
For all z, the condition holds

Bound Variable Naming:

Bound variable names are arbitrary—they're placeholders:

∃e(Employee(e) ∧ e.salary > 50000)
∃x(Employee(x) ∧ x.salary > 50000)

These are semantically identical (α-equivalence). The name doesn't matter as long as it's consistent within its scope and doesn't shadow an outer variable unintentionally.

Variable Shadowing

Operator Precedence and Associativity

Like arithmetic expressions, logical formulas have operator precedence rules that determine how expressions are parsed when parentheses are omitted.

Standard TRC Precedence (highest to lowest):

Parentheses ( ) — highest, explicit grouping
Comparison operators =, ≠, <, >, ≤, ≥ — form atoms
Negation ¬ — unary, right-associative
Conjunction ∧ — binary, left-associative
Disjunction ∨ — binary, left-associative
Implication → — binary, right-associative
Quantifiers ∃, ∀ — extend to the right as far as possible

Precedence Examples
Expression	Parsed As	Explanation
`P ∧ Q ∨ R`	`(P ∧ Q) ∨ R`	∧ binds tighter than ∨
`¬P ∧ Q`	`(¬P) ∧ Q`	¬ binds tightest
`P ∨ Q ∧ R`	`P ∨ (Q ∧ R)`	∧ binds tighter than ∨
`P → Q → R`	`P → (Q → R)`	→ is right-associative
`¬P ∨ Q`	`(¬P) ∨ Q`	Not `¬(P ∨ Q)`
`∃t P(t) ∧ Q`	`(∃t P(t)) ∧ Q`	Quantifier scope defined by parens

When in Doubt, Parenthesize

Quantifier Scope Conventions:

Quantifiers typically extend to the right as far as syntax allows, but conventions vary:

Convention 1 (Minimal Scope):

∃e Employee(e) ∧ e.salary > 50000

Means: (∃e Employee(e)) ∧ e.salary > 50000 — ERROR, e out of scope!

Convention 2 (Maximal Scope):

∃e Employee(e) ∧ e.salary > 50000

Means: ∃e(Employee(e) ∧ e.salary > 50000) — e in scope throughout.

Best Practice: Always use parentheses with quantifiers:

∃e(Employee(e) ∧ e.salary > 50000)

This removes all ambiguity about scope.

Associativity Details:

∧ and ∨ are left-associative: P ∧ Q ∧ R = ((P ∧ Q) ∧ R)
Since ∧ and ∨ are associative operations, this doesn't change results
→ is right-associative: P → Q → R = P → (Q → R)
This matches mathematical convention for chained implications

Well-Formedness Rules

Not every string matching the grammar is a valid TRC query. Additional well-formedness rules ensure semantic correctness.

Rule 1: Variable Declaration

Every tuple variable must be declared (given a range) before use:

✗ { e.name | e.salary > 50000 }           -- e has no range
✓ { e.name | Employee(e) ∧ e.salary > 50000 }  -- e ranges over Employee

Rule 2: Attribute Existence

Attribute references must match the variable's range schema:

✗ { e | Employee(e) ∧ e.budget > 1000000 }  -- Employee has no 'budget'
✓ { d | Department(d) ∧ d.budget > 1000000 } -- Department has 'budget'

Rule 3: Type Compatibility

Comparisons must involve type-compatible operands:

✗ { e | Employee(e) ∧ e.name > 50000 }      -- string vs number
✓ { e | Employee(e) ∧ e.salary > 50000 }    -- number vs number

Rule 4: Free Variable Requirement

The target list must include exactly the free variables of the formula (in some formulations):

✗ { e, d | Employee(e) ∧ e.salary > 50000 } -- d is not declared
✓ { e | Employee(e) ∧ e.salary > 50000 }    -- e is properly declared

Common Well-Formedness Errors

•Unbound Variable: Using a variable without declaring its range
•Scope Escape: Referencing a bound variable outside its quantifier scope
•Schema Mismatch: Accessing an attribute that doesn't exist in the range relation
•Type Error: Comparing incompatible types (string = integer)
•Shadowing Confusion: Reusing a variable name in nested scopes
•Missing Target: Empty target list or target variables not in formula

well-formedness-examples.trc
1
2
3
4
5
6
7
8
9
10
11
12
13
-- INCORRECT: Multiple well-formedness violations
{ x | y.salary > 50000 }                    -- x unused, y undeclared
 
-- INCORRECT: Scope escape
{ e | Employee(e) ∧ ∃d(Department(d) ∧ d.dept_id = 5) ∧ d.name = 'HR' }
--    d is bound inside ∃, but referenced outside                    ↑ ERROR
 
-- INCORRECT: Schema mismatch  
{ e | Employee(e) ∧ e.budget > 1000000 }    -- Employee has no 'budget' attribute
 
-- CORRECT: Properly formed query
{ e | Employee(e) ∧ 
      ∃d(Department(d) ∧ e.dept_id = d.dept_id ∧ d.budget > 1000000) }

Static Checking

Comparison Operators and Atomic Formulas

Atomic formulas are the primitive building blocks that compare values and assert range membership. All complex formulas are built from atoms.

Types of Atoms:

Range Predicate: R(t) — asserts that tuple variable t is in relation R
Attribute Comparison: t₁.A op t₂.B — compares attributes of two tuple variables
Constant Comparison: t.A op constant — compares an attribute to a literal value

Comparison Operators:

TRC Comparison Operators
Operator	Symbol(s)	Meaning	SQL Equivalent
Equality	`=`	Values are equal	`=`
Inequality	`≠`, `<>`, `!=`	Values are not equal	`<>` or `!=`
Less Than	`<`	Left is strictly less than right	`<`
Greater Than	`>`	Left is strictly greater than right	`>`
Less or Equal	`≤`, `<=`	Left is at most right	`<=`
Greater or Equal	`≥`, `>=`	Left is at least right	`>=`

Operand Types:

Comparison operands can be:

Tuple Variable Attributes: e.salary, d.budget
Constants: 50000, 'Alice', DATE '2024-01-15'
Computed Values (in extended TRC): e.salary * 1.1

NULL Handling:

NULL values require special consideration:

NULL = NULL is unknown (not TRUE) in three-valued logic
NULL > 50000 is unknown
Any comparison involving NULL typically evaluates to unknown

TRC (and SQL) adopt three-valued logic: TRUE, FALSE, UNKNOWN. Rows are included in results only when conditions evaluate to TRUE (not UNKNOWN).

Pattern Matching (Extended):

Pure TRC supports exact comparisons. Extended versions may include:

LIKE patterns: e.name LIKE 'A%'
Regular expressions: e.email MATCHES '.*@gmail\.com'
Substring tests: CONTAINS(e.description, 'urgent')

These are handled by extending the atom grammar.

atomic-formulas.trc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-- RANGE ATOMS
Employee(e)                              -- e is in Employee
Department(d)                            -- d is in Department
 
-- ATTRIBUTE-TO-ATTRIBUTE COMPARISONS
e.dept_id = d.dept_id                    -- Foreign key match
e₁.salary > e₂.salary                    -- Self-join comparison
p.start_date < p.end_date                -- Within-tuple comparison
 
-- ATTRIBUTE-TO-CONSTANT COMPARISONS
e.salary > 50000                         -- Threshold filter
e.name = 'Alice'                         -- Exact match
e.hire_date >= DATE '2020-01-01'         -- Date comparison
d.budget ≤ 1000000                       -- Upper bound
 
-- COMBINED IN FORMULAS
{ e | Employee(e) ∧ 
      e.salary > 50000 ∧ 
      e.dept_id = 5 ∧
      ∃m(Employee(m) ∧ e.manager_id = m.emp_id ∧ m.title = 'Director') }

Building Complex Formulas

With atoms and connectives established, we can construct formulas of arbitrary complexity. This section demonstrates the compositional building of expressive queries.

Level 1: Simple Selection

Single relation, single condition:

{ e | Employee(e) ∧ e.salary > 50000 }

Level 2: Multiple Conditions

Conjunctions and disjunctions:

{ e | Employee(e) ∧ e.salary > 50000 ∧ (e.dept_id = 5 ∨ e.dept_id = 7) }

Level 3: Multi-Relation Joins

Free variables from multiple relations:

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

Level 4: Existential Subqueries

Conditions depending on the existence of related data:

{ e | Employee(e) ∧ ∃p(Project(p) ∧ p.lead_id = e.emp_id) }

Level 5: Universal Conditions

Conditions that must hold for all related tuples:

{ d | Department(d) ∧ ∀e(Employee(e) ∧ e.dept_id = d.dept_id → e.salary > 50000) }

Level 6: Nested Quantification

Multiple layers of quantifiers:

{ d | Department(d) ∧ 
      ∃e(Employee(e) ∧ e.dept_id = d.dept_id ∧
         ∀p(Project(p) ∧ p.dept_id = d.dept_id → 
            ∃a(Assignment(a) ∧ a.emp_id = e.emp_id ∧ a.proj_id = p.proj_id))) }

This finds departments where at least one employee works on ALL department projects.

Complex Query ConstructionFind employees who earn more than everyone in the Sales department

Input

Step-by-step construction:

1. Base: Employee(e)
2. Add quantifier: ∀s(...)
3. Quantifier body: Employee(s) ∧ s.dept_id = (Sales dept_id) → e.salary > s.salary
4. Complete: { e | Employee(e) ∧ ∀s(Employee(s) ∧ s.dept_id = 1 → e.salary > s.salary) }

Output

Employees earning more than all Sales department members

Explanation

Build Incrementally

SQL Translation of Formula Syntax

Understanding how TRC formula syntax maps to SQL reinforces comprehension and provides practical applicability.

Formula to SQL Mappings:

TRC to SQL Translation
TRC Construct	SQL Equivalent
`R(t)`	`FROM R AS t`
`t.A = value`	`t.A = value` in WHERE
`P ∧ Q`	`P AND Q`
`P ∨ Q`	`P OR Q`
`¬P`	`NOT P`
`∃t(R(t) ∧ P(t))`	`EXISTS (SELECT 1 FROM R t WHERE P)`
`∀t(R(t) → P(t))`	`NOT EXISTS (SELECT 1 FROM R t WHERE NOT P)`

trc-to-sql-translation.sql

-- TRC: Find employees in high-budget departments with at least one project
-- { e | Employee(e) ∧ 
--       ∃d(Department(d) ∧ e.dept_id = d.dept_id ∧ d.budget > 1000000) ∧
--       ∃p(Project(p) ∧ p.lead_id = e.emp_id) }
 
-- SQL Translation:
SELECT e.*
FROM Employee AS e
WHERE EXISTS (
    SELECT 1 
    FROM Department AS d 
    WHERE e.dept_id = d.dept_id 
      AND d.budget > 1000000
)
AND EXISTS (
    SELECT 1 
    FROM Project AS p 
    WHERE p.lead_id = e.emp_id
);
 
-- TRC: Find departments where ALL employees earn > 50000
-- { d | Department(d) ∧ 
--       ∀e(Employee(e) ∧ e.dept_id = d.dept_id → e.salary > 50000) }
 
-- SQL Translation (using double negation):
SELECT d.*
FROM Department AS d
WHERE NOT EXISTS (
    SELECT 1 
    FROM Employee AS e 
    WHERE e.dept_id = d.dept_id 
      AND e.salary <= 50000  -- Negation of the consequent
);

The Power of EXISTS

Summary: Mastering Formula Syntax

Key Takeaways

•Grammar Foundation: TRC formulas follow a recursive BNF grammar with atoms, connectives, and quantifiers as building blocks
•Logical Connectives: ¬ (NOT), ∧ (AND), ∨ (OR), → (IMPLIES) combine formulas with precise truth-table semantics
•Quantifiers: ∃ (exists) and ∀ (for all) enable conditions over sets of tuples, with ∀ requiring implication for safety
•Operator Precedence: Standard precedence (¬ > ∧ > ∨ > →) governs parsing; parentheses provide clarity
•Well-Formedness: Queries must satisfy rules: variable declaration, attribute existence, type compatibility, scope correctness
•Atomic Formulas: Range predicates R(t) and comparisons (=, ≠, <, >, ≤, ≥) are the primitive conditions
•Compositional Building: Complex queries are built incrementally from simple formulas using logical combination

What's Next:

Page Complete

3 / 5