Relational algebra — select, project আর set অপারেশন

১ · কেন একটি আনুষ্ঠানিক কোয়েরি ভাষা

মডিউল ৩ আর ৪-এ আপনি অনেক SQL লিখেছেন। SQL একটি declarative language: আপনি বলেন কী চাই, DBMS ঠিক করে কীভাবে আনবে। কিন্তু এর জন্য একটি শর্ত আছে। “কী চাই” কথাটির অর্থ একদম নিখুঁত হতে হবে। নইলে দুটি DBMS একই কোয়েরির দুই রকম উত্তর দেবে, আর optimizer কোয়েরিটি নিরাপদে বদলাতে পারবে না।

এই নিখুঁততা তিনটি কাজে লাগে:

• অর্থ ঠিক করা। SQL standard-এর অনেক নিয়ম আসলে algebra-র ভাষায় ভাবা: WHERE মানে selection, FROM-এর কমা মানে product, UNION মানে union.
• Optimization-এর ভিত্তি। দুটি expression সবসময় একই ফল দেয় কি না, তা প্রমাণ করা যায়। তখন query optimizer নিশ্চিন্তে ধীর রূপটিকে দ্রুত রূপে বদলাতে পারে।
• ভাষার ক্ষমতা মাপা। কোন প্রশ্ন একটি ভাষায় লেখা যায় আর কোনটি যায় না, তা স্পষ্ট বলা যায় (ভাবনার প্রশ্ন ৫)।

বাস্তবে আপনার লেখা SQL প্রথমে একটি parse tree হয়। তারপর DBMS তাকে relational algebra-র মতো অপারেটরের একটি গাছে বদলায়, যাকে বলে logical plan. সেই গাছটি নিয়মমাফিক ঘুরিয়ে-বদলে সবচেয়ে সস্তা query plan বেছে নেওয়া হয়। পর্ব ৪২-এ দেখবেন প্রতিটি অপারেটর কোন অ্যালগরিদমে চলে, আর পর্ব ৪৩-এ দেখবেন optimizer খরচ হিসাব করে কীভাবে বাছে। এই পর্ব তার ভাষাটি শেখায়।

Relation মানে set — আর closure: ফলও একটি relation

পর্ব ৫-এ দেখেছেন, একটি relation হলো একই schema-র tuple-এর একটি set. এখান থেকে দুটি কথা আসে। এক, একই tuple দুবার থাকতে পারে না। দুই, tuple-এর কোনো ক্রম নেই; “প্রথম সারি” বলে কিছু নেই। SQL-এর টেবিল এই দুটি নিয়মই ঢিলে করেছে (duplicate চলে, ORDER BY দিয়ে ক্রম আসে)। Relational algebra কিন্তু খাঁটি set ধরে চলে। পার্থক্যটি অংশ ৩-এ বারবার দেখবেন।

Closure-এর কারণেই SQL-এ subquery, view আর CTE সম্ভব: একটি কোয়েরির ফল আরেকটির FROM-এ টেবিলের মতো বসে। অপারেটরগুলো দুই রকম। Unary অপারেটর একটি relation নেয়: σ, π, ρ. Binary অপারেটর দুটি নেয়: ∪, −, ∩, ×, আর পরের পর্বের ⋈ ও ÷.

এই পর্বের উদাহরণ চলবে db-uni বিশ্ববিদ্যালয় ডেটাবেসে। মূলত তিনটি relation: students (student_id, name, dept_id, batch, cgpa — ৮ জন; Fahim-এর cgpa আর Habib-এর dept_id NULL), departments (dept_id, name, building — CSE, EEE, BBA, English) আর enrollments (student_id, course_id, term, grade — ১৩টি ভর্তি)। মাঝে মাঝে instructors (instructor_id, name, dept_id, salary, mentor_id) আর courses (course_id, title, dept_id, credits, instructor_id) লাগবে। প্রতিটি লাইভ এডিটরের নিচে “নমুনা ডেটা” বাক্সে পুরো ডেটা দেখা যায়।

২ · Selection σ — কোন সারি থাকবে

