DM: Chapter 5(Bangla)

ডেটা এবং ইনফরমেশন ম্যানেজমেন্ট: রিলেশনাল ক্যালকুলাস এবং রিলেশনাল কমপ্লিটনেস

• সূচনা: আজকের আলোচনার মূল বিষয় হলো রিলেশনাল ক্যালকুলাস এবং কোর এসকিউএল (Core SQL) ও রিলেশনাল অ্যালজেব্রার সাথে এর সমতুল্যতা।

• আলোচনার আলোচ্যসূচি (Agenda):

  • কুয়েরি ল্যাঙ্গুয়েজ হিসেবে ফার্স্ট অর্ডার লজিক (FOL)।

  • ডোমেইন ইন্ডিপেন্ডেন্স (Domain Independence)।

  • অ্যাক্টিভ ডোমেইন সেম্যান্টিক্সের অধীনে রিলেশনাল ক্যালকুলাস।

  • সেফ রিলেশনাল ক্যালকুলাস ($RC_{safe}$)।

  • রিলেশনাল ক্যালকুলাসের বিভিন্ন প্রকারের সমতুল্যতা।

  • রিলেশনাল কমপ্লিটনেস।

FOL থেকে কুয়েরি ল্যাঙ্গুয়েজ: স্কিমা বনাম ভোকাবুলারি

• ডেটাবেস স্কিমা (Database Schema): একটি ডেটাবেস স্কিমা (নামহীন দৃষ্টিকোণ থেকে) মূলত এমন একটি ভোকাবুলারি যেখানে শুধুমাত্র কনস্ট্যান্ট (constants) এবং প্রেডিকেট নাম (predicate names) থাকে।

• FOL সূত্র (Formulas): FOL সূত্রগুলো একটি ভোকাবুলারির উপর ভিত্তি করে তৈরি করা হয়।

• ভোকাবুলারি সংজ্ঞায়ন: ভোকাবুলারি হলো একটি টিউপল $\sigma = (c_1, . . . , c_m, R_1, . . . , R_k , f_1, . . . , f_{\ell})$, যেখানে অন্তর্ভুক্ত থাকে:

  • কনস্ট্যান্ট সিম্বলসমূহ: $c_i$।

  • প্রেডিকেট সিম্বলসমূহ: $R_i$ যার একটি নির্দিষ্ট অ্যারিটি (arity) থাকে $\text{arity}(R_i)$।

  • ফাংশন সিম্বলসমূহ: $f_i$ যার একটি নির্দিষ্ট অ্যারিটি থাকে $\text{arity}(f_i)$।

• নির্মাণ পদ্ধতি (Construction):

  • ভোকাবুলারি $\sigma = (c_1, . . . , c_m, R_1, . . . , R_k)$ থেকে নামহীন স্কিমা $S_{\sigma} : \text{Rel} \rightarrow \mathbb{N} : R_i \rightarrow \text{arity}(R_i)$ পাওয়া যায়।

  • একইভাবে, একটি স্কিমা $S$ থেকে ভোকাবুলারি $\sigma_S = (R_1, . . . , R_k)$ পাওয়া যায় যেখানে রিলেশন নামগুলোর নির্দিষ্ট অ্যারিটি থাকে।

• উদাহরণ:

  • ভোকাবুলারি $\sigma = (\text{President}, \text{Chair}, \text{Author}[2], \text{Knows}[2], \text{Accepted}[1], \text{Reviewer}[2])$।

  • সংশ্লিষ্ট স্কিমা $S = \{\text{Author}[2], \text{Knows}[2], \text{Accepted}[1], \text{Reviewer}[2]\}$।

ফার্স্ট অর্ডার লজিক (FOL) - সিনট্যাক্স

• পদ বা টার্ম (Terms): কনস্ট্যান্ট এবং ভেরিয়েবলগুলোকে একত্রে টার্ম বলা হয়।

