Domain Relational Calculus

Every formal query language is defined by a syntax—a precise set of rules governing how valid expressions are constructed. In Domain Relational Calculus, the syntax determines how domain variables, membership predicates, logical connectives, and quantifiers combine to form well-formed queries.

Mastering DRC syntax is essential for several reasons:

1. Correctness — Only syntactically valid queries can be interpreted and evaluated
2. Expressiveness — Understanding syntax reveals what queries are possible to express
3. Translation — SQL and other languages can be systematically mapped to/from DRC
4. Foundation — DRC syntax forms the basis for understanding Query-by-Example (QBE)

This page provides a complete, formal treatment of DRC syntax—from atomic building blocks to complex nested expressions.

Every DRC query follows a specific template that consists of two main parts: a target list and a formula. The general form is:

{ <x₁, x₂, ..., xₙ> | P(x₁, x₂, ..., xₙ, y₁, y₂, ..., yₘ) }

Where:

• <x₁, x₂, ..., xₙ> is the target list (also called the result template)
• P(...) is a formula (also called the predicate or condition)
• The vertical bar | read as "such that" separates the target list from the formula
• x₁, ..., xₙ are free variables that appear in the target list
• y₁, ..., yₘ are variables that may be bound by quantifiers

Semantic Interpretation:

The query returns all tuples (x₁, x₂, ..., xₙ) such that the formula P evaluates to TRUE for some assignment of values to the variables.

Components Breakdown:

1. Braces { } — Enclose the entire query, denoting set formation

2. Angle Brackets < > — Denote the tuple structure of results

3. Vertical Bar | — The "such that" separator (some notations use :)

4. Domain Variables — Named placeholders ranging over domain values

5. Formula — A well-formed logical expression evaluating to TRUE or FALSE

Atomic formulas are the simplest well-formed formulas in DRC—the building blocks from which all complex expressions are constructed. There are two types of atomic formulas:

1. Membership Atomic Formulas (Relation Predicates)

A membership formula asserts that a tuple of domain variables (or constants) belongs to a relation:

R(a₁, a₂, ..., aₙ)

Where:

• R is a relation name with n attributes
• Each aᵢ is either a domain variable or a constant
• The formula is TRUE if tuple (a₁, a₂, ..., aₙ) exists in R

Important: The number of arguments must exactly match the arity (number of attributes) of relation R.

Examples:

Employee(e, n, s, d)        -- 4 variables for 4-attribute relation
Department(d, 'Engineering', m)  -- Mix of variables and constants
Project('P001', pn, pd)     -- Constant in first position

2. Comparison Atomic Formulas

A comparison formula relates two terms using a comparison operator:

a θ b

Where:

• a and b are terms (domain variables or constants)
• θ is a comparison operator: =, ≠, <, >, ≤, ≥

Syntactic Rules for Comparisons:

• Both operands must have compatible domains
• Numeric comparisons (<, >, ≤, ≥) require ordered domains
• Equality (=, ≠) works on any domain

Examples:

s > 50000              -- Variable compared to constant
x = y                  -- Two variables (join condition)
n ≠ 'Unknown'          -- Inequality with constant
start_date < end_date  -- Comparison between variables

Complex formulas are built from atomic formulas using logical connectives. DRC supports the standard connectives from first-order logic:

1. Negation (¬ or NOT)

¬P          -- TRUE when P is FALSE, and vice versa

2. Conjunction (∧ or AND)

P ∧ Q       -- TRUE only when both P and Q are TRUE

3. Disjunction (∨ or OR)

P ∨ Q       -- TRUE when at least one of P or Q is TRUE

4. Implication (→ or IMPLIES)

P → Q       -- TRUE when P is FALSE or Q is TRUE
            -- Equivalent to: ¬P ∨ Q

Operator Precedence:

When formulas contain multiple connectives, precedence determines evaluation order (from highest to lowest):

1. ( ) — Parentheses (highest precedence)
2. ¬ — Negation
3. ∧ — Conjunction
4. ∨ — Disjunction
5. → — Implication (lowest precedence)

Example Parsing:

¬P ∧ Q ∨ R → S

Parses as: ((¬P) ∧ Q) ∨ R) → S

Step by step:
  ¬P ∧ Q ∨ R → S
= (¬P) ∧ Q ∨ R → S     (apply ¬)
= ((¬P) ∧ Q) ∨ R → S   (apply ∧)
= (((¬P) ∧ Q) ∨ R) → S (apply ∨)

Best Practice: Use parentheses liberally to make intent clear, even when not strictly necessary.

Quantifiers allow us to make statements about the existence or universality of values satisfying certain conditions. DRC inherits the two quantifiers from first-order logic:

1. Existential Quantifier (∃)

The existential quantifier asserts that at least one value exists satisfying a condition:

∃x (P(x))

Read as: "There exists an x such that P(x) is true"

The formula is TRUE if we can find at least one value for x that makes P(x) true.

2. Universal Quantifier (∀)

The universal quantifier asserts that all values satisfy a condition:

∀x (P(x))

Read as: "For all x, P(x) is true"

The formula is TRUE only if P(x) is true for every possible value of x in the domain.

Quantifier Scope:

