{"id":86335,"date":"2020-06-24T07:42:54","date_gmt":"2020-06-24T05:42:54","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh"},"modified":"2020-06-24T07:42:54","modified_gmt":"2020-06-24T05:42:54","slug":"effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","status":"publish","type":"post","link":"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"Efektiivne funktsionaalsete s\u00f5ltuvuste otsimine andmebaasides","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Funktsionaalsete seoste otsimine andmetes rakendatakse erinevates andmeanal\u00fc\u00fcsi valdkondades: andmebaaside haldamine, andmete puhastamine, andmebaaside p\u00f6\u00f6rdestseerimine ja andmete uurimine. Me oleme juba avaldanud teavet nende seoste kohta. artiklit<\/a><\/noindex> Anastasia Biirsja ja Nikita Bobrov. Seekord jagab Anastasia \u2014 k\u00e4esoleva aasta arvutiteaduse keskuse l\u00f5petaja \u2014 selle t\u00f6\u00f6 arendamisest uurimisprojekti raames, mille ta kaitses keskuses. <\/p>\n

\"Efektiivne
\n<\/a><\/noindex><\/p>\n

\u00dclesande valik <\/h3>\n

\nArvutiteaduse keskuses \u00f5ppimise ajal hakkasin s\u00fcvitsi uurima andmebaase, nimelt funktsionaalsete ja erinevate seoste otsimist. See teema oli seotud minu \u00fclikooli kursuset\u00f6\u00f6ga, seega hakkasin kursuset\u00f6\u00f6 kirjutamise ajal lugema artikleid erinevate andmebaaside seoste kohta. Kirjutasin sellest valdkonnast \u00fclevaate \u2014 oma esimesi kirjutisi. artikleid<\/a><\/noindex> Inglise keeles ja saatsin selle SEIM-2017 konverentsile. Olin v\u00e4ga r\u00f5\u00f5mus, kui sain teada, et see v\u00f5eti siiski vastu, ja otsustasin teemaga s\u00fcvitsi minna. Kontseptsioon ise ei ole uus \u2014 seda on hakatud rakendama juba 90-ndatel, kuid ka praegu leidub sellel rakendust paljudes valdkondades. <\/p>\n

Teise semestri jooksul keskuses alustasin teadusprojekti funktsionaalsete seoste otsimise algoritmide t\u00e4iustamiseks. Tegin selle kallal koost\u00f6\u00f6d Peterburi Riikliku \u00dclikooli doktorandi Nikita Bobroviga JetBrains Researchi baasil. <\/p>\n

Funktsionaalsete seoste leidmise arvutust\u00f6\u00f6 keerukus<\/h3>\n

\nPeamine probleem on arvutust\u00f6\u00f6 keerukus. V\u00f5imalike minimaalsete ja ebatavaliste seoste arv on piiratud \u00fclevalt niisuguse v\u00e4\u00e4rtusega. \"Efektiivne, kus \"Efektiivne \u2014 tabeli atribuutide arv. Algoritmide t\u00f6\u00f6aeg s\u00f5ltub mitte ainult atribuutide arvust, vaid ka ridade arvust. 90-ndatel aastatel suudsid tavap\u00e4rased personaalarvutid funktsionaalsete seoste otsimise algoritmid t\u00f6\u00f6delda andmesarju, mis sisaldasid kuni 20 atribuuti ja k\u00fcmneid tuhandeid ridasid, mitme tunni jooksul. Kaasaegsed algoritmid, mis t\u00f6\u00f6tavad mitme tuumaga protsessoritel, tuvastavad seosed andmesarjades, mis koosnevad sadadest atribuutidest (kuni 200) ja sadadest tuhandetest ridadest, ligikaudu sama ajaga. Siiski on see ebapiisav: selline aeg on enamikus reaalsetes rakendustes vastuv\u00f5etamatu. Seet\u00f5ttu t\u00f6\u00f6tasime v\u00e4lja l\u00e4henemisviise olemasolevate algoritmide kiirendamiseks. <\/p>\n

Partitsioonide ristumiseks m\u00f5eldud vahem\u00e4lustruktuurid<\/h3>\n

