কার্যকরী নির্ভরতার ভূমিকা

এই নিবন্ধে, আমরা ডাটাবেসের কার্যকরী নির্ভরতা সম্পর্কে কথা বলব - সেগুলি কী, কোথায় ব্যবহার করা হয় এবং সেগুলি খুঁজে বের করার জন্য কোন অ্যালগরিদম বিদ্যমান।

আমরা রিলেশনাল ডাটাবেসের প্রেক্ষাপটে কার্যকরী নির্ভরতা বিবেচনা করব। খুব মোটামুটিভাবে বলতে গেলে, এই ধরনের ডেটাবেসে তথ্য টেবিল আকারে সংরক্ষণ করা হয়। এর পরে, আমরা আনুমানিক ধারণাগুলি ব্যবহার করি যেগুলি কঠোর সম্পর্কীয় তত্ত্বে বিনিময়যোগ্য নয়: টেবিলটিকে নিজেই একটি সম্পর্ক বলা হবে, কলামগুলিকে অ্যাট্রিবিউট বলা হবে (তাদের সেটটি একটি সম্পর্ক স্কিমা), এবং একটি উপসেটে সারি মানগুলির সেট গুণাবলী একটি tuple বলা হবে.

উদাহরণস্বরূপ, উপরের টেবিলে, (বেনসন, এম, মরগান) গুণাবলী দ্বারা একটি tuple (রোগী, পল, ডাক্তার).
আরো আনুষ্ঠানিকভাবে, এটি নিম্নরূপ লেখা হয়: [রোগী, পল, ডাক্তার]= (বেনসন, এম, মরগান).
এখন আমরা কার্যকরী নির্ভরতা (FC) ধারণাটি প্রবর্তন করতে পারি:

সংজ্ঞা 1. সম্পর্ক R FD X → Y (যেখানে X, Y ⊆ R) সন্তুষ্ট করে যদি এবং শুধুমাত্র যদি কোনো টিপলের জন্য , ∈ R সন্তুষ্ট: যদি [x]= [এক্স], তারপর [ওয়াই] = [ওয়াই]। এই ধরনের ক্ষেত্রে, X (নির্ধারক বা বৈশিষ্ট্যগুলির সংজ্ঞায়িত সেট) কার্যকরীভাবে Y (নির্ভরশীল সেট) নির্ধারণ করে।

অন্য কথায়, একটি ফেডারেল আইন উপস্থিতি X→Y এর মানে হল যদি আমাদের দুটি টিপল থাকে R এবং তারা বৈশিষ্ট্য মেলে X, তারপর তারা বৈশিষ্ট্য দ্বারা মিলবে Y.
এবং এখন ক্রমে. গুণাবলী বিবেচনা করুন একজন রোগী и পল যার জন্য আমরা জানতে চাই তাদের মধ্যে নির্ভরতা আছে কি না। গুণাবলীর এই ধরনের একটি সেটের জন্য, নিম্নলিখিত নির্ভরতা থাকতে পারে:

1. রোগী → লিঙ্গ
2. লিঙ্গ → রোগী

উপরের সংজ্ঞা অনুসারে, প্রথম নির্ভরতা ধরে রাখার জন্য, কলামের প্রতিটি অনন্য মান একজন রোগী শুধুমাত্র একটি কলাম মান অবশ্যই মিলবে পল. এবং উদাহরণ টেবিলের জন্য, এই সত্য. যাইহোক, এটি বিপরীত দিকে কাজ করে না, অর্থাৎ, দ্বিতীয় নির্ভরতা পূরণ হয় না, এবং বৈশিষ্ট্য পল জন্য একটি নির্ধারক নয় রোগী. একইভাবে, আমরা যদি নির্ভরতা গ্রহণ করি ডাক্তার → রোগী, আপনি দেখতে পারেন যে এটি লঙ্ঘন করা হয়েছে, যেহেতু মান পক্ষীবিশেষ এই বৈশিষ্ট্যের বিভিন্ন মান আছে - এলিস এবং গ্রাহাম.

