论文部分内容阅读
大数据蕴含着许多有价值的知识，想要获取这些知识，需要进行数据分析、数据挖掘等操作，函数查询是这些操作的基础。与一般查询不同，函数查询在查询表达式、查询结果等方面具有自己的特点，但是函数查询缺少类似于关系代数、关系演算等形式化的描述工具，这些问题阻碍了函数查询的理论研究。
为了对函数查询进行理论研究，针对查询结构和复杂度问题，本文给出了形式化定义和分析。目前，关系模型是大数据函数查询的主要数据模型，因此，重点研究关系数据模型中函数查询的结构特征。
首先，对经典关系数据库中属性进行了扩充定义，在此基础上，给出函数查询及其两个基本操作的形式化定义。使用逻辑语言中的一阶表达式语言描述函数查询，并且给出了一阶表达式语言对应于函数查询的两个基本操作，通过研究一阶表达式层次结构，推导出函数查询具有一阶查询层次结构特征，并论证了函数查询的完备性。
其次，针对函数查询解答问题，使用映射可归约方法，将函数查询语言归约到已知的可判定语言，证明函数查询解答问题的可计算性。阐述了传统查询复杂类之间的关系，从数据复杂度及表达复杂度两个方面分析了描述函数查询的一阶表达式语言的复杂度，以及一阶表达式语言相关扩展语言的复杂度。使用NC-factor归约方法，将函数查询类归约到已知的?TQ-complete类中，证明其经过PTIME预处理后，可以在NC时间内求解。在此基础上，证明了函数查询解答问题在大数据上是可处理的，并且给出了大数据环境下可处理查询类中连接查询复杂度的具体分析过程。
最后，利用有向超图、属性网描述大数据分析中的函数查询，给出了分组查询、测量查询、归约查询三个基本函数查询的形式化定义。为了说明这些形式化定义的实际意义，给出了将形式化描述的分组查询、测量查询、归约查询翻译成SQL查询的过程，并在Hadoop环境下执行了分组查询、测量查询、归约查询对应的SQL查询。
为了对函数查询进行理论研究，针对查询结构和复杂度问题，本文给出了形式化定义和分析。目前，关系模型是大数据函数查询的主要数据模型，因此，重点研究关系数据模型中函数查询的结构特征。
首先，对经典关系数据库中属性进行了扩充定义，在此基础上，给出函数查询及其两个基本操作的形式化定义。使用逻辑语言中的一阶表达式语言描述函数查询，并且给出了一阶表达式语言对应于函数查询的两个基本操作，通过研究一阶表达式层次结构，推导出函数查询具有一阶查询层次结构特征，并论证了函数查询的完备性。
其次，针对函数查询解答问题，使用映射可归约方法，将函数查询语言归约到已知的可判定语言，证明函数查询解答问题的可计算性。阐述了传统查询复杂类之间的关系，从数据复杂度及表达复杂度两个方面分析了描述函数查询的一阶表达式语言的复杂度，以及一阶表达式语言相关扩展语言的复杂度。使用NC-factor归约方法，将函数查询类归约到已知的?TQ-complete类中，证明其经过PTIME预处理后，可以在NC时间内求解。在此基础上，证明了函数查询解答问题在大数据上是可处理的，并且给出了大数据环境下可处理查询类中连接查询复杂度的具体分析过程。
最后，利用有向超图、属性网描述大数据分析中的函数查询，给出了分组查询、测量查询、归约查询三个基本函数查询的形式化定义。为了说明这些形式化定义的实际意义，给出了将形式化描述的分组查询、测量查询、归约查询翻译成SQL查询的过程，并在Hadoop环境下执行了分组查询、测量查询、归约查询对应的SQL查询。