Selection একটি relation থেকে সেই tuple-গুলো রাখে, যেগুলো একটি শর্ত পূরণ করে। শর্তটিকে বলে predicate. লেখা হয় গ্রিক অক্ষর σ (সিগমা) দিয়ে, শর্তটি নিচে ছোট করে:

Predicate-এ থাকে attribute, ধ্রুব মান, তুলনা (=, ≠, <, ≤, >, ≥) আর যুক্তির সংযোগ ∧ (AND), ∨ (OR), ¬ (NOT). যেমন σ_{dept_id = 1 ∧ cgpa > 3.5}(students) মানে “CSE-র যেসব শিক্ষার্থীর cgpa 3.5-এর বেশি”. ফলের schema হুবহু ইনপুটের মতো, শুধু সারি কম বা সমান: |σ_p(R)| ≤ |R|. SQL-এ এটিই WHERE.

খাঁটি relational algebra-য় NULL নেই। Codd পরে NULL আর তিন-মানের যুক্তি যোগ করেন, আর SQL সেটি নিয়েছে। SQL-এর σ তাই “predicate TRUE হলে রাখো” — FALSE আর UNKNOWN দুটিই বাদ। এখন দুটি গুরুত্বপূর্ণ নিয়ম।

এই নিয়মের ব্যবহারিক মানে: একটি বড় শর্তকে টুকরো করা যায়, আর টুকরোগুলো যেকোনো ক্রমে, এমনকি গাছের ভিন্ন ভিন্ন জায়গায় বসানো যায়। অংশ ৮-এ ঠিক এটিই কাজে লাগবে।

∨-এর জন্যও একটি সম্পর্ক আছে: σ_{p ∨ q}(R) = σ_p(R) ∪ σ_q(R). প্রমাণ একই ধাঁচের: t বাঁ পাশে ⇔ t ∈ R এবং (p(t) অথবা q(t)) ⇔ (t ∈ R এবং p(t)) অথবা (t ∈ R এবং q(t)) ⇔ t ডান পাশে। ∎ একইভাবে σ_¬p(R) = R − σ_p(R), তবে শুধু খাঁটি দুই-মানের যুক্তিতে। SQL-এ p UNKNOWN হলে সারিটি দুই দিকেই বাদ পড়ে, তাই ডান পাশে NULL-ওয়ালা সারি বাড়তি থেকে যায় — নিচের তৃতীয় কোয়েরি ঠিক এটিই দেখায়। নিচের এডিটরে প্রথম দুটি কোয়েরি এই দুই রূপ, তৃতীয়টি ∨ আর ¬-এর উদাহরণ।

-- σ dept_id = 1 ∧ cgpa > 3.5 (students)
SELECT * FROM students WHERE dept_id = 1 AND cgpa > 3.5;

-- cascade: σ dept_id = 1 ( σ cgpa > 3.5 (students) )
SELECT * FROM (SELECT * FROM students WHERE cgpa > 3.5)
WHERE dept_id = 1;

-- σ ¬(dept_id = 1 ∨ dept_id = 2) (students)
SELECT student_id, name, dept_id FROM students
WHERE NOT (dept_id = 1 OR dept_id = 2);

৩ · Projection π — কোন কলাম থাকবে (আর duplicate কেন যায়)

Projection সারি নয়, কলাম বাছে। π (পাই)-এর নিচে attribute-এর একটি তালিকা L লেখা হয়: π_{name, cgpa}(students) মানে প্রতিটি tuple থেকে শুধু name আর cgpa রাখা।

এখানে t[L] মানে tuple t-এর শুধু L-এর অংশ। সংজ্ঞাটি একটি set, আর set-এ একই জিনিস দুবার থাকে না। তাই কলাম কেটে ফেলার পর দুটি tuple একই হয়ে গেলে ফলে সেটি একবারই আসে। π_batch(students)-এ ৮ জন শিক্ষার্থী আছেন, কিন্তু batch মাত্র তিনটি: 2021, 2022, 2023. ফল তাই ৩টি tuple. সাধারণভাবে |π_L(R)| ≤ |R|, আর সমান হওয়া নিশ্চিত যদি L-এর মধ্যে একটি superkey থাকে — তখন দুটি tuple কখনো L-এ মিলতে পারে না।

