Relational algebra — join আর division

১ · Theta join আর equi join — × তারপর σ

পর্ব ৩২-এ (Relational algebra — select, project আর set অপারেশন) আপনি মৌলিক ছয়টি অপারেটর দেখেছেন: selection σ (সারি ছাঁকা), projection π (কলাম বাছা), rename ρ (নাম বদল), union ∪, set difference − আর Cartesian product ×. প্রতিটির ইনপুট relation, আউটপুটও relation — এই closure property-র জন্যই অপারেটরগুলো একটির পর একটি জোড়া দেওয়া যায়, ঠিক যেমন যোগ আর গুণ মিলিয়ে বড় গাণিতিক রাশি লেখা যায়। এই পর্বে নতুন যা আসবে, তার প্রায় সবই এই ছয়টি দিয়ে লেখা সংক্ষিপ্ত রূপ।

প্রথম সংক্ষিপ্ত রূপটি সবচেয়ে বেশি ব্যবহৃত। R × S দুই relation-এর প্রতিটি tuple-এর সাথে প্রতিটি tuple জোড়ে: |R| · |S| টি tuple. বাস্তবে আমরা প্রায় কখনো সব জোড়া চাই না; চাই শুধু অর্থবহ জোড়া। তাই × এর ঠিক পরে একটি σ বসে। এই জুটির নাম theta join:

θ (গ্রিক অক্ষর থিটা) যেকোনো শর্ত — R-এর একটি attribute আর S-এর একটি attribute-এর তুলনা (=, ≠, <, ≤, >, ≥), আর এমন তুলনার ∧ (AND). যখন θ-তে শুধু সমতার তুলনা থাকে, তখন একে বলে equi join — বাস্তবের প্রায় সব join এই জাতের: foreign key = primary key.

একটি উদাহরণ db-uni থেকে। এই কোর্সের বিশ্ববিদ্যালয় ডেটাবেসের instructors টেবিলে কলাম পাঁচটি: instructor_id, name, dept_id (বিভাগ), salary (মাসিক বেতন, টাকায়) আর mentor_id. প্রশ্ন: “একই বিভাগের মধ্যে কে কার চেয়ে বেশি বেতন পান?” এখানে θ দুই অংশের: a.dept_id = b.dept_id (সমতা) ∧ a.salary > b.salary (অসমতা)। algebra-য় একই relation দুবার লাগে, তাই আগে ρ দিয়ে দুটি নাম:

-- R × S: সব জোড়া
SELECT COUNT(*) AS cross_rows FROM instructors a CROSS JOIN instructors b;

-- σθ(R × S): আগে ×, তারপর WHERE-এ θ
SELECT a.name AS earns_more, b.name AS than_whom, a.dept_id
FROM instructors a CROSS JOIN instructors b
WHERE a.dept_id = b.dept_id AND a.salary > b.salary;

-- R ⋈θ S: একই কাজ JOIN … ON দিয়ে
SELECT a.name AS earns_more, b.name AS than_whom, a.dept_id
FROM instructors a JOIN instructors b
  ON a.dept_id = b.dept_id AND a.salary > b.salary;

সংজ্ঞা থেকে দুটি তথ্য সরাসরি আসে। এক, আকার: 0 ≤ |R ⋈_θ S| ≤ |R| · |S| — σ কখনো সারি বাড়ায় না। দুই, schema: ফলের attribute হলো R-এর সব attribute আর S-এর সব attribute, তাই equi join-এ join-এর কলামটি দুবার থাকে (a.dept_id আর b.dept_id) — একই মান, দুটি কলাম। পরের অংশের natural join ঠিক এই অপচয় দূর করে।

২ · Natural join ⋈ — একই নামের attribute মিলিয়ে

Natural join R ⋈ S-এ কোনো শর্ত লিখতে হয় না। নিয়মটি নিজে থেকেই আসে: R আর S-এর একই নামের সব attribute-এর মান সমান হতে হবে, আর ফলে সেই attribute-গুলো একবারই থাকবে। ধরুন R-এর attribute-সেট A, S-এর B, আর সাধারণ অংশ C = A ∩ B = {C₁, …, C_k}. তাহলে:

এখানে একটি সূক্ষ্মতা আছে। R × S-এ দুই দিকে একই নামের attribute থাকলে নামগুলো আলাদা করতে হয় — তাই কঠোরভাবে লিখলে আগে ρ দিয়ে S-এর সাধারণ attribute-গুলোর নাম বদলাতে হয়, তারপর ×, σ, আর শেষে π দিয়ে বদলানো কপিগুলো ফেলে দিতে হয়। দুটি বিশেষ ক্ষেত্র মনে রাখার মতো: C খালি হলে শর্ত কিছুই থাকে না, তাই R ⋈ S = R × S. A = B হলে (দুটির schema হুবহু এক) প্রতিটি attribute মিলতে হয়, তাই R ⋈ S = R ∩ S.

