Database Management SystemsQuantifiers

Quantifiers in Relational Calculus

LevelIntermediate

Duration75 mins

TopicQuantifiers

4 / 5

Negation

The Power of Denial: Expressing What Is Not

Database queries often need to express absence, exception, or exclusion. These concepts require negation—the logical operation that inverts truth values and, when combined with quantifiers, enables some of the most powerful query patterns.

Consider these common query requirements:

"Find customers who have NOT placed any orders."

"List products that are NOT in stock at ANY warehouse."

"Identify employees who have NOT completed ALL required training."

Each involves negation interacting with quantifiers in specific ways. The customer query negates existence (¬∃). The product query uses universal negation (∀ ... NOT). The training query negates a universal (¬∀ or equivalently ∃¬).

Mastering negation in relational calculus opens the door to anti-joins, exception queries, relational division, and complex filtering logic that would otherwise be difficult or impossible to express.

What You Will Learn

By the end of this page, you will understand the semantics of logical negation, master De Morgan's laws for quantifiers, recognize patterns for negated existence and negated universals, implement anti-join patterns in TRC and SQL, apply the double-negation transformation for universal quantification, and handle the subtleties of negation with NULL values.

Fundamentals of Logical Negation

Logical negation (¬) is the simplest logical connective—it inverts truth values. But its interaction with complex formulas, especially quantified formulas, creates rich and powerful patterns.

Basic Negation

P	¬P
TRUE	FALSE
FALSE	TRUE

Negation is a unary operator—it takes one operand and produces its logical opposite.

