ഡാറ്റാബേസുകളിൽ പ്രവർത്തനപരമായ ഡിപൻഡൻസികൾ കാര്യക്ഷമമായി കണ്ടെത്തുക

ഡാറ്റയിലെ പ്രവർത്തനപരമായ ഡിപൻഡൻസികൾ കണ്ടെത്തുന്നത് ഡാറ്റ വിശകലനത്തിന്റെ വിവിധ മേഖലകളിൽ ഉപയോഗിക്കുന്നു: ഡാറ്റാബേസ് മാനേജ്മെന്റ്, ഡാറ്റ ക്ലീനിംഗ്, ഡാറ്റാബേസ് റിവേഴ്സ് എഞ്ചിനീയറിംഗ്, ഡാറ്റാ പര്യവേക്ഷണം. ആശ്രിതത്വങ്ങളെക്കുറിച്ച് ഞങ്ങൾ ഇതിനകം പ്രസിദ്ധീകരിച്ചിട്ടുണ്ട് ഒരു ലേഖനം അനസ്താസിയ ബിറില്ലോയും നികിത ബോബ്രോവും. ഇത്തവണ, ഈ വർഷം കമ്പ്യൂട്ടർ സയൻസ് സെന്ററിലെ ബിരുദധാരിയായ അനസ്താസിയ, കേന്ദ്രത്തിൽ പ്രതിരോധിച്ച ഗവേഷണ പ്രവർത്തനത്തിന്റെ ഭാഗമായി ഈ സൃഷ്ടിയുടെ വികസനം പങ്കിടുന്നു.

ടാസ്ക് തിരഞ്ഞെടുക്കൽ

സി‌എസ് സെന്ററിൽ പഠിക്കുമ്പോൾ, ഞാൻ ഡാറ്റാബേസുകൾ ആഴത്തിൽ പഠിക്കാൻ തുടങ്ങി, അതായത്, പ്രവർത്തനപരവും വ്യത്യസ്തവുമായ ഡിപൻഡൻസികൾക്കായുള്ള തിരയൽ. ഈ വിഷയം യൂണിവേഴ്സിറ്റിയിലെ എന്റെ കോഴ്‌സ് വർക്കിന്റെ വിഷയവുമായി ബന്ധപ്പെട്ടതാണ്, അതിനാൽ കോഴ്‌സ് വർക്കിൽ ജോലി ചെയ്യുമ്പോൾ, ഡാറ്റാബേസുകളിലെ വിവിധ ഡിപൻഡൻസികളെക്കുറിച്ചുള്ള ലേഖനങ്ങൾ ഞാൻ വായിക്കാൻ തുടങ്ങി. ഞാൻ ഈ മേഖലയെക്കുറിച്ച് ഒരു അവലോകനം എഴുതി - എന്റെ ആദ്യത്തേതിൽ ഒന്ന് ലേഖനങ്ങൾ ഇംഗ്ലീഷിൽ അത് SEIM-2017 കോൺഫറൻസിൽ സമർപ്പിച്ചു. എല്ലാത്തിനുമുപരി, അവൾ അംഗീകരിക്കപ്പെട്ടുവെന്ന് അറിഞ്ഞപ്പോൾ ഞാൻ വളരെ സന്തോഷിച്ചു, വിഷയത്തിലേക്ക് കൂടുതൽ ആഴത്തിൽ പരിശോധിക്കാൻ തീരുമാനിച്ചു. ഈ ആശയം തന്നെ പുതിയതല്ല - 90 കളിൽ ഇത് ഉപയോഗിക്കാൻ തുടങ്ങി, പക്ഷേ ഇപ്പോൾ പോലും ഇത് പല മേഖലകളിലും ഉപയോഗിക്കുന്നു.

കേന്ദ്രത്തിലെ എന്റെ രണ്ടാം സെമസ്റ്റർ സമയത്ത്, പ്രവർത്തനപരമായ ഡിപൻഡൻസികൾ കണ്ടെത്തുന്നതിനുള്ള അൽഗോരിതം മെച്ചപ്പെടുത്തുന്നതിനായി ഞാൻ ഒരു ഗവേഷണ പദ്ധതി ആരംഭിച്ചു. ജെറ്റ് ബ്രെയിൻസ് റിസർച്ചിൽ സെന്റ് പീറ്റേഴ്‌സ്ബർഗ് സ്റ്റേറ്റ് യൂണിവേഴ്‌സിറ്റി ബിരുദ വിദ്യാർത്ഥിനി നികിത ബോബ്രോവിനൊപ്പം അവർ അതിൽ പ്രവർത്തിച്ചു.

