n-ary relation আর relational database-এর গণিত

১ · টেবিল মানেই relation — n-ary relation-এর সংজ্ঞা

পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive”-এ relation ছিল দুটি বস্তুর সম্পর্ক: “গ্রাহক a পণ্য b কিনেছেন”। কিন্তু বাস্তবের তথ্য প্রায়ই দুইয়ের বেশি জিনিস একসঙ্গে বাঁধে। বাজারঘরের একটি অর্ডার বলে: কোন অর্ডার নম্বর, কোন গ্রাহক, কোন পণ্য, কত পিস। এখানে চারটি জিনিস একসঙ্গে সত্য, আর এটিকে চারটি আলাদা জোড়ায় ভাঙলে তথ্য হারায়।

n = 2 হলে এটি পর্ব ৫২-এর binary relation; n = 1 হলে শুধু একটি subset; আর n = 3 হলে ternary relation. পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product”-এ Cartesian product আর ordered pair এসেছে, এখানে আমরা শুধু জোড়ার জায়গায় n-tuple নিচ্ছি। পর্ব ০৪-এর predicate-ও একই জিনিস: দুই argument-এর predicate Ord(c, o) আসলে যে জোড়াগুলোতে সত্য, তাদের সেট। একটি n-ary predicate আর একটি n-ary relation একই তথ্যের দুই রূপ।

বাজারঘরের তিনটি টেবিল এই পর্বজুড়ে চলবে। Customers-এর domain তিনটি: গ্রাহক নম্বর, নাম আর জেলা। Orders-এর চারটি: অর্ডার নম্বর, গ্রাহক নম্বর, পণ্য নম্বর, পরিমাণ।

Orders একটি 4-ary relation: Orders ⊆ OID × CID × PID × ℕ. প্রথম গণনার প্রশ্ন: একটি নির্দিষ্ট domain-এর ওপর কতগুলো আলাদা relation সম্ভব?

1. একটি n-tuple বানাতে প্রথম ঘরের জন্য |A₁|-টি উপায়, দ্বিতীয়টির জন্য |A₂|-টি, এভাবে n-টি স্বাধীন বাছাই। — গুণের নিয়ম, পর্ব ৩১
2. তাই মোট tuple N = ∏|A_i|-টি। — ধাপ ১
3. Relation মানে এই N-উপাদানের সেটের একটি subset, অর্থাৎ power set-এর একটি উপাদান। — সংজ্ঞা ১.১
4. N-উপাদানের সেটের subset 2^N-টি, কারণ প্রতিটি tuple “আছে বা নেই” এই দুই উপায়ে ঠিক হয়। ∎ — power set-এর আকার, পর্ব ১৪

উদাহরণ: |A₁| = 3, |A₂| = 4, |A₃| = 2 হলে tuple 24-টি আর ternary relation 2²⁴ = 16,777,216-টি। মাত্র তিনটি ছোট domain থেকেই প্রায় এক কোটি সাতষট্টি লাখ সম্ভাব্য টেবিল; এজন্যই একটি database-এর “সব সম্ভাব্য অবস্থা” পরীক্ষা করে কোনো নিয়ম যাচাই করা যায় না, প্রমাণ লাগে।

২ · Relational model — schema, attribute আর কেন ক্রম নেই

১৯৭০ সালে IBM-এর গবেষক Edgar F. Codd “A Relational Model of Data for Large Shared Data Banks” নামে একটি প্রবন্ধ প্রকাশ করেন (Communications of the ACM-এ)। তাঁর মূল প্রস্তাব ছিল: database-এর সব তথ্য গাণিতিক relation হিসেবে রাখা হোক, আর প্রশ্ন করা হোক সেটের অপারেশন দিয়ে, ডেটা ডিস্কে কীভাবে সাজানো আছে তা না জেনেই। এই ধারণাটিকেই relational model বলা হয়। আজকের SQL database-গুলো এই মডেলের ওপর দাঁড়িয়ে, যদিও পুরোপুরি মানে না (§৯-এ দেখবেন)।

গণিতের সংজ্ঞায় tuple-এর ঘরগুলো অবস্থান দিয়ে চেনা হয়: প্রথম, দ্বিতীয়, তৃতীয়। Database-এ প্রতিটি অবস্থানের একটি নাম থাকে, যাকে বলে attribute: cid, name, district. Attribute-এর নামসহ relation-এর কাঠামোকে বলে relation schema, যেমন Customers(cid, name, district). Schema হলো টেবিলের “মাথার সারি”, আর কোনো এক মুহূর্তের সারিগুলোর সেট হলো instance; schema অনেকদিন একই থাকে, instance প্রতিদিন বদলায়।

