{"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\/fr\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","title":{"rendered":"Recherche efficace de d\u00e9pendances fonctionnelles dans les bases de donn\u00e9es.","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

La recherche de d\u00e9pendances fonctionnelles dans les donn\u00e9es est appliqu\u00e9e dans diff\u00e9rents domaines de l'analyse des donn\u00e9es : gestion de bases de donn\u00e9es, nettoyage des donn\u00e9es, r\u00e9tro-ing\u00e9nierie de bases de donn\u00e9es et exploration des donn\u00e9es. Nous avons d\u00e9j\u00e0 publi\u00e9 sur ces d\u00e9pendances. article<\/a><\/noindex> Anastasia Birillo et Nikita Bobrov. Cette fois, Anastasia \u2014 dipl\u00f4m\u00e9e du Computer Science Center de cette ann\u00e9e \u2014 partage le d\u00e9veloppement de ce travail dans le cadre de son projet de recherche, qu'elle a pr\u00e9sent\u00e9 au centre. <\/p>\n

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

Choix de la t\u00e2che <\/h3>\n

\nPendant mes \u00e9tudes au centre CS, j'ai commenc\u00e9 \u00e0 \u00e9tudier en profondeur les bases de donn\u00e9es, plus pr\u00e9cis\u00e9ment, la recherche de d\u00e9pendances fonctionnelles et diff\u00e9rentes d\u00e9pendances. Ce sujet \u00e9tait li\u00e9 au th\u00e8me de mon m\u00e9moire \u00e0 l'universit\u00e9, donc pendant que je travaillais sur le m\u00e9moire, j'ai commenc\u00e9 \u00e0 lire des articles sur les diff\u00e9rentes d\u00e9pendances dans les bases de donn\u00e9es. J'ai r\u00e9dig\u00e9 une revue sur ce domaine \u2014 l'une de mes premi\u00e8res. articles<\/a><\/noindex> en anglais et je l'ai soumise \u00e0 la conf\u00e9rence SEIM-2017. J'\u00e9tais tr\u00e8s heureuse d'apprendre qu'elle avait \u00e9t\u00e9 accept\u00e9e, et j'ai d\u00e9cid\u00e9 d'approfondir le sujet. Le concept lui-m\u00eame n'est pas nouveau \u2014 il a commenc\u00e9 \u00e0 \u00eatre appliqu\u00e9 d\u00e8s les ann\u00e9es 90, mais il trouve encore des applications dans de nombreux domaines aujourd'hui. <\/p>\n

Au deuxi\u00e8me semestre de mes \u00e9tudes au centre, j'ai commenc\u00e9 un projet de recherche sur l'am\u00e9lioration des algorithmes de recherche de d\u00e9pendances fonctionnelles. J'ai travaill\u00e9 dessus avec le doctorant de l'Universit\u00e9 d'\u00c9tat de Saint-P\u00e9tersbourg, Nikita Bobrov, chez JetBrains Research. <\/p>\n

Complexit\u00e9 computationnelle de la recherche de d\u00e9pendances fonctionnelles<\/h3>\n

\nLe principal probl\u00e8me est la complexit\u00e9 computationnelle. Le nombre de d\u00e9pendances minimales et non triviaux possibles est limit\u00e9 par la valeur \"Recherche, o\u00f9 \"Recherche \u2014 le nombre d'attributs dans la table. Le temps d'ex\u00e9cution des algorithmes d\u00e9pend non seulement du nombre d'attributs, mais aussi du nombre de lignes. Dans les ann\u00e9es 90, les algorithmes de recherche de d\u00e9pendances fonctionnelles sur un PC de bureau normal pouvaient traiter des ensembles de donn\u00e9es contenant jusqu'\u00e0 20 attributs et des dizaines de milliers de lignes pendant plusieurs heures. Les algorithmes modernes, fonctionnant sur des processeurs multicores, d\u00e9tectent des d\u00e9pendances pour des ensembles de donn\u00e9es compos\u00e9s de centaines d'attributs (jusqu'\u00e0 200) et de centaines de milliers de lignes, en un temps similaire. Pourtant, cela reste insuffisant : ce temps est inacceptable pour la plupart des applications r\u00e9elles. C'est pourquoi nous avons d\u00e9velopp\u00e9 des approches pour acc\u00e9l\u00e9rer les algorithmes existants. <\/p>\n

Sch\u00e9mas de mise en cache pour l'intersection des partitions<\/h3>\n

\nDans la premi\u00e8re partie de notre travail, nous avons d\u00e9velopp\u00e9 des sch\u00e9mas de mise en cache pour une classe d'algorithmes utilisant une m\u00e9thode d'intersection des partitions. Une partition pour un attribut repr\u00e9sente un ensemble de listes, o\u00f9 chaque liste contient les num\u00e9ros de ligne avec les m\u00eames valeurs pour cet attribut. Chaque liste est appel\u00e9e un cluster. De nombreux algorithmes modernes utilisent des partitions pour d\u00e9terminer si une d\u00e9pendance est maintenue ou non, en se basant sur le lemme : La d\u00e9pendance \"Recherche est maintenue si \"Recherche. Ici \"Recherche la partition est d\u00e9sign\u00e9e et on utilise le concept de taille de partition \u2014 le nombre de clusters qu'elle contient. Les algorithmes utilisant des partitions, lorsqu'une d\u00e9pendance est rompue, ajoutent des attributs suppl\u00e9mentaires dans la partie gauche de la d\u00e9pendance, puis la recalculent en effectuant une op\u00e9ration d'intersection des partitions. Cette op\u00e9ration est appel\u00e9e sp\u00e9cialisation dans les articles. Cependant, nous avons remarqu\u00e9 que les partitions pour les d\u00e9pendances qui ne seront maintenues qu'apr\u00e8s plusieurs tours de sp\u00e9cialisation peuvent \u00eatre activement r\u00e9utilis\u00e9es, ce qui peut consid\u00e9rablement r\u00e9duire le temps de fonctionnement des algorithmes, car l'op\u00e9ration d'intersection est co\u00fbteuse. <\/p>\n

C'est pourquoi nous avons propos\u00e9 une heuristique bas\u00e9e sur l'Entropie de Shannon et l'incertitude de Gini, ainsi que notre m\u00e9trique, que nous avons appel\u00e9e Entropie Invers\u00e9e. C'est une l\u00e9g\u00e8re modification de l'Entropie de Shannon et elle augmente \u00e0 mesure que l'unicit\u00e9 de l'ensemble de donn\u00e9es cro\u00eet. L'heuristique propos\u00e9e est la suivante :<\/p>\n

\"Recherche<\/p>\n

Ici \"Recherche \u2014 le degr\u00e9 d'unicit\u00e9 de la partition r\u00e9cemment calcul\u00e9e \"Recherche, et \"Recherche est la m\u00e9diane des degr\u00e9s d'unicit\u00e9 pour certains attributs. Pour la m\u00e9trique d'unicit\u00e9, toutes les trois m\u00e9triques d\u00e9crites ci-dessus ont \u00e9t\u00e9 test\u00e9es. On peut \u00e9galement noter que l'heuristique contient deux modificateurs. Le premier indique \u00e0 quel point la partition actuelle est proche de la cl\u00e9 primaire et permet de mettre en cache dans une plus grande mesure les partitions qui sont \u00e9loign\u00e9es de la cl\u00e9 potentielle. Le second modificateur permet de suivre l'occupation du cache et incite ainsi \u00e0 ajouter plus de partitions dans le cache lorsqu'il y a de la place libre. La r\u00e9solution r\u00e9ussie de cette t\u00e2che a permis d'acc\u00e9l\u00e9rer l'algorithme PYRO de 10 \u00e0 40 % selon le jeu de donn\u00e9es. Il convient de noter que l'algorithme PYRO est le plus performant dans ce domaine. <\/p>\n

La figure ci-dessous montre les r\u00e9sultats de l'application de l'heuristique propos\u00e9e par rapport \u00e0 l'approche de base de mise en cache, qui est bas\u00e9e sur le lancer de d\u00e9s. L'axe X est logarithmique.<\/p>\n

\"Recherche
\n<\/p>\n

M\u00e9thode alternative de stockage des partitions<\/h3>\n

\nNous avons ensuite propos\u00e9 une m\u00e9thode alternative de stockage des partitions. Les partitions repr\u00e9sentent un ensemble de clusters, dans chacun desquels sont stock\u00e9s les num\u00e9ros de tuples ayant les m\u00eames valeurs pour certains attributs. Ces clusters peuvent contenir de longues s\u00e9quences de num\u00e9ros de tuples, par exemple, si les donn\u00e9es du tableau sont ordonn\u00e9es. Par cons\u00e9quent, nous avons propos\u00e9 un sch\u00e9ma de compression pour le stockage des partitions, \u00e0 savoir le stockage par intervalles des valeurs dans les clusters de partition :<\/p>\n

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Premier~intervalle}, underbrace{7, 8}_{Deuxi\u00e8me~intervalle}, 10}}\\ downarrow{Compression}\\ pi(X) = {{underbrace{$, 1, 5}_{Premier~intervalle}, underbrace{7, 8}_{Deuxi\u00e8me~intervalle}, 10}}$$display$$<\/p>\n