নিচের ডায়াগ্রামে দুটি ছোট relation: st(sid, name, dept_id) — তিনজন শিক্ষার্থী, আর dp(dept_id, dname) — তিনটি বিভাগ। Emon-এর বিভাগ 3 dp-তে নেই, আর English (4)-এ st-এর কেউ নেই। ধাপে ধাপে সংজ্ঞাটি প্রয়োগ করুন:

SQL-এ NATURAL JOIN ঠিক এই সংজ্ঞা মানে — নাম মিলিয়ে। আর এখানেই একটি বাস্তব ফাঁদ। db-uni-র students (student_id, name, dept_id, batch, cgpa) আর departments (dept_id, name, building) — দুটিতেই name কলাম আছে! তাই natural join শুধু dept_id নয়, name-ও মেলাতে চাইবে: “শিক্ষার্থীর নাম = বিভাগের নাম”। চালিয়ে দেখুন:

-- equi join: dept_id দুবার আসে
SELECT * FROM students s JOIN departments d ON s.dept_id = d.dept_id
WHERE s.student_id = 2101;

-- USING: join-এর কলাম একবার (natural join-এর মতো)
SELECT * FROM students JOIN departments USING (dept_id)
WHERE student_id = 2101;

-- NATURAL JOIN: dept_id আর name দুটিই মেলাতে চায়
SELECT COUNT(*) AS natural_rows FROM students NATURAL JOIN departments;

-- courses আর instructors-এর সাধারণ কলাম: instructor_id আর dept_id
SELECT course_id, title, name, dept_id FROM courses NATURAL JOIN instructors;

শিক্ষা দুটি। তত্ত্বে natural join খুব সুন্দর, কারণ ভালো ডিজাইনে একই নাম মানে একই অর্থ (পর্ব ৩৬-৩৭-এর normalization-এ decomposition আর join এই অনুমানের ওপর দাঁড়িয়ে)। বাস্তব SQL-এ NATURAL JOIN-এর বদলে JOIN … USING (…) বা ON লিখুন — কোন কলামে মেলাচ্ছেন, তা নিজে বলে দিন।

বিনিময় আর সংযোজন নিয়ম — ছোট প্রমাণ

প্রথমে একটি সহায়ক কথা (lemma). attribute-সেট A ∪ B-র ওপর একটি tuple t ধরুন, আর t[A] মানে t-এর শুধু A-অংশ। সংজ্ঞা থেকে:

কেন? (⇒) R × S-এর একটি জোড়া (r, s) σ পেরোলে সাধারণ attribute-গুলোতে r আর s-এর মান সমান, তাই π-এর পরের tuple t-এর A-অংশ ঠিক r, B-অংশ ঠিক s. (⇐) t[A] = r ∈ R আর t[B] = s ∈ S হলে r আর s সাধারণ attribute-এ একই মান নেয় (দুটিই t-এর অংশ), তাই (r, s) σ পেরোয় আর π-এর পর ঠিক t দেয়। ∎

• বিনিময় (commutativity): lemma-র ডান পাশ “t[A] ∈ R এবং t[B] ∈ S” — R আর S বদলালে একই কথা। তাই R ⋈ S = S ⋈ R. (relational model-এ attribute নাম দিয়ে চেনা হয়, অবস্থান দিয়ে নয়; তাই কলামের ক্রম আলাদা হলেও relation একই।)
• সংযোজন (associativity): T-এর attribute-সেট D ধরুন। lemma দুবার লাগালে t ∈ (R ⋈ S) ⋈ T ⇔ t[A ∪ B] ∈ R ⋈ S এবং t[D] ∈ T ⇔ t[A] ∈ R, t[B] ∈ S, t[D] ∈ T. একইভাবে t ∈ R ⋈ (S ⋈ T)-এর শর্তও ঠিক এই তিনটি। তাই (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T). ∎

ফলাফল বড়: n টি relation-এর natural join যেকোনো ক্রমে, যেকোনো বন্ধনীতে হিসাব করা যায়। theta join-এর জন্য নিয়মটি একটু শর্তসাপেক্ষ: (R ⋈_θ1 S) ⋈_θ2 T = R ⋈_θ1 (S ⋈_θ2 T), যদি θ2-তে শুধু S আর T-এর attribute থাকে — নইলে ডান পাশে θ2 লেখাই যায় না। অংশ ৭-এ optimizer এই স্বাধীনতা কীভাবে কাজে লাগায়, দেখবেন।

৩ · Outer join ⟕ ⟖ ⟗ — মিল না পেলে NULL দিয়ে ভরাট

Natural join-এ Emon আর English হারিয়ে গেছে। “সব শিক্ষার্থী, বিভাগ থাকুক বা না থাকুক” চাইলে দরকার outer join: join-এর ফল, সাথে যে tuple মিল পায়নি (dangling tuple) সেগুলোও — অন্য দিকের attribute-গুলোতে NULL বসিয়ে। তিনটি রূপ:

এগুলো নতুন ক্ষমতা নয়, মৌলিক অপারেটরের সংক্ষেপ — যদি NULL-কে একটি বিশেষ মান হিসেবে মেনে নিই। B − A হলো শুধু S-এ থাকা attribute, আর {(NULL, …, NULL)} সেই attribute-গুলোর ওপর এক-tuple-এর একটি relation. তাহলে:

পড়ুন এভাবে: join-এর ফল, যোগ R-এর সেই tuple-গুলো যারা join-এ কোনো অংশ পায়নি (R − π_A(R ⋈ S)), প্রতিটির পাশে NULL-এর একটি সারি জুড়ে। R ⟖ S একইভাবে S-এর দিক থেকে, আর R ⟗ S = (R ⟕ S) ∪ (R ⟖ S). একই st আর dp-তে দেখুন:

একই কাজ SQL-এ। এডিটরটি আগে ডায়াগ্রামের দুটি ছোট টেবিল তৈরি করে নেয় — st(sid, name, dept_id) আর dp(dept_id, dname). SQLite 3.39 (২০২২) থেকে RIGHT আর FULL JOIN চালায়; এই পাতার ইঞ্জিন তার চেয়ে নতুন।

-- st ⟕ dp
SELECT st.sid, st.name, st.dept_id, dp.dname
FROM st LEFT JOIN dp ON dp.dept_id = st.dept_id;

-- st ⟖ dp
SELECT st.sid, st.name, dp.dept_id, dp.dname
FROM st RIGHT JOIN dp ON dp.dept_id = st.dept_id;

-- st ⟗ dp: dept_id যেকোনো দিক থেকে
SELECT st.sid, st.name, COALESCE(st.dept_id, dp.dept_id) AS dept_id, dp.dname
FROM st FULL JOIN dp ON dp.dept_id = st.dept_id
ORDER BY dept_id;

৪ · Semi join ⋉ আর anti join ▷ — “অন্তত একটি” আর “একটিও নেই”

পর্ব ২০ আর ২১-এ আপনি EXISTS আর NOT EXISTS লিখেছেন। algebra-য় এদের নাম semi join আর anti join, আর সংজ্ঞা মাত্র এক লাইনের:

R ⋉ S হলো R-এর সেই tuple-গুলো, যাদের S-এ অন্তত একটি মিল আছে — কিন্তু ফলে শুধু R-এর attribute (A). R ▷ S হলো বাকিগুলো: যাদের কোনো মিল নেই। anti join-এর চিহ্ন বইভেদে ▷ বা ⊳ — অর্থ একই। দুটি তথ্য সংজ্ঞা থেকেই আসে: R ⋉ S ⊆ R (তাই কখনো সারি বাড়ায় না), আর (R ⋉ S) ∪ (R ▷ S) = R, দুটি পরস্পর-বিচ্ছিন্ন — প্রতিটি tuple ঠিক একটিতে পড়ে। এটি outer join-এর বর্ণনাতেও লুকিয়ে ছিল: অংশ ৩-এর R − π_A(R ⋈ S) আসলে R ▷ S.

উদাহরণ: “কোন শিক্ষক অন্তত একটি কোর্স পড়ান?” = instructors ⋉ courses, আর “কে কোনো কোর্স পড়ান না?” = instructors ▷ courses (শর্ত instructors.instructor_id = courses.instructor_id). db-uni-র courses টেবিলে course_id, title, dept_id, credits আর instructor_id (কে পড়ান):

-- instructors ⋉ courses  (EXISTS)
SELECT i.instructor_id, i.name FROM instructors i
WHERE EXISTS (SELECT 1 FROM courses c WHERE c.instructor_id = i.instructor_id);

-- শুধু ⋈: যতগুলো কোর্স, ততবার
SELECT i.instructor_id, i.name FROM instructors i
JOIN courses c ON c.instructor_id = i.instructor_id;

-- instructors ▷ courses  (NOT EXISTS)
SELECT i.instructor_id, i.name FROM instructors i
WHERE NOT EXISTS (SELECT 1 FROM courses c WHERE c.instructor_id = i.instructor_id);

পর্ব ২০-এর NOT IN ফাঁদ এখানে নতুন আলোয় দেখা যায়: algebra-র ▷ সংজ্ঞায় শুধু ⋈ আর − আছে, যেখানে NULL কখনো কোনো কিছুর সাথে মেলে না, তাই কোনো UNKNOWN তৈরি হয় না। NOT EXISTS এই সংজ্ঞার বিশ্বস্ত অনুবাদ; nullable কলামে NOT IN নয়, কারণ সেটি তিন-মানের যুক্তি-র AND-শিকল।

৫ · Division ÷ — “সবগুলো” প্রশ্নের অপারেটর