SQL এখানে algebra থেকে সরে গেছে। SQL-এর টেবিল একটি multiset (bag), আর সাধারণ SELECT duplicate রাখে। এই আচরণকে বলে bag semantics. Algebra-র π-এর হুবহু SQL রূপ তাই SELECT DISTINCT, শুধু SELECT নয়।

-- SQL-এর bag: duplicate থাকে
SELECT batch FROM students;

-- algebra-র π batch (students): set, duplicate নেই
SELECT DISTINCT batch FROM students;

-- π dept_id, batch (students)
SELECT DISTINCT dept_id, batch FROM students;

কেন SQL duplicate রাখে? প্রথম কারণ খরচ: duplicate মুছতে sort বা hash লাগে। দ্বিতীয় কারণ অর্থ: গড় cgpa বের করতে একই cgpa-র দুজনকেই লাগে। তবে মনে রাখুন, set আর bag-এ কিছু নিয়ম আলাদা। যেমন set-এ R ∪ R = R, কিন্তু bag-এ UNION ALL দিলে প্রতিটি সারি দ্বিগুণ হয়। Optimizer তাই প্রতিটি rule bag-এ খাটে কি না দেখে নেয়।

Projection-এর দুটি নিয়ম। Cascade: L₁ ⊆ L₂ হলে π_L1(π_L2(R)) = π_L1(R) — শুধু শেষ projection-টিই গুরুত্বপূর্ণ। σ-এর সাথে অদলবদল: p-তে ব্যবহৃত সব attribute L-এ থাকলে π_L(σ_p(R)) = σ_p(π_L(R)). শর্তটি জরুরি: π_name(σ_{cgpa > 3.5}(students)) ঠিক আছে, কিন্তু σ_{cgpa > 3.5}(π_name(students)) অর্থহীন, কারণ π-এর পর cgpa কলামটিই নেই।

৪ · Set অপারেটর — ∪, − আর ∩

Relation যেহেতু set, তাই set-এর তিনটি পুরোনো অপারেশন সরাসরি চলে। পর্ব ২২-এ এদের SQL রূপ UNION, EXCEPT আর INTERSECT দেখেছেন। এখানে সংজ্ঞা:

• R ∪ S = { t | t ∈ R অথবা t ∈ S } — union
• R − S = { t | t ∈ R এবং t ∉ S } — set difference
• R ∩ S = { t | t ∈ R এবং t ∈ S } — intersection

একটি শর্ত ছাড়া এগুলো অর্থহীন: R আর S union-compatible হতে হবে। অর্থাৎ দুটির attribute-এর সংখ্যা (degree) সমান, আর i-তম attribute-এর domain দুই পাশে এক। π_{student_id}(students) ∪ π_{course_id}(courses) union-compatible নয়: দুই পাশে একটি করে কলাম, কিন্তু একটি শিক্ষার্থীর id, আরেকটি কোর্সের কোড। ফলের attribute-এর নাম প্রথা অনুযায়ী বাঁ পাশ থেকে আসে।

দুই পাশের attribute-এর অর্থ এক কিন্তু নাম আলাদা হলে ρ দিয়ে নাম মিলিয়ে নেওয়াই পরিষ্কার রীতি। ধরুন বিশ্ববিদ্যালয়ের সমাবর্তনের আমন্ত্রণপত্রের জন্য সব শিক্ষার্থী আর শিক্ষকের id একটি তালিকায় চাই:

ρP(person_id)(πstudent_id(students)) ∪ ρP(person_id)(πinstructor_id(instructors))

দুই পাশেই এখন একটি attribute, নাম person_id, domain পূর্ণসংখ্যার id. তবে লক্ষ করুন, union-compatibility শুধু গঠনের নিয়ম; একটি শিক্ষার্থীর id আর একজন শিক্ষকের id একই সংখ্যা হলে ∪ তাদের এক করে ফেলবে। অর্থ ঠিক আছে কি না, তা নিয়ম দেখে না — লেখককে দেখতে হয়।

-- π student_id (σ course_id='CSE301' (enrollments))
--   ∪ π student_id (σ course_id='CSE101' (enrollments))
SELECT student_id FROM enrollments WHERE course_id = 'CSE301'
UNION
SELECT student_id FROM enrollments WHERE course_id = 'CSE101';