এই দৃষ্টিতে কলামের ক্রমও উঠে যায়: (cid = C1, name = Rahim, district = Dhaka) আর (district = Dhaka, cid = C1, name = Rahim) একই ফাংশন (পর্ব ১৬-এ দুটি ফাংশন সমান যদি প্রতিটি ইনপুটে একই মান দেয়)। আর relation একটি সেট বলে দুটি জিনিস স্বয়ংক্রিয়ভাবে আসে:

• সারির ক্রম নেই। {a, b} = {b, a}; তাই “প্রথম সারি” কথাটির কোনো গাণিতিক অর্থ নেই। SQL-এ ক্রম চাইলে ORDER BY আলাদা করে লিখতে হয়।
• একই সারি দুবার নেই। {a, a} = {a}. এটি পরের অংশে key-র অস্তিত্ব প্রমাণে কাজে লাগবে।

এই পর্বের কাজ গণিত: সংজ্ঞা, উপপাদ্য আর প্রমাণ। টেবিল বানানো, SQL লেখা আর বাস্তব database চালানো শিখতে ডেটাবেস (DBMS) ও SQL কোর্সের পর্ব ৫ “Relational model — relation, tuple, attribute আর domain” দেখুন; এখানে সেই কাজের পেছনের যুক্তিটুকু।

৩ · Key — superkey, candidate key, primary key

বাজারঘরে দুজন গ্রাহকের নাম “Rahim” হতে পারে, কিন্তু গ্রাহক নম্বর কখনো এক হবে না। যে কলাম (বা কলামের দল) দিয়ে প্রতিটি সারিকে আলাদা করে চেনা যায়, সেটিই key. এখানে একটি সূক্ষ্ম বিষয় আছে: key একটি নিয়ম, যা schema-র সব বৈধ instance-এ খাটার কথা। একটি নির্দিষ্ট দিনের টেবিলে নামগুলো আলাদা হলেও name key নয়, কারণ কাল আরেকজন Rahim আসতে পারেন। নিচের সংজ্ঞাগুলো একটি instance r-এর জন্য লেখা; schema-র key মানে এমন সেট, যা সব বৈধ instance-এ শর্ত মানে।

খেয়াল করুন, “minimal” আর “সবচেয়ে ছোট” এক কথা নয়। একটি relation-এ এক attribute-এর candidate key আর দুই attribute-এর candidate key একসঙ্গে থাকতে পারে; দুটিই minimal, কারণ কোনোটির ভেতর থেকে কিছু বাদ দেওয়া যায় না। §৮-এ এমন উদাহরণ দেখবেন।

1. (ক) t ≠ u নিন। K superkey বলে কোনো A ∈ K-তে t[A] ≠ u[A]. — সংজ্ঞা ৩.১
2. A ∈ K ⊆ L, তাই t আর u L-এর একটি attribute-এ আলাদা, অর্থাৎ t[L] ≠ u[L]. তাই L superkey. — subset-এর সংজ্ঞা
3. (খ) U নিজেই superkey: t ≠ u মানে দুটি আলাদা ফাংশন, তাই কোনো attribute-এ মান আলাদা, অর্থাৎ t[U] ≠ u[U]. এখানেই “relation একটি সেট, একই সারি দুবার নেই” কাজে লাগল। — §২
4. U সসীম, তাই এর superkey-subset-গুলোর মধ্যে সবচেয়ে কম উপাদানের একটি K আছে। K-এর কোনো proper subset-এর উপাদান আরও কম, তাই সেটি superkey নয়; অর্থাৎ K candidate key. ∎ — well-ordering, পর্ব ১১

ধাপ ৩ বলছে, SQL-এর টেবিলে (যেখানে একই সারি দুবার থাকতে পারে) উপপাদ্য (খ) ভেঙে যায়: দুটি হুবহু এক সারিকে কোনো কলাম দিয়ে আলাদা করা যায় না। গণিতের relation আর SQL-এর টেবিলের এই পার্থক্য §৯-এ আবার আসবে।

(ক) অংশটির একটি কাজের ফল আছে, যা পরীক্ষায় “K যে candidate key তা দেখান” প্রশ্নের উত্তরের ধাঁচ ঠিক করে দেয়:

1. (⇒) K candidate key হলে K − {A} একটি proper subset, তাই superkey নয়। — সংজ্ঞা
2. (⇐) ধরুন প্রতিটি K − {A} superkey নয়, কিন্তু কোনো proper subset M ⊊ K superkey. K-এর এমন একটি A নিন যা M-এ নেই; তাহলে M ⊆ K − {A}. — proper subset-এর সংজ্ঞা
3. উপপাদ্য ৩.২(ক) অনুযায়ী K − {A}-ও superkey, যা অনুমানের বিরোধী। ∎ — proof by contradiction, পর্ব ০৮

