Calculus Vs Algebra - Learning Module

Loading content...

0/252

Calculus Types: Tuple vs Domain Relational Calculus

Two Flavors of Declarative Power

Relational calculus comes in two distinct flavors, each offering a different perspective on declarative query expression. While both are expressively equivalent to each other (and to relational algebra), they differ in how they conceptualize the fundamental unit of querying.

Tuple Relational Calculus (TRC) treats entire tuples as the primary objects of discourse. Variables range over complete rows in relations, and queries describe which tuples belong in the result.

Domain Relational Calculus (DRC) operates at a finer granularity—individual attribute values. Variables range over domain values, and queries describe which combinations of values form result tuples.

This distinction, while subtle, has significant implications for query formulation, natural expression, and practical influence on query interfaces.

What You Will Learn

By the end of this page, you will deeply understand both TRC and DRC, recognize their syntactic and conceptual differences, know when each formalism is more natural, and appreciate how they influenced different query language designs—most notably, how DRC inspired Query By Example (QBE).

Tuple Relational Calculus (TRC): Reasoning About Rows

Tuple Relational Calculus (TRC), introduced by E.F. Codd, expresses queries in terms of tuple variables—variables that range over the tuples (rows) of relations.

Fundamental Concept:

In TRC, you declare a variable (e.g., t) and assert that it is a tuple in some relation (e.g., EMPLOYEE(t)). You then access individual attributes using dot notation (e.g., t.name, t.salary). The query describes which tuples satisfy your conditions.

General Form of a TRC Query:

{ t.A₁, t.A₂, ..., t.Aₙ | RELATION(t) ∧ condition(t) }

Or more generally:

{ target-list | formula }

Where:

target-list: The attributes to include in the result (using tuple variables)
formula: A logical formula specifying conditions on tuple variables

TRC Syntax Elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-- TRC Expression Structure:
{ <target-list> | <formula> }
 
-- Target List: Attributes from tuple variables
-- Examples:
--   t.name                    (single attribute)
--   t.name, t.department      (multiple attributes)
--   t                         (entire tuple)
 
-- Formula: Built from atomic formulas and logical connectives
-- Atomic formulas:
--   R(t)                      t is a tuple in relation R
--   t.A θ s.B                 attribute comparison (θ ∈ {=,≠,<,>,≤,≥})
--   t.A θ c                   attribute compared to constant
 
-- Logical connectives:
--   φ ∧ ψ                     conjunction (AND)
--   φ ∨ ψ                     disjunction (OR)
--   ¬φ                        negation (NOT)
--   ∃t(φ)                     existential quantifier (there exists)
--   ∀t(φ)                     universal quantifier (for all)

TRC Examples:

Example 1: Simple Selection

Find all employees in the Engineering department.

TRC Simple Selection
1
2
3
4
5
6
7
8
{ t | EMPLOYEE(t) ∧ t.department = 'Engineering' }
 
-- Interpretation:
-- "The set of all tuples t such that:
--  - t is a tuple in the EMPLOYEE relation, AND
--  - the department attribute of t equals 'Engineering'"
 
-- Returns entire tuples from EMPLOYEE where department = 'Engineering'

Example 2: Projection with Selection

Find names and salaries of employees earning more than $100,000.

TRC Projection with Selection
1
2
3
4
5
6
7
{ t.name, t.salary | EMPLOYEE(t) ∧ t.salary > 100000 }
 
-- Interpretation:
-- "The set of (name, salary) pairs from EMPLOYEE
--  where salary exceeds 100,000"
 
-- Note: Target list specifies output attributes explicitly

Example 3: Join Query with Existential Quantifier

Find names of employees who work in departments located in 'New York'.

TRC Join with Existential Quantifier
1
2
3
4
5
6
7
8
9
10
11
{ e.name | EMPLOYEE(e) ∧ 
    ∃d(DEPARTMENT(d) ∧ 
       e.deptId = d.deptId ∧ 
       d.location = 'New York') }
 
-- Interpretation:
-- "Names of employees e for whom there EXISTS a department d
--  where e's deptId matches d's deptId AND d is in New York"
 
-- The existential quantifier ∃d captures the join condition
-- without explicitly mentioning a 'join' operation

TRC Mental Model

Think of TRC as describing 'which rows do I want?' Each tuple variable represents a candidate row, and the formula filters which candidates make it into the result. Joins become existential statements about related rows in other tables.

Domain Relational Calculus (DRC): Reasoning About Values

Domain Relational Calculus (DRC) takes a fundamentally different approach. Instead of variables that range over tuples, DRC uses domain variables—variables that range over individual attribute values from domains.

Fundamental Concept:

In DRC, you declare variables for each attribute position in the result. The formula specifies conditions that these individual values must satisfy, including their membership in relations.

General Form of a DRC Query:

