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

doi:10.11772/j.issn.1001-9081.2019091618

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

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

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

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

东华大学计算机科学与技术学院，上海 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

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.

摘要/Abstract

摘要：

函数查询是大数据应用中重要的操作，查询解答问题一直是数据库理论中的核心问题。为了分析大数据上函数查询解答问题的复杂度，首先，使用映射归约方法将函数查询语言归约到已知的可判定语言，证明了函数查询解答问题的可计算性；其次，使用一阶语言描述函数查询，并分析了一阶语言的复杂度；在此基础上，使用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

中图分类号:

TP311

吴文莉, 刘国华, 张君宝. 大数据上函数查询解答的复杂度分析[J]. 计算机应用, 2020, 40(2): 416-419.

Wenli WU, Guohua LIU, Junbao ZHANG. Complexity analysis of functional query answering on big data[J]. Journal of Computer Applications, 2020, 40(2): 416-419.

图/表 5

表1 数据库B中的关系R1

Tab. 1 Relation R1 of database B

列1	列2
2	5
3	2
4	3
5	2

表2 数据库B中的关系R2

Tab. 2 Relation R2 of database B

列1
4
2

表3 扩充数据库Bf中的关系R1

Tab. 3 Relation R1 of extended database Bf

属性A₁	属性A₂	扩充属性EA₁
2	5	7
3	2	5
4	3	7
5	2	7

表4 扩充数据库Bf中的关系R2

Tab. 4 Relation R2 of extended database Bf

属性A₃	扩充属性EA₂
4	6
2	3

表5 学生表中的部分数据集D0

Tab. 5 Partial dataset D0 of student table

NAME	GENDER	CLASS	SCORE
LEVIN	M	1	79
WU	F	2	80
WANG	F	2	92
FANG	M	2	87
MA	F	1	65

参考文献 18

1	FAN W， GEERTS F， NEVEN F. Making queries tractable on big data with preprocessing［J］. Proceedings of the VLDB Endowment， 2013， 6（9）：685-696. 10.14778/2536360.2536368
2	ABITEBOUL S， HULL R， VIANU V. Foundations of Databases［M］. Boston： Addison-Wesley Press， 1995： 29-65. 10.1016/0304-3975(95)00027-t
3	CHANDRA A K， HAREL D. Structure and complexity of relational queries［J］. Journal of Computer and System Science， 1982， 25（1）：99-128. 10.1016/0022-0000(82)90012-5
4	CHANDRA A K， HAREL D. Computable queries for relational data bases［J］. Journal of Computer and System Sciences， 1980， 21（2）：156-178. 10.1016/0022-0000(80)90032-x
5	SIPSER M. Introduction to the theory of computation［J］. ACM SIGACT News， 1996， 27（1）：27-29. 10.1145/230514.571645
6	HARTMAINS J， STEARNS R E. On the computational complexity of algorithms［J］. Transactions of the American Mathematical Society， 1965， 117：285-306. 10.1090/s0002-9947-1965-0170805-7
7	IMMERMAN N. Languages that capture complexity classes［J］. SIAM Journal on Computing， 1987， 16（4）： 760-778. 10.1137/0216051
8	IMMERMAN N. Relational queries computable in polynomial time［C］// Proceedings of the 14th Annual ACM Symposium on Theory of Computing. New York： ACM， 1982： 147-152. 10.1145/800070.802187
9	DANTSIN E， EITER T， GOOTTLOB G， et al. Complexity and expressive power of logic programming［C］// Proceedings of the 12th Annual IEEE Conference on Computational Complexity. Piscataway： IEEE， 1997： 82-101. 10.1109/ccc.1997.612304
10	JOHNSON D S. A catalog of complexity classes［G］// Handbook of Theoretical Computer Science， Vol. A： Algorithms and Complexity. Cambridge： MIT Press， 1990： 67-161. 10.1016/b978-0-444-88071-0.50007-2
11	HENZINGER M R， HENZINGER T A， KOPKE P W. Computing simulations on finite and infinite graphs［C］// Proceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science. Piscataway： IEEE， 1995， 453-462. 10.1109/sfcs.1995.492576
12	VARDI M Y. The complexity of relational query languages （extended abstract）［C］// Proceedings of 14th ACM Symposium on Theory of Computing. New York： ACM， 1982：137-146. 10.1145/800070.802186
13	STOCKMEYER L J. The polynomial-time hierarchy［J］. Theoretical Computer Science， 1976， 3（1）：1-22. 10.1016/0304-3975(76)90061-x
14	CHANDRA A K， MERLIN P M. Optimal implementation of conjunctive queries in relational databases［C］// Proceedings of 9th Annual ACM Symposium on Theory of Computing. New York： Association for Computing Machinery， 1977：77-90. 10.1145/800105.803397
15	FAN W， HUAI J. Querying big data： bridging theory and practice［J］. Journal of Computer Science and Technology， 2014， 29（5）： 849-869. 10.1007/s11390-014-1473-2
16	GREENLAW R， HOOVER H J， RUZZO W L. Limits to Parallel Computation： P-Completeness Theory［M］. New York： Oxford University Press， 1995： 98-112. 10.1093/oso/9780195085914.003.0005
17	SUCIU D， TANNEN V. A query language for NC［J］. Journal of Computer and System Science， 1997， 55（2）： 299-321. 10.1006/jcss.1997.1525
18	PAPADIMITRIOU C H. Computational Complexity［M］. 2nd ed. Boston： Addison-Wesley Press， 1994： 158-168.

