فنکشنل انحصار کا تعارف

اس مضمون میں ہم ڈیٹا بیس میں فعال انحصار کے بارے میں بات کریں گے - وہ کیا ہیں، وہ کہاں استعمال ہوتے ہیں اور ان کو تلاش کرنے کے لیے کون سے الگورتھم موجود ہیں۔

ہم متعلقہ ڈیٹا بیس کے تناظر میں فعال انحصار پر غور کریں گے۔ بہت موٹے الفاظ میں، اس طرح کے ڈیٹا بیس میں معلومات کو ٹیبل کی شکل میں ذخیرہ کیا جاتا ہے. اس کے بعد، ہم تخمینی تصورات کا استعمال کرتے ہیں جو سخت رشتہ دار نظریہ میں قابل تبادلہ نہیں ہوتے ہیں: ہم ٹیبل کو ہی ایک رشتہ، کالم - اوصاف (ان کا سیٹ - ایک ریلیشن اسکیما)، اور صفات کے ذیلی سیٹ پر قطار کی اقدار کا سیٹ کہیں گے۔ --.ایک ٹپل n.

مثال کے طور پر، اوپر کی میز میں، (بینسن، ایم، ایم آرگن) صفات کا ایک مجموعہ ہے۔ (مریض، پال، ڈاکٹر).
مزید رسمی طور پر، یہ مندرجہ ذیل طور پر لکھا ہے: [مریض، جنس، ڈاکٹر] = (بینسن، ایم، ایم آرگن).
اب ہم فنکشنل انحصار (FD) کا تصور متعارف کروا سکتے ہیں:

تعریف 1۔ رشتہ R وفاقی قانون X → Y (جہاں X, Y ⊆ R) کو مطمئن کرتا ہے اگر اور صرف اس صورت میں جب کسی بھی ٹیپلس کے لیے , ∈ R رکھتا ہے: if [X] = [X]، پھر [Y] = [وائی]۔ اس صورت میں، ہم کہتے ہیں کہ X (تعمیر کنندہ، یا صفات کا تعین کرنے والا مجموعہ) فعال طور پر Y (منحصر سیٹ) کا تعین کرتا ہے۔

دوسرے لفظوں میں، وفاقی قانون کی موجودگی X → Y اس کا مطلب ہے کہ اگر ہمارے پاس دو ٹوپل ہیں۔ R اور وہ صفات میں مماثل ہیں۔ X، پھر وہ صفات میں موافق ہوں گے۔ Y.
اور اب، ترتیب میں۔ آئیے اوصاف کو دیکھتے ہیں۔ مریض۔ и پال جس کے لیے ہم یہ جاننا چاہتے ہیں کہ آیا ان کے درمیان انحصار ہے یا نہیں۔ صفات کے اس مجموعے کے لیے، درج ذیل انحصارات موجود ہو سکتے ہیں:

1. مریض → جنس
2. جنس → مریض

جیسا کہ اوپر بیان کیا گیا ہے، پہلے انحصار کو برقرار رکھنے کے لیے، ہر ایک منفرد کالم کی قدر مریض۔ صرف ایک کالم کی قدر مماثل ہونی چاہیے۔ پال. اور مثال کے طور پر میز کے لئے یہ واقعی معاملہ ہے. تاہم، یہ مخالف سمت میں کام نہیں کرتا، یعنی، دوسرا انحصار مطمئن نہیں ہے، اور وصف پال کے لئے ایک فیصلہ کن نہیں ہے صبر. اسی طرح اگر ہم انحصار کو لے لیں۔ ڈاکٹر → مریض، آپ دیکھ سکتے ہیں کہ اس کی خلاف ورزی ہوئی ہے، قیمت کے بعد سے رابن اس وصف کے کئی مختلف معنی ہیں - ایلس اور گراہم.

اس طرح، فعال انحصار ٹیبل صفات کے سیٹ کے درمیان موجودہ تعلقات کا تعین کرنا ممکن بناتا ہے۔ یہاں سے ہم سب سے زیادہ دلچسپ کنکشن پر غور کریں گے، یا اس طرح کے X → Yوہ کیا ہیں:

• غیر معمولی، یعنی انحصار کا دائیں جانب بائیں کا ذیلی سیٹ نہیں ہے۔ (Y ̸⊆ X);
• کم سے کم، یعنی ایسی کوئی انحصار نہیں ہے۔ Z → Yکہ Z ⊂ X.

اس وقت تک جو انحصار سمجھا جاتا ہے وہ سخت تھے، یعنی انہوں نے میز پر کسی قسم کی خلاف ورزی نہیں کی تھی، لیکن ان کے علاوہ، وہ بھی ہیں جو ٹیپلز کی اقدار کے درمیان کچھ متضاد ہونے کی اجازت دیتے ہیں۔ اس طرح کے انحصار کو ایک الگ کلاس میں رکھا جاتا ہے، جسے تخمینہ کہا جاتا ہے، اور ٹیپلز کی ایک مخصوص تعداد کے لیے ان کی خلاف ورزی کی اجازت ہے۔ اس رقم کو زیادہ سے زیادہ ایرر انڈیکیٹر ایمیکس کے ذریعے ریگولیٹ کیا جاتا ہے۔ مثال کے طور پر، غلطی کی شرح = 0.01 کا مطلب یہ ہوسکتا ہے کہ اوصاف کے زیر غور سیٹ پر دستیاب ٹیوپلز کے 1٪ کے ذریعہ انحصار کی خلاف ورزی کی جاسکتی ہے۔ یعنی، 1000 ریکارڈز کے لیے، زیادہ سے زیادہ 10 ٹیپلز وفاقی قانون کی خلاف ورزی کر سکتے ہیں۔ ہم قدرے مختلف میٹرک پر غور کریں گے، جس کا موازنہ کیا جا رہا ٹیوپلز کی جوڑی کی طرف سے مختلف اقدار کی بنیاد پر کیا جا رہا ہے۔ نشے کے لیے X → Y رویہ پر r یہ اس طرح سمجھا جاتا ہے:

آئیے غلطی کا حساب لگاتے ہیں۔ ڈاکٹر → مریض اوپر کی مثال سے. ہمارے پاس دو ٹیپلز ہیں جن کی قدر وصف پر مختلف ہے۔ مریض۔، لیکن اتفاق ڈاکٹر: [ڈاکٹر، مریض] = (رابن، ایلس) اور [ڈاکٹر، مریض] = (رابن، گراہم)۔ غلطی کی تعریف کے بعد، ہمیں تمام متضاد جوڑوں کو مدنظر رکھنا چاہیے، جس کا مطلب ہے کہ ان میں سے دو ہوں گے: (, ) اور اس کا الٹا (, )۔ آئیے اسے فارمولے میں تبدیل کریں اور حاصل کریں:

اب آئیے اس سوال کا جواب دینے کی کوشش کرتے ہیں: "یہ سب کیوں ہے؟" درحقیقت وفاقی قوانین مختلف ہیں۔ پہلی قسم وہ انحصار ہے جو ڈیٹا بیس ڈیزائن کے مرحلے پر منتظم کے ذریعے طے کی جاتی ہے۔ وہ عام طور پر تعداد میں کم، سخت ہوتے ہیں، اور بنیادی ایپلیکیشن ڈیٹا کو نارملائزیشن اور ریلیشنل اسکیما ڈیزائن ہے۔

دوسری قسم انحصار ہے، جو "پوشیدہ" ڈیٹا اور صفات کے درمیان پہلے سے نامعلوم تعلقات کی نمائندگی کرتی ہے۔ یعنی، اس طرح کے انحصار کے بارے میں ڈیزائن کے وقت نہیں سوچا گیا تھا اور وہ موجودہ ڈیٹا سیٹ کے لیے پائے جاتے ہیں، تاکہ بعد میں، بہت سے شناخت شدہ وفاقی قوانین کی بنیاد پر، ذخیرہ شدہ معلومات کے بارے میں کوئی نتیجہ اخذ کیا جا سکے۔ یہ بالکل وہی انحصار ہے جس کے ساتھ ہم کام کرتے ہیں۔ ان کے ساتھ ڈیٹا مائننگ کے ایک پورے شعبے کے ذریعے مختلف تلاش کی تکنیکوں اور ان کی بنیاد پر بنائے گئے الگورتھم سے نمٹا جاتا ہے۔ آئیے معلوم کریں کہ کسی بھی ڈیٹا میں پایا جانے والا فنکشنل انحصار (عین مطابق یا تخمینہ) کیسے کارآمد ہو سکتا ہے۔

