Skip to main content

Relational Algebra and Calculus: Examples

Relations and notation

The examples use:

  • Student(student_id, name)
  • Enrollment(student_id, course_id, grade)
  • Course(course_id, title)
  • RequiredCourse(course_id)

Each example starts with SQL, then shows the equivalent RA, TRC, and DRC query. RA builds results with operators; TRC uses tuple variables, while DRC uses value variables.

Selection and projection

Find the course IDs for enrollments with an A grade.

SELECT DISTINCT course_id
FROM Enrollment
WHERE grade = 'A';
Language Query
RA \(\pi_{course\_id}(\sigma_{grade='A'}(Enrollment))\)
TRC \(\{t \mid \exists e\in Enrollment\ (t[course\_id]=e[course\_id]\land e[grade]='A')\}\)
DRC \(\{\langle cid\rangle \mid \exists sid,g\ (\langle sid,cid,g\rangle\in Enrollment\land g='A')\}\)

Translate: selection becomes a predicate; projection becomes the output attributes. In DRC, list relation values in schema order: student_id, course_id, grade.

Join and filter

Find students who received an A in DBMS.

SELECT DISTINCT s.name
FROM Student AS s
JOIN Enrollment AS e ON e.student_id = s.student_id
JOIN Course AS c ON c.course_id = e.course_id
WHERE c.title = 'DBMS' AND e.grade = 'A';
Language Query
RA \(\pi_{name}(\sigma_{title='DBMS'\land grade='A'}(Student\bowtie Enrollment\bowtie Course))\)
TRC \(\{t \mid \exists s\in Student\ \exists e\in Enrollment\ \exists c\in Course\ (t[name]=s[name]\land s[student\_id]=e[student\_id]\land e[course\_id]=c[course\_id]\land c[title]='DBMS'\land e[grade]='A')\}\)
DRC \(\{\langle n\rangle \mid \exists sid,cid,g,title\ (\langle sid,n\rangle\in Student\land\langle sid,cid,g\rangle\in Enrollment\land\langle cid,title\rangle\in Course\land title='DBMS'\land g='A')\}\)

The joins match the shared IDs. The calculus equality predicates express those same join conditions.

Alternative conditions

Find students who received an A or S in DBMS.

SELECT DISTINCT s.name
FROM Student AS s
JOIN Enrollment AS e ON e.student_id = s.student_id
JOIN Course AS c ON c.course_id = e.course_id
WHERE c.title = 'DBMS' AND e.grade IN ('A', 'S');
Language Query
RA \(\pi_{name}(\sigma_{title='DBMS'\land(grade='A'\lor grade='S')}(Student\bowtie Enrollment\bowtie Course))\)
TRC \(\{t \mid \exists s\in Student\ \exists e\in Enrollment\ \exists c\in Course\ (t[name]=s[name]\land s[student\_id]=e[student\_id]\land e[course\_id]=c[course\_id]\land c[title]='DBMS'\land(e[grade]='A'\lor e[grade]='S'))\}\)
DRC \(\{\langle n\rangle \mid \exists sid,cid,g,title\ (\langle sid,n\rangle\in Student\land\langle sid,cid,g\rangle\in Enrollment\land\langle cid,title\rangle\in Course\land title='DBMS'\land(g='A'\lor g='S'))\}\)

OR in a selection becomes \(\lor\) in the calculus predicate.

Union

Find student IDs enrolled in DBMS or Math.

SELECT e.student_id
FROM Enrollment AS e
JOIN Course AS c ON c.course_id = e.course_id
WHERE c.title = 'DBMS'
UNION
SELECT e.student_id
FROM Enrollment AS e
JOIN Course AS c ON c.course_id = e.course_id
WHERE c.title = 'Math';
Language Query
RA \(\pi_{student\_id}(Enrollment\bowtie\sigma_{title='DBMS'}(Course))\cup\pi_{student\_id}(Enrollment\bowtie\sigma_{title='Math'}(Course))\)
TRC \(\{t \mid \exists e\in Enrollment\ \exists c\in Course\ (t[student\_id]=e[student\_id]\land e[course\_id]=c[course\_id]\land(c[title]='DBMS'\lor c[title]='Math'))\}\)
DRC \(\{\langle sid\rangle \mid \exists cid,g,title\ (\langle sid,cid,g\rangle\in Enrollment\land\langle cid,title\rangle\in Course\land(title='DBMS'\lor title='Math'))\}\)