এইভাবে, কার্যকরী নির্ভরতা আপনাকে টেবিলের বৈশিষ্ট্যগুলির সেটগুলির মধ্যে বিদ্যমান সম্পর্কগুলি নির্ধারণ করতে দেয়। এখান থেকে এবং এখন থেকে, আমরা সবচেয়ে আকর্ষণীয় সংযোগগুলি বিবেচনা করব, বা বরং, যেমন X→Yকি তারা:

• নন-তুচ্ছ, অর্থাৎ নির্ভরতার ডান দিকটি বাম দিকের উপসেট নয় (Y ⊆ X);
• ন্যূনতম, অর্থাৎ, এমন কোন নির্ভরতা নেই Z → Y, যে Z ⊂ X.

এই বিন্দু পর্যন্ত বিবেচিত নির্ভরতাগুলি কঠোর ছিল, অর্থাৎ, তারা টেবিলে কোনও লঙ্ঘনের জন্য সরবরাহ করেনি, তবে সেগুলি ছাড়াও, এমনগুলিও রয়েছে যা টিপলের মানগুলির মধ্যে কিছু অসঙ্গতিকে অনুমতি দেয়। এই ধরনের নির্ভরতাগুলিকে একটি পৃথক শ্রেণীতে নেওয়া হয়, যাকে আনুমানিক বলা হয়, এবং সেগুলিকে নির্দিষ্ট সংখ্যক টিপলে লঙ্ঘন করার অনুমতি দেওয়া হয়। এই সংখ্যা সর্বোচ্চ ত্রুটি নির্দেশক emax দ্বারা সমন্বয় করা হয়. উদাহরণস্বরূপ, ত্রুটির হার = 0.01 এর অর্থ হতে পারে যে বিবেচিত বৈশিষ্ট্যগুলির সেটে উপলব্ধ টিপলের 1% দ্বারা নির্ভরতা লঙ্ঘন হতে পারে। অর্থাৎ, 1000টি রেকর্ডের জন্য, সর্বাধিক 10 টি টিপল ফেডারেল আইন লঙ্ঘন করতে পারে। আমরা তুলনা করা টিপলগুলির জোড়াভিত্তিক বিভিন্ন মানের উপর ভিত্তি করে একটি সামান্য ভিন্ন মেট্রিক বিবেচনা করব। আসক্তির জন্য X→Y সম্পর্ক r এটা এই মত গণনা করা হয়:

এর জন্য ত্রুটি গণনা করা যাক ডাক্তার → রোগী উপরের উদাহরণ থেকে। আমাদের দুটি টিপল রয়েছে যার মানগুলি বৈশিষ্ট্যে আলাদা একজন রোগী, কিন্তু সাথে মিলে যায় ডাক্তার: [ডাক্তার, রোগী] = (রবিন, এলিস) এবং [ডাক্তার, রোগী] = (রবিন, গ্রাহাম) একটি ত্রুটির সংজ্ঞা অনুসরণ করে, আমাদের অবশ্যই সমস্ত বিরোধপূর্ণ জোড়া বিবেচনা করতে হবে, যার অর্থ তাদের মধ্যে দুটি থাকবে :(, ) এবং এর বিপরীত (, ) সূত্রে প্রতিস্থাপন করুন এবং পান:

এবং এখন প্রশ্নটির উত্তর দেওয়ার চেষ্টা করা যাক: "কেন এটি সব?"। আসলে, FZ ভিন্ন। প্রথম প্রকার হল সেইসব নির্ভরতা যা অ্যাডমিনিস্ট্রেটর দ্বারা ডাটাবেস ডিজাইন পর্যায়ে সংজ্ঞায়িত করা হয়। সাধারণত কিছু আছে, তারা কঠোর, এবং প্রধান অ্যাপ্লিকেশন হল ডেটা স্বাভাবিককরণ এবং সম্পর্ক স্কিমা ডিজাইন।

