英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料
FastMFD: 一种基于 Spark 的高效、快速的大规模分布式最小函数依赖挖掘算法
摘要
最小函数依赖是关系数据库中的一个重要关系。它可以描述关系数据库中复杂和不规则属性之间的某些特殊关系。从关系数据库中提取最小功能依赖（MFD）是一种重要的数据库分析技术。然而，随着数据量的日益增长，即便最高效的单机算法在关系属性的数量增长上是呈指数级的。在单机上挖掘发现 MFD 是困难且低效的，只能应用于小型集中式数据集。从大数据中，尤其是大规模分布式存储的数据集中发现 MFD 是极具挑战性的。 Apache Spark 是一个应用于大数据处理的分析引擎; 我们提出了一种基于 Spark 实现的新算法FastMFD，用于并行发现大规模分布式数据集中的所有 MFD。 FastMFD 使用 RDD 框架和DataFrame 框架来存储和处理分布式数据集。 FastMFD 删除等效属性。 FastMFD 还提供了用于搜索和修剪的双向搜索算法。通过在真实数据集上进行算法实验，本研究提出的算法比现有的函数依赖发现方法更高效、更快。
关键词：最小函数依赖、大数据、并行编程、Spark
1 导论
函数依赖是数据库中属性之间的依赖关系：函数依赖表明一个属性的值由一些其他属性的值唯一决定的。例如，设 为模式 上的一个关系实例， 和 是 的子集。只有当 中任意两个元组，有 ，使得 ，关系 满足函数依赖 。设 为 的一个子集，如果 不符合函数依赖，那么 是一个最小函数依赖。
1.1 目地
MFD在关系理论和关系数据库设计中发挥着重要作用。当前的研究主要是从集中式数据库中发现FD; 通常，集中式数据库的规模很小。然而，随着大数据时代的到来，我们无法将所有数据存储在单个集中式数据库中并发现FD，大规模数据是分布式的，我们无法将它们集中存储在一起。而且，关系通常是分散的，并且分布在不同的节点[10]。分布式计算通过在多计算节点之间合理分配计算量为分析和处理此类大数据创造了前提条件[12]。在本文中，我们解决了在大规模分布式大数据中发现最小功能依赖性的问题。
给定关系模式 和模式 的实例 ，我们希望发现保留 的所有MFD。 MFD是FD的子集; 如果我们获得MFD，我们可以轻松地将MFD扩展到FD。大多数方法都是为集中式数据库设计的，例如TANE [6]和FUN [9]; 它们可用于有效地在集中式数据库中发现FD。
1.2 相关工作
已经发明的许多用于发现函数依赖的算法，其中大部分都应用于集中式数据库。 我们可以将这些算法分为两类，一类是自顶向下搜索候选 FD，另一类是自底向上搜索候选依赖。 TANE [6]和FUN [9]自顶向下搜索候选依赖; 他们以广度优先的方式遍历搜索空间，逐层检查候选依赖的是否满足。 验证候选依赖的满足性，通过满足条件的FD在低一层修剪候选依赖以减少搜索空间，这些算法在水平方向上工作。 这些算法自顶向下搜索候选依赖。 FastFDs [13]和Dep-Miner [8]自底向上搜索候选依赖，这些算法以深度优先的方式遍历搜索空间，它以LHS的单个属性开始并逐渐附加更多属性，直到找到一个正确的RHS。 本文[15]提供了一个从大规模分布式数据集中挖掘FD的框架; 该框架独立地发现FD并在每个站点修剪候选依赖，然后将所有数据发送到中心站点并使用算法来集中式数据库来发现FD。 该方法从发布的数据中发现FD; 但是，由于发现FD的主要工作是在中心站点完成的，因此该方法效率低，无法应用于大数据。 FMFD [7]也提供了一种从分布式数据中发现FD的新方法; 它使用公共属性将数据划分到不同的分区，并将它们发送到不同的站点。 在每个站点，它可以独立且正确地发现FD。 该方法可以从大型分布式数据中发现FD; 但是，当属性数量很大时，此方法太慢而无法找到所有FD。
FD_Mine [14]提出了一种在数据中发现函数依赖的新方法。 它使用等价且具有比TANE更好的性能。 但是，它也不能应用于大规模和分布式数据集。 本文[2]提供了一种使用MapReduce [5]模型提取大型数据集中的函数依赖的方法。 MapReduce为大规模数据处理提供了一种支持。 这是一种处理大规模数据的很好方法，因此在论文中，我们介绍了一种基于Apache Spark的算法[11]，Apache Spark是一种内存中的集群计算引擎，为各种工作负载提供支持，包括批处理， 流式传输和迭代计算[3]。 与Hadoop不同，它将中间结果保存在内存而不是HDFS中，并且具有比Hadoop MapReduce更好的性能。
1.3 问题
然而，当这些方法应用于分布式数据集时，通常结果是不准确的。 例 1 图1给出了关系， 水平划分成两个部分（图1b），每个与其他部分分开。 ID是的键，，， 是 的属性。 我们可以简单地使用集中式数据库的算法来发现 在图1中的和中都是MFD。然而，这个结论在中是不正确的。因此这些现有的集中式数据库算法不能直接应用在分布式数据，除非当我们将所有数据发送到单个站点时，但这会占用太多的网络带宽，此外通常没有足够内存来存储。 本文将介绍一种基于Apache Spark [11]的新算法FastMFD，以发现分布式数据中的所有MFD。
1.4 目地和主要贡献
本文提供了一种新的算法 FastMFD，用于从分布式数据中发现MFD。 本研究的主要贡献如下：
- 一种新的搜索和修剪策略，FastMFD，遍历搜索空间并修剪候选 MFD，不仅是自顶向下，而且结合了自底向上；
- FastMFD使用两个属性的等价来减少属性的数量，这可以减少大量的候选MFD；
- FastMFD基于Spark; 它使用RDD和DataFrame来存储分布式数据并验证不同环境中的候选MFD；
- FastMFD提供分布式数据的算法和中心化数据的算法，以验证候选依赖；
本文使用实际数据对FastMFD进行实验，实验结果表明FastMFD具有良好的可扩展性，在减少MFD发现时间方面表现良好。 确切的算法在Sect 3 中给出，实验结果见Sect 4。
2. 预备知识
使用Spark平台的RDD和DataFrame框架，FastMFD算法在时间花费上有着显著的效果。 相应地，我们应该了解Spark相关知识。
2.1 Spark
Spark是一个Apache项目，被标记为“像闪电一样的快速集群计算”。 它拥有一个繁荣的开源社区，是目前最活跃的Apache项目。 Spark提供了更快，更通用的数据处理平台。 Spark提供了一个全面统一的框架，用于管理具有不同属性（文本数据，图表数据等）的数据集和数据源（批量数据或实时数据）的大数据处理需求。 Spark具有运行速度快，可用性好，通用性强，运行无处不在的特点。
- 运行速度
- Spark有一个DAG执行引擎，支持内存中数据的迭代计算。 官方数据显示，如果数据是由磁盘读取的，速度是Hadoop MapReduce的10倍以上，如果从内存中读取数据，速度可高达100倍。
- 可用性
- Spark不仅支持Scala编写应用程序，还支持Java和Python语言，特别是Scala是一种高效且可扩展的语言，可以使用简单的代码处理复杂的处理。
- 强适用性
- Spark生态系统Berkeley数据堆栈（BDAS）包含Spark Core，Spark SQL，Spark Streaming，MLLib和GraphX等组件，这些组件是Spark Core内存计算框架，SparkStreaming应用程序，Spark SQL实时处理即席查询 ，MLlib或MLbase机器学习和GraphX地图，它们由AMP实验室提供，能够无缝集成并提供一站式解决方案平台。
- 跨平台
- Spark具有很强的适应性。 它可以读取HDFS，Cassandra，HBase，S3和Techyon来读取和写入持久层的本机数据。 它可以使用Mesos，YARN和独立的Standalone作为资源管理器来安排作业，完成Spark应用程序的计算。
2.2 RDD
Spark引入了一个名为Resilient Distributed Dataset（RDD）的概念。 它是一个不可变的，容错的和分布式的对象集。 我们可以平行操作这套装置。 RDD可以包含在加载外部数据集或从驱动器应用程序分发集合时创建的任何类型的对象。 RDD支持两种类型的操作：
- Transformation （如映射，过滤，连接，联合等）。 它对RDD执行操作，然后创建新的RDD以保存结果；
- Action （例如合并，计数，优先等），它在RDD上执行某种计算，并返回结果。
在Spark中，转换是“惰性的”，也就是说，它们不会立即计算结果。 相反，它们只是“记住”要执行的操作以及要操作的数据集（例如文件）。 只有在调用行为时，才会真正计算转换，并将结果返回给驱动程序。 这种设计使Spark更有效率。 例如，如果需要通过各种方式转换大文件并将文件传递给第一个行为，则Spark将仅处理文件的第一行内容并返回结果而不处理整个文件。 默认情况下，当您对转换后的RDD运行操作时，可能会重新计算RDD。 但是，您还可以使用持久性或缓存方法在内存中保持RDD持久性，以便Spark将这些元素保留在群集上。 当您下次查询时，查询速度会快得多。
2.3 DataFrame
DataFrame具有数据的结构信息，即模式。 DataFrame是分布式Row对象的集合。 DataFrame是一个基于RDD的分布式数据集，类似于传统数据库中的二维表。 DataFrame和RDD之间的主要区别在于前者具有模式元信息，即由二维表数据集表示的每一列DataFrame都具有名称和类型。 这使Spark SQL能够深入了解更多结构信息，以便隐藏在DataFrame后面的数据源和作用于DataFrame的转换可以针对显着提高运行时效率的最终目标。 DataFrame具有以下功能：
- KB 到 PB 级别的数据集支持；
- 支持多种数据格式和多种存储系统；
- Spark SQL的Catalyst优化器对代码优化和生成；
- Spark无缝集成所有大数据工具和基础平台；
3 FastMFD 算法
这一小节详细介绍了 FastMFD 算法
3.1 函数依赖的属性
本节将讨论提议工作所需的概念基础。设 为一个关系模式， 作为 的一个实例。定义了一个属性集合：，的属性集合表示为。表示单个属性，而 表示属性集合。 中集合的基数由表示，它给出了关系中的不同值的数量。代表着中属性的个数，设 和 。
本文中，只发现非平凡的函数依赖，即满足，并且。
定义 1 设 为两组属性，和之间的函数依赖可以表示为 ，只有当中有：，如果 ，则 时；
定义 2 设 为两组属性，只有存在: ，如果 ，且$Z ot ightarrow Y$时，是最小函数依赖；
定义 3 如果 有个属性，则非平凡候选函数依赖的总数为 ；
定义 4 设为一个属性集合， 表示集合中 的一个划分；
定义 5 只有 时，满足函数依赖；
定义1 定义什么是FD，定义2定义什么是MFD。 此外，定义3计算候选MFD的数量。 在本文中，我们只发现其右侧（RHS）只有一个属性的最小函数依赖。 这不会导致缺少MFD，因为我们可以轻松地将几个具有相同左侧（LHS）的MFD组合到一个其RHS具有多个属性的MFD中。
3.1.1 移除等价依赖和等值属性
定义 6 设 为两组属性，如果有 和，则和可以看作是等价属性，表示为；
定义 7 设为中一个属性，如果下所有值都相等，则说明是一个等值属性；
在FastMFD逐级搜索所有候选依赖之前，FastMFD首先找到等效属性。 根据定义6和7，如果我们找到一对等价属性或相等属性，我们可以从属性集中删除其中一个，并在FastMFD发现除了它之外的所有MFD时将其恢复。
例 2 设 ，如果 ，从 删除，然后设，从挖掘MFDs。假使发现
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[441152]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
