Tuple and domain relational calculus

Relational calculus describes the answer to a query instead of the steps that compute it. A tuple relational calculus query has the form { t | P(t) }: it returns every tuple t that makes the formula P true. P is built from comparisons of attributes, the connectives ∧ (and), ∨ (or), ¬ (not) and ⇒ (implies), and two quantifiers: ∃, “there exists”, and ∀, “for all”. In domain relational calculus, the variables stand for single attribute values instead of whole tuples. Some formulas, such as “every tuple that is not in R”, have answers that depend on which values are assumed to exist; these unsafe queries are excluded. Codd’s theorem says that safe tuple calculus, safe domain calculus and relational algebra express exactly the same queries, so any question written in one can be written in the others. This lesson writes each query as a Python comprehension that runs, translates every quantifier into SQL, and evaluates an unsafe query over two domains to get two different answers.

The parts of a calculus query

A query names one free variable and states a condition on it. The building blocks of the condition are atoms:

• t ∈ R: the tuple t is in the relation R.
• t.A θ s.B: an attribute of t compared with an attribute of another tuple variable s, where θ is one of =, ≠, <, ≤, > and ≥.
• t.A θ c: an attribute compared with a constant, such as s.branch = ‘CSE’.

Atoms combine with ∧, ∨, ¬ and ⇒, and the quantifiers introduce new variables. ∃e ∈ Enrolled (F) says that some tuple e of Enrolled makes F true, and is shorthand for ∃e (e ∈ Enrolled ∧ F). ∀k ∈ Core (F) says that every tuple of Core makes F true, and is shorthand for ∀k (k ∈ Core ⇒ F). A variable introduced by a quantifier is bound; the variable of the query, the one before the bar, is the only one left free, and the answer is the set of its values that make the formula true.

The result needs a heading of its own. Formally, { t | ∃s ∈ Student (s.branch = ‘CSE’ ∧ t.name = s.name) } returns tuples t with the single attribute name, and a common shorthand writes it as { s.name | s ∈ Student ∧ s.branch = ‘CSE’ }. The examples use the shorter form, over the module’s sample relations written as Python named tuples:

"""The sample relations, with named tuples so that a tuple variable s has s.sid, s.name and s.branch."""
from collections import namedtuple

S = namedtuple("Student", "sid name branch")
C = namedtuple("Course", "cid title dept credits")
E = namedtuple("Enrolled", "sid cid grade")
K = namedtuple("Core", "cid")

Student = [S(1, "Asha", "CSE"), S(2, "Bilal", "ECE"), S(3, "Chitra", "CSE"),
           S(4, "Dev", "ME"), S(5, "Esha", "CSE"), S(6, "Farhan", "ECE")]
Course = [C("CS201", "Databases", "CSE", 4), C("CS202", "Operating Systems", "CSE", 4),
          C("CS301", "Compilers", "CSE", 4), C("MA101", "Discrete Mathematics", "MATH", 3),
          C("EC210", "Signals and Systems", "ECE", 3), C("HS101", "Technical Writing", "HSS", 2)]
Enrolled = [E(1, "CS201", "A"), E(1, "CS202", "B"), E(1, "MA101", "A"), E(2, "EC210", "A"),
            E(2, "MA101", "B"), E(3, "CS201", "B"), E(3, "MA101", "A"), E(4, "MA101", "C"),
            E(5, "CS201", "A"), E(5, "CS202", "A"), E(5, "MA101", "B"), E(5, "HS101", "A")]
Core = [K("CS201"), K("CS202"), K("MA101")]

Existential and universal quantifiers, run

A calculus query and a Python set comprehension have the same shape: the free variable becomes the loop variable of the comprehension, ∃ becomes any(...) and ∀ becomes all(...), each over the relation the variable ranges over. Python’s all() returns True for an empty iterable, which is exactly the logic of ∀ over an empty range.

"""Tuple relational calculus queries, each written as a Python set comprehension.

∃e ∈ Enrolled (...) becomes any(... for e in Enrolled) and ∀c ∈ Core (...) becomes all(... for c in Core).
"""
from college import Core, Course, Enrolled, Student


def show(query, answer):
    print(query)
    print("  →", sorted(answer) if answer else "no tuples")


show("{ s.name | s ∈ Student ∧ s.branch = 'CSE' }",
     {s.name for s in Student if s.branch == "CSE"})