UNION removes duplicates, matching the set results of RA and calculus.

Intersection

Find students enrolled in both DBMS and Math.

SELECT e.student_id
FROM Enrollment AS e
JOIN Course AS c ON c.course_id = e.course_id
WHERE c.title = 'DBMS'
INTERSECT
SELECT e.student_id
FROM Enrollment AS e
JOIN Course AS c ON c.course_id = e.course_id
WHERE c.title = 'Math';
Language Query
RA \(\pi_{student\_id}(Enrollment\bowtie\sigma_{title='DBMS'}(Course))\cap\pi_{student\_id}(Enrollment\bowtie\sigma_{title='Math'}(Course))\)
TRC \(\{t \mid \exists e_1\in Enrollment\ \exists c_1\in Course\ \exists e_2\in Enrollment\ \exists c_2\in Course\ (t[student\_id]=e_1[student\_id]\land e_1[student\_id]=e_2[student\_id]\land e_1[course\_id]=c_1[course\_id]\land e_2[course\_id]=c_2[course\_id]\land c_1[title]='DBMS'\land c_2[title]='Math')\}\)
DRC \(\{\langle sid\rangle \mid \exists cid_1,g_1,title_1,cid_2,g_2,title_2\ (\langle sid,cid_1,g_1\rangle\in Enrollment\land\langle cid_1,title_1\rangle\in Course\land title_1='DBMS'\land\langle sid,cid_2,g_2\rangle\in Enrollment\land\langle cid_2,title_2\rangle\in Course\land title_2='Math')\}\)

The two outputs are union-compatible: each contains student IDs. Intersection returns IDs present in both.

Existential quantification

Find students with at least one enrollment.

SELECT s.student_id, s.name
FROM Student AS s
WHERE EXISTS (
  SELECT 1
  FROM Enrollment AS e
  WHERE e.student_id = s.student_id
);
Language Query
RA \(\pi_{student\_id,name}(Student\bowtie Enrollment)\)
TRC \(\{t \mid \exists s\in Student\ (t[student\_id]=s[student\_id]\land t[name]=s[name]\land\exists e\in Enrollment\ (e[student\_id]=s[student\_id]))\}\)
DRC \(\{\langle sid,n\rangle \mid \langle sid,n\rangle\in Student\land\exists cid,g\ (\langle sid,cid,g\rangle\in Enrollment)\}\)

The enrollment tuple and its course_id and grade values are witnesses: they must exist, but are not part of the output.

Comparisons

Find students with a DBMS enrollment whose grade is not C.

SELECT DISTINCT s.student_id, s.name
FROM Student AS s
JOIN Enrollment AS e ON e.student_id = s.student_id
JOIN Course AS c ON c.course_id = e.course_id
WHERE c.title = 'DBMS' AND e.grade <> 'C';
Language Query
RA \(\pi_{student\_id,name}(\sigma_{title='DBMS'\land grade\ne 'C'}(Student\bowtie Enrollment\bowtie Course))\)
TRC \(\{t \mid \exists s\in Student\ (t[student\_id]=s[student\_id]\land t[name]=s[name]\land\exists e\in Enrollment\ \exists c\in Course\ (e[student\_id]=s[student\_id]\land e[course\_id]=c[course\_id]\land c[title]='DBMS'\land e[grade]\ne 'C'))\}\)
DRC \(\{\langle sid,n\rangle \mid \langle sid,n\rangle\in Student\land\exists cid,g,title\ (\langle sid,cid,g\rangle\in Enrollment\land\langle cid,title\rangle\in Course\land title='DBMS'\land g\ne 'C')\}\)

Comparisons such as \(=\) and \(\ne\) are predicates in both calculi. As in SQL, this classical example does not model NULL.

Set difference and negation

Find students enrolled in DBMS but not Math.

