Abstract:

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 NC-factor reduction method was used to reduce the functional query class to the known \mathrm{\Pi }{\mathrm{{\rm T}}}_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.

Key words: big data, functional query, query answering, complexity, database

摘要：

函数查询是大数据应用中重要的操作，查询解答问题一直是数据库理论中的核心问题。为了分析大数据上函数查询解答问题的复杂度，首先，使用映射归约方法将函数查询语言归约到已知的可判定语言，证明了函数查询解答问题的可计算性；其次，使用一阶语言描述函数查询，并分析了一阶语言的复杂度；在此基础上，使用NC-factor归约方法将函数查询类归约到已知的\mathrm{\Pi }{\mathrm{{\rm T}}}_Q-complete类中。证明函数查询解答问题经过PTIME（多项式时间）预处理后，可以在NC（并行多项式-对数）时间内求解。通过以上证明可以推出，函数查询解答问题在大数据上是可处理的。

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