-- bag রূপ: duplicate থাকে
SELECT student_id FROM enrollments WHERE course_id = 'CSE301'
UNION ALL
SELECT student_id FROM enrollments WHERE course_id = 'CSE101';

∪ আর ∩ commutative আর associative: R ∪ S = S ∪ R, (R ∪ S) ∪ T = R ∪ (S ∪ T). কিন্তু − দুটির কোনোটিই নয়। R − S আর S − R সাধারণত আলাদা, আর (R − S) − T ≠ R − (S − T). “কোন শিক্ষার্থী কোনো কোর্সেই ভর্তি হননি?” — এর উত্তর difference দিয়ে:

πstudent_id(students) − πstudent_id(enrollments)

∩ আসলে − দিয়েই লেখা যায়

-- π student_id (students) − π student_id (enrollments)
SELECT student_id FROM students
EXCEPT
SELECT student_id FROM enrollments;

-- R ∩ S সরাসরি
SELECT student_id FROM enrollments WHERE course_id = 'CSE101'
INTERSECT
SELECT student_id FROM enrollments WHERE course_id = 'CSE201';

-- R − (R − S): ভেতরের অংশ subquery-তে, কারণ SQLite বাঁ থেকে ডানে চলে
SELECT student_id FROM enrollments WHERE course_id = 'CSE101'
EXCEPT
SELECT * FROM (SELECT student_id FROM enrollments WHERE course_id = 'CSE101'
               EXCEPT
               SELECT student_id FROM enrollments WHERE course_id = 'CSE201');

৫ · Cartesian product × আর rename ρ

এ পর্যন্ত প্রতিটি অপারেটর একটি relation-এর ভেতরে কাজ করেছে, অথবা একই আকারের দুটি relation মিলিয়েছে। কিন্তু “Arif কোন বিভাগের, সেই বিভাগ কোন ভবনে?” — এমন প্রশ্নে দুটি ভিন্ন relation-এর তথ্য একই tuple-এ আনতে হয়। এর মৌলিক অপারেটর Cartesian product:

অর্থাৎ R-এর প্রতিটি tuple S-এর প্রতিটি tuple-এর সাথে জোড়া লাগে (r ⧺ s মানে দুটি tuple পাশাপাশি জুড়ে একটি লম্বা tuple). R-এর degree m আর S-এর n হলে ফলের degree m + n. সারির সংখ্যা ঠিক |R| × |S|. students (৮) × departments (৪) = ৩২টি tuple, যার বেশিরভাগই অর্থহীন জোড়া (Arif-এর পাশে EEE, BBA, English…)। তাই × প্রায় সবসময় একটি σ-এর সাথে আসে, যা ঠিক জোড়াগুলো রাখে: σ_{students.dept_id = departments.dept_id}(students × departments). এই জোড়াটিকেই পরের পর্বে join ⋈ নাম দেওয়া হবে। SQL-এ × হলো CROSS JOIN, বা FROM-এ কমা দিয়ে দুটি টেবিল।

-- π name (σ batch=2023 (students)) × π name (σ dept_id=1 (instructors))
SELECT s.name AS student, i.name AS instructor
FROM (SELECT name FROM students WHERE batch = 2023) AS s
CROSS JOIN (SELECT name FROM instructors WHERE dept_id = 1) AS i;

-- |students × departments| = 8 × 4
SELECT COUNT(*) AS rows_in_product FROM students CROSS JOIN departments;

Rename ρ — একই relation দুবার লাগলে

উপরের এডিটরে দুই পাশেই name নামে কলাম ছিল, তাই AS দিয়ে আলাদা নাম দিতে হয়েছে। Algebra-তে একই সমস্যা আছে: × করলে দুই পাশের একই নামের attribute আলাদা করতে হয়। কখনো আবার একই relation-কে নিজের সাথেই জোড়া লাগাতে হয়। এর জন্য rename অপারেটর ρ (রো):

• ρ_S(R) — relation R-কে S নামে ডাকা। তার attribute হয় S.A, S.B, …
• ρ_{S(B1, …, Bn)}(R) — relation-এর সাথে attribute-এর নামও বদলানো।

