{"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\/pl\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"Efektywne wyszukiwanie zale\u017cno\u015bci funkcjonalnych w bazach danych.","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Wyszukiwanie zale\u017cno\u015bci funkcyjnych w danych znajduje zastosowanie w r\u00f3\u017cnych obszarach analizy danych: zarz\u0105dzanie bazami danych, czyszczenie danych, in\u017cynieria wsteczna baz danych oraz eksploracja danych. O samych zale\u017cno\u015bciach ju\u017c publikowali\u015bmy artyku\u0142<\/a><\/noindex> Anastasii Birillo i Nikity Bobrowa. Tym razem Anastasia \u2014 absolwentka Computer Science Center tego roku \u2014 dzieli si\u0119 rozwojem tej pracy w ramach Bada\u0144 Naukowych, kt\u00f3re obroni\u0142a w centrum. <\/p>\n

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

Wyb\u00f3r zadania <\/h3>\n

\nPodczas nauki w CS Center zacz\u0119\u0142am zg\u0142\u0119bia\u0107 temat baz danych, a dok\u0142adniej, wyszukiwania zale\u017cno\u015bci funkcyjnych i r\u00f3\u017cnicowych. Temat ten by\u0142 zwi\u0105zany z tematyk\u0105 mojej pracy dyplomowej na uniwersytecie, wi\u0119c w trakcie pracy nad ni\u0105 zacz\u0119\u0142am czyta\u0107 artyku\u0142y dotycz\u0105ce r\u00f3\u017cnych zale\u017cno\u015bci w bazach danych. Napisa\u0142am przegl\u0105d tej dziedziny \u2014 jeden z moich pierwszych artyku\u0142\u00f3w<\/a><\/noindex> w j\u0119zyku angielskim i z\u0142o\u017cy\u0142am go na konferencj\u0119 SEIM-2017. By\u0142am bardzo zadowolona, kiedy dowiedzia\u0142am si\u0119, \u017ce zosta\u0142 przyj\u0119ty, i postanowi\u0142am jeszcze bardziej zag\u0142\u0119bi\u0107 si\u0119 w temat. Sama koncepcja nie jest nowa \u2014 zacz\u0119to j\u0105 stosowa\u0107 ju\u017c w latach 90., ale nadal znajduje zastosowanie w wielu dziedzinach. <\/p>\n

W drugim semestrze nauki w centrum rozpocz\u0119\u0142am projekt badawczy maj\u0105cy na celu popraw\u0119 algorytm\u00f3w wyszukiwania zale\u017cno\u015bci funkcyjnych. Pracowa\u0142am nad nim razem z doktorantem z SPbGU Nikit\u0105 Bobrowem w JetBrains Research. <\/p>\n

Obliczeniowa z\u0142o\u017cono\u015b\u0107 wyszukiwania zale\u017cno\u015bci funkcyjnych<\/h3>\n

\nG\u0142\u00f3wnym problemem jest obliczeniowa z\u0142o\u017cono\u015b\u0107. Liczba mo\u017cliwych minimalnych i nietrywialnych zale\u017cno\u015bci jest ograniczona z g\u00f3ry warto\u015bci\u0105 \"Efektywne, gdzie \"Efektywne \u2014 liczba atrybut\u00f3w tabeli. Czas pracy algorytm\u00f3w zale\u017cy nie tylko od liczby atrybut\u00f3w, ale r\u00f3wnie\u017c od liczby wierszy. W latach 90. algorytmy do wyszukiwania zale\u017cno\u015bci funkcyjnych na zwyk\u0142ym komputerze stacjonarnym mog\u0142y przetwarza\u0107 zbiory danych zawieraj\u0105ce do 20 atrybut\u00f3w i dziesi\u0105tki tysi\u0119cy wierszy, przez kilka godzin. Nowoczesne algorytmy, dzia\u0142aj\u0105ce na wielordzeniowych procesorach, odkrywaj\u0105 zale\u017cno\u015bci dla zbior\u00f3w danych sk\u0142adaj\u0105cych si\u0119 ze setek atrybut\u00f3w (do 200) i setek tysi\u0119cy wierszy, w zbli\u017conym czasie. Niemniej jednak to nie wystarcza: czas ten jest nieakceptowalny dla wi\u0119kszo\u015bci rzeczywistych aplikacji. Dlatego opracowywali\u015bmy podej\u015bcia do przyspieszenia istniej\u0105cych algorytm\u00f3w. <\/p>\n

Schematy pami\u0119ci podr\u0119cznej dla przeci\u0119cia partycji<\/h3>\n

\nW pierwszej cz\u0119\u015bci pracy opracowali\u015bmy schematy buforowania dla klasy algorytm\u00f3w wykorzystuj\u0105cych metod\u0119 przeci\u0119cia partycji. Partycja dla atrybutu reprezentuje zestaw list, gdzie ka\u017cda lista zawiera numery wierszy o identycznych warto\u015bciach dla danego atrybutu. Ka\u017cda taka lista nazywana jest klastrem. Wiele nowoczesnych algorytm\u00f3w u\u017cywa partycji do okre\u015blenia, czy zale\u017cno\u015b\u0107 jest utrzymywana, kieruj\u0105c si\u0119 zasad\u0105: Zale\u017cno\u015b\u0107 \"Efektywne jest utrzymywana, je\u015bli \"Efektywne. Tutaj \"Efektywne oznaczana jest partycja i u\u017cywa si\u0119 poj\u0119cia wielko\u015bci partycji \u2014 liczby klastr\u00f3w w niej. Algorytmy, kt\u00f3re wykorzystuj\u0105 partycje, w przypadku naruszenia zale\u017cno\u015bci dodaj\u0105 dodatkowe atrybuty do lewej strony zale\u017cno\u015bci, po czym przeliczaj\u0105 j\u0105, wykonuj\u0105c operacj\u0119 przeci\u0119cia partycji. Taka operacja w artyku\u0142ach nazywana jest specjalizacj\u0105. Zauwa\u017cyli\u015bmy jednak, \u017ce partycje dla zale\u017cno\u015bci, kt\u00f3re b\u0119d\u0105 utrzymywane tylko po kilku rundach specjalizacji, mog\u0105 by\u0107 aktywnie ponownie wykorzystywane, co mo\u017ce znacznie skr\u00f3ci\u0107 czas dzia\u0142ania algorytm\u00f3w, poniewa\u017c operacja przeci\u0119cia jest kosztowna. <\/p>\n

Dlatego zaproponowali\u015bmy heurystyk\u0119 opart\u0105 na entropii Shannona i niepewno\u015bci Jina, a tak\u017ce nasz\u0105 metryk\u0119, kt\u00f3r\u0105 nazwali\u015bmy Odwrotna Entropia. Jest to nieznaczna modyfikacja entropii Shannona i ro\u015bnie w miar\u0119 wzrostu unikalno\u015bci zbioru danych. Proponowana heurystyka wygl\u0105da nast\u0119puj\u0105co:<\/p>\n

\"Efektywne<\/p>\n

Tutaj \"Efektywne \u2014 stopie\u0144 unikalno\u015bci niedawno obliczonej partycji \"Efektywne, a \"Efektywne jest miar\u0105 unikalno\u015bci median dla poszczeg\u00f3lnych atrybut\u00f3w. Wszystkie trzy metryki opisane powy\u017cej zosta\u0142y przetestowane jako miary unikalno\u015bci. Warto r\u00f3wnie\u017c zauwa\u017cy\u0107, \u017ce w heurystyce obecne s\u0105 dwa modyfikatory. Pierwszy wskazuje, jak bardzo bie\u017c\u0105ca partycja jest zbli\u017cona do klucza podstawowego i pozwala w wi\u0119kszym stopniu buforowa\u0107 te partycje, kt\u00f3re s\u0105 dalekie od potencjalnego klucza. Drugi modyfikator pozwala \u015bledzi\u0107 zaj\u0119to\u015b\u0107 pami\u0119ci podr\u0119cznej, co z kolei stymuluje dodawanie wi\u0119kszej liczby partycji do pami\u0119ci podr\u0119cznej w przypadku dost\u0119pnego miejsca. Sukces w rozwi\u0105zaniu tego problemu pozwoli\u0142 przyspieszy\u0107 algorytm PYRO o 10-40% w zale\u017cno\u015bci od zestawu danych. Warto zauwa\u017cy\u0107, \u017ce algorytm PYRO jest najbardziej skuteczny w tej dziedzinie. <\/p>\n

Na poni\u017cszym rysunku mo\u017cna zobaczy\u0107 wyniki zastosowania proponowanej heurystyki w por\u00f3wnaniu z podstawowym podej\u015bciem do buforowania opartym na rzutowaniu monety. O\u015b X jest logarithmiczna.<\/p>\n

\"Efektywne
\n<\/p>\n

Alternatywny spos\u00f3b przechowywania partycji<\/h3>\n

\nNast\u0119pnie zaproponowali\u015bmy alternatywny spos\u00f3b przechowywania partycji. Partycje stanowi\u0105 zestaw klastr\u00f3w, w kt\u00f3rych przechowywane s\u0105 numery krotek o tych samych warto\u015bciach dla okre\u015blonych atrybut\u00f3w. Te klastry mog\u0105 zawiera\u0107 d\u0142ugie sekwencje numer\u00f3w krotek, na przyk\u0142ad, je\u015bli w tabeli dane s\u0105 uporz\u0105dkowane. Dlatego zaproponowali\u015bmy schemat kompresji do przechowywania partycji, a mianowicie przechowywanie przedzia\u0142\u00f3w warto\u015bci w klastrach partycji:<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Pierwszy~przedzia\u0142}, underbrace{7, 8}_{Drugi~przedzia\u0142}, 10}}\\ downarrow{Kompresja}\\ pi(X) = {{underbrace{$, 1, 5}_{Pierwszy~przedzia\u0142}, underbrace{7, 8}_{Drugi~przedzia\u0142}, 10}}$$display$$<\/p>\n

