দক্ষতার সাথে ডাটাবেসে কার্যকরী নির্ভরতা খুঁজুন

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

কার্য নির্বাচন

সিএস সেন্টারে অধ্যয়ন করার সময়, আমি গভীরভাবে ডেটাবেস অধ্যয়ন করতে শুরু করি, যথা, কার্যকরী এবং পার্থক্য নির্ভরতার অনুসন্ধান। এই বিষয়টি বিশ্ববিদ্যালয়ে আমার কোর্সওয়ার্কের বিষয়ের সাথে সম্পর্কিত ছিল, তাই কোর্সওয়ার্কে কাজ করার সময়, আমি ডাটাবেসের বিভিন্ন নির্ভরতা সম্পর্কে নিবন্ধ পড়তে শুরু করি। আমি এই এলাকার একটি পর্যালোচনা লিখেছিলাম - আমার প্রথম এক নিবন্ধ ইংরেজিতে এবং এটি SEIM-2017 সম্মেলনে জমা দিয়েছে। আমি খুব খুশি হয়েছিলাম যখন আমি জানতে পারলাম যে সে সব পরে গৃহীত হয়েছে, এবং বিষয়টির আরও গভীরে যাওয়ার সিদ্ধান্ত নিয়েছি। ধারণাটি নিজেই নতুন নয় - এটি 90 এর দশকে ব্যবহার করা শুরু হয়েছিল, তবে এখনও এটি অনেক ক্ষেত্রে ব্যবহৃত হয়।

কেন্দ্রে আমার দ্বিতীয় সেমিস্টারের সময়, আমি কার্যকরী নির্ভরতা খুঁজে বের করার জন্য অ্যালগরিদম উন্নত করার জন্য একটি গবেষণা প্রকল্প শুরু করেছি। তিনি জেটব্রেইন্স রিসার্চের সেন্ট পিটার্সবার্গ স্টেট ইউনিভার্সিটির স্নাতক ছাত্র নিকিতা বব্রভের সাথে একসাথে এটিতে কাজ করেছেন।

কার্যকরী নির্ভরতা অনুসন্ধানের গণনাগত জটিলতা

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

পার্টিশন ইন্টারসেকশনের জন্য ক্যাশিং স্কিম

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

অতএব, আমরা শ্যানন এনট্রপি এবং জিনি অনিশ্চয়তার উপর ভিত্তি করে একটি হিউরিস্টিক প্রস্তাব করেছি, সেইসাথে আমাদের মেট্রিক, যাকে আমরা বলেছিলাম বিপরীত এনট্রপি। এটি শ্যানন এনট্রপির সামান্য পরিবর্তন এবং ডেটা সেটের স্বতন্ত্রতা বৃদ্ধির সাথে সাথে এটি বৃদ্ধি পায়। প্রস্তাবিত হিউরিস্টিক নিম্নরূপ:

এটা হল — সম্প্রতি গণনা করা পার্টিশনের স্বতন্ত্রতার মাত্রা এবং স্বতন্ত্র বৈশিষ্ট্যের জন্য স্বতন্ত্রতার মাত্রার মধ্যক। উপরে বর্ণিত তিনটি মেট্রিকই একটি স্বতন্ত্রতা মেট্রিক হিসাবে পরীক্ষা করা হয়েছিল। আপনি লক্ষ্য করতে পারেন যে হিউরিস্টিকটিতে দুটি পরিবর্তনকারী রয়েছে। প্রথমটি নির্দেশ করে বর্তমান পার্টিশনটি প্রাইমারি কী-এর কতটা কাছাকাছি এবং সম্ভাব্য কী থেকে দূরে থাকা পার্টিশনগুলিকে আরও বেশি পরিমাণে ক্যাশে করার অনুমতি দেয়। দ্বিতীয় সংশোধক আপনাকে ক্যাশে দখল নিরীক্ষণ করতে দেয় এবং এর ফলে ফাঁকা স্থান উপলব্ধ থাকলে ক্যাশে আরও পার্টিশন যোগ করতে উৎসাহিত করে। এই সমস্যার সফল সমাধান ডেটাসেটের উপর নির্ভর করে PYRO অ্যালগরিদমকে 10-40% গতি বাড়ানোর অনুমতি দিয়েছে। এটি লক্ষণীয় যে PYRO অ্যালগরিদম এই ক্ষেত্রে সবচেয়ে সফল।

নীচের চিত্রে আপনি একটি মৌলিক মুদ্রা-ফ্লিপ ক্যাশিং পদ্ধতির তুলনায় প্রস্তাবিত হিউরিস্টিক প্রয়োগের ফলাফল দেখতে পারেন। X অক্ষ লগারিদমিক।

পার্টিশন সংরক্ষণ করার একটি বিকল্প উপায়

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

$$display$$pi(X) = {{আন্ডারব্রেস{1, 2, 3, 4, 5}_{প্রথম ব্যবধান}, আন্ডারব্রেস{7, 8}_{দ্বিতীয় ব্যবধান}, 10}}\ downarrow{ কম্প্রেশন} \ pi(X) = {{আন্ডারব্রেস{$, 1, 5}_{প্রথম~ইন্টারভাল}, আন্ডারব্রেস{7, 8}_{সেকেন্ড~ইনটারভাল}, 10}}$$display$$

এই পদ্ধতিটি TANE অ্যালগরিদমের অপারেশন চলাকালীন মেমরি খরচ 1 থেকে 25% কমাতে সক্ষম হয়েছিল। TANE অ্যালগরিদম হল ফেডারেল আইন অনুসন্ধানের জন্য একটি ক্লাসিক অ্যালগরিদম; এটি কাজ করার সময় পার্টিশন ব্যবহার করে। অনুশীলনের অংশ হিসাবে, TANE অ্যালগরিদমটি বেছে নেওয়া হয়েছিল, যেহেতু প্রস্তাবিত পদ্ধতিটি কাজ করে কিনা তা মূল্যায়ন করার জন্য PYRO-এর তুলনায় এটিতে ইন্টারভাল স্টোরেজ প্রয়োগ করা অনেক সহজ ছিল। প্রাপ্ত ফলাফল নীচের চিত্রে উপস্থাপন করা হয়. X অক্ষ লগারিদমিক।

সম্মেলন ADBIS-2019

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

উত্স: www.habr.com