DM: Chapter 6 bangla note

ডাটালগ সিনট্যাক্স (Datalog Syntax)

• সংজ্ঞা (Definition): একটি $S$ এর ওপর ডাটালগ রুল (Rule) হলো একটি অভিব্যক্তি যার রূপ নিম্নরূপ:

  • $R_0(x) :- R_1(u_1), . . . , R_n(u_n)$

  • এখানে $n eq 0$ এবং $n eq 1$ নয়, অর্থাৎ অন্তত একটি বা একাধিক বডি উপাদান থাকতে হবে।

  • $R_0(x)$ অংশটিকে বলা হয় হেড (head) এবং $R_1(u_1), . . . , R_n(u_n)$ অংশটিকে বলা হয় বডি (body), যা নির্দিষ্ট বিষয়বস্তু বা শর্ত নির্দেশ করে।

• উপাদানসমূহ:

  • $R_i \text{ (i = 1 to n)}$ সবগুলো $R_i$ যোগ্য রিলেশন হওয়া উচিত, যা $S$ এর অংশ হিসেবে সংজ্ঞায়িত।

  • $x$ এবং প্রত্যেক $i$ এর জন্য $u_i$ হলো ধ্রুবক (constants) এবং চলক (variables) এর টাপল (tuples), যা তথ্যের প্রতিনিধিত্ব করে।

• নিরাপত্তা শর্ত (Safety Condition): চলক $x$ এর প্রতিটি উপাদান অবশ্যই কোনো না কোনো $u_i$ তে থাকতে হবে। অর্থাৎ হেডের প্রতিটি চলক বডিতে উপস্থিত থাকতে হবে, যা ডাটালগ প্রোগ্রামের নিরাপত্তা নিশ্চিত করে।

• ডাটালগ প্রোগ্রাম: $S$ এর ওপর একটি ডাটালগ প্রোগ্রাম হলো ডাটালগ রুলসমূহের একটি সসীম সেট, যা প্রাযুক্তিক ও বৈজ্ঞানিক গবেষণায় তথ্য সংরক্ষণ ও তথ্য আহরণের জন্য ব্যবহৃত হয়।

• সতর্কবার্তা: ডাটালগ এবং প্রোলগ (Prolog) এর স্বাদ একই রকম হলেও তারা একদম এক নয়; ডাটালগ খুব বেশি তথ্য নিষ্কাশনে দক্ষ কিন্তু সীমাবদ্ধতা রয়েছে।

ইন্টেনশনাল বনাম এক্সটেনশনাল প্রেডিকেটস (IDB vs EDB)

• ইন্টেনশনাল প্রেডিকেটস (IDB):

  • যদি কোনো রিলেশন নাম একটি ডাটালগ প্রোগ্রামের রুলের হেডে (head) উপস্থিত থাকে, তবে তাকে ইন্টেনশনাল বলা হয়।

  • একে IDB (Intensional Database Predicates) বলা হয়, যা কেবলমাত্র গঠনমূলকভাবে সৃষ্ট হয় এবং মূলত সমস্যার সমাধানের জন্য ব্যবহার করা হয়।

• এক্সটেনশনাল প্রেডিকেটস (EDB):

  • যে প্রেডিকেটগুলো রুলের হেডে উপস্থিত থাকে না, তাদের এক্সটেনশনাল বলা হয়।

  • একে EDB (Extensional Database Predicates) বলা হয়, যা সাধারণত নির্দিষ্ট তথ্য দিয়ে স্পষ্ট গণনার (explicit enumeration) মাধ্যমে নির্ধারিত হয়।

• উদাহরণ (রিচিবিলিটি - Reachability):

  • রুল ১: $Reachable(x) :- Edge('s', x).$

  • রুল ২: $Reachable(x) :- Reachable(y), Edge(y, x).$

  • এখানে $Reachable$ হলো IDB এবং $Edge$ হলো EDB, যা খাদ্য নিরাপত্তা বিশ্লেষণ এবং তথ্য অনুসন্ধানে ব্যবহৃত হয়।

ডাটালগ সিম্যান্টিক্স (Datalog Semantics)

ডাটালগের ডিক্লারেটিভ (Declarative) এবং অপারেশনাল (Operational) সিম্যান্টিক্স মিলে যায়, যা ফলস্বরূপ তথ্য আহরণের প্রক্রিয়া অর্জন করতে সহায়তা করে। এর প্রধান তিনটি দিক রয়েছে:

• মডেল থিওরেটিক সিম্যান্টিক্স (Model Theoretic Semantics):

  • এটি লজিক ফর্মুলার ওপর ভিত্তি করে তৈরি (Declarative) এবং গঠনমূলক তথ্য গঠন করে।