{ <x₁, x₂, ..., xₙ> | formula(x₁, x₂, ..., xₙ) }

Where:

x₁, x₂, ..., xₙ: Domain variables for result attribute positions
formula: A logical formula involving domain variables

Key Difference:

Instead of EMPLOYEE(t) and t.name, in DRC you would have domain variables like n, d, s (for name, department, salary) and write EMPLOYEE(n, d, s) to assert that (n, d, s) is a tuple in EMPLOYEE.

DRC Syntax Elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-- DRC Expression Structure:
{ <x₁, x₂, ..., xₙ> | <formula> }
 
-- Domain Variables: Individual values from attribute domains
-- Examples:
--   n              (a name value)
--   d              (a department value)
--   x, y, z        (any domain values)
 
-- Key Atomic Formula:
--   R(x₁, x₂, ..., xₖ)    -- Tuple (x₁, x₂, ..., xₖ) is in R
--   
-- The formula R(x, y, z) asserts that the VALUES x, y, z
-- form a tuple in relation R. The order corresponds to
-- the attribute order in R's schema.
 
-- Other atomic formulas:
--   x θ y           comparison between domain variables
--   x θ c           domain variable compared to constant
 
-- Logical connectives: same as TRC (∧, ∨, ¬, ∃, ∀)

DRC Examples:

Example 1: Simple Selection

Find all employees in the Engineering department.

(Assuming EMPLOYEE has attributes: name, department, salary)

DRC Simple Selection
1
2
3
4
5
6
7
8
9
{ <n, d, s> | EMPLOYEE(n, d, s) ∧ d = 'Engineering' }
 
-- Interpretation:
-- "All triples (n, d, s) such that:
--  - (n, d, s) is a tuple in EMPLOYEE, AND
--  - d (the department value) equals 'Engineering'"
 
-- Compare to TRC: { t | EMPLOYEE(t) ∧ t.department = 'Engineering' }
-- DRC explicitly lists all attribute values; TRC treats the tuple as a unit

Example 2: Projection with Selection

Find names and salaries of employees earning more than $100,000.

DRC Projection with Selection
1
2
3
4
5
6
7
8
9
10
11
{ <n, s> | ∃d(EMPLOYEE(n, d, s) ∧ s > 100000) }
 
-- Interpretation:
-- "Pairs (n, s) such that there exists some department d
--  where (n, d, s) is in EMPLOYEE and s > 100000"
 
-- The existential quantifier over d achieves projection:
-- we don't include d in the result, only n and s
 
-- Compare to TRC: { t.name, t.salary | EMPLOYEE(t) ∧ t.salary > 100000 }
-- DRC projections require explicit existential quantification

Example 3: Join Query

Find names of employees who work in departments located in 'New York'.

(DEPARTMENT schema: deptId, deptName, location)

DRC Join Query
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{ <n> | ∃d,s,did,dn,loc(
    EMPLOYEE(n, d, s) ∧ 
    DEPARTMENT(did, dn, loc) ∧
    d = did ∧ 
    loc = 'New York') }
 
-- Interpretation:
-- "Names n such that there exist values d, s, did, dn, loc
--  where (n, d, s) is an employee tuple,
--  (did, dn, loc) is a department tuple,
--  d matches did (join condition),
--  and location is New York"
 
-- All non-result attributes must be existentially quantified
-- This is more verbose than TRC but exposes all values explicitly

DRC Mental Model

Think of DRC as describing 'which combinations of values do I want?' You're filling in blanks for each column of the result. Relation membership assertions check that these value combinations actually exist in your tables.

Comparing TRC and DRC: Side-by-Side Analysis

Let's systematically compare the two calculus variants to understand their differences and relative advantages.

TRC vs DRC Fundamental Comparison
Aspect	Tuple Relational Calculus (TRC)	Domain Relational Calculus (DRC)
Variable Range	Tuples (entire rows)	Domain values (individual attributes)
Relation Assertion	R(t) — t is a tuple in R	R(x₁, x₂, ...) — values form a tuple in R
Attribute Access	t.attributeName (dot notation)	Positional variables corresponding to schema
Projection	List desired attributes: t.A, t.B	Include only desired variables; ∃ over others
Selection	Condition on t.attribute	Condition on domain variable
Join Expression	∃s(S(s) ∧ t.A = s.B)	∃... variables ...(S(...) ∧ condition)
Result Structure	Subset of attributes from variables	Tuple of domain variables
Verbosity	Generally more concise	More verbose (explicit quantification)
Schema Awareness	Must know attribute names	Must know attribute positions and domains

Same Query in Both:

Query: Find names of employees who earn more than their manager.

(Assume EMPLOYEE has: id, name, salary, managerId)

