DM: Chapter 7 bangla

সমতা (Equality) এর মাধ্যমে ডেটালগ (Datalog)

ডেটালগের সিনট্যাক্সকে ভেরিয়েবল বা ধ্রুবকের মধ্যে সমতা ব্যবহারের মাধ্যমে প্রসারিত করা যায়।

সিনট্যাক্স (Syntax)

• রুলে সমতা অ্যাটম (Equality atoms) থাকতে পারে:

  • ভেরিয়েবল সমূহের মধ্যে সমীকরণ: $x = y$

  • ভেরিয়েবল এবং ধ্রুবকের (Constant) মধ্যে সমীকরণ: $x = c$

নিরাপত্তার শর্ত (Safety Condition)

• সমস্ত ভেরিয়েবলকে অবশ্যই বডি অ্যাটমে (Body atoms) উপস্থিত থাকতে হবে।

উদাহরণ

একটি গ্রাফের এমন সমস্ত নোড খুঁজে বের করা যা একটি নির্দেশিত ত্রিভুজ (Directed Triangle) এবং একটি নির্দেশিত আয়তক্ষেত্র (Directed Rectangle) উভয় ক্ষেত্রেই বিদ্যমান:

• $InTriangle(x) :- Edge(x, y), Edge(y, z), Edge(z, x).$

• $InRectangle(x) :- Edge(x, y), Edge(y, z), Edge(z, w), Edge(w, x).$

• $InBoth(x) :- InTriangle(x), InRectangle(y), x = y.$

সিম্যান্টিকস এবং এলএফপি (Semantics and LFP)

• ম্যাপিং: একটি রুলকে সন্তুষ্ট করতে হলে হমোমরফিজম বা ম্যাপিংকে সংগতিপূর্ণ হতে হবে। অর্থাৎ, যদি রুলে $x = y$ থাকে, তবে 
  (x) = 
  (y) হতে হবে।

• লিমিট ফিক্সপয়েন্ট (LFP): সমতাযুক্ত ডেটালগের জন্য LFP সিম্যান্টিকস সবসময় সংজ্ঞায়িত। ইমিডিয়েট-কনসিকুয়েন্স অপারেটর ($T_P$) বারবার প্রয়োগ করলে এটি একটি ফিক্সপয়েন্টে পৌঁছায়।

ডেটালগ বনাম সমতাযুক্ত ডেটালগ (Expressive Power)

• প্রতিজ্ঞপ্তি (Proposition): ডেটালগ এবং সমতাযুক্ত ডেটালগ একই ধরণের প্রকাশ ক্ষমতা (Expressive Power) রাখে।

• প্রমাণ পদ্ধতি: প্রতিটি সমতাযুক্ত কুয়েরিকে সাধারণ ডেটালগে রূপান্তর করা সম্ভব:

  • $x = c$ থাকলে রুলে $x$-কে $c$ দ্বারা প্রতিস্থাপন করতে হবে।

  • $x = y$ থাকলে $x$-কে $y$ দ্বারা প্রতিস্থাপন করতে হবে।

  • যদি কোনো ধ্রুবকের মধ্যে অসঙ্গতি দেখা দেয় (যেমন $c = d$), তবে সেই রুলটি বাদ দিতে হবে।

  • স্বতস্ফূর্ত সমতা (যেমন $c = c$) রুল থেকে সরিয়ে ফেলা যায়।

নেগেশনের সংযোজন: অসমতা (Non-Equality)

অসমতা ($x \neq y$) ব্যবহারের মাধ্যমে ডেটালগকে আরও শক্তিশালী করা যায়।

সংজ্ঞা

• রুলে অসমতা অ্যাটম থাকতে পারে:

  • $x \neq y$ (দুটি ভেরিয়েবল আলাদা)

  • $x \neq c$ (ভেরিয়েবল নির্দিষ্ট ধ্রুবকের সমান নয়)

• নিরাপত্তার শর্তানুসারে সমস্ত ভেরিয়েবলকে পজিটিভ বডি অ্যাটমে থাকতে হবে।

উদাহরণ

এমন নির্দেশিত ত্রিভুজ খুঁজে বের করা যার তিনটি নোডই ভিন্ন:

• $Answer(x) :- Edge(x, y), Edge(y, z), Edge(z, x), x \neq y, y \neq z, x \neq z.$

প্রকাশ ক্ষমতা এবং প্রমাণের যুক্তি

• অসমতাযুক্ত ডেটালগ সাধারণ ডেটালগের চেয়ে গুণগতভাবে বেশি শক্তিশালী (Strictly more expressive)।

• যুক্তি: ডেটালগ কুয়েরি হমোমরফিজমের মাধ্যমে সংরক্ষিত (Preserved under homomorphisms) থাকে, কিন্তু অসমতাযুক্ত কুয়েরি তা থাকে না।