• ফিক্সপয়েন্ট সিম্যান্টিক্স (Fixpoint Semantics):

  • এটি ফিক্সপয়েন্ট অপারেটরের পুনরাবৃত্তিমূলক প্রয়োগের ওপর ভিত্তি করে তৈরি (Operational) এবং কার্যকরী ফলাফল পাওয়ার জন্য ব্যবহৃত হয়।

• প্রুফ-ট্রি সিম্যান্টিক্স (Proof-tree Semantics):

  • এটি ডাটালগের একটি গুরুত্বপূর্ণ সমাধান পদ্ধতি, যদিও এটি এই কোর্সের আওতাভুক্ত নয়।

মডেল থিওরেটিক ডাটালগ সিম্যান্টিক্স (Model Theoretic Datalog Semantics)

• একটি ডাটালগ রুল $\rho: R_0(x) :- R_1(u_1), . . . , R_n(u_n)$ কে ১ম ক্রমের লজিক (First Order - FO) বাক্য $\phi_\rho$ হিসেবে ব্যাখ্যা করা যেতে পারে:

  • $\forall x_1 \cdots \forall x_m (R_1(u_1) \wedge \dots \wedge R_n(u_n) \rightarrow R_0(x))$

• এটি মূলত কিছু সীমাবদ্ধতার (constraints) সেট তৈরি করে যাকে FO থিওরি $\{\phi_\rho \mid \rho \in P\}$ বলা হয়।

• আউটপুট (Output): একটি ডাটালগ প্রোগ্রাম $P$ এবং ডাটাবেস $D$ এর জন্য আউটপুট $P(D)$ হলো $P$ এর ন্যূনতম মডেল (minimal model w.r.t. $\subseteq$) যা $D$ কে ধারণ করে, এটি ডেটা বিশ্লেষণে দরকারী।

• বৈধতা: ডাটালগ প্রোগ্রামের জন্য সর্বদা একটি মডেল থাকে এবং একটি অনন্য (unique) ন্যূনতম মডেল বিদ্যমান থাকে, যা তথ্যের বিশ্লেষণে ভিত্তি স্থাপন করে।

ফিক্সপয়েন্ট সিম্যান্টিক্স (Fixpoint Semantics)

• অবিলম্বে ফলাফল (Immediate Consequences): $D$ এর ওপর $P$ এর ইমিডিয়েট কনসিকোয়েন্স হলো:

  • $D$ তে থাকা সকল তথ্য (facts), যা গবেষণার ফলাফল নির্দেশ করে।

  • এমন সব তথ্য $R(a)$ যার জন্য $P$ তে একটি রুল $\rho$ আছে এবং এমন একটি ভ্যালুয়েশন আছে যা বডির সকল অ্যাটমকে $D$ এর তথ্যের সাথে ম্যাপ করে এবং হেডকে $R(a)$ তে ম্যাপ করে, যা ফলাফলকে প্রসারিত করে।

• ফিক্সপয়েন্ট অপারেটর ($T_P$):

  • $T_P(D)$ হলো একটি ফাংশন যা ডাটাবেসকে তার ইমিডিয়েট কনসিকোয়েন্সে ম্যাপ করে।

  • $T^1_P(D) = T_P(D)$ এবং $T^i_P = T_P \circ T^{i-1}_P(D)$

  • যদি $T_P(D) = D$ হয়, তবে $D$ কে ফিক্সপয়েন্ট বলা হয়, যা একটি গুরুত্বপূর্ণ ধারণা।

  • আউটপুট $P(D) = T^\infty_P(D)$, যা ক্ষুদ্রতম ফিক্সপয়েন্ট নির্দেশ করে যা প্রক্রিয়ার বিলম্ব দূর করে।

ডাটালগ একটি কুয়েরি ল্যাঙ্গুয়েজ হিসেবে

• সংজ্ঞা: একটি ডাটালগ কুয়েরি $q$ হলো একটি জোড়া $q = (P, R)$, যেখানে $P$ একটি ডাটালগ প্রোগ্রাম এবং $R$ হলো একটি ইন্টেনশনাল রিলেশন নাম।

• ডাটাবেস $D$ এর ওপর কুয়েরির আউটপুট $q(D)$ হলো $P(D)$ থেকে রিলেশন $R$ এর টাপলগুলোর সেট, যা ফলস্বরূপ তথ্য আহরণের দক্ষতা প্রদান করে।

• বৈশিষ্ট্য:

  • ডাটালগ কুয়েরিগুলো হোমোমরফিজম (Homomorphisms) এর অধীনে সংরক্ষিত থাকে এবং এটি মনোটোন (Monotone), যা ব্যবহৃত ডেটার প্রাসঙ্গিকতার উপর নির্ভর করে।

  • ব্যর্থতা: ডাটালগ অসমতা (inequalities), নেতিবাচক রিলেশনাল অ্যাটম (negative relational atoms) অথবা ডিফারেন্স (difference) প্রকাশ করতে পারে না, যা তার সীমাবদ্ধতা নির্দেশ করে।