কিছু প্রশ্নে “অন্তত একটি” নয়, চাই “প্রতিটি”: “কোন শিক্ষার্থী CSE-র সব core কোর্স নিয়েছেন?”, “কোন সরবরাহকারী (supplier) সব যন্ত্রাংশ সরবরাহ করে?”, “কোন গ্রাহক তালিকার প্রতিটি পণ্য একবার হলেও কিনেছেন?” যুক্তিবিদ্যায় “সবার জন্য” হলো ∀ — universal quantification. join, σ বা π-এর কোনোটিই একা ∀ প্রকাশ করে না; সবগুলো স্বভাবে “অস্তিত্ব” (∃) খোঁজে। এই কাজের জন্য Codd তাঁর মূল algebra-য় একটি আলাদা অপারেটর রেখেছিলেন: division ÷.

৫.১ · আনুষ্ঠানিক সংজ্ঞা

ধরুন R-এর attribute X ∪ Y, আর S-এর attribute ঠিক Y (X আর Y পরস্পর-বিচ্ছিন্ন, Y খালি নয়)। উদাহরণে R = takes(sid, cid), S = core(cid); X = {sid}, Y = {cid}. তাহলে:

সমতুল্য আরেকটি বর্ণনা, যা নামটির ব্যাখ্যা দেয়: R ÷ S হলো π_X(R)-এর সবচেয়ে বড় উপসেট T, যার জন্য T × S ⊆ R. ঠিক যেমন পূর্ণসংখ্যায় 13 ÷ 4 = 3, কারণ 3 হলো সবচেয়ে বড় q যার জন্য q × 4 ≤ 13 — আর “ভাগশেষ” পড়ে থাকে। এখানেও (R ÷ S) × S ⊆ R, আর R-এর বাড়তি tuple-গুলো (যেমন Dilruba-র বাড়তি CSE301) ভাগশেষ।

৫.২ · মৌলিক অপারেটর দিয়ে উৎপত্তি

÷ কোনো নতুন ক্ষমতা আনে না; এটি π, × আর − দিয়ে লেখা যায়। যুক্তিটি দোকানদারের উল্টো দিক থেকে: “কে যোগ্য” সরাসরি না খুঁজে আগে খুঁজুন “কে অযোগ্য”, তারপর সবার থেকে তাঁদের বাদ দিন।

1. T₁ = π_X(R) — সব প্রার্থী।
2. T₂ = T₁ × S — “প্রত্যেক প্রার্থী প্রতিটি core নিলে” যে জোড়াগুলো থাকত।
3. T₃ = T₂ − R — যে জোড়াগুলো থাকা উচিত ছিল কিন্তু নেই: কার কোন core বাকি।
4. T₄ = π_X(T₃) — অন্তত একটি core বাকি এমন প্রার্থী, অর্থাৎ অযোগ্যরা।
5. R ÷ S = T₁ − T₄.

প্রমাণ. t ∈ π_X(R) নিন। t ∈ T₄ ⇔ এমন s ∈ S আছে যার জন্য (t, s) ∈ T₂ − R ⇔ এমন s ∈ S আছে যার জন্য (t, s) ∉ R (কারণ t ∈ T₁ বলে (t, s) সবসময় T₂-তে আছে)। তাই t ∉ T₄ ⇔ প্রতিটি s ∈ S-এর জন্য (t, s) ∈ R — ঠিক সংজ্ঞার শর্ত। যুক্তির মূল চাবি: ¬∃s ¬P(s) ≡ ∀s P(s). ∎

নিচের ডায়াগ্রামে ছোট উদাহরণ: takes-এ ৬টি tuple — Arif (CSE101, CSE201), Bristy (CSE101), Dilruba (CSE101, CSE201, CSE301); core = {CSE101, CSE201}.

SQL-এ ÷ অপারেটর নেই, কিন্তু উপরের সূত্রটি প্রায় অক্ষরে অক্ষরে লেখা যায় — × হলো CROSS JOIN, − হলো EXCEPT, π হলো SELECT DISTINCT (EXCEPT নিজেও duplicate ফেলে দেয়)। এডিটরটি ডায়াগ্রামের takes(sid, cid) আর core(cid) টেবিল তৈরি করে নেয়:

-- T3 = (π sid(R) × S) − R : কার কোন core বাকি
SELECT t.sid, c.cid FROM (SELECT DISTINCT sid FROM takes) t CROSS JOIN core c
EXCEPT
SELECT sid, cid FROM takes;

-- R ÷ S = π sid(R) − π sid(T3)
SELECT sid FROM takes
EXCEPT
SELECT sid FROM (SELECT t.sid, c.cid
                 FROM (SELECT DISTINCT sid FROM takes) t CROSS JOIN core c
                 EXCEPT
                 SELECT sid, cid FROM takes);

৫.৩ · SQL-এ প্রথম ধরন — দুই স্তরের NOT EXISTS

SQL-এ ∀ নেই, কিন্তু ∃ আছে (EXISTS). তাই প্রমাণের চাবিটিই কাজে লাগে: “প্রতিটি core নিয়েছেন” ≡ “এমন কোনো core নেই, যেটি তিনি নেননি”। দুটি “না” — দুটি NOT EXISTS. এবার আসল db-uni-তে: enrollments টেবিলে student_id, course_id, term আর grade (প্রতিটি ভর্তি একটি সারি)। এডিটর একটি cse_core(course_id) টেবিল বানায় — CSE101, CSE201, CSE301:

-- এমন কোনো core নেই, যেটি এই শিক্ষার্থী নেননি
SELECT s.student_id, s.name
FROM students s
WHERE NOT EXISTS (
  SELECT 1 FROM cse_core k
  WHERE NOT EXISTS (
    SELECT 1 FROM enrollments e
    WHERE e.student_id = s.student_id
      AND e.course_id = k.course_id));

৫.৪ · দ্বিতীয় ধরন — GROUP BY … HAVING COUNT

অনেকের কাছে সহজ চিন্তা গোনা: “শিক্ষার্থী যতগুলো ভিন্ন core নিয়েছেন, সেই সংখ্যা = মোট core-এর সংখ্যা” হলে তিনি সব নিয়েছেন। দুটি সতর্কতা লাগে: শুধু core কোর্সগুলোই গুনতে হবে (তাই আগে cse_core-এর সাথে join), আর একই কোর্স দুবার নিলে (ফেল করে আবার) যেন দুবার না গোনা হয় (তাই COUNT(DISTINCT …))।

-- প্রত্যেকে কয়টি core নিয়েছেন
SELECT e.student_id, COUNT(DISTINCT e.course_id) AS core_taken
FROM enrollments e JOIN cse_core k ON k.course_id = e.course_id
GROUP BY e.student_id;

-- সংখ্যা = মোট core হলে, সব নিয়েছেন
SELECT e.student_id
FROM enrollments e JOIN cse_core k ON k.course_id = e.course_id
GROUP BY e.student_id
HAVING COUNT(DISTINCT e.course_id) = (SELECT COUNT(*) FROM cse_core);

৫.৫ · খালি ভাজক — তিন পদ্ধতি, তিন উত্তর

ভাজক S খালি হলে কী হয়? algebra-র সূত্রে T₂ = T₁ × ∅ = ∅, তাই T₄ = ∅ আর R ÷ ∅ = π_X(R) — R-এর সবাই। যুক্তিবিদ্যায় এটি স্বাভাবিক: খালি সেটের ওপর “সবার জন্য” সবসময় সত্য (vacuous truth). কিন্তু SQL-এর দুই পদ্ধতি এখানে একমত নয়। পরীক্ষা: “কোন শিক্ষার্থী Rumana Islam (instructor 4)-এর পড়ানো সব কোর্স নিয়েছেন?” — Rumana কোনো কোর্স পড়ান না (অংশ ৪)।

SELECT COUNT(*) AS not_exists_way FROM students s
WHERE NOT EXISTS (SELECT 1 FROM courses c WHERE c.instructor_id = 4
  AND NOT EXISTS (SELECT 1 FROM enrollments e
      WHERE e.student_id = s.student_id AND e.course_id = c.course_id));

SELECT COUNT(*) AS count_way FROM (SELECT e.student_id
  FROM enrollments e JOIN courses c ON c.course_id = e.course_id
  WHERE c.instructor_id = 4 GROUP BY e.student_id
  HAVING COUNT(DISTINCT e.course_id) =
         (SELECT COUNT(*) FROM courses WHERE instructor_id = 4));

SELECT COUNT(DISTINCT student_id) AS algebra_way FROM enrollments;

৬ · Extended relational algebra — γ, generalized projection আর completeness

মৌলিক algebra দিয়ে “প্রতিটি বিভাগে কতজন শিক্ষার্থী?” বা “মোট বেতন কত?” লেখা যায় না — যোগ, গড় বা গণনার কোনো অপারেটর নেই। বাস্তব DBMS-এর জন্য তাই algebra-কে বাড়ানো হয়েছে; একে বলে extended relational algebra.

৬.১ · Aggregation আর grouping — γ

Grouping operator-এর লেখা বইভেদে আলাদা: Garcia-Molina–Ullman–Widom-এর বইয়ে γ_L(R), Silberschatz–Korth–Sudarshan-এর বইয়ের পুরোনো সংস্করণে বাঁকা 𝒢 (নতুন সংস্করণে γ)। সাধারণ রূপ:

বাঁ দিকের নিচে grouping attribute (যাদের মান এক, তারা এক দলে), ডান দিকের নিচে aggregate function — COUNT, SUM, AVG, MIN, MAX. অর্থ: E-কে G-এর মান অনুযায়ী ভাগ করুন, প্রতিটি দল থেকে একটি tuple — G-এর মান আর প্রতিটি F-এর ফল। G খালি হলে পুরো E একটি দল, ফলে একটি tuple. SQL-এ এটিই GROUP BY (পর্ব ১৮), আর HAVING হলো γ-এর ওপরে বসানো একটি σ. উদাহরণ: _{dept_id}γ_{COUNT(student_id), AVG(cgpa)}(students).