ഫങ്ഷണൽ ഡിപൻഡൻസികൾക്കായി തിരയുന്നതിന്റെ കമ്പ്യൂട്ടേഷണൽ സങ്കീർണ്ണത

പ്രധാന പ്രശ്നം കമ്പ്യൂട്ടേഷണൽ സങ്കീർണ്ണതയാണ്. സാധ്യമായ ഏറ്റവും കുറഞ്ഞതും നിസ്സാരമല്ലാത്തതുമായ ഡിപൻഡൻസികളുടെ എണ്ണം മുകളിൽ മൂല്യം കൊണ്ട് പരിമിതപ്പെടുത്തിയിരിക്കുന്നു എവിടെ - പട്ടിക ആട്രിബ്യൂട്ടുകളുടെ എണ്ണം. അൽഗോരിതങ്ങളുടെ പ്രവർത്തന സമയം ആട്രിബ്യൂട്ടുകളുടെ എണ്ണത്തെ മാത്രമല്ല, വരികളുടെ എണ്ണത്തെയും ആശ്രയിച്ചിരിക്കുന്നു. 90-കളിൽ, ഒരു സാധാരണ ഡെസ്‌ക്‌ടോപ്പ് പിസിയിലെ ഫെഡറൽ നിയമ തിരയൽ അൽഗോരിതങ്ങൾക്ക് 20 ആട്രിബ്യൂട്ടുകളും പതിനായിരക്കണക്കിന് വരികളും അടങ്ങുന്ന ഡാറ്റാ സെറ്റുകൾ മണിക്കൂറുകൾക്കുള്ളിൽ പ്രോസസ്സ് ചെയ്യാനാകും. മൾട്ടി-കോർ പ്രോസസറുകളിൽ പ്രവർത്തിക്കുന്ന ആധുനിക അൽഗോരിതങ്ങൾ, ഏകദേശം ഒരേ സമയം നൂറുകണക്കിന് ആട്രിബ്യൂട്ടുകളും (200 വരെ) ലക്ഷക്കണക്കിന് വരികളും അടങ്ങുന്ന ഡാറ്റാ സെറ്റുകളുടെ ഡിപൻഡൻസികൾ കണ്ടെത്തുന്നു. എന്നിരുന്നാലും, ഇത് പര്യാപ്തമല്ല: മിക്ക യഥാർത്ഥ ലോക ആപ്ലിക്കേഷനുകൾക്കും അത്തരമൊരു സമയം അസ്വീകാര്യമാണ്. അതിനാൽ, നിലവിലുള്ള അൽഗോരിതങ്ങൾ വേഗത്തിലാക്കാൻ ഞങ്ങൾ സമീപനങ്ങൾ വികസിപ്പിച്ചെടുത്തു.

പാർട്ടീഷൻ കവലകൾക്കായുള്ള കാഷിംഗ് സ്കീമുകൾ

