Schedule আর serializability — conflict আর view

১ · Schedule — অনেক transaction-এর কাজ এক সারিতে

পর্ব ৪৪-এ দেখেছেন, একটি transaction কয়েকটি কাজের এমন একটি দল, যা হয় পুরোটা হবে, নয়তো একটুও না — ACID-এর চারটি গুণ নিয়ে। সেখানে “I” মানে isolation: একসাথে চললেও প্রতিটি transaction যেন একা চলছে। এই পর্বে প্রশ্নটি নিখুঁত করা হবে: “একা চলছে যেন” কথাটির গাণিতিক মানে কী, আর কোনো নির্দিষ্ট ঘটনাক্রম সেই শর্ত মানে কি না, তা কীভাবে যাচাই করবেন।

তত্ত্বে DBMS একটি transaction-কে দেখে শুধু কয়েকটি মৌলিক অপারেশন হিসেবে; ভেতরের হিসাব (যোগ, বিয়োগ) সে জানে না। চিহ্নগুলো:

• R1(A) — transaction T1 ডেটা item A পড়ে (read). item মানে একটি সারি, একটি কলামের মান বা একটি page — যে স্তরে DBMS নজর রাখে।
• W2(B) — T2 item B-তে লেখে (write).
• C1 — T1 commit করে; A1 — T1 abort করে, অর্থাৎ rollback.

একটি schedule হলো কয়েকটি transaction-এর সব অপারেশনের একটি সারি, যেখানে প্রতিটি transaction-এর নিজের অপারেশনগুলোর ক্রম অটুট থাকে। যদি একটি transaction পুরো শেষ হওয়ার পরেই পরেরটি শুরু হয়, সেটি serial schedule. অন্যথায় non-serial — অপারেশনগুলো interleaving-এ, অর্থাৎ পালা করে মেশানো। যে schedule-এ প্রতিটি transaction-এর শেষ অপারেশন C বা A, তাকে বলে সম্পূর্ণ (complete) schedule; অংশ ৭-এর আগে পর্যন্ত আমরা commit-এর কথা বাদ রেখে শুধু read আর write দেখব, কারণ serializability-র প্রশ্নে সেগুলোই নির্ধারক।

এই পর্বের চলমান উদাহরণ একটি মোবাইল ওয়ালেটের দুটি লেনদেন। অ্যাকাউন্ট A-তে ১,০০০ টাকা, B-তে ২,০০০. T1: A থেকে B-তে ১০০ টাকা পাঠায়। T2: A থেকে B-তে ৫০ টাকা পাঠায়। প্রতিটি transaction চারটি অপারেশন: R(A), W(A), R(B), W(B). ফোনের পর্দায় পাশাপাশি কলাম না এঁটে যায়, তাই schedule লেখা হবে খাড়া টেবিলে — প্রতিটি transaction-এর একটি কলাম, প্রতিটি সারিতে একটি অপারেশন, ওপর থেকে নিচে সময়।

মোটা অক্ষরগুলো T2-এর সেই অপারেশন, যা serial ক্রম থেকে আগে সরে এসেছে। S-এ T2 A পড়ে T1 লেখার পরে (৯০০), লেখে ৮৫০ — সব ঠিক। S′-এ T2 A পড়ে T1 লেখার আগে: দুজনেই ১,০০০ পড়ে, T1 লেখে ৯০০, তারপর T2 লেখে ৯৫০ — T1-এর কাটা ১০০ টাকা মুছে গেছে। দুই অ্যাকাউন্টের মোট টাকা ৩,০০০ থেকে হয়েছে ৩,১০০; শূন্য থেকে ১০০ টাকা তৈরি। এটিই পর্ব ৪৪-এর lost update.

২ · কেন পালা করে চালানো — আর লক্ষ্যটি কী

সবচেয়ে নিরাপদ পথ তো serial — একটির পর একটি। তবু কোনো বড় DBMS তা করে না, কারণ একটি transaction-এর বেশিরভাগ সময় কাটে অপেক্ষায়: ডিস্ক থেকে page আসার, নেটওয়ার্কে অ্যাপের পরের নির্দেশের, বা লগ ডিস্কে লেখা শেষ হওয়ার। সেই সময় CPU বসে থাকলে অপচয়।