-- dept_id γ COUNT(*), COUNT(cgpa), AVG(cgpa) (students)
SELECT dept_id, COUNT(*) AS n, COUNT(cgpa) AS with_cgpa,
       ROUND(AVG(cgpa), 2) AS avg_cgpa
FROM students GROUP BY dept_id;

-- G খালি: পুরো relation একটি দল
SELECT COUNT(*) AS students, MAX(cgpa) AS best FROM students;

-- π d.name, total (departments ⋈ (dept_id γ SUM(salary) (instructors)))
SELECT d.name AS dept, g.total_salary
FROM departments d
JOIN (SELECT dept_id, SUM(salary) AS total_salary
      FROM instructors GROUP BY dept_id) g ON g.dept_id = d.dept_id;

৬.২ · Generalized projection

মৌলিক π শুধু attribute বাছে। Generalized projection π_{F1, …, Fn}(E)-এ প্রতিটি F একটি রাশি হতে পারে — attribute, ধ্রুবক বা গাণিতিক হিসাব — যেমন π_{name, salary × 12 → yearly}(instructors). SQL-এর SELECT name, salary * 12 AS yearly ঠিক এটি (db-uni-তে Dr. Mahbub Alam-এর yearly 1320000). আর ρ দিয়ে ফলের attribute-এর নাম দেওয়াই SQL-এর AS.

৬.৩ · Extended অপারেটরের সারসংক্ষেপ

Set বনাম bag: এই পর্বের সব সংজ্ঞা set-এর ওপর — কোনো tuple দুবার থাকে না, তাই π নিজেই duplicate মোছে। SQL টেবিল আর কোয়েরির ফল কিন্তু bag: SELECT dept_id FROM students 1 চারবার দেয়। তাই পাঠ্যবইয়ের bag algebra-য় দুটি বাড়তি অপারেটর থাকে: δ (duplicate মোছা, SQL-এর DISTINCT) আর τ (সাজানো, ORDER BY). algebra থেকে SQL-এ অনুবাদ করার সময় প্রতিটি π-এর পাশে ভাবুন — এখানে duplicate কি ফলের অর্থ বদলাবে? গোনা বা যোগের আগে বদলায়; EXISTS-এর ভেতরে বদলায় না।

৬.৪ · Relational completeness

১৯৭২ সালে Codd তাঁর “Relational Completeness of Data Base Sublanguages” প্রবন্ধে একটি মানদণ্ড দেন: কোনো কোয়েরি-ভাষা relationally complete, যদি relational calculus (পর্ব ৩৪) দিয়ে যত কোয়েরি লেখা যায়, সবই সেই ভাষায় লেখা যায়। তিনি দেখান মৌলিক algebra-ও ঠিক এতটা প্রকাশ করতে পারে (safe calculus আর algebra সমান শক্তির)। SQL relationally complete: σ হলো WHERE, π হলো SELECT DISTINCT, × হলো CROSS JOIN, ∪ হলো UNION, − হলো EXCEPT বা NOT EXISTS, ρ হলো AS. আর SQL এর চেয়েও বেশি পারে — aggregation, ORDER BY, আর WITH RECURSIVE (পর্ব ২৫)। শেষেরটি গুরুত্বপূর্ণ: ১৯৭৯ সালে Alfred Aho আর Jeffrey Ullman প্রমাণ করেন, মৌলিক algebra দিয়ে transitive closure (“A-র mentor-এর mentor-এর … যত স্তরই হোক”) প্রকাশ করা যায় না। অর্থাৎ “complete” মানে “সব পারে” নয়, “calculus যা পারে, তা পারে”।

৭ · Query tree আর join-এর ক্রম বদল

একটি algebra রাশিকে গাছ হিসেবে আঁকা যায়: পাতায় (leaf) টেবিল, ভেতরের প্রতিটি গিঁটে (node) একটি অপারেটর, ডেটা নিচ থেকে ওপরে যায়। একে বলে query tree. DBMS আপনার SQL প্রথমে এমন একটি গাছে বদলায়, তারপর equivalence rule দিয়ে গাছটি নতুন করে সাজায় — ফল একই, কাজ কম। মূল নিয়মগুলো (E মানে যেকোনো রাশি):

1. σ ভাঙা: σ_{θ1 ∧ θ2}(E) = σ_θ1(σ_θ2(E)), আর σ-গুলোর ক্রম বদলানো যায়।
2. × থেকে ⋈: σ_θ(E₁ × E₂) = E₁ ⋈_θ E₂.
3. বিনিময় আর সংযোজন: E₁ ⋈ E₂ = E₂ ⋈ E₁; (E₁ ⋈ E₂) ⋈ E₃ = E₁ ⋈ (E₂ ⋈ E₃) — অংশ ২-এর প্রমাণ।
4. σ নিচে ঠেলা (predicate pushdown): θ₀-তে শুধু E₁-এর attribute থাকলে σ_θ0(E₁ ⋈_θ E₂) = σ_θ0(E₁) ⋈_θ E₂.
5. π নিচে ঠেলা: L₁, L₂ যথাক্রমে E₁, E₂-এর দরকারি attribute, আর θ-তে শুধু এদের মধ্যের attribute থাকলে π_{L1 ∪ L2}(E₁ ⋈_θ E₂) = π_L1(E₁) ⋈_θ π_L2(E₂). θ-তে অন্য attribute থাকলে সেগুলোও নিচের π-তে রাখতে হয়, আর ওপরে একটি π রেখে শেষে ফেলতে হয়।

