Relational model: relational algebra, tuple calculus, SQL

Relations, tuples, attributes, and domains

Definition. A relation is a set of tuples over named attributes, each with a domain. The relational model is set-based: duplicate tuples are not distinct relation members. A relation schema names attributes; an instance is the current set of rows.

Example. Student(Sid,Name,Dept) describes student rows with an identifier, name, and department.

Exam point. SQL tables usually allow duplicates unless constrained, so SQL bag behavior differs from classical relational algebra.

Use the following small instance throughout:

Student

Sid	Name	Dept
1	Ana	CS
2	Bo	EE
3	Cy	CS

Course

Cid	Title
10	DB
20	OS

Enroll

Sid	Cid	Grade
1	10	A
1	20	B
2	10	A
3	10	B

Selection and projection

Definition. Selection σ_condition(R) retains tuples satisfying a predicate. Projection π_attributes(R) keeps specified columns and removes duplicate tuples under classical set semantics. Selection is analogous to row filtering; projection is column selection.

Example. σ_Dept='CS'(Student) returns Ana and Cy.

Exam point. Projection can reduce cardinality because duplicate projected tuples collapse in relational algebra.

Solved examples

Example 1 — selection. Find CS students.

1. Evaluate Dept='CS' for each Student row.
2. Rows 1 and 3 satisfy it; row 2 does not.
3. RA: σ_{Dept='CS'}(Student).
4. SQL: SELECT * FROM Student WHERE Dept='CS';
5. Tuple calculus: {s | Student(s) ∧ s.Dept='CS'}.
6. Result: (1,Ana,CS), (3,Cy,CS).

Example 2 — projection. Find the set of departments.

1. Keep only Dept: CS, EE, CS.
2. Classical projection removes duplicate CS.
3. RA: π_{Dept}(Student).
4. SQL: SELECT DISTINCT Dept FROM Student;
5. Tuple calculus: {⟨s.Dept⟩ | Student(s)}.
6. Result: {CS,EE}.

Relational algebra operators and composition

Definition. Relational algebra is a procedural query language whose operators take relations and return relations. Operators can be composed; parentheses determine evaluation order, though algebraic equivalences permit reordering under set semantics.

Example. π_Name(σ_Dept='CS'(Student)) first filters CS rows, then returns names.

Exam point. Selection and projection commute only under compatible attribute conditions; projection must retain attributes needed by later predicates or joins.

Solved examples

Example — push projection safely. Find names of CS students.

1. Filter Student by Dept='CS'.
2. Project Name after selection.
3. RA: π_Name(σ_{Dept='CS'}(Student)).
4. SQL: SELECT Name FROM Student WHERE Dept='CS';
5. Calculus: {⟨s.Name⟩ | Student(s) ∧ s.Dept='CS'}.
6. Result: Ana, Cy. Dept is needed to filter, even though it is not output.

Union, intersection, and difference

Definition. Set operations require union-compatible relations: same number of attributes with corresponding domains compatible. Union contains tuples in either input; intersection contains tuples in both; difference contains tuples in the left but not right relation.

Example. π_Sid(Enroll) gives enrolled IDs; subtract it from all student IDs to find students with no enrollment.

Exam point. SQL UNION removes duplicates by default; UNION ALL preserves them.

Solved examples

Example 1 — difference. Find students with no enrollment.

1. All IDs are {1,2,3}.
2. Enroll IDs projected are {1,2,3}.
3. RA: π_Sid(Student) − π_Sid(Enroll) = ∅.
4. SQL: SELECT Sid FROM Student EXCEPT SELECT Sid FROM Enroll;
5. Tuple calculus: {s.Sid | Student(s) ∧ ¬∃e(Enroll(e) ∧ e.Sid=s.Sid)}.
6. No student is unenrolled in this instance.

Example 2 — union. Find IDs enrolled in course 10 or course 20.

1. Select Cid=10 and project Sid: {1,2,3}.
2. Select Cid=20 and project Sid: {1}.
3. Union gives {1,2,3}.
4. RA: π_Sid(σ_{Cid=10}(Enroll)) ∪ π_Sid(σ_{Cid=20}(Enroll)).
5. SQL can use WHERE Cid IN (10,20); calculus uses existential quantification over Enroll.

Cartesian product and joins

Definition. Cartesian product pairs every tuple from R with every tuple from S. A theta join selects product pairs satisfying a condition; an equijoin uses equality; a natural join matches same-named attributes and returns one copy of each matched attribute. Outer joins preserve unmatched tuples with nulls.