TRC Version
1
2
3
4
5
6
7
8
9
10
11
{ e.name | 
  EMPLOYEE(e) ∧ 
  ∃m(EMPLOYEE(m) ∧ 
     e.managerId = m.id ∧
     e.salary > m.salary) }
 
-- Read: "Names of employees e
-- for whom there exists a
-- manager m (also an employee)
-- where e reports to m and
-- e earns more than m"

DRC Version
1
2
3
4
5
6
7
8
9
10
11
{ <n> | 
  ∃eid,esal,emgr(
    EMPLOYEE(eid, n, esal, emgr) ∧
    ∃mid,mn,msal,mmgr(
      EMPLOYEE(mid, mn, msal, mmgr) ∧
      emgr = mid ∧
      esal > msal)) }
 
-- All attributes are explicit
-- More variables to manage
-- Same logical meaning

Expressive Equivalence Holds

Despite syntactic differences, TRC and DRC are expressively equivalent to each other—any query in one can be systematically translated to the other. The choice is about convenience and naturalness for specific queries, not capability.

When to Use Which Calculus

While TRC and DRC are equivalent in power, each has contexts where it's more natural or convenient.

TRC is Preferred When:

•Working with records: When you conceptualize data as rows/records, TRC's tuple-centric view is natural
•Named attributes matter: Dot notation (t.name) is clearer than positional (x₃)
•Fewer attributes projected: Listing t.A, t.B is simpler than quantifying over excluded attributes
•Schema stability: Attribute names are more robust than positions if schema evolves
•SQL-like thinking: TRC's structure maps closely to SQL, aiding translation

DRC is Preferred When:

•Value-level reasoning: When the query naturally thinks about individual values
•Visual query interfaces: DRC inspired QBE, which fills in value blanks in table templates
•Constrained domains: When reasoning about domain constraints on individual values
•Mathematical formalization: DRC is sometimes preferred in theoretical analysis
•Few attributes total: With small schemas, positional notation is manageable

Practical Reality:

In practice, TRC is more commonly used in academic presentations and maps more directly to SQL. Most database textbooks emphasize TRC, and SQL's structure clearly derives from tuple-variable thinking (FROM clause aliases like FROM Employees e are tuple variables).

However, DRC's influence appears in visual query tools and some specialized query interfaces where users interact with data at the value level rather than the row level.

The Best Approach

Master TRC thoroughly—it's the primary formalism you'll encounter and maps to SQL. Understand DRC conceptually—it builds intuition about value-level reasoning and explains interfaces like QBE. Know both for completeness; prefer TRC for most practical work.

DRC's Legacy: Query By Example (QBE)

Domain Relational Calculus directly inspired one of the most innovative query interfaces ever developed: Query By Example (QBE), created by Moshe Zloof at IBM in the 1970s.

The QBE Insight:

Zloof recognized that DRC's value-centric approach could be visualized. Instead of writing formulas, users would fill in example values in table skeletons. The system would interpret these examples as DRC queries.

How QBE Works:

QBE presents the user with blank table templates. Users fill in:

Constants: Actual values that must match
Example elements: Variables (like '_x') representing unknown values
Conditions: Constraints using example elements
P.: 'Print' marker indicating desired output columns

QBE Query Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- QBE: Find names and salaries of employees in Engineering
 
┌─────────────────────────────────────────────────────────┐
│ EMPLOYEE  │  Id   │   Name    │  Department  │ Salary  │
├───────────┼───────┼───────────┼──────────────┼─────────┤
│           │       │   P._n    │  Engineering │  P._s   │
└───────────┴───────┴───────────┴──────────────┴─────────┘
 
-- Interpretation:
-- P._n means "print the name value"
-- P._s means "print the salary value"  
-- "Engineering" is a constant condition
-- _n and _s are example elements (domain variables!)
 
-- Equivalent DRC:
-- { <n, s> | ∃id, d(EMPLOYEE(id, n, d, s) ∧ d = 'Engineering') }
 
-- QBE makes the DRC structure visual and intuitive!

QBE Join Example:

QBE Join Query
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
-- QBE: Find employees who work in NY departments
 
┌─────────────────────────────────────────────────────────┐
│ EMPLOYEE  │  Id   │   Name    │  DeptId      │ Salary  │
├───────────┼───────┼───────────┼──────────────┼─────────┤
│           │       │   P._n    │    _d        │         │
└───────────┴───────┴───────────┴──────────────┴─────────┘
 
┌─────────────────────────────────────────────────────────┐
│ DEPARTMENT │  DeptId  │  DeptName  │  Location        │
├────────────┼──────────┼────────────┼──────────────────┤
│            │   _d     │            │   New York       │
└────────────┴──────────┴────────────┴──────────────────┘
 
-- Shared variable _d links the tables (join condition!)
-- P._n prints employee names
-- "New York" is the location constraint
 