নিয়ম ৪-এর প্রমাণ: E₁ ⋈_θ E₂-এর প্রতিটি tuple একটি জোড়া (r, s), r ∈ E₁. θ₀ শুধু r-এর মান দেখে, তাই জোড়াটি σ_θ0 পেরোয় ⇔ r নিজে σ_θ0 পেরোয়। অতএব ছাঁকা আগে করা আর পরে করা একই জোড়ার সেট দেয়। ∎ (outer join-এ নিয়মটি শুধু রাখা-দিকের শর্তে খাটে: R ⟕ S-এর ওপরের R-এর শর্ত নিচে ঠেলা যায়, কিন্তু S-এর শর্ত নিচে ঠেললে ফল বদলায় — ওপরের শর্ত NULL-ভরাট সারি বাদ দিত, নিচের শর্তের পর সেগুলো আবার NULL-সহ ফিরে আসে।)

উদাহরণ প্রশ্ন: “CSE বিভাগের যেসব শিক্ষার্থী কোনো কোর্সে 'A' পেয়েছেন, তাঁদের নাম।” প্রথম গাছ সরাসরি সংজ্ঞা থেকে, তারপর নিয়ম দিয়ে সাজানো — প্রতিটি ধাপে সবচেয়ে বড় মধ্যবর্তী ফলের আকার দেখুন (সংখ্যাগুলো db-uni-র আসল ডেটা থেকে):

এই ছোট ডেটায় ৪১৬ বনাম ৪ হাস্যকর মনে হতে পারে, কিন্তু অনুপাতটি বড় ডেটায়ও থাকে: দশ হাজার শিক্ষার্থী আর দশ লাখ ভর্তিতে প্রথম গাছটি অসম্ভব, শেষটি এক সেকেন্ডের কম। নিয়ম ৩ (join-এর ক্রম বদল) এর সাথে যুক্ত হলে optimizer বেছে নিতে পারে কোন দুটি টেবিল আগে জুড়লে মধ্যবর্তী ফল সবচেয়ে ছোট — একে বলে join order নির্বাচন, যার পুরো খরচ-হিসাব পর্ব ৪৩-এ।

৮ · পরীক্ষার ধাঁচের সমস্যা — বিশ্ববিদ্যালয়ের schema-য়

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় relational algebra-র প্রশ্ন সাধারণত এমন: একটি schema দেওয়া, ইংরেজিতে প্রশ্ন, algebra-য় উত্তর লিখতে হবে। নিচে db-uni-র schema সংক্ষেপে — students(student_id, name, dept_id, batch, cgpa), instructors(instructor_id, name, dept_id, salary, mentor_id), courses(course_id, title, dept_id, credits, instructor_id), enrollments(student_id, course_id, term, grade), departments(dept_id, name, building). প্রতিটির পাশে উত্তর আর এই ডেটায় ফল।