Negation with Conjunctions and Disjunctions (De Morgan's Laws)

When negation is applied to conjunctions or disjunctions, De Morgan's laws govern the transformation:

¬(P ∧ Q) ≡ (¬P ∨ ¬Q) — "Not both" means "at least one is false"

¬(P ∨ Q) ≡ (¬P ∧ ¬Q) — "Neither" means "both are false"

These laws allow us to push negation inward through logical operators, transforming complex negated expressions into equivalent forms.

Negation with Implications

The implication operator has a specific negation pattern:

¬(P → Q) ≡ P ∧ ¬Q — "Not (if P then Q)" means "P is true but Q is false"

This is critical for understanding how negated universals decompose, since universals often use implication form.

The Implication Negation Pattern

Remember: P → Q means "if P, then Q." The ONLY way this can be false is if P is true AND Q is false. So ¬(P → Q) ≡ P ∧ ¬Q. This pattern recurs constantly when negating universal statements of the form ∀x (Condition(x) → Property(x)).

Double Negation

¬¬P ≡ P — Double negation elimination

Negating twice returns to the original truth value. This principle is fundamental to the double-negation pattern for implementing universal quantification.

Negation Scope

Negation applies to the immediately following formula (or parenthesized sub-formula):

¬P ∧ Q means "(not P) and Q"

¬(P ∧ Q) means "not (P and Q)"

Parentheses are essential for controlling negation scope.

Negation in TRC Syntax

In TRC, negation is written as:

¬ (standard logic notation)
NOT (SQL-like notation)
~ (some systems)

Example: ¬∃e (Employee(e) ∧ e.salary > 100000)

Reads: "There does not exist an employee with salary greater than 100000."

Fundamental Negation Equivalences
Original	Negated Form	Equivalent Transformation
P	¬P	Direct negation
P ∧ Q	¬(P ∧ Q)	¬P ∨ ¬Q (De Morgan)
P ∨ Q	¬(P ∨ Q)	¬P ∧ ¬Q (De Morgan)
P → Q	¬(P → Q)	P ∧ ¬Q
¬P	¬¬P	P (double negation)
∀x P(x)	¬∀x P(x)	∃x ¬P(x) (quantifier negation)
∃x P(x)	¬∃x P(x)	∀x ¬P(x) (quantifier negation)

De Morgan's Laws for Quantifiers

The classical De Morgan's laws extend to quantifiers, providing the fundamental connection between ∀ and ∃ through negation.

Quantifier De Morgan's Laws

Law 1: Negated Universal

¬∀x P(x) ≡ ∃x ¬P(x)

In words: "Not all x satisfy P" is equivalent to "Some x fails P."

Intuition: If it's false that everyone passes, then someone must fail.

Law 2: Negated Existential

¬∃x P(x) ≡ ∀x ¬P(x)

In words: "There is no x satisfying P" is equivalent to "All x fail P."

Intuition: If nobody passes, then everyone must fail.

Derivation from Quantifier Duality

These laws follow directly from quantifier duality:

∀x P(x) ≡ ¬∃x ¬P(x)

Negating both sides:

¬∀x P(x) ≡ ¬¬∃x ¬P(x) ≡ ∃x ¬P(x)

Similarly for the existential case.

de_morgan_quantifiers_examples.trc

TRC Examples

# Example 1: Negated Universal
# "Not all employees have salary > 50000"
# ¬∀e (Employee(e) → e.salary > 50000)
# Equivalent to:
∃e (Employee(e) ∧ ¬(e.salary > 50000))
# Which simplifies to:
∃e (Employee(e) ∧ e.salary ≤ 50000)
# "Some employee has salary ≤ 50000"
 
# Example 2: Negated Existential
# "No customer has placed more than 100 orders"
# ¬∃c (Customer(c) ∧ c.orderCount > 100)
# Equivalent to:
∀c (Customer(c) → ¬(c.orderCount > 100))
# Which simplifies to:
∀c (Customer(c) → c.orderCount ≤ 100)
# "All customers have at most 100 orders"
 
# Example 3: Nested Negation with Universal
# "Not all departments have at least one manager"
# ¬∀d (Department(d) → ∃m (Manager(m) ∧ m.deptId = d.id))
# Apply De Morgan for ∀:
∃d (Department(d) ∧ ¬∃m (Manager(m) ∧ m.deptId = d.id))
# Apply De Morgan for inner ∃:
∃d (Department(d) ∧ ∀m (Manager(m) → m.deptId ≠ d.id))
# "Some department has no managers" OR equivalently:
∃d (Department(d) ∧ ∀m ¬(Manager(m) ∧ m.deptId = d.id))
 
# Example 4: Complex Negation
# "Not every course is taken by some student"
# ¬∀c (Course(c) → ∃e (Enrollment(e) ∧ e.cid = c.cid))
# Apply De Morgan:
∃c (Course(c) ∧ ∀e (Enrollment(e) → e.cid ≠ c.cid))
# "Some course is taken by no student" (unregistered courses exist)

Pushing Negation Through Quantifiers

The mnemonic: When negation passes through a quantifier, the quantifier FLIPS (∀↔∃) and the negation continues inward. This is sometimes called 'pushing negation inside.' The process continues until negation reaches atomic predicates, where it becomes simple comparison inversions (> becomes ≤, = becomes ≠, etc.).

Negation Normal Form (NNF)

A formula is in Negation Normal Form when negation appears only immediately before atomic predicates, not before complex sub-formulas. Any formula can be converted to NNF using:

De Morgan's laws for ∧ and ∨
Quantifier De Morgan's laws for ∀ and ∃
Implication elimination: P → Q ≡ ¬P ∨ Q
Double negation elimination: ¬¬P ≡ P

Example:

Original: ¬∀x (P(x) → ∃y Q(x, y))

Step 1 (¬∀ → ∃¬): ∃x ¬(P(x) → ∃y Q(x, y))

Step 2 (¬(P → Q) ≡ P ∧ ¬Q): ∃x (P(x) ∧ ¬∃y Q(x, y))

Step 3 (¬∃ → ∀¬): ∃x (P(x) ∧ ∀y ¬Q(x, y))

NNF Result: ∃x (P(x) ∧ ∀y ¬Q(x, y))

Negation Normal Form is useful for query optimization and theorem proving, as it standardizes where negations appear.

Negated Existence: The Anti-Join Pattern

One of the most common and practical uses of negation is the negated existence pattern, which implements anti-joins—finding elements that do NOT have corresponding matches.

The Pattern

{a | A(a) ∧ ¬∃b (B(b) ∧ link(a, b))}

This reads: "Find all elements of A for which there does NOT exist a related element in B."

Common Applications

1. Customers without orders {c | Customer(c) ∧ ¬∃o (Order(o) ∧ o.custId = c.id)}

2. Products never reviewed {p | Product(p) ∧ ¬∃r (Review(r) ∧ r.productId = p.id)}

3. Employees who have never managed a project {e | Employee(e) ∧ ¬∃p (Project(p) ∧ p.managerId = e.id)}

4. Courses with no prerequisites {c | Course(c) ∧ ¬∃p (Prerequisite(p) ∧ p.courseId = c.id)}

5. Departments with no current vacancies {d | Department(d) ∧ ¬∃v (Vacancy(v) ∧ v.deptId = d.id ∧ v.status = 'Open')}

anti_join_sql_patterns.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
-- TRC: {c | Customer(c) ∧ ¬∃o (Order(o) ∧ o.custId = c.id)}
 
-- SQL Pattern 1: NOT EXISTS (most direct translation)
SELECT c.id, c.name
FROM Customer c
WHERE NOT EXISTS (
    SELECT 1 FROM Order o WHERE o.custId = c.id
);
 
-- SQL Pattern 2: LEFT JOIN with NULL check (often efficient)
SELECT c.id, c.name
FROM Customer c
LEFT JOIN Order o ON o.custId = c.id
WHERE o.id IS NULL;
 
-- SQL Pattern 3: NOT IN (caution with NULLs!)
SELECT c.id, c.name
FROM Customer c
WHERE c.id NOT IN (
    SELECT o.custId FROM Order o WHERE o.custId IS NOT NULL
);
-- Warning: If any custId in Order is NULL, the entire NOT IN returns false
-- Always filter NULLs or use NOT EXISTS instead
 
-- SQL Pattern 4: EXCEPT / MINUS (set difference approach)
SELECT c.id FROM Customer c
EXCEPT
SELECT o.custId FROM Order o;
 
-- Complex anti-join: Employees who have never worked on ANY project with budget > 1M
-- TRC: {e | Employee(e) ∧ ¬∃w (Works(w) ∧ w.empId = e.id ∧ 
--           ∃p (Project(p) ∧ p.id = w.projectId ∧ p.budget > 1000000))}
 
SELECT e.id, e.name
FROM Employee e
WHERE NOT EXISTS (
    SELECT 1 FROM Works w
    JOIN Project p ON w.projectId = p.id
    WHERE w.empId = e.id AND p.budget > 1000000
);

NOT IN and NULL: A Dangerous Combination

Be extremely careful with NOT IN when the subquery can return NULL values. In SQL's three-valued logic, comparing anything to NULL yields UNKNOWN, and NOT IN with any NULL in the list returns no rows. Always use NOT EXISTS or explicitly filter NULLs in NOT IN subqueries. This is a common source of subtle bugs.

Equivalence of Anti-Join Forms

The following are logically equivalent (assuming proper NULL handling):

Method	TRC Equivalent	Pros	Cons
NOT EXISTS	Direct translation of ¬∃	Always correct, NULL-safe	May need correlation
LEFT JOIN + NULL	Set difference semantics	Often optimizes well	Requires understanding of NULL
NOT IN	Simple syntax	Compact for simple cases	NULL-sensitive!
EXCEPT/MINUS	Pure set operation	Clear set semantics	May need projection

Anti-Join with Multiple Conditions

Anti-joins can incorporate complex conditions in the negated existence:

"Customers who have NOT ordered in the past 30 days (but have ordered before)"

{c | Customer(c) ∧ ∃o₁ (Order(o₁) ∧ o₁.custId = c.id) ∧ # Has ordered ¬∃o₂ (Order(o₂) ∧ o₂.custId = c.id ∧ o₂.date > CURRENT_DATE - 30) # Not recently }

This combines a positive existence (has ordered) with a negated existence (not recently).

Negated Universals: Finding Exceptions

Negating a universal statement—claiming that NOT all elements satisfy a condition—is equivalent to asserting that SOME element fails the condition. This pattern is useful for finding exceptions and violations.

The Pattern

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

is equivalent to:

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

Examples

1. "Not all products are in stock" → "Some product is out of stock"

¬∀p (Product(p) → p.stock > 0) ≡ ∃p (Product(p) ∧ p.stock ≤ 0)

2. "Not all students passed the exam" → "Some student failed"

¬∀s (Student(s) → s.examGrade ≥ 60) ≡ ∃s (Student(s) ∧ s.examGrade < 60)

3. "It's not the case that all departments are profitable" → "Some department has a loss"

¬∀d (Department(d) → d.profit > 0) ≡ ∃d (Department(d) ∧ d.profit ≤ 0)

Finding Elements That Violate Universal Constraints

This pattern is particularly useful for constraint checking and exception finding:

negated_universal_examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
-- Find students who have NOT passed ALL their exams
-- Original: Students where ¬∀exam (passed)
-- Equivalent: Students who have at least one unpassed exam
 
-- TRC: { s | Student(s) ∧ ¬∀e ((Exam(e) ∧ e.studentId = s.id) → e.passed = TRUE) }
-- Transformed: { s | Student(s) ∧ ∃e (Exam(e) ∧ e.studentId = s.id ∧ e.passed = FALSE) }
 
SELECT DISTINCT s.id, s.name
FROM Student s
WHERE EXISTS (
    SELECT 1 FROM Exam e
    WHERE e.studentId = s.id AND e.passed = FALSE
);
 
-- Find departments where NOT all employees have completed training
-- Those with at least one employee lacking training
 
SELECT DISTINCT d.id, d.name
FROM Department d
WHERE EXISTS (
    SELECT 1 
    FROM Employee e
    WHERE e.deptId = d.id
    AND NOT EXISTS (
        SELECT 1 FROM TrainingCompletion tc
        WHERE tc.empId = e.id
    )
);
 
-- Find suppliers who do NOT supply all parts (contrast with division)
-- These are suppliers missing at least one part
 
SELECT s.id, s.name
FROM Supplier s
WHERE EXISTS (
    SELECT 1 FROM Part p
    WHERE NOT EXISTS (
        SELECT 1 FROM Supply sup
        WHERE sup.suppId = s.id AND sup.partId = p.id
    )
);
 
-- Find projects where NOT all tasks are complete
SELECT p.id, p.name
FROM Project p
WHERE EXISTS (
    SELECT 1 FROM Task t
    WHERE t.projectId = p.id AND t.status != 'Complete'
);

Negated Universal = Existential Negation

Instead of thinking 'not all satisfy property,' think 'find one that fails property.' This reframing converts a potentially complex negated universal into a straightforward existence check for counterexamples. Counterexample searching is often computationally easier than universal verification.

Double Negation: Implementing Universal via ¬∃¬

Since SQL lacks a direct FOR ALL construct, universal quantification is implemented using the double negation transformation. This is one of the most important patterns in database query formulation.

The Fundamental Equivalence

∀x P(x) ≡ ¬∃x ¬P(x)

"All x satisfy P" ≡ "There is no x that fails P"

This transforms a universal into a negated existence of counterexamples.

Step-by-Step Transformation

Original Query: "Find suppliers who supply ALL parts."

TRC: {s | Supplier(s) ∧ ∀p (Part(p) → ∃sp (Supply(sp) ∧ sp.sid = s.id ∧ sp.pid = p.id))}

Step 1 - Identify the universal: ∀p (Part(p) → ∃sp (...))

Step 2 - Apply ∀ ≡ ¬∃¬: ¬∃p ¬(Part(p) → ∃sp (...))

Step 3 - Simplify ¬(A → B) = A ∧ ¬B: ¬∃p (Part(p) ∧ ¬∃sp (...))

Step 4 - This is SQL's NOT EXISTS pattern:

NOT EXISTS (
    SELECT 1 FROM Part p
    WHERE NOT EXISTS (
        SELECT 1 FROM Supply sp
        WHERE sp.sid = s.id AND sp.pid = p.id
    )
)

double_negation_examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
-- Pattern: Universal Quantification via Double Negation
 
-- Example 1: Students enrolled in ALL computer science courses
-- TRC: { s | Student(s) ∧ ∀c ((Course(c) ∧ c.dept = 'CS') → 
--           ∃e (Enrollment(e) ∧ e.sid = s.id ∧ e.cid = c.id)) }
 
SELECT s.id, s.name
FROM Student s
WHERE NOT EXISTS (                    -- ∀ → ¬∃¬
    SELECT 1 FROM Course c            -- For each CS course...
    WHERE c.dept = 'CS'
    AND NOT EXISTS (                  -- ...that student hasn't taken
        SELECT 1 FROM Enrollment e
        WHERE e.sid = s.id AND e.cid = c.id
    )
);
-- Reading: "Find students for whom there is no CS course they haven't taken"
 
-- Example 2: Managers who have approved ALL pending requests
-- TRC: { m | Manager(m) ∧ ∀r ((Request(r) ∧ r.status = 'Pending') → 
--           ∃a (Approval(a) ∧ a.requestId = r.id ∧ a.managerId = m.id)) }
 
SELECT m.id, m.name
FROM Manager m
WHERE NOT EXISTS (
    SELECT 1 FROM Request r
    WHERE r.status = 'Pending'
    AND NOT EXISTS (
        SELECT 1 FROM Approval a
        WHERE a.requestId = r.id AND a.managerId = m.id
    )
);
 
-- Example 3: Products available at ALL warehouses
-- TRC: { p | Product(p) ∧ ∀w (Warehouse(w) → 
--           ∃i (Inventory(i) ∧ i.productId = p.id ∧ i.warehouseId = w.id ∧ i.quantity > 0)) }
 
SELECT p.id, p.name
FROM Product p
WHERE NOT EXISTS (
    SELECT 1 FROM Warehouse w
    WHERE NOT EXISTS (
        SELECT 1 FROM Inventory i
        WHERE i.productId = p.id 
          AND i.warehouseId = w.id 
          AND i.quantity > 0
    )
);

Reading Double-Negated SQL

To understand NOT EXISTS (... NOT EXISTS ...), read it as: 'There is no outer element for which there is no inner match.' The double negation cancels into: 'Every outer element has an inner match.' This is the universal pattern. Practice reading the double negation aloud until it becomes natural.

Alternative: Using COUNT for Universal

Some queries can verify universals using counting instead of double negation:

"Students enrolled in all CS courses" can also be expressed as:

SELECT s.id, s.name
FROM Student s
WHERE (
    SELECT COUNT(*) FROM Enrollment e
    JOIN Course c ON e.cid = c.id
    WHERE e.sid = s.id AND c.dept = 'CS'
) = (
    SELECT COUNT(*) FROM Course c WHERE c.dept = 'CS'
);

This says: "The number of CS courses this student is enrolled in equals the total number of CS courses."

Trade-offs:

COUNT approach: Simpler to write, but may be less efficient (requires counting)
Double negation: More complex syntax, but often optimizes better with indexes
The optimizer may transform between these forms anyway

Empty Set Handling

A critical consideration: What if there are NO CS courses?

Double negation: NOT EXISTS finds no counterexamples → TRUE (all students qualify vacuously)
COUNT approach: 0 = 0 → TRUE (also matches vacuously)

Both correctly handle empty sets, but you should verify this is the desired behavior for your business logic.

Negation and NULL: Three-Valued Logic

SQL's handling of NULL introduces three-valued logic (TRUE, FALSE, UNKNOWN), which complicates negation. Understanding this is essential for writing correct queries.

Three-Valued Logic Basics

When any operand is NULL, comparisons return UNKNOWN:

Expression	Result
NULL = 5	UNKNOWN
NULL ≠ 5	UNKNOWN
NULL > 10	UNKNOWN
NULL = NULL	UNKNOWN

Negation Truth Table with UNKNOWN

P	¬P
TRUE	FALSE
FALSE	TRUE
UNKNOWN	UNKNOWN

Negating UNKNOWN yields UNKNOWN—negation does NOT convert unknown to known.

AND/OR with UNKNOWN

P	Q	P ∧ Q	P ∨ Q
TRUE	UNKNOWN	UNKNOWN	TRUE
FALSE	UNKNOWN	FALSE	UNKNOWN
UNKNOWN	UNKNOWN	UNKNOWN	UNKNOWN

Note: FALSE ∧ UNKNOWN = FALSE (if one side is definitely false, the conjunction is false). TRUE ∨ UNKNOWN = TRUE (if one side is definitely true, the disjunction is true).

Impact of NULLs on Query Patterns
Pattern	NULL Behavior	Potential Issue
x != value	NULL != value → UNKNOWN → filtered out	NULLs silently excluded
NOT (x = value)	NOT UNKNOWN = UNKNOWN → filtered out	Same as above
x NOT IN (...)	If list contains NULL, always UNKNOWN	Returns no rows!
NOT EXISTS (...)	NULL-safe (checks row existence)	Works correctly
x IS NOT NULL	Explicit NULL check	Correct way to test

The NOT IN Trap with NULL

If the subquery in NOT IN can return NULL, the entire NOT IN returns UNKNOWN (which is FALSE in WHERE context), returning no rows. Consider: x NOT IN (1, 2, NULL). For any x, this becomes x!=1 AND x!=2 AND x!=NULL → TRUE AND TRUE AND UNKNOWN → UNKNOWN. Always use NOT EXISTS or filter NULLs in the subquery.

null_safe_negation.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
-- DANGEROUS: NOT IN with possible NULLs
-- This may return NO rows if any managerId is NULL!
SELECT e.id, e.name
FROM Employee e
WHERE e.id NOT IN (SELECT managerId FROM Department);
 
-- SAFE: NOT EXISTS (NULL-safe)
SELECT e.id, e.name
FROM Employee e
WHERE NOT EXISTS (
    SELECT 1 FROM Department d WHERE d.managerId = e.id
);
 
-- SAFE: NOT IN with NULL filtered
SELECT e.id, e.name
FROM Employee e
WHERE e.id NOT IN (
    SELECT managerId FROM Department WHERE managerId IS NOT NULL
);
 
-- SAFE: LEFT JOIN anti-pattern
SELECT e.id, e.name
FROM Employee e
LEFT JOIN Department d ON d.managerId = e.id
WHERE d.id IS NULL;
 
-- Checking for "value is not X" including NULLs
-- WRONG (excludes NULLs):
SELECT * FROM Employee WHERE dept != 'Sales';
 
-- RIGHT (includes NULLs and non-Sales):
SELECT * FROM Employee WHERE dept != 'Sales' OR dept IS NULL;
 
-- Using COALESCE for NULL handling in negation
SELECT * FROM Employee WHERE COALESCE(dept, 'Unknown') != 'Sales';

Practical Applications of Negation Patterns

Let's apply negation patterns to solve realistic database problems.

Application 1: Finding Inactive Users

Business Requirement: "Identify users who have not logged in within the past 90 days."

Analysis: This is a negated existence of recent activity.

TRC: {u | User(u) ∧ ¬∃l (Login(l) ∧ l.userId = u.id ∧ l.timestamp > CURRENT_DATE - 90)}

SQL:

SELECT u.id, u.email
FROM User u
WHERE NOT EXISTS (
    SELECT 1 FROM Login l
    WHERE l.userId = u.id
    AND l.timestamp > CURRENT_DATE - INTERVAL '90 days'
);

Application 2: Compliance Verification Exception

Business Requirement: "Find employees who have NOT completed all mandatory training modules."

Analysis: This is a negated universal—find those for whom ¬(all mandatory training completed).

TRC: {e | Employee(e) ∧ ¬∀t ((Training(t) ∧ t.mandatory = TRUE) → ∃c (Completion(c) ∧ c.empId = e.id ∧ c.trainingId = t.id))}

Transformed: {e | Employee(e) ∧ ∃t (Training(t) ∧ t.mandatory = TRUE ∧ ¬∃c ...)}

This finds employees missing at least one mandatory training.

practical_negation_examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
-- Application 3: Customers who ordered in 2023 but NOT in 2024
-- Combining positive and negative existence
 
SELECT c.id, c.name
FROM Customer c
WHERE EXISTS (
    SELECT 1 FROM Order o
    WHERE o.custId = c.id AND YEAR(o.orderDate) = 2023
)
AND NOT EXISTS (
    SELECT 1 FROM Order o
    WHERE o.custId = c.id AND YEAR(o.orderDate) = 2024
);
 
-- Application 4: Find "exclusive" relationships
-- Products sold ONLY in region 'East' (nowhere else)
 
SELECT p.id, p.name
FROM Product p
WHERE EXISTS (
    SELECT 1 FROM Sale s WHERE s.productId = p.id AND s.region = 'East'
)
AND NOT EXISTS (
    SELECT 1 FROM Sale s WHERE s.productId = p.id AND s.region != 'East'
);
 
-- Application 5: Orphan Record Detection
-- Order items referencing deleted products
 
SELECT oi.id, oi.orderId, oi.productId
FROM OrderItem oi
WHERE NOT EXISTS (
    SELECT 1 FROM Product p WHERE p.id = oi.productId
);
 
-- Application 6: Gap Finding
-- Days in January with no sales
 
WITH January AS (
    SELECT DATE '2024-01-01' + (n - 1) AS date
    FROM generate_series(1, 31) AS s(n)
)
SELECT j.date
FROM January j
WHERE NOT EXISTS (
    SELECT 1 FROM Sale s WHERE DATE(s.saleTime) = j.date
);
 
-- Application 7: Universal with Exception
-- Departments where ALMOST all employees have certification (>90%)
 
SELECT d.id, d.name
FROM Department d
WHERE (
    SELECT COUNT(*) FROM Employee e
    JOIN Certification c ON e.id = c.empId
    WHERE e.deptId = d.id
) >= 0.9 * (
    SELECT COUNT(*) FROM Employee e WHERE e.deptId = d.id
);

Pattern Selection Guide

NOT EXISTS: Use for relationships that should NOT exist (anti-join, exclusion). NOT EXISTS(NOT EXISTS()): Use for universal 'all' conditions (division). ¬∀ → ∃¬: Use for finding exceptions/violations. Negation + positive existence: Use for 'this but not that' patterns.

Summary: Negation Mastered

We have thoroughly explored negation in relational calculus—from fundamental logical properties through practical SQL implementations. Let's consolidate our understanding:

Key Takeaways

•De Morgan's Laws for Quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x) — negation flips quantifiers and passes inward.
•Anti-Join Pattern: ¬∃ implements anti-joins—finding elements WITHOUT corresponding matches. Use NOT EXISTS in SQL.
•Negated Universal = Existential Exception: ¬∀(...) transforms to ∃ NOT(...), useful for finding violations and exceptions.
•Double Negation for FOR ALL: Universal quantification ∀ is implemented as ¬∃¬ in SQL, creating the characteristic NOT EXISTS(NOT EXISTS()) pattern.
•NULL Complications: Three-valued logic makes negation subtle. ¬UNKNOWN = UNKNOWN. NOT IN is dangerous with NULLs; prefer NOT EXISTS.
•Negation Normal Form: Push negation to atomic predicates using De Morgan's laws for cleaner formulas.
•Practical Patterns: Inactive users, compliance exceptions, exclusive relationships, orphan detection all leverage negation.

Looking Ahead

With universal quantification (∀), existential quantification (∃), scope rules, and negation now mastered, we're ready to tackle complex expressions—formulas that combine all these elements in sophisticated ways to express intricate query conditions.

Page Complete

You now command the full power of negation in relational calculus. The ability to express absence, exclusion, and exception through De Morgan's laws and anti-join patterns is essential for advanced database querying. Next, we'll synthesize everything into complex composite expressions.

4 / 5

Loading learning content...

Database Management SystemsQuantifiers

Quantifiers in Relational Calculus

LevelIntermediate

Duration75 mins

TopicQuantifiers

4 / 5

Negation

The Power of Denial: Expressing What Is Not

Consider these common query requirements:

"Find customers who have NOT placed any orders."

"List products that are NOT in stock at ANY warehouse."

"Identify employees who have NOT completed ALL required training."

Mastering negation in relational calculus opens the door to anti-joins, exception queries, relational division, and complex filtering logic that would otherwise be difficult or impossible to express.

What You Will Learn

Fundamentals of Logical Negation

Logical negation (¬) is the simplest logical connective—it inverts truth values. But its interaction with complex formulas, especially quantified formulas, creates rich and powerful patterns.

Basic Negation

P	¬P
TRUE	FALSE
FALSE	TRUE

Negation is a unary operator—it takes one operand and produces its logical opposite.

Negation with Conjunctions and Disjunctions (De Morgan's Laws)

When negation is applied to conjunctions or disjunctions, De Morgan's laws govern the transformation:

¬(P ∧ Q) ≡ (¬P ∨ ¬Q) — "Not both" means "at least one is false"

¬(P ∨ Q) ≡ (¬P ∧ ¬Q) — "Neither" means "both are false"

These laws allow us to push negation inward through logical operators, transforming complex negated expressions into equivalent forms.

Negation with Implications

The implication operator has a specific negation pattern:

¬(P → Q) ≡ P ∧ ¬Q — "Not (if P then Q)" means "P is true but Q is false"

This is critical for understanding how negated universals decompose, since universals often use implication form.

The Implication Negation Pattern

Double Negation

¬¬P ≡ P — Double negation elimination

Negating twice returns to the original truth value. This principle is fundamental to the double-negation pattern for implementing universal quantification.

Negation Scope

Negation applies to the immediately following formula (or parenthesized sub-formula):

¬P ∧ Q means "(not P) and Q"

¬(P ∧ Q) means "not (P and Q)"

Parentheses are essential for controlling negation scope.

Negation in TRC Syntax

In TRC, negation is written as:

¬ (standard logic notation)
NOT (SQL-like notation)
~ (some systems)

Example: ¬∃e (Employee(e) ∧ e.salary > 100000)

Reads: "There does not exist an employee with salary greater than 100000."

Fundamental Negation Equivalences
Original	Negated Form	Equivalent Transformation
P	¬P	Direct negation
P ∧ Q	¬(P ∧ Q)	¬P ∨ ¬Q (De Morgan)
P ∨ Q	¬(P ∨ Q)	¬P ∧ ¬Q (De Morgan)
P → Q	¬(P → Q)	P ∧ ¬Q
¬P	¬¬P	P (double negation)
∀x P(x)	¬∀x P(x)	∃x ¬P(x) (quantifier negation)
∃x P(x)	¬∃x P(x)	∀x ¬P(x) (quantifier negation)

De Morgan's Laws for Quantifiers

The classical De Morgan's laws extend to quantifiers, providing the fundamental connection between ∀ and ∃ through negation.

Quantifier De Morgan's Laws

Law 1: Negated Universal

¬∀x P(x) ≡ ∃x ¬P(x)

In words: "Not all x satisfy P" is equivalent to "Some x fails P."

Intuition: If it's false that everyone passes, then someone must fail.

Law 2: Negated Existential

¬∃x P(x) ≡ ∀x ¬P(x)

In words: "There is no x satisfying P" is equivalent to "All x fail P."

Intuition: If nobody passes, then everyone must fail.

Derivation from Quantifier Duality

These laws follow directly from quantifier duality:

∀x P(x) ≡ ¬∃x ¬P(x)

Negating both sides:

¬∀x P(x) ≡ ¬¬∃x ¬P(x) ≡ ∃x ¬P(x)

Similarly for the existential case.

de_morgan_quantifiers_examples.trc

TRC Examples

# Example 1: Negated Universal
# "Not all employees have salary > 50000"
# ¬∀e (Employee(e) → e.salary > 50000)
# Equivalent to:
∃e (Employee(e) ∧ ¬(e.salary > 50000))
# Which simplifies to:
∃e (Employee(e) ∧ e.salary ≤ 50000)
# "Some employee has salary ≤ 50000"
 
# Example 2: Negated Existential
# "No customer has placed more than 100 orders"
# ¬∃c (Customer(c) ∧ c.orderCount > 100)
# Equivalent to:
∀c (Customer(c) → ¬(c.orderCount > 100))
# Which simplifies to:
∀c (Customer(c) → c.orderCount ≤ 100)
# "All customers have at most 100 orders"
 
# Example 3: Nested Negation with Universal
# "Not all departments have at least one manager"
# ¬∀d (Department(d) → ∃m (Manager(m) ∧ m.deptId = d.id))
# Apply De Morgan for ∀:
∃d (Department(d) ∧ ¬∃m (Manager(m) ∧ m.deptId = d.id))
# Apply De Morgan for inner ∃:
∃d (Department(d) ∧ ∀m (Manager(m) → m.deptId ≠ d.id))
# "Some department has no managers" OR equivalently:
∃d (Department(d) ∧ ∀m ¬(Manager(m) ∧ m.deptId = d.id))
 
# Example 4: Complex Negation
# "Not every course is taken by some student"
# ¬∀c (Course(c) → ∃e (Enrollment(e) ∧ e.cid = c.cid))
# Apply De Morgan:
∃c (Course(c) ∧ ∀e (Enrollment(e) → e.cid ≠ c.cid))
# "Some course is taken by no student" (unregistered courses exist)

Pushing Negation Through Quantifiers

Negation Normal Form (NNF)

A formula is in Negation Normal Form when negation appears only immediately before atomic predicates, not before complex sub-formulas. Any formula can be converted to NNF using:

De Morgan's laws for ∧ and ∨
Quantifier De Morgan's laws for ∀ and ∃
Implication elimination: P → Q ≡ ¬P ∨ Q
Double negation elimination: ¬¬P ≡ P

Example:

Original: ¬∀x (P(x) → ∃y Q(x, y))

Step 1 (¬∀ → ∃¬): ∃x ¬(P(x) → ∃y Q(x, y))

Step 2 (¬(P → Q) ≡ P ∧ ¬Q): ∃x (P(x) ∧ ¬∃y Q(x, y))

Step 3 (¬∃ → ∀¬): ∃x (P(x) ∧ ∀y ¬Q(x, y))

NNF Result: ∃x (P(x) ∧ ∀y ¬Q(x, y))

Negation Normal Form is useful for query optimization and theorem proving, as it standardizes where negations appear.

Negated Existence: The Anti-Join Pattern

One of the most common and practical uses of negation is the negated existence pattern, which implements anti-joins—finding elements that do NOT have corresponding matches.

The Pattern

{a | A(a) ∧ ¬∃b (B(b) ∧ link(a, b))}

This reads: "Find all elements of A for which there does NOT exist a related element in B."

Common Applications

1. Customers without orders {c | Customer(c) ∧ ¬∃o (Order(o) ∧ o.custId = c.id)}

2. Products never reviewed {p | Product(p) ∧ ¬∃r (Review(r) ∧ r.productId = p.id)}

3. Employees who have never managed a project {e | Employee(e) ∧ ¬∃p (Project(p) ∧ p.managerId = e.id)}

4. Courses with no prerequisites {c | Course(c) ∧ ¬∃p (Prerequisite(p) ∧ p.courseId = c.id)}

5. Departments with no current vacancies {d | Department(d) ∧ ¬∃v (Vacancy(v) ∧ v.deptId = d.id ∧ v.status = 'Open')}

anti_join_sql_patterns.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
-- TRC: {c | Customer(c) ∧ ¬∃o (Order(o) ∧ o.custId = c.id)}
 
-- SQL Pattern 1: NOT EXISTS (most direct translation)
SELECT c.id, c.name
FROM Customer c
WHERE NOT EXISTS (
    SELECT 1 FROM Order o WHERE o.custId = c.id
);
 
-- SQL Pattern 2: LEFT JOIN with NULL check (often efficient)
SELECT c.id, c.name
FROM Customer c
LEFT JOIN Order o ON o.custId = c.id
WHERE o.id IS NULL;
 
-- SQL Pattern 3: NOT IN (caution with NULLs!)
SELECT c.id, c.name
FROM Customer c
WHERE c.id NOT IN (
    SELECT o.custId FROM Order o WHERE o.custId IS NOT NULL
);
-- Warning: If any custId in Order is NULL, the entire NOT IN returns false
-- Always filter NULLs or use NOT EXISTS instead
 
-- SQL Pattern 4: EXCEPT / MINUS (set difference approach)
SELECT c.id FROM Customer c
EXCEPT
SELECT o.custId FROM Order o;
 
-- Complex anti-join: Employees who have never worked on ANY project with budget > 1M
-- TRC: {e | Employee(e) ∧ ¬∃w (Works(w) ∧ w.empId = e.id ∧ 
--           ∃p (Project(p) ∧ p.id = w.projectId ∧ p.budget > 1000000))}
 
SELECT e.id, e.name
FROM Employee e
WHERE NOT EXISTS (
    SELECT 1 FROM Works w
    JOIN Project p ON w.projectId = p.id
    WHERE w.empId = e.id AND p.budget > 1000000
);

NOT IN and NULL: A Dangerous Combination

Equivalence of Anti-Join Forms

The following are logically equivalent (assuming proper NULL handling):

Method	TRC Equivalent	Pros	Cons
NOT EXISTS	Direct translation of ¬∃	Always correct, NULL-safe	May need correlation
LEFT JOIN + NULL	Set difference semantics	Often optimizes well	Requires understanding of NULL
NOT IN	Simple syntax	Compact for simple cases	NULL-sensitive!
EXCEPT/MINUS	Pure set operation	Clear set semantics	May need projection

Anti-Join with Multiple Conditions

Anti-joins can incorporate complex conditions in the negated existence:

"Customers who have NOT ordered in the past 30 days (but have ordered before)"

{c | Customer(c) ∧ ∃o₁ (Order(o₁) ∧ o₁.custId = c.id) ∧ # Has ordered ¬∃o₂ (Order(o₂) ∧ o₂.custId = c.id ∧ o₂.date > CURRENT_DATE - 30) # Not recently }

This combines a positive existence (has ordered) with a negated existence (not recently).

Negated Universals: Finding Exceptions

The Pattern

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

is equivalent to:

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

Examples

1. "Not all products are in stock" → "Some product is out of stock"

¬∀p (Product(p) → p.stock > 0) ≡ ∃p (Product(p) ∧ p.stock ≤ 0)

2. "Not all students passed the exam" → "Some student failed"

¬∀s (Student(s) → s.examGrade ≥ 60) ≡ ∃s (Student(s) ∧ s.examGrade < 60)

3. "It's not the case that all departments are profitable" → "Some department has a loss"

¬∀d (Department(d) → d.profit > 0) ≡ ∃d (Department(d) ∧ d.profit ≤ 0)

Finding Elements That Violate Universal Constraints

This pattern is particularly useful for constraint checking and exception finding:

negated_universal_examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
-- Find students who have NOT passed ALL their exams
-- Original: Students where ¬∀exam (passed)
-- Equivalent: Students who have at least one unpassed exam
 
-- TRC: { s | Student(s) ∧ ¬∀e ((Exam(e) ∧ e.studentId = s.id) → e.passed = TRUE) }
-- Transformed: { s | Student(s) ∧ ∃e (Exam(e) ∧ e.studentId = s.id ∧ e.passed = FALSE) }
 
SELECT DISTINCT s.id, s.name
FROM Student s
WHERE EXISTS (
    SELECT 1 FROM Exam e
    WHERE e.studentId = s.id AND e.passed = FALSE
);
 
-- Find departments where NOT all employees have completed training
-- Those with at least one employee lacking training
 
SELECT DISTINCT d.id, d.name
FROM Department d
WHERE EXISTS (
    SELECT 1 
    FROM Employee e
    WHERE e.deptId = d.id
    AND NOT EXISTS (
        SELECT 1 FROM TrainingCompletion tc
        WHERE tc.empId = e.id
    )
);
 
-- Find suppliers who do NOT supply all parts (contrast with division)
-- These are suppliers missing at least one part
 
SELECT s.id, s.name
FROM Supplier s
WHERE EXISTS (
    SELECT 1 FROM Part p
    WHERE NOT EXISTS (
        SELECT 1 FROM Supply sup
        WHERE sup.suppId = s.id AND sup.partId = p.id
    )
);
 
-- Find projects where NOT all tasks are complete
SELECT p.id, p.name
FROM Project p
WHERE EXISTS (
    SELECT 1 FROM Task t
    WHERE t.projectId = p.id AND t.status != 'Complete'
);

Negated Universal = Existential Negation

Double Negation: Implementing Universal via ¬∃¬

The Fundamental Equivalence

∀x P(x) ≡ ¬∃x ¬P(x)

"All x satisfy P" ≡ "There is no x that fails P"

This transforms a universal into a negated existence of counterexamples.

Step-by-Step Transformation

Original Query: "Find suppliers who supply ALL parts."

TRC: {s | Supplier(s) ∧ ∀p (Part(p) → ∃sp (Supply(sp) ∧ sp.sid = s.id ∧ sp.pid = p.id))}

Step 1 - Identify the universal: ∀p (Part(p) → ∃sp (...))

Step 2 - Apply ∀ ≡ ¬∃¬: ¬∃p ¬(Part(p) → ∃sp (...))

Step 3 - Simplify ¬(A → B) = A ∧ ¬B: ¬∃p (Part(p) ∧ ¬∃sp (...))

Step 4 - This is SQL's NOT EXISTS pattern:

NOT EXISTS (
    SELECT 1 FROM Part p
    WHERE NOT EXISTS (
        SELECT 1 FROM Supply sp
        WHERE sp.sid = s.id AND sp.pid = p.id
    )
)

double_negation_examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
-- Pattern: Universal Quantification via Double Negation
 
-- Example 1: Students enrolled in ALL computer science courses
-- TRC: { s | Student(s) ∧ ∀c ((Course(c) ∧ c.dept = 'CS') → 
--           ∃e (Enrollment(e) ∧ e.sid = s.id ∧ e.cid = c.id)) }
 
SELECT s.id, s.name
FROM Student s
WHERE NOT EXISTS (                    -- ∀ → ¬∃¬
    SELECT 1 FROM Course c            -- For each CS course...
    WHERE c.dept = 'CS'
    AND NOT EXISTS (                  -- ...that student hasn't taken
        SELECT 1 FROM Enrollment e
        WHERE e.sid = s.id AND e.cid = c.id
    )
);
-- Reading: "Find students for whom there is no CS course they haven't taken"
 
-- Example 2: Managers who have approved ALL pending requests
-- TRC: { m | Manager(m) ∧ ∀r ((Request(r) ∧ r.status = 'Pending') → 
--           ∃a (Approval(a) ∧ a.requestId = r.id ∧ a.managerId = m.id)) }
 
SELECT m.id, m.name
FROM Manager m
WHERE NOT EXISTS (
    SELECT 1 FROM Request r
    WHERE r.status = 'Pending'
    AND NOT EXISTS (
        SELECT 1 FROM Approval a
        WHERE a.requestId = r.id AND a.managerId = m.id
    )
);
 
-- Example 3: Products available at ALL warehouses
-- TRC: { p | Product(p) ∧ ∀w (Warehouse(w) → 
--           ∃i (Inventory(i) ∧ i.productId = p.id ∧ i.warehouseId = w.id ∧ i.quantity > 0)) }
 
SELECT p.id, p.name
FROM Product p
WHERE NOT EXISTS (
    SELECT 1 FROM Warehouse w
    WHERE NOT EXISTS (
        SELECT 1 FROM Inventory i
        WHERE i.productId = p.id 
          AND i.warehouseId = w.id 
          AND i.quantity > 0
    )
);

Reading Double-Negated SQL

Alternative: Using COUNT for Universal

Some queries can verify universals using counting instead of double negation:

"Students enrolled in all CS courses" can also be expressed as:

SELECT s.id, s.name
FROM Student s
WHERE (
    SELECT COUNT(*) FROM Enrollment e
    JOIN Course c ON e.cid = c.id
    WHERE e.sid = s.id AND c.dept = 'CS'
) = (
    SELECT COUNT(*) FROM Course c WHERE c.dept = 'CS'
);

This says: "The number of CS courses this student is enrolled in equals the total number of CS courses."

Trade-offs:

COUNT approach: Simpler to write, but may be less efficient (requires counting)
Double negation: More complex syntax, but often optimizes better with indexes
The optimizer may transform between these forms anyway

Empty Set Handling

A critical consideration: What if there are NO CS courses?

Double negation: NOT EXISTS finds no counterexamples → TRUE (all students qualify vacuously)
COUNT approach: 0 = 0 → TRUE (also matches vacuously)

Both correctly handle empty sets, but you should verify this is the desired behavior for your business logic.

Negation and NULL: Three-Valued Logic

SQL's handling of NULL introduces three-valued logic (TRUE, FALSE, UNKNOWN), which complicates negation. Understanding this is essential for writing correct queries.

Three-Valued Logic Basics

When any operand is NULL, comparisons return UNKNOWN:

Expression	Result
NULL = 5	UNKNOWN
NULL ≠ 5	UNKNOWN
NULL > 10	UNKNOWN
NULL = NULL	UNKNOWN

Negation Truth Table with UNKNOWN

P	¬P
TRUE	FALSE
FALSE	TRUE
UNKNOWN	UNKNOWN

Negating UNKNOWN yields UNKNOWN—negation does NOT convert unknown to known.

AND/OR with UNKNOWN

P	Q	P ∧ Q	P ∨ Q
TRUE	UNKNOWN	UNKNOWN	TRUE
FALSE	UNKNOWN	FALSE	UNKNOWN
UNKNOWN	UNKNOWN	UNKNOWN	UNKNOWN

Note: FALSE ∧ UNKNOWN = FALSE (if one side is definitely false, the conjunction is false). TRUE ∨ UNKNOWN = TRUE (if one side is definitely true, the disjunction is true).

Impact of NULLs on Query Patterns
Pattern	NULL Behavior	Potential Issue
x != value	NULL != value → UNKNOWN → filtered out	NULLs silently excluded
NOT (x = value)	NOT UNKNOWN = UNKNOWN → filtered out	Same as above
x NOT IN (...)	If list contains NULL, always UNKNOWN	Returns no rows!
NOT EXISTS (...)	NULL-safe (checks row existence)	Works correctly
x IS NOT NULL	Explicit NULL check	Correct way to test

The NOT IN Trap with NULL

null_safe_negation.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
-- DANGEROUS: NOT IN with possible NULLs
-- This may return NO rows if any managerId is NULL!
SELECT e.id, e.name
FROM Employee e
WHERE e.id NOT IN (SELECT managerId FROM Department);
 
-- SAFE: NOT EXISTS (NULL-safe)
SELECT e.id, e.name
FROM Employee e
WHERE NOT EXISTS (
    SELECT 1 FROM Department d WHERE d.managerId = e.id
);
 
-- SAFE: NOT IN with NULL filtered
SELECT e.id, e.name
FROM Employee e
WHERE e.id NOT IN (
    SELECT managerId FROM Department WHERE managerId IS NOT NULL
);
 
-- SAFE: LEFT JOIN anti-pattern
SELECT e.id, e.name
FROM Employee e
LEFT JOIN Department d ON d.managerId = e.id
WHERE d.id IS NULL;
 
-- Checking for "value is not X" including NULLs
-- WRONG (excludes NULLs):
SELECT * FROM Employee WHERE dept != 'Sales';
 
-- RIGHT (includes NULLs and non-Sales):
SELECT * FROM Employee WHERE dept != 'Sales' OR dept IS NULL;
 
-- Using COALESCE for NULL handling in negation
SELECT * FROM Employee WHERE COALESCE(dept, 'Unknown') != 'Sales';

Practical Applications of Negation Patterns

Let's apply negation patterns to solve realistic database problems.

Application 1: Finding Inactive Users

Business Requirement: "Identify users who have not logged in within the past 90 days."

Analysis: This is a negated existence of recent activity.

TRC: {u | User(u) ∧ ¬∃l (Login(l) ∧ l.userId = u.id ∧ l.timestamp > CURRENT_DATE - 90)}

SQL:

SELECT u.id, u.email
FROM User u
WHERE NOT EXISTS (
    SELECT 1 FROM Login l
    WHERE l.userId = u.id
    AND l.timestamp > CURRENT_DATE - INTERVAL '90 days'
);

Application 2: Compliance Verification Exception

Business Requirement: "Find employees who have NOT completed all mandatory training modules."

Analysis: This is a negated universal—find those for whom ¬(all mandatory training completed).

TRC: {e | Employee(e) ∧ ¬∀t ((Training(t) ∧ t.mandatory = TRUE) → ∃c (Completion(c) ∧ c.empId = e.id ∧ c.trainingId = t.id))}

Transformed: {e | Employee(e) ∧ ∃t (Training(t) ∧ t.mandatory = TRUE ∧ ¬∃c ...)}

This finds employees missing at least one mandatory training.

practical_negation_examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
-- Application 3: Customers who ordered in 2023 but NOT in 2024
-- Combining positive and negative existence
 
SELECT c.id, c.name
FROM Customer c
WHERE EXISTS (
    SELECT 1 FROM Order o
    WHERE o.custId = c.id AND YEAR(o.orderDate) = 2023
)
AND NOT EXISTS (
    SELECT 1 FROM Order o
    WHERE o.custId = c.id AND YEAR(o.orderDate) = 2024
);
 
-- Application 4: Find "exclusive" relationships
-- Products sold ONLY in region 'East' (nowhere else)
 
SELECT p.id, p.name
FROM Product p
WHERE EXISTS (
    SELECT 1 FROM Sale s WHERE s.productId = p.id AND s.region = 'East'
)
AND NOT EXISTS (
    SELECT 1 FROM Sale s WHERE s.productId = p.id AND s.region != 'East'
);
 
-- Application 5: Orphan Record Detection
-- Order items referencing deleted products
 
SELECT oi.id, oi.orderId, oi.productId
FROM OrderItem oi
WHERE NOT EXISTS (
    SELECT 1 FROM Product p WHERE p.id = oi.productId
);
 
-- Application 6: Gap Finding
-- Days in January with no sales
 
WITH January AS (
    SELECT DATE '2024-01-01' + (n - 1) AS date
    FROM generate_series(1, 31) AS s(n)
)
SELECT j.date
FROM January j
WHERE NOT EXISTS (
    SELECT 1 FROM Sale s WHERE DATE(s.saleTime) = j.date
);
 
-- Application 7: Universal with Exception
-- Departments where ALMOST all employees have certification (>90%)
 
SELECT d.id, d.name
FROM Department d
WHERE (
    SELECT COUNT(*) FROM Employee e
    JOIN Certification c ON e.id = c.empId
    WHERE e.deptId = d.id
) >= 0.9 * (
    SELECT COUNT(*) FROM Employee e WHERE e.deptId = d.id
);

Pattern Selection Guide

Summary: Negation Mastered

We have thoroughly explored negation in relational calculus—from fundamental logical properties through practical SQL implementations. Let's consolidate our understanding:

Key Takeaways

•De Morgan's Laws for Quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x) — negation flips quantifiers and passes inward.
•Anti-Join Pattern: ¬∃ implements anti-joins—finding elements WITHOUT corresponding matches. Use NOT EXISTS in SQL.
•Negated Universal = Existential Exception: ¬∀(...) transforms to ∃ NOT(...), useful for finding violations and exceptions.
•Double Negation for FOR ALL: Universal quantification ∀ is implemented as ¬∃¬ in SQL, creating the characteristic NOT EXISTS(NOT EXISTS()) pattern.
•NULL Complications: Three-valued logic makes negation subtle. ¬UNKNOWN = UNKNOWN. NOT IN is dangerous with NULLs; prefer NOT EXISTS.
•Negation Normal Form: Push negation to atomic predicates using De Morgan's laws for cleaner formulas.
•Practical Patterns: Inactive users, compliance exceptions, exclusive relationships, orphan detection all leverage negation.

Looking Ahead

Page Complete

4 / 5