• সিনট্যাক্স সংজ্ঞা: একটি স্কিমা $S$ এবং কনস্ট্যান্ট সেট $\text{Const}$ এর বিপরীতে FOL সূত্রগুলো নিম্নরূপ:

  • অ্যাটোমিক সূত্র (Atomic Formulae): যদি $a \in \text{Const}$ এবং $x, y$ ভেরিয়েবল হয়, তবে $x = a$ এবং $x = y$ হলো অ্যাটোমিক সূত্র।

  • যদি $u_1, . . . , u_k$ টার্ম হয় এবং $R$ একটি $k$-অ্যারি রিলেশন হয়, তবে $R(u_1, . . . , u_k)$ একটি অ্যাটোমিক সূত্র।

  • লজিক্যাল কানেক্টিভস: যদি $\phi_1$ এবং $\phi_2$ সূত্র হয়, তবে $(\phi_1 \wedge \phi_2)$, $(\phi_1 \vee \phi_2)$, এবং $(\neg \phi_1)$ ও সূত্র।

  • কোয়ন্টিফায়ার (Quantifiers): যদি $\phi$ একটি সূত্র হয় এবং $x \in \text{Vars}$ হয়, তবে $(\exists x \phi)$ এবং $(\forall x \phi)$ সূত্র হিসেবে গণ্য হবে।

• সংক্ষিপ্ত চিহ্ন (Shorthand Notations):

  • রিডাবিলিটি ঠিক থাকলে ব্র্যাকেট বর্জন করা যায়।

  • অপারেটরের অগ্রাধিকার: $\neg$ সবচেয়ে শক্তিশালী, এরপর $\wedge$, তারপর $\vee$, এবং সবশেষে কোয়িন্টিফায়ারসমূহ।

  • একাধিক এক্সিস্টেনশিয়াল বা ইউনিভার্সাল ভেরিয়েবলকে একত্রে লেখা যায় (যেমন: $\exists x, y$)।

  • $\phi \Rightarrow \psi$ মানে হলো $\psi \vee \neg \phi$।

  • $\neg(x = y)$ এর পরিবর্তে $x \neq y$ লেখা হয়।

ডেটাবেস ইনস্ট্যান্স বনাম স্ট্রাকচার

• ডেটাবেস ইনস্ট্যান্স: এটি মূলত একটি সসীম কাঠামো বা স্ট্রাকচার।

• ভোকাবুলারি $\sigma$ এর জন্য স্ট্রাকচার: এটি একটি টিউপল $\mathcal{A} = (A, \cdot^{\mathcal{A}})$ যেখানে:

  • $A$ হলো উপাদানের একটি সেট যাকে ডোমেইন বলা হয় (এটি অসীম হতে পারে)।

  • $\cdot^{\mathcal{A}}$ একটি ফাংশন যা সিম্বলগুলোকে ইন্টারপ্রিট করে।

  • প্রতি কনস্ট্যান্ট $c_i$ এর জন্য $c_i^{\mathcal{A}} \in A$।

  • প্রতি প্রেডিকেট $R_i$ এর জন্য $R_i^{\mathcal{A}} : A^{\text{arity}(R_i)} \rightarrow \{\text{true}, \text{false}\}$।

  • প্রতি ফাংশন $f_i$ এর জন্য $f_i^{\mathcal{A}} : A^{\text{arity}(f_i)} \rightarrow A$।

• সসীম কাঠামো (Finite Structure): যদি ডোমেইন $A$ সসীম হয়, তবে তাকে সসীম কাঠামো বলে।

• ডেটাবেস এবং স্ট্রাকচারের সংযোগ: একটি ডেটাবেস ইনস্ট্যান্স $D$ কে একটি স্ট্রাকচার হিসেবে গণ্য করা যায় যেখানে ডোমেইন $A$ এমন যে $\text{Dom}(D) \subseteq A \subseteq \text{Const}$।

ফার্স্ট অর্ডার লজিক (FOL) - সেম্যান্টিক্স

• ভ্যালুয়েশন (Valuation): একটি স্ট্রাকচার $\mathcal{A}$ এবং সূত্র $\phi$ এর জন্য ভ্যালুয়েশন $\eta$ হলো ভেরিয়েবল থেকে ডোমেইন $A$ তে একটি ম্যাপিং। $\eta[x/a]$ মানে হলো ভেরিয়েবল $x$ এর মান $a$।