ജോലിയുടെ ആദ്യ ഭാഗത്ത്, പാർട്ടീഷൻ ഇന്റർസെക്ഷൻ രീതി ഉപയോഗിക്കുന്ന ഒരു ക്ലാസ് അൽഗോരിതങ്ങൾക്കായി ഞങ്ങൾ കാഷിംഗ് സ്കീമുകൾ വികസിപ്പിച്ചെടുത്തു. ഒരു ആട്രിബ്യൂട്ടിനുള്ള പാർട്ടീഷൻ എന്നത് ഒരു കൂട്ടം ലിസ്റ്റുകളാണ്, അവിടെ ഓരോ ലിസ്റ്റിലും തന്നിരിക്കുന്ന ആട്രിബ്യൂട്ടിനുള്ള അതേ മൂല്യങ്ങളുള്ള ലൈൻ നമ്പറുകൾ അടങ്ങിയിരിക്കുന്നു. അത്തരം ഓരോ ലിസ്റ്റിനെയും ഒരു ക്ലസ്റ്റർ എന്ന് വിളിക്കുന്നു. പല ആധുനിക അൽഗോരിതങ്ങളും ഒരു ഡിപൻഡൻസി കൈവശം വച്ചിട്ടുണ്ടോ ഇല്ലയോ എന്ന് നിർണ്ണയിക്കാൻ പാർട്ടീഷനുകൾ ഉപയോഗിക്കുന്നു, അതായത്, അവ ലെമ്മ: ആശ്രിതത്വം പാലിക്കുന്നു. എങ്കിൽ നടത്തി . ഇവിടെ ഒരു പാർട്ടീഷൻ നിയുക്തമാക്കുകയും പാർട്ടീഷൻ വലുപ്പം എന്ന ആശയം ഉപയോഗിക്കുകയും ചെയ്യുന്നു - അതിലെ ക്ലസ്റ്ററുകളുടെ എണ്ണം. പാർട്ടീഷനുകൾ ഉപയോഗിക്കുന്ന അൽഗോരിതങ്ങൾ, ഡിപൻഡൻസി ലംഘിക്കപ്പെടുമ്പോൾ, ഡിപൻഡൻസിയുടെ ഇടതുവശത്ത് അധിക ആട്രിബ്യൂട്ടുകൾ ചേർക്കുക, തുടർന്ന് അത് വീണ്ടും കണക്കാക്കുകയും പാർട്ടീഷനുകളുടെ കവലയുടെ പ്രവർത്തനം നടത്തുകയും ചെയ്യുന്നു. ഈ പ്രവർത്തനത്തെ ലേഖനങ്ങളിൽ സ്പെഷ്യലൈസേഷൻ എന്ന് വിളിക്കുന്നു. എന്നാൽ കുറച്ച് റൗണ്ട് സ്പെഷ്യലൈസേഷനുശേഷം മാത്രം നിലനിർത്തുന്ന ഡിപൻഡൻസികൾക്കുള്ള പാർട്ടീഷനുകൾ സജീവമായി പുനരുപയോഗിക്കാൻ കഴിയുമെന്ന് ഞങ്ങൾ ശ്രദ്ധിച്ചു, ഇത് അൽഗോരിതങ്ങളുടെ പ്രവർത്തന സമയം ഗണ്യമായി കുറയ്ക്കും, കാരണം ഇന്റർസെക്ഷൻ പ്രവർത്തനം ചെലവേറിയതാണ്.

അതിനാൽ, ഞങ്ങൾ ഷാനൺ എൻട്രോപ്പി, ജിന്നി അനിശ്ചിതത്വം എന്നിവയെ അടിസ്ഥാനമാക്കിയുള്ള ഒരു ഹ്യൂറിസ്റ്റിക് നിർദ്ദേശിച്ചു, അതുപോലെ തന്നെ ഞങ്ങളുടെ മെട്രിക്, ഞങ്ങൾ റിവേഴ്സ് എൻട്രോപ്പി എന്ന് വിളിക്കുന്നു. ഇത് ഷാനൺ എൻട്രോപ്പിയുടെ ഒരു ചെറിയ പരിഷ്ക്കരണമാണ് കൂടാതെ ഡാറ്റാ സെറ്റിന്റെ പ്രത്യേകത വർദ്ധിക്കുന്നതിനനുസരിച്ച് വർദ്ധിക്കുന്നു. നിർദ്ദിഷ്ട ഹ്യൂറിസ്റ്റിക് ഇപ്രകാരമാണ്:

ഇത് - അടുത്തിടെ കണക്കാക്കിയ പാർട്ടീഷന്റെ പ്രത്യേകതയുടെ അളവ് ഒപ്പം വ്യക്തിഗത ആട്രിബ്യൂട്ടുകളുടെ അദ്വിതീയതയുടെ ഡിഗ്രികളുടെ ശരാശരിയാണ്. മുകളിൽ വിവരിച്ച മൂന്ന് മെട്രിക്കുകളും ഒരു അദ്വിതീയ മെട്രിക് ആയി പരീക്ഷിച്ചു. ഹ്യൂറിസ്റ്റിക്സിൽ രണ്ട് മോഡിഫയറുകൾ ഉണ്ടെന്നും നിങ്ങൾക്ക് ശ്രദ്ധിക്കാം. നിലവിലെ പാർട്ടീഷൻ പ്രൈമറി കീയുമായി എത്ര അടുത്താണെന്ന് ആദ്യത്തേത് സൂചിപ്പിക്കുന്നു കൂടാതെ പൊട്ടൻഷ്യൽ കീയിൽ നിന്ന് വളരെ അകലെയുള്ള പാർട്ടീഷനുകൾ ഒരു പരിധി വരെ കാഷെ ചെയ്യാൻ നിങ്ങളെ അനുവദിക്കുന്നു. രണ്ടാമത്തെ മോഡിഫയർ കാഷെ ഒക്യുപൻസി നിരീക്ഷിക്കാൻ നിങ്ങളെ അനുവദിക്കുകയും അതുവഴി ശൂന്യമായ ഇടം ലഭ്യമാണെങ്കിൽ കാഷെയിലേക്ക് കൂടുതൽ പാർട്ടീഷനുകൾ ചേർക്കുന്നത് പ്രോത്സാഹിപ്പിക്കുകയും ചെയ്യുന്നു. ഈ പ്രശ്നത്തിന്റെ വിജയകരമായ പരിഹാരം ഡാറ്റാസെറ്റിനെ ആശ്രയിച്ച് PYRO അൽഗോരിതം 10-40% വേഗത്തിലാക്കാൻ ഞങ്ങളെ അനുവദിച്ചു. PYRO അൽഗോരിതം ഈ മേഖലയിൽ ഏറ്റവും വിജയകരമാണെന്നത് ശ്രദ്ധിക്കേണ്ടതാണ്.

അടിസ്ഥാന കോയിൻ-ഫ്ലിപ്പ് കാഷിംഗ് സമീപനവുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ നിർദ്ദിഷ്ട ഹ്യൂറിസ്റ്റിക് പ്രയോഗിക്കുന്നതിന്റെ ഫലങ്ങൾ ചുവടെയുള്ള ചിത്രത്തിൽ നിങ്ങൾക്ക് കാണാൻ കഴിയും. X അക്ഷം ലോഗരിഥമിക് ആണ്.

പാർട്ടീഷനുകൾ സംഭരിക്കുന്നതിനുള്ള ഒരു ബദൽ മാർഗം

പാർട്ടീഷനുകൾ സംഭരിക്കുന്നതിനുള്ള ഒരു ബദൽ മാർഗ്ഗം ഞങ്ങൾ നിർദ്ദേശിച്ചു. പാർട്ടീഷനുകൾ എന്നത് ഒരു കൂട്ടം ക്ലസ്റ്ററുകളാണ്, അവ ഓരോന്നും ചില ആട്രിബ്യൂട്ടുകൾക്കായി ഒരേ മൂല്യങ്ങളുള്ള ട്യൂപ്പിളുകളുടെ എണ്ണം സംഭരിക്കുന്നു. ഈ ക്ലസ്റ്ററുകളിൽ ട്യൂപ്പിൾ നമ്പറുകളുടെ ദൈർഘ്യമേറിയ ശ്രേണികൾ അടങ്ങിയിരിക്കാം, ഉദാഹരണത്തിന് ഒരു പട്ടികയിലെ ഡാറ്റ ക്രമപ്പെടുത്തിയിട്ടുണ്ടെങ്കിൽ. അതിനാൽ, പാർട്ടീഷനുകൾ സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു കംപ്രഷൻ സ്കീം നിർദ്ദേശിച്ചു, അതായത് പാർട്ടീഷനുകളുടെ ക്ലസ്റ്ററുകളിലെ മൂല്യങ്ങളുടെ ഇടവേള സംഭരണം:

$$display$$pi(X) = {{അണ്ടർബ്രേസ്{1, 2, 3, 4, 5}_{ആദ്യ ഇടവേള}, അണ്ടർബ്രേസ്{7, 8}_{രണ്ടാം ഇടവേള}, 10}}\ താഴേക്ക്{ കംപ്രഷൻ} \ pi(X) = {{അണ്ടർബ്രേസ്{$, 1, 5}_{ആദ്യ~ഇന്റർവെൽ}, അണ്ടർബ്രേസ്{7, 8}_{സെക്കൻഡ്~ഇന്റർവൽ}, 10}}$$ഡിസ്‌പ്ലേ$$