দ্বিতীয় প্রকারটি হল "লুকানো" ডেটা এবং বৈশিষ্ট্যগুলির মধ্যে পূর্বে অজানা সম্পর্কগুলিকে উপস্থাপন করে নির্ভরতা। অর্থাৎ, এই ধরনের নির্ভরতাগুলি ডিজাইনের সময় চিন্তা করা হয়নি এবং সেগুলি ইতিমধ্যেই বিদ্যমান ডেটা সেটের জন্য পাওয়া গেছে, যাতে পরে, চিহ্নিত FD-এর সেটের উপর ভিত্তি করে, সঞ্চিত তথ্য সম্পর্কে কোনো সিদ্ধান্তে আসা যায়। এই ধরনের নির্ভরতা নিয়েই আমরা কাজ করি। তারা তাদের ভিত্তিতে নির্মিত বিভিন্ন অনুসন্ধান কৌশল এবং অ্যালগরিদম সহ ডেটা মাইনিংয়ের পুরো ক্ষেত্রে নিযুক্ত রয়েছে। আসুন জেনে নেই যে কোন ডেটাতে পাওয়া কার্যকরী নির্ভরতা (সঠিক বা আনুমানিক) কীভাবে কার্যকর হতে পারে।

আজ, নির্ভরতা প্রয়োগের প্রধান ক্ষেত্রগুলির মধ্যে, ডেটা পরিষ্কারকে আলাদা করা হয়। এটি "নোংরা ডেটা" সনাক্ত করার এবং তারপরে তাদের সংশোধন করার জন্য প্রক্রিয়াগুলির বিকাশ জড়িত। "নোংরা ডেটা" এর উজ্জ্বল প্রতিনিধি হল সদৃশ, ডেটা ত্রুটি বা টাইপো, অনুপস্থিত মান, পুরানো ডেটা, অতিরিক্ত স্পেস এবং এর মতো।

ডেটা ত্রুটি উদাহরণ:

ডেটাতে নকলের উদাহরণ:

উদাহরণস্বরূপ, আমাদের কাছে একটি টেবিল এবং ফেডারেল আইনগুলির একটি সেট রয়েছে যা অবশ্যই পূরণ করতে হবে। এই ক্ষেত্রে ডেটা ক্লিনিং এমনভাবে ডেটা পরিবর্তন করে যাতে ফেডারেল আইন সত্য হয়। একই সময়ে, পরিবর্তনের সংখ্যা ন্যূনতম হওয়া উচিত (এই পদ্ধতির জন্য অ্যালগরিদম রয়েছে, যা আমরা এই নিবন্ধে ফোকাস করব না)। নীচে যেমন একটি তথ্য রূপান্তর একটি উদাহরণ. বাম দিকে প্রাথমিক সম্পর্ক রয়েছে, যেখানে স্পষ্টতই, প্রয়োজনীয় এফএলগুলি পূরণ করা হয় না (এফএলগুলির একটির লঙ্ঘনের একটি উদাহরণ লাল রঙে হাইলাইট করা হয়েছে)। ডানদিকে আপডেট করা সম্পর্ক, সবুজ কক্ষগুলি পরিবর্তিত মানগুলি দেখায়। এই ধরনের একটি পদ্ধতি বহন করার পরে, প্রয়োজনীয় নির্ভরতা বজায় রাখা শুরু হয়।

অ্যাপ্লিকেশনের আরেকটি জনপ্রিয় ক্ষেত্র হল ডাটাবেস ডিজাইন। এখানে এটি স্বাভাবিক ফর্ম এবং স্বাভাবিকীকরণ সম্পর্কে স্মরণ করা মূল্যবান। নর্মালাইজেশন হল একটি সম্পর্ককে কিছু সেটের প্রয়োজনীয়তার সাথে সঙ্গতিপূর্ণ করার প্রক্রিয়া, যার প্রতিটি তার নিজস্ব উপায়ে স্বাভাবিক ফর্ম দ্বারা সংজ্ঞায়িত করা হয়। আমরা বিভিন্ন স্বাভাবিক ফর্মের প্রয়োজনীয়তাগুলি বর্ণনা করব না (এটি নতুনদের জন্য ডাটাবেস কোর্সের যে কোনও বইয়ে করা হয়েছে), তবে শুধুমাত্র মনে রাখবেন যে তাদের প্রত্যেকটি নিজস্ব উপায়ে কার্যকরী নির্ভরতার ধারণা ব্যবহার করে। সর্বোপরি, এফডিগুলি অন্তর্নিহিতভাবে অখণ্ডতার সীমাবদ্ধতা যা একটি ডাটাবেস ডিজাইন করার সময় বিবেচনায় নেওয়া হয় (এই কাজের প্রেক্ষাপটে, এফডিগুলিকে কখনও কখনও সুপারকি বলা হয়)।