show("{ s.name | s ∈ Student ∧ ∃e ∈ Enrolled ∃c ∈ Course (e.sid = s.sid ∧ e.cid = c.cid ∧ c.dept = 'MATH' ∧ e.grade = 'A') }",
     {s.name for s in Student
      if any(e.sid == s.sid and e.cid == c.cid and c.dept == "MATH" and e.grade == "A" for e in Enrolled for c in Course)})

show("{ s.name | s ∈ Student ∧ ¬∃e ∈ Enrolled (e.sid = s.sid) }",
     {s.name for s in Student if not any(e.sid == s.sid for e in Enrolled)})

show("{ s.name | s ∈ Student ∧ ∀k ∈ Core ∃e ∈ Enrolled (e.sid = s.sid ∧ e.cid = k.cid) }",
     {s.name for s in Student if all(any(e.sid == s.sid and e.cid == k.cid for e in Enrolled) for k in Core)})

# P ⇒ Q is (not P) or Q: the courses outside CSE impose nothing.
show("{ s.name | s ∈ Student ∧ ∀c ∈ Course (c.dept = 'CSE' ⇒ ∃e ∈ Enrolled (e.sid = s.sid ∧ e.cid = c.cid)) }",
     {s.name for s in Student
      if all(c.dept != "CSE" or any(e.sid == s.sid and e.cid == c.cid for e in Enrolled) for c in Course)})

# A universal quantifier over an empty range is true: with no core courses, every student qualifies.
show("the same ∀k ∈ Core query with Core empty",
     {s.name for s in Student if all(any(e.sid == s.sid and e.cid == k.cid for e in Enrolled) for k in [])})

show("{ s.name | s ∈ Student ∧ ∀e ∈ Enrolled (e.sid = s.sid ⇒ e.grade = 'A') }",
     {s.name for s in Student if all(e.sid != s.sid or e.grade == "A" for e in Enrolled)})

{ s.name | s ∈ Student ∧ s.branch = 'CSE' }
  → ['Asha', 'Chitra', 'Esha']
{ s.name | s ∈ Student ∧ ∃e ∈ Enrolled ∃c ∈ Course (e.sid = s.sid ∧ e.cid = c.cid ∧ c.dept = 'MATH' ∧ e.grade = 'A') }
  → ['Asha', 'Chitra']
{ s.name | s ∈ Student ∧ ¬∃e ∈ Enrolled (e.sid = s.sid) }
  → ['Farhan']
{ s.name | s ∈ Student ∧ ∀k ∈ Core ∃e ∈ Enrolled (e.sid = s.sid ∧ e.cid = k.cid) }
  → ['Asha', 'Esha']
{ s.name | s ∈ Student ∧ ∀c ∈ Course (c.dept = 'CSE' ⇒ ∃e ∈ Enrolled (e.sid = s.sid ∧ e.cid = c.cid)) }
  → no tuples
the same ∀k ∈ Core query with Core empty
  → ['Asha', 'Bilal', 'Chitra', 'Dev', 'Esha', 'Farhan']
{ s.name | s ∈ Student ∧ ∀e ∈ Enrolled (e.sid = s.sid ⇒ e.grade = 'A') }
  → ['Farhan']

Each quantifier pattern answers a kind of question that the algebra answers with its own operator:

• ∃ (there is a matching tuple) is a join followed by a projection, or a semijoin: the students with an A in a MATH course, through two existential variables, one over Enrolled and one over Course.
• ¬∃ (there is no matching tuple) is an antijoin, or a difference: Farhan, the student with no enrolment.
• ∀ … ∃ (every tuple of one relation is matched) is division: Asha and Esha took every core course.
• ∀ with ⇒ restricts what “every” ranges over. P ⇒ Q is false only when P is true and Q is false, so it is the same as ¬P ∨ Q. ∀c ∈ Course (c.dept = ‘CSE’ ⇒ …) only makes demands of CSE courses, and since nobody took CS301, no student satisfies it.

The last two queries show vacuous truth. With an empty Core, the ∀ has nothing to check and holds for all six students. And the query for students all of whose enrolments have grade A returns only Farhan, who has no enrolments: for him the left side of the implication is never true, so the implication never fails. Questions that say “all” or “only” need this check: what does the query return for a tuple with nothing to check?