ρ ফলের tuple বদলায় না, শুধু নাম বদলায়; তবু এটি ছাড়া কিছু প্রশ্ন লেখাই যায় না। একটি ক্লাসিক উদাহরণ: aggregate ফাংশন ছাড়া সর্বোচ্চ cgpa বের করা। কৌশল: “যার চেয়ে বড় কোনো cgpa আছে” এমন সব cgpa বের করুন, তারপর সব cgpa থেকে সেগুলো বাদ দিন। যা থাকে, তার চেয়ে বড় কেউ নেই।

πcgpa(students) − πs.cgpa(σs.cgpa < t.cgpa(ρs(students) × ρt(students)))

-- সর্বোচ্চ cgpa, MAX ছাড়া: ρ দিয়ে students-কে দুবার
SELECT cgpa FROM students WHERE cgpa IS NOT NULL
EXCEPT
SELECT s.cgpa FROM students AS s CROSS JOIN students AS t
WHERE s.cgpa < t.cgpa;

-- NULL-এর শর্তটি বাদ দিলে কী হয়?
SELECT cgpa FROM students
EXCEPT
SELECT s.cgpa FROM students AS s CROSS JOIN students AS t
WHERE s.cgpa < t.cgpa;

৬ · মূল ছয়টি অপারেটর, derived অপারেটর আর SQL-এর সাথে মিল

পাঠ্যবইয়ে relational algebra-র মূল (primitive) অপারেটর ধরা হয় ছয়টি: {σ, π, ∪, −, ×, ρ}. “মূল” মানে দুটি কথা। এক, বাকি সব অপারেটর এদের দিয়ে লেখা যায়। দুই, এদের কোনোটিকে বাকি পাঁচটি দিয়ে লেখা যায় না। যেমন − কেন অপরিহার্য? বাকি পাঁচটি monotone: ইনপুটে tuple বাড়ালে ফলের tuple কখনো কমে না। কিন্তু R − S-এ S বড় করলে ফল ছোট হয়। monotone অপারেটরের যেকোনো সমন্বয়ও monotone (আরোহ যুক্তিতে), তাই তারা কখনো − তৈরি করতে পারবে না। একইভাবে × ছাড়া ফলের degree কখনো বাড়ানো যায় না, তাই × অপরিহার্য।

বাকিগুলো derived অপারেটর: এরা নতুন ক্ষমতা আনে না, শুধু লেখা ছোট করে, আর DBMS এদের জন্য দ্রুত অ্যালগরিদম রাখে।

ফলের আকার — degree আর cardinality

পরীক্ষায় প্রায়ই জিজ্ঞেস করা হয়: “R-এর degree m আর |R| = r, S-এর degree n আর |S| = s হলে ফলের degree আর সারির সংখ্যা কত?” প্রতিটি অপারেটরের সংজ্ঞা থেকেই উত্তর আসে। সারির সংখ্যার ক্ষেত্রে বেশিরভাগ অপারেটরের শুধু একটি সীমা বলা যায়, নির্দিষ্ট সংখ্যা নয় — নির্দিষ্ট সংখ্যা ডেটার ওপর নির্ভর করে।

যেমন ∪-এর সর্বনিম্ন max(r, s), কারণ বড়টির সব tuple ফলে থাকবেই; সর্বোচ্চ r + s, যখন দুই পাশে কোনো সাধারণ tuple নেই। এই সীমাগুলো শুধু পরীক্ষার জন্য নয় — optimizer মাঝের relation-এর আকার অনুমান করতে ঠিক এই যুক্তি দিয়ে শুরু করে।

Relational algebra ↔ SQL

সবচেয়ে কাজের সূত্রটি হলো সাধারণ SELECT-এর অনুবাদ। SELECT DISTINCT A1, …, Ak FROM R1, …, Rm WHERE p মানে:

এটি পর্ব ১৫-এর logical processing order-এর গণিত রূপ: আগে FROM (×), তারপর WHERE (σ), শেষে SELECT (π)। ORDER BY, LIMIT, GROUP BY আর aggregate ফাংশন মূল algebra-য় নেই। ক্রম relation-এর ধারণার বাইরে, আর গোনা-যোগের জন্য পাঠ্যবইয়ে একটি বাড়তি অপারেটর γ (grouping) নিয়ে extended relational algebra বানানো হয়।