অর্থাৎ k-টি attribute-এর একটি key-র minimality দেখাতে 2^k − 2-টি proper non-empty subset পরীক্ষা লাগে না, k-টি “একটি বাদ” পরীক্ষাই যথেষ্ট। আর যদি একটি candidate key-তে k-টি attribute আর পুরো schema-য় n-টি, তাহলে ওই key-কে ধারণ করে এমন superkey ঠিক 2^n−k-টি: key-র বাইরের n − k-টি attribute প্রতিটি “নেওয়া বা না নেওয়া”। Key-গুলো ডিজাইনে কীভাবে বাছা হয়, আর foreign key ও integrity constraint-এর ব্যবহার, ডেটাবেস (DBMS) ও SQL কোর্সের পর্ব ৬ “Key আর integrity constraint”-এ আছে।

৪ · Relational algebra — selection, projection, rename আর সেটের অপারেশন

Codd-এর দ্বিতীয় বড় ধারণা: প্রশ্নগুলোও গণিত। কয়েকটি অপারেশন আছে, প্রতিটি এক বা দুটি relation নিয়ে একটি নতুন relation দেয়। ফল আবার relation বলে অপারেশনগুলো একটির ওপর আরেকটি বসিয়ে যেকোনো জটিল প্রশ্ন লেখা যায়, ঠিক যেমন +, × দিয়ে সংখ্যার রাশি লেখা যায়। এই ব্যবস্থার নাম relational algebra.

শেষ দুটি লাইন সরাসরি পর্ব ১৫ “সেটের অপারেশন — union, intersection, Venn diagram আর identity” আর পর্ব ১৪-এর Cartesian product. তাই সেখানকার সব identity এখানেও চলে: R ∪ S = S ∪ R, R − (S ∪ T) = (R − S) ∩ (R − T), ইত্যাদি। Selection-এর জন্য দুটি সহজ নিয়ম সংজ্ঞা থেকেই আসে, কারণ “c₁ আর c₂ দুটিই সত্য” মানে প্রথমে একটি দিয়ে ছেঁকে তারপর অন্যটি দিয়ে ছাঁকা:

σ_{c1 ∧ c2}(R) = σ_c1(σ_c2(R)) = σ_c2(σ_c1(R))

Projection-এ পুনরাবৃত্তি বাদ পড়াটা গণিতের দিক থেকে স্বাভাবিক, কিন্তু প্রথমবার দেখলে অবাক লাগে। Orders থেকে শুধু গ্রাহক নম্বর নিলে ৬টি অর্ডারের জায়গায় মাত্র ৩টি মান থাকে:

1(O1, C1, P1, 2)2(O2, C1, P3, 1)3(O3, C2, P2, 5)4(O4, C3, P1, 1)5(O5, C3, P4, 2)6(O6, C1, P2, 3)7ফল: π_cid(Orders)

শেষ ধাপের পর্যবেক্ষণটি একটি ছোট উপপাদ্য:

1. f(t) = t[X] একটি ফাংশন R → π_X(R), আর π-এর সংজ্ঞা অনুযায়ী এটি onto. — সংজ্ঞা ৪.১
2. Onto ফাংশনে codomain-এর আকার domain-এর চেয়ে বেশি হতে পারে না, তাই |π_X(R)| ≤ |R|. — পর্ব ১৬
3. সসীম সেটে একটি onto f-এর ক্ষেত্রে |π_X(R)| = |R| হয় ঠিক তখনই যখন f one-to-one (pigeonhole, পর্ব ৩২)। আর f one-to-one মানেই t ≠ u ⇒ t[X] ≠ u[X], অর্থাৎ X superkey. ∎ — সংজ্ঞা ৩.১

৫ · Natural join — মিলে যাওয়া সারি জোড়া দেওয়া

Orders-এ শুধু গ্রাহক নম্বর আছে, জেলা নেই; জেলা আছে Customers-এ। “কোন অর্ডার কোন জেলায় যাবে” জানতে দুটি টেবিলকে cid দিয়ে জুড়তে হবে। Cartesian product সব জোড়া দেয় (4 × 6 = 24), যার বেশিরভাগই অর্থহীন (C2-এর অর্ডারের সঙ্গে Rahim-এর ঠিকানা)। দরকার শুধু সেই জোড়া, যেখানে দুই দিকের cid এক।

সংজ্ঞাটি এভাবে লেখার সুবিধা হলো প্রমাণে সরাসরি ব্যবহার করা যায়। হিসাবের নিয়মটি সহজ: R-এর প্রতিটি সারি নিন, S-এর প্রতিটি সারির সঙ্গে মেলান, সাধারণ কলামে মিললে জুড়ে দিন। নিচে একটি ছোট উদাহরণ:

1S = (C1,Dhaka) (C2,Khulna) (C4,Sylhet)2R: (O1, C1)3R: (O3, C2)4R: (O4, C1)5R: (O7, C5)6ফল: R ⋈ S