Example. Student ⋈_{Student.Sid=Enroll.Sid} Enroll associates each enrollment with a student.

Exam point. Natural join can accidentally match same-named columns that were not intended as a join key.

Solved examples

Example 1 — equijoin. Return student names and course IDs.

1. Match Student.Sid to Enroll.Sid.
2. Four enrollment rows match: Ana with 10 and 20, Bo with 10, Cy with 10.
3. RA: π_{Name,Cid}(Student ⋈_{Student.Sid=Enroll.Sid} Enroll).
4. SQL: SELECT S.Name,E.Cid FROM Student S JOIN Enroll E ON S.Sid=E.Sid;
5. Tuple calculus: {⟨s.Name,e.Cid⟩ | Student(s)∧Enroll(e)∧s.Sid=e.Sid}.
6. Result rows: (Ana,10),(Ana,20),(Bo,10),(Cy,10).

Example 2 — join then filter. Find CS students enrolled in DB (Cid 10).

1. Join Student and Enroll by Sid.
2. Keep Dept=CS and Cid=10.
3. RA: π_Name(σ_{Dept='CS'∧Cid=10}(Student ⋈ Enroll)).
4. SQL: SELECT DISTINCT S.Name FROM Student S JOIN Enroll E ON S.Sid=E.Sid WHERE S.Dept='CS' AND E.Cid=10;
5. Calculus: {⟨s.Name⟩ | Student(s)∧Enroll(e)∧s.Sid=e.Sid∧s.Dept='CS'∧e.Cid=10}.
6. Result: Ana, Cy.

Division and “for all” queries

Definition. Division R(X,Y)÷S(Y) returns X-values paired in R with every Y-value in S. It expresses universal requirements such as “students enrolled in all required courses.” If S is empty, classical division returns every X in the active domain of R's X attributes under the formal definition.

Example. Enroll(Sid,Cid) ÷ Required(Cid) finds students enrolled in every required course.

Exam point. Verify the divisor includes only the required set; extra enrollments do not hurt.

Solved examples

Example — students in every listed course. Required Cids are {10,20}; Enroll pairs are (1,10),(1,20),(2,10),(3,10).

1. Student 1 has both 10 and 20.
2. Students 2 and 3 have only 10.
3. π_{Sid,Cid}(Enroll) ÷ Required(Cid) returns {1}.
4. SQL: SELECT E.Sid FROM Enroll E JOIN Required R ON R.Cid=E.Cid GROUP BY E.Sid HAVING COUNT(DISTINCT E.Cid)=(SELECT COUNT(*) FROM Required);
5. Tuple calculus: {⟨s.Sid⟩ | Student(s) ∧ ∀r(Required(r)→∃e(Enroll(e)∧e.Sid=s.Sid∧e.Cid=r.Cid))}.
6. Result: Sid 1.

Tuple relational calculus

Definition. Tuple calculus is declarative: a query specifies conditions a tuple must satisfy. A formula uses relation predicates, comparisons, logical connectives, and quantifiers. Safe-range calculus restricts outputs to values from the database domain, avoiding infinite answers.

Example. {s | Student(s) ∧ s.Dept='CS'} returns tuples in Student whose department is CS.

Exam point. Bound variables are quantified; free variables determine output values.

Solved examples

Example 1 — existential query. Find students with at least one enrollment in course 20.

1. Require Student(s).
2. Require there exists e with Enroll(e), same Sid, and Cid=20.
3. Formula: {⟨s.Name⟩ | Student(s)∧∃e(Enroll(e)∧e.Sid=s.Sid∧e.Cid=20)}.
4. SQL: SELECT DISTINCT S.Name FROM Student S WHERE EXISTS (SELECT 1 FROM Enroll E WHERE E.Sid=S.Sid AND E.Cid=20);
5. Result: Ana.

Example 2 — universal query via negation. Find students enrolled in every course.

1. Express no course exists for which the student lacks an enrollment.
2. Formula: {⟨s.Sid⟩ | Student(s)∧¬∃c(Course(c)∧¬∃e(Enroll(e)∧e.Sid=s.Sid∧e.Cid=c.Cid))}.
3. SQL can use double NOT EXISTS.
4. This is equivalent to a “for all courses, an enrollment exists” condition.

SQL selection, joins, and NULL

Definition. SQL SELECT-FROM-WHERE queries retrieve columns from table expressions and filter rows. SQL uses three-valued logic: comparisons with NULL usually yield UNKNOWN; WHERE retains only TRUE. IS NULL tests nullness explicitly.