Domain Relational Calculus - Learning Module

Loading content...

0/241

Query Examples: DRC in Practice

Learning Through Examples

Theory without practice is incomplete. Now that we understand DRC syntax and its relationship to TRC, we need to develop fluency—the ability to translate a problem statement into a correct DRC query without excessive deliberation.

This page presents a carefully curated collection of DRC query examples, organized by complexity and pattern type. Each example includes:

The problem statement in plain English
The complete DRC query
Step-by-step construction explanation
Key insights and variations

By working through these examples, you'll internalize the patterns that make DRC query writing intuitive.

Reference Schema

We'll use a university database schema for most examples:

Student(StudentID, Name, Major, GPA, AdvisorID) Professor(ProfID, Name, Department, Salary) Course(CourseID, Title, Department, Credits) Enrollment(StudentID, CourseID, Semester, Grade) Teaching(ProfID, CourseID, Semester) Department(DeptID, DeptName, ChairID, Budget)

Basic Selection Queries

Selection queries filter tuples based on conditions. These are the simplest DRC queries and form the foundation for more complex patterns.

Example 1.1: Simple Selection

Find the names of all students majoring in Computer Science.

example_1_1.txt
Query:
{ <n> | ∃s ∃m ∃g ∃a (Student(s, n, m, g, a) ∧ m = 'Computer Science') }
 
Alternative (constant directly in predicate):
{ <n> | ∃s ∃g ∃a (Student(s, n, 'Computer Science', g, a)) }
 
