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

S\u00f8gning efter funktionelle afh\u00e6ngigheder i data anvendes i forskellige retninger inden for dataanalyse: databaseh\u00e5ndtering, datarensning, reverse engineering af databaser og dataeksploration. Vi har allerede offentliggjort om selve afh\u00e6ngighederne. artiklen<\/a><\/noindex> Anastasia Birillo og Nikita Bobrov. Denne gang deler Anastasia \u2014 nyuddannet fra Computer Science Center i \u00e5r \u2014 udviklingen af dette arbejde som en del af forskningsprojektet, hun pr\u00e6senterede i centret. <\/p>\n

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

Valg af opgave <\/h3>\n

\nUnder min uddannelse i CS centret begyndte jeg at studere databaser grundigt, is\u00e6r s\u00f8gning efter funktionelle og differentielle afh\u00e6ngigheder. Dette emne var relateret til emnet for mit bachelorprojekt p\u00e5 universitetet, s\u00e5 mens jeg arbejdede med mit projekt begyndte jeg at l\u00e6se artikler om forskellige afh\u00e6ngigheder i databaser. Jeg skrev en oversigt over dette omr\u00e5de \u2014 en af mine f\u00f8rste. artikler<\/a><\/noindex> p\u00e5 engelsk, og jeg indsendte den til konferencen SEIM-2017. Jeg var meget glad, da jeg fandt ud af, at den faktisk blev accepteret, og jeg besluttede at dykke dybere ned i emnet. Selve konceptet er ikke nyt \u2014 det begyndte at blive anvendt allerede i 90'erne, men det finder stadig anvendelse i mange omr\u00e5der. <\/p>\n

I andet semester af min uddannelse i centret begyndte jeg et forskningsprojekt for at forbedre algoritmerne til at finde funktionelle afh\u00e6ngigheder. Jeg arbejdede p\u00e5 det sammen med ph.d.-studerende fra St. Petersborg Universitet, Nikita Bobrov, p\u00e5 JetBrains Research. <\/p>\n

Den beregningsm\u00e6ssige kompleksitet ved at finde funktionelle afh\u00e6ngigheder<\/h3>\n

\nDet prim\u00e6re problem \u2014 den beregningsm\u00e6ssige kompleksitet. Antallet af mulige minimale og ikke-trivielle afh\u00e6ngigheder er begr\u00e6nset af v\u00e6rdien \"Effektiv, hvor \"Effektiv \u2014 antallet af attributter i tabellen. Tiden for algoritmernes k\u00f8rsel afh\u00e6nger ikke kun af antallet af attributter, men ogs\u00e5 af antallet af r\u00e6kker. I 90'erne kunne algoritmer til at finde funktionelle afh\u00e6ngigheder p\u00e5 en almindelig station\u00e6r computer behandle datas\u00e6t med op til 20 attributter og titusinder af r\u00e6kker i op til flere timer. Moderne algoritmer, der k\u00f8rer p\u00e5 multi-core processorer, opdager afh\u00e6ngigheder for datas\u00e6t, der best\u00e5r af hundrede attributter (op til 200) og hundredtusinder af r\u00e6kker, omtrent p\u00e5 samme tid. Alligevel er dette ikke tilstr\u00e6kkeligt: s\u00e5dan tid er uacceptabel for de fleste virkelige applikationer. Derfor udviklede vi metoder til at accelerere eksisterende algoritmer. <\/p>\n

Cache-skemaer til partitioneringens krydsninger<\/h3>\n

\nI den f\u00f8rste del af arbejdet udviklede vi cache-skemaer for en klasse af algoritmer, der bruger metoden med partisionsintersection. En partition for en attribut repr\u00e6senterer et s\u00e6t af lister, hvor hver liste indeholder r\u00e6kke numre med de samme v\u00e6rdier for den p\u00e5g\u00e6ldende attribut. Hver s\u00e5dan liste kaldes et kluster. Mange moderne algoritmer bruger partitioner til at bestemme, om en afh\u00e6ngighed opretholdes eller ej, og f\u00f8lger specifikt lemmaet: Afh\u00e6ngigheden \"Effektiv opretholdes, hvis \"Effektiv. Her \"Effektiv betegner partitionen og anvender begrebet partitionsst\u00f8rrelse \u2014 antallet af klustre i den. Algoritmer, der bruger partitioner, tilf\u00f8jer ekstra attributter i venstre del af afh\u00e6ngigheden ved brud p\u00e5 afh\u00e6ngigheden, hvorefter de omberegner den ved at udf\u00f8re en operation for at krydse partitioner. Denne operation kaldes specialisering i artiklerne. Men vi bem\u00e6rkede, at partitioner for afh\u00e6ngigheder, der kun vil blive opretholdt efter flere runder af specialisering, kan blive aktivt genbrugt, hvilket kan betydeligt reducere algoritmernes k\u00f8retid, da krydsning af partitioner er en kostbar operation. <\/p>\n