৭ · Expression tree — প্রশ্ন থেকে গাছ, গাছ থেকে উত্তর

Closure-এর কারণে প্রতিটি algebra expression একটি গাছ: পাতায় (leaf) মূল relation, প্রতিটি ভেতরের node-এ একটি অপারেটর, আর প্রতিটি node-এর ফল তার ওপরের node-এর ইনপুট। একে বলে expression tree (বা query tree). গাছটি নিচ থেকে ওপরে হিসাব হয়। প্রতিটি node-এর ফলকে বলে intermediate result. প্রশ্নটি নিন: “CSE বিভাগের যেসব শিক্ষার্থীর cgpa 3.5-এর বেশি, তাঁদের নাম।”

-- গাছটি হুবহু: π( σ( σ( ρs(students) × ρd(departments) ) ) )
SELECT DISTINCT s.name
FROM students AS s CROSS JOIN departments AS d
WHERE s.dept_id = d.dept_id
  AND d.name = 'CSE'
  AND s.cgpa > 3.5;

গাছ নিচ থেকে ওপরে হিসাব করার ক্রমটি আসলে tree-র post-order traversal: আগে দুই সন্তান, তারপর নিজে। তবে একটি কথা মনে রাখুন। ডায়াগ্রামে প্রতিটি মাঝের relation পুরোটা লিখে দেখানো হয়েছে, কিন্তু বাস্তব DBMS সাধারণত তা করে না। × বা join থেকে একটি tuple বেরোলেই সেটি সাথে সাথে ওপরের σ-এ যায়, তারপর π-এ, আর ফলের প্রথম সারি তৈরি হয়ে যায় — পুরো ৩২টি সারি কোথাও জমা থাকে না। একে বলে pipelining; পর্ব ৪২-এ দেখবেন কোন অপারেটর এভাবে চলতে পারে (σ, π) আর কোনটিকে আগে সব ইনপুট পড়তে হয় (sort, duplicate মোছা)। Algebra বলে কী হিসাব হবে; কীভাবে, তা ইঞ্জিনের সিদ্ধান্ত।

Assignment ← — লম্বা expression-কে ধাপে ভাঙা

এক লাইনের expression বড় হলে পড়া কঠিন। তাই algebra-তে একটি assignment চিহ্ন আছে: T ← E মানে “E-এর ফলকে T নামে একটি অস্থায়ী relation হিসেবে রাখো”। এটি নতুন কোনো ক্ষমতা আনে না, শুধু নাম দিয়ে ধাপ সাজায় — ঠিক প্রোগ্রামিংয়ের অস্থায়ী variable-এর মতো। একই প্রশ্ন এবার ধাপে ধাপে, selection-গুলো আগে বসিয়ে:

CSE    ← σname = 'CSE'(departments)
Good   ← σcgpa > 3.5(students)
Pairs  ← ρP(sname, sdept, ddept)(πGood.name, Good.dept_id, CSE.dept_id(Good × CSE))
Result ← πsname(σsdept = ddept(Pairs))

SQL-এ এর সবচেয়ে কাছের রূপ CTE (পর্ব ২৫): প্রতিটি WITH name AS (…) একটি ←.

-- প্রতিটি WITH = একটি ←
WITH cse   AS (SELECT * FROM departments WHERE name = 'CSE'),
     good  AS (SELECT * FROM students WHERE cgpa > 3.5),
     pairs AS (SELECT good.name AS sname, good.dept_id AS sdept,
                      cse.dept_id AS ddept
               FROM good CROSS JOIN cse)
SELECT DISTINCT sname FROM pairs WHERE sdept = ddept;

৮ · Equivalence rule — selection নিচে নামালে খরচ কমে

দুটি expression equivalent (E₁ ≡ E₂) যদি ডেটাবেসের যেকোনো অবস্থায় দুটি একই relation দেয় — শুধু আজকের ডেটায় নয়। Optimizer এমন নিয়মের একটি তালিকা রাখে আর গাছ বদলাতে সেগুলো প্রয়োগ করে। প্রধান কয়েকটি:

নিয়ম ৪-এর প্রমাণ। E₁ × E₂-এর প্রতিটি tuple হলো r ⧺ s, যেখানে r ∈ E₁, s ∈ E₂. p শুধু E₁-এর attribute দেখে, তাই p(r ⧺ s) = p(r). তাহলে r ⧺ s ∈ σ_p(E₁ × E₂) ⇔ r ∈ E₁, s ∈ E₂, p(r) ⇔ r ∈ σ_p(E₁), s ∈ E₂ ⇔ r ⧺ s ∈ σ_p(E₁) × E₂. ∎ নিয়ম ৭ − -এ কেন খাটে না: R(A, B) = {(1, 2)}, S(A, B) = {(1, 3)} নিন। π_A(R − S) = π_A({(1, 2)}) = {1}, কিন্তু π_A(R) − π_A(S) = {1} − {1} = ∅. একটি counterexample-ই যথেষ্ট।

নিয়ম ১ আর ৪ মিলিয়ে optimizer-এর সবচেয়ে পুরোনো কৌশল: selection-কে যত নিচে সম্ভব নামানো (predicate pushdown). কারণ × আর join-এর খরচ ইনপুটের আকারের গুণফলের ওপর নির্ভর করে। ইনপুট ছোট করলে পুরো গাছ সস্তা হয়।

-- সরল গাছের ×
SELECT COUNT(*) AS naive_rows FROM students CROSS JOIN departments;

-- selection নামানোর পর ×
SELECT COUNT(*) AS pushed_rows
FROM (SELECT * FROM students WHERE cgpa > 3.5)
CROSS JOIN (SELECT * FROM departments WHERE name = 'CSE');

একটি হিসাব মনে রাখুন। × এর আউটপুট ঠিক |R| · |S|. σ_p(R)-এর আকার |R|-এর একটি ভগ্নাংশ, যাকে বলে selectivity: p যত কম সারি রাখে, selectivity তত ছোট, আর নামানোর লাভ তত বড়। একই যুক্তিতে projection-ও নিচে নামানো যায় (দরকারি কলাম আগেই রেখে), যাতে প্রতিটি মাঝের tuple ছোট হয়। তবে যেকোনো জায়গায় নয় — ওপরের কোনো শর্ত বা জোড়ায় যে কলাম লাগবে, তা রাখতেই হবে।

৯ · পরীক্ষার ধাঁচে — ইংরেজি প্রশ্ন থেকে algebra

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় প্রচলিত ধরন হলো: একটি schema দেওয়া থাকে, আর কয়েকটি ইংরেজি প্রশ্নের relational algebra লিখতে হয়। একটি নিয়মিত পদ্ধতি মেনে চলুন: (১) কোন attribute দেখাতে হবে → শেষে π; (২) তথ্য কোন relation-এ → পাতা; (৩) একাধিক relation হলে × আর জোড়ার σ; (৪) প্রশ্নের শর্ত → σ; (৫) “কখনো না”, “কেউ না” → −; “দুটিতেই” → ∩; “অথবা” দুই উৎস থেকে → ∪. Schema: students(student_id, name, dept_id, batch, cgpa), enrollments(student_id, course_id, term, grade), instructors(instructor_id, name, dept_id, salary, mentor_id), courses(course_id, title, dept_id, credits, instructor_id).

1. Find the ids of students who enrolled in both CSE201 and CSE301.
   

   πstudent_id(σcourse_id='CSE201'(enrollments)) ∩ πstudent_id(σcourse_id='CSE301'(enrollments))

   সাধারণ ভুল: σ_{course_id='CSE201' ∧ course_id='CSE301'}(enrollments). একটি tuple-এর course_id একসাথে দুটি হতে পারে না, তাই ফল সবসময় খালি।
2. Find the names of students who got grade A in some course.
   

   πname(σstudents.student_id = enrollments.student_id ∧ grade='A'(students × enrollments))

   “some course” মানে অন্তত একটি; π-এর duplicate মোছা নিশ্চিত করে যে দুবার A পাওয়া শিক্ষার্থীর নাম একবারই আসে।