• Throughput বাড়ে: এক transaction I/O-র অপেক্ষায় থাকলে CPU অন্যটির কাজ করে; প্রতি সেকেন্ডে বেশি transaction শেষ হয়।
• অপেক্ষার সময় কমে: মাসিক হিসাবের একটি লম্বা রিপোর্ট চলার সময় একটি ছোট পেমেন্ট তার পেছনে মিনিটের পর মিনিট আটকে থাকে না।
• বহু CPU core কাজে লাগে: serial ক্রমে একসাথে একটির বেশি transaction চলতেই পারে না।

কিন্তু S′ দেখিয়েছে, যেকোনো মিশ্রণ নিরাপদ নয়। তাহলে কোনটি নিরাপদ? যুক্তিটি সরল। ধরে নেওয়া হয়, প্রতিটি transaction একা চললে ডেটাবেসকে একটি সঠিক অবস্থা থেকে আরেকটি সঠিক অবস্থায় নেয় (ACID-এর C). তাহলে যেকোনো serial schedule-ও সঠিক — একটির পর একটি সঠিক ধাপ। সুতরাং কোনো মিশ্র schedule যদি কোনো একটি serial schedule-এর সমতুল্য হয়, সেটিও সঠিক। একে বলে serializability, আর এটিই একসাথে চলা transaction-এর সঠিকতার প্রচলিত মাপকাঠি।

“সমতুল্য” মানে কী? সবচেয়ে সরল চিন্তা: শেষ অবস্থা মিললেই হলো (result equivalence). কিন্তু সেটি সংখ্যার কাকতালীয় মিলের ওপর নির্ভর করে — অন্য প্রাথমিক মানে মিল ভেঙে যেতে পারে, আর DBMS transaction-এর ভেতরের হিসাব জানেই না। তাই দরকার এমন সংজ্ঞা, যা শুধু read আর write-এর ক্রম দেখে বিচার করে, সব প্রাথমিক মানের জন্য। এমন দুটি সংজ্ঞা আছে: conflict আর view.

৩ · Conflict — কোন দুটি অপারেশনের ক্রম গুরুত্বপূর্ণ

দুটি পাশাপাশি অপারেশন অদলবদল করলে কি ফল বদলায়? দুটি আলাদা item হলে কখনো না — A আর B-র কাজ একে অপরকে ছোঁয় না। একই item হলে নির্ভর করে read না write:

সংজ্ঞা: দুটি অপারেশন conflicting, যদি (১) তারা আলাদা transaction-এর, (২) একই item-এর, আর (৩) অন্তত একটি write. একই transaction-এর দুটি অপারেশন কখনো অদলবদল হয় না — নিজের ক্রম অটুট রাখা schedule-এর সংজ্ঞাতেই আছে।

এখান থেকে প্রথম সমতুল্যতা। একটি schedule থেকে পাশাপাশি দুটি non-conflicting অপারেশন বারবার অদলবদল করে আরেকটি schedule পাওয়া গেলে দুটি conflict equivalent. আর কোনো serial schedule-এর conflict equivalent হলে schedule-টি conflict serializable. নিচে S আর S′ দুটিকেই অদলবদলে serial বানানোর চেষ্টা:

এই হাতের খেলা বড় schedule-এ চলবে না, তবে এর সার কথাটি সহজ: অদলবদলে conflicting জোড়ার ক্রম কখনো বদলায় না. তাই আসল প্রশ্ন — সব conflicting জোড়া কোন দিকে মুখ করে আছে। নিচের এডিটরে schedule রাখা একটি টেবিলে: ops(pos, tx, op, item) — pos সময়ের ক্রম, tx transaction-এর নম্বর, op 'R' বা 'W', item ডেটার নাম। একটি self join (পর্ব ২০) সব conflicting জোড়া বের করে। ডেটা S′-এর:

CREATE TABLE ops (pos INTEGER PRIMARY KEY, tx INTEGER, op TEXT, item TEXT);
INSERT INTO ops VALUES (1,1,'R','A'), (2,2,'R','A'), (3,1,'W','A'), (4,2,'W','A'),
                       (5,1,'R','B'), (6,1,'W','B'), (7,2,'R','B'), (8,2,'W','B');
SELECT a.op || a.tx || '(' || a.item || ')' AS first,
       b.op || b.tx || '(' || b.item || ')' AS second,
       a.op || b.op AS kind,
       'T' || a.tx || '→T' || b.tx AS edge
FROM ops a JOIN ops b
  ON a.item = b.item AND a.tx <> b.tx AND a.pos < b.pos
