{"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\/de\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"Effektive Suche nach funktionalen Abh\u00e4ngigkeiten in Datenbanken","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Die Suche nach funktionalen Abh\u00e4ngigkeiten in Daten wird in verschiedenen Analysebereichen angewendet: Datenbankmanagement, Datenbereinigung, Reverse Engineering von Datenbanken und Datenexploration. \u00dcber die Abh\u00e4ngigkeiten selbst haben wir bereits ver\u00f6ffentlicht einen Artikel<\/a><\/noindex> Anastasia Birillo und Nikita Bobrov. Diesmal teilt Anastasia \u2013 Absolventin des Computer Science Centers dieses Jahres \u2013 die Entwicklung ihrer Arbeit im Rahmen der Forschungsarbeit, die sie im Zentrum verteidigt hat. <\/p>\n

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

Aufgabenwahl <\/h3>\n

\nW\u00e4hrend meines Studiums im CS-Zentrum begann ich, mich intensiv mit Datenbanken zu besch\u00e4ftigen, insbesondere mit der Suche nach funktionalen und differenziellen Abh\u00e4ngigkeiten. Dieses Thema war mit dem Thema meiner Abschlussarbeit an der Universit\u00e4t verbunden, sodass ich beim Arbeiten an meiner Arbeit begann, Artikel zu verschiedenen Abh\u00e4ngigkeiten in Datenbanken zu lesen. Ich schrieb einen \u00dcberblick \u00fcber dieses Gebiet \u2013 eine meiner ersten Artikel<\/a><\/noindex> in englischer Sprache und reichte ihn f\u00fcr die Konferenz SEIM-2017 ein. Ich war sehr froh, als ich erfuhr, dass er angenommen wurde, und beschloss, mich tiefer mit dem Thema zu befassen. Das Konzept selbst ist nicht neu \u2013 es wird seit den 90er Jahren angewendet, kommt aber immer noch in vielen Bereichen zur Anwendung. <\/p>\n

Im zweiten Semester meines Studiums im Zentrum begann ich ein Forschungsprojekt zur Verbesserung der Algorithmen zur Suche nach funktionalen Abh\u00e4ngigkeiten. Ich arbeitete daran zusammen mit dem Doktoranden Nikita Bobrov von der Universit\u00e4t St. Petersburg basierend auf JetBrains Research. <\/p>\n

Berechnungskomplexit\u00e4t der Suche nach funktionalen Abh\u00e4ngigkeiten<\/h3>\n

\nDas Hauptproblem ist die Berechnungskomplexit\u00e4t. Die Anzahl der m\u00f6glichen minimalen und nicht-trivialen Abh\u00e4ngigkeiten ist nach oben durch den Wert begrenzt \"Effektive

\"Effektive \u2013 die Anzahl der Attribute der Tabelle. Die Laufzeit der Algorithmen h\u00e4ngt nicht nur von der Anzahl der Attribute, sondern auch von der Anzahl der Zeilen ab. In den 90er Jahren konnten Algorithmen zur Suche nach funktionalen Abh\u00e4ngigkeiten auf einem normalen Desktop-PC Datens\u00e4tze mit bis zu 20 Attributen und Tausenden von Zeilen in mehreren Stunden verarbeiten. Moderne Algorithmen, die auf Mehrkernprozessoren arbeiten, erkennen Abh\u00e4ngigkeiten f\u00fcr Datens\u00e4tze mit Hunderte von Attributen (bis zu 200) und Hunderttausenden von Zeilen in etwa der gleichen Zeit. Dennoch ist das nicht ausreichend: Diese Zeit ist f\u00fcr die meisten realen Anwendungen inakzeptabel. Daher haben wir Ans\u00e4tze zur Beschleunigung bestehender Algorithmen entwickelt. <\/p>\n

Caching-Modelle f\u00fcr die Partitionierung<\/h3>\n

\nIm ersten Teil der Arbeit haben wir Caching-Schemata f\u00fcr die Klasse von Algorithmen entwickelt, die das Methode des Partitionenschnitts verwenden. Eine Partition f\u00fcr ein Attribut besteht aus einer Gruppe von Listen, wobei jede Liste die Zeilennummern mit denselben Werten f\u00fcr dieses Attribut enth\u00e4lt. Jede solche Liste wird als Cluster bezeichnet. Viele moderne Algorithmen verwenden Partitionen, um festzustellen, ob eine Abh\u00e4ngigkeit gehalten wird oder nicht, und halten sich dabei an das Lemma: Abh\u00e4ngigkeit \"Effektive wird gehalten, wenn \"Effektive. Hier wird die Partition bezeichnet und das Konzept der Partitionsgr\u00f6\u00dfe - die Anzahl der Cluster darin - verwendet. Algorithmen, die Partitionen verwenden, f\u00fcgen bei Verletzung der Abh\u00e4ngigkeit zus\u00e4tzliche Attribute in den linken Teil der Abh\u00e4ngigkeit ein und berechnen sie dann neu, indem sie den Schnitt der Partitionen durchf\u00fchren. Dieser Vorgang wird in den Artikeln als Spezialisierung bezeichnet. Wir haben jedoch festgestellt, dass Partitionen f\u00fcr Abh\u00e4ngigkeiten, die erst nach mehreren Runden der Spezialisierung gehalten werden, aktiv wiederverwendet werden k\u00f6nnen, was die Laufzeit der Algorithmen erheblich verk\u00fcrzen kann, da der Schnitt eine kostenintensive Operation ist. \"Effektive Daher haben wir eine Heuristik vorgeschlagen, die auf der Shannon-Entropie und der Ungewissheit von Genie basiert, sowie auf unserer Metrik, die wir als Umgekehrte Entropie bezeichnet haben. Sie ist eine geringf\u00fcgige Modifikation der Shannon-Entropie und w\u00e4chst mit zunehmender Einzigartigkeit des Datensatzes. Die vorgeschlagene Heuristik sieht wie folgt aus: <\/p>\n

\u2014 Der Grad der Einzigartigkeit der k\u00fcrzlich berechneten Partition<\/p>\n

\"Effektive<\/p>\n

Hier \"Effektive \u2014 Grad der Einzigartigkeit einer k\u00fcrzlich berechneten Partition \"Effektive, und \"Effektive ist die Median der Einzigartigkeitsstufen f\u00fcr einzelne Attribute. Alle drei oben beschriebenen Metriken wurden als Metrik der Einzigartigkeit getestet. Es f\u00e4llt auch auf, dass die Heuristik zwei Modifikatoren enth\u00e4lt. Der erste gibt an, wie nahe die aktuelle Partition am Prim\u00e4rschl\u00fcssel ist und erm\u00f6glicht es in gr\u00f6\u00dferem Ma\u00dfe, diejenigen Partitionen zwischenzuspeichern, die weit vom potenziellen Schl\u00fcssel entfernt sind. Der zweite Modifikator erm\u00f6glicht es, die Cache-Auslastung zu \u00fcberwachen und f\u00f6rdert damit die Aufnahme einer gr\u00f6\u00dferen Anzahl von Partitionen in den Cache, wenn Platz vorhanden ist. Die erfolgreiche L\u00f6sung dieses Problems erlaubte eine Beschleunigung des PYRO-Algorithmus um 10-40 Prozent, abh\u00e4ngig von dem Datensatz. Es ist erw\u00e4hnenswert, dass der PYRO-Algorithmus in diesem Bereich am erfolgreichsten ist. <\/p>\n

In der untenstehenden Abbildung sind die Ergebnisse der Anwendung der vorgeschlagenen Heuristik im Vergleich zum grundlegenden Ansatz des Cachings zu sehen, der auf dem Werfen einer M\u00fcnze basiert. Die X-Achse ist logarithmisch.<\/p>\n

\"Effektive
\n<\/p>\n

Alternativer Ansatz zur Speicherung von Partitionen<\/h3>\n

\nDann haben wir einen alternativen Ansatz zur Speicherung von Partitionen vorgeschlagen. Partitionen stellen eine Menge von Clustern dar, in denen die Nummern von Tuplen mit denselben Werten f\u00fcr bestimmte Attribute gespeichert sind. Diese Cluster k\u00f6nnen lange Sequenzen von Tuplennummern enthalten, beispielsweise wenn die Daten in der Tabelle sortiert sind. Daher haben wir ein Kompressionsschema f\u00fcr die Speicherung von Partitionen vorgeschlagen, n\u00e4mlich die intervallbasierte Speicherung von Werten in den Clustern der Partitionen:<\/p>\n

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

Diese Methode konnte den Speicherverbrauch w\u00e4hrend der Ausf\u00fchrung des TANE-Algorithmus um 1 bis 25 % reduzieren. Der TANE-Algorithmus ist ein klassischer Algorithmus zur Suche nach funktionalen Abh\u00e4ngigkeiten, der w\u00e4hrend seiner Ausf\u00fchrung Partitionen verwendet. Innerhalb der Praxis wurde der TANE-Algorithmus ausgew\u00e4hlt, da es wesentlich einfacher war, die intervallbasierte Speicherung zu implementieren als beispielsweise im PYRO, um zu bewerten, ob der vorgeschlagene Ansatz funktioniert. Die erhaltenen Ergebnisse sind in der untenstehenden Abbildung dargestellt. Die X-Achse ist logarithmisch.<\/p>\n

\"Effektive
\n<\/p>\n

Konferenz ADBIS-2019<\/h3>\n

\nIm Ergebnis der Studie im September 2019 habe ich einen Artikel pr\u00e4sentiert Intelligentes Caching zur effizienten Entdeckung funktionaler Abh\u00e4ngigkeiten<\/a><\/noindex> Auf der 23. Europ\u00e4ischen Konferenz \u00fcber Fortschritte in Datenbanken und Informationssystemen (ADBIS-2019) bemerkte Bernhard Thalheim, eine bedeutende Pers\u00f6nlichkeit im Bereich der Datenbanken, w\u00e4hrend seiner Pr\u00e4sentation meine Arbeit. Die Forschungsergebnisse bildeten die Grundlage meiner Masterarbeit im Fachbereich Mathematik und Mechanik an der Universit\u00e4t St. Petersburg, im Rahmen derer beide vorgeschlagenen Ans\u00e4tze (Caching und Kompression) in die beiden Algorithmen TANE und PYRO integriert wurden. Die Ergebnisse zeigten, dass die vorgeschlagenen Ans\u00e4tze universell sind, da bei beiden Algorithmen und beiden Ans\u00e4tzen eine signifikante Reduktion des Speicherverbrauchs sowie eine erhebliche Verk\u00fcrzung der Laufzeit der Algorithmen beobachtet wurde.
\n
Quelle: 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\udd47Effektive Suche nach funktionalen Abh\u00e4ngigkeiten in Datenbanken | ProHoster","description":"Die Suche nach funktionalen Abh\u00e4ngigkeiten in Daten wird in verschiedenen Bereichen der Datenanalyse angewendet: Datenbankmanagement, Datenbereinigung, Reverse Engineering von Datenbanken und Datenexploration.","canonical_url":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"de_DE","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\/de\/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\/de\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}