1. (ক) কোনো সাধারণ attribute নেই, তাই যেকোনো t ∈ R আর u ∈ S জুড়ে X ∪ Y-এর একটি tuple হয়, যার X-অংশ t আর Y-অংশ u. এটিই Cartesian product. — সংজ্ঞা ৫.১
2. (খ) X = Y = X ∪ Y হলে শর্ত হয় “t ∈ R এবং t ∈ S”, অর্থাৎ t ∈ R ∩ S. — intersection-এর সংজ্ঞা
3. (গ) ফলের প্রতিটি t একটি জোড়া (t[X], t[Y]) ∈ R × S থেকে আসে, আর আলাদা t আলাদা জোড়া দেয় (X ∪ Y-এর প্রতিটি ঘর এই দুই অংশের কোনো একটিতে আছে)। তাই ফলের আকার |R × S|-এর বেশি নয়। ∎ — one-to-one ফাংশন

এবার একটি ছোট relational algebra engine. Relation রাখা হয়েছে (schema, tuple-এর সেট) জোড়া হিসেবে; select, project আর join মাত্র কয়েক লাইন, আর প্রতিটি লাইন ওপরের সংজ্ঞার সরাসরি অনুবাদ। প্রশ্ন: “ঢাকার গ্রাহকেরা কোন কোন category-র পণ্য কিনেছেন?” relational algebra-য়: π_{name, category}(σ_{district = Dhaka}(Customers ⋈ Orders ⋈ Products)). প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def select(r, pred):                    # sigma: keep rows where pred holds
    A, rows = r
    return A, {t for t in rows if pred(dict(zip(A, t)))}

def project(r, keep):                   # pi: keep columns, a set drops repeats
    A, rows = r
    return tuple(keep), {tuple(t[A.index(a)] for a in keep) for t in rows}

def join(r, s):                         # natural join on shared attributes
    (A, R), (B, S) = r, s
    common = [a for a in A if a in B]
    extra = [b for b in B if b not in A]
    out = {t + tuple(u[B.index(b)] for b in extra)
           for t in R for u in S
           if all(t[A.index(c)] == u[B.index(c)] for c in common)}
    return A + tuple(extra), out

cust = (("cid", "name", "district"), {("C1", "Rahim", "Dhaka"),
        ("C2", "Karim", "Khulna"), ("C3", "Sumi", "Dhaka"), ("C4", "Nila", "Sylhet")})
prod = (("pid", "pname", "category"), {("P1", "Tea", "grocery"),
        ("P2", "Rice", "grocery"), ("P3", "Fan", "electronics"), ("P4", "Lamp", "electronics")})
orders = (("oid", "cid", "pid", "qty"), {("O1", "C1", "P1", 2), ("O2", "C1", "P3", 1),
          ("O3", "C2", "P2", 5), ("O4", "C3", "P1", 1), ("O5", "C3", "P4", 2), ("O6", "C1", "P2", 3)})

big = join(join(cust, orders), prod)
print("schema:", big[0])
print("|cust|, |orders|, |big| =", len(cust[1]), len(orders[1]), len(big[1]))
dhaka = select(big, lambda t: t["district"] == "Dhaka")
ans = project(dhaka, ["name", "category"])
print(ans[0])
for row in sorted(ans[1]):
    print("  ", row)
print("pi_cid(orders):", sorted(project(orders, ["cid"])[1]))
print("never ordered:", sorted(project(cust, ["cid"])[1] - project(orders, ["cid"])[1]))

schema: ('cid', 'name', 'district', 'oid', 'pid', 'qty', 'pname', 'category')
|cust|, |orders|, |big| = 4 6 6
('name', 'category')
   ('Rahim', 'electronics')
   ('Rahim', 'grocery')
   ('Sumi', 'electronics')
   ('Sumi', 'grocery')
pi_cid(orders): [('C1',), ('C2',), ('C3',)]
never ordered: [('C4',)]

৬ · বীজগণিতের সমীকরণ আর query optimisation

একই প্রশ্ন বিভিন্ন রাশিতে লেখা যায়, যেমন 3 × (4 + 5) আর 3 × 4 + 3 × 5. ফল একই, কিন্তু খরচ আলাদা হতে পারে। Database-এর query optimizer ঠিক এই কাজ করে: আপনার লেখা query-কে relational algebra-য় অনুবাদ করে, তারপর প্রমাণিত সমীকরণ (equivalence rule) দিয়ে এমন একটি সমতুল্য রাশিতে বদলায়, যা কম খরচে চলে। “সমতুল্য” মানে: যেকোনো instance-এ দুই রাশির ফল একই relation. সবচেয়ে গুরুত্বপূর্ণ নিয়মটি হলো selection pushdown: আগে ছাঁকুন, পরে জোড়া দিন।

দুটি সেট সমান দেখাতে দুই দিকের subset দেখাতে হয়, যাকে পর্ব ১৪-এ double inclusion বলা হয়েছে। মূল পর্যবেক্ষণ: c শুধু X-এর ঘর দেখে, তাই X ∪ Y-এর একটি tuple t-এর জন্য c(t) আর c(t[X]) একই কথা।

