Relational Algebra & Calculus

Syllabus tag: Paper-II, Section-B, Topic IV.3 (part 2) — Relational Algebra & Calculus

Definition

Relational Algebra is a procedural query language — a query is a sequence of operations that specify how to compute the result. Relational Calculus is a declarative/non-procedural language — a query specifies what result is wanted (like SQL), letting the system determine how.

Relational Algebra Operators

• Selection and Projection are unary (one input relation); Union, Intersection, Difference, Product, and Join are binary.
• Union, Intersection, and Difference require the two relations to be union-compatible (same degree, matching domains).

Numerical — Worked Relational Algebra Query (FPSC 2021, Q6(a) style)

Schema: Student(Stu_Reg, Stu_Name, Stu_Address), Instructor(Ins_ID, Ins_Name, Ins_Dept_ID), Course(Cr_Code, Cr_Title, Cr_CreditHrs), Enrolled(Stu_Reg, Cr_Code)

• Query: "Find the names of students enrolled in the course titled 'Database Systems'."

π_Stu_Name ( Student ⋈ ( σ_Cr_Title='Database Systems' (Course) ⋈ Enrolled ) )

• Read inside-out: first select the target course row, natural-join it to Enrolled to get the registered students, natural-join that to Student to pull names, then project just Stu_Name.

Relational Calculus

• Tuple Relational Calculus (TRC): { t | P(t) } — t ranges over tuples; P(t) is a predicate t must satisfy.

  Example: { t | t ∈ Student ∧ t.Address = 'Lahore' }

• Domain Relational Calculus (DRC): variables range over individual domain values (attribute values), not whole tuples.

  Example: { <n> | ∃ r (⟨r, n, 'Lahore'⟩ ∈ Student) }