WHERE a.op = 'W' OR b.op = 'W'
ORDER BY a.pos, b.pos;

৪ · Precedence graph আর মূল উপপাদ্য

ওপরের edge কলামটিই পরের ধারণার বীজ। একটি schedule S-এর precedence graph (serialization graph নামেও পরিচিত) একটি directed graph:

• Node: S-এর প্রতিটি transaction একটি।
• Edge Ti → Tj: যদি Ti-এর কোনো অপারেশন Tj-এর কোনো অপারেশনের সাথে conflict করে, আর Ti-এরটি S-এ আগে আসে। অর্থ: “যেকোনো সমতুল্য serial ক্রমে Ti-কে Tj-এর আগে থাকতে হবে।”

এবার তিনটি transaction-এর একটি schedule, অপারেশন ধরে ধরে graph গড়ে তোলা:

প্রমাণ (⇒, cycle থাকলে serializable নয়): ধরুন S একটি serial schedule S_s-এর conflict equivalent. অদলবদলে conflicting জোড়ার ক্রম বদলায় না, তাই S আর S_s-এর precedence graph হুবহু এক। serial schedule-এ edge Ti → Tj মানে Ti পুরোটা Tj-এর আগে শেষ হয়েছে। এখন graph-এ যদি cycle T1 → T2 → … → Tk → T1 থাকে, তাহলে S_s-এ T1 আছে T2-এর আগে, … , Tk-এর আগে, আবার Tk আছে T1-এর আগে — অর্থাৎ T1 নিজের আগে। অসম্ভব। তাই cycle থাকলে S conflict serializable নয়।

প্রমাণ (⇐, cycle না থাকলে serializable): cycle-হীন directed graph-এর (DAG) সবসময় একটি topological ক্রম থাকে — node-গুলোর এমন সারি, যেখানে প্রতিটি edge সামনের দিকে যায়। সেই ক্রমে transaction-গুলো সাজিয়ে serial schedule S_s বানান। S-এর যেকোনো conflicting জোড়া (Ti-এর p আগে, Tj-এর q পরে) একটি edge Ti → Tj দিয়েছে, তাই S_s-এও Ti আগে, অর্থাৎ p আগে। তাহলে S আর S_s-এ সব conflicting জোড়ার ক্রম এক। এবার S-কে bubble sort-এর মতো S_s-এর দিকে নিন: যতক্ষণ S_s-এর তুলনায় উল্টো ক্রমের কোনো পাশাপাশি জোড়া আছে, সেটি অদলবদল করুন। সেই জোড়া একই transaction-এর হতে পারে না (নিজের ক্রম দুটিতেই এক), conflicting-ও হতে পারে না (তাদের ক্রম দুটিতেই এক) — তাই অদলবদল বৈধ, আর প্রতিবার উল্টো জোড়ার সংখ্যা একটি কমে। শেষে S = S_s. ∎

যাচাইয়ের খরচও স্পষ্ট: n টি অপারেশনের schedule-এ জোড়া তুলনা O(n²), আর t টি transaction আর e টি edge-এর graph-এ cycle খোঁজা O(t + e). এবার SQL-এ একই কাজ। নিচের ডেটা একটি নতুন schedule: R1(A) R2(B) R3(C) W1(B) W2(C) W3(A). প্রথম CTE edge বানায়; walk নামের recursive CTE (পর্ব ২৫) প্রতিটি edge থেকে হাঁটা শুরু করে, আর যে হাঁটা শুরুর node-এ ফিরে আসে, সেটি cycle. হাঁটার দৈর্ঘ্য transaction-এর সংখ্যায় সীমিত, যাতে recursion থামে — পর্ব ২৫-এর cycle detection-এর কৌশল।

INSERT INTO ops VALUES (1,1,'R','A'), (2,2,'R','B'), (3,3,'R','C'),
                       (4,1,'W','B'), (5,2,'W','C'), (6,3,'W','A');
WITH RECURSIVE
edges(src, dst) AS (
  SELECT DISTINCT a.tx, b.tx FROM ops a JOIN ops b
    ON a.item = b.item AND a.tx <> b.tx AND a.pos < b.pos
  WHERE a.op = 'W' OR b.op = 'W'),
walk(start, cur, len, path) AS (
  SELECT src, dst, 1, 'T' || src || '→T' || dst FROM edges
  UNION ALL
  SELECT w.start, e.dst, w.len + 1, w.path || '→T' || e.dst
  FROM walk w JOIN edges e ON e.src = w.cur
  WHERE w.cur <> w.start AND w.len < (SELECT COUNT(DISTINCT tx) FROM ops))