নীচের ছবিতে চারটি সাধারণ ফর্মের জন্য তাদের আবেদন বিবেচনা করুন। প্রত্যাহার করুন যে Boyce-Codd স্বাভাবিক ফর্ম তৃতীয় ফর্মের তুলনায় আরো কঠোর, কিন্তু চতুর্থটির চেয়ে কম কঠোর। আমরা এখনও পরেরটি বিবেচনা করি না, যেহেতু এটির প্রণয়নের জন্য বহু-মূল্যবান নির্ভরতার বোঝার প্রয়োজন, যা এই নিবন্ধে আমাদের আগ্রহের নয়।

আরেকটি ক্ষেত্র যেখানে নির্ভরতাগুলি তাদের পথ খুঁজে পেয়েছে তা হল একটি নিষ্পাপ বেইস ক্লাসিফায়ার তৈরি করা, উল্লেখযোগ্য বৈশিষ্ট্যগুলি বের করা এবং একটি রিগ্রেশন মডেলকে পুনরায় প্যারামেট্রিজ করার মতো সমস্যার ক্ষেত্রে বৈশিষ্ট্য স্থানের মাত্রা হ্রাস করা। মূল নিবন্ধগুলিতে, এই সমস্যাটিকে অপ্রয়োজনীয় বৈশিষ্ট্য (বৈশিষ্ট্যের অপ্রয়োজনীয়তা) এবং প্রাসঙ্গিক (বৈশিষ্ট্যের প্রাসঙ্গিকতা) নির্ধারণ বলা হয় [5, 6], এবং এটি ডাটাবেস ধারণাগুলির সক্রিয় ব্যবহারের মাধ্যমে সমাধান করা হয়। এই ধরনের কাজগুলির উপস্থিতির সাথে, আমরা বলতে পারি যে আজ এমন সমাধানগুলির চাহিদা রয়েছে যা ডাটাবেস, বিশ্লেষণ এবং উপরের অপ্টিমাইজেশন সমস্যাগুলিকে একটি টুলে [7, 8, 9] একত্রিত করার অনুমতি দেয়।

একটি ডেটা সেটে FD অনুসন্ধান করার জন্য অনেকগুলি অ্যালগরিদম (আধুনিক এবং খুব আধুনিক নয় উভয়ই) রয়েছে৷ এই জাতীয় অ্যালগরিদমগুলিকে তিনটি গ্রুপে ভাগ করা যেতে পারে:

• ল্যাটিস ট্রাভার্সাল অ্যালগরিদম
• সামঞ্জস্যপূর্ণ মান অনুসন্ধানের উপর ভিত্তি করে অ্যালগরিদম (পার্থক্য- এবং সম্মত-সেট অ্যালগরিদম)
• জোড়াভিত্তিক তুলনার উপর ভিত্তি করে অ্যালগরিদম (নির্ভরতা আনয়ন অ্যালগরিদম)

প্রতিটি ধরণের অ্যালগরিদমের একটি সংক্ষিপ্ত বিবরণ নীচের সারণীতে উপস্থাপন করা হয়েছে:


এই শ্রেণীবিভাগ সম্পর্কে আরও বিশদ [4] এ পাওয়া যাবে। নীচে প্রতিটি ধরণের জন্য অ্যালগরিদমের উদাহরণ রয়েছে:

বর্তমানে, নতুন অ্যালগরিদম আবির্ভূত হচ্ছে যা একবারে কার্যকরী নির্ভরতা খুঁজে বের করার জন্য বিভিন্ন পদ্ধতির সমন্বয় করে। এই ধরনের অ্যালগরিদমের উদাহরণ হল Pyro [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-এ যদি সবচেয়ে বড় কোনো উপাদান থাকে, তাহলে তাকে ইনফিমাম বলা হয় এবং 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}।

