هن آرٽيڪل ۾ اسين ڊيٽابيس ۾ فنڪشنل انحصار جي باري ۾ ڳالهائينداسين - اهي ڇا آهن، اهي ڪٿي استعمال ڪيا ويا آهن ۽ انهن کي ڳولڻ لاء ڪهڙا الگورتھم موجود آهن.
اسان لاڳاپو ڊيٽابيس جي حوالي سان فنڪشنل انحصار تي غور ڪنداسين. ان کي بلڪل چٽيءَ طرح بيان ڪجي ته اهڙي ڊيٽابيس ۾ معلومات جدولن جي صورت ۾ محفوظ ڪئي ويندي آهي. اڳيون، اسان تقريبن تصورات استعمال ڪندا آهيون جيڪي سخت رشتي واري نظريي ۾ مٽائي نه سگھندا آهن: اسان ٽيبل کي پاڻ کي هڪ تعلق سڏينداسين، ڪالمن - خاصيتون (انهن جو سيٽ - هڪ رشتي اسڪيما)، ۽ صفات جي هڪ ذيلي سيٽ تي قطار جي قيمتن جو سيٽ. - هڪ ٽوپي.
مثال طور، مٿي ڏنل جدول ۾، (بينسن، ايم، ايم آرگن) صفتن جو هڪ ٽڪرو آهي (مريض، پال، ڊاڪٽر).
وڌيڪ رسمي طور تي، هي هن ريت لکيو ويو آهي: [مريض، جنس، ڊاڪٽر] = (بينسن، ايم، ايم آرگن).
هاڻي اسان فنڪشنل انحصار (FD) جو تصور متعارف ڪرائي سگهون ٿا:
وصف 1. تعلق R وفاقي قانون کي پورو ڪري ٿو X → Y (جتي X، Y ⊆ R) جيڪڏهن ۽ صرف جيڪڏهن ڪنهن ٽوپل لاءِ , ∈ R رکي ٿو: if [X] = [X]، پوءِ [ي] = [ي]. انهي صورت ۾، اسان چئون ٿا ته X (تعين ڪندڙ، يا صفتن جو سيٽ) فنڪشنل طور تي Y (انحصار سيٽ) کي طئي ڪري ٿو.
ٻين لفظن ۾، هڪ وفاقي قانون جي موجودگي X → Y مطلب ته جيڪڏهن اسان وٽ ٻه ٽوپل آهن R ۽ اهي خاصيتون ۾ ملن ٿا X، پوءِ اهي صفتن ۾ ملندا Y.
۽ هاڻي، ترتيب ۾. اچو ته خاصيتون ڏسو هڪ مريض и جنس جنهن لاءِ اسان اهو معلوم ڪرڻ چاهيون ٿا ته انهن جي وچ ۾ انحصار آهي يا نه. خاصيتن جي اهڙي سيٽ لاء، هيٺيون انحصار موجود ٿي سگھي ٿو:
- مريض → جنس
- جنس → مريض
جيئن مٿي بيان ڪيو ويو آهي، ترتيب ڏيڻ لاء پهرين انحصار لاء، هر منفرد ڪالمن جي قيمت هڪ مريض صرف هڪ ڪالمن جو قدر ملندو جنس. ۽ مثال جي جدول لاءِ اهو واقعي آهي. بهرحال، اهو ڪم مخالف طرف ۾ نٿو ڪري، اهو آهي، ٻيو انحصار مطمئن نه آهي، ۽ خاصيت جنس لاء مقرر نه آهي مريض. ساڳئي طرح، جيڪڏهن اسان انحصار وٺون ٿا ڊاڪٽر → مريض، توهان ڏسي سگهو ٿا ته ان جي ڀڃڪڙي ڪئي وئي آهي، قيمت کان وٺي Robin ھن صفت جا ڪيترائي مختلف مطلب آھن - ايلس ۽ گراهم.
اهڙيء طرح، فنڪشنل انحصار ان کي ممڪن بڻائي ٿو ته موجوده رشتي کي جدول جي خاصيتن جي سيٽن جي وچ ۾ طئي ڪرڻ. ھتان کان پوء اسين سڀ کان وڌيڪ دلچسپ ڪنيڪشن تي غور ڪنداسين، يا ان جي بدران X → Yاهي ڇا آهن:
- غير معمولي، اهو آهي، انحصار جي ساڄي پاسي کاٻي جو هڪ ذيلي سيٽ نه آهي (Y ̸⊆ X);
- گھٽ ۾ گھٽ، اھو آھي، ڪو به انحصار نه آھي Z → Y، اهو Z ⊂ X.
انحصار هن نقطي تي غور ڪيو ويو سخت هو، اهو آهي ته، انهن ميز تي ڪنهن به خلاف ورزي لاء مهيا نه ڪيو، پر انهن کان علاوه، اهي پڻ آهن جيڪي ٽوپل جي قدرن جي وچ ۾ ڪجهه تضاد جي اجازت ڏين ٿيون. اهڙا انحصار هڪ الڳ ڪلاس ۾ رکيا ويا آهن، جن کي لڳ ڀڳ سڏيو ويندو آهي، ۽ انهن کي ٽوپل جي هڪ خاص تعداد جي خلاف ورزي ڪرڻ جي اجازت آهي. اها رقم وڌ ۾ وڌ غلطي جي اشاري ايمڪس پاران منظم ڪئي وئي آهي. مثال طور، غلطي جي شرح = 0.01 جو مطلب ٿي سگھي ٿو ته انحصار جي خلاف ورزي ٿي سگھي ٿو 1٪ دستياب ٽپلس جي سمجھي سيٽ تي منسوب ڪيل. اھو آھي، 1000 ريڪارڊ لاء، وڌ ۾ وڌ 10 ٽوپلس وفاقي قانون جي ڀڃڪڙي ڪري سگھن ٿا. اسان هڪ ٿورڙي مختلف ميٽرڪ تي غور ڪنداسين، جنهن جي بنياد تي ٽيپل جي مختلف قدرن جي مقابلي ۾. لت لاءِ X → Y رويي تي r اهو هن طرح سمجهيو ويندو آهي:
اچو ته غلطي جي حساب سان ڊاڪٽر → مريض مٿين مثال مان. اسان وٽ ٻه ٽوپل آهن جن جي قيمت خاصيت تي مختلف آهي هڪ مريض، پر اتفاق سان ڊاڪٽر: [ڊاڪٽر ، مريض] = (رابن، ايلس) ۽ [ڊاڪٽر ، مريض] = (رابن، گراهم). غلطي جي تعريف جي پٺيان، اسان کي سڀني متضاد جوڑوں کي حساب ۾ رکڻ گهرجي، جنهن جو مطلب آهي ته انهن مان ٻه هوندا: (, ) ۽ ان جو ڦيرو (, ). اچو ته ان کي فارمولا ۾ متبادل بڻايون ۽ حاصل ڪريو:
هاڻي اچو ته سوال جو جواب ڏيڻ جي ڪوشش ڪريو: "اهو سڀ ڪجهه ڇو آهي؟" حقيقت ۾، وفاقي قانون مختلف آهن. پهريون قسم اهي انحصار آهن جيڪي ڊيٽابيس ڊيزائن اسٽيج تي منتظم طرفان مقرر ڪيا ويا آهن. اهي عام طور تي تعداد ۾ ٿورڙا آهن، سخت، ۽ بنيادي ايپليڪيشن ڊيٽا کي عام ڪرڻ ۽ لاڳاپيل اسڪيما ڊيزائن آهي.
ٻيو قسم انحصار آهي، جيڪو "لڪيل" ڊيٽا جي نمائندگي ڪري ٿو ۽ صفات جي وچ ۾ اڳ ۾ اڻڄاتل رشتا. اهو آهي، ڊزائن جي وقت تي اهڙي انحصار بابت نه سوچيو ويو آهي ۽ اهي اڳ ۾ ئي موجود ڊيٽا سيٽ لاء مليا آهن، تنهنڪري بعد ۾، ڪيترن ئي سڃاڻپ ٿيل وفاقي قانونن جي بنياد تي، ذخيرو ٿيل معلومات بابت ڪو به نتيجو ڪڍي سگهجي ٿو. اهو خاص طور تي اهي انحصار آهن جن سان اسان ڪم ڪريون ٿا. انهن کي ڊيل ڪيو ويو آهي ڊيٽا مائننگ جي پوري فيلڊ سان مختلف ڳولا جي ٽيڪنڪ ۽ الگورتھم سان انهن جي بنياد تي ٺاهيل. اچو ته اهو معلوم ڪريون ته ڪنهن به ڊيٽا ۾ موجود فنڪشنل انحصار (ساڳي يا لڳ ڀڳ) ڪيئن ڪارائتو ٿي سگهي ٿو.
اڄ، انحصار جي مکيه ايپليڪيشنن مان هڪ آهي ڊيٽا جي صفائي. اهو "گندي ڊيٽا" جي سڃاڻپ ڪرڻ ۽ پوء ان کي درست ڪرڻ لاء ترقي ڪندڙ عمل شامل آهي. ”گندي ڊيٽا“ جا نمايان مثال آهن نقل، ڊيٽا ۾ غلطيون يا ٽائپ، گم ٿيل قدر، پراڻي ڊيٽا، اضافي اسپيس، وغيره.
ڊيٽا جي غلطي جو مثال:
ڊيٽا ۾ نقل جا مثال:
مثال طور، اسان وٽ هڪ ٽيبل آهي ۽ وفاقي قانونن جو هڪ سيٽ جنهن تي عمل ڪيو وڃي. هن معاملي ۾ ڊيٽا کي صاف ڪرڻ ۾ ڊيٽا کي تبديل ڪرڻ شامل آهي ته جيئن وفاقي قانون درست ٿي وڃن. انهي حالت ۾، تبديلين جو تعداد گهٽ ۾ گهٽ هجڻ گهرجي (هن طريقي سان پنهنجي الگورتھم آهي، جنهن تي اسان هن مضمون ۾ ڌيان نه ڏينداسين). هيٺ ڏنل ڊيٽا جي اهڙي تبديلي جو هڪ مثال آهي. کاٻي پاسي اصل تعلق آھي، جنھن ۾، ظاھر آھي، ضروري FLs نه مليا آھن (ھڪڙو FLs جي خلاف ورزي جو ھڪڙو مثال ڳاڙھي ۾ نمايان ٿيل آھي). ساڄي پاسي تازو ٿيل تعلق آهي، سائي سيلن سان تبديل ٿيل قدر ڏيکاريندي. هن طريقيڪار کان پوء، ضروري انحصار برقرار رکڻ شروع ڪيو.
ٻيو مشهور ايپليڪيشن ڊيٽابيس ڊيزائن آهي. هتي ان کي ياد ڪرڻ جي قابل آهي عام فارم ۽ normalization. نارملائيزيشن (Normalization) هڪ رشتي کي ضرورتن جي هڪ خاص سيٽ سان مطابقت ۾ آڻڻ جو عمل آهي، جن مان هر هڪ پنهنجي انداز ۾ عام شڪل جي وضاحت ڪري ٿو. اسان مختلف عام فارمن جي ضرورتن کي بيان نه ڪنداسين (اهو ڪنهن به ڪتاب ۾ شروع ڪندڙن لاء ڊيٽابيس ڪورس تي ڪيو ويو آهي)، پر اسان صرف اهو نوٽ ڪنداسين ته انهن مان هر هڪ پنهنجي طريقي سان فنڪشنل انحصار جي تصور کي استعمال ڪري ٿو. سڀ کان پوء، FLs موروثي طور تي سالميت جي رڪاوٽون آهن جيڪي اڪائونٽ ۾ رکيا ويندا آهن جڏهن ڊيٽابيس ٺاهي رهيا آهن (هن ڪم جي حوالي سان، FLs ڪڏهن ڪڏهن سپر ڪيز سڏيو ويندو آهي).
اچو ته ھيٺ ڏنل تصوير ۾ چار عام فارمن لاء انھن جي درخواست تي غور ڪريو. ياد رهي ته Boyce-Codd عام فارم ٽين فارم کان وڌيڪ سخت آهي، پر چوٿين کان گهٽ سخت آهي. اسان هن وقت لاءِ بعد ۾ غور نه ڪري رهيا آهيون، ڇاڪاڻ ته ان جي ٺهڻ لاءِ گهڻ-قيمتي انحصار کي سمجهڻ جي ضرورت آهي، جيڪي هن مضمون ۾ اسان لاءِ دلچسپ نه آهن.
هڪ ٻيو علائقو جنهن ۾ انحصار مليا آهن انهن جي ايپليڪيشن ڪمن ۾ فيچر اسپيس جي طول و عرض کي گهٽائيندي آهي جيئن ته هڪ بيوقوف بيز ڪلاسفير تعمير ڪرڻ، اهم خاصيتن جي نشاندهي ڪرڻ، ۽ ريگريشن ماڊل کي ٻيهر ترتيب ڏيڻ. اصل مضمونن ۾، هن ڪم کي فالتو ۽ خصوصيت جي مطابقت جو تعين سڏيو ويندو آهي [5, 6]، ۽ اهو ڊيٽابيس تصورات جي فعال استعمال سان حل ڪيو ويندو آهي. اهڙن ڪمن جي اچڻ سان، اسان اهو چئي سگهون ٿا ته اڄ حل جي گهرج آهي، جيڪا اسان کي ڊيٽابيس، تجزياتي ۽ مٿين اصلاح جي مسئلن جي عمل کي هڪ اوزار ۾ گڏ ڪرڻ جي اجازت ڏئي ٿي [7، 8، 9].
ڊيٽا سيٽ ۾ وفاقي قانونن جي ڳولا لاءِ ڪيترائي الگورتھم (ٻئي جديد ۽ جديد نه آھن) آھن. اھڙين الگورتھم کي ٽن گروھن ۾ ورهائي سگھجي ٿو:
- الجبري لٽيسس جي ٽرورسل استعمال ڪندي الگورتھم (Lattice traversal algorithms)
- اتفاق ڪيل قدرن جي ڳولا جي بنياد تي الگورتھم (فرق- ۽ متفق-سيٽ الگورتھم)
- الگورتھم جو بنياد تي ٻڌل مقابلي (انحصار شامل ڪرڻ الگورتھم)
هر قسم جي الگورتھم جو مختصر بيان هيٺ ڏنل جدول ۾ پيش ڪيو ويو آهي:
توهان هن درجي بندي بابت وڌيڪ پڙهي سگهو ٿا [4]. هيٺ ڏنل هر قسم جي الگورتھم جا مثال آهن:
في الحال، نوان الگورتھم ظاهر ٿي رهيا آهن جيڪي فنڪشنل انحصار کي ڳولڻ لاء ڪيترن ئي طريقن کي گڏ ڪن ٿا. اهڙن الگورتھم جا مثال آهن Pyro [2] ۽ HyFD [3]. انهن جي ڪم جو هڪ تجزيو هن سلسلي جي ايندڙ مضمونن ۾ متوقع آهي. هن آرٽيڪل ۾ اسان صرف بنيادي تصورات ۽ ليما جو جائزو وٺندا سين جيڪي ضروري آهن انحصار ڳولڻ جي ٽيڪنالاجي کي سمجهڻ لاء.
اچو ته هڪ سادي سان شروع ڪريون- فرق- ۽ اتفاق- سيٽ، ٻئي قسم جي الگورتھم ۾ استعمال ٿيل. فرق-سيٽ ٽوپلن جو هڪ سيٽ آهي جنهن ۾ هڪجهڙا قدر نه هوندا آهن، جڏهن ته اتفاق-سيٽ، ان جي برعڪس، ٽيپلز آهن جن ۾ ساڳيا قدر آهن. اها ڳالهه نوٽ ڪرڻ گهرجي ته هن معاملي ۾ اسان کي رڳو انحصار جي کاٻي پاسي تي غور ڪري رهيا آهن.
هڪ ٻيو اهم تصور جيڪو مٿي سامهون آيو آهي اهو آهي الجبرائي لٽيس. جيئن ته ڪيترائي جديد الگورتھم هن تصور تي هلندا آهن، اسان کي اهو ڄاڻڻ گهرجي ته اهو ڇا آهي.
لٽيس جي تصور کي متعارف ڪرائڻ لاءِ، ضروري آھي ته ھڪ جزوي ترتيب ڏنل سيٽ (يا جزوي طور تي ترتيب ڏنل سيٽ، مخفف طور تي پوسيٽ) جي وضاحت ڪرڻ ضروري آھي.
وصف 2. هڪ سيٽ S چيو ويندو آهي جزوي طور تي ترتيب ڏنل بائنري رشتي ⩽ جيڪڏهن سڀني لاءِ a, b, c ∈ S هيٺيون خاصيتون مطمئن آهن:
- Reflexivity، يعني هڪ ⩽ a
- مخالف هم آهنگي، يعني جيڪڏهن a ⩽ b ۽ b ⩽ a، ته پوءِ a = b
- Transitivity، يعني، 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 ۾ ھڪڙو وڏو عنصر آھي، پوء ان کي انفيم سڏيو ويندو آھي ۽ ان کي inf A جي نالي سان بيان ڪيو ويندو آھي.
مثال طور مٿي ڏنل جزوي ترتيب ڏنل سيٽ ⟨P ({1, 2, 3})، ⊆⟩ تي غور ڪريو ۽ ان ۾ اعليٰ ۽ انفيمم ڳوليو:
ھاڻي اسان ھڪ الجبري لٽيس جي تعريف ٺاھي سگھون ٿا.
وصف 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). هن جو مطلب اهو آهي ته اڳتي وڌو، جڏهن اسان جالي سان گڏ مٿي وڃون ٿا، اسان انحصار کي نه ٿا جانچي سگهون الف، سي → ب، ڇاڪاڻ ته اهو هاڻي گهٽ ۾ گهٽ نه هوندو. ساڳئي طرح، اسان ان کي جانچ نه ڪنداسين ته انحصار منعقد ڪيو ويو سي → ب.
ان کان علاوه، ضابطي جي طور تي، وفاقي قانونن کي ڳولڻ لاء سڀ جديد الگورتھم ڊيٽا جي جوڙجڪ کي استعمال ڪن ٿا جهڙوڪ ورهاڱي (اصل ماخذ ۾ - ورهايل ورهاڱي [1]). ورهاڱي جي رسمي تعريف هن ريت آهي:
وصف 6. اچو ته X ⊆ R کي رشتي r لاءِ خاصيتن جو هڪ سيٽ ڪيو وڃي. ڪلستر r ۾ ٽوپلن جي اشارن جو هڪ سيٽ آهي جنهن جي قيمت X لاءِ ساڳي آهي، يعني c(t) = {i|ti[X] = t[X]}. ورهاڱي ڪلستر جو هڪ سيٽ آهي، يونٽ جي ڊيگهه جي ڪلسٽرن کان سواء:
سادي لفظن ۾، هڪ وصف لاء هڪ ورهاڱي X فهرستن جو هڪ سيٽ آهي، جتي هر لسٽ ۾ ساڳين قدرن سان لائن نمبر شامل آهن X. جديد ادب ۾، ورهاڱي جي نمائندگي ڪندڙ ساخت کي پوزيشن لسٽ انڊيڪس (PLI) سڏيو ويندو آهي. يونٽ ڊگھائي ڪلسٽرز PLI ڪمپريشن مقصدن لاءِ خارج ڪيا ويا آھن ڇاڪاڻ ته اھي ڪلسٽر آھن جن ۾ صرف ھڪ رڪارڊ نمبر ھوندو آھي ھڪڙي منفرد قدر سان جنھن کي سڃاڻڻ ھميشه آسان ھوندو.
اچو ته هڪ مثال ڏسو. اچو ته مريضن سان ساڳي ٽيبل تي واپس وڃو ۽ ڪالمن لاء ورهاڱي ٺاهي هڪ مريض и جنس (هڪ نئون ڪالم کاٻي پاسي ظاهر ٿيو آهي، جنهن ۾ ٽيبل جي قطار جا نمبر نشان لڳل آهن):
ان کان علاوه، تعريف جي مطابق، ورهاڱي لاء ڪالمن هڪ مريض اصل ۾ خالي هوندو، ڇاڪاڻ ته اڪيلو ڪلستر ورهاڱي مان خارج ٿيل آهن.
Partitions ڪيترن ئي خاصيتن سان حاصل ڪري سگهجي ٿو. ۽ ائين ڪرڻ جا ٻه طريقا آهن: ٽيبل ذريعي وڃڻ سان، هڪ ئي وقت ۾ سڀئي ضروري خاصيتون استعمال ڪندي هڪ ورهاڱي کي ٺاهيو، يا ان کي ٺاهيو ان کي پارشنز جي چونڪ جي آپريشن کي استعمال ڪندي خاصيتن جي سبسيٽ کي استعمال ڪندي. وفاقي قانون ڳولها الگورتھم ٻئي اختيار کي استعمال ڪن ٿا.
سادي لفظن ۾، مثال طور، ڪالمن طرفان ورهاڱي حاصل ڪرڻ لاء جي سهولت, توهان لاء partitions وٺي سگهو ٿا AC и B (يا جدا جدا ذيلي سيٽن جو ڪو ٻيو سيٽ) ۽ انهن کي هڪ ٻئي سان ڳنڍيو. ٻن ڀاڱن جي چونڪ جو آپريشن تمام وڏي ڊگھائي جا ڪلستر چونڊيندو آھي جيڪي ٻنھي ڀاڱن ۾ عام آھن.
اچو ته هڪ مثال ڏسو:
پهرين صورت ۾، اسان هڪ خالي ورهاڱي حاصل ڪيو. جيڪڏهن توهان ميز تي ويجهي نظر اچن ٿا، ته پوء حقيقت ۾، انهن ٻن خاصيتن لاء هڪجهڙائي قدر نه آهن. جيڪڏهن اسان ٽيبل کي ٿورڙو تبديل ڪريون ٿا (ساڄي پاسي وارو ڪيس)، اسان اڳ ۾ ئي هڪ غير خالي چونڪ حاصل ڪنداسين. ان کان علاوه، لائنون 1 ۽ 2 اصل ۾ خاصيتون لاء ساڳيا قدر شامل آهن جنس и ڊاڪٽر.
اڳيون، اسان کي اهڙي تصور جي ضرورت پوندي جيئن ورهاڱي جي سائيز. رسمي طور:
آسان لفظ ۾، ورهاڱي جي ماپ آهي ڪلستر جو تعداد جيڪو ورهاڱي ۾ شامل آهي (ياد رکو ته اڪيلو ڪلستر ورهاڱي ۾ شامل نه آهن!):
ھاڻي اسان ھڪ اھم ليما جي وضاحت ڪري سگھون ٿا، جنھن کي ڏنل ڀاڱن لاءِ اسان کي اھو طئي ڪرڻ جي اجازت ڏئي ٿي ته ڇا انحصار رکيل آھي يا نه:
ليما 1. انحصار A, B → C رکي ٿو جيڪڏھن ۽ صرف جيڪڏھن
ليما جي مطابق، اهو طئي ڪرڻ لاء ته ڇا انحصار رکي ٿو، چار مرحلن کي انجام ڏيڻ گهرجي:
- انحصار جي کاٻي پاسي لاء ورهاڱي جي حساب ڪريو
- انحصار جي ساڄي پاسي لاء ورهاڱي جي حساب ڪريو
- پهرين ۽ ٻئي قدم جي پيداوار جو حساب ڪريو
- پهرين ۽ ٽئين مرحلن ۾ حاصل ڪيل حصن جي سائزن جو مقابلو ڪريو
هيٺ ڏنل هڪ مثال آهي چيڪ ڪرڻ جو ته ڇا انحصار هن ليما جي مطابق آهي:
هن آرٽيڪل ۾، اسان تصورن جي جانچ ڪئي جهڙوڪ فنڪشنل انحصار، تقريبن فنڪشنل انحصار، ڏٺو ويو ته اهي ڪٿي استعمال ڪيا ويا آهن، انهي سان گڏ جسماني افعال جي ڳولا لاء ڪهڙا الگورتھم موجود آهن. اسان پڻ تفصيل سان جانچيو بنيادي پر اهم تصورات جيڪي فعال طور تي استعمال ڪيا ويا آهن جديد الگورتھم ۾ وفاقي قانونن جي ڳولا لاءِ.
حوالا:
- Huhtala Y. et al. TANE: فنڪشنل ۽ تقريبن انحصار کي ڳولڻ لاء هڪ موثر الگورتھم // ڪمپيوٽر جرنل. - 1999. - ٽي. 42. - نمبر. 2. ص 100-111.
- Kruse S.، Naumann F. لڳ ڀڳ انحصار جي موثر دريافت // VLDB اوقاف جي عمل. - 2018. - ٽي. 11. - نمبر. 7. ص 759-772.
- Papenbrock T.، Naumann F. فنڪشنل انحصار جي دريافت لاء هڪ هائبرڊ اپروچ // ڊيٽا جي انتظام تي 2016 جي بين الاقوامي ڪانفرنس جي عمل. - ACM، 2016. - pp. 821-833.
- Papenbrock T. et al. فنڪشنل انحصار دريافت: ست الگورتھم جو هڪ تجرباتي جائزو // VLDB انڊومينٽ جي عمل. - 2015. - ٽي. 8. - نمبر. 10. ص 1082-1093.
- ڪمار اي وغيره. شامل ٿيڻ يا نه ٿيڻ لاءِ؟: فيچر جي چونڊ کان اڳ شامل ٿيڻ بابت ٻه ڀيرا سوچڻ // ڊيٽا جي انتظام تي 2016 جي بين الاقوامي ڪانفرنس جي ڪارروائي. - ACM، 2016. - ص 19-34.
- ابو خامس M. et al. اسپارس ٽينسر سان گڏ ڊيٽابيس ۾ سکيا // 37th ACM SIGMOD-SIGACT-SIGAI سمپوزيم جي عملن تي ڊيٽابيس سسٽم جي اصولن تي. - ACM، 2018. - pp. 325-340.
- Hellerstein J.M. et al. MADlib تجزياتي لائبريري: يا MAD صلاحيتن، SQL // VLDB Endowment جي عمل. - 2012. - ٽي. 5. - نمبر. 12. - ص 1700-1711.
- Qin C.، Rusu F. terascale distributed gradient descent optimization لاءِ تصنيفاتي تقريبن // ڪلائوڊ ۾ ڊيٽا اينالائيٽڪس تي چوٿين ورڪشاپ جي ڪارروائي. - ACM، 2015. - P. 1.
- مينگ ايڪس وغيره. مليب: اپاچي اسپارڪ ۾ مشين لرننگ // دي جرنل آف مشين لرننگ ريسرچ. - 2016. - ٽي. 17. - نمبر. 1. ص 1235-1241.
مضمون جا ليکڪ: ، محقق تي , и ، محقق تي
جو ذريعو: www.habr.com