\nEsimese t\u00f6\u00f6 osas t\u00f6\u00f6tasime v\u00e4lja vahem\u00e4lus hoidmise skeemid algoritmide klassile, mis kasutavad partisioonide ristmeetodit. Partisioon atribuudile esindab kogumit loetelu, kus iga loetelu sisaldab ridade numbreid, mis omavad sarnaseid v\u00e4\u00e4rtusi antud atribuudile. Iga sellist loetelu nimetatakse klastriks. Paljud kaasaegsed algoritmid kasutavad partisioone, et m\u00e4\u00e4ratleda, kas s\u00f5ltuvus on olemas v\u00f5i mitte, j\u00e4rgides just seda lemmat: S\u00f5ltuvus \"Efektiivne on olemas, kui \"Efektiivne. Siin \"Efektiivne t\u00e4histatakse partisioon ja kasutatakse m\u00f5iste partisiooni suurus - klastrite arvu m\u00e4\u00e4ratlemiseks. Partitsioone kasutavad algoritmid, kui s\u00f5ltuvus puruneb, lisavad vasakule poole s\u00f5ltuvuse t\u00e4iendavad atribuudid, mille j\u00e4rel nad arvutavad selle \u00fcle, tehes partisioonide ristamise operatsiooni. Sellist operatsiooni nimetatakse spetsialiseerimiseks. Kuid oleme m\u00e4rganud, et partisioonid s\u00f5ltuvuste jaoks, mis j\u00e4\u00e4vad alles alles p\u00e4rast mitmeid spetsialiseerimise ringe, v\u00f5ivad olla aktiivselt taaskasutatud, mis v\u00f5ib m\u00e4rkimisv\u00e4\u00e4rselt v\u00e4hendada algoritmide t\u00f6\u00f6aega, kuna ristamisoperatsioon on kulukas. <\/p>\n

Seet\u00f5ttu pakkusime v\u00e4lja heuristiku, mis p\u00f5hineb Shannon'i entropial ja Ginny ebakindlusel, samuti meie meetril, mille me nimetasime Tagasi Entroopiaks. See on v\u00e4ike muudatus Shannon'i entropiast ja kasvab koos andmekogu ainulaadsuse suurenemisega. Pakutud heuristika n\u00e4eb v\u00e4lja j\u00e4rgmine:<\/p>\n

\"Efektiivne<\/p>\n

Siin \"Efektiivne \u2014 hiljuti arvutatud partisiooni ainulaadsuse aste \"Efektiivne, vaid \"Efektiivne on unikalsuse m\u00e4\u00e4ra median, mis kehtib \u00fcksikutele omadustele. Unikalsuse m\u00f5\u00f5dikutena on proovitud k\u00f5iki kolme \u00fclaltoodud m\u00f5\u00f5dikut. Samuti on m\u00e4rgata, et heuristikasse kuuluvad kaks modifikaatorit. Esimene n\u00e4itab, kui l\u00e4hedal on praegune partitsioon algsele v\u00f5tmele, ja v\u00f5imaldab rohkem neid partitsioone vahem\u00e4lus hoida, mis on kaugel potentsiaalsest v\u00f5tmest. Teine modifikaator v\u00f5imaldab j\u00e4lgida vahem\u00e4lu kasutamist, edendades seel\u00e4bi suuremate partitsioonide lisamist vahem\u00e4llu, kui ruumi on vaba. Selle \u00fclesande edukas lahendamine v\u00f5imaldas kiirendada algoritmi PYRO 10-40% s\u00f5ltuvalt andmestikust. Tuleb m\u00e4rkida, et algoritm PYRO on selles valdkonnas k\u00f5ige edukam. <\/p>\n

Alloleval pildil on n\u00e4ha ettepanekut heuristika rakendamise tulemused v\u00f5rreldes p\u00f5hiettekandega, mis p\u00f5hineb m\u00fcndi viskamisel. X telg on logaritmiline.<\/p>\n

\"Efektiivne
\n<\/p>\n

Alternatiivne viis partitsioonide salvestamiseks<\/h3>\n

\nK seej\u00e4rel pakkusime v\u00e4lja alternatiivse viisi partitsioonide salvestamiseks. Partitsioonid esindavad klastrite komplekti, milles iga\u00fches on salvestatud tuplike numbrid, millel on sama v\u00e4\u00e4rtus teatud omadustes. Need klastrid v\u00f5ivad sisaldada pikki j\u00e4rjestusi tuplite numbri, n\u00e4iteks kui tabelis on andmed j\u00e4rjestatud. Seet\u00f5ttu pakkusime partitsioonide salvestamiseks tihendamisstrateegiat, nimelt v\u00e4\u00e4rtuste intervallide hoidmine partitsioonide klastri sees:<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Esimene~intervall}, underbrace{7, 8}_{Teine~intervall}, 10}}\\ downarrow{Tihendamine}\\ pi(X) = {{underbrace{$, 1, 5}_{Esimene~intervall}, underbrace{7, 8}_{Teine~intervall}, 10}}$$display$$<\/p>\n