Breakdown:
• Target: <n> — We want student names
• Source: Student relation (s=ID, n=Name, m=Major, g=GPA, a=Advisor)
• Condition: m = 'Computer Science'
• Quantified: s, g, a (their specific values don't matter)
 
Result: {(Alice), (Bob), (Carol), ...}

Example 1.2: Selection with Comparison

Find names and GPAs of students with GPA above 3.5.

example_1_2.txt
Query:
{ <n, g> | ∃s ∃m ∃a (Student(s, n, m, g, a) ∧ g > 3.5) }
 
Breakdown:
• Target: <n, g> — We want name AND GPA (two values)
• Condition: g > 3.5 (comparison predicate)
• Both n and g are FREE (appear in target)
• s, m, a are existentially bound
 
Result: {(Alice, 3.8), (Carol, 3.9), (David, 3.7), ...}

Example 1.3: Selection with Multiple Conditions

Find names of Computer Science students with GPA between 3.0 and 3.8.

example_1_3.txt
Query:
{ <n> | ∃s ∃m ∃g ∃a (
    Student(s, n, m, g, a) ∧ 
    m = 'Computer Science' ∧ 
    g ≥ 3.0 ∧ 
    g ≤ 3.8
) }
 
Key Points:
• Multiple conditions combined with ∧ (AND)
• Range condition expressed as two separate comparisons
• All conditions must be true for a tuple to be selected

Pattern Recognition

For basic selections: (1) Identify target attributes for the target list, (2) Write the membership predicate with all attributes, (3) Add selection conditions, (4) Existentially quantify non-target variables. This pattern handles most simple queries.

Projection Queries

Projection queries retrieve specific columns without filtering rows (other than duplicate elimination inherent in the set model).

Example 2.1: Simple Projection

List all distinct student majors.

example_2_1.txt
Query:
{ <m> | ∃s ∃n ∃g ∃a (Student(s, n, m, g, a)) }
 
Breakdown:
• Target: <m> — Only the major
• No selection condition — all tuples contribute
• Result is automatically duplicate-free (it's a set)
 
Result: {(Computer Science), (Mathematics), (Physics), (History), ...}

Example 2.2: Multi-Column Projection

List all distinct (course title, department) pairs.

example_2_2.txt
Query:
{ <t, d> | ∃c ∃cr (Course(c, t, d, cr)) }
 
Breakdown:
• Target: <t, d> — Title and Department
• Course schema: (CourseID, Title, Department, Credits)
• Variables c (CourseID) and cr (Credits) are quantified away
 
Result: {(Algorithms, Computer Science), (Calculus, Mathematics), ...}

Example 2.3: Full Tuple Retrieval

Retrieve all information about all professors.

example_2_3.txt

Query:
{ <p, n, d, s> | Professor(p, n, d, s) }
 
Breakdown:
• Target: <p, n, d, s> — All four attributes
• No existential quantifiers needed — all variables are free
• No conditions — all tuples returned
• This is equivalent to "SELECT * FROM Professor" in SQL
 
Note: All variables appearing in membership predicate are also in target,
      so none need to be existentially quantified.

Set Semantics

DRC results are sets—duplicates are automatically eliminated. If the original table has students with the same major, the projection on major will list each major only once. This differs from SQL's default bag semantics (which preserves duplicates unless DISTINCT is specified).

Two-Table Join Queries

Join queries combine data from multiple relations. In DRC, joins are expressed elegantly through shared variables.

Example 3.1: Basic Equijoin

Find student names and their advisors' names.

example_3_1.txt
Query:
{ <sn, pn> | ∃s ∃m ∃g ∃a ∃d ∃sal (
    Student(s, sn, m, g, a) ∧ 
    Professor(a, pn, d, sal)
) }
 
Join Mechanism:
• Variable 'a' appears in BOTH predicates
• In Student: a = AdvisorID
• In Professor: a = ProfID (1st position)
• Same variable → values must match → natural join
 
Result: {(Alice, Dr. Smith), (Bob, Dr. Smith), (Carol, Dr. Jones), ...}

Example 3.2: Join with Selection

Find names of CS students and their course titles for Fall 2024.

example_3_2.txt
Query:
{ <sn, ct> | ∃sid ∃m ∃g ∃a ∃cid ∃sem ∃grade ∃dept ∃cr (
    Student(sid, sn, m, g, a) ∧ 
    m = 'Computer Science' ∧
    Enrollment(sid, cid, sem, grade) ∧ 
    sem = 'Fall 2024' ∧
    Course(cid, ct, dept, cr)
) }
 
Three Tables Joined:
• Student ⟶ Enrollment via shared 'sid' (StudentID)
• Enrollment ⟶ Course via shared 'cid' (CourseID)
• Selections: m = 'Computer Science', sem = 'Fall 2024'
 
Target: Student name (sn) and Course title (ct)

Example 3.3: Self-Join

Find pairs of students who have the same advisor.

example_3_3.txt
Query:
{ <n1, n2> | ∃s1 ∃m1 ∃g1 ∃a ∃s2 ∃m2 ∃g2 (
    Student(s1, n1, m1, g1, a) ∧ 
    Student(s2, n2, m2, g2, a) ∧ 
    s1 < s2
) }
 
Self-Join Analysis:
• Two references to Student table
• Different variable sets for each (s1,n1,m1,g1 vs s2,n2,m2,g2)
• Shared 'a' enforces same advisor
• s1 < s2 prevents:
  - Self-pairs (Alice, Alice)
  - Duplicate pairs ((Alice, Bob) and (Bob, Alice))
 
Result: {(Alice, Bob), (Carol, David), ...} — unordered pairs

The Variable Sharing Pattern

In DRC, joins are beautifully implicit. When the same variable appears at matching positions in multiple relation predicates, values must be equal. No explicit 'ON' or '=' clause needed—the join condition is embedded in the variable structure itself.

Negation and Difference Queries

Negation expresses the absence of certain tuples or values. These queries require careful construction to remain safe.

Example 4.1: Simple Negation

Find students who are NOT in the Computer Science major.

example_4_1.txt
Query:
{ <n> | ∃s ∃m ∃g ∃a (Student(s, n, m, g, a) ∧ m ≠ 'Computer Science') }
 
Note: This uses inequality (≠), not logical negation (¬)
      The student MUST exist in the table — only the major differs
 
Alternative using NOT:
{ <n> | ∃s ∃m ∃g ∃a (Student(s, n, m, g, a) ∧ ¬(m = 'Computer Science')) }
 
Both are equivalent and produce students in Math, Physics, History, etc.

Example 4.2: Set Difference (NOT IN)

Find students who are not enrolled in any course.

example_4_2.txt
Query:
{ <n> | ∃s ∃m ∃g ∃a (
    Student(s, n, m, g, a) ∧ 
    ¬∃c ∃sem ∃gr (Enrollment(s, c, sem, gr))
) }
 
Structure:
• Outer: Find students (positive existence)
• Inner: ¬∃... (there does NOT exist an enrollment)
• The negated existential says "no enrollment tuple exists for this student"
 
SQL equivalent:
SELECT Name FROM Student 
WHERE StudentID NOT IN (SELECT StudentID FROM Enrollment)

Example 4.3: Finding Non-Matches

Find professors who don't teach any course.

example_4_3.txt
Query:
{ <pn> | ∃p ∃d ∃sal (
    Professor(p, pn, d, sal) ∧ 
    ¬∃c ∃sem (Teaching(p, c, sem))
) }
 
Safety Analysis:
• The outer Professor predicate binds 'p' to actual professor IDs
• The negated Teaching predicate uses this bound 'p'
• This is SAFE — we're not asking for arbitrary values not in Teaching
• We're asking for PROFESSORS who don't appear in Teaching
 
Unsafe version (DON'T DO THIS):
{ <pn> | ¬∃p ∃d ∃sal (Professor(p, pn, d, sal)) }
This asks for names NOT in Professor — potentially infinite!

Safe Negation Pattern

Always ensure negation is applied to an inner predicate whose variables are bound by an outer positive predicate. The pattern Positive(x) ∧ ¬Negative(x) is safe. The pattern ¬Positive(x) alone is unsafe because x could take infinite values.

Universal Quantification Queries

Universal quantification expresses "for all" conditions—finding items that satisfy a property for every member of some set. These are among the most powerful (and tricky) DRC queries.

Example 5.1: Simple Universal

Find students who are enrolled in ALL courses offered by the CS department.

example_5_1.txt
Query:
{ <sn> | ∃sid ∃m ∃g ∃a (
    Student(sid, sn, m, g, a) ∧ 
    ∀cid ∀ct ∀cr (
        Course(cid, ct, 'Computer Science', cr) → 
        ∃sem ∃gr (Enrollment(sid, cid, sem, gr))
    )
) }
 
Reading this query:
"Find student names where:
 - The student exists in Student table, AND
 - FOR ALL courses in CS department:
   IF a course is in CS, THEN this student is enrolled in it"
 
The implication pattern:
∀x (Condition(x) → Property(x))
means "everything satisfying Condition also satisfies Property"

Example 5.2: Alternative Form Using Double Negation

The same query can be expressed using the equivalence: ∀x P(x) ≡ ¬∃x ¬P(x)

example_5_2.txt
Alternative Query (double negation):
{ <sn> | ∃sid ∃m ∃g ∃a (
    Student(sid, sn, m, g, a) ∧ 
    ¬∃cid ∃ct ∃cr (
        Course(cid, ct, 'Computer Science', cr) ∧ 
        ¬∃sem ∃gr (Enrollment(sid, cid, sem, gr))
    )
) }
 
Reading this version:
"Find student names where:
 - The student exists, AND
 - There does NOT exist a CS course where:
   - This student is NOT enrolled"
 
Translation: "There's no CS course this student is missing"
Equivalent to: "Student is enrolled in all CS courses"

Example 5.3: Division Pattern

Find students who have taken every course that student 'Alice' has taken.

example_5_3.txt
Query:
{ <sn> | ∃sid ∃m ∃g ∃a (
    Student(sid, sn, m, g, a) ∧ 
    ∀cid (
        (∃asid ∃am ∃ag ∃aa ∃asem ∃agr (
            Student(asid, 'Alice', am, ag, aa) ∧ 
            Enrollment(asid, cid, asem, agr)
        )) → 
        (∃sem ∃gr (Enrollment(sid, cid, sem, gr)))
    )
) }
 
Pattern breakdown:
• For ALL courses cid:
  • IF Alice is enrolled in cid
  • THEN this student is also enrolled in cid
 
This is the DIVISION operation in relational algebra:
"Students whose enrolled courses ⊇ Alice's enrolled courses"

The Universal Implication Pattern

Most universal queries follow the template: ∀x (Condition(x) → Property(x)). This says 'for everything satisfying Condition, Property holds.' Without the antecedent condition, you'd assert Property for ALL domain values—rarely what's intended.

Complex Multi-Table Queries

Real-world queries often combine multiple tables, conditions, and quantification patterns. Let's work through several complex examples.

Example 6.1: Three-Way Join with Conditions

Find names of students who received an 'A' in a course taught by a professor from their own major's department.

example_6_1.txt
Query:
{ <sn> | ∃sid ∃m ∃g ∃a ∃cid ∃sem ∃ct ∃cr ∃pid ∃pn ∃sal (
    Student(sid, sn, m, g, a) ∧ 
    Enrollment(sid, cid, sem, 'A') ∧     -- Grade = 'A'
    Course(cid, ct, m, cr) ∧              -- Course dept = Student major
    Teaching(pid, cid, sem) ∧             -- Prof teaches this course
    Professor(pid, pn, m, sal)            -- Prof in same dept as student major
) }
 
Join chain:
Student ──(sid)──> Enrollment ──(cid)──> Course
                        │                   │
                   (cid,sem)               (m)
                        │                   │
                        v                   v
                   Teaching ─────(m)────> Professor
 
The shared variable 'm' ensures:
• Course is in student's major department
• Professor is from that same department

Example 6.2: Combining Existential and Universal

Find professors who have taught every student majoring in Computer Science (i.e., every CS student has taken at least one course from this professor).

example_6_2.txt
Query:
{ <pn> | ∃pid ∃d ∃sal (
    Professor(pid, pn, d, sal) ∧ 
    ∀sid ∀sn ∀g ∀a (
        Student(sid, sn, 'Computer Science', g, a) → 
        ∃cid ∃sem1 ∃sem2 ∃gr (
            Teaching(pid, cid, sem1) ∧ 
            Enrollment(sid, cid, sem2, gr)
        )
    )
) }
 
Structure:
• Outer: Find professors (existential)
• Middle: For ALL CS students (universal with implication)
• Inner: There EXISTS a course linking prof and student
 
Note: sem1 and sem2 may differ — student might take course in 
different semester than professor taught it. To require same 
semester, use shared variable 'sem'.

Example 6.3: Nested Quantification

Find department names where every professor in that department has taught at least one course that every CS student has enrolled in.

example_6_3.txt
Query:
{ <dn> | ∃did ∃ch ∃b (
    Department(did, dn, ch, b) ∧ 
    ∀pid ∀pn ∀sal (
        Professor(pid, pn, did, sal) → 
        ∃cid ∃sem (
            Teaching(pid, cid, sem) ∧ 
            ∀sid ∀sn ∀g ∀a (
                Student(sid, sn, 'Computer Science', g, a) → 
                ∃sem2 ∃gr (Enrollment(sid, cid, sem2, gr))
            )
        )
    )
) }
 
Nesting depth:
1. ∃ Department (find departments)
2.   ∀ Professor in department (for every prof in dept)
3.     → ∃ Course taught by prof (there exists a course where)
4.         ∀ CS Student (every CS student)
5.           → ∃ Enrollment in that course (is enrolled)
 
This is a complex universal pattern with four levels of quantification!

Managing Complexity

Complex queries with nested quantifiers can be hard to read. Consider breaking them down conceptually: (1) What is the output? (2) What constraints exist? (3) Are they 'for all' or 'there exists' constraints? Building the query layer by layer helps manage complexity.

Set Operations in DRC

DRC can express all set operations from relational algebra using logical connectives.

Example 7.1: Union

Find names of people who are either students or professors.

example_7_1.txt
Query:
{ <n> | (∃s ∃m ∃g ∃a (Student(s, n, m, g, a))) ∨ 
        (∃p ∃d ∃sal (Professor(p, n, d, sal))) }
 
Union pattern:
• Use disjunction (∨) between two existence conditions
• Same variable 'n' in both — unifies the name from either source
• Result: All names appearing in Student OR Professor
 
Note: This is well-defined because n ranges over values in 
EITHER relation — bound by the disjunction.

Example 7.2: Intersection

Find names of people who are both students and professors.

example_7_2.txt
Query:
{ <n> | (∃s ∃m ∃g ∃a (Student(s, n, m, g, a))) ∧ 
        (∃p ∃d ∃sal (Professor(p, n, d, sal))) }
 
Intersection pattern:
• Use conjunction (∧) between two existence conditions
• Same variable 'n' in both
• Result: Names appearing in BOTH Student AND Professor
 
This finds teaching assistants or people in dual roles.

Example 7.3: Set Difference

Find names of students who are NOT also professors.

example_7_3.txt
Query:
{ <n> | (∃s ∃m ∃g ∃a (Student(s, n, m, g, a))) ∧ 
        ¬(∃p ∃d ∃sal (Professor(p, n, d, sal))) }
 
Set Difference pattern:
• Positive membership in first relation
• Negated membership in second relation
• Result: Student names NOT appearing as Professor names
 
Alternative syntax:
{ <n> | ∃s ∃m ∃g ∃a (
    Student(s, n, m, g, a) ∧ 
    ¬∃p ∃d ∃sal (Professor(p, n, d, sal))
) }

Set Operations Pattern Summary
Operation	Relational Algebra	DRC Pattern
Union	R ∪ S	R(x) ∨ S(x)
Intersection	R ∩ S	R(x) ∧ S(x)
Difference	R − S	R(x) ∧ ¬S(x)

Logical Connectives → Set Operations

The correspondence is elegant: ∨ (OR) → Union, ∧ (AND) → Intersection, ∧ ¬ (AND NOT) → Difference. This shows how first-order logic naturally captures set-theoretic operations on relations.

Summary: Query Writing Guidelines

We've worked through a comprehensive set of DRC query examples. Let's consolidate the key patterns and strategies:

DRC Query Writing Strategy

•Identify the target — What columns/values should appear in the result? These become the target list variables.
•Identify source relations — Which tables contain the needed data? Write membership predicates for each.
•Establish joins — Use the same variable in positions that should match across relations.
•Add selection conditions — Write comparison predicates for filtering (=, ≠, <, >, etc.).
•Determine quantification — Variables not in target list: ∃ for 'exists', ∀ for 'for all' constraints.
•Handle negation carefully — Ensure negated predicates have variables bound by positive outer predicates.

Key Patterns to Remember

•Join — Shared variables between predicates: R(a,b) ∧ S(b,c)
•Selection — Comparison predicates: x > 100, y = 'value'
•Negation — Safe pattern: Positive(x) ∧ ¬Negative(x)
•Universal — Implication pattern: ∀x (Condition(x) → Property(x))
•Union — Disjunction: R(x) ∨ S(x)
•Intersection — Conjunction: R(x) ∧ S(x)
•Division — Nested universal: ∀y (S(y) → R(x,y))

What's Next:

We'll conclude our exploration of Domain Relational Calculus by examining its connection to Query-by-Example (QBE)—the pioneering visual query language that directly implemented DRC's value-oriented philosophy. Understanding this connection reveals how theoretical formalisms become practical user interfaces.

Page Complete

You've now worked through a comprehensive array of DRC query examples—from basic selections to complex nested quantification. With practice, these patterns become second nature. Next, we'll see how DRC's concepts directly inspired the Query-by-Example visual interface.