{"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\/sv\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"Effektiv s\u00f6kning efter funktionella beroenden i databaser","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

S\u00f6kning av funktionella beroenden i data till\u00e4mpas inom olika omr\u00e5den av dataanalys: databasf\u00f6rvaltning, datarensning, reverse engineering av databaser och datautforskning. Vi har redan publicerat om sj\u00e4lva beroenden. artikeln<\/a><\/noindex> Anastasia Birillo och Nikita Bobrov. Denna g\u00e5ng delar Anastasia - en nyutexaminerad fr\u00e5n Computer Science Center det h\u00e4r \u00e5ret - med sig av utvecklingen av detta arbete inom ramen f\u00f6r sitt forskningsprojekt, som hon f\u00f6rsvarade vid centret. <\/p>\n

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

Val av uppgift <\/h3>\n

\nUnder min utbildning i CS-centret b\u00f6rjade jag f\u00f6rdjupa mig i databaser, specifikt s\u00f6kning av funktionella och differentierade beroenden. Det h\u00e4r \u00e4mnet var relaterat till min uppsats i universitetet, s\u00e5 under arbetet med uppsatsen b\u00f6rjade jag l\u00e4sa artiklar om olika beroenden i databaser. Jag skrev en \u00f6versikt \u00f6ver detta omr\u00e5de - en av mina f\u00f6rsta. artiklar<\/a><\/noindex> p\u00e5 engelska och skickade den till konferensen SEIM-2017. Jag blev mycket glad n\u00e4r jag fick veta att den hade accepterats, och jag beslutade mig f\u00f6r att f\u00f6rdjupa mig i \u00e4mnet. Sj\u00e4lva konceptet \u00e4r inte nytt - det b\u00f6rjade anv\u00e4ndas redan p\u00e5 90-talet, men det till\u00e4mpas fortfarande inom m\u00e5nga omr\u00e5den. <\/p>\n

Under andra terminen av utbildningen i centret b\u00f6rjade jag ett forskningsprojekt f\u00f6r att f\u00f6rb\u00e4ttra algoritmer f\u00f6r s\u00f6kning av funktionella beroenden. Jag arbetade med detta tillsammans med doktoranden Nikita Bobrov fr\u00e5n SPbGU p\u00e5 basis av JetBrains Research. <\/p>\n

Ber\u00e4kningskomplexiteten f\u00f6r s\u00f6kningen av funktionella beroenden<\/h3>\n

\nDet huvudsakliga problemet \u00e4r ber\u00e4kningskomplexiteten. Antalet m\u00f6jliga minimala och icke-triviala beroenden \u00e4r begr\u00e4nsat av v\u00e4rdet \"Effektiv, d\u00e4r \"Effektiv \u2014 antalet attribut i tabellen. Algoritmernas k\u00f6rtid beror inte bara p\u00e5 antalet attribut utan ocks\u00e5 p\u00e5 antalet rader. Under 90-talet kunde algoritmer f\u00f6r s\u00f6kning av funktionella beroenden p\u00e5 vanliga station\u00e4ra datorer bearbeta datam\u00e4ngder som inneh\u00f6ll upp till 20 attribut och tiotusentals rader p\u00e5 upp till flera timmar. Moderna algoritmer, som k\u00f6rs p\u00e5 flerk\u00e4rniga processorer, uppt\u00e4cker beroenden f\u00f6r datam\u00e4ngder best\u00e5ende av hundratals attribut (upp till 200) och hundratusentals rader p\u00e5 ungef\u00e4r samma tid. \u00c4nd\u00e5 \u00e4r detta otillr\u00e4ckligt: s\u00e5dan tid \u00e4r oacceptabel f\u00f6r de flesta verkliga applikationer. D\u00e4rf\u00f6r har vi utvecklat metoder f\u00f6r att snabba upp befintliga algoritmer. <\/p>\n

Cache-scheman f\u00f6r partitioneringsintersektion<\/h3>\n

\nI den f\u00f6rsta delen av arbetet utvecklade vi cache-scheman f\u00f6r en klass av algoritmer som anv\u00e4nder metoden f\u00f6r partiell \u00f6verlappning. En partition f\u00f6r en attribut representerar en upps\u00e4ttning listor, d\u00e4r varje lista inneh\u00e5ller radnummer med samma v\u00e4rden f\u00f6r det aktuella attributet. Varje s\u00e5dan lista kallas ett kluster. M\u00e5nga moderna algoritmer anv\u00e4nder partitioner f\u00f6r att best\u00e4mma om en beroende h\u00e5lls eller inte, och f\u00f6ljer den lemma: Beroende \"Effektiv h\u00e5lls om \"Effektiv. H\u00e4r \"Effektiv betecknas partitionen och begreppet partitionsstorlek anv\u00e4nds \u2014 antalet kluster i den. Algoritmer som anv\u00e4nder partitioner l\u00e4gger till ytterligare attribut i v\u00e4nster del av beroendet n\u00e4r beroendet bryts, varefter de r\u00e4knar om det genom att utf\u00f6ra operationen av partiell \u00f6verlappning. Denna operation kallas specialisering i artiklar. Men vi har noterat att partitioner f\u00f6r beroenden som kommer att h\u00e5llas f\u00f6rst efter flera omg\u00e5ngar av specialisering kan \u00e5teranv\u00e4ndas aktivt, vilket kan avsev\u00e4rt minska algoritmernas k\u00f6rtid, eftersom operationen av partiell \u00f6verlappning \u00e4r kostsam. <\/p>\n

D\u00e4rf\u00f6r f\u00f6reslog vi en heuristik baserad p\u00e5 Shannon-entropi och Gini-os\u00e4kerhet, samt v\u00e5r metrik som vi kallade Invers Entropi. Den \u00e4r en obetydlig modifiering av Shannon-entropin och \u00f6kar i takt med att unikheten av datasetet \u00f6kar. Den f\u00f6reslagna heuristiken ser ut som f\u00f6ljer:<\/p>\n

\"Effektiv<\/p>\n

H\u00e4r \"Effektiv \u2014 graden av unikhet hos den nyligen ber\u00e4knade partitionen \"Effektiv, och \"Effektiv \u00e4r medianen av unikhetsgrader f\u00f6r specifika attribut. Som en unikhetsmetrik testades alla tre metoderna som beskrevs ovan. Det kan ocks\u00e5 noteras att det finns tv\u00e5 modifierare i heuristiken. Den f\u00f6rsta indikerar hur n\u00e4ra den aktuella partitionen \u00e4r den prim\u00e4ra nyckeln och m\u00f6jligg\u00f6r mer caching av partitioner som ligger l\u00e5ngt fr\u00e5n den potentiella nyckeln. Den andra modifieraren till\u00e5ter \u00f6vervakning av cachebelastningen och stimulerar d\u00e4rmed till\u00e4gg av fler partitioner i cachen n\u00e4r det finns ledigt utrymme. Att framg\u00e5ngsrikt l\u00f6sa denna uppgift har m\u00f6jliggjort en hastighets\u00f6kning av algoritmen PYRO med 10-40% beroende p\u00e5 datam\u00e4ngden. Det \u00e4r v\u00e4rt att notera att algoritmen PYRO \u00e4r den mest framg\u00e5ngsrika inom detta omr\u00e5de. <\/p>\n

I diagrammet nedan syns resultaten av till\u00e4mpningen av den f\u00f6reslagna heuristiken j\u00e4mf\u00f6rt med den grundl\u00e4ggande cachingmetoden, som baserades p\u00e5 att kasta en mynt. X-axeln \u00e4r logaritmisk.<\/p>\n

\"Effektiv
\n<\/p>\n

Alternativt s\u00e4tt att lagra partitioner<\/h3>\n

\nD\u00e4refter f\u00f6reslog vi ett alternativt s\u00e4tt att lagra partitioner. Partitioner representerar en upps\u00e4ttning kluster, d\u00e4r var och en lagrar nummer p\u00e5 tuples med samma v\u00e4rden f\u00f6r vissa attribut. Dessa kluster kan inneh\u00e5lla l\u00e5nga sekvenser av tuplesnummer, till exempel om data i tabellen \u00e4r ordnade. D\u00e4rf\u00f6r f\u00f6reslog vi ett komprimeringsschema f\u00f6r lagring av partitioner, n\u00e4mligen intervalllagring av v\u00e4rden i partitionernas kluster:<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{F\u00f6rsta~intervallet}, underbrace{7, 8}_{Andra~intervallet}, 10}}\\ downarrow{Komprimering}\\ pi(X) = {{underbrace{$, 1, 5}_{F\u00f6rsta~intervallet}, underbrace{7, 8}_{Andra~intervallet}, 10}}$$display$$<\/p>\n