-- The visual linking is intuitive even for non-programmers

QBE's Lasting Impact

QBE demonstrated that formal calculus could be made accessible. Its influence appears in Microsoft Access's query designer, various visual database tools, and modern 'query builders' in analytics platforms. The DRC foundation enables visual, fill-in-the-blank query construction.

The DRC-QBE Correspondence:

QBE Element	DRC Construct
Example element (_x)	Domain variable
Constant value	Equality condition
P. (print)	Include in target list
Shared examples	Join via equality
Condition box	Additional predicates

QBE is essentially a visual syntax for DRC. Understanding DRC helps you understand how visual query tools work under the hood.

Formal Relationship Between TRC and DRC

We've stated that TRC and DRC are equivalent. Let's understand this equivalence more formally.

TRC to DRC Translation:

Given a TRC expression, we can systematically convert to DRC:

For each tuple variable t with schema (A₁, A₂, ..., Aₙ), introduce domain variables x₁, x₂, ..., xₙ
Replace R(t) with R(x₁, x₂, ..., xₙ)
Replace t.Aᵢ with xᵢ
Adjust the target list to use domain variables
Preserve all logical connectives

TRC to DRC Translation Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-- TRC Query:
{ t.name | EMPLOYEE(t) ∧ t.salary > 50000 }
 
-- Translation Process:
-- EMPLOYEE has schema: (id, name, dept, salary)
 
-- Step 1: Introduce domain vars: id→x₁, name→x₂, dept→x₃, salary→x₄
-- Step 2: Replace EMPLOYEE(t) → EMPLOYEE(x₁, x₂, x₃, x₄)
-- Step 3: Replace t.name → x₂, t.salary → x₄
-- Step 4: Target includes x₂
 
-- DRC Result:
{ <x₂> | ∃x₁,x₃,x₄(EMPLOYEE(x₁, x₂, x₃, x₄) ∧ x₄ > 50000) }
 
