科研之友
微信
新浪微博
Facebook
分享链接
摘要
函数查询是大数据应用中重要的操作,查询解答问题一直是数据库理论中的核心问题。为了分析大数据上函数查询解答问题的复杂度,首先,使用映射归约方法将函数查询语言归约到已知的可判定语言,证明了函数查询解答问题的可计算性;其次,使用一阶语言描述函数查询,并分析了一阶语言的复杂度;在此基础上,使用NC-factor归约方法将函数查询类归约到已知的ΠΤQ-complete类中。证明函数查询解答问题经过PTIME(多项式时间)预处理后,可以在NC(并行多项式-对数)时间内求解。通过以上证明可以推出,函数查询解答问题在大数据上是可处理的。
- 单位