Derfor foreslog vi en heuristik baseret p\u00e5 Shannons Entropi og Ginis usikkerhed, samt vores metrik, som vi kaldte Omvendt Entropi. Denne er en ubetydelig modifikation af Shannons Entropi og vokser i takt med, at unikheden af datas\u00e6ttet stiger. Den foresl\u00e5ede heuristik ser s\u00e5ledes ud:<\/p>\n

\"Effektiv<\/p>\n

Her \"Effektiv \u2014 graden af unikhed i den nyligt beregnede partition \"Effektiv, og \"Effektiv er en median score for unikke egenskaber. Alle tre metrics, der er beskrevet ovenfor, blev pr\u00f8vet som en unikhedsmetrik. Det er ogs\u00e5 v\u00e6rd at bem\u00e6rke, at der er to modifikatorer i heuristikken. Den f\u00f8rste angiver, hvor t\u00e6t den nuv\u00e6rende partition er p\u00e5 den prim\u00e6re n\u00f8gle, og g\u00f8r det let at cache de partitioner, der er langt fra den potentielle n\u00f8gle. Den anden modifikator giver mulighed for at spore cache-beholdningen, hvilket stimulerer tilf\u00f8jelsen af flere partitioner til cachen, n\u00e5r der er ledig plads. At l\u00f8se denne opgave har gjort det muligt at accelerere PYRO-algoritmen med 10-40 procent afh\u00e6ngigt af datas\u00e6ttet. Det skal bem\u00e6rkes, at PYRO-algoritmen er den mest succesfulde i dette omr\u00e5de. <\/p>\n

I figuren nedenfor kan man se resultaterne af anvendelsen af den foresl\u00e5ede heuristik sammenlignet med den grundl\u00e6ggende cache-tilgang baseret p\u00e5 flipping af en m\u00f8nt. X-aksen er logaritmisk.<\/p>\n

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

Alternativ metode til opbevaring af partitioner<\/h3>\n

\nDerefter foreslog vi en alternativ metode til opbevaring af partitioner. Partitioner repr\u00e6senterer en samling af klynger, hvor hver indeholder numre p\u00e5 tupler med samme v\u00e6rdier for bestemte egenskaber. Disse klynger kan indeholde lange sekvenser af tuple-numre, for eksempel hvis dataene i tabellen er sorteret. Derfor foreslog vi en komprimeringsskema til opbevaring af partitioner, specifikt intervalopbevaring af v\u00e6rdier i partitionens klynger:<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{F\u00f8rste~interval}, underbrace{7, 8}_{Andet~interval}, 10}}\\ downarrow{Kompression}\\ pi(X) = {{underbrace{$, 1, 5}_{F\u00f8rste~interval}, underbrace{7, 8}_{Andet~interval}, 10}}$$display$$<\/p>\n

Denne metode form\u00e5ede at reducere hukommelsesforbruget under udf\u00f8relsen af TANE-algoritmen med 1 til 25%. TANE-algoritmen er en klassisk algoritme til s\u00f8gning af FDs, den bruger partitioner i sin proces. I praksis blev netop TANE-algoritmen valgt, da det var meget lettere at implementere intervalopbevaring i den end for eksempel i PYRO for at vurdere, om den foresl\u00e5ede tilgang virker. De opn\u00e5ede resultater pr\u00e6senteres i figuren nedenfor. X-aksen er logaritmisk.<\/p>\n

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

ADBIS-2019 Konference<\/h3>\n

\nI september 2019 pr\u00e6senterede jeg en artikel baseret p\u00e5 forskningsresultaterne Smart caching for effektiv opdagelse af funktionelle afh\u00e6ngigheder<\/a><\/noindex> p\u00e5 konferencen 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Under pr\u00e6sentationen blev arbejdet fremh\u00e6vet af Bernhard Thalheim, en betydningsfuld person inden for databaser. Forskningsresultaterne dannede grundlaget for min afhandling p\u00e5 matematik-naturvidenskab ved St. Petersborg Universitet, hvor begge de foresl\u00e5ede tilgange (caching og kompression) blev implementeret i begge algoritmer: TANE og PYRO. Resultaterne viste, at de foresl\u00e5ede tilgange er universelle, da der blev observeret en betydelig reduktion i b\u00e5de hukommelsesforbruget og algoritmernes k\u00f8retid i begge algoritmer ved begge tilgange.
\n
Kilde: 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\u00f8gning efter funktionelle afh\u00e6ngigheder i databaser | ProHoster","description":"S\u00f8gning efter funktionelle afh\u00e6ngigheder i data anvendes inden for forskellige retninger af dataanalyse: databaseadministration, datarensning, reverse engineering af databaser og dataudforskning.","canonical_url":"https:\/\/prohoster.info\/da\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"da_DK","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\/da\/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\/da\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}