1. (⊆) t ∈ σ_c(R ⋈ S) নিন। তাহলে t ∈ R ⋈ S আর c(t) সত্য। — σ-এর সংজ্ঞা
2. t ∈ R ⋈ S থেকে t[X] ∈ R আর t[Y] ∈ S. — সংজ্ঞা ৫.১
3. c শুধু X-এর attribute দেখে, তাই c(t[X]) = c(t) সত্য; সুতরাং t[X] ∈ σ_c(R). — অনুমান আর σ-এর সংজ্ঞা
4. t[X] ∈ σ_c(R) আর t[Y] ∈ S, তাই t ∈ σ_c(R) ⋈ S. — সংজ্ঞা ৫.১, σ_c(R)-এর schema-ও X
5. (⊇) t ∈ σ_c(R) ⋈ S নিন। তাহলে t[X] ∈ σ_c(R), অর্থাৎ t[X] ∈ R আর c(t[X]) সত্য; আর t[Y] ∈ S. — দুই সংজ্ঞা
6. t[X] ∈ R আর t[Y] ∈ S বলে t ∈ R ⋈ S; আর c(t) = c(t[X]) সত্য, তাই t ∈ σ_c(R ⋈ S). ∎ — ধাপ ৩-এর একই পর্যবেক্ষণ

অনুমানটি কোথায় লেগেছে দেখুন: ধাপ ৩ আর ৬. শর্ত যদি S-এর কোনো attribute দেখে (যেমন category = 'grocery' আর R = Customers), তাহলে σ_c(R) লেখাই যায় না, কারণ R-এ ওই কলাম নেই। তখন শর্তটি S-এর দিকে নামাতে হয়। আর যে শর্ত দুই দিকের attribute একসঙ্গে দেখে, তা নামানো যায় না।

কিছু সমীকরণ দেখতে স্বাভাবিক, কিন্তু মিথ্যা। নিচের প্রমাণটি পড়ে ভুল ধরার চেষ্টা করুন:

নিচের ব্লক দুটি দাবিই এলোমেলো ছোট টেবিলে পরীক্ষা করে: pushdown প্রতিবার সত্য কি না, কাজ কতটা কমে, আর projection-difference সমীকরণ কতবার ভাঙে।

import random
random.seed(53)

def table(n):                           # n random pairs over {0,1,2,3}
    return {(random.randrange(4), random.randrange(4)) for _ in range(n)}

def join_ab_bc(R, S):                   # R(a,b) natural join S(b,c)
    return {(a, b, c) for (a, b) in R for (b2, c) in S if b == b2}

ok = bad = work_before = work_after = 0
first_bad = None
for trial in range(500):
    R, S = table(random.randint(0, 8)), table(random.randint(0, 8))
    cond = lambda a: a >= 2             # condition uses only R's attribute a
    left = {t for t in join_ab_bc(R, S) if cond(t[0])}
    sR = {(a, b) for (a, b) in R if cond(a)}
    right = join_ab_bc(sR, S)
    ok += left == right
    work_before += len(R) * len(S)      # pairs compared before pushdown
    work_after += len(sR) * len(S)      # pairs compared after pushdown
    T = table(random.randint(0, 8))     # projection vs difference
    lhs = {a for (a, b) in R - T}
    rhs = {a for (a, b) in R} - {a for (a, b) in T}
    if lhs != rhs:
        bad += 1
        if first_bad is None:
            first_bad = (sorted(R), sorted(T), lhs, rhs)
print("pushdown equal in", ok, "of 500 trials")
print("pairs compared: before", work_before, " after", work_after)
print("pi(R - T) != pi(R) - pi(T) in", bad, "of 500 trials")
R, T, lhs, rhs = first_bad
print("example R =", R)
print("        T =", T)
print("pi_a(R - T) =", sorted(lhs), " pi_a(R) - pi_a(T) =", sorted(rhs))

pushdown equal in 500 of 500 trials
pairs compared: before 6148  after 3139
pi(R - T) != pi(R) - pi(T) in 302 of 500 trials
example R = [(0, 0), (2, 3), (3, 3)]
        T = [(0, 2), (1, 3)]
pi_a(R - T) = [0, 2, 3]  pi_a(R) - pi_a(T) = [2, 3]

Optimizer-এর কাজের বাকি অংশ, যেমন খরচ অনুমান, statistics আর join-এর ক্রম বাছাই, ডেটাবেস (DBMS) ও SQL কোর্সের পর্ব ৪৩ “Query optimization — cost, statistics আর plan”-এ; অপারেশনগুলোর আরও উদাহরণ পর্ব ৩২ আর পর্ব ৩৩-এ।

৭ · Functional dependency আর Armstrong-এর axiom

