毕业设计（论文）-Spark框架下语义数据并行推理方法研究.docx

Spark框架下语义数据并行推理方法研究1绪论1.1 研究背景与意义随着语义万维网的快速发展与应用，Web中现已经存在大规模的本体数据，并且在逐年增长，到2011年9月统计RDF数据集总数已经超过了310亿条1，另外，以链接开放数据（Linked Open Data, LOD）工程为例2，如图1所示，LOD连接数据集把不同领域的数据集链接组成一个巨大的数据集。截止到2017 年2月LOD 工程中一共包含2973个RDF开放数据集，总共包含的三元组个数为1492亿个http:/stats.lod2.eu/。比较2011年的295 个RDF 开放数据集、310 亿个RDF 三元组的规模扩大10倍多，并且每时每刻都在爆发式增长，因此从而如何通过对大规模语义信息进行并行推理高效的发现海量语义信息中的隐藏信息是现阶段研究十分重要的问题。然而，传统的语义Web推理工具都是在单机环境下设计实现使用，这些传统的推理系统在对海量本体数据进行处理时难免会遇到在计算性能上和存储空间上等一系列的问题，所以，研究寻找在云环境下海量语义数据并行化高效推理机制与方法是本文中核心问题。这一段除了用图表示外，还可以补充一个比较表，就更清晰。图1-1 LOD链接数据集RDF数据集推理所关注的是主要目标是如何借助自动推理机从给定的推导出一些结论，从而使隐含的语义数据推导出来3。对隐含的语义数据的支持是RDF与其他数据类型的本质区别，也是语义网发展的重要推动力4。目前，Hadoop是一个开源的分布式框架，是Apache下的一个开源项目。Hadoop运行可以在上千上万个普通机器的节点组成的集群上，通过分布式的计算模型和存储模型来处理大数据集，Hadoop已经成为大数据存储和并行处理的主流平台。Spark目前也是Apache下的一个大型开源项目，Spark大数据处理模型可以运行在Hadoop平台下，Spark采用函数式编程语言Scala34实现，同时还支持Python，Java开发语言，Spark计算模型克服了在迭代式计算和交互式计算中的不足5。Spark处理模型是基于MapReduce计算框架实现的分布式计算，拥有MapReduce所具有的可扩展性、容错性、兼容性优点；但与MapReduce相比较不同的是Spark处理模型中间输出结果可以保存在内存中，从而不再需要再反复读写HDFS，使得并行处理效率比在MapReduce平台下提高了100倍5,6。因此，本文论文研究方向实现在Hadoop环境下基于Spark下大规模RDF数据的高效推理，提出一种高效的基于Spark的RDFS的推理算法。论文本文的研究意义在于，首先在Hadoop环境下基于Spark构建海量数据并行推理框架，并搭建相关平台。其次，研究基于Spark框架语义数据并行推理策略并研究设计基于Spark框架的并行推理算法，最后通过实验分析与urbian文章中提出的方法进行对比，得出该并行推理算法推理的准确性和效率。1.2 国内外研究现状现如今，为了实现高效率、易扩展的大规模语义数据的推理机制，有学者对传统的推理算法从不同方面进行改动，目前为止，较为新颖受人认可的推理方式为结合Spark技术基于RDFS、OWL推理规则提出推理算法。1.2.1 Hadoop平台及Spark、HDFS相关技术研究现状和发展动态及相关技术近年来，基于HDFS分布式文件系统、MapReduce分布式计算模型和HBase分布式数据库模型实现的开源 Hadoop 平台11。其具备的高效率、易扩展的大规模数据存储和计算能力，及高容错、支持不同环境、低成本等特性，已经成为云计算研究领域中较为广泛使用的数据密集型计算和存储模型， Hadoop 已经成为对大数据处理的传统平台12。随着技术的发展，前两年在Hadoop中使用最广泛的是MapReduce分布式处理模型，但是它最大的弊端在于，存储数据需要反复访问HDFS文件系统，不断的进行I/O操作，仅仅在这个存储层面上分析就降低了平台处理效率。Spark是现如今主流的云计算处理平台，它是由UC Berkeley AMPLab在2009年发起的，然后被Apache软件基金会接管的类似于MapReduce的分布式并行计算模型，是目前大规模数据下使用较为广泛的开源项目之一。其最大的区别在于，Spark是针对MapReduce在迭代式机器学习算法和交互式数据挖掘等应用方面的低效率，而提出的新的基于内存计算框架，既保留了MapReduce的可扩展性、容错性、兼容性，又弥补了MapReduce在这些应用上的不足，丙炔Spark采用基于内存的集群计算，所以Spark在这些应用上比MapReduce快100倍5,6。Spark采用新型函数式编程语言Scala实现，除此之外也支持JAVA、Python等语言，还支持对不同数据源的访问，如HDFS、Amazon S3。Spark核心在与将分布式内存抽象成弹性分布式数据集(Resilient Distributed Datasets。RDD)35。RDD支持基于工作集的应用，同时具有数据流模型的特点：自动容错、位置感知调度和可伸缩性。RDD允许用户在执行不同操作时可以将中间结果缓存在内存中。以便后续的操作能够重用，这极大地提升了计算速度，大量的减少了对磁盘的频繁访问。另外，Spark既可以作为一个原生生态系统单独构建分布式处理框架也可以搭建在Hadoop平台之下。自己总结特点，用（1）（2）（3）列出 Spark计算模型主要由四部分组成：Spark SQL、Spark Streaming、MLlib、GraphX，Spark组成结构如图1-2所示。图2 Spark组成结构以下是对Spark四个组成部分的具体介绍：（1）Spark SQL：Spark SQL在Spark程序中提供查询结构化数据的工具，既可以SQL语言也可以使用其他支持的数据形式的API(JSON文件、parquet文件、Apache Hive等)，同时支持Scala，Java，Python语言。（2）Spark Streaming：Spark中提供处理相关流式应用的库。结合了交互式查询和批处理式查询，方便重用批处理的代码和历史数据。同样的，Spark Streaming也可访问不同的数据源，能够从HDFS、Flume、Kafka中读取数据。（3）MLlib：Spark中提供的机器学习库，包含了常用的机器学习算法。相关算法包括了K-means、naive Bayes、logistics regression等算法。（4）GraphX：Spark中处理图的框架，实现相关的图形算法。正因为上述的优点，Spark处理框架已经成为大数据的处理计算首选平台与在大数据应用上的发展趋势5,6。1.2.2 语义数据推理机制的国内外发展现状目前，对语义数据推理根据所采用的推理原理不同，在大体方向上将推理算法分为两种基本类型：前向链推理和后向链推理。前向链推理：前向链推理是由数据驱动的推理方式，当语义数据存入系统时被触发推理，通过不断地应用推理规则进行迭代推理，从而得到新的三元组。并且，原三元组和推理得到的三元组共同都保存在RDF存储系统中。后向链推理：后向链推理是由目标驱动推理方式，推理发生在查询时执行，从查询目标出发，利用推理规则不断地进行目标消解来完成推理，从规则的结论出发，反向推理把得出结论的相关规则在作为目标不断地反复迭代，以推理得出已知数据所能涵盖的全部解空间。当前，研究较为广泛的是前向链推理，语义数据的前向链推理方面有很多相关研究，并且在语义数据的前向链并行推理有较大的发展，可以将相关研究大致地分为以下两类：传统单机环境下语义数据推理方法、Hadoop平台下基于MapReduce分布式并行推理方法以及基于Spark计算模型的分布式并行推理方式，现总结如下。（1）传统单机环境下语义数据推理方法传统单机环境下的语义数据推理方法是语义数据推理发展的开端，单机环境下的推理对如今云环境下的分布式并行推理的研究有着重要的启发意义，是语义推理的开端，该推理方式主要代表性研究由下表所示。表1-1 传统单机环境下语义推理方法三线表表要精简，一目了然。可以在表下方在详细阐述优点和缺点推理方式算法简介以及优点缺点基于单节点传统的单机推理系统有Jena21、Pellet22、Sesame23等。这些基于单节点的系统为语义数据推理打下了技术基础单节点运行环境上的限制，在可扩展性和计算性能方面存在不足，现如今，难以满足处理海量语义数据的要求。基于关系型数据库 24推理方法采用关系数据库作为RDF存储系统，结合现有的单机推理系统对语义数据进行推理，满足了语义信息的存储和查询要求。与单机推理系统相比，这类系统是在存储方式上进行了改进。推理速度和可扩展性方面也存在不足。基于分布式哈希技术Kaoudi25采用了基于分布式哈希技术的并行推理方法。该方法将数据存储在分布式哈希表中，推理过程需不断访问哈希表以避免数据重复。主要问题是负载不均衡，因此在处理大规模数据的场景下，在性能上会产生较大的限制。基于数据划分对语义数据规则进行划分来实现语义数据并行化推理，有友MacCartney团队26提出了一种基于图划分的一阶逻辑推理算法;Soma和Prasanna27 团队提出了一种通过数据划分来实现并行推理的技术， Weaver与HendIer28提出了一种数据划分模型，在该模型下推理任务可被分解为相互独立的多个并行子任务，各节点对本地的数据应用所有的推理规则，直到不再有新的数据产生，最后通过合并各节点局部结果得到全局解。Soma提出方法并没有提供大数据集下的实验结果。Weaver提出方法没有检测和过滤重复数据，另外该方案在每个数据单元上使用传统的推理机，计算效率较低。基于P2P网络的推理方法基于P2P网络的并行化推理方法Marvin29，该方法以其特定的前向推理方式，推理规则以逐步接待的方式执行直到不会再推理产生新隐含数据为止。整个推理过程也需要多次数据通信30，网络数据通信对计算的效率造成了很大的影响。(2) Hadoop平台下并行推理方法Hadoop平台下基于MapReduce计算框架的并行推理方法在底层采用Hadoop MapReduce平台和处理框架，主要结合数据划分方法来实现大规模语义数据的推理。Urbani31提出的基于MapReduce利用RDFS规则的分布式并行推理算法。该推理算法主要通过分析比较十三条RDFS推理规则之间的依赖关系，分析出得出RDFS规则之间的依赖关系，将需要通过未知次数的迭代工作才能完成的推理工作简化到只需要四次MapReduce作业，就可完成推理，从而提高了推理效率。但是，在该推理方法中的四个推理步骤，是使用相同的数据划分方案，采用不同的是推理计算方法，这使得有大量的数据重复传输与中间输出结果得不到利用，以及大部分的运行时间都使用在数据的传输、磁盘的输入输出上，从而使得性能上有很大的限制。Haijiang32团队提出的基于MapReduce的分布式规则执行机制，但是在该文献中没有给出相关实验室数据。Ha33团队针对RDFS推理规则中的特定的部分具有传递性质关系的规则提出了特定的解决方案。这些研究都在为基于MapReduce在语义推理领域做出了重要贡献。（3）基于Spark处理平台的并行推理方法。现如今，随着Spark分布式计算平台的提出与发展，Spark处理框架比MapReduce在迭代处理，交互式数据分析上的性能高出很多，所以现在基于Spark计算模型的语义并行推理算法已经成为国内外研究趋势，Cichlid推理机制，分别通过对RDFS、OWL推理的规则的划分分类，并在搭建Spark分布式计算平台，在很大程度上提高了语义数据推理的效率。但是，该种方法在数据划分上还是采用与MapReduce计算框架中同样的划分方式，在数据划分方面还是采用比较保守的方法。Je-Min Kim提出了在Spark框架下基于OWL推理规则的推理方式，通过对OWL推理规则相同特质的规则组合，然后在Spark中不同的RDD中进行执行推理。但是，该文忽略了对推理得出的重复数据消除的步骤，由于OWL推理规则本身的特征，通过推理会产生大量重复或者无用的数据，所以这些冗余数据对存储来说是没有意义的。综上所述，在国内外现有的基于MapReduce的计算模型与基于Spark框架下的采用RDFS、OWL推理规则划分的前向链式推理方法进行改进，提出高性能、可扩展并且在Spark分布式并行计算框架下实现的推理方法是十分迫切的需求。1.3 研究目标及内容Spark框架下语义数据并行推理系统结构，分为三部分，数据源的流入，RDFS三元组的存储，以及基于Spark计算模型下的RDFS推理机制以及OWL推理机制，具体如图3所示：这个图缺少一个输出，即通过推理后得到什么？另外这个系统结构图扩充后放入第三章比较合适。图3 系统结构图本文主要研究Spark框架下语义数据并行推理方法，在国内外已有的研究基础上进一步优化，提高对大规模语义数据推理的效率、以及可扩展性。由图三所示，研究目标有以下三点：（1）实现语义数据划分方法。语义数据的划分为语义推理的基础，是实现大规模语义数据的推理机制的保证。（2）优化实现Spark框架下基于RDFS规则的推理算法，通过在现已有的前向链推理算法的基础上，对算法进行优化，减少推理步骤、降低数据吞吐量等方式，缩短推理时间，提高推理效率。（3）优化实现Spark框架下基于OWL规则的推理算法，在现有的OWL推理算法的基础上进行优化，将OWL推理规则的做出更为合理的划分，从而提高推理效率。根据上述三点研究目标，本文的研究内容如下：（1）研究大规模语义数据划分方法。对海量语义数据首先进行三元组数据划分，将三元组划分为模式三元组和实例三元组，再分别把模式三元组直接存储到各个节点的内存中，把实例三元组存储到Spark环境集群下的HBase中。（2）研究RDFS规则推理，优化基于RDFS规则的推理方法。分析13条RDFS推理规则之间的依赖关系，分析之后对具有共同特性的RDFS规则归类，并根据共同特性构建相应推理模型，按照RDFS规则间依赖关系确定Spark框架中推理规则模型应用顺序，在不同RDD中完成各个推理模型的推理操作，再按照之前确定的模型应用顺序执行完成整个推理过程，再将推理结果在一个RDD中完成去重操作，过滤重复数据。 (3) 研究OWL的推理规则，设计基于OWL规则的推理算法。利用前向链式推理在Spark框架下结合OWL推理规则研究设计实现并行化推理算法。前向链推理是从数据插入存储系统时触发，不断应用规则进行迭代从而得出结论。推理算法首先将复杂的26条OWL推理规则进行模型划分，把OWL规则划分为不同的推理模型，先确定各个模型内部的执行顺序，再确定各个推理模型的之间的依赖关系，从而得出整个推理规则执行顺序。最后在Spark中不同规则模型应用不同RDD完成整个推理过程，提高推理效率。1.4 本文组织结构本文共分为五个章节，组织结构如下：第一章：描述了本文的研究背景和意义，介绍了研究课题的国内外现状，通过对本文研究目标的分析，概述了主要研究内容。第二章：介绍了本文研究的相关技术理论。首先对语义Web领域进行综述，介绍了语义Web领域的技术基础RDF/RDFS和OWL推理规则，然后分析了云环境平台Spark以及Spark关键技术弹性数据集RDD。第三章：研究RDFS规则推理，优化基于RDFS规则的推理方法。第四章： 研究OWL的推理规则，设计基于OWL规则的推理算法。这一部分后面要扩展，具体说明利用什么方法，基于。设计了。算法，实现了。第五章： 总结了本文所有工作，并针对本文工作中的不足最新的研究进展，=分析了指出下一步的研究内容计划。2 相关技术与理论综述本章首先在综述RDF与语义数据推理技术的基础上，详细分析了具体介绍RDFS推理规则与OWL推理规则，总结了基于形式概念分析的语义推理相关研究。介绍了云计算平台Hadoop及其分布式计算模型Spark，然后分析了Spark关键技术RDD，描述云计算平台Hadoop以及Hadoop下的分布式计算模型Spark，最后介绍形式概念分析与语义推理的相关性研究。2.1 RDF与语义数据推理相关技术RDF是一种由W3C推荐的数据模型，并且作为语义网的数据交换标准。RDF数据模型又可以称之为RDF图，RDF图组成的包括了资源、属性和陈述。其中资源用特定的统一资源标识符（URI, Uniform Resource Identifier）来表示，资源可以是互联网中所包含的任意数据、虚拟数据或者是现实中的其他事物；属性则是描述资源自身的内部特征、以及众多资源之间的关系，RDF图中的每一条属性都蕴含了特殊的意义；陈述三元组，用（主语、谓语、宾语）的形式来表示其中主语代表的是资源，由URI表示；属性则代表谓语，同样也是由URI表示；宾语是资源（URI）或文本。RDF定义了一个简单的图模型用来揭示资源之间的关系，这种简单的图模型也可以用RDF三元组来表示。基于RDF数据模型，RDFS和OWL分别定义了一组不同的语义数据推理规则，在RDFS与OWL规则中每一条规则分别代表隐含信息的能力。而推理是推导RDF三元组中隐含信息的过程，采用了RDFS或OWL推理规则中从现有的RDF数据信息中应用规则进行推理。例如，可以这样描述一个推理过程，给定一个RDF图P，在RDF图P中应用RDFS或OWL推理规则得到一些新的三元组Q，添加Q到P中，然后得到新的规模更大的RDF图P，所以，从P到P的过程称为语义推理。2.1.12 基于RDFS推理规则的语义推理RDF Shema（RDFS）是RDF数据模型的词汇描述语言。RDFS也可以视为是RDF数据模型中的基本类型系统，是一种简洁的本体语言，即“一种对共享概念化的、明确的形式化说明”。RDFS规则推理可以完成几乎所有的RDFS蕴含推理，另外，RDFS推理规则还具有良好的可计算性和易读性，是目前在语义数据推理领域中所采用的使用最为广泛的方法之一，得到了众多研究者的关注和研究。在RDFS推理规则集中包含13条推理规则，如表2-1所示，在RDFS推理规则中，主要包含的属性有rdfs:subProperyOf与rdfs:subClassOf，属性限制条件有rdfs:domain、rdfs：range和rdfs:ConstraintProperty，表示类的条件有rdfs:Resource与rdfs:Class。在RDFS规则中描述语义数据之间的关系主要包括以下四种l 类与实例关系l 子类和类继承关系l 属性、子属性与属性层次关系l 属性限制条件论文不出现项目符号，用（1）、（2）。表2-1 RDFS规则规则条件结论1s p o(if o is a literal)_:n rdf:type rdfs:Literal2p rdfs:domain x s p os rdf:type x3p rdfs:range x s p oo rdf:type x4a:4b:s p os p os rdf:type rdfs:Resourceo rdf:type rdfs:Resource5p rdfs:subProperyOf q q rdfs:subProperyOf rp rdfs:subProperyOf r6p rdf:type rdf:Propertyp rdfs:subPropertyOf p7s p o p rdfs:subProperyOf qs q o8s rdf:type rdfs:Class s rdfs:subClassOf rdfs:Resource9s rdf:type x x rdfs:subClassOf ys rdfs:subClassOf y10s rdf:type rdfs:Classs rdfs:subClassOf s11x rdfs:subClassOf y y rdfs:subClassOf zx rdfs:subClassOf z12p rdf:type rdfs:ContainerMembershipPropertyp rdfs:subProperyOf rdfs:member13o rdf:type rdfs:Datatypeo rdfs:subClassOf rdfs:Literal在运用RDFS推理规则进行推理时，主要应用规则2，3，5，7，9，11，规则2，3主要包含限制属性domain与range，规则5，7包含subProperyOf代表上述关系中的属性、子属性之间的层次关系，规则9，11包含subClassOf代表上述关系中的类与子类的之间的继承关系，而这三个关系之间的依赖关系在第三章详细分析。2.1.23 基于OWL推理规则的语义推理OWL（Ontology Web language）Web本体语言与RDFS相似也是W3C推荐的本体描述语言。RDF的发展产生了多种本体描述语言，而OWL为其中一种，与RDFS相比OWL可以更好的对本体进行描述，OWL又包含三种子语言，分别为OWL Full、OWL DL以及OWL Lite，用户根据不同的需求去选择。如图2-1所示，在W3C提出的语义本体语言栈中，OWL描述语言处于栈中的最顶端。正因为OWL在W3C推荐的本体语言地位较高，OWL推理规则也在语义推理领域中应用越来越广泛。这个图后期要自己绘制，不能copy图2-1 本体描述语言层次如下表2-2所示，OWL推理规则与RDFS推理规则相比，从推理规则的数量上来说OWL推理规则集总共包含23条推理规则接近于RDFS推理规则集的两倍；规则种类上来说，OWL规则所包含的推理条件更为复杂。所以，基于OWL推理规则进行的大规模语义数据推理，推理层次很深，范围更广，能够挖掘的隐藏数据信息更多。表2-2 OWL推理规则集No.AntecedentConsequence1p rdf:type owl:FunctionalPropertyu p v, u p wv owl:sameAs w2p rdf:type owl:InverseFunctinalPropertyv p u, w p uv owl:sameAs w3p rdf:type owl:SymmertricPropertyv p uu p v4p rdf:type owl:TransitivePropertyu p w, w p vu p v5au p vu owl:sameAs u5b678a8b9101112a12b12c13a13b13c14a14b1516u p vv owl:sameAs w v owl:sameAs w, w owl:sameAs up owl:inverseOf q, v p wp owl:inverseOf q, v q wv rdf:type owl:Class, v owl:sameAs wp rdf:type owl:Property, p owl:sameAs qu p v, u owl:sameAs x, v owl:sameAs yv owl:equivalentClass wv owl:equivalentClass wv rdfs:subClassOf w, w rdfs:subClassOf vv owl:equivalentProperty w v owl:equivalentProperty wv rdfs:subPropertyOf w w rdfs:subPropertyOf vv owl:hasValue wv owl:onProperty p, u p vv owl:hasValue wv owl:onProperty p, u rdf:type vv owl:someValuesFrom w, u p xv owl:onProperty p, x rdf:type wv owl:allValuesFrom u, w p xv owl:onProperty p, w rdf:typevv owl:sameAs vw owl:sameAs vv owl:sameAs uw q vw p vv rdfs:subClassOf wp rdfs:subPropertyOf qx p yv rdfs:subClassOf ww rdfs:subClassOf vv owl:equivalentClass wv rdfs:subPropertyOf ww rdfs:subPropertyOf vv owl:equivalentProperty wu rdf:type vu p vu rdf:type vx rdf:type u在OWL推理规则中与RDFS规则有共同特性的规则条件有：类（Class），Class定义了一些具有共同属性的个体的集合。在许多个类之间可以确定出某一个特定的层次关系，也就是子类和类的关系。子类（rdfs：subClassof），子类表明的是某一个类是另一个类的子类，也就是给出了两个类之间具有层次结构。例如，可以声明汽车类是交通工具类的子类，通过该特性可以推理出如果某个个体“汽车”，那么该个体也是一种“交通工具”。属性（rdfs：Property），属性表示对象之间或者对象和数值的关系。分为对象属性和数值属性。子属性（rdfs：subPropertyOf），子属性表示的是某个属性是另一个或多个属性的子属性，即为属性之间所具有的层次关系。例如，可以定义有兄弟是有亲戚的子属性。根据该关系，推理可以推出：如果某个个体具有有兄弟的属性，那么它也一定具有有亲戚属性。以上为OWL推理规则中与RDFS推理规则共同具有的条件关系，以下现分析OWL规则中特有的规则条件关系，包括。（1）OWL 推理规则中类、属性以及对象间的等价性Owl:equivalentClass：在OWL推理规则12的三条推理规则中，均含有该性质。Owl:equivalentClass表示当两个类被定义为等价时，即定义这两个类具有相同的实例。OWL规则12中根据条件v owl:equivalentClass w可以推理出 v rdfs:subClassOf w与w rdfs:subClassOf 两个结论，反之根据结论也可以退出条件，说明了声明为等价类的两类，为同义类。Owl:equivalentProperty：表示某两个属性等价。OWL推理规则13中主要包含该种属性， 与等价类类似。Owl:sameAs：表示两个个体相同。Owl：sameAs广泛存在Owl推理规则中，使用sameAs类似创建一个相同的别名。在第三章中，把具有sameAs的规则同意放置在同一个集合中执行，减少推理出无用三元组。（2）OWL推理规则中的属性特征与属性约束规则Owl:inverseOf：表示可以定义某属性与另一个属性为逆关系。OWL推理规则8中，p owl:inverseOf q v p w- w q v表示属性p与q为逆关系，三元组v p w含有属性p，则可以推理出w q v。Owl:TransitiveProperty：表示属性是具有传递性的。OWL推理规则4中，p rdf:type owl:TransitiveProperty u p w w p v- u p v表示属性p具有传递性，而三元组u p w与w p v中均具有传递性的谓语p，以上均作为条件可以推理出三元组u p v。Owl:SymmetricProperty：表示属性是具有对称性的。OWL推理规则3中，p rdf:type owl:SymmertricProperty v p u- u p v表示属性p具有对称性，而且属性p为三元组v p u中具有对称性质的谓语，则可以推理出三元组u p v。Owl:FunctionalProperty：表示属性是具有唯一性的。即一个属性如果被声明为函数型属性(owl:FunctionalProperty)，那么在每个个体中，属性至多只有一个值。OWL规则1则是该条规则的应用。Owl:InverseFunctionalProperty：表示如果某一属性被声明为具反函数性质的(inverse functional)，那么它的逆属性是函数型的，也就是说该属性的逆属性具有唯一性。OWL推理规则中规则2，p rdf:type owl:InverseFunctinalProperty v p u w p u- v owl:sameAs w，三元组v p u 与w p u具有反函数执行的属性p，应用同一性质后可以推理得出v，w相同。Owl:allValuesFrom：表示该属性用于某个类时有一个局部性值域约束。Owl:someValuesFrom：表示该属性至少有一个值是属于某个类型的。这两个对属性值的约束分别体现在OWL推理规则中的规则15，16。通过以上对OWL推理规则的分析，可以发现OWL推理规则较之RDFS规则无论是从数量上还是推理条件种类上来说OWL推理规则都更为复。对OWL推理规则的应用需要通过对OWL推理规则的深入分析后，首先对OWL推理规则进行推理模块的划分，然后不仅仅要分析划分好的推理模块内部推理规则之间的关系，还要深入挖掘推理模块之间的关系，从而确定模块的执行顺序，最后在Spark分布式计算框架下进行推理算法的执行，在最大程度上提高推理效率。2.4 3基于语义推理与形式概念分析相关性研究的语义推理形式概念分析理论最早产生于数学领域，是从序理论和泛代数融合发展而来的。形式概念格理论由德国 wille 教授提出，并对其进行了形式化描述。发展至今形式概念分析与不同领域相结合，其中也包括了语义数据推理。形式概念格是由多个节点组建而成，概念格中的不同的每个节点就是一个形式概念，而且，每一个不同的概念用一个单独的节点表示，所以是由多个形式概念来构成一个完成的形式概念格。概念的形式化描述是形式概念主要内容，主要包含内涵和外延两部分。内涵是指概念外延包含的实例所具有的的共同特性的集合；外延是指概念覆盖的所有实例的集合。形式背景是概念内涵、概念外延和概念之间的关系所共同组成。类似于属性、对象和对象-属性间关系构成的三元组。语义数据RDF三元组中，与形式概念格中的（属性、对象、关系）三元组极为类似的（主语，谓语，宾语）三元组，因此文献6中利用该处相似性提出基于交互式数据探索并结合形式概念分析，通过概念格分析提供搜索RDF数据链接数据，它以RDF三元组为基础并可根据用户要求从RDF资源中RDF Schema提供了一个搜索内容空间。从可视化角度来看，概念格可以通过 hasse 图将概念特性的二元关系层次结构清晰直观地绘制，体现出概念间泛化和特化关系。从语义本体分析来看：形式背景是有概念的内涵即对象集，概念的外延即属性集和两者间的关系组成的三元组，所以形式背景可以形式化描述对象和属性，它的层级结构还能揭示他们的关系。概念格中格节点的偏序关系，可以挖掘出概念中存在的各种各样的规则。因此，概念格在语义描述上，可以挖掘概念词间隐含的语义知识，还能揭露概念间的关系，所以，很多形式概念分析与语义本体相结合实现语义推理5。形式背景不仅可以分析概念之间更深层次的语义，而且通过规定不同的对象-属性的二维关系，可以揭示不同含义的关系，在文献5中，利用概念语义空间匹配出与概念存在语义关系的词语，通过Jean推理机推理，完成推理，在完成语义检索之前丰富了检索库，实现扩展功能。2.52 分布式集群计算框架Spark计算框架Spark是一种基于内存的分布式集群计算模型。Spark自身提供很多机制从而使得大规模数据能够快速的处理。其中，在Spark中核心特点是它的基于内存的并行处理模型，将所有数据分块加载到内存之中。Spark的第二个优势在于，与MapReduce中复杂的两阶段数据处理模型相比，Spark提供了一个更为灵活的基于有向无环图（DAG, directed acyclic graph），如此因此可以大大减少MapReduce中的Jop数量，可以将多个MapReduce操作简化到一个Spark作业中，减少了MapReduce的数量同时还降低了对HDFS文件的系统的反复访问次数。如图2-1表示的是多个RDD在一个Spark作业中完成某个任务，而这些多个RDD则构成了一个有向无环图。图中表示，18个RDD分别使用RDD内置的操作算子完成了在MapReduce中需要多个Map和Reduce操作所能完成的工作，从图中还可以看出，在该次操作中，仅仅对HDFS文件系统都写了一次，同样的若使用MapReduce计算模型，需要多次的读写，从而降低效率。所以，Spark提供的有向无环图机制在减少Job的数量上以及减少中间数据对HDFS读写上提高了计算性能。图2-1 Spark中RDD组成DAG除此之外，Spark还提供了大量计算接口，不仅包含传统的map、reduce接口， 还增加了filter、flatMap、union等操作接口，使得编写Spark程序更加灵活方便。Spark这种编程模型是建立在一种新的基于抽象分布式内存之上，被称为弹性分布式数据集（RDD, Resilient Distributed Dataset）实现了大规模数据在内存中计算。在Spark中，RDD是一个不可变的数据集合，提供了各种各样的内置操作可以将数据从一个RDD转移到另一个RDD之中。Spark可以缓存各个工作节点中RDD的数据到内存之中，让各个节点可以重用这些数据从而提高了数据处理效率。另外，RDD是只读的记录分区的集合，新的RDD只能通过在其他RDD执行确定的转换操作（如map、join和group by），然而这些限制使得实现容错的开销很低,从而提高了RDD的高容错性，当一个节点创建失败时，Spark可以从其他的RDD中追踪到足够多的数据信息来重构。图2-2 Spark工作流程如图2-2所示，在Spark计算模型中，需要一个主驱动程序。在驱动程序中，主要工作为根据计算任务确定执行节点中的各个RDD的操作序列，以及根据各个RDD中返回的操作结果确定下一步任务。RDD的操作序列是由称为转换的一系列数据操作抽象而成，例如，map，filter，groupBy，join等Spark中的内置RDD算子。通过RDD之间的转换，Spark通过各个节点上的本地数据集合实现了大规模数据的分布式操作。另外，Spark提供了两种共享变量，广播变量和累加器。广播变量将一个只读的变量缓存在每个但节点上，而不用在任务之间传递变量，广播变量可被用于有效地给每个节点一个大输入数据集的副本，进而减少通信的开销，广播变量通过SparkContext.broadcast()来创建；累加器是仅仅被相关操作累加的变量，因此可以在并行中被有效地支持，通过调用SparkContext.accumulator()来创建。通过广播变量与累加器可以在一定程度上减少各个节点之间的数据通讯，从而提高了计算效率。Spark official web site: 2.3语义推理与形式概念分析相关性研究形式概念分析理论最早产生于数学领域，是从序理论和泛代数融合发展而来的。形式概念格理论由德国 wille 教授提出，并对其进行了形式化描述。发展至今形式概念分析与不同领域相结合，其中也包括了语义数据推理。形式概念格是由多个节点组建而成，概念格中的不同的每个节点就是一个形式概念，而且，每一个不同的概念用一个单独的节点表示，所以是由多个形式概念来构成一个完成的形式概念格。概念的形式化描述是形式概念主要内容，主要包含内涵和外延两部分。内涵是指概念外延包含的实例所具有的的共同特性的集合；外延是指概念覆盖的所有实例的集合。形式背景是概念内涵、概念外延和概念之间的关系所共同组成。类似于属性、对象和对象-属性间关系构成的三元组。语义数据RDF三元组中，与形式概念格中的（属性、对象、关系）三元组极为类似的（主语，谓语，宾语）三元组，因此文献6中利用该处相似性提出基于交互式数据探索并结合形式概念分析，通过概念格分析提供搜索RDF数据链接数据，它以RDF三元组为基础并可根据用户要求从RDF资源中RDF Schema提供了一个搜索内容空间。从可视化角度来看，概念格可以通过 hasse 图将概念特性的二元关系层次结构清晰直观地绘制，体现出概念间泛化和特化关系。从语义本体分析来看：形式背景是有概念的内涵即对象集，概念的外延即属性集和两者间的关系组成的三元组，所以形式背景可以形式化描述对象和属性，它的层级结构还能揭示他们的关系。概念格中格节点的偏序关系，可以挖掘出概念中存在的各种各样的规则。因此，概念格在语义描述上，可以挖掘概念词间隐含的语义知识，还能揭露概念间的关系，所以，很多形式概念分析与语义本体相结合实现语义推理5。形式背景不仅可以分析概念之间更深层次的语义，而且通过规定不同的对象-属性的二维关系，可以揭示不同含义的关系，在文献5中，利用概念语义空间匹配出与概念存在语义关系的词语，通过Jean推理机推理，完成推理，在完成语义检索之前丰富了检索库，实现扩展功能。2.4 本章小结本章对本文研究所需用到的相关技术和相关理论进行了深入的调研与分析，包括RDF与语义数据推理相关技术在此之中又深入分析了RDFS推理规则和OWL推理规则；云计算平台相关技术Spark计算框架以及语义推理与形式概念分析相关性研究，为后续大规模语义数据的推理方法研究奠定了基础。3基于OWL推理规则算法设计本章首先对与RDFS推理规则相比更为复杂、使用更为广泛OWL推理规则进行深入分析，将二十六条推理规则根据推理前因中所包含的实例三元组的个数将其划分为五个模块，然后再对划分好的五个模块内部分别进行分析，确定模块中的执行顺序，随后再分析各个模块间之间的依赖关系从而确定的各个模块的执行顺序，最后完成基于OWL推理算法的设计，并通过实验得出实验结果。3.1 OWL推理规则分析与定义在该节中，首先对表3-1中的OWL规则集进行分析，把OWL规则按在前因中所包含的实例三元组的个数可以分为以下五类，为了方便后续深入分析，首先把五类规则模型分别定义。表3-1 OWL规则集No.AntecedentConsequence1p rdf:type owl:FunctionalPropertyu p v, u p wv owl:sameAs w2P rdf:type owl:InverseFunctinalPropertyv p u, w p uv owl:sameAs w3p rdf:type owl:SymmertricPropertyv p uu p v4p rdf:type owl:TransitivePropertyu p w, w p vu p v5au p vu owl:sameAs u5b678a8b9101112a12b12c13a13b13c14a14b1516u p vv owl:sameAs w v owl:sameAs w, w owl:sameAs up owl:inverseOf q, v p wp owl:inverseOf q, v q wv rdf:type owl:Class, v owl:sameAs wp rdf:type owl:Property, p owl:sameAs qu p v, u owl:sameAs x, v owl:sameAs yv owl:equivalentClass wv owl:equivalentClass wv rdfs:subClassOf w, w rdfs:subClassOf vv owl:equivalentProperty w v owl:equivalentProperty wv rdfs:subPropertyOf w w rdfs:subPropertyOf vv owl:hasValue wv owl:onProperty p, u p vv owl:hasValue wv owl:onProperty p, u rdf:type vv owl:someValuesFrom w, u p xv owl:onProperty p, x rdf:type wv owl:allValuesFrom u, w p xv owl:onProperty p, w rdf:typevv owl:sameAs vw owl:sameAs vv owl:sameAs uw q vw p vv rdfs:subClassOf wp rdfs:subPropertyOf qx p yv rdfs:subClassOf ww rdfs:subClassOf vv owl:equivalentClass wv rdfs:subPropertyOf ww rdfs:subPropertyOf vv owl:equivalentProperty wu rdf:type vu p vu rdf:type vx rdf:type u定义1 Ant-Sim：前因只包含一个三元组，包括规则5a、5b、6、12a、12