• সন্তুষ্টির শর্তসমূহ (Satisfaction - $(\mathcal{A}, \eta) \models \phi$):

  • $(\mathcal{A}, \eta) \models x = y$ যদি $\eta(x) = \eta(y)$ হয়।

  • $(\mathcal{A}, \eta) \models x = a$ যদি $\eta(x) = a^{\mathcal{A}}$ হয়।

  • $(\mathcal{A}, \eta) \models R(u_1, . . . , u_k)$ যদি $(\eta(u_1), . . . ,       \eta(u_k)) \in R^{\mathcal{A}}$ হয়।

  • কনজাংশন ($\wedge$), ডিজাংশন ($\vee$), নেগেশন ($\neg$) স্বাভাবিক লজিক নিয়ম অনুসরণ করে।

  • $(\mathcal{A}, \eta) \models \exists x \psi$ যদি কোনো $a \in A$ এর জন্য $(\mathcal{A}, \eta[x/a]) \models \psi$ হয়।

  • $(\mathcal{A}, \eta) \models \forall x \psi$ যদি সকল $a \in A$ এর জন্য $(\mathcal{A}, \eta[x/a]) \models \psi$ হয়।

কুয়েরি ল্যাঙ্গুয়েজ হিসেবে রিলেশনাল ক্যালকুলাস

• সংজ্ঞা: একটি রিলেশনাল ক্যালকুলাস এক্সপ্রেশন হলো $\phi(x)$ ফরম্যাটের একটি সূত্র, যেখানে $\phi$ একটি FOL সূত্র এবং $x$ হলো ফ্রি ভেরিয়েবলগুলোর একটি টিউপল।

• ইভালুয়েশন বা মূল্যায়ন: ডেটাবেস $D$ এবং কুয়েরি $q = \phi(x_1, . . . , x_k)$ এর জন্য:

  • $q(D) = \{ a \in A^k \mid D \models \phi(a) \}$।

• সতর্কতা: স্লাইডের সংজ্ঞাসমূহ বইয়ের সংজ্ঞার থেকে সামান্য ভিন্ন হতে পারে যা পরবর্তীতে আলোচিত হবে।

ডোমেইন ইন্ডিপেন্ডেন্স (Domain Independence)

• লজিক এবং ডেটাবেসের পার্থক্য: কিছু RC কুয়েরির উত্তর শুধুমাত্র ডেটাবেসের মানের উপর নয়, বরং বিবেচ্য ডোমেইন $\text{Const}$ এর উপর নির্ভর করে। এটি ডেটাবেসের ক্ষেত্রে কাম্য নয়।

• সংজ্ঞা: একটি RC কুয়েরি $q$ কে ডোমেইন ইন্ডিপেন্ডেন্ট বলা হয় যদি প্রতি ডেটাবেস $D$ এবং ডোমেইন সেট $A, B$ এর জন্য (যেখানে $\text{Dom}(D) \cup \text{Dom}(q) \subseteq A$ এবং $B$) কুয়েরির ফলাফল সমান হয়: $q(D, A) = q(D, B)$।

• অনির্ণয়যোগ্যতা (Undecidability): ডোমেইন ইন্ডিপেন্ডেন্স একটি অনির্ণয়যোগ্য বৈশিষ্ট্য। কোনো ডেটাবেস সিস্টেম স্বয়ংক্রিয়ভাবে পরীক্ষা করে বলতে পারে না যে একটি কুয়েরি ডোমেইন ইন্ডিপেন্ডেন্ট কিনা।

• সমাধানসমূহ:

  1. অ্যাক্টিভ ডোমেইন সেম্যান্টিক্স ($RC_{adom}$): সকল ভেরিয়েবলকে শুধুমাত্র ডেটাবেসে বিদ্যমান মানগুলোর (Active Domain) মধ্যে সীমাবদ্ধ রাখা।

  2. সেফ রিলেশনাল ক্যালকুলাস ($RC_{safe}$): কিছু সিনট্যাকটিক সীমাবদ্ধতা আরোপ করা যা ডোমেইন ডিপেন্ডেন্ট কুয়েরিগুলোকে বর্জন করে।

সেফ রিলেশনাল ক্যালকুলাস এবং SRNF

• উদ্দেশ্য: একটি সিনট্যাকটিক কন্ডিশন খুঁজে বের করা যাতে প্রতিটি ভেরিয়েবল কোনো কনস্ট্যান্ট বা রিলেশনের সাথে সম্পর্কিত থাকে।