এফডি সনাক্তকরণ অ্যালগরিদমগুলিতে, অনুসন্ধানের স্থানটি প্রায়শই একটি জালির আকারে উপস্থাপন করা হয়, যেখানে একটি উপাদানের সেট (সার্চ জালির প্রথম স্তরটি পড়ুন, যেখানে নির্ভরতার বাম দিকে একটি বৈশিষ্ট্য রয়েছে) প্রতিটি বৈশিষ্ট্যকে উপস্থাপন করে। মূল সম্পর্ক।
শুরুতে, ফর্মের নির্ভরতা ∅ → একক বৈশিষ্ট্য। এই পদক্ষেপটি আপনাকে কোন বৈশিষ্ট্যগুলি প্রাথমিক কীগুলি নির্ধারণ করতে দেয় (এই জাতীয় বৈশিষ্ট্যগুলির জন্য কোনও নির্ধারক নেই এবং তাই বাম দিকটি খালি)। আরও, এই ধরনের অ্যালগরিদমগুলি জালির উপরে চলে যায়। একই সময়ে, এটি লক্ষণীয় যে পুরো জালিটিকে বাইপাস করা যায় না, অর্থাৎ, যদি বাম দিকের পছন্দসই সর্বাধিক আকারটি ইনপুটে পাস করা হয়, তবে অ্যালগরিদম এই আকারের সাথে স্তরের বাইরে যাবে না।

নীচের চিত্রটি দেখায় যে আপনি কীভাবে FD অনুসন্ধানের সমস্যায় বীজগণিত জালি ব্যবহার করতে পারেন। এখানে, প্রতিটি প্রান্ত (এক্স, এক্সওয়াই) নির্ভরতা প্রতিনিধিত্ব করে X→Y. উদাহরণস্বরূপ, আমরা প্রথম স্তর পাস করেছি এবং আমরা জানি যে নির্ভরতা অনুষ্ঠিত হচ্ছে A→ B (আমরা শীর্ষবিন্দুগুলির মধ্যে একটি সবুজ সংযোগ দিয়ে এটি প্রদর্শন করব A и B) তাই আরও, যখন আমরা জালি উপরে উঠি, আমরা নির্ভরতা পরীক্ষা করতে পারি না A, C→ B, কারণ এটি আর ন্যূনতম হবে না। একইভাবে, নির্ভরশীলতা অনুষ্ঠিত হলে আমরা এটি পরীক্ষা করব না C→B.

উপরন্তু, একটি নিয়ম হিসাবে, FDs অনুসন্ধানের জন্য সমস্ত আধুনিক অ্যালগরিদম পার্টিশন হিসাবে এই জাতীয় ডেটা কাঠামো ব্যবহার করে (মূল উত্সে - স্ট্রাইপড পার্টিশন [1])। একটি পার্টিশনের আনুষ্ঠানিক সংজ্ঞা নিম্নরূপ:

সংজ্ঞা 6. ধরা যাক X ⊆ R সম্পর্ক r-এর জন্য বৈশিষ্ট্যগুলির একটি সেট। একটি ক্লাস্টার হল r থেকে টিপলের সূচকগুলির একটি সেট যার মান X এর জন্য একই, যেমন c(t) = {i|ti[X] = t[X]}। একটি পার্টিশন হল একক দৈর্ঘ্যের ক্লাস্টার বাদ দিয়ে ক্লাস্টারগুলির একটি সেট:

সহজ ভাষায়, একটি বৈশিষ্ট্যের জন্য একটি পার্টিশন X তালিকার একটি সেট, যেখানে প্রতিটি তালিকার জন্য একই মান সহ লাইন সংখ্যা রয়েছে X. আধুনিক সাহিত্যে, পার্টিশনের প্রতিনিধিত্বকারী একটি কাঠামোকে পজিশন লিস্ট ইনডেক্স (PLI) বলা হয়। একক দৈর্ঘ্যের ক্লাস্টারগুলি PLI কম্প্রেশনের উদ্দেশ্যে বাদ দেওয়া হয়েছে কারণ সেগুলি এমন ক্লাস্টার যাতে শুধুমাত্র একটি অনন্য মান সহ একটি রেকর্ড নম্বর থাকে যা সবসময় সেট করা সহজ হবে।

