డేటాబేస్‌లలో ఫంక్షనల్ డిపెండెన్సీలను సమర్థవంతంగా కనుగొనండి

డేటాలో ఫంక్షనల్ డిపెండెన్సీలను కనుగొనడం అనేది డేటా విశ్లేషణ యొక్క వివిధ రంగాలలో ఉపయోగించబడుతుంది: డేటాబేస్ మేనేజ్‌మెంట్, డేటా క్లీనింగ్, డేటాబేస్ రివర్స్ ఇంజనీరింగ్ మరియు డేటా ఎక్స్‌ప్లోరేషన్. మేము ఇప్పటికే డిపెండెన్సీల గురించి ప్రచురించాము వ్యాసం అనస్తాసియా బిరిల్లో మరియు నికితా బోబ్రోవ్. ఈసారి, ఈ సంవత్సరం కంప్యూటర్ సైన్స్ సెంటర్‌లో గ్రాడ్యుయేట్ అయిన అనస్తాసియా, ఆమె కేంద్రంలో సమర్థించిన పరిశోధన పనిలో భాగంగా ఈ పని యొక్క అభివృద్ధిని పంచుకుంది.

విధి ఎంపిక

CS సెంటర్‌లో చదువుతున్నప్పుడు, నేను డేటాబేస్‌లను లోతుగా అధ్యయనం చేయడం ప్రారంభించాను, అవి ఫంక్షనల్ మరియు డిఫరెన్సీల కోసం శోధన. ఈ అంశం విశ్వవిద్యాలయంలో నా కోర్స్‌వర్క్ యొక్క అంశానికి సంబంధించినది, కాబట్టి కోర్సులో పని చేస్తున్నప్పుడు, నేను డేటాబేస్‌లలోని వివిధ డిపెండెన్సీల గురించి కథనాలను చదవడం ప్రారంభించాను. నేను ఈ ప్రాంతం యొక్క సమీక్షను వ్రాసాను - నా మొదటి వాటిలో ఒకటి వ్యాసాలు ఆంగ్లంలో మరియు SEIM-2017 సమావేశానికి సమర్పించారు. ఆమె అంగీకరించబడిందని తెలుసుకున్నప్పుడు నేను చాలా సంతోషించాను మరియు అంశంపై లోతుగా పరిశోధించాలని నిర్ణయించుకున్నాను. భావన కొత్తది కాదు - ఇది 90 లలో తిరిగి ఉపయోగించడం ప్రారంభమైంది, కానీ ఇప్పుడు కూడా ఇది చాలా ప్రాంతాలలో ఉపయోగించబడుతుంది.

సెంటర్‌లో నా రెండవ సెమిస్టర్‌లో, ఫంక్షనల్ డిపెండెన్సీలను కనుగొనడానికి అల్గారిథమ్‌లను మెరుగుపరచడానికి నేను పరిశోధన ప్రాజెక్ట్‌ను ప్రారంభించాను. ఆమె జెట్‌బ్రెయిన్స్ రీసెర్చ్‌లో సెయింట్ పీటర్స్‌బర్గ్ స్టేట్ యూనివర్శిటీ గ్రాడ్యుయేట్ విద్యార్థి నికితా బోబ్రోవ్‌తో కలిసి పని చేసింది.

ఫంక్షనల్ డిపెండెన్సీల కోసం శోధించడం యొక్క గణన సంక్లిష్టత

ప్రధాన సమస్య గణన సంక్లిష్టత. సాధ్యమయ్యే కనిష్ట మరియు నాన్-ట్రివియల్ డిపెండెన్సీల సంఖ్య పైన విలువ ద్వారా పరిమితం చేయబడింది పేరు - పట్టిక లక్షణాల సంఖ్య. అల్గోరిథంల యొక్క ఆపరేటింగ్ సమయం లక్షణాల సంఖ్యపై మాత్రమే కాకుండా, వరుసల సంఖ్యపై కూడా ఆధారపడి ఉంటుంది. 90వ దశకంలో, సాధారణ డెస్క్‌టాప్ PCలోని ఫెడరల్ లా సెర్చ్ అల్గారిథమ్‌లు గరిష్టంగా 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