See meetod suutis v\u00e4hendada algoritmi TANE ajaloo k\u00e4igus m\u00e4lutarbimist 1 kuni 25%. Algoritm TANE on klassikaline algoritm funktsionaalsete s\u00f5ltuvuste otsimiseks, mis kasutab oma t\u00f6\u00f6s partitsioone. Praktika raames valiti just algoritm TANE, kuna intervallide salvestamise rakendamine oli sellel palju lihtsam kui n\u00e4iteks PYRO, et hinnata, kas pakutud l\u00e4henemine t\u00f6\u00f6tab. Saadud tulemused on esitatud alloleval pildil. X telg on logaritmiline.<\/p>\n

\"Efektiivne
\n<\/p>\n

Konverents ADBIS-2019<\/h3>\n

\n2019. aasta septembris esitasin oma uuringu tulemuste p\u00f5hjal artikli Nutikas vahem\u00e4lu efektiivseks funktsionaalsete s\u00f5ltuvuste avastamiseks<\/a><\/noindex> 23. Euroopa andmebaaside ja teabe s\u00fcsteemide konverentsil (ADBIS-2019) m\u00e4rkis Bernhard Thalheim, kes on andmebaaside valdkonnas silmapaistev isik, et minu uurimist\u00f6\u00f6 tulemused moodustasid aluse minu magistrit\u00f6\u00f6le matemaatika ja mehhaanika erialal SPbGU-s. Sellest tulenevalt viidi m\u00f5lemad pakutud l\u00e4henemisviisid (vahem\u00e4lu ja kompressioon) ellu m\u00f5lemas algoritmis: TANE ja PYRO. Uuringute tulemused n\u00e4itasid, et pakutud l\u00e4henemisviisid on universaalsed, kuna m\u00f5lema algoritmi puhul m\u00f5lema l\u00e4henemise korral t\u00e4heldati m\u00e4rgatavat m\u00e4lu tarbimise v\u00e4henemist ja oluliselt l\u00fchenenud algoritmide t\u00f6\u00f6aega.
\n
Allikas: habr.com<\/a> <\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\u041f\u043e\u0438\u0441\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0432 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u043d\u044b\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u0445 \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0434\u0430\u043d\u043d\u044b\u0445: \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u0430\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u0445, \u043e\u0447\u0438\u0441\u0442\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0440\u0435\u0432\u0451\u0440\u0441-\u0438\u043d\u0436\u0438\u043d\u0438\u0440\u0438\u043d\u0433 \u0431\u0430\u0437 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u044d\u043a\u0441\u043f\u043b\u043e\u0440\u0430\u0446\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u041f\u0440\u043e \u0441\u0430\u043c\u0438 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043c\u044b \u0443\u0436\u0435 \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u044e \u0410\u043d\u0430\u0441\u0442\u0430\u0441\u0438\u0438 \u0411\u0438\u0440\u0438\u043b\u043b\u043e \u0438 \u041d\u0438\u043a\u0438\u0442\u044b \u0411\u043e\u0431\u0440\u043e\u0432\u0430. \u0412 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u0410\u043d\u0430\u0441\u0442\u0430\u0441\u0438\u044f \u2014 \u0432\u044b\u043f\u0443\u0441\u043a\u043d\u0438\u0446\u0430 Computer Science Center \u044d\u0442\u043e\u0433\u043e \u0433\u043e\u0434\u0430 \u2014 \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u0440\u0430\u0437\u0432\u0438\u0442\u0438\u0435\u043c \u044d\u0442\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u041d\u0418\u0420, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043e\u043d\u0430 […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":86336,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-86335","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47T\u00f5hus funktsionaalsete s\u00f5ltuvuste otsimine andmebaasides | ProHoster","description":"Funktsionaalsete s\u00f5ltuvuste otsimine andmetes rakendub erinevates andmeanal\u00fc\u00fcsi suundades: andmebaaside haldamine, andmete puhastamine, andmebaaside reverse engineering ja andmete uurimine.","canonical_url":"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"et_EE","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0432 \u0431\u0430\u0437\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 | ProHoster","og:description":"\u041f\u043e\u0438\u0441\u043a \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0432 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u043d\u044b\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u0445 \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0434\u0430\u043d\u043d\u044b\u0445: \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u0430\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u0445, \u043e\u0447\u0438\u0441\u0442\u043a\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0440\u0435\u0432\u0451\u0440\u0441-\u0438\u043d\u0436\u0438\u043d\u0438\u0440\u0438\u043d\u0433 \u0431\u0430\u0437 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u044d\u043a\u0441\u043f\u043b\u043e\u0440\u0430\u0446\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445.","og:url":"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2020-06-24T05:42:54+00:00","article:modified_time":"2020-06-24T05:42:54+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"86335","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":null,"breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-02-28 14:17:33","updated":"2022-09-27 17:20:14","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}