Trouver efficacement les dépendances fonctionnelles dans les bases de données

La recherche de dépendances fonctionnelles dans les données est utilisée dans divers domaines de l'analyse des données : gestion de bases de données, nettoyage des données, ingénierie inverse des bases de données et exploration des données. Nous avons déjà publié sur les dépendances elles-mêmes статью Anastasia Birillo et Nikita Bobrov. Cette fois, Anastasia, diplômée du Centre d'Informatique cette année, partage l'évolution de ces travaux dans le cadre des travaux de recherche qu'elle a défendus au centre.

Sélection de tâche

Pendant mes études au centre CS, j'ai commencé à étudier en profondeur les bases de données, à savoir la recherche de dépendances fonctionnelles et différentielles. Ce sujet était lié au sujet de mes cours à l'université, donc tout en travaillant sur mes cours, j'ai commencé à lire des articles sur diverses dépendances dans les bases de données. J'ai écrit une critique sur ce domaine - une de mes premières articles en anglais et l'a soumis à la conférence SEIM-2017. J'ai été très heureux d'apprendre qu'elle avait finalement été acceptée et j'ai décidé d'approfondir le sujet. Le concept lui-même n'est pas nouveau - il a commencé à être utilisé dans les années 90, mais il est encore utilisé aujourd'hui dans de nombreux domaines.

Au cours de mon deuxième semestre au centre, j'ai démarré un projet de recherche visant à améliorer les algorithmes de recherche de dépendances fonctionnelles. Elle a travaillé dessus avec Nikita Bobrov, étudiant diplômé de l'Université d'État de Saint-Pétersbourg, chez JetBrains Research.

Complexité informatique de la recherche de dépendances fonctionnelles

Le principal problème est la complexité informatique. Le nombre de dépendances minimales et non triviales possibles est limité ci-dessus par la valeur Où — nombre d'attributs de table. Le temps de fonctionnement des algorithmes dépend non seulement du nombre d'attributs, mais aussi du nombre de lignes. Dans les années 90, les algorithmes de recherche des lois fédérales sur un ordinateur de bureau ordinaire pouvaient traiter des ensembles de données contenant jusqu'à 20 attributs et des dizaines de milliers de lignes en plusieurs heures. Les algorithmes modernes exécutés sur des processeurs multicœurs détectent les dépendances pour des ensembles de données constitués de centaines d'attributs (jusqu'à 200) et de centaines de milliers de lignes à peu près en même temps. Cependant, cela ne suffit pas : un tel délai est inacceptable pour la plupart des applications du monde réel. Par conséquent, nous avons développé des approches pour accélérer les algorithmes existants.

Schémas de mise en cache pour les intersections de partitions

Dans la première partie du travail, nous avons développé des schémas de mise en cache pour une classe d'algorithmes utilisant la méthode d'intersection de partitions. Une partition pour un attribut est un ensemble de listes, où chaque liste contient des numéros de ligne avec les mêmes valeurs pour un attribut donné. Chacune de ces listes est appelée un cluster. De nombreux algorithmes modernes utilisent des partitions pour déterminer si une dépendance est maintenue ou non, c'est-à-dire qu'ils adhèrent au lemme : Dépendance détenu si . Ici une partition est désignée et le concept de taille de partition est utilisé - le nombre de clusters qu'elle contient. Les algorithmes qui utilisent des partitions, lorsque la dépendance est violée, ajoutent des attributs supplémentaires sur le côté gauche de la dépendance, puis la recalculent en effectuant l'opération d'intersection des partitions. Cette opération est appelée spécialisation dans les articles. Mais nous avons remarqué que les partitions des dépendances qui ne seraient conservées qu'après quelques tours de spécialisation peuvent être activement réutilisées, ce qui peut réduire considérablement le temps d'exécution des algorithmes, car l'opération d'intersection est coûteuse.

Par conséquent, nous avons proposé une heuristique basée sur l'entropie de Shannon et l'incertitude de Ginny, ainsi que notre métrique, que nous avons appelée l'entropie inverse. Il s'agit d'une légère modification de l'entropie de Shannon et augmente à mesure que le caractère unique de l'ensemble de données augmente. L’heuristique proposée est la suivante :

il est — degré d'unicité de la partition récemment calculée Et est la médiane des degrés d’unicité des attributs individuels. Les trois métriques décrites ci-dessus ont été testées en tant que métrique d'unicité. Vous pouvez également remarquer qu’il existe deux modificateurs dans l’heuristique. Le premier indique à quel point la partition actuelle est proche de la clé primaire et vous permet de mettre davantage en cache les partitions éloignées de la clé potentielle. Le deuxième modificateur vous permet de surveiller l'occupation du cache et encourage ainsi l'ajout de partitions supplémentaires au cache si de l'espace libre est disponible. La solution réussie de ce problème nous a permis d'accélérer l'algorithme PYRO de 10 à 40 %, selon l'ensemble de données. Il convient de noter que l’algorithme PYRO est le plus performant dans ce domaine.

Dans la figure ci-dessous, vous pouvez voir les résultats de l'application de l'heuristique proposée par rapport à une approche de base de mise en cache par tirage au sort. L'axe X est logarithmique.

Une autre façon de stocker les partitions

Nous avons alors proposé une manière alternative de stocker les partitions. Les partitions sont un ensemble de clusters dont chacun stocke un nombre de tuples avec des valeurs identiques pour certains attributs. Ces clusters peuvent contenir de longues séquences de numéros de tuple, par exemple si les données d'un tableau sont ordonnées. Par conséquent, nous avons proposé un schéma de compression pour stocker les partitions, à savoir le stockage par intervalles des valeurs dans des clusters de partitions :

$$display$$pi(X) = {{sous-accolade{1, 2, 3, 4, 5}_{Premier intervalle}, sous-accolade{7, 8}_{Deuxième intervalle}, 10}}\ downarrow{ Compression} \ pi(X) = {{sous-accolade{$, 1, 5}_{Premier~intervalle}, sous-accolade{7, 8}_{Seconde~intervalle}, 10}}$$affichage$$

Cette méthode a permis de réduire la consommation de mémoire lors du fonctionnement de l'algorithme TANE de 1 à 25 %. L'algorithme TANE est un algorithme classique de recherche de lois fédérales, il utilise des partitions lors de son travail. Dans le cadre de la pratique, l'algorithme TANE a été choisi, car il était beaucoup plus facile d'y implémenter le stockage par intervalles que, par exemple, dans PYRO afin d'évaluer si l'approche proposée fonctionne. Les résultats obtenus sont présentés dans la figure ci-dessous. L'axe X est logarithmique.

Conférence ADBIS-2019

Sur la base des résultats de la recherche, j'ai publié en septembre 2019 un article Mise en cache intelligente pour une découverte efficace des dépendances fonctionnelles à la 23e Conférence européenne sur les progrès des bases de données et des systèmes d'information (ADBIS-2019). Lors de la présentation, le travail a été souligné par Bernhard Thalheim, une personnalité importante dans le domaine des bases de données. Les résultats de la recherche ont constitué la base de ma thèse de maîtrise en mathématiques et mécanique à l'Université d'État de Saint-Pétersbourg, au cours de laquelle les deux approches proposées (mise en cache et compression) ont été implémentées dans les deux algorithmes : TANE et PYRO. De plus, les résultats ont montré que les approches proposées sont universelles, puisque sur les deux algorithmes, avec les deux approches, une réduction significative de la consommation mémoire a été observée, ainsi qu'une réduction significative du temps de fonctionnement des algorithmes.

Source: habr.com