SELECT path AS cycle FROM walk WHERE cur = start;

৫ · সমতুল্য serial ক্রম — topological sort

Graph-এ cycle না থাকলে উত্তরের দ্বিতীয় অংশ: কোন serial ক্রম? সেটি topological sort — DSA কোর্সের topological sort পর্বে যে অ্যালগরিদম বিস্তারিত দেখেছেন। Kahn-এর পদ্ধতিতে: যে node-এর দিকে কোনো edge আসে না, তাকে সারিতে বসান, তার edge-গুলো মুছে দিন, আবার একই কাজ। একাধিক node একসাথে প্রস্তুত থাকলে যেকোনোটি আগে নেওয়া যায় — তাই সমতুল্য serial ক্রম একাধিক হতে পারে।

SQL-এ একটি সহজ বিকল্প: প্রতিটি transaction-এর level = কোনো উৎস থেকে তার কাছে আসার দীর্ঘতম পথের দৈর্ঘ্য। edge Ti → Tj থাকলে level(Tj) ≥ level(Ti) + ১, তাই level অনুযায়ী সাজালে সব edge সামনের দিকে যায় — একটি বৈধ topological ক্রম। একই level-এর transaction-গুলো যেকোনো ক্রমে বসতে পারে। এই এডিটরে চারটি transaction-এর schedule: R2(A) W2(A) W2(B) R1(A) R4(B) W1(C) W4(D) R3(C) R3(D).

INSERT INTO ops VALUES (1,2,'R','A'), (2,2,'W','A'), (3,2,'W','B'), (4,1,'R','A'),
  (5,4,'R','B'), (6,1,'W','C'), (7,4,'W','D'), (8,3,'R','C'), (9,3,'R','D');
WITH RECURSIVE
edges(src, dst) AS (
  SELECT DISTINCT a.tx, b.tx FROM ops a JOIN ops b
    ON a.item = b.item AND a.tx <> b.tx AND a.pos < b.pos
  WHERE a.op = 'W' OR b.op = 'W'),
lvl(tx, d) AS (
  SELECT DISTINCT tx, 0 FROM ops
  UNION ALL
  SELECT e.dst, l.d + 1 FROM lvl l JOIN edges e ON e.src = l.tx
  WHERE l.d < (SELECT COUNT(DISTINCT tx) FROM ops))
SELECT 'T' || tx AS tx, MAX(d) AS level FROM lvl
GROUP BY tx ORDER BY level, tx;

এবার নিজের যেকোনো schedule পরীক্ষা করুন। নিচের ছোট JavaScript চেকারটি পুরো কাজ একবারে করে: schedule-এর লেখা পড়ে, conflicting জোড়া থেকে edge বানায় (প্রতিটি edge প্রথম কোন জোড়া থেকে এলো তা দেখায়), তারপর Kahn-এর topological sort চালায়। সব node সারিতে বসলে serializable, নইলে cycle. প্রথম লাইনের লেখাটি বদলে চালান — C1 বা A2-এর মতো commit/abort লিখলে চেকার সেগুলো উপেক্ষা করে।

const schedule = "R1(A) R2(A) W1(A) W2(A) R1(B) W1(B) R2(B) W2(B)";

const ops = schedule.trim().split(/\s+/).filter(s => !/^[CA]\d+$/.test(s)).map(s => {
  const m = s.match(/^([RW])(\d+)\((\w+)\)$/);
  if (!m) throw new Error("এই অংশটি বোঝা গেল না: " + s);
  return { op: m[1], tx: "T" + m[2], item: m[3], text: s };
});
const txs = [...new Set(ops.map(o => o.tx))];
const out = new Map(txs.map(t => [t, new Set()]));     // precedence graph
ops.forEach((a, i) => ops.slice(i + 1).forEach(b => {
  if (a.item === b.item && a.tx !== b.tx && (a.op === "W" || b.op === "W") && !out.get(a.tx).has(b.tx)) {
    out.get(a.tx).add(b.tx);
    console.log(`${a.text} আগে, ${b.text} পরে → edge ${a.tx}→${b.tx}`);
  }
}));
// Kahn-এর topological sort: যার দিকে কোনো edge আসে না, সে আগে
const indeg = new Map(txs.map(t => [t, 0]));
out.forEach(set => set.forEach(t => indeg.set(t, indeg.get(t) + 1)));
const ready = txs.filter(t => indeg.get(t) === 0), order = [];
while (ready.length) {
  const t = ready.shift();
  order.push(t);
  out.get(t).forEach(u => { indeg.set(u, indeg.get(u) - 1); if (indeg.get(u) === 0) ready.push(u); });
}
if (order.length === txs.length) console.log("Conflict serializable ✓  সমতুল্য serial ক্রম: " + order.join(" → "));
else console.log("Conflict serializable নয় ✗  cycle-এ (বা তার পরে) আটকে আছে: " + txs.filter(t => !order.includes(t)).join(", "));