TANE അൽഗോരിതത്തിന്റെ പ്രവർത്തന സമയത്ത് മെമ്മറി ഉപഭോഗം 1 മുതൽ 25% വരെ കുറയ്ക്കാൻ ഈ രീതിക്ക് കഴിഞ്ഞു. ഫെഡറൽ നിയമങ്ങൾക്കായി തിരയുന്നതിനുള്ള ഒരു ക്ലാസിക് അൽഗോരിതം ആണ് TANE അൽഗോരിതം; ഇത് അതിന്റെ പ്രവർത്തന സമയത്ത് പാർട്ടീഷനുകൾ ഉപയോഗിക്കുന്നു. പരിശീലനത്തിന്റെ ഭാഗമായി, TANE അൽഗോരിതം തിരഞ്ഞെടുത്തു, കാരണം അതിൽ ഇടവേള സംഭരണം നടപ്പിലാക്കുന്നത് വളരെ എളുപ്പമാണ്, ഉദാഹരണത്തിന്, PYRO-യിൽ നിർദ്ദിഷ്ട സമീപനം പ്രവർത്തിക്കുന്നുണ്ടോ എന്ന് വിലയിരുത്തുന്നതിന്. ലഭിച്ച ഫലങ്ങൾ ചുവടെയുള്ള ചിത്രത്തിൽ അവതരിപ്പിച്ചിരിക്കുന്നു. X അക്ഷം ലോഗരിഥമിക് ആണ്.

കോൺഫറൻസ് ADBIS-2019

ഗവേഷണ ഫലങ്ങളെ അടിസ്ഥാനമാക്കി, 2019 സെപ്റ്റംബറിൽ ഞാൻ ഒരു ലേഖനം പ്രസിദ്ധീകരിച്ചു കാര്യക്ഷമമായ പ്രവർത്തനപരമായ ആശ്രിതത്വം കണ്ടെത്തുന്നതിനുള്ള സ്മാർട്ട് കാഷിംഗ് ഡാറ്റാബേസുകളിലെയും ഇൻഫർമേഷൻ സിസ്റ്റങ്ങളിലെയും പുരോഗതിയെക്കുറിച്ചുള്ള 23-ാമത് യൂറോപ്യൻ കോൺഫറൻസിൽ (ADBIS-2019). അവതരണ വേളയിൽ, ഡാറ്റാബേസ് മേഖലയിലെ ഒരു പ്രധാന വ്യക്തിയായ ബെർണാർഡ് താൽഹൈം ഈ കൃതി ശ്രദ്ധിച്ചു. സെന്റ് പീറ്റേഴ്‌സ്ബർഗ് സ്റ്റേറ്റ് യൂണിവേഴ്‌സിറ്റിയിലെ ഗണിതശാസ്ത്രത്തിലും മെക്കാനിക്‌സിലുമുള്ള ബിരുദാനന്തര ബിരുദത്തിലെ എന്റെ പ്രബന്ധത്തിന്റെ അടിസ്ഥാനം ഗവേഷണ ഫലങ്ങൾ രൂപീകരിച്ചു, ഈ സമയത്ത് രണ്ട് നിർദ്ദിഷ്ട സമീപനങ്ങളും (കാഷിംഗും കംപ്രഷനും) രണ്ട് അൽഗോരിതങ്ങളിലും നടപ്പിലാക്കി: TANE, PYRO. കൂടാതെ, നിർദ്ദിഷ്ട സമീപനങ്ങൾ സാർവത്രികമാണെന്ന് ഫലങ്ങൾ കാണിക്കുന്നു, കാരണം രണ്ട് അൽഗോരിതങ്ങളിലും, രണ്ട് സമീപനങ്ങളിലും, മെമ്മറി ഉപഭോഗത്തിൽ ഗണ്യമായ കുറവും അതുപോലെ തന്നെ അൽഗോരിതങ്ങളുടെ പ്രവർത്തന സമയത്തിൽ ഗണ്യമായ കുറവും നിരീക്ഷിക്കപ്പെട്ടു.

അവലംബം: www.habr.com