• Both TRC and DRC are declarative and, under safety restrictions, equivalent in expressive power to relational algebra (Codd's theorem).

MCQ Trap

• Relational Algebra is procedural (how); Relational Calculus is declarative (what) — same expressive power, different style.
• Natural Join automatically equates and removes duplicate common-name columns; a Theta Join with = on those same columns (an equijoin) keeps both columns.
• Division (÷) is the operator behind "find X related to ALL Y" queries — frequently tested conceptually even without full computation.

CSS Exam Angle

• FPSC likes giving a schema and asking for the algebra expression for a specific English query (2021) — practice translating English → algebra directly, in both directions.
• Always state clearly which operators are unary vs binary and which require union-compatibility — a common short-note question.

Likely Questions

1. List the basic relational algebra operators with their symbols and one-line meaning each.
2. Differentiate relational algebra and relational calculus by procedurality and give one example of each.
3. Given a schema, write the relational algebra expression for a stated English-language query.
4. Explain the Division operator with an example of the kind of query it answers.
5. Differentiate a Theta Join, Equijoin, and Natural Join.

---

📘 Enrichment — Operators Evaluated on Real Data

Sample instances (use these for every operator):

Student

Enrolled

Course

Worked Example — Division Step by Step

Query: "Find students enrolled in all courses." → Enrolled ÷ π Code (Course)

• Divisor = {C1, C2}. A Reg qualifies only if it is paired with both C1 and C2.
• S1 has C1 and C2 ✅ · S2 has only C1 ❌ · S3 has only C2 ❌ → Result: S1 (Ali).

Division rewritten with basic operators (frequently asked — proves division is not a primitive):

1. T1 = π Reg (Enrolled) = {S1, S2, S3}
2. T2 = T1 × π Code (Course) = every possible (Reg, Code) pair = 6 pairs
3. T3 = T2 − Enrolled = pairs that should exist but don't = {(S2, C2), (S3, C1)}
4. T4 = π Reg (T3) = students missing at least one course = {S2, S3}
5. Result = T1 − T4 = {S1} ✅

Worked Example — Query Tree for an Algebra Expression

π Name ( σ Title='DBMS' (Course) ⋈ Enrolled ⋈ Student )

flowchart BT
    C["Course"] --> S1["σ Title='DBMS'"]
    S1 --> J1["⋈ on Code"]
    E["Enrolled"] --> J1
    J1 --> J2["⋈ on Reg"]
    ST["Student"] --> J2
    J2 --> P["π Name"]

Evaluation bottom-up: σ gives (C1, DBMS) → join with Enrolled gives S1, S2 → join with Student → π Name = Ali, Sara.

Same Query in All Three Languages

Query: "Names of students from Lahore enrolled in C2."

• Relational algebra: π Name (σ City='Lahore' ∧ Code='C2' (Student ⋈ Enrolled))
• Tuple relational calculus: { s.Name | Student(s) ∧ s.City='Lahore' ∧ ∃e (Enrolled(e) ∧ e.Reg=s.Reg ∧ e.Code='C2') }
• Domain relational calculus: { ⟨n⟩ | ∃r ( ⟨r, n, 'Lahore'⟩ ∈ Student ∧ ⟨r, 'C2'⟩ ∈ Enrolled ) }
• SQL: SELECT s.Name FROM Student s JOIN Enrolled e ON s.Reg=e.Reg WHERE s.City='Lahore' AND e.Code='C2';
• Answer on the sample data: Ali, Omar.

Safe vs Unsafe Calculus Expressions

• { t | ¬ Student(t) } is unsafe — it describes every tuple in the universe that is not a student (infinite result).
• A safe expression only produces values that appear in the database (its "domain") — only safe calculus is equivalent to relational algebra.

Extended Operators (bonus marks)

• Outer joins: left ⟕, right ⟖, full ⟗ — keep unmatched tuples padded with NULL.
• Aggregation / grouping: City 𝒢 COUNT(Reg) (Student) → Lahore 2, Karachi 1.
• Assignment ← to store intermediate results: Temp ← σ City='Lahore' (Student).

---

✍️ Model Answers — Likely Questions

Q1. List the basic relational algebra operators with symbols and meanings.

• Fundamental (6): Selection σ (rows), Projection π (columns), Union ∪, Set difference −, Cartesian product ×, Rename ρ.
• Derived (expressible via the fundamental ones): Intersection ∩ (= R − (R − S)), Join ⋈ (= σ over ×), Division ÷, Assignment ←.
• Unary: σ, π, ρ. Binary: ∪, −, ×, ∩, ⋈, ÷.
• ∪, ∩, − require union compatibility.

Illustrate two or three operators using the result table above (e.g., σ City='Lahore' → Ali, Omar).

Q2. Differentiate relational algebra and relational calculus with examples.

Conclusion: by Codd's theorem, algebra and safe calculus are equally expressive (relationally complete); SQL borrows calculus's declarative style, while the optimizer internally uses algebra.

Q3. Given a schema, write the algebra expression for an English query.

Method in four steps: (1) identify tables needed; (2) apply σ as early as possible; (3) join on shared keys; (4) π the requested columns last.

Example: "Titles of courses taken by Ali" → π Title ( σ Name='Ali' (Student) ⋈ Enrolled ⋈ Course ) → DBMS, OS.

Draw the query tree to earn diagram marks.

Q4. Explain the Division operator with an example.

R ÷ S returns the values of R's extra attributes that are associated with every tuple of S — the algebra answer to "for all" queries. Use the Enrolled ÷ π Code(Course) = {S1} worked example above and show the 5-step rewrite using π, ×, − to earn full marks. Real-life examples: "suppliers who supply all parts", "customers who bought every product in a category".

Q5. Differentiate theta join, equijoin and natural join.

• Theta join R ⋈θ S: any comparison condition (<, >, ≠, =), e.g. join Employee and SalaryGrade on Salary BETWEEN Low AND High.
• Equijoin: a theta join using only =; both join columns appear in the result.
• Natural join: equijoin on all same-named attributes, with duplicate columns removed automatically.

Example: Student ⋈ Enrolled natural join has 4 columns (Reg once); the equijoin on Student.Reg = Enrolled.Reg has 5 columns (Reg twice).

---

⚡ 60-Second Revision

• Six fundamental: σ π ∪ − × ρ. Everything else is derived.
• π removes duplicates (set semantics); SQL SELECT does not unless DISTINCT.
• Division = "for all"; rewrite: π(R) − π((π(R) × S) − R).
• Algebra = procedural; Calculus (TRC/DRC) = declarative; equal power when safe.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2018 · Paper-II · Q5(A) · 8 marks

Q. Relations R (M tuples) and S (N tuples), with M > N > 0. Give the minimum and maximum possible sizes of: (i) R − S (ii) R ∪ S (iii) R ∩ S (iv) R ⋈ S.

Ans. (R and S are union-compatible for (i)–(iii).)

2021 · Paper-II · Q6(a) · 8 marks

Q. Schema: Students(Stu_Reg, Stu_Name, Stu_Address), Instructor(Ins_ID, Ins_Name, Ins_Dept_ID), Course(Cr_Code, Cr_Title, Cr_CrHours), Dept(Dept_ID, Dept_Name), Results(Res_Stu_Reg, Res_Cr_Code, Res_Marks, Res_Ins_ID, Res_Grade). Write relational algebra for: (i) all student details in section BSSE (ii) all instructor names and their department names (instructors with no department still shown) (iii) Stu_Reg, Stu_Name, Cr_Code, Cr_Title, Res_Marks for students with 75 or more marks (iv) Res_Stu_Reg, Ins_Name, Res_Grade for instructors whose Dept_ID is 1.

Ans. (σ = selection, π = projection, ⋈ = join, ⟕ = left outer join.)

• (i) σ Stu_Reg LIKE '%BSSE%' (Students) (the schema has no section column, so the section is read from the registration number)
• (ii) π Ins_Name, Dept_Name ( Instructor ⟕ Ins_Dept_ID = Dept_ID Dept )
• (iii) π Stu_Reg, Stu_Name, Cr_Code, Cr_Title, Res_Marks ( σ Res_Marks ≥ 75 ( Students ⋈ Stu_Reg = Res_Stu_Reg Results ⋈ Res_Cr_Code = Cr_Code Course ) )
• (iv) π Res_Stu_Reg, Ins_Name, Res_Grade ( σ Ins_Dept_ID = 1 ( Instructor ⋈ Ins_ID = Res_Ins_ID Results ) )