Two equivalences let you move between the quantifiers. ∀x F is the same as ¬∃x ¬F (nothing fails F), and ¬(P ∧ Q) is the same as ¬P ∨ ¬Q. Together they turn “every core course was taken” into “no core course exists that was not taken”, which is how SQL has to say it.

From calculus to SQL

SQL has EXISTS but no FOR ALL, so every universal quantifier is written with two negations. Each pattern above has a direct SQL form and an algebra counterpart:

• s ∈ Student is FROM student s, and in the algebra the relation Student itself.
• s.branch = ‘CSE’ is WHERE s.branch = 'CSE', a selection σ branch = ‘CSE’.
• ∃e ∈ Enrolled (F) is EXISTS (SELECT 1 FROM enrolled e WHERE F), a join and a projection, or a semijoin.
• ¬∃e ∈ Enrolled (F) is NOT EXISTS (SELECT 1 FROM enrolled e WHERE F), an antijoin, or a difference.
• ∀k ∈ Core (F) is NOT EXISTS (SELECT 1 FROM core k WHERE NOT F), a division.
• P ⇒ Q is NOT P OR Q, or NOT (P AND NOT Q).

CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
CREATE TABLE core (cid TEXT PRIMARY KEY);
INSERT INTO student VALUES
  (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
  (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
  ('CS201', 'Databases', 'CSE', 4), ('CS202', 'Operating Systems', 'CSE', 4),
  ('CS301', 'Compilers', 'CSE', 4), ('MA101', 'Discrete Mathematics', 'MATH', 3),
  ('EC210', 'Signals and Systems', 'ECE', 3), ('HS101', 'Technical Writing', 'HSS', 2);
INSERT INTO enrolled VALUES
  (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
  (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
  (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');
INSERT INTO core VALUES ('CS201'), ('CS202'), ('MA101');

-- Each quantifier of the calculus becomes a subquery: ∃ is EXISTS, ¬∃ is NOT EXISTS,
-- and ∀x (P ⇒ Q) is "no x with P and not Q": NOT EXISTS (... WHERE P AND NOT Q).
SELECT '∃ an A in a MATH course' AS formula, group_concat(name, ', ' ORDER BY sid) AS students
FROM student s
WHERE EXISTS (SELECT 1 FROM enrolled e JOIN course c ON c.cid = e.cid
              WHERE e.sid = s.sid AND c.dept = 'MATH' AND e.grade = 'A')
UNION ALL
SELECT '¬∃ any enrolment', group_concat(name, ', ' ORDER BY sid)
FROM student s
WHERE NOT EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = s.sid)
UNION ALL
SELECT '∀ core courses taken', group_concat(name, ', ' ORDER BY sid)
FROM student s
WHERE NOT EXISTS (SELECT 1 FROM core k
                  WHERE NOT EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = s.sid AND e.cid = k.cid))
UNION ALL
SELECT '∀ enrolments have grade A', group_concat(name, ', ' ORDER BY sid)
FROM student s
WHERE NOT EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = s.sid AND NOT (e.grade = 'A'));

┌───────────────────────────┬──────────────┐
│          formula          │   students   │
├───────────────────────────┼──────────────┤
│ ∃ an A in a MATH course   │ Asha, Chitra │
│ ¬∃ any enrolment          │ Farhan       │
│ ∀ core courses taken      │ Asha, Esha   │
│ ∀ enrolments have grade A │ Farhan       │
└───────────────────────────┴──────────────┘

SQL returns the same students as the comprehensions. The last row is the implication written the SQL way: no enrolment of the student exists whose grade is not A. Because EXISTS only asks whether a row exists, PostgreSQL’s manual describes the subquery as being “evaluated to determine whether it returns any rows”, so what the subquery selects does not matter and SELECT 1 is enough.

Safe and unsafe expressions

The calculus allows formulas that no database could answer from its contents. Take a relation Branch with the codes CSE, ECE and ME, and the query { t | ¬(t ∈ Branch) }: every tuple that is not a branch. Is CIVIL in the answer? Is a string of ten thousand random letters? The formula says yes to both, so the answer depends on the set of values the variables may take, the domain, which the database does not store. Such an expression is unsafe. The program evaluates the unsafe query and a safe version over two domains:

"""An unsafe query depends on the domain its variables range over; a safe one does not."""
from college import Course, Student

branches = {s.branch for s in Student}   # a relation Branch(code): CSE, ECE, ME


def unsafe(domain):
    """{ t | ¬ Branch(t) }: every code of the domain that is not a branch."""
    return sorted(t for t in domain if t not in branches)


def safe(domain):
    """{ t | ∃c ∈ Course (t = c.dept) ∧ ¬ Branch(t) }: t must be a department of some course."""
    return sorted(t for t in domain if any(t == c.dept for c in Course) and t not in branches)


# The active domain: every branch and department code that occurs in the database.
active = branches | {c.dept for c in Course}
# A larger domain: the same codes and two more that occur nowhere in the database.
larger = active | {"CIVIL", "MBA"}

for name, domain in (("active domain", active), ("larger domain", larger)):
    print(f"{name:14} unsafe → {unsafe(domain)}")
    print(f"{'':14} safe   → {safe(domain)}")

active domain  unsafe → ['HSS', 'MATH']
               safe   → ['HSS', 'MATH']
larger domain  unsafe → ['CIVIL', 'HSS', 'MATH', 'MBA']
               safe   → ['HSS', 'MATH']

Over the active domain, the values that occur in the database, the unsafe query returns HSS and MATH. Over a larger domain with two more codes, it also returns CIVIL and MBA, although not a single tuple of the database changed. The safe version requires t to be the department of some course, so its answer is the same for both domains. A query whose answer is the same for every domain that contains the database’s values and the query’s constants is called domain-independent, and safe expressions are the ones built so that this always holds: every value of every variable is taken from a relation the query names, or from one of its constants.

A practical rule follows: tie every variable to a relation with a positive atom before you negate anything. ¬(t ∈ R) on its own is unsafe, but t ∈ S ∧ ¬(t ∈ R) is safe, and it is the difference S − R. Codd’s own calculus ruled such queries out by its syntax: in his 1972 paper, “both bound and free variables must have clearly defined ranges”, and a range cannot be given merely by stating which relation a variable is not in. His range-coupled quantifiers are the ∃e ∈ Enrolled and ∀k ∈ Core of this lesson.

Domain relational calculus

The domain relational calculus uses one variable per attribute value. A query has the form { ⟨x1, …, xn⟩ | P }, and an atom R(x1, …, xn) says that the tuple of those values is in R. The CSE students are { ⟨n⟩ | ∃i ∃b (Student(i, n, b) ∧ b = ‘CSE’) }: some sid i and some branch b exist that make (i, n, b) a student of CSE. Joins appear as shared variables, since the same variable i in Student(i, n, b) and Enrolled(i, c, g) forces the two sids to be equal. Query-by-Example, the table-based query language that M. M. Zloof described in 1977, works the same way: its users write example elements, which play the part of these variables, into the columns of empty tables.

The program below asks one question, the students who took every core course, in four languages: the algebra’s division formula with the candidates taken from Student, the tuple calculus, the domain calculus with every variable ranging over the active domain, and SQL with two NOT EXISTS:

"""One question in four languages: the students who took every core course.

The algebra, the tuple calculus, the domain calculus and SQL must give the same answer (Codd's theorem), also
when the list of core courses is empty.
"""
import sqlite3

from college import Core, Enrolled, Student


def algebra(core):
    # π sid (Student) − π sid ((π sid (Student) × Core) − π sid, cid (Enrolled)), then the names
    candidates = {s.sid for s in Student}
    missing = {(i, k.cid) for i in candidates for k in core} - {(e.sid, e.cid) for e in Enrolled}
    sids = candidates - {i for (i, _) in missing}
    return {s.name for s in Student if s.sid in sids}


def tuple_calculus(core):
    # { s.name | s ∈ Student ∧ ∀k ∈ Core ∃e ∈ Enrolled (e.sid = s.sid ∧ e.cid = k.cid) }
    return {s.name for s in Student if all(any(e.sid == s.sid and e.cid == k.cid for e in Enrolled) for k in core)}


def domain_calculus(core):
    # { ⟨n⟩ | ∃i ∃b (Student(i, n, b) ∧ ∀c (Core(c) ⇒ ∃g Enrolled(i, c, g))) }, every variable over the active domain
    student, enrolled, core_set = set(Student), set(Enrolled), {k.cid for k in core}
    domain = {v for row in Student + Enrolled + list(core) for v in row}
    return {n for n in domain
            if any((i, n, b) in student
                   and all(c not in core_set or any((i, c, g) in enrolled for g in domain) for c in domain)
                   for i in domain for b in domain)}


def sql(core):
    db = sqlite3.connect(":memory:")
    db.execute("CREATE TABLE student (sid INTEGER, name TEXT, branch TEXT)")
    db.execute("CREATE TABLE enrolled (sid INTEGER, cid TEXT, grade TEXT)")
    db.execute("CREATE TABLE core (cid TEXT)")
    db.executemany("INSERT INTO student VALUES (?, ?, ?)", Student)
    db.executemany("INSERT INTO enrolled VALUES (?, ?, ?)", Enrolled)
    db.executemany("INSERT INTO core VALUES (?)", core)
    rows = db.execute("""
        SELECT s.name FROM student s
        WHERE NOT EXISTS (SELECT 1 FROM core k
                          WHERE NOT EXISTS (SELECT 1 FROM enrolled e
                                            WHERE e.sid = s.sid AND e.cid = k.cid))""").fetchall()
    return {name for (name,) in rows}


for label, core in (("three core courses", Core), ("no core courses", [])):
    answers = {f.__name__: f(core) for f in (algebra, tuple_calculus, domain_calculus, sql)}
    print(f"{label}:")
    for name, answer in answers.items():
        print(f"  {name:16} {sorted(answer)}")
    print("  all four agree:", len({frozenset(a) for a in answers.values()}) == 1)

three core courses:
  algebra          ['Asha', 'Esha']
  tuple_calculus   ['Asha', 'Esha']
  domain_calculus  ['Asha', 'Esha']
  sql              ['Asha', 'Esha']
  all four agree: True
no core courses:
  algebra          ['Asha', 'Bilal', 'Chitra', 'Dev', 'Esha', 'Farhan']
  tuple_calculus   ['Asha', 'Bilal', 'Chitra', 'Dev', 'Esha', 'Farhan']
  domain_calculus  ['Asha', 'Bilal', 'Chitra', 'Dev', 'Esha', 'Farhan']
  sql              ['Asha', 'Bilal', 'Chitra', 'Dev', 'Esha', 'Farhan']
  all four agree: True

All four agree, with three core courses and with none. The empty case also shows why the algebra’s version uses π sid (Student) instead of π sid (Enrolled) as its candidates: the calculus query ranges over Student, so the algebra has to as well.

Codd’s theorem

E. F. Codd defined a relational algebra and a relational calculus in his 1972 paper “Relational Completeness of Data Base Sublanguages” and gave an algorithm that translates any expression of the calculus into an equivalent expression of the algebra. Translating the other way is direct, one operator at a time: σ is a condition, × introduces a second variable, ∪ is ∨, − is ∧ ¬, π is ∃ over the dropped attributes. Together the two directions are known as Codd’s theorem: relational algebra, safe tuple relational calculus and safe domain relational calculus have exactly the same expressive power.

Codd turned the result into a yardstick: he called a query language relationally complete if it can express every query of the relational calculus. SQL is, since every operator of the algebra has a direct SQL form, and it goes further with bags, NULL, aggregates and, through recursive queries, transitive closure, which neither the algebra nor the calculus can express. The two kinds of language also play different roles. The calculus states what the answer is, the way an SQL query does; the algebra states how to compute it, the way a query plan does, and a database’s work between the two is the subject of the query-processing module of this track.

Exercise

"""Write each tuple-calculus query as a Python set comprehension: any(...) for ∃ and all(...) for ∀.

student, course and enrolled are lists of named tuples with the lesson's attributes: s.sid, s.name and s.branch;
c.cid, c.title, c.dept and c.credits; e.sid, e.cid and e.grade. Return a set of names, or of course ids.
"""


def took_some_ece_course(student, course, enrolled):
    """{ s.name | s ∈ Student ∧ ∃e ∈ Enrolled ∃c ∈ Course (e.sid = s.sid ∧ e.cid = c.cid ∧ c.dept = 'ECE') }"""
    return set()


def only_a_grades(student, course, enrolled):
    """{ s.name | s ∈ Student ∧ ∀e ∈ Enrolled (e.sid = s.sid ⇒ e.grade = 'A') }"""
    return set()


def taken_by_every_cse_student(student, course, enrolled):
    """{ c.cid | c ∈ Course ∧ ∀s ∈ Student (s.branch = 'CSE' ⇒ ∃e ∈ Enrolled (e.sid = s.sid ∧ e.cid = c.cid)) }"""
    return set()

from collections import namedtuple

from quantifiers import only_a_grades, taken_by_every_cse_student, took_some_ece_course

S = namedtuple("Student", "sid name branch")
C = namedtuple("Course", "cid title dept credits")
E = namedtuple("Enrolled", "sid cid grade")


def college():
    """The sample relations of the lesson."""
    student = [S(1, "Asha", "CSE"), S(2, "Bilal", "ECE"), S(3, "Chitra", "CSE"),
               S(4, "Dev", "ME"), S(5, "Esha", "CSE"), S(6, "Farhan", "ECE")]
    course = [C("CS201", "Databases", "CSE", 4), C("CS202", "Operating Systems", "CSE", 4),
              C("CS301", "Compilers", "CSE", 4), C("MA101", "Discrete Mathematics", "MATH", 3),
              C("EC210", "Signals and Systems", "ECE", 3), C("HS101", "Technical Writing", "HSS", 2)]
    enrolled = [E(1, "CS201", "A"), E(1, "CS202", "B"), E(1, "MA101", "A"), E(2, "EC210", "A"),
                E(2, "MA101", "B"), E(3, "CS201", "B"), E(3, "MA101", "A"), E(4, "MA101", "C"),
                E(5, "CS201", "A"), E(5, "CS202", "A"), E(5, "MA101", "B"), E(5, "HS101", "A")]
    return student, course, enrolled


def other_college():
    """Different data: two CSE students who share one course, and a second ECE course."""
    student = [S(10, "Ravi", "ECE"), S(11, "Meena", "CSE"), S(12, "Kiran", "CSE"), S(13, "Lata", "ME")]
    course = [C("CS201", "Databases", "CSE", 4), C("EC220", "Circuits", "ECE", 4),
              C("MA101", "Discrete Mathematics", "MATH", 3)]
    enrolled = [E(10, "EC220", "A"), E(11, "CS201", "A"), E(11, "MA101", "A"),
                E(12, "CS201", "B"), E(12, "EC220", "A"), E(13, "MA101", "A")]
    return student, course, enrolled


def test_took_some_ece_course():
    """∃: the students with an enrolment in an ECE course"""
    assert took_some_ece_course(*college()) == {"Bilal"}
    assert took_some_ece_course(*other_college()) == {"Ravi", "Kiran"}


def test_only_a_grades():
    """∀ with ⇒: only A grades, which is also true of a student with no enrolments"""
    assert only_a_grades(*college()) == {"Farhan"}
    assert only_a_grades(*other_college()) == {"Ravi", "Meena", "Lata"}


def test_taken_by_every_cse_student():
    """∀ over students: the courses that every CSE student took"""
    assert taken_by_every_cse_student(*college()) == {"CS201", "MA101"}
    assert taken_by_every_cse_student(*other_college()) == {"CS201"}


def test_no_cse_students():
    """with no CSE students, the universal condition holds for every course"""
    student, course, enrolled = college()
    others = [s for s in student if s.branch != "CSE"]
    assert taken_by_every_cse_student(others, course, enrolled) == {c.cid for c in course}

Check yourself

Interview questions

What makes a tuple relational calculus expression unsafe? Its answer depends on the domain, the set of values the variables may take, and not only on the data. { t | ¬(t ∈ R) } returns every tuple outside R, which grows with the domain and is infinite over an infinite one. A safe expression takes every value of every variable from the relations it names or from its own constants, so it gives the same finite answer over any domain that contains them. For example, t ∈ S ∧ ¬(t ∈ R) is safe: it is S − R.

Key takeaways

• A tuple-calculus query { t | P(t) } returns the tuples that make P true; ∃ and ∀ bind further variables, each over a relation.
• ∃ corresponds to a join or semijoin, ¬∃ to an antijoin, and ∀ … ∃ to division.
• P ⇒ Q is ¬P ∨ Q, and ∀x F is ¬∃x ¬F, which is how SQL writes “for all”: NOT EXISTS … WHERE NOT.
• A ∀ over an empty range is true, so a student with no enrolments has “only A grades”.
• An unsafe query such as { t | ¬(t ∈ R) } depends on the domain; safe queries take every value from the database or the query’s constants.
• Domain calculus uses one variable per value and expresses joins through shared variables.
• Codd’s theorem: relational algebra, safe tuple calculus and safe domain calculus express the same queries.