آج، انحصار کی اہم ایپلی کیشنز میں سے ایک ڈیٹا کی صفائی ہے. اس میں "گندے ڈیٹا" کی نشاندہی کرنے اور پھر اسے درست کرنے کے عمل کو تیار کرنا شامل ہے۔ "گندے ڈیٹا" کی نمایاں مثالیں نقلیں، ڈیٹا کی غلطیاں یا ٹائپوز، گمشدہ اقدار، پرانا ڈیٹا، اضافی جگہیں، اور اس طرح کی چیزیں ہیں۔

ڈیٹا کی خرابی کی مثال:

ڈیٹا میں ڈپلیکیٹس کی مثال:

مثال کے طور پر، ہمارے پاس ایک میز اور وفاقی قوانین کا ایک سیٹ ہے جن پر عمل درآمد ہونا ضروری ہے۔ اس معاملے میں ڈیٹا کی صفائی میں ڈیٹا کو تبدیل کرنا شامل ہے تاکہ وفاقی قوانین درست ہو جائیں۔ اس صورت میں، ترمیم کی تعداد کم سے کم ہونی چاہیے (اس طریقہ کار کے اپنے الگورتھم ہیں، جن پر ہم اس مضمون میں توجہ نہیں دیں گے)۔ ذیل میں اس طرح کے ڈیٹا کی تبدیلی کی ایک مثال ہے۔ بائیں طرف اصل رشتہ ہے، جس میں، ظاہر ہے، ضروری FL پورے نہیں ہوئے ہیں (FLs میں سے کسی ایک کی خلاف ورزی کی مثال سرخ رنگ میں نمایاں کی گئی ہے)۔ دائیں جانب تازہ ترین رشتہ ہے، جس میں سبز خلیے تبدیل شدہ اقدار کو ظاہر کر رہے ہیں۔ اس طریقہ کار کے بعد، ضروری انحصار کو برقرار رکھا جانے لگا۔

ایک اور مقبول ایپلی کیشن ڈیٹا بیس ڈیزائن ہے۔ یہاں یہ عام شکلوں اور نارملائزیشن کو یاد کرنے کے قابل ہے۔ نارملائزیشن کسی رشتے کو تقاضوں کے ایک مخصوص سیٹ کے مطابق لانے کا عمل ہے، جن میں سے ہر ایک کو اپنے طریقے سے معمول کی شکل میں بیان کیا جاتا ہے۔ ہم مختلف عام شکلوں کی ضروریات کو بیان نہیں کریں گے (یہ ابتدائیوں کے لیے ڈیٹا بیس کورس کی کسی بھی کتاب میں کیا گیا ہے)، لیکن ہم صرف یہ نوٹ کریں گے کہ ان میں سے ہر ایک اپنے طریقے سے فنکشنل انحصار کے تصور کو استعمال کرتا ہے۔ بہر حال، FLs فطری طور پر سالمیت کی رکاوٹیں ہیں جو ڈیٹا بیس کو ڈیزائن کرتے وقت مدنظر رکھی جاتی ہیں (اس کام کے تناظر میں، FLs کو بعض اوقات سپر کیز کہا جاتا ہے)۔

آئیے ذیل کی تصویر میں چار عام شکلوں کے لیے ان کی درخواست پر غور کریں۔ یاد رکھیں کہ Boyce-Codd نارمل شکل تیسری شکل سے زیادہ سخت ہے، لیکن چوتھی شکل سے کم سخت ہے۔ ہم فی الحال مؤخر الذکر پر غور نہیں کر رہے ہیں، کیونکہ اس کی تشکیل کے لیے کثیر قیمتی انحصار کی سمجھ کی ضرورت ہے، جو اس مضمون میں ہمارے لیے دلچسپ نہیں ہیں۔

