{"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 di dipendenze funzionali nei dati \u00e8 applicata in diverse aree dell'analisi dei dati: gestione di database, pulizia dei dati, reverse engineering di database ed esplorazione dei dati. Abbiamo gi\u00e0 pubblicato informazioni sulle dipendenze stesse. articolo<\/a><\/noindex> di Anastasia Birillo e Nikita Bobrov. Questa volta Anastasia, laureata al Computer Science Center di quest'anno, condivide lo sviluppo di quest'opera nell'ambito della ricerca scientifica, che ha difeso nel centro. <\/p>\n

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

Scelta del compito <\/h3>\n

\nDurante il mio percorso di studi al CS Center ho approfondito lo studio dei database, in particolare la ricerca di dipendenze funzionali e differenziali. Questo argomento era legato alla mia tesi universitaria, quindi durante la scrittura ho cominciato a leggere articoli sulle varie dipendenze nei database. Ho scritto una panoramica su quest'area, uno dei miei primi lavori articoli<\/a><\/noindex> in inglese e l'ho presentata alla conferenza SEIM-2017. Ero molto contenta quando ho scoperto che era stata accettata e ho deciso di approfondire l'argomento. Il concetto stesso non \u00e8 nuovo: \u00e8 stato applicato per la prima volta negli anni '90, ma continua a trovare applicazione in molti settori. <\/p>\n

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

La complessit\u00e0 computazionale della ricerca di dipendenze funzionali<\/h3>\n

\nIl problema principale \u00e8 la complessit\u00e0 computazionale. Il numero di dipendenze minime e non banali possibili \u00e8 limitato superiormente dal valore \"Ricerca, dove \"Ricerca cio\u00e8 il numero di attributi della 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 comune PC desktop potevano elaborare set di dati contenenti fino a 20 attributi e decine di migliaia di righe in diverse ore. Gli algoritmi moderni, che lavorano su processori multi-core, scoprono dipendenze per set di dati composti da centinaia di attributi (fino a 200) e centinaia di migliaia di righe, in tempi simili. Tuttavia, questo non \u00e8 sufficiente: tale tempo \u00e8 inaccettabile per la maggior parte delle applicazioni reali. Pertanto, abbiamo sviluppato approcci per accelerare 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 quel dato attributo. Ogni lista \u00e8 chiamata cluster. Molti algoritmi moderni utilizzano le partizioni per determinare se una dipendenza \u00e8 mantenuta o meno, seguendo precisamente il lemma: Una dipendenza \"Ricerca \u00e8 mantenuta se \"Ricerca. Qui \"Ricerca denota una partizione e viene utilizzato il concetto di dimensione della partizione - il numero di cluster in essa. Gli algoritmi che utilizzano le partizioni, quando una dipendenza viene violata, aggiungono ulteriori attributi al lato sinistro della dipendenza, dopo di che la ricalcolano, eseguendo l'operazione di intersezione delle partizioni. Tale operazione \u00e8 chiamata specializzazione in articoli. Ma abbiamo notato che le partizioni per dipendenze che saranno mantenute solo dopo diversi turni di specializzazione possono essere riutilizzate attivamente, il che pu\u00f2 ridurre significativamente 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. Questa \u00e8 una leggera modifica dell'entropia di Shannon e cresce man mano che cresce l'unicit\u00e0 del set di dati. L'euristica proposta \u00e8 la seguente:<\/p>\n

\"Ricerca<\/p>\n

Qui \"Ricerca il grado di unicit\u00e0 della recente partizione calcolata \"Ricerca, e \"Ricerca \u00e8 la mediana dei gradi di unicit\u00e0 per i singoli attributi. Sono state testate come metriche di unicit\u00e0 tutte e tre le metriche descritte sopra. Inoltre, si pu\u00f2 notare che nell'euristica ci sono due modificatori. Il primo indica quanto sia vicina la partizione corrente alla chiave primaria e consente di memorizzare in cache maggiormente quelle partizioni che sono lontane dalla chiave potenziale. Il secondo modificatore consente di monitorare l'occupazione della cache e stimola quindi l'aggiunta di un numero maggiore di partizioni nella cache quando c'\u00e8 spazio libero. Risolvere con successo questo problema ha permesso di accelerare l'algoritmo PYRO dal 10% al 40% a seconda del set di dati. \u00c8 importante notare che l'algoritmo PYRO \u00e8 il pi\u00f9 efficace in questo campo. <\/p>\n

Nella figura sottostante \u00e8 possibile osservare i risultati dell'applicazione dell'euristica proposta rispetto all'approccio di base del caching, basato sul lancio di una moneta. L'asse X \u00e8 logaritmico.<\/p>\n

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

Metodo alternativo per la memorizzazione delle partizioni<\/h3>\n

\nSuccessivamente, abbiamo proposto un metodo alternativo per la memorizzazione delle partizioni. Le partizioni rappresentano un insieme di cluster, ciascuno 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 intervallare dei 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 tra l'1 e il 25%. L'algoritmo TANE \u00e8 un algoritmo classico per la scoperta delle dipendenze funzionali, che utilizza le partizioni nel suo funzionamento. Nell'ambito della pratica \u00e8 stato scelto proprio l'algoritmo TANE, poich\u00e9 integrare la memorizzazione intervallare in esso era significativamente pi\u00f9 semplice che, ad esempio, in PYRO, per valutare se l'approccio proposto funziona. I risultati ottenuti sono presentati nella figura sottostante. L'asse X \u00e8 logaritmico.<\/p>\n

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

Conferenza ADBIS-2019<\/h3>\n

\nA seguito della ricerca, nel settembre 2019 ho presentato un articolo Smart Caching for Efficient Functional Dependency Discovery<\/a><\/noindex> alla 23\u00aa Conferenza Europea su Avanzamenti nei Database e nei Sistemi Informativi (ADBIS-2019). Durante la presentazione, il lavoro \u00e8 stato riconosciuto da Bernhard Thalheim, una figura importante nel campo dei database. I risultati della ricerca sono stati la base della mia tesi di laurea in Matematica e Meccanica all'Universit\u00e0 Statale di San Pietroburgo, durante la quale entrambi gli approcci proposti (caching e compressione) sono stati implementati in entrambi gli algoritmi: TANE e PYRO. I risultati hanno dimostrato che gli approcci proposti sono universali, poich\u00e9 in entrambi gli algoritmi con entrambi gli approcci si \u00e8 osservata una significativa riduzione della memoria utilizzata, cos\u00ec come una significativa riduzione dei tempi 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 efficiente delle dipendenze funzionali nei database | ProHoster","description":"La ricerca di dipendenze funzionali nei dati \u00e8 applicata in diverse aree dell'analisi dei dati: gestione dei database, pulizia dei dati, reverse engineering dei database e data exploration.","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}]}}