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

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

કાર્ય પસંદગી

સીએસ સેન્ટરમાં અભ્યાસ કરતી વખતે, મેં ડેટાબેઝનો ઊંડાણપૂર્વક અભ્યાસ કરવાનું શરૂ કર્યું, ખાસ કરીને, કાર્યાત્મક અને વિભેદક નિર્ભરતા શોધવાનું. આ વિષય મારા યુનિવર્સિટીના અભ્યાસક્રમ સાથે સંબંધિત હતો, તેથી તેના પર કામ કરતી વખતે, મેં ડેટાબેઝમાં વિવિધ નિર્ભરતાઓ વિશેના લેખો વાંચવાનું શરૂ કર્યું. મેં આ ક્ષેત્રની સમીક્ષા લખી - મારા પ્રથમમાંથી એક લેખો અંગ્રેજીમાં અને 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