高效查找数据库中的函数依赖关系

查找数据中的函数依赖关系用于数据分析的各个领域：数据库管理、数据清理、数据库逆向工程和数据探索。 我们已经发布了有关依赖项本身的信息 文章 阿纳斯塔西娅·比里洛和尼基塔·博布罗夫。 此次，计算机科学中心今年的毕业生Anastasia分享了这项工作的进展，作为她在中心答辩的研究工作的一部分。

任务选择

在CS中心学习期间，我开始深入研究数据库，即函数依赖和差异依赖的搜索。 这个主题与我在大学的课程作业主题相关，因此在学习课程作业时，我开始阅读有关数据库中各种依赖关系的文章。 我写了一篇关于这个领域的评论——这是我的第一篇评论 用品 英文版并提交给 SEIM-2017 会议。 当我发现她最终被录取时，我非常高兴，并决定深入研究这个话题。 这个概念本身并不新鲜——它早在 90 年代就开始使用，但即使现在它也被用于许多领域。

在该中心的第二个学期，我开始了一个研究项目，以改进查找函数依赖关系的算法。 她与 JetBrains Research 的圣彼得堡国立大学研究生 Nikita Bobrov 一起进行了这项研究。

搜索函数依赖关系的计算复杂度

主要问题是计算复杂性。 可能的最小和重要依赖项的数量受上述值的限制 哪里 — 表属性的数量。 算法的运行时间不仅取决于属性的数量，还取决于行的数量。 在 90 世纪 20 年代，普通台式电脑上的联邦法律搜索算法可以在几个小时内处理包含多达 200 个属性和数万行的数据集。 在多核处理器上运行的现代算法大约在同一时间检测由数百个属性（最多 XNUMX 个）和数十万行组成的数据集的依赖性。 然而，这还不够：这样的时间对于大多数实际应用程序来说是不可接受的。 因此，我们开发了加速现有算法的方法。

分区交叉点的缓存方案

在工作的第一部分中，我们为一类使用分区交集方法的算法开发了缓存方案。 属性的分区是一组列表，其中每个列表包含给定属性具有相同值的行号。 每个这样的列表称为一个簇。 许多现代算法使用分区来确定是否保留依赖关系，即它们遵循引理：依赖关系 举行如果 。 这里 指定一个分区并使用分区大小的概念——其中的簇数。 使用分区的算法，当依赖关系被违反时，会在依赖关系的左侧添加额外的属性，然后重新计算，执行分区交集的操作。 这种操作在文章中称为专业化。 但我们注意到，只有在几轮专业化之后才会保留的依赖分区可以被主动重用，这可以显着减少算法的运行时间，因为交集操作是昂贵的。

因此，我们提出了一种基于香农熵和金尼不确定性的启发式方法，以及我们的度量标准，我们将其称为逆熵。 它是香农熵的轻微修改，并随着数据集的唯一性增加而增加。 提议的启发式如下：

这是 — 最近计算的分区的唯一性程度 和 是各个属性的唯一性程度的中位数。 上述所有三个指标都作为唯一性指标进行了测试。 您还可以注意到启发式中有两个修饰符。 第一个指示当前分区与主键的接近程度，并允许您更大程度地缓存那些远离潜在键的分区。 第二个修饰符允许您监视缓存占用情况，从而鼓励在可用空间可用时向缓存添加更多分区。 这个问题的成功解决使我们能够将 PYRO 算法的速度提高 10-40%，具体取决于数据集。 值得注意的是，PYRO 算法在这方面是最成功的。

在下图中，您可以看到应用所提出的启发式方法与基本的硬币翻转缓存方法相比的结果。 X 轴是对数轴。

存储分区的另一种方法

然后我们提出了另一种存储分区的方法。 分区是一组簇，每个簇存储多个具有相同属性值的元组。 这些簇可能包含长的元组编号序列，例如，如果表中的数据是有序的。 因此，我们提出了一种存储分区的压缩方案，即分区簇中值的区间存储：

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{第一个间隔}, underbrace{7, 8}_{第二个间隔}, 10}}\ downarrow{ 压缩} \ pi(X) = {{下括号{$, 1, 5}_{第一个~间隔}，下括号{7, 8}_{第二个~间隔}, 10}}$$显示$$

该方法能够将 TANE 算法运行期间的内存消耗减少 1% 至 25%。 TANE 算法是搜索联邦法律的经典算法；它在工作过程中使用分区。 作为实践的一部分，选择了 TANE 算法，因为在其中实现区间存储比在 PYRO 中实现区间存储要容易得多，以便评估所提出的方法是否有效。 得到的结果如下图所示。 X 轴是对数轴。

会议 ADBIS-2019

根据研究结果，我于2019年XNUMX月发表了一篇文章 用于高效功能依赖性发现的智能缓存 在第 23 届欧洲数据库和信息系统进展会议 (ADBIS-2019) 上。 在演示过程中，数据库领域的重要人物 Bernhard Thalheim 注意到了这项工作。 研究结果构成了我在圣彼得堡国立大学数学和力学硕士学位论文的基础，在此期间，所提出的两种方法（缓存和压缩）都在两种算法中实现：TANE 和 PYRO。 此外，结果表明所提出的方法是通用的，因为在两种算法上，两种方法都观察到内存消耗显着减少，并且算法的运行时间显着减少。

来源： habr.com