একটি উদাহরণ বিবেচনা করুন। আসুন রোগীদের সাথে একই টেবিলে ফিরে যাই এবং কলামগুলির জন্য পার্টিশন তৈরি করি একজন রোগী и পল (বাম দিকে একটি নতুন কলাম উপস্থিত হয়েছে, যেখানে টেবিলের সারি নম্বরগুলি চিহ্নিত করা হয়েছে):

এই ক্ষেত্রে, সংজ্ঞা অনুযায়ী, কলামের জন্য পার্টিশন একজন রোগী আসলে খালি থাকবে, যেহেতু একক ক্লাস্টারগুলিকে পার্টিশন থেকে বাদ দেওয়া হয়েছে।

পার্টিশন বিভিন্ন বৈশিষ্ট্য দ্বারা প্রাপ্ত করা যেতে পারে. এবং এর জন্য দুটি উপায় রয়েছে: টেবিলের মধ্য দিয়ে হেঁটে, সমস্ত প্রয়োজনীয় বৈশিষ্ট্যগুলির দ্বারা একবারে একটি পার্টিশন তৈরি করুন বা বৈশিষ্ট্যগুলির একটি উপসেট দ্বারা পার্টিশনগুলি অতিক্রম করার অপারেশন ব্যবহার করে এটি তৈরি করুন। FD অনুসন্ধান অ্যালগরিদম দ্বিতীয় বিকল্প ব্যবহার করে।

সহজ কথায়, উদাহরণস্বরূপ, কলাম দ্বারা একটি পার্টিশন পেতে অ আ ক খ, আপনি পার্টিশন নিতে পারেন জন্য AC и B (অথবা ডিসজয়েন্ট সাবসেটের অন্য কোন সেট) এবং একে অপরের সাথে ছেদ করে। দুটি পার্টিশন অতিক্রম করার ক্রিয়াকলাপ সর্বাধিক দৈর্ঘ্যের ক্লাস্টারগুলি নির্বাচন করে যা উভয় পার্টিশনে সাধারণ।

একটি উদাহরণ নেওয়া যাক:

প্রথম ক্ষেত্রে, আমরা একটি খালি পার্টিশন পেয়েছি। আপনি যদি টেবিলটি ঘনিষ্ঠভাবে দেখেন তবে প্রকৃতপক্ষে, দুটি বৈশিষ্ট্যের জন্য কোন অভিন্ন মান নেই। যদি আমরা টেবিলটি সামান্য পরিবর্তন করি (ডানদিকের কেস), তাহলে আমরা ইতিমধ্যে একটি অ-খালি ছেদ পাব। একই সময়ে, লাইন 1 এবং 2 সত্যিই বৈশিষ্ট্যগুলির জন্য একই মান ধারণ করে পল и ডাক্তার.

এর পরে, আমাদের পার্টিশনের আকারের মতো একটি ধারণা দরকার। আনুষ্ঠানিকভাবে:

সহজ কথায়, পার্টিশনের আকার হল পার্টিশনে অন্তর্ভুক্ত ক্লাস্টারের সংখ্যা (মনে রাখবেন যে একক ক্লাস্টারগুলি পার্টিশনে অন্তর্ভুক্ত নয়!):

এখন আমরা মূল লেমাগুলির মধ্যে একটিকে সংজ্ঞায়িত করতে পারি, যা প্রদত্ত পার্টিশনের জন্য, নির্ভরতা রাখা হয়েছে কিনা তা নির্ধারণ করতে দেয়:

লেম্মা ঘ. নির্ভরতা A, B → C যদি এবং শুধুমাত্র যদি হয়

লেমার মতে, নির্ভরতা রাখা হচ্ছে কিনা তা নির্ধারণ করার জন্য চারটি ধাপ রয়েছে:

1. নির্ভরতার বাম দিকের জন্য পার্টিশন গণনা করুন
2. নির্ভরতার ডান দিকের জন্য পার্টিশন গণনা করুন
3. প্রথম এবং দ্বিতীয় ধাপের গুণফল গণনা করুন
4. প্রথম এবং তৃতীয় ধাপে প্রাপ্ত পার্টিশনের আকার তুলনা করুন