ایک اور شعبہ جس میں انحصار کو اپنی درخواست ملی ہے وہ کاموں میں خصوصیت کی جگہ کی جہت کو کم کر رہا ہے جیسے کہ ایک سادہ Bayes کی درجہ بندی کرنا، اہم خصوصیات کی نشاندہی کرنا، اور ریگریشن ماڈل کو دوبارہ پیرامیٹر کرنا۔ اصل مضامین میں، اس کام کو بے کار اور خصوصیت کی مطابقت کا تعین کہا جاتا ہے [5, 6]، اور اسے ڈیٹا بیس کے تصورات کے فعال استعمال سے حل کیا جاتا ہے۔ اس طرح کے کاموں کی آمد کے ساتھ، ہم کہہ سکتے ہیں کہ آج ایسے حل کی مانگ ہے جو ہمیں ڈیٹا بیس، تجزیات اور مندرجہ بالا اصلاحی مسائل کے نفاذ کو ایک ٹول میں جوڑنے کی اجازت دیتے ہیں [7, 8, 9]۔

ڈیٹا سیٹ میں وفاقی قوانین کو تلاش کرنے کے لیے بہت سے الگورتھم (جدید اور اتنے جدید دونوں نہیں) ہیں۔ ایسے الگورتھم کو تین گروپوں میں تقسیم کیا جا سکتا ہے:

• الجبری جالیوں کے ٹراورسل کا استعمال کرتے ہوئے الگورتھم (Lattice traversal algorithms)
• متفقہ اقدار کی تلاش پر مبنی الگورتھم (فرق- اور متفق سیٹ الگورتھم)
• جوڑے کے لحاظ سے موازنہ پر مبنی الگورتھم (انحصار انڈکشن الگورتھم)

ہر قسم کے الگورتھم کی ایک مختصر تفصیل ذیل کے جدول میں پیش کی گئی ہے۔


آپ اس درجہ بندی کے بارے میں مزید پڑھ سکتے ہیں [4]۔ ذیل میں ہر قسم کے الگورتھم کی مثالیں ہیں:

فی الحال، نئے الگورتھم نمودار ہو رہے ہیں جو فنکشنل انحصار کو تلاش کرنے کے لیے کئی طریقوں کو یکجا کرتے ہیں۔ ایسے الگورتھم کی مثالیں پائرو [2] اور HyFD [3] ہیں۔ اس سلسلے کے اگلے مضامین میں ان کے کام کا تجزیہ متوقع ہے۔ اس مضمون میں ہم صرف ان بنیادی تصورات اور لیما کا جائزہ لیں گے جو انحصار کا پتہ لگانے کی تکنیک کو سمجھنے کے لیے ضروری ہیں۔

آئیے ایک سادہ سے شروع کریں - فرق- اور اتفاق سیٹ، جو دوسری قسم کے الگورتھم میں استعمال ہوتا ہے۔ ڈیفرینس سیٹ ٹیپلز کا ایک سیٹ ہے جس کی قدریں ایک جیسی نہیں ہیں، جبکہ اتفاق سیٹ، اس کے برعکس، ٹیپلز ہیں جن کی قدریں ایک جیسی ہیں۔ یہ بات قابل غور ہے کہ اس معاملے میں ہم انحصار کے صرف بائیں جانب پر غور کر رہے ہیں۔

ایک اور اہم تصور جس کا اوپر سامنا ہوا وہ ہے الجبری جالی۔ چونکہ بہت سے جدید الگورتھم اس تصور پر کام کرتے ہیں، ہمیں اس کے بارے میں ایک خیال رکھنے کی ضرورت ہے۔

جالی کے تصور کو متعارف کرانے کے لیے، جزوی طور پر ترتیب دیا گیا سیٹ (یا جزوی طور پر ترتیب دیا گیا سیٹ، مختصراً پوسیٹ) کی وضاحت ضروری ہے۔

تعریف 2۔ کہا جاتا ہے کہ ایک سیٹ S کو جزوی طور پر بائنری ریلیشن ⩽ کے ذریعے ترتیب دیا گیا ہے اگر تمام a, b, c ∈ S کے لیے درج ذیل خصوصیات مطمئن ہیں:

1. اضطراری صلاحیت، یعنی a ⩽ a
2. مخالف ہم آہنگی، یعنی اگر a ⩽ b اور b ⩽ a، تو a = b
3. منتقلی، یعنی a ⩽ b اور b ⩽ c کے لیے یہ اس کی پیروی کرتا ہے a ⩽ c

اس طرح کے تعلق کو (ڈھیلا) جزوی ترتیب کا رشتہ کہا جاتا ہے، اور سیٹ خود کو جزوی طور پر ترتیب دیا گیا سیٹ کہا جاتا ہے۔ رسمی اشارے: ⟨S، ⩽⟩۔

جزوی طور پر ترتیب دیے گئے سیٹ کی سب سے آسان مثال کے طور پر، ہم تمام قدرتی اعداد N کے سیٹ کو معمول کے ترتیب کے تعلق ⩽ کے ساتھ لے سکتے ہیں۔ یہ تصدیق کرنا آسان ہے کہ تمام ضروری محور مطمئن ہیں۔

ایک زیادہ معنی خیز مثال۔ تمام ذیلی سیٹوں کے سیٹ پر غور کریں {1, 2, 3}، جو کہ شمولیت کے تعلق سے ترتیب دیا گیا ہے ⊆۔ درحقیقت، یہ تعلق تمام جزوی ترتیب کی شرائط کو پورا کرتا ہے، لہذا ⟨P ({1, 2, 3}), ⊆⟩ جزوی طور پر ترتیب دیا گیا مجموعہ ہے۔ نیچے دی گئی تصویر اس سیٹ کی ساخت کو ظاہر کرتی ہے: اگر ایک عنصر کو تیر کے ذریعے دوسرے عنصر تک پہنچایا جا سکتا ہے، تو وہ ایک ترتیب سے تعلق رکھتے ہیں۔

ہمیں ریاضی کے شعبے سے دو اور آسان تعریفوں کی ضرورت ہوگی - سپریم اور انفیمم۔

تعریف 3۔ آئیے ⟨S، ⩽⟩ کو جزوی طور پر ترتیب دیا گیا سیٹ، A ⊆ S۔ A کا اوپری باؤنڈ ایک عنصر u ∈ S اس طرح ہے کہ ∀x ∈ S: x ⩽ u۔ آئیے U کو S کے تمام اوپری حدود کا سیٹ بنائیں۔ اگر U میں سب سے چھوٹا عنصر ہے، تو اسے سپریمم کہا جاتا ہے اور اسے sup A سے تعبیر کیا جاتا ہے۔

عین نچلی حد کا تصور اسی طرح متعارف کرایا گیا ہے۔

تعریف 4۔ آئیے ⟨S، ⩽⟩ کو جزوی طور پر ترتیب دیا گیا سیٹ، A ⊆ S۔ A کا انفیمم ایک عنصر l ∈ S ایسا ہے کہ ∀x ∈ S: l ⩽ x۔ L کو S کے تمام نچلے باؤنڈز کا سیٹ ہونے دیں۔ اگر L میں ایک سب سے بڑا عنصر ہے، تو اسے infimum کہا جاتا ہے اور inf A کے طور پر ظاہر کیا جاتا ہے۔

مثال کے طور پر اوپر دیے گئے جزوی طور پر ترتیب دیے گئے سیٹ ⟨P ({1, 2, 3})، ⊆⟩ پر غور کریں اور اس میں سب سے اوپر اور infimum تلاش کریں:

اب ہم الجبری جالی کی تعریف تشکیل دے سکتے ہیں۔

تعریف 5۔ ⟨P،⩽⟩ کو جزوی طور پر ترتیب دیا گیا سیٹ بننے دیں کہ ہر دو عنصر کے ذیلی سیٹ کا اوپری اور نچلا باؤنڈ ہو۔ پھر P کو الجبری جالی کہا جاتا ہے۔ اس صورت میں، sup{x, y} کو x ∨ y، اور inf {x, y} کو x ∧ y کے طور پر لکھا جاتا ہے۔

