《计算机应用》唯一官方网站 ›› 2020, Vol. 40 ›› Issue (2): 416-419.DOI: 10.11772/j.issn.1001-9081.2019091618

• 第36届CCF中国数据库学术会议(NDBC 2019) • 上一篇    下一篇

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

吴文莉, 刘国华(), 张君宝   

  1. 东华大学 计算机科学与技术学院,上海 201620
  • 收稿日期:2019-08-12 修回日期:2019-09-24 接受日期:2019-10-24 发布日期:2019-10-31 出版日期:2020-02-10
  • 通讯作者: 刘国华
  • 作者简介:吴文莉(1995—),女,安徽芜湖人,硕士研究生,主要研究方向:数据库
    张君宝(1988—),男,黑龙江尚志人,博士研究生,主要研究方向:以数据为中心的BPM数据分析。

Complexity analysis of functional query answering on big data

Wenli WU, Guohua LIU(), Junbao ZHANG   

  1. School of Computer Science and Technology,Donghua University,Shanghai 201620,China
  • Received:2019-08-12 Revised:2019-09-24 Accepted:2019-10-24 Online:2019-10-31 Published:2020-02-10
  • Contact: Guohua LIU
  • About author:WU Wenli, born in 1995, M. S. candidate. Her research interests include database.
    ZHANG Junbao, born in 1988, Ph. D. candidate. His research interests include data-centric BPM data analysis.

摘要:

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

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

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 ΠΤ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

中图分类号: