Relational Algebra in DBMS: Operators and Examples | Part 4

DBMS Part 4: relational algebra ko tables se seekho. Part 3 mein SQL se rows nikale. Relational algebra query ki formal, operator-based language hai: ek relation input, doosra relation output. Yeh examples set semantics use karte hain, yani duplicate tuples nahi. SQL usually duplicates allow karta hai unless DISTINCT, aur NULL ka behavior bhi alag hota hai.

1. Relational algebra: definition aur notation

Definition: Relational algebra relational data par operators ka collection hai, jisme har operator ek ya zyada relations par kaam karke naya relation deta hai. Is closure property se operators chain kar sakte hain. Core operators selection (σ), projection (π), Cartesian product (×), union (∪), set difference (−) aur rename (ρ) hain; joins derived operations hain.

Dataset: Students(id,name,sem) = (101,Asha,3), (102,Ravi,3), (103,Meera,5). Enrollment(student_id,course_id) = (101,10), (101,20), (102,10). Courses(course_id,title) = (10,DBMS), (20,OS). Har example mein result ko isi dataset par calculate karenge.

2. Selection σ rows filter karta hai

Definition: σ_condition(R) mein R ki wohi rows rehti hain jo condition satisfy karti hain; columns same rehte hain. Example: σ_sem=3(Students) = (101,Asha,3), (102,Ravi,3). SQL equivalent SELECT * FROM Students WHERE sem = 3. Selection ko SQL SELECT se confuse mat karo: algebra ka σ row filter hai, jabki SQL SELECT poori query clause hai.

3. Projection π columns choose karta hai

Definition: π_columns(R) sirf named columns rakhta hai. Classical set algebra duplicate result rows hata deta hai. Example: π_sem(Students) = {(3),(5)}, (3) do baar nahi. SQL equivalent SELECT DISTINCT sem FROM Students; plain SQL SELECT sem mein 3 do baar aa sakta hai.

Point	Selection σ	Projection π
Filters	Rows by condition	Columns by list
Schema	Same columns	Chosen columns only
Example	Sem 3 students	Distinct semesters

4. Product ×, join ⋈ aur composed query

Cartesian product: R × S mein R ki har row S ki har row ke saath pair hoti hai. 3 Students × 2 Courses = 6 pairs, jo actual enrollment nahi batata. Theta join: R ⋈_condition S = σ_condition(R × S), matching pairs only. Implementations product materialize kiye bina efficiently join kar sakti hain.

Worked query: DBMS (course_id 10) mein kaun students hain? Pehle σ_{course_id=10}(Enrollment) = (101,10), (102,10). Isse Students ko condition Students.id = Enrollment.student_id par join karo: Asha aur Ravi. Phir π_name lagao, result {Asha,Ravi}. Symbolically: π_name(Students ⋈_{id=student_id} σ_{course_id=10}(Enrollment)).

SELECT DISTINCT s.name
FROM Students s
JOIN Enrollment e ON e.student_id = s.id
WHERE e.course_id = 10;

Natural join caution: same-named columns par equality automatically lagata hai. Agar accidentally ek extra column name common ho gaya, result badal sakta hai; practical SQL mein explicit JOIN ON safer aur clearer hai.

5. Union, difference aur rename

Union R ∪ S: dono relations ki rows ka set; difference R − S: R ki woh rows jo S mein nahi. Inputs union-compatible hone chahiye: same number of attributes aur corresponding compatible domains. Example A = {101,102} (DBMS student IDs), B = {101} (OS student IDs). A ∪ B = {101,102}; A − B = {102} (DBMS but not OS). SQL UNION duplicates hatata hai; UNION ALL nahi. SQL EXCEPT set difference jaisa hai, DBMS dialect check karo.

Rename ρ: relation/columns ko temporary name deta hai. Self-join mein Students ko S1 aur S2 bolna padta hai, warna same column identity ambiguous ho jati hai.

6. Division: 'sabhi courses' wala question

Definition: Agar R(student_id,course_id) aur S(course_id), to R ÷ S un student_id values ka set hai jinke saath S ka har course_id R mein present hai. Enrollment ÷ {(10),(20)} = {101}, kyunki Asha dono courses leti hai, Ravi sirf DBMS. Agar S empty hai to formal set definition ke hisaab se R mein present student IDs qualify karte hain; practical query ko business intent ke hisaab se handle karo.

SQL mein "all" question ko NOT EXISTS double-check pattern ya GROUP BY count se likh sakte hain, lekin course IDs distinct aur filtering consistent honi chahiye. Division exam mein universal quantifier (for every) samajhne ke liye useful hai.

7. Dataset ko table mein dekho: relation vs result

Ek relation ka schema attribute names aur unke domains batata hai; uski instance abhi stored tuples ka set hai. Yahan Students ka schema (id, name, sem) hai aur instance mein teen tuples hain. Classical relation mein row order ka meaning nahi hota. Neeche output ko padhne ke liye order mein dikhaya hai, algebra ne ordering guarantee nahi ki.

Students.id	name	sem
101	Asha	3
102	Ravi	3
103	Meera	5

Enrollment.student_id	course_id
101	10
101	20
102	10

Query ka data-flow diagram

Enrollment (3 tuples)
↓ σ course_id=10
(101,10), (102,10): 2 tuples
↓ join Students on id=student_id
(101,Asha,3,101,10), (102,Ravi,3,102,10)
↓ π name
{Asha, Ravi}

Selection pehle lagane se is example mein join input kam hota hai. Yeh logical expression hai, DBMS ka physical execution plan alag ho sakta hai. Projection ko blindly neeche push mat karo: join ke liye id aur student_id chahiye. Agar naam hi rakhe aur key hata di, join condition evaluate nahi hogi.

8. Operators ke point-by-point exam differences

Pair	First	Second	Is dataset par
Product vs join	Product har combination deta hai	Theta join predicate satisfy karne wale combinations deta hai	Students × Courses: 6 tuples. Students joined to Enrollment: 3 matching tuples
Union vs intersection	A ∪ B: either input mein ho	A ∩ B: dono inputs mein ho	A={101,102}, B={101}: union {101,102}, intersection {101}
A − B vs B − A	A mein ho, B mein nahi	B mein ho, A mein nahi	{102} vs empty set. Difference commutative nahi hai
Equijoin vs natural join	Explicit equality predicate	Har common-named attribute par equality; common columns ek baar	id aur student_id different names hain, isliye explicit condition chahiye
Classical algebra vs SQL	Relations sets hain, projection duplicates hata deta hai	SQL query results duplicates rakh sakte hain; DISTINCT explicitly use karo	π sem = {3,5}, plain SELECT sem gives 3,3,5

Natural join edge case: Students(id,name,sem) aur Enrollment(student_id,course_id) mein koi common attribute name nahi. Classical natural join then Cartesian product jaisa result deta hai: 3 × 3 = 9 combinations, not the intended three enrollments. Rename id to student_id first or use theta/equality join. Schema change se common names badle to natural join ka meaning bhi badal sakta hai.

Intersection derived formula: A ∩ B = A − (A − B). Yahan A − B = {102}, then {101,102} − {102} = {101}. Union, intersection aur difference mein compatible schemas check karo. Sirf same row count hona compatibility nahi hai.

9. Division ko missing-pair method se solve karo

Question: required Courses {10,20} ke har course mein kaun enrolled hai? Let R = Enrollment, S = π course_id(Courses), C = π student_id(R). Division ka result C − π student_id((C × S) − R) hai. Relation attributes ko align karke difference lagao.

Step	Result	Meaning
C	{101,102}	Enrollment mein present candidate IDs
C × S	{(101,10),(101,20),(102,10),(102,20)}	4 required candidate-course pairs
(C × S) − R	{(102,20)}	Missing pair
π student_id(missing)	{102}	Failing candidate
C − failing	{101}	Asha qualifies

Meera (103) is Students mein, lekin π student_id(Enrollment) mein nahi. Is division expression ka candidate universe {101,102} hai. Agar required-course relation empty ho to missing pairs empty aur result {101,102} hoga. Agar business question sab Students se candidates leta hai, empty requirement par {101,102,103} qualify karenge. Candidate universe explicitly define karo; SQL ke outer table ko choose karna result badal sakta hai.