3. Find the ids and names of instructors who teach no course.
   

   πinstructor_id, name(instructors) − πinstructor_id, name(σinstructors.instructor_id = courses.instructor_id(instructors × courses))

   সাধারণ ভুল: π_name(instructors) − π_{instructor_id}(courses). দুই পাশ union-compatible নয় — একটি নাম, আরেকটি সংখ্যা। − এর দুই পাশে একই attribute রাখুন, তারপর দরকার হলে ওপরে π.
4. Find the highest cgpa. অংশ ৫-এর ρ-ওয়ালা expression. পরীক্ষায় aggregate নিষেধ থাকলে এটিই প্রত্যাশিত উত্তর।
5. Find all pairs of student ids (a, b) where a and b are in the same department.
   

   πs1.student_id, s2.student_id(σs1.dept_id = s2.dept_id ∧ s1.student_id < s2.student_id(ρs1(students) × ρs2(students)))

   এখানে ρ ছাড়া উপায় নেই, কারণ একই relation-এর দুটি কপি লাগছে। s1.student_id < s2.student_id শর্তটি দুটি কাজ করে: নিজের সাথে নিজের জোড়া (2101, 2101) বাদ দেয়, আর (2101, 2102) ও (2102, 2101)-এর একটিই রাখে। db-uni-তে ফল ৭টি জোড়া: CSE-র চারজনের ৬টি, EEE-র দুজনের ১টি। BBA-তে একজন, তাই জোড়া নেই; Habib-এর dept_id NULL, তাই তিনি কারও সাথে মেলেন না।
6. Find the ids of students who are in the EEE department (dept_id = 2) or enrolled in BBA101.
   

   πstudent_id(σdept_id = 2(students)) ∪ πstudent_id(σcourse_id = 'BBA101'(enrollments))

   দুটি আলাদা relation থেকে আসা “অথবা”, তাই ∪; দুই পাশ π_{student_id} করে union-compatible বানানো হয়েছে। উত্তর {2103, 2203, 2202}. একটি σ-এর ভেতরে ∨ দিয়ে লেখা যেত না, কারণ dept_id আর course_id একই relation-এ নেই।

-- প্রশ্ন ১: ∩
SELECT student_id FROM enrollments WHERE course_id = 'CSE201'
INTERSECT
SELECT student_id FROM enrollments WHERE course_id = 'CSE301';

-- প্রশ্ন ২: π(σ(×))
SELECT DISTINCT s.name FROM students s CROSS JOIN enrollments e
WHERE s.student_id = e.student_id AND e.grade = 'A';

-- প্রশ্ন ৩: −
SELECT instructor_id, name FROM instructors
EXCEPT
SELECT i.instructor_id, i.name FROM instructors AS i CROSS JOIN courses AS c
WHERE i.instructor_id = c.instructor_id;

১০ · AI-এর যুগে relational algebra

AI সহকারী SQL লেখে দ্রুত, আর relational algebra-র প্রশ্নের উত্তরও দেয়। কিন্তু দুই জায়গাতেই এর পরিচিত ভুল আছে। Algebra জানলে আপনি সেগুলো ধরতে পারবেন, কারণ প্রতিটি SQL-কে আপনি π(σ(×)) আকারে পড়তে পারেন:

AI-এর দেওয়া উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি relation আর attribute-এর নাম আসল schema-য় আছে; কিছু বানানো নয়
• প্রতিটি ∪, −, ∩-এর দুই পাশ union-compatible — কলামের সংখ্যা আর অর্থ একই
• SQL অনুবাদে π-এর জায়গায় DISTINCT আছে, অথবা কেন দরকার নেই বলতে পারি
• NULL-ওয়ালা আর duplicate-ওয়ালা একটি করে সারি দিয়ে নমুনা ডেটায় চালিয়েছি, সারির সংখ্যা হাতে মিলিয়েছি
• কোনো rewrite (selection নামানো, π বিতরণ) থাকলে সেটি সারণির কোন নিয়ম আর তার শর্ত পূরণ হচ্ছে কি না দেখেছি
• বড় টেবিলে EXPLAIN দেখেছি — অকারণ বিশাল × বা পুরো টেবিল scan হচ্ছে কি না