• উদাহরণ: ধরুন একটি ডেটাবেস $D = \{E(a, b), E(b, c), E(c, a)\}$ এবং অন্যটি $D' = \{E(a, a)\}$। $D$ থেকে $D'$ এ একটি হমোমরফিজম থাকলেও, ত্রিভুজের ভিন্ন নোডের শর্তটি $D'$ এ কাজ করবে না।

নেগেশনসহ ডেটালগ ($Datalog^{\neg}$)

$Datalog^{\neg}$ হলো এমন একটি রূপ যেখানে রুলের বডিতে অ্যাটমের উপর নেগেশন (Negation) বা না-বাচকতা অনুমোদন করা হয়।

নিরাপত্তার শর্ত (Safety Condition)

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

ফিক্সপয়েন্ট সিম্যান্টিকস ($T_P$ Operator)

নেগেশনের ক্ষেত্রে ইমিডিয়েট কনসিকুয়েন্স অপারেটরটি নিম্নোক্তভাবে কাজ করে:

1. ডাটাবেসের সকল বর্তমান ফ্যাক্ট ($D$) গ্রহণ করে।

2. এমন ফ্যাক্ট $R(a)$ তৈরি করে যার জন্য একটি ভ্যালুয়েশন আছে যা:

   • সমস্ত পজিটিভ অ্যাটমকে ডাটাবেসের ফ্যাক্টে ম্যাপ করে।

   • সমস্ত নেগেটিভ অ্যাটমকে ডাটাবেসে নেই এমন ফ্যাক্টে ম্যাপ করে।

মডেল-থিওরেটিক বনাম এলএফপি সিম্যান্টিকস

পজিটিভ ডেটালগে এই দুটি একে অপরের সমান হলেও, $Datalog^{\neg}$ এর ক্ষেত্রে তারা এক নাও হতে পারে।

• উদাহরণ: রুল $R(0) :- Q(0), \neg R(1)$ এবং $R(1) :- Q(0), \neg R(0)$ এর জন্য একের অধিক মিনিমাল মডেল থাকতে পারে, কিন্তু LFP এর মাধ্যমে প্রাপ্ত ফলাফল এই মিনিমাল মডেলগুলোর সমান নাও হতে পারে।

সেমি-পজিটিভ ডেটালগ (Semi-Positive Datalog)

যদি নেগেশন শুধুমাত্র EDB (Extensional Database) অ্যাটমের ওপর প্রয়োগ করা হয়, তবে তাকে সেমি-পজিটিভ ডেটালগ বলে।

বৈশিষ্ট্যসমূহ

• এতে একটি অনন্য মিনিমাল মডেল থাকে এবং ফিক্সপয়েন্ট অপারেটর তা খুঁজে পায়।

• এটি মনোটোনিক নয়, তবে সেমি-মনোটোনিক (Semi-monotone)।

• রূপান্তর: প্রতিটি সেমি-পজিটিভ প্রোগ্রামকে একটি পজিটিভ প্রোগ্রামে রূপান্তর করা সম্ভব যদি আমরা প্রতিটি রিলেশন $R$ এর পরিপূরক হিসেবে একটি নতুন রিলেশন $R^-$ তৈরি করি।

স্ট্র্যাটিফাইড ডেটালগ (Stratified Datalog)

নেগেশনের কারণে সৃষ্ট অস্পষ্টতা দূর করতে স্ট্র্যাটিফিকেশন ব্যবহার করা হয়।

স্ট্র্যাটিফিকেশনের শর্তাবলী

একটি প্রোগ্রামকে $P_1, \dots, P_n$ স্তরে (Strata) ভাগ করা হয় যাতে:

1. একটি নির্দিষ্ট আইডিবি (IDB) প্রেডিকেট $R$ এর জন্য সমস্ত রুল একই স্তরে থাকে (ধরা যাক স্তর $i$)।

2. যদি $R$ এর রুলে প্রেডিকেট $S$ পজিটিভ হিসেবে থাকে, তবে $S$ এর স্তর অবশ্যই $R$ এর স্তরের সমান বা তার নিচে হবে ($\sigma(S) \leq \sigma(R)$)।

3. যদি $R$ এর রুলে প্রেডিকেট $S$ নেগেটিভ হিসেবে থাকে, তবে $S$ এর স্তর অবশ্যই $R$ এর স্তরের নিচে হতে হবে ($\sigma(S) < \sigma(R)$)।

সিম্যান্টিকস

• প্রতিটি স্তরের ফলাফল একটার পর একটা (Sequential) ফিক্সপয়েন্ট সিম্যান্টিকস ব্যবহার করে গণনা করা হয়।

• স্তরায়ন বা স্ট্র্যাটিফিকেশন একাধিক হতে পারে, তবে ফলাফল বা সিম্যান্টিকস সবসময় একই থাকে।