-- Note: x₁, x₃ must be existentially quantified (they're not in output)

DRC to TRC Translation:

The reverse translation works by grouping domain variables into tuple variables:

For each relation R(x₁, ..., xₙ), introduce a tuple variable t
Replace R(x₁, ..., xₙ) with R(t)
Replace xᵢ with t.Aᵢ (where Aᵢ is the i-th attribute name)
Handle free variables in target list as attributes of tuple variables
Existentially quantified groups become separate tuple variables

DRC to TRC Translation Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-- DRC Query:
{ <x> | ∃y,z(EMPLOYEE(x, y, z) ∧ z > 50000) }
 
-- Where EMPLOYEE has schema: (name, dept, salary)
 
-- Translation Process:
-- Step 1: x, y, z all come from EMPLOYEE → introduce t for EMPLOYEE
-- Step 2: Replace EMPLOYEE(x, y, z) → EMPLOYEE(t)
-- Step 3: x→t.name, y→t.dept, z→t.salary
-- Step 4: Target <x> becomes t.name
 
-- TRC Result:
{ t.name | EMPLOYEE(t) ∧ t.salary > 50000 }
 
-- The existential quantifiers over y, z disappear—
-- they're implicit in choosing which attributes to project

Mechanical but Tedious

The translations are mechanical—algorithms exist to perform them automatically. But the translations can produce verbose, non-idiomatic expressions. This is fine for proving equivalence; for human understanding, write directly in whichever calculus feels natural.

Extended Features of Relational Calculus

While we've focused on core TRC and DRC, both can be extended with additional features to match practical query language capabilities.

Common Extensions:

Calculus Extensions

•Arithmetic expressions: Allow t.salary * 1.1 in target lists or conditions
•String operations: Pattern matching, concatenation in predicates
•Aggregate extensions: Special syntax for COUNT, SUM, etc. (beyond core calculus)
•Sorting specifications: ORDER BY-style extensions for result ordering
•Null handling: Three-valued logic extensions for NULL comparisons
•Grouping: Extensions for GROUP BY semantics

Example with Arithmetic:

Extended TRC with Arithmetic
1
2
3
4
5
6
7
8
9
-- Find names and 10% salary increases for senior employees
{ t.name, t.salary * 1.1 | 
  EMPLOYEE(t) ∧ t.yearsEmployed > 10 }
 
-- The arithmetic expression t.salary * 1.1 is an extension
-- Core calculus has no arithmetic—just attribute references
 
-- This extension is necessary for practical queries
-- SQL includes this naturally in SELECT clause

Aggregate Extension Example:

Extended TRC with Aggregates
1
2
3
4
5
6
7
8
9
10
11
12
-- Find departments with average salary > $70,000
-- This CANNOT be expressed in core relational calculus!
 
-- Possible extended syntax:
{ d.deptName, AVG(e.salary) | 
  DEPARTMENT(d) ∧ 
  GROUP_BY(d.deptId) ∧
  HAVING(AVG{e.salary : EMPLOYEE(e) ∧ e.deptId = d.deptId} > 70000) }
 
-- This is NOT standard calculus—it's an extension
-- Aggregates are fundamentally outside first-order logic
-- SQL adds them as built-in features beyond pure calculus

Know the Boundaries

Extensions like aggregates go beyond what core calculus (and algebra) can express. When learning SQL, recognize which features are 'relational calculus' features (SELECT-FROM-WHERE) versus extensions (GROUP BY, HAVING, window functions). This helps you understand query language design and limits.

Summary: Choosing Your Declarative Lens

We've explored the two flavors of relational calculus in depth. While both are declarative and expressively equivalent, they offer different cognitive approaches to query formulation.

Key Takeaways

•TRC uses tuple variables that range over rows; access attributes via dot notation
•DRC uses domain variables that range over individual values; assert tuple membership
•Both are expressively equivalent to each other and to relational algebra
•TRC is closer to SQL and more commonly used in practice
•DRC inspired QBE, showing how visual query interfaces can be grounded in calculus
•Translations exist between TRC and DRC, though they can be verbose
•Extensions add capabilities (arithmetic, aggregates) beyond core calculus power

What's Next:

Having understood the calculus types, we now examine how relational calculus serves as the foundation for SQL. The next page traces the direct lineage from calculus concepts to SQL syntax, showing how every SELECT-FROM-WHERE query has its roots in relational calculus. You'll never look at SQL the same way again.

Page Complete

You now have a deep understanding of both Tuple Relational Calculus and Domain Relational Calculus. This knowledge not only prepares you for formal database theory but also illuminates the foundations of SQL and visual query tools. The declarative paradigm has many faces—you now recognize its core forms.

Calculus Types: Tuple vs Domain Relational Calculus

Two Flavors of Declarative Power

Tuple Relational Calculus (TRC) treats entire tuples as the primary objects of discourse. Variables range over complete rows in relations, and queries describe which tuples belong in the result.

This distinction, while subtle, has significant implications for query formulation, natural expression, and practical influence on query interfaces.

What You Will Learn

Tuple Relational Calculus (TRC): Reasoning About Rows

Tuple Relational Calculus (TRC), introduced by E.F. Codd, expresses queries in terms of tuple variables—variables that range over the tuples (rows) of relations.

Fundamental Concept:

General Form of a TRC Query:

{ t.A₁, t.A₂, ..., t.Aₙ | RELATION(t) ∧ condition(t) }

Or more generally:

{ target-list | formula }

Where:

target-list: The attributes to include in the result (using tuple variables)
formula: A logical formula specifying conditions on tuple variables

TRC Syntax Elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-- TRC Expression Structure:
{ <target-list> | <formula> }
 
-- Target List: Attributes from tuple variables
-- Examples:
--   t.name                    (single attribute)
--   t.name, t.department      (multiple attributes)
--   t                         (entire tuple)
 
-- Formula: Built from atomic formulas and logical connectives
-- Atomic formulas:
--   R(t)                      t is a tuple in relation R
--   t.A θ s.B                 attribute comparison (θ ∈ {=,≠,<,>,≤,≥})
--   t.A θ c                   attribute compared to constant
 
-- Logical connectives:
--   φ ∧ ψ                     conjunction (AND)
--   φ ∨ ψ                     disjunction (OR)
--   ¬φ                        negation (NOT)
--   ∃t(φ)                     existential quantifier (there exists)
--   ∀t(φ)                     universal quantifier (for all)

TRC Examples:

Example 1: Simple Selection

Find all employees in the Engineering department.

TRC Simple Selection
1
2
3
4
5
6
7
8
{ t | EMPLOYEE(t) ∧ t.department = 'Engineering' }
 
-- Interpretation:
-- "The set of all tuples t such that:
--  - t is a tuple in the EMPLOYEE relation, AND
--  - the department attribute of t equals 'Engineering'"
 
-- Returns entire tuples from EMPLOYEE where department = 'Engineering'

Example 2: Projection with Selection

Find names and salaries of employees earning more than $100,000.

TRC Projection with Selection
1
2
3
4
5
6
7
{ t.name, t.salary | EMPLOYEE(t) ∧ t.salary > 100000 }
 
-- Interpretation:
-- "The set of (name, salary) pairs from EMPLOYEE
--  where salary exceeds 100,000"
 
-- Note: Target list specifies output attributes explicitly

Example 3: Join Query with Existential Quantifier

Find names of employees who work in departments located in 'New York'.

TRC Join with Existential Quantifier
1
2
3
4
5
6
7
8
9
10
11
{ e.name | EMPLOYEE(e) ∧ 
    ∃d(DEPARTMENT(d) ∧ 
       e.deptId = d.deptId ∧ 
       d.location = 'New York') }
 
-- Interpretation:
-- "Names of employees e for whom there EXISTS a department d
--  where e's deptId matches d's deptId AND d is in New York"
 
-- The existential quantifier ∃d captures the join condition
-- without explicitly mentioning a 'join' operation

TRC Mental Model

Domain Relational Calculus (DRC): Reasoning About Values

Fundamental Concept:

In DRC, you declare variables for each attribute position in the result. The formula specifies conditions that these individual values must satisfy, including their membership in relations.

General Form of a DRC Query:

{ <x₁, x₂, ..., xₙ> | formula(x₁, x₂, ..., xₙ) }

Where:

x₁, x₂, ..., xₙ: Domain variables for result attribute positions
formula: A logical formula involving domain variables

Key Difference:

DRC Syntax Elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-- DRC Expression Structure:
{ <x₁, x₂, ..., xₙ> | <formula> }
 
-- Domain Variables: Individual values from attribute domains
-- Examples:
--   n              (a name value)
--   d              (a department value)
--   x, y, z        (any domain values)
 
-- Key Atomic Formula:
--   R(x₁, x₂, ..., xₖ)    -- Tuple (x₁, x₂, ..., xₖ) is in R
--   
-- The formula R(x, y, z) asserts that the VALUES x, y, z
-- form a tuple in relation R. The order corresponds to
-- the attribute order in R's schema.
 
-- Other atomic formulas:
--   x θ y           comparison between domain variables
--   x θ c           domain variable compared to constant
 
-- Logical connectives: same as TRC (∧, ∨, ¬, ∃, ∀)

DRC Examples:

Example 1: Simple Selection

Find all employees in the Engineering department.

(Assuming EMPLOYEE has attributes: name, department, salary)

DRC Simple Selection
1
2
3
4
5
6
7
8
9
{ <n, d, s> | EMPLOYEE(n, d, s) ∧ d = 'Engineering' }
 
-- Interpretation:
-- "All triples (n, d, s) such that:
--  - (n, d, s) is a tuple in EMPLOYEE, AND
--  - d (the department value) equals 'Engineering'"
 
-- Compare to TRC: { t | EMPLOYEE(t) ∧ t.department = 'Engineering' }
-- DRC explicitly lists all attribute values; TRC treats the tuple as a unit

Example 2: Projection with Selection

Find names and salaries of employees earning more than $100,000.

DRC Projection with Selection
1
2
3
4
5
6
7
8
9
10
11
{ <n, s> | ∃d(EMPLOYEE(n, d, s) ∧ s > 100000) }
 
-- Interpretation:
-- "Pairs (n, s) such that there exists some department d
--  where (n, d, s) is in EMPLOYEE and s > 100000"
 
-- The existential quantifier over d achieves projection:
-- we don't include d in the result, only n and s
 
-- Compare to TRC: { t.name, t.salary | EMPLOYEE(t) ∧ t.salary > 100000 }
-- DRC projections require explicit existential quantification

Example 3: Join Query

Find names of employees who work in departments located in 'New York'.

(DEPARTMENT schema: deptId, deptName, location)

DRC Join Query
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{ <n> | ∃d,s,did,dn,loc(
    EMPLOYEE(n, d, s) ∧ 
    DEPARTMENT(did, dn, loc) ∧
    d = did ∧ 
    loc = 'New York') }
 
-- Interpretation:
-- "Names n such that there exist values d, s, did, dn, loc
--  where (n, d, s) is an employee tuple,
--  (did, dn, loc) is a department tuple,
--  d matches did (join condition),
--  and location is New York"
 
-- All non-result attributes must be existentially quantified
-- This is more verbose than TRC but exposes all values explicitly

DRC Mental Model

Comparing TRC and DRC: Side-by-Side Analysis

Let's systematically compare the two calculus variants to understand their differences and relative advantages.

TRC vs DRC Fundamental Comparison
Aspect	Tuple Relational Calculus (TRC)	Domain Relational Calculus (DRC)
Variable Range	Tuples (entire rows)	Domain values (individual attributes)
Relation Assertion	R(t) — t is a tuple in R	R(x₁, x₂, ...) — values form a tuple in R
Attribute Access	t.attributeName (dot notation)	Positional variables corresponding to schema
Projection	List desired attributes: t.A, t.B	Include only desired variables; ∃ over others
Selection	Condition on t.attribute	Condition on domain variable
Join Expression	∃s(S(s) ∧ t.A = s.B)	∃... variables ...(S(...) ∧ condition)
Result Structure	Subset of attributes from variables	Tuple of domain variables
Verbosity	Generally more concise	More verbose (explicit quantification)
Schema Awareness	Must know attribute names	Must know attribute positions and domains

Same Query in Both:

Query: Find names of employees who earn more than their manager.

(Assume EMPLOYEE has: id, name, salary, managerId)

TRC Version
1
2
3
4
5
6
7
8
9
10
11
{ e.name | 
  EMPLOYEE(e) ∧ 
  ∃m(EMPLOYEE(m) ∧ 
     e.managerId = m.id ∧
     e.salary > m.salary) }
 
-- Read: "Names of employees e
-- for whom there exists a
-- manager m (also an employee)
-- where e reports to m and
-- e earns more than m"

DRC Version
1
2
3
4
5
6
7
8
9
10
11
{ <n> | 
  ∃eid,esal,emgr(
    EMPLOYEE(eid, n, esal, emgr) ∧
    ∃mid,mn,msal,mmgr(
      EMPLOYEE(mid, mn, msal, mmgr) ∧
      emgr = mid ∧
      esal > msal)) }
 
-- All attributes are explicit
-- More variables to manage
-- Same logical meaning

Expressive Equivalence Holds

When to Use Which Calculus

While TRC and DRC are equivalent in power, each has contexts where it's more natural or convenient.

TRC is Preferred When:

•Working with records: When you conceptualize data as rows/records, TRC's tuple-centric view is natural
•Named attributes matter: Dot notation (t.name) is clearer than positional (x₃)
•Fewer attributes projected: Listing t.A, t.B is simpler than quantifying over excluded attributes
•Schema stability: Attribute names are more robust than positions if schema evolves
•SQL-like thinking: TRC's structure maps closely to SQL, aiding translation

DRC is Preferred When:

•Value-level reasoning: When the query naturally thinks about individual values
•Visual query interfaces: DRC inspired QBE, which fills in value blanks in table templates
•Constrained domains: When reasoning about domain constraints on individual values
•Mathematical formalization: DRC is sometimes preferred in theoretical analysis
•Few attributes total: With small schemas, positional notation is manageable

Practical Reality:

However, DRC's influence appears in visual query tools and some specialized query interfaces where users interact with data at the value level rather than the row level.

The Best Approach

DRC's Legacy: Query By Example (QBE)

Domain Relational Calculus directly inspired one of the most innovative query interfaces ever developed: Query By Example (QBE), created by Moshe Zloof at IBM in the 1970s.

The QBE Insight:

How QBE Works:

QBE presents the user with blank table templates. Users fill in:

Constants: Actual values that must match
Example elements: Variables (like '_x') representing unknown values
Conditions: Constraints using example elements
P.: 'Print' marker indicating desired output columns

QBE Query Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- QBE: Find names and salaries of employees in Engineering
 
┌─────────────────────────────────────────────────────────┐
│ EMPLOYEE  │  Id   │   Name    │  Department  │ Salary  │
├───────────┼───────┼───────────┼──────────────┼─────────┤
│           │       │   P._n    │  Engineering │  P._s   │
└───────────┴───────┴───────────┴──────────────┴─────────┘
 
-- Interpretation:
-- P._n means "print the name value"
-- P._s means "print the salary value"  
-- "Engineering" is a constant condition
-- _n and _s are example elements (domain variables!)
 
-- Equivalent DRC:
-- { <n, s> | ∃id, d(EMPLOYEE(id, n, d, s) ∧ d = 'Engineering') }
 
-- QBE makes the DRC structure visual and intuitive!

QBE Join Example:

QBE Join Query
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
-- QBE: Find employees who work in NY departments
 
┌─────────────────────────────────────────────────────────┐
│ EMPLOYEE  │  Id   │   Name    │  DeptId      │ Salary  │
├───────────┼───────┼───────────┼──────────────┼─────────┤
│           │       │   P._n    │    _d        │         │
└───────────┴───────┴───────────┴──────────────┴─────────┘
 
┌─────────────────────────────────────────────────────────┐
│ DEPARTMENT │  DeptId  │  DeptName  │  Location        │
├────────────┼──────────┼────────────┼──────────────────┤
│            │   _d     │            │   New York       │
└────────────┴──────────┴────────────┴──────────────────┘
 
-- Shared variable _d links the tables (join condition!)
-- P._n prints employee names
-- "New York" is the location constraint
 
-- The visual linking is intuitive even for non-programmers

QBE's Lasting Impact

The DRC-QBE Correspondence:

QBE Element	DRC Construct
Example element (_x)	Domain variable
Constant value	Equality condition
P. (print)	Include in target list
Shared examples	Join via equality
Condition box	Additional predicates

QBE is essentially a visual syntax for DRC. Understanding DRC helps you understand how visual query tools work under the hood.

Formal Relationship Between TRC and DRC

We've stated that TRC and DRC are equivalent. Let's understand this equivalence more formally.

TRC to DRC Translation:

Given a TRC expression, we can systematically convert to DRC:

For each tuple variable t with schema (A₁, A₂, ..., Aₙ), introduce domain variables x₁, x₂, ..., xₙ
Replace R(t) with R(x₁, x₂, ..., xₙ)
Replace t.Aᵢ with xᵢ
Adjust the target list to use domain variables
Preserve all logical connectives

TRC to DRC Translation Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-- TRC Query:
{ t.name | EMPLOYEE(t) ∧ t.salary > 50000 }
 
-- Translation Process:
-- EMPLOYEE has schema: (id, name, dept, salary)
 
-- Step 1: Introduce domain vars: id→x₁, name→x₂, dept→x₃, salary→x₄
-- Step 2: Replace EMPLOYEE(t) → EMPLOYEE(x₁, x₂, x₃, x₄)
-- Step 3: Replace t.name → x₂, t.salary → x₄
-- Step 4: Target includes x₂
 
-- DRC Result:
{ <x₂> | ∃x₁,x₃,x₄(EMPLOYEE(x₁, x₂, x₃, x₄) ∧ x₄ > 50000) }
 
-- Note: x₁, x₃ must be existentially quantified (they're not in output)

DRC to TRC Translation:

The reverse translation works by grouping domain variables into tuple variables:

For each relation R(x₁, ..., xₙ), introduce a tuple variable t
Replace R(x₁, ..., xₙ) with R(t)
Replace xᵢ with t.Aᵢ (where Aᵢ is the i-th attribute name)
Handle free variables in target list as attributes of tuple variables
Existentially quantified groups become separate tuple variables

DRC to TRC Translation Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-- DRC Query:
{ <x> | ∃y,z(EMPLOYEE(x, y, z) ∧ z > 50000) }
 
-- Where EMPLOYEE has schema: (name, dept, salary)
 
-- Translation Process:
-- Step 1: x, y, z all come from EMPLOYEE → introduce t for EMPLOYEE
-- Step 2: Replace EMPLOYEE(x, y, z) → EMPLOYEE(t)
-- Step 3: x→t.name, y→t.dept, z→t.salary
-- Step 4: Target <x> becomes t.name
 
-- TRC Result:
{ t.name | EMPLOYEE(t) ∧ t.salary > 50000 }
 
-- The existential quantifiers over y, z disappear—
-- they're implicit in choosing which attributes to project

Mechanical but Tedious

Extended Features of Relational Calculus

While we've focused on core TRC and DRC, both can be extended with additional features to match practical query language capabilities.

Common Extensions:

Calculus Extensions

•Arithmetic expressions: Allow t.salary * 1.1 in target lists or conditions
•String operations: Pattern matching, concatenation in predicates
•Aggregate extensions: Special syntax for COUNT, SUM, etc. (beyond core calculus)
•Sorting specifications: ORDER BY-style extensions for result ordering
•Null handling: Three-valued logic extensions for NULL comparisons
•Grouping: Extensions for GROUP BY semantics

Example with Arithmetic:

Extended TRC with Arithmetic
1
2
3
4
5
6
7
8
9
-- Find names and 10% salary increases for senior employees
{ t.name, t.salary * 1.1 | 
  EMPLOYEE(t) ∧ t.yearsEmployed > 10 }
 
-- The arithmetic expression t.salary * 1.1 is an extension
-- Core calculus has no arithmetic—just attribute references
 
-- This extension is necessary for practical queries
-- SQL includes this naturally in SELECT clause

Aggregate Extension Example:

Extended TRC with Aggregates
1
2
3
4
5
6
7
8
9
10
11
12
-- Find departments with average salary > $70,000
-- This CANNOT be expressed in core relational calculus!
 
-- Possible extended syntax:
{ d.deptName, AVG(e.salary) | 
  DEPARTMENT(d) ∧ 
  GROUP_BY(d.deptId) ∧
  HAVING(AVG{e.salary : EMPLOYEE(e) ∧ e.deptId = d.deptId} > 70000) }
 
-- This is NOT standard calculus—it's an extension
-- Aggregates are fundamentally outside first-order logic
-- SQL adds them as built-in features beyond pure calculus

Know the Boundaries

Summary: Choosing Your Declarative Lens

We've explored the two flavors of relational calculus in depth. While both are declarative and expressively equivalent, they offer different cognitive approaches to query formulation.

Key Takeaways

•TRC uses tuple variables that range over rows; access attributes via dot notation
•DRC uses domain variables that range over individual values; assert tuple membership
•Both are expressively equivalent to each other and to relational algebra
•TRC is closer to SQL and more commonly used in practice
•DRC inspired QBE, showing how visual query interfaces can be grounded in calculus
•Translations exist between TRC and DRC, though they can be verbose
•Extensions add capabilities (arithmetic, aggregates) beyond core calculus power

What's Next:

Page Complete