Safe vs unsafe expressions; relational completeness

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Write "for all c in COURSE, P(c) ⇒ Q(c)" with ¬∃. from Lesson 3.2.2
2. What is the basic set of RA operators? from Lesson 3.1.6
3. What does R − S return? from Lesson 3.1.2

1 · The Hook

{ t | ¬(t ∈ STUDENT) } reads innocently: "all tuples that are not students". But how many tuples are not students? Every possible tuple of every possible value: infinitely many. A DBMS cannot return that. TRC needs a rule that bans such queries, and GATE asks you to spot them.

2 · Predict First

Which of these can a DBMS actually answer? (a) { t | t ∈ STUDENT ∧ ¬(t.dept = 'CS') } (b) { t | ¬(t ∈ STUDENT) }

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

(a) Yes: t ranges over STUDENT, so the answer is the finite set {Bhavin, Diya}. (b) No: t is not tied to any relation, so the answer is infinite. (b) is unsafe.

Domain of a formula

The domain of a TRC expression, dom(P), is the set of all values that appear in the formula as constants, plus all values in the relations mentioned in it. It is finite.

Safe expression

A TRC expression { t | P(t) } is safe if every value in every result tuple comes from dom(P). Practical test: the result variable must be range-restricted: tied to a relation by a positive t ∈ R (or by t.A = s.A for some range-restricted s), not only by negations.

Relational completeness

A query language is relationally complete if it can express every query of basic relational algebra (σ, π, ∪, −, ×, ρ).

Codd's theorem: basic relational algebra, safe tuple relational calculus and safe domain relational calculus have exactly the same expressive power.

• Unsafe TRC can describe more (infinite answers), but those are not real queries.
• Neither basic RA nor safe TRC can compute aggregates (COUNT, SUM) or recursive closure ("all prerequisites of prerequisites, at any depth"). Extended RA (γ) and SQL go beyond them.
• SQL is relationally complete.

Domain relational calculus (one look)

DRC uses variables for values instead of tuples: { ⟨n⟩ | ∃r ∃d ∃g (⟨r, n, d, g⟩ ∈ STUDENT ∧ d = 'CS') } returns CS student names. Safe DRC has the same power as safe TRC.

4 · Visual

             finite world                          infinite world
  +-------------------------------------+
  |  values in STUDENT, COURSE, ...     |    every other string, number, tuple ...
  |  + constants in the query           |
  |  = dom(P)                           |
  +-------------------------------------+
  SAFE: every answer value lies inside the box.
  UNSAFE: some answer may lie outside (e.g. "not a student").

5 · Worked Examples

Example 1 Easy

Is { t | t ∈ ENROLL ∧ t.grade ≠ 'A' } safe? What does it return?

Solution

Safe: t ranges over ENROLL. Returns the 4 enrolments with grades B or C.

Example 2 Medium

Rewrite the unsafe "students' rolls that are not in ENROLL" as a safe expression.

Solution

Unsafe: { t | ¬∃e ∈ ENROLL (e.roll = t.roll) }. Safe: { t.roll | t ∈ STUDENT ∧ ¬∃e ∈ ENROLL (e.roll = t.roll) }, restricting t to STUDENT first.

Example 3 GATE

Which statement is true? (A) Safe TRC can express aggregation. (B) Basic RA and safe TRC are equally expressive. (C) TRC is more expressive than RA for safe queries. (D) SQL is not relationally complete.

Solution

(B) (Codd's theorem). A, C, D are false.

8 · Connect the Dots

Chapter 3.2 is complete: TRC syntax, the three patterns, and safety. Next: the Chapter 3.2 Lock-in, then Chapter 3.3: SQL, the language real systems use, which mixes calculus-style WHERE clauses with algebra-style operators.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Safety

Which expression is unsafe?

1. (A) { t | t ∈ R ∨ t ∈ S }
2. (B) { t | t ∈ R ∧ ¬(t ∈ S) }
3. (C) { t | t ∈ R ∧ t.A = 3 }
4. (D) { t | ¬(t ∈ R) }

Q2 · MCQ · 1 mark(s) — Completeness

Codd's theorem says that basic relational algebra is equivalent in expressive power to:

1. (A) safe TRC and safe DRC
2. (B) extended relational algebra
3. (C) all TRC expressions, safe or unsafe
4. (D) SQL with aggregation

Q3 · MSQ · 2 mark(s) — Expressiveness

Which cannot be expressed in basic relational algebra?

1. (A) Number of students in each department
2. (B) Students who took every CS course
3. (C) All prerequisites of a course, at any depth (unknown depth)
4. (D) Courses that no student took

Q4 · MCQ · 2 mark(s) — Safety

Is { t | t ∈ R ∨ t.A = 5 } safe?

1. (A) Yes, because 5 is a constant
2. (B) Yes, because R is mentioned
3. (C) No, because ∨ is never allowed
4. (D) No, because the second disjunct allows any tuple with A = 5

Q5 · MCQ · 1 mark(s) — DRC

In domain relational calculus, variables range over:

1. (A) relations
2. (B) tuples
3. (C) schemas
4. (D) attribute values

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

domain of a formulasafe expressionunsafe expressionrange-restricted variablerelational completenessCodd's theoremdomain relational calculus (DRC)