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

• 作者: 刘国华 吴文莉 张君宝
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 大数据 函数查询 查询解答 复杂度 数据库
• 年，卷（期）: 2020,（2）
• 所属期刊栏目: 第36届CCF中国数据库学术会议(NDBC2019)
• 页码范围: 416-419
• 页数: 4页
• 分类号: TP311
• 字数: 5656字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2019091618

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘国华	东华大学计算机科学与技术学院	63	422	9.0	18.0
2	吴文莉	东华大学计算机科学与技术学院	2	0	0.0	0.0
3	张君宝	东华大学计算机科学与技术学院	2	2	1.0	1.0