এই লেমা দ্বারা নির্ভরতা রাখা হয়েছে কিনা তা পরীক্ষা করার একটি উদাহরণ নীচে দেওয়া হল:

এই নিবন্ধে, আমরা কার্যকরী নির্ভরতা, আনুমানিক কার্যকরী নির্ভরতা, সেগুলি কোথায় ব্যবহার করা হয় তা পরীক্ষা করে এবং এফডি অনুসন্ধানের জন্য কোন অ্যালগরিদম বিদ্যমান এর মতো ধারণাগুলি বিশ্লেষণ করেছি। আমরা মৌলিক, কিন্তু গুরুত্বপূর্ণ ধারণাগুলিও বিশদভাবে বিশ্লেষণ করেছি যেগুলি FDs অনুসন্ধানের জন্য আধুনিক অ্যালগরিদমে সক্রিয়ভাবে ব্যবহৃত হয়।

সাহিত্যের লিঙ্ক:

1. হুহতালা ওয়াই এট আল। TANE: কার্যকরী এবং আনুমানিক নির্ভরতা আবিষ্কারের জন্য একটি দক্ষ অ্যালগরিদম // কম্পিউটার জার্নাল। - 1999। - টি। 42। - না। 2. - এস. 100-111।
2. ক্রুস এস., নউম্যান এফ. আনুমানিক নির্ভরতাগুলির দক্ষ আবিষ্কার //ভিএলডিবি এনডাউমেন্টের কার্যক্রম। - 2018। - T. 11. - না। 7. - এস. 759-772।
3. Papenbrock T., Naumann F. কার্যকরী নির্ভরতা আবিষ্কারের জন্য একটি হাইব্রিড পদ্ধতি // ডেটা ম্যানেজমেন্ট অন 2016 ইন্টারন্যাশনাল কনফারেন্সের কার্যক্রম। - ACM, 2016। - P. 821-833।
4. Papenbrock T. et al. কার্যকরী নির্ভরতা আবিষ্কার: সাতটি অ্যালগরিদমের একটি পরীক্ষামূলক মূল্যায়ন //ভিএলডিবি এনডাউমেন্টের কার্যক্রম। - 2015. - টি. 8. - না। 10. - এস. 1082-1093।
5. কুমার এট আল। যোগ দিতে বা না যোগ দিতে?: ফিচার নির্বাচনের আগে যোগদানের বিষয়ে দুবার চিন্তা করা // ডেটা ম্যানেজমেন্ট অন 2016 আন্তর্জাতিক সম্মেলনের কার্যক্রম। - ACM, 2016। - S. 19-34।
6. Abo Khamis M. et al. ইন-ডেটাবেস লার্নিং উইথ স্পারস টেনসর // প্রসিডিংস অফ দ্য 37 তম ACM SIGMOD-SIGACT-SIGAI সিম্পোজিয়াম অন প্রিন্সিপলস অফ ডাটাবেস সিস্টেম। - ACM, 2018। - P. 325-340।
7. হেলারস্টেইন জেএম এট আল। MADlib অ্যানালিটিক্স লাইব্রেরি: বা MAD দক্ষতা, SQL // Proceedings of the VLDB Endowment. - 2012. - ভি. 5. - না। 12. - এস. 1700-1711।
8. কিন সি., রুসু এফ. টেরাস্কেল ডিস্ট্রিবিউটেড গ্রেডিয়েন্ট ডিসেন্ট অপ্টিমাইজেশানের জন্য অনুমানমূলক অনুমান // ক্লাউডে ডেটা বিশ্লেষণের উপর চতুর্থ কর্মশালার প্রক্রিয়া। - ACM, 2015. - পৃ. 1।
9. মেং এক্স. এট আল। মিলিব: অ্যাপাচি স্পার্কে মেশিন লার্নিং // মেশিন লার্নিং রিসার্চের জার্নাল। - 2016. - টি. 17. - না। 1. - এস. 1235-1241।

প্রবন্ধ লেখক: আনাস্তাসিয়া বিরিলো, গবেষক JetBrains গবেষণা, সিএস ছাত্র и নিকিতা বব্রভ, গবেষক JetBrains গবেষণা

উত্স: www.habr.com