Denna metod lyckades minska minnesf\u00f6rbrukningen vid k\u00f6rningen av algoritmen TANE med 1 till 25%. Algoritmen TANE \u00e4r en klassisk algoritm f\u00f6r att s\u00f6ka efter funktionella beroenden, och den anv\u00e4nder partitioner under sin verksamhet. I praktiken valdes just algoritmen TANE, eftersom det var mycket enklare att implementera intervalllagring i den \u00e4n i PYRO, f\u00f6r att utv\u00e4rdera om den f\u00f6reslagna metoden fungerar. Resultaten som erh\u00f6lls visas i diagrammet nedan. X-axeln \u00e4r logaritmisk.<\/p>\n

\"Effektiv
\n<\/p>\n

ADBIS-2019-konferensen<\/h3>\n

\nEnligt resultaten av studien i september 2019 presenterade jag en artikel Smart caching f\u00f6r effektiv uppt\u00e4ckte av funktionella beroenden<\/a><\/noindex> Vid konferensen 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019) ber\u00f6mde Bernhard Thalheim, en framst\u00e5ende person inom databaser, arbetet under presentationen. Resultaten fr\u00e5n forskningen l\u00e5g till grund f\u00f6r min magisteruppsats vid matematikmekaniska institutionen vid SPbGU, d\u00e4r b\u00e5da de f\u00f6reslagna metoderna (cache-lagring och komprimering) implementerades i b\u00e5da algoritmerna: TANE och PYRO. Resultaten visade att de f\u00f6reslagna metoderna \u00e4r universella, eftersom b\u00e5da algoritmerna uppvisade en betydande minskning av minnesanv\u00e4ndningen samt en betydande minskning av algoritmernas k\u00f6rtid.
\n
K\u00e4lla: 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\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\udd47Effektiv s\u00f6kning av funktionella beroenden i databaser | ProHoster","description":"S\u00f6kning av funktionella beroenden i data till\u00e4mpas inom olika omr\u00e5den av dataanalys: databashantering, datareng\u00f6ring, reverse engineering av databaser och datautforskning.","canonical_url":"https:\/\/prohoster.info\/sv\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sv_SE","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\/sv\/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\/sv\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sv\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}