[1]	余敦辉, 万鹏, 王社. 基于企业知识图谱构建的实体关联查询系统[J]. 计算机应用, 2021, 41(9): 2510-2516.
[2]	李翀, 王宇宸, 杜伟静, 何晓涛, 刘学敏, 张士波, 李树仁. 基于Web of Science的PageRank人才挖掘算法[J]. 计算机应用, 2021, 41(5): 1356-1360.
[3]	张凌哲, 黄向东, 乔嘉林, 勾王敏浩, 王建民. 面向时序数据的两阶段日志结构合并树文件合并框架[J]. 计算机应用, 2021, 41(3): 618-622.
[4]	张效伟, 江大伟, 陈珂, 陈刚. 关系数据库中聚合代数约束的高效发现算法——AAC-Hunter[J]. 计算机应用, 2021, 41(3): 636-642.
[5]	周翔, 翟俊海, 黄雅婕, 申瑞彩, 侯璎真. 基于随机森林和投票机制的大数据样例选择算法[J]. 计算机应用, 2021, 41(1): 74-80.
[6]	曹策俊, 刘桔. 灾害运作管理中应急组织决策建模方法综述[J]. 计算机应用, 2020, 40(7): 2142-2149.
[7]	朱小杰, 赵子豪, 杜一. 模型驱动的大数据流水线框架PiFlow[J]. 计算机应用, 2020, 40(6): 1638-1647.
[8]	徐志强, 蒋铁钢, 杨立波. 基于随机支撑挑选的广义正交匹配追踪算法[J]. 计算机应用, 2020, 40(4): 1104-1108.
[9]	兰海, 韩珂, 申砾, 崔秋, 彭煜玮. TiDB的多索引访问优化[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 410-415.
[10]	杨程, 陆佳民, 冯钧. 分布式环境下大规模资源描述框架数据划分方法综述[J]. 计算机应用, 2020, 40(11): 3184-3191.
[11]	李孜颖, 石振国. 面向大数据任务的调度方法[J]. 计算机应用, 2020, 40(10): 2923-2928.
[12]	章永来, 周耀鉴. 聚类算法综述[J]. 计算机应用, 2019, 39(7): 1869-1882.
[13]	马建刚, 马应龙. 语义驱动的司法文档学习分类方法[J]. 计算机应用, 2019, 39(6): 1696-1700.
[14]	范吉立, 何蒲, 李晓华, 聂铁铮, 于戈. 基于区块链的去中心化物品共享交易服务系统[J]. 计算机应用, 2019, 39(5): 1330-1335.
[15]	纪丽娜, 陈凯, 于彦伟, 宋鹏, 王淑莹, 王成锐. 基于城市交通大数据的车辆类别挖掘及应用分析[J]. 计算机应用, 2019, 39(5): 1343-1350.

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

Complexity analysis of functional query answering on big data

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 18

相关文章 15

编辑推荐

Metrics