• সেফ-রেঞ্জ নরমাল ফর্ম (SRNF): একটি FOL এক্সপ্রেশন SRNF-এ থাকবে যদি:

  • ভেরিয়েবল নাম পুনরায় ব্যবহার না করা হয়।

  • কোনো ইউনিভার্সাল কোয়িন্টিফায়ার ($\forall$) না থাকে (পরিবর্তে $\neg \exists \neg$ ব্যবহার)।

  • কোনো ইমপ্লিকেশন ($\Rightarrow$) না থাকে।

  • কোনো ডাবল নেগেশন ($\neg \neg$) না থাকে।

  • কনজাংশন এবং ডিজাংশনগুলো সরলীকৃত (flattened) থাকে।

• রেঞ্জ-রেস্ট্রিক্টেড ভেরিয়েবল ($rr(\phi)$):

  • $rr(x = a) = \{x\}$

  • $rr(R(t_1, . . . , t_n)) = \text{Vars}(t_1) \cup . . . \cup \text{Vars}(t_n)$

  • $rr(\phi \wedge \psi) = rr(\phi) \cup rr(\psi)$

  • $rr(\phi \vee \psi) = rr(\phi) \cap rr(\psi)$

  • নেগেশনের ক্ষেত্রে $rr(\neg \phi) = \emptyset$।

• সেফ সূত্র: একটি সূত্র $\phi$ সেফ হবে যদি এটি SRNF-এ থাকে এবং এর সকল ফ্রি ভেরিয়েবল $rr(\phi)$ সেটের অন্তর্ভুক্ত হয়।

কড-এর উপপাদ্য (Codd’s Theorem) এবং রিলেশনাল কমপ্লিটনেস

• উপপাদ্য: ডোমেইন-ইন্ডিপেন্ডেন্ট রিলেশনাল ক্যালকুলাস, কোর এসকিউএল (Core SQL), এবং রিলেশনাল অ্যালজেব্রা (RA) হুবহু একই মানের কুয়েরি প্রকাশ করতে পারে।

• রিলেশনাল কমপ্লিটনেস: কোনো ল্যাঙ্গুয়েজ যদি সকল RC কুয়েরি প্রকাশ করতে পারে, তবে তাকে রিলেশনাল কমপ্লিট বলা হয়। এটি প্রোগ্রামিং ল্যাঙ্গুয়েজের টিউরিং-কমপ্লিটনেসের মতো একটি ভিত্তিগত মানদণ্ড।

সীমাবদ্ধতা এবং অন্যান্য বৈশিষ্ট্য

• যা প্রকাশ করা সম্ভব নয়: রিলেশনাল কমপ্লিট হওয়া মানেই টিউরিং কমপ্লিট হওয়া নয়। যেমন:

  • দুটি নোডের মধ্যে পথ আছে কিনা (Path connectivity / Reachability)।

  • প্যারেটি কুয়েরি (Parity query - উপাদানের সংখ্যা জোড় না বিজোড়)।

  • এগ্রিগেশন (Aggregation) বা নতুন মান তৈরি করা (Value invention)।

• 0-1 ল (0-1 Law): যে কোনো কনস্ট্যান্ট-মুক্ত FO সেন্টেন্সের ক্ষেত্রে ডোমেইন সাইজ অসীমের দিকে ধাবিত হলে এর সত্য হওয়ার সম্ভাবনা হয় $0$ অথবা $1$ হবে। এই বৈশিষ্ট্যটি ব্যবহার করে প্রমাণ করা যায় যে কার্ডিনালিটি কুয়েরি (যেমন: একটি রিলেশনের আকার অন্যটির চেয়ে ছোট কিনা) FOL-এ প্রকাশ করা সম্ভব নয়।

পঠন নির্দেশিকা

• বই: Database Theory - চ্যাপ্টার 3 (First Order Logic) এবং চ্যাপ্টার 6 (Equivalence of Logic and Algebra)।

• বিশেষ দ্রষ্টব্য: বইয়ে FOL বলতে মূলত অ্যাক্টিভ ডোমেইন সেম্যান্টিক্স বোঝানো হয়েছে। ডোমেইন ইন্ডিপেন্ডেন্স এবং সেফনেস সংক্রান্ত বিস্তারিত তথ্যের জন্য Alice বইটি দেখা যেতে পারে (http://webdam.inria.fr/Alice/)।