৬ · View serializability — blind write-এর জগৎ

Conflict serializability নিরাপদ, কিন্তু কিছু নির্দোষ schedule-কেও বাদ দেয়। এই schedule দেখুন — T1 A পড়ে আর লেখে, T2 আর T3 না পড়েই A-তে লেখে:

Precedence graph: R1(A) → W2(A) থেকে T1 → T2, আর W2(A) → W1(A) থেকে T2 → T1 — cycle, তাই conflict serializable নয়। অথচ ভাবুন: A-র শেষ মান সবসময় T3-এর লেখা, আর T1 যা পড়ল তা প্রাথমিক মান। serial T1, T2, T3-এও ঠিক তা-ই। কেউ “ভুল” কিছু দেখেনি। T2 আর T3-এর write-কে বলে blind write — নিজে না পড়ে লেখা, যেমন “ঠিকানা বদলে নতুন ঠিকানা লেখো”, পুরোনোটি না দেখেই।

এই উদারতা ধরতে view equivalence. একই transaction-গুলোর দুটি schedule S আর S′ view equivalent, যদি প্রতিটি item X-এর জন্য তিনটি শর্ত মানে:

1. প্রাথমিক read: S-এ কোনো Ti X-এর প্রাথমিক মান পড়লে S′-এও Ti প্রাথমিক মান পড়ে।
2. Read-from: S-এ Ti যদি Tj-এর লেখা X পড়ে (অর্থাৎ Ri(X)-এর ঠিক আগের শেষ write-টি Wj(X)), তাহলে S′-এও তা-ই।
3. শেষ write: S-এ X-এর শেষ write যে transaction করে, S′-এও সে-ই করে।

প্রথম দুটি নিশ্চিত করে প্রতিটি transaction একই মান দেখে, তাই একই হিসাব করে; তৃতীয়টি নিশ্চিত করে ডেটাবেসের শেষ অবস্থা এক। কোনো serial schedule-এর view equivalent হলে S view serializable. ওপরের S₄ আর serial T1, T2, T3 মিলিয়ে দেখুন: R1(A) দুটিতেই প্রাথমিক মান পড়ে; আর কোনো read নেই; A-র শেষ write দুটিতেই W3(A). তিনটি শর্ত পূরণ — S₄ view serializable, কিন্তু conflict serializable নয়। অন্য serial ক্রম কেন চলবে না, তা-ও দেখুন: T2 যদি T1-এর আগে থাকে, R1(A) পড়বে T2-এর লেখা — প্রথম শর্ত ভাঙে; T3 শেষে না থাকলে A-র শেষ write অন্য কারও — তৃতীয় শর্ত ভাঙে। তাই একমাত্র উত্তর T1, T2, T3. view-এর প্রশ্নে এভাবেই এগোন: শর্তগুলো থেকে “কে কার আগে থাকতেই হবে” বের করুন, তারপর এমন একটি serial ক্রম খুঁজুন যা সবকটি মানে।

• প্রতিটি conflict serializable schedule view serializable: অদলবদলে conflicting জোড়ার ক্রম বজায় থাকে, তাই কে কার লেখা পড়ে আর কে শেষে লেখে — তিনটিই WR আর WW জোড়ার ক্রম দিয়ে নির্ধারিত — বদলায় না। উল্টোটা সত্য নয়, S₄ তার প্রমাণ।
• পার্থক্য আসে শুধু blind write থেকে: কোনো schedule view serializable কিন্তু conflict serializable নয় হলে তাতে অন্তত একটি blind write আছে। blind write না থাকলে দুই ধারণা এক।
• যাচাই কঠিন: ১৯৭৯ সালে Christos Papadimitriou প্রমাণ করেন, একটি schedule view serializable কি না তা যাচাই করা NP-complete. সাধারণ graph যথেষ্ট নয়; লাগে “polygraph” — এমন edge-জোড়া, যার যেকোনো একটি বেছে নিতে হয়, আর বাছাইয়ের সংখ্যা সূচকীয় হারে বাড়ে।

