{"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\/it\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"Ricerca efficace delle dipendenze funzionali nei database","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

La ricerca delle dipendenze funzionali nei dati viene applicata in vari campi dell'analisi dei dati: gestione dei database, pulizia dei dati, reverse engineering dei database ed esplorazione dei dati. Di queste dipendenze abbiamo gi\u00e0 pubblicato articolo<\/a><\/noindex> di Anastasia Birillo e Nikita Bobrov. Questa volta Anastasia, laureata del Computer Science Center di quest'anno, condivide lo sviluppo di questo lavoro nell'ambito del NIR, che ha presentato al centro. <\/p>\n

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

Scelta del compito <\/h3>\n

\nDurante l'apprendimento al CS Center, ho iniziato a studiare in profondit\u00e0 i database, in particolare la ricerca di dipendenze funzionali e differenziali. Questo argomento era collegato al tema della mia tesi universitaria, quindi durante il lavoro sulla tesi ho iniziato a leggere articoli sulle varie dipendenze nei database. Ho scritto una panoramica di quest'area \u2014 uno dei miei primi articoli<\/a><\/noindex> in inglese e l'ho presentato alla conferenza SEIM-2017. Ero molto felice quando ho scoperto che era stato accettato e ho deciso di approfondire il tema. Il concetto stesso non \u00e8 nuovo: \u00e8 stato applicato fin dagli anni '90, ma anche adesso trova applicazione in molti campi. <\/p>\n

Nel secondo semestre di studio al centro, ho iniziato un progetto di ricerca volto a migliorare gli algoritmi di ricerca delle dipendenze funzionali. Ho lavorato a questo progetto insieme al dottorando di SPbGU Nikita Bobrov presso JetBrains Research. <\/p>\n

Complesso computazionale della ricerca delle dipendenze funzionali<\/h3>\n

\nIl problema principale \u00e8 la complessit\u00e0 computazionale. Il numero possibile di dipendenze minime e non banali \u00e8 limitato superiormente dal valore \"Ricerca, dove \"Ricerca \u00e8 il numero di attributi nella tabella. Il tempo di esecuzione degli algoritmi dipende non solo dal numero di attributi, ma anche dal numero di righe. Negli anni '90, gli algoritmi per la ricerca delle dipendenze funzionali su un normale PC desktop potevano elaborare set di dati contenenti fino a 20 attributi e decine di migliaia di righe, richiedendo anche diverse ore. Gli algoritmi moderni, che operano su processori multicore, trovano dipendenze per set di dati composti da centinaia di attributi (fino a 200) e centinaia di migliaia di righe, in un tempo simile. Tuttavia, ci\u00f2 non \u00e8 sufficiente: tale tempo \u00e8 inaccettabile per la maggior parte delle applicazioni reali. Pertanto, abbiamo sviluppato approcci per velocizzare gli algoritmi esistenti. <\/p>\n

Schemi di caching per l'intersezione delle partizioni<\/h3>\n

\nNella prima parte del lavoro abbiamo sviluppato schemi di caching per una classe di algoritmi che utilizzano il metodo di intersezione delle partizioni. Una partizione per un attributo rappresenta un insieme di liste, dove ogni lista contiene i numeri di riga con valori identici per questo attributo. Ogni lista di questo tipo \u00e8 chiamata cluster. Molti algoritmi moderni usano partizioni per determinare se una dipendenza \u00e8 mantenuta o meno, seguendo il lemma: La dipendenza \"Ricerca \u00e8 mantenuta, se \"Ricerca. Qui \"Ricerca \u00e8 designata la partizione e si usa il concetto di dimensione della partizione \u2014 il numero di cluster in essa. Gli algoritmi che usano partizioni, quando la dipendenza \u00e8 violata, aggiungono attributi aggiuntivi al lato sinistro della dipendenza, dopo di che la ricalcolano eseguendo l'operazione di intersezione delle partizioni. Questa operazione \u00e8 chiamata specializzazione negli articoli. Ma abbiamo notato che le partizioni per le dipendenze, che saranno mantenute solo dopo diversi turni di specializzazione, possono essere riutilizzate attivamente, il che pu\u00f2 notevolmente ridurre il tempo di esecuzione degli algoritmi, poich\u00e9 l'operazione di intersezione \u00e8 costosa. <\/p>\n

Pertanto, abbiamo proposto un'euristica basata sull'Entropia di Shannon e sull'incertezza di Gini, oltre alla nostra metrica, che abbiamo chiamato Entropia Inversa. Essa \u00e8 una lieve modifica dell'Entropia di Shannon e cresce man mano che aumenta l'unicit\u00e0 del set di dati. L'euristica proposta appare come segue:<\/p>\n

\"Ricerca<\/p>\n

Qui \"Ricerca \u00e8 il grado di unicit\u00e0 della partizione appena calcolata \"Ricerca, ma \"Ricerca \u00e8 una mediana dei livelli di unicit\u00e0 per singoli attributi. Come metrica di unicit\u00e0 sono state testate tutte e tre le metriche descritte sopra. Si pu\u00f2 anche notare che nell'euristica sono presenti due modificatori. Il primo indica quanto sia vicina la partizione attuale alla chiave primaria e consente di memorizzare nella cache in modo pi\u00f9 efficace quelle partizioni che sono lontane dalla chiave potenziale. Il secondo modificatore consente di monitorare l'occupazione della cache e stimola cos\u00ec l'aggiunta di un numero maggiore di partizioni nella cache in presenza di spazio libero. La risoluzione riuscita di questo compito ha permesso di accelerare l'algoritmo PYRO del 10-40% a seconda del dataset. Vale la pena notare che l'algoritmo PYRO \u00e8 il pi\u00f9 efficace in questo ambito. <\/p>\n

Nell'immagine sottostante si possono vedere i risultati dell'applicazione dell'euristica proposta rispetto all'approccio di caching di base basato sul lancio della moneta. L'asse X \u00e8 logaritmico.<\/p>\n

\"Ricerca
\n<\/p>\n

Metodo alternativo di memorizzazione delle partizioni<\/h3>\n

\nPoi abbiamo proposto un metodo alternativo di memorizzazione delle partizioni. Le partizioni rappresentano un insieme di cluster, ognuno dei quali contiene i numeri delle tuple con valori identici per determinati attributi. Questi cluster possono contenere lunghe sequenze di numeri di tuple, ad esempio, se i dati nella tabella sono ordinati. Pertanto, abbiamo proposto uno schema di compressione per la memorizzazione delle partizioni, ossia la memorizzazione degli intervalli di valori nei cluster delle partizioni:<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Primo~intervallo}, underbrace{7, 8}_{Secondo~intervallo}, 10}}\\ downarrow{Compressione}\\ pi(X) = {{underbrace{$, 1, 5}_{Primo~intervallo}, underbrace{7, 8}_{Secondo~intervallo}, 10}}$$display$$<\/p>\n

