ડેટાબેસેસમાં કાર્યાત્મક નિર્ભરતાને અસરકારક રીતે શોધો

ડેટામાં કાર્યાત્મક અવલંબન શોધવાનો ઉપયોગ ડેટા વિશ્લેષણના વિવિધ ક્ષેત્રોમાં થાય છે: ડેટાબેઝ મેનેજમેન્ટ, ડેટા ક્લિનિંગ, ડેટાબેઝ રિવર્સ એન્જિનિયરિંગ અને ડેટા એક્સપ્લોરેશન. અમે પહેલેથી જ નિર્ભરતા વિશે પ્રકાશિત કર્યું છે એક લેખ એનાસ્તાસિયા બિરિલો અને નિકિતા બોબ્રોવ. આ વખતે, આ વર્ષે કોમ્પ્યુટર સાયન્સ સેન્ટરની સ્નાતક અનાસ્તાસિયા, સંશોધન કાર્યના ભાગ રૂપે આ કાર્યના વિકાસને શેર કરે છે જેનો તેણીએ કેન્દ્રમાં બચાવ કર્યો હતો.

કાર્ય પસંદગી

CS કેન્દ્રમાં અભ્યાસ કરતી વખતે, મેં ડેટાબેસેસનો ઊંડાણપૂર્વક અભ્યાસ કરવાનું શરૂ કર્યું, એટલે કે, કાર્યાત્મક અને તફાવત નિર્ભરતાની શોધ. આ વિષય યુનિવર્સિટીમાં મારા અભ્યાસક્રમના વિષય સાથે સંબંધિત હતો, તેથી અભ્યાસક્રમ પર કામ કરતી વખતે, મેં ડેટાબેઝમાં વિવિધ અવલંબન વિશેના લેખો વાંચવાનું શરૂ કર્યું. મેં આ વિસ્તારની સમીક્ષા લખી છે - મારી પ્રથમમાંની એક લેખો અંગ્રેજીમાં અને 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 માં મેં એક લેખ પ્રકાશિત કર્યો કાર્યક્ષમ કાર્યાત્મક નિર્ભરતા શોધ માટે સ્માર્ટ કેશીંગ ડેટાબેસેસ અને ઇન્ફર્મેશન સિસ્ટમ્સમાં એડવાન્સિસ (ADBIS-23) પર 2019મી યુરોપિયન કોન્ફરન્સમાં. પ્રેઝન્ટેશન દરમિયાન, ડેટાબેઝના ક્ષેત્રમાં નોંધપાત્ર વ્યક્તિ, બર્નહાર્ડ થેલહેમ દ્વારા કાર્યની નોંધ લેવામાં આવી હતી. સંશોધન પરિણામોએ સેન્ટ પીટર્સબર્ગ સ્ટેટ યુનિવર્સિટીમાં ગણિત અને મિકેનિક્સમાં માસ્ટર ડિગ્રી પર મારા નિબંધનો આધાર બનાવ્યો, જે દરમિયાન બંને સૂચિત અભિગમો (કેશિંગ અને કમ્પ્રેશન) બંને અલ્ગોરિધમ્સમાં લાગુ કરવામાં આવ્યા: TANE અને PYRO. તદુપરાંત, પરિણામો દર્શાવે છે કે સૂચિત અભિગમો સાર્વત્રિક છે, કારણ કે બંને એલ્ગોરિધમ્સ પર, બંને અભિગમો સાથે, મેમરી વપરાશમાં નોંધપાત્ર ઘટાડો જોવા મળ્યો હતો, તેમજ એલ્ગોરિધમ્સના સંચાલન સમયમાં નોંધપાત્ર ઘટાડો જોવા મળ્યો હતો.

સોર્સ: www.habr.com