大数据背景下关于函数查询解答的复杂度研究

吕鹏辉

天津凯立达众创空间孵化器有限公司 天津 300000

引言

对于大数据应用而言，函数查询是重要操作。即便是查询较为简单的线性，基于大数据背景，查询所需时间是人们难以接受的，远超过人们可接受的范围；在大数据时代下，对于P类函数查询，存在较大的困难，是难以进行处理的。对于传统查询而言，主要基于数据库，是一个从其至关系的函数，然而，没有包括查询函数本身情况[1]。

1 基于函数查询，问题解答的可计算性

问题解释：已知函数查询Qf，同时获知扩充数据库Bf，试问对于该查询计算机而言，能否进行计算。依据相关计算理论得知，对于判断某一问题能否计算，可将问题进一步转化，来判定该问题是否属于语言问题范畴，由此，可将问题进行如下转化：得知语言F=｛｝，在Bf解答中，Qf（Bf）是可以进行函数查询的，在式子中，Bf表示扩充数据库，某一串为，在Bf＇中，Qf＇（Bf＇）是函数查询，Bf＇作为扩充数据库，通过以上已知条件，试问是否含于语言F。定义1 ，映射的归约性特点。若已知某一可计算函数，记为函数f:∑*指向于∑*，促使基于任何一个ω，都存在ω属于Lg1，同时又等价于f（ω）属于Lg2，则可基于语言Lg1，将其映射至Lg2，且记为语言Lg1小于或者等于m Lg2。此时由Lg1至Lg2，将函数f称为归约。

引理一，若某一语言E=｛B，Q（B）>｝是可以进行判定的，在B中，Q（B）是可进行解答查询的，B作为数据库。引理2。若语言Lg1小于或者等于m Lg2，再加上可对Lg2进行判定，那么亦可对语言Lg1进行判定。定理一。若某一语言F=｛｝，在Bf解答中，Qf（Bf）是可以进行函数查询的，在式子中，Bf表示扩充数据库。求证，依据引理一可以得知，可对语言E进行判定。基于语言E，将M设为其的判定器，从由语言F至语言E，将函数f称为归约。基于语言F，其判定器描述如下，记为N：N等于查询编码，记为Qf，也就是：（1）对f（）进行计算。（2）基于f（），来对判定器进行运行，随之输出判定器的输出。从由语言F至语言E，将函数f称为归约，若包含于语言F，则表明f（）含于语言E。所以，当包含于语言F时，那么判定器可接受f（）。所以，通过查询编码的运行，可对语言F进行判定，具体而言，说明语言F具有可判定性[2]。

2 基于函数查询，问题解答的复杂度

现如今，存在诸多复杂类，比如NPTIME、PSPACE and LOGSPACE and so on。对于查询解答的复杂，主要介绍2种方式，一种是表达复杂度，另一种是数据复杂度，接下来对这两种衡量方法进行阐述。对于数据复杂度而言，第一步需对函数查询进行明确，之后把查询使用至任何一个数据库中，之后结合数据库函数，来对数据复杂度进行判定。对于表达复杂度而言，首先需对数据库进行确定，基于查询语言，来对其任何一个表达式进行查询，之后结合表达式长度，来给出相应的复杂度。定义2，一阶语言。将L视为一阶语言，该语言不存在函数符号，有着相应的等式，将R1，R2等视为关系符号。用Ri代表关系自身，或者表示关系，对于关系Ri而言，在上下文中可找出其元数。把First视为一种语言，由下述表达式构成，具体而言，。在其中，ψ是一阶函数的公式，表示不一样的变量向量，在其中，包括ψ公式中的全部变量；表示不一样的谓词符号，在其中，包括ψ公式中的全部关系。对于函数查询而言，可借助于First语言来进行表达。

若存在绝对值等于b，关系符号的秩为ai+1，可得First的表达式，也就是，其中代表一种函数查询，并记为Qf。定理二，对于first语言而言，其数据复杂度是LOGSPACE，也就是对数空间复杂性，其表达复杂度为PSPACE，具体而言，也就是多项式复杂性。对于函数查询而言，其实质就是一种函数，基于某一个元组查询难度，来对函数查询的复杂进行衡量。对于first语言数据复杂度而言，是表达式集合Gr（Qf）的复杂度。对于first语言而言，其表达复杂度为集合Grfirst（Bf）的复杂度。基于大数据环境，对于以往P类问题而言，始终是较难的问题。例如对于扫描类查询而言，如其数据量为1PB时，完成结果的查询，所需时间大概为1.9天。所以，以往对查询复杂度的分析，难以满足大数据解答[3]。

3 结束语

通过以上的分析可以得知，对于数据复杂度而言，第一步需对函数查询进行明确，之后把查询使用至任何一个数据库中，之后结合数据库函数，来对数据复杂度进行判定；对于函数查询而言，可借助于First语言来进行表达；基于大数据环境，对于以往P类问题而言，始终是较难的问题；对于传统查询而言，主要基于数据库，是一个从其至关系的函数，并没有包括查询函数本身情况；在大数据应用过程中，函数查询是关键环节，在数据库理论问题中，查询解答问题是重要问题。