آئیے چیک کریں کہ ہماری کام کرنے والی مثال ⟨P ({1, 2, 3}), ⊆⟩ ایک جالی ہے۔ درحقیقت، کسی بھی a، b ∈ P ({1, 2, 3})، a∨b = a∪b، اور a∧b = a∩b کے لیے۔ مثال کے طور پر، سیٹ {1، 2} اور {1، 3} پر غور کریں اور ان کا انفیمم اور سپریمم تلاش کریں۔ اگر ہم ان کو کاٹتے ہیں تو ہمیں سیٹ {1} ملے گا، جو انفیمم ہوگا۔ ہم ان کو ملا کر سپریمم حاصل کرتے ہیں - {1, 2, 3}۔

جسمانی مسائل کی شناخت کے لیے الگورتھم میں، تلاش کی جگہ کو اکثر جالی کی شکل میں ظاہر کیا جاتا ہے، جہاں ایک عنصر کے سیٹ (سرچ جالی کے پہلے درجے کو پڑھیں، جہاں انحصار کا بائیں جانب ایک وصف پر مشتمل ہوتا ہے) ہر ایک وصف کی نمائندگی کرتا ہے۔ اصل رشتہ کا۔
سب سے پہلے، ہم شکل ∅ → کی انحصار پر غور کرتے ہیں۔ واحد وصف۔ یہ مرحلہ آپ کو یہ تعین کرنے کی اجازت دیتا ہے کہ کون سی صفات بنیادی کلیدیں ہیں (ایسی صفات کے لیے کوئی تعین کنندہ نہیں ہے، اور اس لیے بائیں طرف خالی ہے)۔ مزید، اس طرح کے الگورتھم جالی کے ساتھ اوپر کی طرف بڑھتے ہیں۔ یہ بات قابل غور ہے کہ پوری جالی کو عبور نہیں کیا جا سکتا، یعنی اگر بائیں جانب کا مطلوبہ زیادہ سے زیادہ سائز ان پٹ تک پہنچا دیا جائے، تو الگورتھم اس سائز کے ساتھ ایک سطح سے آگے نہیں جائے گا۔

ذیل کی تصویر دکھاتی ہے کہ FZ تلاش کرنے کے مسئلے میں الجبری جالی کیسے استعمال کی جا سکتی ہے۔ یہاں ہر کنارے (X، XY) انحصار کی نمائندگی کرتا ہے۔ X → Y. مثال کے طور پر، ہم پہلے درجے سے گزر چکے ہیں اور جانتے ہیں کہ علت برقرار ہے A → B (ہم اسے عمودی کے درمیان سبز کنکشن کے طور پر دکھائیں گے۔ A и B)۔ اس کا مطلب یہ ہے کہ مزید، جب ہم جالی کے ساتھ اوپر جاتے ہیں، تو ہم انحصار کی جانچ نہیں کر سکتے A، C → Bکیونکہ یہ اب کم سے کم نہیں رہے گا۔ اسی طرح، ہم اس کی جانچ نہیں کریں گے کہ آیا انحصار رکھا گیا تھا۔ C → B.

اس کے علاوہ، ایک اصول کے طور پر، وفاقی قوانین کی تلاش کے لیے تمام جدید الگورتھم ڈیٹا ڈھانچہ کا استعمال کرتے ہیں جیسے کہ پارٹیشن (اصل ماخذ میں - سٹرپڈ پارٹیشن [1])۔ تقسیم کی رسمی تعریف اس طرح ہے:

تعریف 6۔ آئیے X ⊆ R کو تعلق r کے لیے صفات کا ایک مجموعہ بنائیں۔ ایک کلسٹر r میں ٹیپلز کے انڈیکس کا ایک مجموعہ ہے جس کی قیمت X کے لیے ایک جیسی ہے، یعنی c(t) = {i|ti[X] = t[X]}۔ ایک پارٹیشن کلسٹرز کا ایک سیٹ ہے، یونٹ کی لمبائی کے کلسٹرز کو چھوڑ کر:

آسان الفاظ میں، ایک وصف کے لیے ایک تقسیم X فہرستوں کا ایک مجموعہ ہے، جہاں ہر فہرست میں لائن نمبرز ہوتے ہیں جن کی قدریں ایک جیسی ہوتی ہیں۔ X. جدید ادب میں، پارٹیشنز کی نمائندگی کرنے والے ڈھانچے کو پوزیشن لسٹ انڈیکس (PLI) کہا جاتا ہے۔ یونٹ کی لمبائی والے کلسٹرز کو PLI کمپریشن مقاصد کے لیے خارج کر دیا گیا ہے کیونکہ وہ ایسے کلسٹرز ہیں جن میں صرف ایک ریکارڈ نمبر ہوتا ہے جس کی منفرد قدر ہوتی ہے جس کی شناخت کرنا ہمیشہ آسان ہوتا ہے۔

آئیے ایک مثال دیکھتے ہیں۔ آئیے مریضوں کے ساتھ اسی میز پر واپس آتے ہیں اور کالموں کے لیے پارٹیشن بناتے ہیں۔ مریض۔ и پال (بائیں طرف ایک نیا کالم نمودار ہوا ہے، جس میں ٹیبل کے قطار کے نمبر نشان زد ہیں):

مزید یہ کہ تعریف کے مطابق کالم کے لیے تقسیم مریض۔ اصل میں خالی ہو جائے گا، کیونکہ سنگل کلسٹرز کو پارٹیشن سے خارج کر دیا گیا ہے۔

پارٹیشنز کو کئی صفات سے حاصل کیا جا سکتا ہے۔ اور ایسا کرنے کے دو طریقے ہیں: ٹیبل سے گزر کر، تمام ضروری صفات کو ایک ساتھ استعمال کرتے ہوئے ایک پارٹیشن بنائیں، یا اوصاف کے سب سیٹ کا استعمال کرتے ہوئے پارٹیشنز کے انٹرسیکشن کے آپریشن کا استعمال کرتے ہوئے اسے بنائیں۔ وفاقی قانون کی تلاش کے الگورتھم دوسرا آپشن استعمال کرتے ہیں۔

سادہ الفاظ میں، مثال کے طور پر، کالم کے لحاظ سے تقسیم حاصل کرنا ABC، آپ پارٹیشنز لے سکتے ہیں۔ AC и B (یا منقطع ذیلی سیٹوں کا کوئی دوسرا سیٹ) اور انہیں ایک دوسرے سے کاٹ دیں۔ دو پارٹیشنز کے انٹرسیکشن کا آپریشن سب سے بڑی لمبائی کے کلسٹرز کا انتخاب کرتا ہے جو دونوں پارٹیشنز میں مشترک ہیں۔

آئیے ایک مثال دیکھتے ہیں:

پہلی صورت میں، ہمیں ایک خالی پارٹیشن ملا۔ اگر آپ میز کو قریب سے دیکھتے ہیں، تو درحقیقت، دونوں صفات کے لیے کوئی ایک جیسی اقدار نہیں ہیں۔ اگر ہم ٹیبل میں تھوڑا سا ترمیم کرتے ہیں (دائیں طرف کا کیس)، تو ہمیں پہلے سے ہی ایک غیر خالی چوراہا ملے گا۔ مزید یہ کہ لائنیں 1 اور 2 دراصل صفات کے لیے ایک جیسی اقدار پر مشتمل ہیں۔ پال и ڈاکٹر۔.

اگلا، ہمیں پارٹیشن سائز جیسے تصور کی ضرورت ہوگی۔ رسمی طور پر:

سیدھے الفاظ میں، پارٹیشن سائز پارٹیشن میں شامل کلسٹرز کی تعداد ہے (یاد رکھیں کہ ایک کلسٹرز پارٹیشن میں شامل نہیں ہیں!):

اب ہم کلیدی لیموں میں سے ایک کی وضاحت کر سکتے ہیں، جو دیے گئے پارٹیشنز کے لیے ہمیں یہ تعین کرنے کی اجازت دیتا ہے کہ انحصار ہے یا نہیں:

لیما 1. انحصار A, B → C رکھتا ہے اگر اور صرف اس صورت میں

لیما کے مطابق، اس بات کا تعین کرنے کے لیے کہ آیا انحصار ہے، چار مراحل کو انجام دینا ضروری ہے:

1. انحصار کے بائیں جانب کی تقسیم کا حساب لگائیں۔
2. انحصار کے دائیں طرف کی تقسیم کا حساب لگائیں۔
3. پہلے اور دوسرے مرحلے کی پیداوار کا حساب لگائیں۔
4. پہلے اور تیسرے مراحل میں حاصل کردہ پارٹیشنز کے سائز کا موازنہ کریں۔

ذیل میں یہ جانچنے کی ایک مثال ہے کہ آیا انحصار اس لیما کے مطابق ہے:

اس آرٹیکل میں، ہم نے تصورات کا جائزہ لیا جیسے فنکشنل انحصار، لگ بھگ فنکشنل انحصار، یہ دیکھا کہ وہ کہاں استعمال ہوتے ہیں، اور ساتھ ہی جسمانی افعال کی تلاش کے لیے کون سے الگورتھم موجود ہیں۔ ہم نے ان بنیادی لیکن اہم تصورات کا بھی تفصیل سے جائزہ لیا جو وفاقی قوانین کی تلاش کے لیے جدید الگورتھم میں فعال طور پر استعمال ہوتے ہیں۔

حوالہ جات:

1. Huhtala Y. et al. ٹین: فنکشنل اور تخمینی انحصار کو دریافت کرنے کے لیے ایک موثر الگورتھم // کمپیوٹر جرنل۔ - 1999. - T. 42. - نمبر. 2۔ صفحہ 100-111۔
2. Kruse S.، Naumann F. تخمینی انحصار کی موثر دریافت // VLDB انڈومنٹ کی کارروائی۔ – 2018 – T. 11. – نمبر۔ 7۔ صفحہ 759-772۔
3. Papenbrock T.، Naumann F. ایک ہائبرڈ اپروچ ٹو فنکشنل انحصار کی دریافت // ڈیٹا کے انتظام پر 2016 کی بین الاقوامی کانفرنس کی کارروائی۔ – ACM، 2016۔ – صفحہ 821-833۔
4. Papenbrock T. et al. فنکشنل انحصار کی دریافت: سات الگورتھم کی تجرباتی تشخیص // VLDB انڈومنٹ کی کارروائی۔ - 2015. - T. 8. - نمبر. 10۔ صفحہ 1082-1093۔
5. کمار اے وغیرہ۔ شامل ہونا یا شامل ہونا؟: فیچر کے انتخاب سے پہلے شمولیت کے بارے میں دو بار سوچنا // ڈیٹا کے انتظام پر 2016 کی بین الاقوامی کانفرنس کی کارروائی۔ – ACM، 2016۔ – صفحہ 19-34۔
6. ابو خامس ایم وغیرہ۔ اسپارس ٹینسرز کے ساتھ ڈیٹا بیس میں سیکھنا // ڈیٹا بیس سسٹمز کے اصولوں پر 37ویں ACM SIGMOD-SIGACT-SIGAI سمپوزیم کی کارروائی۔ – ACM، 2018۔ – صفحہ 325-340۔
7. Hellerstein J. M. et al. MADlib تجزیاتی لائبریری: یا MAD مہارتیں، SQL // VLDB Endowment کی کارروائی۔ - 2012. - T. 5. - نمبر. 12. - صفحہ 1700-1711۔
8. کن سی.، روسو ایف. ٹیرا اسکیل کے لیے قیاس آرائی پر مبنی تخمینے تقسیم شدہ گریڈینٹ ڈیسنٹ آپٹیمائزیشن // کلاؤڈ میں ڈیٹا اینالیٹکس پر چوتھی ورکشاپ کی کارروائی۔ - ACM، 2015 - صفحہ 1۔
9. Meng X. et al. ملیب: اپاچی اسپارک میں مشین لرننگ // مشین لرننگ ریسرچ کا جرنل۔ - 2016. - T. 17. - نمبر. 1۔ صفحہ 1235-1241۔

مضمون کے مصنفین: اناستاسیا بریلوپر محقق جیٹ برینز ریسرچ, سی ایس سینٹر کا طالب علم и نکیتا بوبروفپر محقق جیٹ برینز ریسرچ

ماخذ: www.habr.com