বাজারঘরের নিয়ম: একটি অর্ডার একজন গ্রাহকেরই; একজন গ্রাহকের একটিই জেলা; একটি পণ্যের একটিই category. এগুলো টেবিলের “বাক্য” নয়, টেবিলের ওপর শর্ত। এমন শর্তের গাণিতিক রূপের নাম functional dependency.

উদাহরণ: OrderLine(oid, cid, district, pid, category, qty) টেবিলে oid → cid, cid → district, pid → category আর {oid, pid} → qty. Superkey-কেও এই ভাষায় লেখা যায়: K superkey ⇔ K → U খাটে (দুটি tuple K-তে মিললে পুরো সারিতে মেলে, অর্থাৎ একই সারি)। একটি FD যদি সব instance-এ নিজে থেকেই খাটে, যেমন {oid, pid} → oid, তাকে বলে trivial FD; এটি ঠিক তখনই হয় যখন Y ⊆ X.

প্রশ্ন হলো: কয়েকটি FD জানা থাকলে আর কোন কোন FD নিশ্চিতভাবে খাটে? যেমন oid → cid আর cid → district থেকে oid → district আসা উচিত। William W. Armstrong ১৯৭৪ সালের একটি প্রবন্ধে তিনটি নিয়ম দেন বলে জানা যায়, যা আজ Armstrong-এর axiom নামে পরিচিত:

“Sound” মানে নিয়মগুলো কখনো মিথ্যা FD দেয় না (পর্ব ০৬-এর soundness-এর একই অর্থ)। তিনটির প্রমাণ, প্রতিটিতে দুটি tuple t, u নিয়ে:

1. Reflexivity: t[X] = u[X] ধরুন। Y ⊆ X, তাই Y-এর প্রতিটি ঘর X-এরও ঘর, আর সেখানে মান সমান; অর্থাৎ t[Y] = u[Y]. — subset-এর সংজ্ঞা
2. Augmentation: t[XZ] = u[XZ] ধরুন। তাহলে t[X] = u[X] আর t[Z] = u[Z]. X → Y থেকে t[Y] = u[Y]. দুটি মিলে t[YZ] = u[YZ]. — X ⊆ XZ, Z ⊆ XZ
3. Transitivity: t[X] = u[X] ধরুন। X → Y থেকে t[Y] = u[Y]; তারপর Y → Z থেকে t[Z] = u[Z]. তাই X → Z. ∎ — দুবার সংজ্ঞা ৭.১

এই তিনটি থেকে আরও নিয়ম আসে: union (X → Y আর X → Z হলে X → YZ), decomposition (X → YZ হলে X → Y), pseudo-transitivity (X → Y আর WY → Z হলে WX → Z), সবই এই তিনটির ফল। উল্টো দিকের গভীর ফলটি হলো completeness: F থেকে যে FD সত্যিই আসে (F মানে এমন প্রতিটি instance-এ খাটে), তা এই তিন নিয়মে বের করা যায়। এর প্রমাণের মূল ধারণা §৮-এর শেষে।

৮ · Attribute closure — কোন attribute-গুলো নির্ধারিত, আর key খোঁজা

Armstrong-এর নিয়ম পরপর খাটিয়ে সব FD তালিকা করা যায়, কিন্তু U-তে n-টি attribute থাকলে সম্ভাব্য FD 2ⁿ · 2ⁿ-টি। কাজের প্রশ্ন সাধারণত ছোট: “X জানলে কোন কোন attribute জানা যায়?” এর উত্তরই attribute closure X⁺: F-এর অধীনে X → A আসে এমন সব attribute A-র সেট।

Algorithm থামবেই: প্রতিটি পালায় M অন্তত একটি attribute বাড়ে, নইলে থামে, আর M ⊆ U; তাই বড়জোর |U| + 1 পালা। নিচে R(A, B, C, D, E), F = {A → B, BC → D, B → C, D → E}-এ {A}⁺:

1M ← {A}2পালা ১: A → B3পালা ১: BC → D4পালা ১: B → C5পালা ১: D → E6পালা ২: BC → D7পালা ২: D → E8পালা ৩: কিছু বদলায় না