ডাটালগ মূল্যায়ন কৌশল (Datalog Evaluation Techniques)

১. নেইভ ডাটালগ মূল্যায়ন (Naive Datalog Evaluation)

• এটি খুব সহজভাবে ফিক্সপয়েন্টে পৌঁছানো পর্যন্ত পুনরাবৃত্তি করে, যা দুটি ইনপুটের মধ্যে সম্পর্ক স্থাপন করে।

• এটি ডাটাবেসের সাইজের সাপেক্ষে পলিনোমিয়াল (Polynomial) ধাপে সম্পন্ন হয়।

• সীমাবদ্ধতা: এতে আগে আবিষ্কৃত তথ্যগুলো বারবার নতুন করে গণনা করা হয় (Redundant derivation), যা সময় এবং স্থান উভয় হিসাবেই ব্যয়বহুল।

২. সেমি-নেইভ ডাটালগ মূল্যায়ন (Semi-Naive Datalog Evaluation)

• এটি কেবলমাত্র নতুন আবিষ্কৃত তথ্যের ওপর ভিত্তি করে পরবর্তী ধাপের গণনা করে, যা স্থানিক এবং কার্যকরী দিক থেকে আরও কার্যকর।

• যদি নিয়মটি হয় $R(x, y) :- R(x, z), R(z, y)$:

  • ধরা যাক, $i$ ধাপে নতুন পাওয়া তথ্য $\Delta R(i) = R(i) - R(i-1)$।

  • তাহলে পরবর্তী ধাপের নতুন তথ্য $\Delta R(i+1) = f(R(i-1), \Delta R(i)) \cup f(\Delta R(i), R(i-1)) \cup f(\Delta R(i), \Delta R(i))$

    • এর ফলে অপ্রয়োজনীয় পুনরাবৃত্তি রোধ করা সম্ভব হয়, যা দক্ষতা বৃদ্ধি করে।

লিনিয়ার ডাটালগ প্রোগ্রাম (Linear Datalog Programs)

• একটি রুল যদি তার বডিতে বড়জোড় একটি IDB রিলেশন ধারণ করে, তবে তাকে লিনিয়ার (Linear) রুল বলা হয়, যা সিস্টেমের জটিলতা কমিয়ে আনে।

• লিনিয়ার ডাটালগ প্রোগ্রাম কেবলমাত্র লিনিয়ার রুল নিয়ে গঠিত যা কার্যকরী প্রভাব ফেলে।

• লিনিয়ার প্রোগ্রামগুলো নন-লিনিয়ার প্রোগ্রামের চেয়ে বেশি দক্ষতার সাথে গণনা করা যায়।

• লিনিয়ার ক্ষেত্রে গণনা: $\Delta R(i+1) = f(\Delta R(i), E(0))$, যা স্পষ্টতঃ প্রচুর তথ্য সংগ্রহ করতে সহায়ক।

ডাটালগের প্রকাশক্ষমতা ও সীমাবদ্ধতা (Expressiveness and Limits)

• ডাটালগ প্রোগ্রামের অধিকাংশ বৈশিষ্ট্য অনির্ণেয় বা আনডেসাইডেবল (Undecidable), যেমন:

  • ফিক্সপয়েন্টে পৌঁছানোর জন্য পাসের সংখ্যার কোনো ঊর্ধ্বসীমা (Bound) আছে কি না?

  • দুটি ডাটালগ কুয়েরি একে অপরের অন্তর্ভুক্ত (Containment) কি না?

• স্যাটিসফায়েবিলিটি (Satisfiability):
  
  

  • প্রতিটি ডাটালগ কুয়েরি $(P, R)$ কি স্যাটিসফায়েবল (Satisfiable)? (এটি একটি চিন্তার প্রশ্ন হিসেবে রাখা হয়েছে)।

উদাহরণ: পয়েন্টস-টু অ্যানালাইসিস (Points-To Analysis)

• একটি C প্রোগ্রামের নির্দেশাবলীকে EDB রিলেশনে অনুবাদ করা যায়:

  • $AddressOf(a, b)$ মানে $a = \&b$

  • $Assign(a, b)$ মানে $a = b$

  • $Load(a, b)$ মানে $a = *b$

  • $Store(a, b)$ মানে $*a = b$

• পয়েন্টস-টু (PointsTo) বিশ্লেষণ ডাটালগ রুল দ্বারা করা যেতে পারে:

  1. $PointsTo(x, y) :- AddressOf(x, y).$

  2. $PointsTo(x, y) :- Assign(x, z), PointsTo(z, y).$

  3. $PointsTo(x, w) :- Load(x, z), PointsTo(z, y), PointsTo(y, w).$

  4. $PointsTo(x, y) :- Store(z, w), PointsTo(z, x), PointsTo(w, y).$