在本文中，我们将讨论数据库中的函数依赖关系 - 它们是什么、它们在哪里使用以及存在哪些算法来查找它们。
我们将在关系数据库的上下文中考虑函数依赖性。 非常粗略地说，在此类数据库中，信息以表的形式存储。 接下来，我们使用严格关系理论中不可互换的近似概念：我们将表本身称为关系，列 - 属性（它们的集合 - 关系模式）以及属性子集上的行值集合- 一个元组。
例如，在上表中， （本森，M，M 器官) 是一个属性元组 （病人、保罗、医生）.
更正式地说，写成如下： [患者、性别、医生] = （本森，M，M 风琴）.
现在我们可以引入函数依赖（FD）的概念：
定义1。 关系 R 满足联邦法 X → Y（其中 X, Y ⊆ R）当且仅当对于任何元组 , ε R 成立：如果 [X] = [X]，那么 [Y] = [是]。 在这种情况下，我们说 X（决定因素，或定义属性集）在功能上决定 Y（依赖集）。
换句话说，联邦法律的存在 X → Y 意味着如果我们有两个元组 R 并且它们在属性上匹配 X，那么它们的属性就会一致 Y.
现在，按顺序进行。 我们来看看属性 病人 и 性别 我们想要找出它们之间是否存在依赖关系。 对于这样一组属性，可能存在以下依赖关系：
- 患者 → 性别
- 性别 → 患者
如上所述，为了保持第一个依赖关系，每个唯一的列值 病人 只有一列值必须匹配 性别。 对于示例表来说，情况确实如此。 但是，反之则不行，即不满足第二个依赖关系，属性 性别 不是决定因素 病人。 类似地，如果我们取依赖关系 医生→病人，您可以看到它被违反了，因为该值 知更鸟 该属性有几种不同的含义 - 埃利斯和格雷厄姆.
因此，函数依赖性使得确定表属性集之间的现有关系成为可能。 从这里开始，我们将考虑最有趣的联系，或者更确切地说，这样的联系 X → Y它们是什么：
- 非平凡的，即依赖项的右侧不是左侧的子集 (Y̸⊆X);
- 最小，即不存在这种依赖性 Z → Y该 Z ⊂ X.
到目前为止考虑的依赖关系是严格的，也就是说，它们没有规定表上的任何违规，但除此之外，还存在允许元组的值之间存在一些不一致的依赖关系。 这种依赖关系被放置在一个单独的类中，称为近似，并且允许在一定数量的元组中违反。 该量由最大误差指标 emax 调节。 例如，错误率 = 0.01 可能意味着 1% 的可用元组对所考虑的属性集的依赖性可能会被违反。 也就是说，对于 1000 条记录，最多有 10 个元组可能违反联邦法律。 我们将考虑一个稍微不同的度量，基于被比较的元组的成对不同值。 为了成瘾 X → Y 关于态度 r 它被认为是这样的：
我们来计算一下误差 医生→病人 从上面的例子来看。 我们有两个元组，它们的属性值不同 病人，但重合于 医生: [医生、病人] = (罗宾·埃利斯）和 [医生、病人] = (罗宾·格雷厄姆）。 根据错误的定义，我们必须考虑所有冲突对，这意味着将有两个：（, ) 及其逆 (, ）。 我们将其代入公式可得：
现在让我们尝试回答这个问题：“这一切都是为了什么呢？” 事实上，联邦法律有所不同。 第一类是管理员在数据库设计阶段确定的依赖关系。 它们通常数量较少、严格，主要应用是数据规范化和关系模式设计。
第二种类型是依赖关系，它代表“隐藏”数据和属性之间以前未知的关系。 也就是说，在设计时没有考虑到此类依赖关系，而是针对现有数据集找到了这些依赖关系，以便稍后根据许多已确定的联邦法律，可以得出有关存储信息的任何结论。 我们所处理的正是这些依赖关系。 它们是由整个数据挖掘领域以及基于其基础的各种搜索技术和算法来处理的。 让我们弄清楚在任何数据中找到的函数依赖关系（精确或近似）如何有用。
如今，依赖关系的主要应用之一是数据清理。 它涉及开发识别“脏数据”然后纠正它的流程。 “脏数据”的突出例子是重复、数据错误或拼写错误、缺失值、过时的数据、多余的空格等。
数据错误示例：
数据重复的示例：
例如，我们有一个表格和一组必须执行的联邦法律。 在这种情况下，数据清理涉及更改数据以使联邦法律变得正确。 在这种情况下，修改的数量应该是最少的（这个过程有它自己的算法，我们在本文中不会重点讨论）。 下面是此类数据转换的示例。 左边是原始关系，其中显然没有满足必要的 FL（违反其中一个 FL 的示例以红色突出显示）。 右侧是更新后的关系，绿色单元格显示更改后的值。 在此过程之后，开始维护必要的依赖关系。
另一个流行的应用是数据库设计。 这里值得回顾一下范式和规范化。 规范化是使关系符合一组特定要求的过程，每个要求都由范式以自己的方式定义。 我们不会描述各种范式的要求（任何一本针对初学者的数据库课程的书中都会这样做），但我们只会注意到它们中的每一个都以自己的方式使用函数依赖的概念。 毕竟，FL 本质上是设计数据库时考虑的完整性约束（在此任务的上下文中，FL 有时称为超级密钥）。
让我们考虑一下它们在下图中的四种范式的应用。 回想一下，Boyce-Codd 范式比第三种形式更严格，但比第四种形式不太严格。 我们现在不考虑后者，因为它的表述需要理解多值依赖关系，而这对我们在本文中并不感兴趣。
依赖性应用的另一个领域是在构建朴素贝叶斯分类器、识别重要特征以及重新参数化回归模型等任务中降低特征空间的维数。 在原来的文章中，这个任务被称为冗余和特征相关性的确定[5, 6]，并且通过积极使用数据库概念来解决。 随着此类工作的出现，我们可以说今天需要一种解决方案，使我们能够将上述优化问题的数据库、分析和实施结合到一个工具中[7]。
有许多算法（现代的和不太现代的）用于在数据集中搜索联邦法律。这些算法可以分为三组：
- 使用代数格遍历的算法（格遍历算法）
- 基于搜索一致值的算法（差异集算法和一致集算法）
- 基于成对比较的算法（依赖归纳算法）
下表列出了每种算法的简要描述：
您可以阅读有关此分类的更多信息 [4]。 以下是每种类型的算法示例：
目前，新算法的出现结合了多种方法来查找函数依赖关系。 此类算法的示例包括 Pyro [2] 和 HyFD [3]。 本系列的以下文章将对其工作进行分析。 在本文中，我们将仅研究理解依赖性检测技术所需的基本概念和引理。
让我们从第二类算法中使用的一个简单的差异集和一致集开始。 差异集是一组不具有相同值的元组，而一致集则相反，是具有相同值的元组。 值得注意的是，在这种情况下我们只考虑依赖的左侧。
上面遇到的另一个重要概念是代数格。 由于许多现代算法都基于这个概念，因此我们需要了解它是什么。
为了引入格的概念，需要定义一个偏序集（或称偏序集，缩写为偏序集）。
定义2。 如果对于所有 a、b、c ∈ S 满足以下属性，则称集合 S 是按二元关系 ⩽ 部分排序的：
- 自反性，即 a ⩽ a
- 反对称性，即如果 a ⩽ b 且 b ⩽ a，则 a = b
- 传递性，即，对于 a ⩽ b 和 b ⩽ c，可得出 a ⩽ c
这样的关系称为（松散）偏序关系，集合本身称为偏序集合。 正式符号：⟨S，⩽⟩。
作为最简单的偏序集合的例子，我们可以采用所有自然数 N 组成的集合，并具有通常的顺序关系 ⩽。 很容易验证是否满足所有必要的公理。
一个更有意义的例子。 考虑所有子集 {1, 2, 3} 的集合，按包含关系 ⊆ 排序。 事实上，这个关系满足所有偏序条件，因此 ⟨P ({1, 2, 3}), ⊆⟩ 是一个偏序集。 下图展示了这个集合的结构：如果一个元素可以通过指向另一个元素的箭头到达，那么它们就存在顺序关系。
我们需要数学领域的两个更简单的定义——上确界和下确界。
定义3。 令 ⟨S, ⩽⟩ 为偏序集，A ⊆ S。A 的上界是元素 u ∈ S，使得 ∀x ∈ S: x ⩽ u。 设U为S的所有上界的集合。如果U中存在最小元素，则称为上界，记为sup A。
类似地引入了精确下界的概念。
定义4。 令 ⟨S, ⩽⟩ 为偏序集，A ⊆ S。A 的下确界是一个元素 l ∈ S，使得 ∀x ∈ S: l ⩽ x。 设L是S的所有下界的集合。如果L中存在最大元素，则称为下确界，记为inf A。
以上面的偏序集合 ⟨P ({1, 2, 3}), ⊆⟩ 为例，并找到其中的上确界和下确界：
现在我们可以制定代数格的定义。
定义5。 令 ⟨P,⩽⟩ 为偏序集，使得每个二元素子集都有上界和下界。 则 P 称为代数格。 在这种情况下，sup{x, y} 写为 x ∨ y，inf {x, y} 写为 x ∧ y。
让我们检查一下我们的工作示例 ⟨P ({1, 2, 3}), ⊆⟩ 是一个格子。 事实上，对于任何 a，b ∈ P ({1, 2, 3})，a∨b = a∪b，且 a∧b = a∩b。 例如，考虑集合 {1, 2} 和 {1, 3} 并找到它们的下确界和上界。 如果我们将它们相交，我们将得到集合 {1}，这将是下确界。 我们通过将它们组合起来得到至上值 - {1, 2, 3}。
在识别物理问题的算法中，搜索空间通常以格的形式表示，其中一个元素的集合（读取搜索格的第一级，其中依赖项的左侧由一个属性组成）代表每个属性的原始关系。
首先，我们考虑 ∅ → 形式的依赖关系 单一属性。 此步骤允许您确定哪些属性是主键（对于此类属性，没有决定因素，因此左侧为空）。 此外，此类算法沿着晶格向上移动。 值得注意的是，并不是可以遍历整个格子，也就是说，如果将所需的左侧最大尺寸传递给输入，那么算法将不会超出具有该尺寸的级别。
下图显示了如何使用代数格来解决寻找 FZ 的问题。 这里每条边（X、XY) 代表依赖关系 X → Y。 比如我们过了第一关，知道瘾维持了 甲→乙 （我们将其显示为顶点之间的绿色连接 A и B）。 这意味着进一步，当我们沿着格子向上移动时，我们可能不会检查依赖关系 A、C→B，因为它将不再是最小的。 同样，如果依赖关系被保留，我们也不会检查它 C→B.
此外，作为一项规则，所有用于搜索联邦法律的现代算法都使用诸如分区之类的数据结构（在原始源中 - 剥离分区 [1]）。 分区的正式定义如下：
定义6。 令 X ⊆ R 为关系 r 的一组属性。 簇是 r 中具有相同 X 值的元组索引的集合，即 c(t) = {i|ti[X] = t[X]}。 分区是一组簇，不包括单位长度的簇：
简单来说，就是属性的分区 X 是一组列表，其中每个列表包含具有相同值的行号 X。 在现代文献中，表示分区的结构称为位置列表索引（PLI）。 出于 PLI 压缩目的，排除了单位长度簇，因为它们是仅包含具有唯一值且始终易于识别的记录号的簇。
让我们看一个例子。 让我们返回到包含患者的同一张表并为列构建分区 病人 и 性别 （左侧出现了一个新列，其中标记了表格行号）：
此外，根据定义，列的分区 病人 实际上是空的，因为单个簇被排除在分区之外。
分区可以通过几个属性来获得。 有两种方法可以做到这一点：通过遍历表，一次性使用所有必要的属性构建分区，或者使用属性子集进行分区交集操作来构建分区。 联邦法律搜索算法使用第二种选择。
简而言之，例如按列进行分区 美国广播公司，你可以将分区 AC и B （或任何其他不相交子集的集合）并将它们彼此相交。 两个分区的交集操作选择两个分区共有的最大长度的簇。
让我们看一个例子：
在第一种情况下，我们收到一个空分区。 如果仔细观察该表，那么确实，这两个属性没有相同的值。 如果我们稍微修改一下表格（右侧的情况），我们就已经得到了一个非空交集。 而且，第 1 行和第 2 行实际上包含相同的属性值 性别 и 医生.
接下来我们需要一个分区大小这样的概念。 正式：
简单地说，分区大小是分区中包含的簇的数量（请记住，分区中不包含单个簇！）：
现在我们可以定义关键引理之一，对于给定的分区，它允许我们确定是否保留依赖关系：
引理1。 依赖关系 A, B → C 成立当且仅当
根据引理，要确定依赖关系是否成立，必须执行四个步骤：
- 计算依赖项左侧的分区
- 计算依赖项右侧的分区
- 计算第一步和第二步的乘积
- 比较第一步和第三步得到的分区大小
下面是根据此引理检查依赖性是否成立的示例：
在本文中，我们研究了函数依赖、近似函数依赖等概念，研究了它们的用途，以及存在哪些搜索物理函数的算法。 我们还详细研究了现代算法中用于搜索联邦法律的基本但重要的概念。
参考：
- Huhtala Y.等人。 TANE：一种用于发现函数和近似依赖关系的有效算法//计算机杂志。 – 1999. – T.42. – 否。 2. – 第 100-111 页。
- Kruse S.、Naumann F. 近似依赖关系的高效发现 // VLDB 捐赠基金的会议记录。 – 2018. – T.11. – 否。 7. – 第 759-772 页。
- Papenbrock T.、Naumann F. 函数依赖发现的混合方法//2016 年国际数据管理会议论文集。 – ACM，2016 年。 – 第 821-833 页。
- Papenbrock T.等人。 函数依赖发现：七种算法的实验评估 //VLDB 捐赠基金论文集。 – 2015. – T.8. – 否。 10. – 第 1082-1093XNUMX 页。
- 库马尔·A.等人。 加入还是不加入？：在选择特征之前再三考虑加入//2016 年国际数据管理会议论文集。 – ACM，2016。 – 第 19-34 页。
- 阿博·哈米斯·M.等人。 稀疏张量的数据库内学习 //第 37 届 ACM SIGMOD-SIGACT-SIGAI 数据库系统原理研讨会论文集。 – ACM，2018。 – 第 325-340 页。
- 海勒斯坦 JM 等人。 MADlib 分析库：或 MAD 技能、SQL //VLDB 捐赠基金的会议记录。 – 2012. – T.5. – 否。 12. – 第 1700-1711 页。
- Qin C.，Rusu F。万亿级分布式梯度下降优化的推测近似//第四届云数据分析研讨会论文集。 – ACM，2015。 – 第 1 页。
- 孟X.等。 Mllib：apache Spark 中的机器学习 //机器学习研究杂志。 – 2016 年。 – T.17。 – 否。 1. – 第 1235-1241 页。
文章作者： ，研究员 , и ，研究员
来源： habr.com