1. Sound দিক (M-এ যা ঢোকে, তা নির্ধারিত): দাবি করি প্রতিটি মুহূর্তে X → M বের করা যায়। শুরুতে M = X, reflexivity. — induction-এর ভিত্তি, পর্ব ১০
2. ধরুন X → M বের হয়, আর V → W খাটিয়ে M বাড়ল, যেখানে V ⊆ M ছিল। Reflexivity-তে M → V, transitivity-তে X → V, তারপর X → W. Union নিয়মে X → M ∪ W. — induction-এর ধাপ
3. তাই Y ⊆ M হলে X → M আর decomposition-এ X → Y. — ধাপ ২
4. Complete দিক (মূল ধারণা): ধরুন A ∉ M. দুই সারির একটি instance বানান: দুটি সারি M-এর প্রতিটি attribute-এ 0, আর বাকি সব attribute-এ একটিতে 0, অন্যটিতে 1. — counterexample গঠন
5. এই instance F-এর প্রতিটি V → W মানে: V ⊆ M না হলে দুই সারি V-তে আলাদা, শর্ত ফাঁকা অর্থে সত্য; V ⊆ M হলে algorithm থেমেছে বলে W ⊆ M, তাই W-তেও দুই সারি এক। — M আর কোনো FD-তে বাড়ে না
6. কিন্তু দুই সারি X ⊆ M-এ এক আর A-তে আলাদা, তাই এখানে X → A খাটে না। Sound নিয়ম কখনো এমন FD দিতে পারে না যা F মানে এমন একটি instance-এ মিথ্যা; তাই X → A বের হয় না। ∎ — উপপাদ্য ৭.২

ধাপ ৪–৬-এর একই দুই-সারির কৌশল থেকে Armstrong-এর নিয়মের completeness-ও আসে। আর শেষ লাইনটি key খোঁজার যন্ত্র দেয়: সব subset X ছোট থেকে বড় ক্রমে নিন, X⁺ = U হলে X superkey, আর আগে পাওয়া কোনো key-র superset না হলে X candidate key (corollary ৩.৩-এর ভাবনা)। নিচের ব্লক এটিই করে দুটি schema-তে: বাজারঘরের OrderLine আর পরীক্ষার ধাঁচের R(A, B, C, D) with F = {AB → C, C → D, D → A}.

from itertools import combinations

def closure(X, F):                      # X+ under the FDs in F
    C = set(X)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in F:
            if lhs <= C and not rhs <= C:
                C |= rhs
                changed = True
    return C

def candidate_keys(U, F):               # smallest first, skip supersets
    keys, supers = [], 0
    for k in range(1, len(U) + 1):
        for X in map(set, combinations(sorted(U), k)):
            if closure(X, F) == U:
                supers += 1
                if not any(K <= X for K in keys):
                    keys.append(X)
    return [sorted(K) for K in keys], supers

fd = lambda l, r: (set(l.split()), set(r.split()))
U1 = {"oid", "cid", "district", "pid", "category", "qty"}
F1 = [fd("oid", "cid"), fd("cid", "district"),
      fd("pid", "category"), fd("oid pid", "qty")]
print("{oid}+ =", sorted(closure({"oid"}, F1)))
print("{oid,pid}+ == U:", closure({"oid", "pid"}, F1) == U1)
print("keys, superkeys:", candidate_keys(U1, F1))
U2 = set("ABCD")
F2 = [fd("A B", "C"), fd("C", "D"), fd("D", "A")]
for X in ("A", "C", "AB", "BC", "BD"):
    print(X + "+ =", "".join(sorted(closure(set(X), F2))))
print("keys, superkeys:", candidate_keys(U2, F2))

{oid}+ = ['cid', 'district', 'oid']
{oid,pid}+ == U: True
keys, superkeys: ([['oid', 'pid']], 16)
A+ = A
C+ = ACD
AB+ = ABCD
BC+ = ABCD
BD+ = ABCD
keys, superkeys: ([['A', 'B'], ['B', 'C'], ['B', 'D']], 7)

৯ · গণিত বনাম SQL, আর পরীক্ষার অঙ্ক

এই পর্বের সব উপপাদ্য গাণিতিক relation-এর জন্য। SQL-এর টেবিল দুই জায়গায় আলাদা, আর সেটি সৎভাবে জানা দরকার।

• Bag, সেট নয়। SQL-এ একই সারি একাধিকবার থাকতে পারে, আর SELECT পুনরাবৃত্তি রাখে; DISTINCT লিখলে তবেই সেট। এই নিয়মের নাম bag semantics: টেবিল একটি multiset, যার ধারণা পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই”-এর পুনরাবৃত্তিসহ সংগ্রহের মতো। Bag-এ কিছু সেট-identity ভাঙে: সেটে R ∪ R = R, কিন্তু SQL-এর UNION ALL-এ সারি দ্বিগুণ হয়।
• NULL. অজানা মানের জন্য SQL একটি বিশেষ চিহ্ন রাখে, যা কোনো domain-এর উপাদান নয়। NULL-এর সঙ্গে তুলনার ফল TRUE বা FALSE নয়, UNKNOWN; এটিই three-valued logic. ফলে “district = 'Dhaka' অথবা district ≠ 'Dhaka'” সব সারি দেয় না, যা পর্ব ০২-এর দুই-মানের যুক্তিতে একটি tautology হতো।

from collections import Counter

rows = [("C1", "Dhaka"), ("C2", "Khulna"), ("C3", "Dhaka"),
        ("C4", None), ("C5", None)]                # None plays SQL's NULL