10. Tested SQL bridge: set meaning ko query se verify karo

Existing example query aur neeche ke added queries SQLite 3 ke in-memory database par run kiye gaye. CREATE/INSERT setup sirf apne empty practice database mein use karo. Ordered displayed results readability ke liye hain; ORDER BY na ho to SQL row order fixed nahi.

CREATE TABLE Students (id INTEGER PRIMARY KEY, name TEXT, sem INTEGER);
CREATE TABLE Enrollment (student_id INTEGER, course_id INTEGER);
CREATE TABLE Courses (course_id INTEGER, title TEXT);
INSERT INTO Students VALUES (101,'Asha',3),(102,'Ravi',3),(103,'Meera',5);
INSERT INTO Enrollment VALUES (101,10),(101,20),(102,10);
INSERT INTO Courses VALUES (10,'DBMS'),(20,'OS');

DBMS but not OS

SELECT student_id FROM Enrollment WHERE course_id=10 EXCEPT SELECT student_id FROM Enrollment WHERE course_id=20;

Result student_id: 102.

All required courses: double NOT EXISTS

SELECT DISTINCT e.student_id FROM Enrollment e WHERE NOT EXISTS (SELECT 1 FROM Courses c WHERE NOT EXISTS (SELECT 1 FROM Enrollment e2 WHERE e2.student_id=e.student_id AND e2.course_id=c.course_id)) ORDER BY e.student_id;

Result student_id: 101. Inner NOT EXISTS asks whether a required enrollment is missing; outer NOT EXISTS requires no missing course. Outer candidates yahan Enrollment se liye hain, exactly division ke C se match karte hain.

Rename and self-join: same-semester student pairs

SELECT s1.name,s2.name FROM Students s1 JOIN Students s2 ON s1.sem=s2.sem AND s1.id<s2.id ORDER BY s1.id,s2.id;

Result: (Asha, Ravi). S1 and S2 aliases same Students relation ki do roles hain. id comparison self-pairs aur reversed duplicate pairs rokta hai. Without S1.id < S2.id, Asha-Ravi aur Ravi-Asha dono aa sakte hain.

11. Extra practice: pehle intermediate results likho

1. π name(σ sem=5(Students))? {Meera}. Selection leaves one tuple, projection keeps its name.
2. Enrollment × Courses has how many tuples? 3 × 2 = 6. Students × Enrollment has 3 × 3 = 9.
3. Students joined with Enrollment on id=student_id has how many tuples? 3, not 2: Asha matches two enrollment rows, Ravi one.
4. A ∩ B and B − A? {101} and empty set. Order of difference matters.
5. Can π sem equal σ sem=3? No. First changes schema to one attribute and returns {3,5}; second keeps three attributes and two student tuples.
6. Does natural join always implement the intended relationship? No. It uses names, not foreign-key intent. No common names gives product; extra common names add predicates.
7. Is GROUP BY part of basic classical algebra? No. Aggregation appears in extended relational algebra; do not silently treat it as one of the basic set operators.
8. Does division with empty requirements always return every student? Only every member of its chosen candidate relation. With C from Enrollment: 101,102; with C from Students: 101,102,103.

Practice questions: answers

1. Selection vs projection? σ rows ko predicate se filter karta hai; π columns choose karta hai aur classical sets mein duplicate tuples remove karta hai.
2. 3 × 2 product kitni rows? 6 pairs, chahe actual Enrollment mein sirf 3 links hon.
3. DBMS but not OS ka result? {102} = {101,102} − {101}.
4. Division ka use? "Har required course lene wale students" jaise for-all query.

Five-minute revision

σ rows; π columns; × all pairs; ⋈ matching pairs; ∪ either set; − first-only; ρ naming; ÷ all-required combinations. Classical relational algebra set semantics hai; SQL bag semantics aur NULL differences yaad rakho. Dataset par har intermediate relation likh kar solve karo.

Sources: Duke University: Relational Algebra and Calculus lecture; MIT OCW: Relational Model; PostgreSQL: SQL tutorial. Next: normalization and functional dependencies.

DBMS Exam Notes series: Previous: Part 3: SQL Queries | DBMS series and hub | Next: Part 5: Normalization