Cette m\u00e9thode a pu r\u00e9duire la consommation de m\u00e9moire lors de l'ex\u00e9cution de l'algorithme TANE de 1 \u00e0 25 %. L'algorithme TANE est un algorithme classique de d\u00e9couverte de d\u00e9pendances fonctionnelles, il utilise des partitions pendant son fonctionnement. Dans le cadre de la pratique, c'est pr\u00e9cis\u00e9ment l'algorithme TANE qui a \u00e9t\u00e9 choisi, car il \u00e9tait beaucoup plus simple d'y int\u00e9grer le stockage par intervalles que, par exemple, dans PYRO, afin d'\u00e9valuer si l'approche propos\u00e9e fonctionne. Les r\u00e9sultats obtenus sont pr\u00e9sent\u00e9s dans la figure ci-dessous. L'axe X est logarithmique.<\/p>\n

\"Recherche
\n<\/p>\n

Conf\u00e9rence ADBIS-2019<\/h3>\n

\nSuite aux r\u00e9sultats de la recherche en septembre 2019, j'ai pr\u00e9sent\u00e9 un article Caching Intelligent pour une D\u00e9couverte Efficace des D\u00e9pendances Fonctionnelles<\/a><\/noindex> Lors de la 23e Conf\u00e9rence Europ\u00e9enne sur les Avanc\u00e9es dans les Bases de Donn\u00e9es et les Syst\u00e8mes d'Information (ADBIS-2019), Bernhard Thalheim, une figure marquante dans le domaine des bases de donn\u00e9es, a soulign\u00e9 mon travail. Les r\u00e9sultats de ma recherche ont servi de base \u00e0 ma th\u00e8se de ma\u00eetrise en math\u00e9matiques appliqu\u00e9es \u00e0 l'Universit\u00e9 d'\u00c9tat de Saint-P\u00e9tersbourg, au cours de laquelle les deux approches propos\u00e9es (la mise en cache et la compression) ont \u00e9t\u00e9 int\u00e9gr\u00e9es dans les deux algorithmes : TANE et PYRO. Ces r\u00e9sultats ont montr\u00e9 que les approches propos\u00e9es sont universelles, car une r\u00e9duction significative de la m\u00e9moire utilis\u00e9e et du temps d'ex\u00e9cution des algorithmes a \u00e9t\u00e9 observ\u00e9e dans les deux cas.
\n
Source : 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\udd47Recherche efficace de d\u00e9pendances fonctionnelles dans les bases de donn\u00e9es | ProHoster","description":"La recherche de d\u00e9pendances fonctionnelles dans les donn\u00e9es est appliqu\u00e9e dans divers domaines d'analyse de donn\u00e9es : gestion de bases de donn\u00e9es, nettoyage de donn\u00e9es, r\u00e9tro-ing\u00e9nierie de bases de donn\u00e9es et exploration de donn\u00e9es.","canonical_url":"https:\/\/prohoster.info\/fr\/blog\/administrirovanie\/effektivnyj-poisk-funkczionalnyh-zavisimostej-v-bazah-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"fr_FR","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\/fr\/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\/fr\/wp-json\/wp\/v2\/posts\/86335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/comments?post=86335"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts\/86335\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media\/86336"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media?parent=86335"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/categories?post=86335"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/tags?post=86335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}