as_set = {d for _, d in rows}                      # algebra: projection is a set
as_bag = Counter(d for _, d in rows)               # SQL SELECT district: a bag
print("set :", len(as_set), "rows", sorted(as_set, key=str))
print("bag :", sum(as_bag.values()), "rows", dict(as_bag))

def eq3(x, y):                                     # SQL's three-valued "="
    if x is None or y is None:
        return "UNKNOWN"
    return "TRUE" if x == y else "FALSE"

print("Python None == None :", None == None)
print("SQL    NULL = NULL  :", eq3(None, None))
where_true = [c for c, d in rows if eq3(d, "Dhaka") == "TRUE"]
where_not = [c for c, d in rows if eq3(d, "Dhaka") == "FALSE"]
print("district = 'Dhaka'  :", where_true)
print("district <> 'Dhaka' :", where_not)
print("missing from both   :", sorted({c for c, _ in rows} - set(where_true) - set(where_not)))

set : 3 rows ['Dhaka', 'Khulna', None]
bag : 5 rows {'Dhaka': 2, 'Khulna': 1, None: 2}
Python None == None : True
SQL    NULL = NULL  : UNKNOWN
district = 'Dhaka'  : ['C1', 'C3']
district <> 'Dhaka' : ['C2']
missing from both   : ['C4', 'C5']

পরীক্ষার ধাঁচের অঙ্ক

অঙ্ক ১. R(A, B) ৩টি সারি, S(C, D) ৪টি সারি। R ⋈ S-এ কয়টি সারি? সমাধান: কোনো সাধারণ attribute নেই, তাই উপপাদ্য ৫.২(ক) অনুযায়ী R ⋈ S = R × S, আর সারি 3 · 4 = 12. যদি সাধারণ attribute থাকত, উত্তর 0 থেকে 12-এর মধ্যে যেকোনো কিছু হতে পারত।

অঙ্ক ২. R(A, B, C, D, E), F = {A → B, B → C, C → A, D → E}. সব candidate key আর superkey-র সংখ্যা বের করুন। সমাধান: D কোনো FD-র ডান দিকে নেই, তাই প্রতিটি key-তে D থাকবে; D⁺ = {D, E}, তাই একা D যথেষ্ট নয়। {A, D}⁺: A থেকে B, B থেকে C, D থেকে E, মোট U. একইভাবে {B, D}⁺ = {C, D}⁺ = U, কারণ A, B, C একটি চক্রে একে অন্যকে নির্ধারণ করে। প্রতিটি দুই attribute-এর, আর একটি করে বাদ দিলে (A বা D একা) superkey নয়, তাই corollary ৩.৩ অনুযায়ী candidate key: AD, BD, CD. Superkey মানে D আছে, {A, B, C}-এর অন্তত একটি আছে, আর E ইচ্ছেমতো: (2³ − 1) · 2 = 14টি (scratch-এ brute force দিয়ে মেলানো)।

অঙ্ক ৩. F = {A → B, B → C, CD → E} হলে {A, D}⁺ কত, আর {A}⁺? সমাধান: {A, D} থেকে B, তারপর C, তারপর C আর D দুটিই এসে গেছে বলে CD → E থেকে E: {A, D}⁺ = {A, B, C, D, E}. কিন্তু {A}⁺ = {A, B, C}, কারণ D না থাকলে CD → E খাটে না।

১০ · AI-এর যুগে — relational algebra আর key-র উত্তর যাচাই

Key আর FD-র অঙ্কে AI সহকারী প্রায়ই ধাপগুলো সুন্দর করে লেখে, কিন্তু কয়েকটি নির্দিষ্ট ভুল বারবার করে, আর আত্মবিশ্বাসী সুরে:

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

• প্রতিটি দাবিকৃত key-র closure নিজে হিসাব করে U পেয়েছি
• প্রতিটি key থেকে একটি একটি attribute বাদ দিয়ে দেখেছি, আর superkey থাকে না
• কোনো FD-র বাঁ দিক ভাঙা হয়নি, তা দেখেছি
• সব subset-এর brute force চালিয়ে key-র তালিকা আর superkey-র সংখ্যা মিলিয়েছি
• প্রতিটি algebra-সমীকরণের শর্ত (যেমন pushdown-এ c-এর কলাম) মিলিয়েছি, আর ছোট এলোমেলো টেবিলে পরীক্ষা করেছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত জায়গায় মিলিয়েছি

Relational algebra-র সুবিধা হলো এর প্রতিটি দাবি ছোট টেবিলে পরীক্ষা করা যায়: চার-পাঁচ সারির দুটি টেবিল, আর ত্রিশ লাইনের একটি engine. AI একটি সমীকরণ “সবসময় সত্য” বললে কয়েকশো এলোমেলো টেবিলে চালিয়ে দেখুন; একটিও counterexample পেলে দাবিটি মিথ্যা, আর কোনোটি না পেলে প্রমাণ খুঁজুন।