তাই বাস্তব DBMS view serializability সরাসরি যাচাই করে না। এর মূল্য তাত্ত্বিক: সঠিকতার একটি বড় সীমানা আঁকা। তবে একটি জায়গায় এর ছায়া আছে — timestamp-ভিত্তিক concurrency control-এর Thomas write rule পুরোনো blind write নিঃশব্দে ফেলে দিয়ে কিছু view-serializable schedule মেনে নেয়; পর্ব ৪৬-এ দেখবেন।

৭ · Recoverability — commit-এর ক্রমও গুরুত্বপূর্ণ

এ পর্যন্ত ধরে নিয়েছি সব transaction commit করে। বাস্তবে transaction abort করে — ব্যালান্স কম, constraint ভাঙা, deadlock, বা অ্যাপের নিজের সিদ্ধান্তে। তখন তার লেখা মুছতে হয়। সমস্যা হয় যদি অন্য কেউ ইতিমধ্যে সেই লেখা পড়ে ফেলে — commit না হওয়া ডেটা পড়াকে বলে dirty read. এখান থেকে তিনটি ক্রমশ কড়া শর্ত:

শর্তগুলো না মানলে কী হয়, ধাপে ধাপে দেখুন। T1 A লেখে, T2 সেটি পড়ে B লেখে, T3 সেই B পড়ে; T4 আলাদা item নিয়ে কাজ করে। তারপর T1 abort করে:

Cascadeless হলেও একটি ফাঁক থাকে। W1(A) W2(A) A1: কেউ dirty read করেনি, কিন্তু T1 abort হলে A-তে T1-এর before-image বসালে T2-এর লেখাও মুছে যায়। strict শর্ত এই ফাঁক বন্ধ করে — অসমাপ্ত লেখার ওপর লেখাও নিষেধ — ফলে recovery-র নিয়ম সরল থাকে: “abort মানে নিজের লেখা item-এ before-image বসাও”। পর্ব ৪৮-এর লগ-ভিত্তিক recovery এর ওপরই দাঁড়িয়ে।

৮ · বাস্তব DBMS কীভাবে নিশ্চিত করে

কোনো DBMS আগে schedule বানিয়ে পরে graph পরীক্ষা করে না — ততক্ষণে অপারেশনগুলো ঘটে গেছে। বদলে সে এমন concurrency control প্রটোকল মেনে চলে, যা কেবল নিরাপদ schedule-ই তৈরি হতে দেয়। সবচেয়ে প্রচলিতটি two-phase locking (2PL): প্রতিটি transaction পড়ার আগে shared lock, লেখার আগে exclusive lock নেয়, আর নিয়ম একটাই — একবার কোনো lock ছাড়লে আর নতুন lock নেওয়া যাবে না. ফলে দুটি পর্ব: growing (শুধু নেওয়া) আর shrinking (শুধু ছাড়া)।

কেন 2PL conflict serializable schedule দেয় (প্রমাণের রূপরেখা): প্রতিটি transaction-এর lock point ধরুন — যে মুহূর্তে সে শেষ lock-টি পায়। edge Ti → Tj মানে কোনো item X-এ Ti-এর অপারেশন আগে আর Tj-এর conflicting অপারেশন পরে; দুটির lock একসাথে থাকতে পারে না (অন্তত একটি exclusive), তাই Ti X-এর lock ছেড়েছে Tj তা পাওয়ার আগে। Ti কোনো lock ছাড়ে তার lock point-এর পরে, আর Tj X-এর lock পায় তার lock point-এর আগে বা ঠিক তখনই। তাই lockpoint(Ti) < lockpoint(Tj). সব edge lock point বাড়ার দিকে যায়, ফলে cycle অসম্ভব; সমতুল্য serial ক্রম হলো lock point-এর ক্রম।