SELECT DISTINCT s.student_id, s.name
FROM Student AS s
WHERE EXISTS (
  SELECT 1
  FROM Enrollment AS e
  JOIN Course AS c ON c.course_id = e.course_id
  WHERE e.student_id = s.student_id AND c.title = 'DBMS'
)
AND NOT EXISTS (
  SELECT 1
  FROM Enrollment AS e
  JOIN Course AS c ON c.course_id = e.course_id
  WHERE e.student_id = s.student_id AND c.title = 'Math'
);
Language Query
RA \(\pi_{student\_id,name}(Student\bowtie Enrollment\bowtie\sigma_{title='DBMS'}(Course))-\pi_{student\_id,name}(Student\bowtie Enrollment\bowtie\sigma_{title='Math'}(Course))\)
TRC \(\{t \mid \exists s\in Student\ (t[student\_id]=s[student\_id]\land t[name]=s[name]\land\exists e\in Enrollment\ \exists c\in Course\ (e[student\_id]=s[student\_id]\land e[course\_id]=c[course\_id]\land c[title]='DBMS')\land\neg\exists e_2\in Enrollment\ \exists c_2\in Course\ (e_2[student\_id]=s[student\_id]\land e_2[course\_id]=c_2[course\_id]\land c_2[title]='Math'))\}\)
DRC \(\{\langle sid,n\rangle \mid \langle sid,n\rangle\in Student\land\exists cid,g,title\ (\langle sid,cid,g\rangle\in Enrollment\land\langle cid,title\rangle\in Course\land title='DBMS')\land\neg\exists cid_2,g_2,title_2\ (\langle sid,cid_2,g_2\rangle\in Enrollment\land\langle cid_2,title_2\rangle\in Course\land title_2='Math')\}\)

RA subtracts the matching student rows. TRC and DRC express the same exclusion with NOT EXISTS, written as \(\neg\exists\).

Division and “every”

Assume RequiredCourse is nonempty and lists the courses students must take. Find students enrolled in every required course.

SELECT s.student_id, s.name
FROM Student AS s
WHERE NOT EXISTS (
  SELECT 1
  FROM RequiredCourse AS r
  WHERE NOT EXISTS (
    SELECT 1
    FROM Enrollment AS e
    WHERE e.student_id = s.student_id
      AND e.course_id = r.course_id
  )
);
Language Query
RA \(\pi_{student\_id,name}(Student\bowtie(\pi_{student\_id,course\_id}(Enrollment)\div RequiredCourse))\)
TRC \(\{t \mid \exists s\in Student\ (t[student\_id]=s[student\_id]\land t[name]=s[name]\land\forall r\in RequiredCourse\ \exists e\in Enrollment\ (e[student\_id]=s[student\_id]\land e[course\_id]=r[course\_id]))\}\)
DRC \(\{\langle sid,n\rangle \mid \langle sid,n\rangle\in Student\land\forall rc\ (\langle rc\rangle\in RequiredCourse\rightarrow\exists cid,g\ (\langle sid,cid,g\rangle\in Enrollment\land cid=rc))\}\)

Division in RA corresponds to universal quantification: “for every required course, an enrollment exists.” The DRC implication excludes values outside RequiredCourse; equivalently, there must be no required course without an enrollment.

Translation guide

Query idea SQL Relational algebra TRC / DRC
Keep rows matching a condition WHERE Selection \(\sigma\) Add a predicate
Return selected columns SELECT Projection \(\pi\) Put output attributes in the result tuple
Match related rows JOIN ... ON Join \(\bowtie\) Use relation variables and equalities
Either condition OR or IN Selection with \(\lor\) Use \(\lor\)
Exclude matching rows NOT EXISTS or EXCEPT Difference \(-\) Use \(\neg\) or \(\neg\exists\)
There is a matching row EXISTS Join or projection Use \(\exists\)
Every required value has a match Nested NOT EXISTS Division \(\div\) Use \(\forall\); guard with implication \(\rightarrow\)

In TRC, output components are attributes of tuple variables. In DRC, output variables are the free variables. Quantify the other variables, and ensure every output is restricted to values from a relation; this keeps the query safe.