Ta metoda pozwoli\u0142a na zmniejszenie zu\u017cycia pami\u0119ci podczas dzia\u0142ania algorytmu TANE od 1 do 25%. Algorytm TANE to klasyczny algorytm do wyszukiwania FZ, kt\u00f3ry korzysta z partycji w trakcie swojej pracy. W ramach praktyki wybrano w\u0142a\u015bnie algorytm TANE, poniewa\u017c wprowadzenie przechowywania przedzia\u0142\u00f3w by\u0142o znacznie prostsze ni\u017c na przyk\u0142ad w PYRO, aby oceni\u0107, czy proponowane podej\u015bcie dzia\u0142a. Uzyskane wyniki przedstawiono na poni\u017cszym rysunku. O\u015b X jest logarithmiczna.<\/p>\n

\"Efektywne
\n<\/p>\n

Konferencja ADBIS-2019<\/h3>\n

\nNa podstawie bada\u0144 w wrze\u015bniu 2019 roku wyst\u0105pi\u0142am ze swoj\u0105 prac\u0105 Inteligentne buforowanie dla efektywnego odkrywania zale\u017cno\u015bci funkcjonalnych<\/a><\/noindex> na konferencji 23. Europejskiej Konferencji na temat Post\u0119p\u00f3w w Bazach Danych i Systemach Informacyjnych (ADBIS-2019). W trakcie wyst\u0105pienia swoj\u0105 prac\u0119 podkre\u015bli\u0142 Bernhard Thalheim, znacz\u0105ca posta\u0107 w dziedzinie baz danych. Wyniki bada\u0144 sta\u0142y si\u0119 fundamentem mojej pracy magisterskiej na Wydziale Matematyczno-Fizycznym Uniwersytetu Petersburskiego, podczas kt\u00f3rej oba zaproponowane podej\u015bcia (cache'owanie i kompresja) zosta\u0142y wdro\u017cone w obu algorytmach: TANE i PYRO. Wyniki pokaza\u0142y, \u017ce zaproponowane podej\u015bcia s\u0105 uniwersalne, poniewa\u017c w obu algorytmach przy obu metodach zaobserwowano znaczne zmniejszenie zu\u017cycia pami\u0119ci oraz znacz\u0105ce skr\u00f3cenie czasu dzia\u0142ania algorytm\u00f3w.
\n
\u0179r\u00f3d\u0142o: 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\udd47Efektywne wyszukiwanie zale\u017cno\u015bci funkcjonalnych w bazach danych | ProHoster","description":"Wyszukiwanie zale\u017cno\u015bci funkcjonalnych w danych stosuje si\u0119 w r\u00f3\u017cnych obszarach analizy danych: zarz\u0105dzanie bazami danych, oczyszczanie danych, in\u017cynieria odwrotna baz danych oraz eksploracja danych.","canonical_url":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pl_PL","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\/pl\/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\/pl\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}