অংশ ১-এর খারাপ S′ 2PL-এ কী হতো? R1(A) আর R2(A) দুজনেই A-র shared lock পায় — shared lock একসাথে চলে। এবার W1(A)-এর জন্য T1-এর লাগে exclusive lock, কিন্তু T2-এর shared lock আছে: T1 অপেক্ষা করে। W2(A)-এর জন্য T2-ও exclusive চায়, T1-এর shared lock-এর কারণে অপেক্ষা করে। দুজনেই দুজনের অপেক্ষায় — deadlock. DBMS একজনকে abort করে, ধরুন T2; T1 এগিয়ে যায়, T2 পরে নতুন করে চলে নতুন মান পড়ে। lost update ঘটতেই পারল না — দাম একটি abort আর আবার চালানো। cycle-ওয়ালা schedule 2PL-এ এভাবেই আটকে যায়: হয় অপেক্ষায়, নয়তো deadlock-এ।

সাধারণ 2PL কিন্তু recoverability দেয় না: shrinking পর্বে exclusive lock ছেড়ে দিলে অন্যরা commit-এর আগেই সেই লেখা পড়তে পারে। তাই বাস্তবে চলে strict 2PL: exclusive lock ধরে রাখা হয় commit বা abort পর্যন্ত (rigorous 2PL-এ সব lock). তখন কেউ অসমাপ্ত লেখা পড়তেও পারে না, তার ওপর লিখতেও পারে না — schedule strict, তাই cascadeless আর recoverable-ও, আবার conflict serializable. দাম আছে: lock-এর অপেক্ষা আর deadlock — পর্ব ৪৬-এর বিষয়।

• SQLite: একসাথে একজনই লেখে (ডেটাবেস-স্তরের lock), তাই লেখার transaction-গুলো আসলেই একটির পর একটি; স্বাভাবিক আচরণ SERIALIZABLE.
• MySQL/InnoDB: স্বাভাবিক isolation level REPEATABLE READ. SERIALIZABLE-এ (autocommit বন্ধ থাকলে) সাধারণ SELECT-ও shared lock নিয়ে পড়ে — 2PL-এর ধাঁচ।
• PostgreSQL: স্বাভাবিক READ COMMITTED. ৯.১ সংস্করণ (২০১১) থেকে SERIALIZABLE মানে serializable snapshot isolation (SSI): lock-এ আটকে না রেখে, নিরাপদ নয় এমন নির্ভরতার নকশা দেখলে একটি transaction-কে বাতিল করে।
• Oracle: স্বাভাবিক READ COMMITTED; তার “SERIALIZABLE” আসলে snapshot isolation, যা কিছু non-serializable ফল (write skew) হতে দেয় — পর্ব ৪৭-এ বিস্তারিত।

শেষ দুটির একটি ব্যবহারিক পরিণতি: SERIALIZABLE-এ অ্যাপকে ব্যর্থ transaction আবার চালানোর জন্য প্রস্তুত থাকতে হয়। তুলনার জন্য (এখানে চালানো যায় না):

BEGIN ISOLATION LEVEL SERIALIZABLE;
UPDATE accounts SET balance = balance - 100 WHERE id = 'A';
UPDATE accounts SET balance = balance + 100 WHERE id = 'B';
COMMIT;
-- বিপজ্জনক নির্ভরতা ধরা পড়লে কোনো একটি statement বা COMMIT ব্যর্থ হয়:
-- ERROR: could not serialize access due to read/write dependencies
--        among transactions   (SQLSTATE 40001)
-- অ্যাপের কাজ: ROLLBACK, তারপর পুরো transaction আবার চালানো

৯ · পরীক্ষার ধাঁচের সমস্যা — পূর্ণ সমাধান

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই অধ্যায়ের প্রশ্ন প্রায় সবসময় একই কাঠামোর: schedule দেওয়া, graph আঁকুন, serializable কি না বলুন, ক্রম দিন, recoverability শ্রেণি বলুন। পাঁচটি নমুনা:

সমস্যা ১ · R1(A) R2(B) W2(A) W1(B)

Graph: R1(A), W2(A) → T1 → T2; R2(B), W1(B) → T2 → T1. দুটি transaction-এর cycle — conflict serializable নয়. View? W2(A) আর W1(B) দুটিই blind write, তাই প্রশ্নটি খোলা; serial ক্রম দুটি পরীক্ষা করুন। T1, T2-তে R2(B) পড়ত T1-এর লেখা B, অথচ S-এ পড়ে প্রাথমিক মান — অমিল। T2, T1-এ R1(A) পড়ত T2-এর লেখা A — অমিল। View serializable-ও নয়. শিক্ষা: blind write থাকা view serializability-র প্রয়োজনীয় শর্ত, যথেষ্ট নয়।

