大数据上函数查询解答的复杂度分析  

Complexity analysis of functional query answering on big data

作　　者：吴文莉 刘国华[1] 张君宝[1] WU Wenli;LIU Guohua;ZHANG Junbao(School of Computer Science and Technology,Donghua University,Shanghai 201620,China)

机构地区：[1]东华大学计算机科学与技术学院

出　　处：《计算机应用》2020年第2期416-419,共4页journal of Computer Applications

摘　　要：函数查询是大数据应用中重要的操作,查询解答问题一直是数据库理论中的核心问题。为了分析大数据上函数查询解答问题的复杂度,首先,使用映射归约方法将函数查询语言归约到已知的可判定语言,证明了函数查询解答问题的可计算性;其次,使用一阶语言描述函数查询,并分析了一阶语言的复杂度;在此基础上,使用NC-factor归约方法将函数查询类归约到已知的ΠΤQ-complete类中。证明函数查询解答问题经过PTIME(多项式时间)预处理后,可以在NC(并行多项式-对数)时间内求解。通过以上证明可以推出,函数查询解答问题在大数据上是可处理的。Functional query is an important operation in big data application,and the problem of query answering has always been the core problem in database theory.In order to analyze the complexity of the functional query answering problem on big data,firstly,the functional query language was reduced to a known decidable language by using mapping reduction method,which proves the computability of the functional query answering problem.Secondly,first-order language was used to describe the functional query,and the plexity of the first-order language was analyzed.On this basis,the NCfactor reduction method was used to reduce the functional query class to the knownΠΤQ-complete class.It is proved that functional query answering problem can be solved in NC time after PTIME(Polynomial TIME)preprocessing.It can be conducted that the functional query answering problem can be handled on big data.

关 键 词：大数据 函数查询 查询解答 复杂度 数据库 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]