1. যে শিক্ষার্থী কোনো কোর্সে ভর্তি হননি. π_{student_id}(students) − π_{student_id}(enrollments), অথবা students ▷ enrollments. ফল: 2302 Habib Ullah.
2. যে শিক্ষক CSE-র প্রতিটি কোর্স পড়ান. π_{instructor_id, course_id}(courses) ÷ π_{course_id}(σ_{dept_id = 1}(courses)). ফল: খালি — CSE-র চারটি কোর্স তিনজন শিক্ষকের মধ্যে ভাগ করা। (এখানে ভাজ্য courses নিজেই, কারণ db-uni-তে কোর্স–শিক্ষক সম্পর্ক courses-এর একটি কলামে; অনেক বইয়ের schema-য় এর জন্য আলাদা teaches টেবিল থাকে।)
3. যে শিক্ষার্থী Tasnim Chowdhury (6)-এর পড়ানো সব কোর্স নিয়েছেন. π_{student_id, course_id}(enrollments) ÷ π_{course_id}(σ_{instructor_id = 6}(courses)). ভাজক {CSE301, CSE302}. ফল: 2101 Arif Hossain — Bristy আর Dilruba শুধু CSE301 নিয়েছেন।
4. একই কোর্সে পড়েছেন এমন শিক্ষার্থী-জোড়া (প্রতিটি জোড়া একবার). π_{a.student_id, b.student_id}(σ_{a.student_id < b.student_id}(ρ_a(enrollments) ⋈_{a.course_id = b.course_id} ρ_b(enrollments))). ফল ৫টি জোড়া: (2201, 2301), (2101, 2102), (2101, 2201), (2102, 2201), (2103, 2203). π-এর আগে course_id রাখলে ৮টি সারি, কারণ 2101–2102 এর মতো জোড়া দুটি কোর্সে একসাথে।
5. সর্বোচ্চ বেতন — aggregation ছাড়া. π_salary(instructors) − π_a.salary(σ_{a.salary < b.salary}(ρ_a(instructors) × ρ_b(instructors))). যুক্তি: যে বেতনের চেয়ে বড় কোনো বেতন আছে, সেগুলো বাদ দিলে থাকে শুধু সর্বোচ্চটি। ফল: 120000 (Dr. Anisur Rahman). γ দিয়ে একই কাজ: γ_MAX(salary)(instructors).
6. প্রতিটি বিভাগের নাম আর শিক্ষার্থীর সংখ্যা, শূন্যসহ. _d.nameγ_{COUNT(s.student_id)}(departments ⟕ students). outer join বলে English আসে ০ নিয়ে; COUNT(*) লিখলে NULL-ভরাট সারিটিও ১ গোনা হতো।
7. অন্তত দুটি ভিন্ন কোর্স নিয়েছেন এমন শিক্ষার্থী — aggregation ছাড়া. π_{a.student_id}(σ_{a.course_id ≠ b.course_id}(ρ_a(enrollments) ⋈_{a.student_id = b.student_id} ρ_b(enrollments))). নিজের সাথে জোড়া দিয়ে দেখা হচ্ছে, একই শিক্ষার্থীর দুটি আলাদা কোর্স আছে কি না। ফল ৪ জন: 2101, 2102, 2201, 2301. “অন্তত k টি” লিখতে k টি কপি আর প্রতিটি জোড়ায় ≠ লাগে — তাই বাস্তবে γ_COUNT অনেক সহজ।
8. ঠিক একটি কোর্স নিয়েছেন এমন শিক্ষার্থী. π_{student_id}(enrollments) − (আগের সমস্যার ফল). “ঠিক একটি” = “অন্তত একটি” − “অন্তত দুটি”। ফল: 2103, 2202, 2203.

প্রথম তিনটি পাতাতেই চালিয়ে দেখুন। দ্বিতীয়টিতে ভাজ্যের ভূমিকায় courses t — “শিক্ষক i কোর্স c পড়ান” জানতে এটিই আমাদের teaches:

-- ১) students ▷ enrollments
SELECT s.student_id, s.name FROM students s
WHERE NOT EXISTS (SELECT 1 FROM enrollments e WHERE e.student_id = s.student_id);

-- ২) CSE-র প্রতিটি কোর্স পড়ান এমন শিক্ষক
SELECT i.name FROM instructors i
WHERE NOT EXISTS (SELECT 1 FROM courses c WHERE c.dept_id = 1
  AND NOT EXISTS (SELECT 1 FROM courses t
                  WHERE t.course_id = c.course_id AND t.instructor_id = i.instructor_id));

-- ৩) Tasnim (6)-এর সব কোর্স নিয়েছেন এমন শিক্ষার্থী
SELECT s.student_id, s.name FROM students s
WHERE NOT EXISTS (SELECT 1 FROM courses c WHERE c.instructor_id = 6
  AND NOT EXISTS (SELECT 1 FROM enrollments e
                  WHERE e.student_id = s.student_id AND e.course_id = c.course_id));

৯ · AI-এর যুগে relational algebra

AI-কে “এই প্রশ্নের relational algebra লেখো” বললে উত্তর প্রায়ই দেখতে নিখুঁত — চিহ্নগুলো ঠিক জায়গায়। কিন্তু algebra-র ভুল চোখে পড়ে না, কারণ কেউ এটি “চালায়” না। এই বিষয়ে AI-এর প্রচলিত ভুল:

AI-এর লেখা algebra বা division কোয়েরি হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রশ্নের শব্দ “অন্তত একটি”, “একটিও না” না “প্রতিটি” — সেই অনুযায়ী ⋉, ▷ বা ÷ হয়েছে
• প্রতিটি অপারেটরের পর schema (কোন attribute) হাতে লিখে দেখেছি; ÷-এর ভাজকের attribute ভাজ্যের মধ্যে আছে
• natural join-এর সাধারণ attribute ঠিক সেগুলোই, যা মেলাতে চাই
• SQL অনুবাদ নমুনা ডেটায় চালিয়েছি; সারির সংখ্যা হাতে হিসাবের সাথে মিলেছে
• মিলহীন, একাধিক মিলের আর NULL-যুক্ত tuple দিয়ে পরীক্ষা করেছি
• ভাজক খালি হলে কী চাই, ঠিক করেছি আর সেটি চালিয়ে দেখেছি
• বড় টেবিলে EXPLAIN দেখেছি: NOT EXISTS anti join হচ্ছে, join কলামে index আছে