সমস্যা ২ · R1(A) W1(A) R2(B) W2(B) R3(A) R3(B)

Graph: W1(A), R3(A) → T1 → T3; W2(B), R3(B) → T2 → T3. T1 আর T2-এর মধ্যে কোনো conflict নেই (আলাদা item). cycle নেই — conflict serializable. topological ক্রম দুটি: T1, T2, T3 এবং T2, T1, T3. দুটিই সঠিক উত্তর; একটি দিলে যথেষ্ট, দুটি দিলে আরও ভালো।

সমস্যা ৩ · শ্রেণিবিভাগ

চারটিই conflict serializable (একমাত্র edge T1 → T2). serializability আর recoverability যে আলাদা মাপকাঠি, প্রথম সারিটিই তার প্রমাণ।

সমস্যা ৪ · R1(A) W1(A) R2(A) W2(A) C2 R1(B) W1(B) C1

Graph: A-তে তিনটি conflict (RW, WR, WW; R1(A) আর R2(A) দুটিই read), সবকটি T1 → T2; B শুধু T1-এর। Conflict serializable, ক্রম T1, T2. Recoverable? R2(A) পড়ে W1(A)-এর লেখা, আর C2 আসে C1-এর আগে — non-recoverable. W1(B)-এর আগে কোনো সমস্যা দেখা দিয়ে T1 abort করলে T2-এর commit করা ফল ভুল ভিত্তিতে থেকে যাবে। strict 2PL-এ এটি ঘটতেই পারত না: T1-এর A-র exclusive lock C1 পর্যন্ত থাকত, R2(A) অপেক্ষা করত।

সমস্যা ৫ · একটি সারি সরালে শ্রেণি বদলায়

Graph: W1(A), R3(A) → T1 → T3; B-তে T2-এর দুটি অপারেশন T3-এর দুটির আগে → T2 → T3. T1 আর T2 আলাদা item ছোঁয়। cycle নেই — conflict serializable, ক্রম T1, T2, T3 বা T2, T1, T3. Recoverable? T3 পড়ে A T1 থেকে (C1 আছে C3-এর আগে) আর B T2 থেকে (C2 আছে C3-এর আগে) — হ্যাঁ। Cascadeless? R3(B) আসে ৭ নম্বরে, অথচ C2 ৯ নম্বরে — T3 পড়েছে T2-এর অসমাপ্ত লেখা, তাই না. T2 abort করলে T3-কেও যেতে হতো। প্রতিকার: C2-কে ৭ নম্বরের আগে নিয়ে এলে প্রতিটি read আর প্রতিটি পরের write commit-হওয়া ডেটার ওপর হয় — schedule তখন cascadeless, এমনকি strict. serializability একই থাকে, কারণ commit-এর অবস্থান precedence graph বদলায় না। পরীক্ষায় এই পার্থক্যটি প্রায়ই ধরা হয়: graph দেখে read আর write, recoverability দেখে commit আর abort.

১০ · AI-এর যুগে serializability

এই অধ্যায়ের প্রশ্নে AI প্রায়ই আত্মবিশ্বাসী কিন্তু ভুল উত্তর দেয়, কারণ ছোট একটি ক্রমের পার্থক্যেই উত্তর উল্টে যায়। আর concurrency-র কোড লেখার সময় AI প্রায়ই transaction, isolation level আর retry-র কথাই তোলে না। সাধারণ ভুল:

AI-এর দেওয়া উত্তর বা কোড মেনে নেওয়ার আগে — চেকলিস্ট

• প্রতিটি edge-এর পেছনে দুটি নির্দিষ্ট অপারেশন আছে — একই item, আলাদা transaction, অন্তত একটি write
• graph আর serial ক্রম চেকার বা SQL এডিটরে নিজে চালিয়ে মিলিয়েছি
• প্রশ্নটি conflict না view serializability, স্পষ্ট; blind write থাকলে view-ও আলাদা দেখেছি
• recoverability-র জন্য commit আর abort-এর অবস্থান আলাদা করে মিলিয়েছি
• অ্যাপের কোডে transaction-এর সীমানা, isolation level আর 40001-এর পর retry আছে
• DBMS-নির্দিষ্ট দাবি (কোন level-এ কী নিশ্চয়তা) সেই DBMS-এর ডকুমেন্টেশনে মিলিয়েছি