Questo metodo \u00e8 riuscito a ridurre il consumo di memoria durante l'esecuzione dell'algoritmo TANE dal 1 al 25%. L'algoritmo TANE \u00e8 un algoritmo classico per la ricerca di FD, utilizza le partizioni nel suo funzionamento. Nell'ambito della pratica \u00e8 stato scelto proprio l'algoritmo TANE, in quanto implementare la memorizzazione per intervallo \u00e8 stato significativamente pi\u00f9 semplice rispetto a, ad esempio, PYRO, per valutare se l'approccio proposto funziona. I risultati ottenuti sono presentati nell'immagine sottostante. L'asse X \u00e8 logaritmico.<\/p>\n

\"Ricerca
\n<\/p>\n

Conferenza ADBIS-2019<\/h3>\n

\nIn base ai risultati della ricerca di settembre 2019, ho presentato un articolo Caching Intelligente per una Scoperta Efficiente delle Dipendenze Funzionali<\/a><\/noindex> alla conferenza 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Durante l'intervento, il lavoro \u00e8 stato sottolineato da Bernhard Thalheim, una figura di rilievo nel campo dei database. I risultati delle ricerche hanno costituito la base della mia tesi di laurea nel programma di matematica e meccanica della SPbGU, durante la quale entrambi gli approcci proposti (caching e compressione) sono stati implementati negli algoritmi: TANE e PYRO. I risultati hanno dimostrato che gli approcci proposti sono universali, poich\u00e9 su entrambi gli algoritmi con entrambi gli approcci si \u00e8 osservata una significativa riduzione della memoria utilizzata, nonch\u00e9 una significativa riduzione del tempo di esecuzione degli algoritmi.
\n
Fonte: 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\udd47Ricerca efficace delle dipendenze funzionali nei database | ProHoster","description":"La ricerca delle dipendenze funzionali nei dati viene applicata in diversi ambiti dell'analisi dei dati: gestione dei database, pulizia dei dati, reverse engineering dei database ed esplorazione dei dati.","canonical_url":"https:\/\/prohoster.info\/it\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"it_IT","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\/it\/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\/it\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}