The scope of a quantifier is the formula immediately following it (inside parentheses). A variable is bound within its quantifier's scope and free outside.

∃x (Employee(e, x, s, d) ∧ x = 'Alice')
    └─────────────────────────────────┘
                  scope of ∃x

Nested Quantifiers:

Quantifiers can be nested to express complex conditions:

∃d ∀e (Department(d, dn, m) → 
       ( Employee(e, n, s, d) → s > 50000 ))

This says: "There exists a department d such that for all employees e, if e is in d, then e's salary exceeds 50000."

Order Matters:

∃x ∀y P(x,y)  ≠  ∀y ∃x P(x,y)   (usually different!)

∃x ∀y (x > y): "There is a number greater than all numbers" → FALSE
∀y ∃x (x > y): "For any number, there's a larger one" → TRUE

A Well-Formed Formula (WFF) is a syntactically valid expression in DRC. Not every string of symbols is a WFF—we need a precise recursive definition:

Definition of WFF in DRC:

Base Cases:

1. If R is a relation with n attributes and a₁, ..., aₙ are domain variables or constants, then R(a₁, ..., aₙ) is a WFF (membership atomic formula)
2. If a and b are domain variables or constants and θ is a comparison operator, then a θ b is a WFF (comparison atomic formula)

Recursive Cases: 3. If P is a WFF, then (¬P) is a WFF 4. If P and Q are WFFs, then (P ∧ Q) is a WFF 5. If P and Q are WFFs, then (P ∨ Q) is a WFF 6. If P and Q are WFFs, then (P → Q) is a WFF 7. If P is a WFF and x is a domain variable free in P, then (∃x P) is a WFF 8. If P is a WFF and x is a domain variable free in P, then (∀x P) is a WFF

Closure: Nothing else is a WFF.

Free and Bound Variables:

A variable x in formula P is:

• Free if it appears outside the scope of any quantifier binding x
• Bound if it appears within the scope of a quantifier binding x

A variable can be free in some occurrences and bound in others within the same formula.

Examples:

Employee(e, n, s, d) ∧ s > 50000
  All variables are FREE (no quantifiers)

∃e (Employee(e, n, s, d) ∧ s > 50000)
  e is BOUND, but n, s, d remain FREE

∃e ∃s ∃d (Employee(e, n, s, d) ∧ s > 50000)
  e, s, d are BOUND; only n is FREE

The Free Variable Requirement:

For a DRC query to be valid:

• Every variable in the target list must be FREE in the formula
• A bound variable has no single value to return—it's universalized or existentialized away

Now let's see how these syntactic elements combine to form complete, complex queries. We'll build up from simple selections to multi-table joins with conditions.

Pattern 1: Simple Selection

Return values from one relation with a condition:

{ <n, s> | ∃e ∃d (Employee(e, n, s, d) ∧ s > 60000) }

• Target: employee names and salaries
• Source: Employee relation
• Condition: salary exceeds 60000
• Variables e and d are existentially quantified (we don't care about their specific values)

Pattern 2: Projection Only

Return specific attributes from all tuples:

{ <n> | ∃e ∃s ∃d (Employee(e, n, s, d)) }

• Returns all employee names
• No condition beyond membership
• Duplicates are automatically eliminated (it's a set)

The "All X Satisfying Y" Pattern:

Many queries ask for items that satisfy a property for ALL items in some set. This is expressed using:

∀x (Condition(x) → Property(x))

Alternatively, using the equivalence ∀x P ≡ ¬∃x ¬P:

¬∃x (Condition(x) ∧ ¬Property(x))

This says "there's no x satisfying Condition where Property fails."

Example: Find students registered for ALL courses

{ <sn> | ∃s (Student(s, sn) ∧
             ∀c ∀cn (Course(c, cn) → 
                    ∃g (Registration(s, c, g))))
}

Or equivalently:

{ <sn> | ∃s (Student(s, sn) ∧
             ¬∃c ∃cn (Course(c, cn) ∧ 
                     ¬∃g (Registration(s, c, g)))))
}

Different textbooks and systems use slightly different syntactic conventions for DRC. Understanding these variations helps when reading different sources:

1. Set Builder Notation Variations:

2. Quantifier Notations:

∃x (P)     -- Standard mathematical notation
(∃x)(P)    -- Additional parentheses
∃x.P       -- Dot notation (from lambda calculus)
∃x: P      -- Colon notation

3. Connective Symbols:

AND:  ∧, ·, &, AND
OR:   ∨, +, |, OR  
NOT:  ¬, ~, !, NOT
→:    ⇒, ⊃, IMPLIES

4. Domain Declaration Styles:

Some notations explicitly declare variable domains:

{ <x, y> | x ∈ dom(Name), y ∈ dom(Salary), 
           ∃e ∃d (Employee(e, x, y, d) ∧ ...) }

Others infer domains from membership predicates (more common in practice).

We've explored the complete syntax of Domain Relational Calculus. Let's consolidate the key elements:

What's Next:

Now that we've mastered DRC syntax, we'll compare DRC with TRC in depth. While both are relationally complete, they differ in how queries are expressed. Understanding these differences illuminates the design space of declarative query languages and prepares us for understanding real-world systems like SQL and QBE.