AAC-Hunter: efficient algorithm for discovering aggregation algebraic constraints in relational databases

doi:10.11772/j.issn.1001-9081.2020091473

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (3): 636-642.DOI: 10.11772/j.issn.1001-9081.2020091473

Special Issue: 第37届CCF中国数据库学术会议(NDBC 2020)

• The 37th CCF National Database Conference (NDBC 2020) • Previous Articles Next Articles

AAC-Hunter: efficient algorithm for discovering aggregation algebraic constraints in relational databases

ZHANG Xiaowei¹, JIANG Dawei^1,2, CHEN Ke^1,2, CHEN Gang^1,2

1. College of Computer Science and Technology, Zhejiang University, Hangzhou Zhejiang 310027, China;
2. Key Laboratory of Big Data Intelligent Computing of Zhejiang Province(Zhejiang University), Hangzhou Zhejiang 310027, China

Received:2020-09-07 Revised:2020-10-30 Online:2021-03-10 Published:2020-11-10
Supported by:
This work is partially supported by the Youth Program of National Natural Science Foundation of China (61702449).

关系数据库中聚合代数约束的高效发现算法——AAC-Hunter

张效伟¹, 江大伟^1,2, 陈珂^1,2, 陈刚^1,2

1. 浙江大学计算机科学与技术学院, 杭州 310027;
2. 浙江省大数据智能计算重点实验室(浙江大学), 杭州 310027

通讯作者: 陈珂
作者简介:张效伟(1996-),男,浙江嘉兴人,硕士研究生,主要研究方向:数据库约束发现;江大伟(1982-),男,安徽蚌埠人,研究员,博士,主要研究方向:分布式数据库、大数据管理、区块链;陈珂(1977-),女,河南开封人,副教授,博士,CCF会员,主要研究方向:时空数据库、数据挖掘、数据隐私保护;陈刚(1973-),男,浙江奉化人,教授,博士,CCF会员,主要研究方向:大数据管理。
基金资助:
国家自然科学基金青年科学基金资助项目（61702449）。

Abstract

Abstract: In order to better maintain the data integrity and help auditors find anomalous reimbursement records in relational databases, the algorithm AAC-Hunter (Aggregation Algebraic Constraints Hunter), which discovered Aggregation Algebraic Constraints (AACs) automatically, was proposed. An AAC is a fuzzy constraint defined between the aggregation results of two columns in the database and acts on most but not all records. Firstly, joining, grouping and algebraic expressions were enumerated to generate candidate AACs. Secondly, the value range sets of these candidate AACs were calculated. Finally, the AAC results were output. However, this method was not able to face the performance challenges caused by massive data, so that a set of heuristic rules were applied to decrease the size of candidate constraint space and the optimization strategies based on intermediate results reuse and trivial candidate AACs elimination were employed to speed up the value range set calculation for candidate AACs. Experimental results on TPC-H and European Soccer datasets show that AAC-Hunter reduces the constraint discovery space by 95.68% and 99.94% respectively, and shortens running time by 96.58% and 92.51% respectively, compared with the baseline algorithm without heuristic rules or optimization strategies. As the effectiveness of AAC-Hunter is verified, it can be seen that AAC-Hunter can improve the efficiency and capability of auditing application.

Key words: constraints discovery, Aggregation Algebraic Constraint (AAC), relational database, data-driven, auditing

摘要： 针对如何更好地维护关系数据库的数据完整性以及帮助审计员找出违规的报销记录的问题，提出了自动发现聚合代数约束（AAC）的算法AAC-Hunter。AAC是一种定义在数据库中两列的聚合结果之间的模糊约束，作用于大多数而非全部记录上。AAC-Hunter首先枚举连接、分组和代数表达式来产生候选AAC，然后分别计算这些候选AAC的值域集合，最后输出AAC结果。但该方法无法应对海量数据带来的性能挑战，因此AAC-Hunter提出了一套启发式规则减小候选约束空间规模以及基于中间结果复用和消除平凡候选AAC的两个优化策略来加速候选AAC的值域集合计算。实验结果表明了对比不使用启发式规则和优化策略的基线算法，AAC-Hunter在TPC-H和European Soccer数据集上分别减小了95.68%和99.94%的约束发现空间，分别缩短了96.58%和92.51%的运行时间。可见AAC-Hunter具备有效性，能够提升审计应用的效率和能力。

关键词: 约束发现, 聚合代数约束, 关系数据库, 数据驱动, 审计

CLC Number:

TP311.1

ZHANG Xiaowei, JIANG Dawei, CHEN Ke, CHEN Gang. AAC-Hunter: efficient algorithm for discovering aggregation algebraic constraints in relational databases[J]. Journal of Computer Applications, 2021, 41(3): 636-642.

张效伟, 江大伟, 陈珂, 陈刚. 关系数据库中聚合代数约束的高效发现算法——AAC-Hunter[J]. 计算机应用, 2021, 41(3): 636-642.

References

[1] HUHTALA Y,KÄRKKÄINEN J,PORKKA P,et al. TANE:an efficient algorithm for discovering functional and approximate dependencies[J]. The Computer Journal,1999,42(2):100-111.
[2] WYSS C,GIANNELLA C,ROBERTSON E. FastFDs:a heuristicdriven,depth-first algorithm for mining functional dependencies from relation instances extended abstract[C]//Proceedings of the 2001 International Conference on Data Warehousing and Knowledge Discovery,LNCS 2114. Berlin:Springer,2001:101-110.
[3] BERTI-ÉQUILLE L, HARMOUCH H, NAUMANN F, et al. Discovery of genuine functional dependencies from relational data with missing values[J]. Proceedings of the VLDB Endowment, 2018,11(8):880-892.
[4] FLACH P A, SAVNIK I. Database dependency discovery:a machine learning approach[J]. AI Communications,1999,12(3):139-160.
[5] CHIANG F,MILLER R J. Discovering data quality rules[J]. Proceedings of the VLDB Endowment,2008,1(1):1166-1177.
[6] FAN W, GEERTS F, LI J, et al. Discovering conditional functional dependencies[J]. IEEE Transactions on Knowledge and Data Engineering,2011,23(5):683-698.
[7] GOETHALS B, LAURENT D, LE PAGE W. Discovery and application of functional dependencies in conjunctive query mining[C]//Proceedings of the 2010 International Conference on Data Warehousing and Knowledge Discovery, LNCS 6263. Berlin:Springer,2010:142-156.
[8] 杜岳峰, 申德荣, 聂铁铮, 等. 基于关联数据的一致性和时效性清洗方法[J]. 计算机学报,2017,40(1):92-106.(DU Y F, SHEN D R,NIE T Z,et al. A cleaning method for consistency and currency in related data[J]. Chinese Journal of Computers,2017, 40(1):92-106.)
[9] CHU X,ILYAS I F,PAPOTTI P. Discovering denial constraints[J]. Proceedings of the VLDB Endowment,2013,6(13):1498-1509.
[10] BLEIFU T,KRUSE S,NAUMANN F. Efficient denial constraint discovery with hydra[J]. Proceedings of the VLDB Endowment, 2017,11(3):311-323.
[11] PENA E H M,DE ALMEIDA E C,NAUMANN F. Discovery of approximate(and exact)denial constraints[J]. Proceedings of the VLDB Endowment,2019,13(3):266-278.
[12] 卢菁, 党延领, 刘丛. DR-RDC:基于校准否定约束集的数据修复方法[J]. 小型微型计算机系统,2019,40(5):1083-1088. (LU J,DANG Y L,LIU C. DR-RDC:data repair approach based on revised denial constraint sets[J]. Journal of Chinese Computer Systems,2019,40(5):1083-1088.)
[13] DE CARVALHO M G,LAENDER A H F,GONÇALVES M A,et al. An evolutionary approach to complex schema matching[J]. Information Systems,2013,38(3):302-316.
[14] DHAMANKAR R,LEE Y,DOAN A,et al. iMAP:discovering complex semantic matches between database schemas[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York:ACM,2004:383-394.
[15] WEI Z,LECK U,LINK S. Discovery and ranking of embedded uniqueness constraints[J]. Proceedings of the VLDB Endowment, 2019,12(13):2339-2352.
[16] BROWN P G,HAAS P J. BHUNT:automatic discovery of fuzzy algebraic constraints in relational data[C]//Proceedings of the 29th International Conference on Very Large Data Bases. Burlington,MA:Morgan Kaufmann Publishers,2003:668-679.
[17] 李默涵, 李建中. 数据时效性修复问题的求解算法[J]. 计算机研究与发展,2015,52(9):1992-2001.(LI M H,LI J Z. Algorithms for improving data currency[J]. Journal of Computer Research and Development,2015,52(9):1992-2001.)
[18] 段旭良, 郭兵, 沈艳, 等. 基于时效规则的数据修复方法[J]. 软件学报,2019,30(3):589-603.(DUAN X L,GUO B,SHEN Y,et al. Data repair algorithm based on currency rules[J]. Journal of Software,2019,30(3):589-603.)
[19] 陈伟, QIU R, 刘思峰. 数据库技术在计算机辅助审计中的应用研究[J]. 计算机应用研究,2008,25(6):1908-1910.(CHEN W,QIU R,LIU S F. Study on database technologies used in computer-aided audit[J]. Application Research of Computers, 2008,25(6):1908-1910.)

AAC-Hunter: efficient algorithm for discovering aggregation algebraic constraints in relational databases

关系数据库中聚合代数约束的高效发现算法——AAC-Hunter

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 11

Recommended Articles

Metrics

[1]	ZHU Lin, NING Qian, LEI Yinjie, CHEN Bingcai. Remaining useful life prediction for turbofan engines by genetic algorithm-based selective ensembling and temporal convolutional network [J]. Journal of Computer Applications, 2020, 40(12): 3534-3540.
[2]	LIU Yudong, WANG Xu'an, TU Guangsheng, WANG Han. Cloud outsourcing data secure auditing protocol throughout whole lifecycle [J]. Journal of Computer Applications, 2019, 39(7): 1954-1958.
[3]	DENG Tianmin, FANG Fang, YUE Yunxia, YANG Qizhi. GNSS/INS global high-precision positioning method based on Elman neural network [J]. Journal of Computer Applications, 2019, 39(4): 994-1000.
[4]	YIN Xuemei, ZHOU Junhua, ZHU Yaoqin. Data modeling and data-driven method in collaborative design of complex products [J]. Journal of Computer Applications, 2018, 38(10): 3017-3024.
[5]	DONG Haitao, TIAN Jing, YANG Jun, YE Xiaozhou, SONG Lei. Efficient plaintext gathering method for data protected by SSL/TLS protocol in network auditing [J]. Journal of Computer Applications, 2015, 35(10): 2891-2895.
[6]	MA Rui-min CHEN Ji-hong. Database watermarking algorithm based on parity modulation in two-dimension space [J]. Journal of Computer Applications, 2012, 32(08): 2268-2270.
[7]	. Design of integrated system for heterogeneous network query terminal [J]. Journal of Computer Applications, 2009, 29(08): 2191-2193.
[8]	. Relational database watermark method based on user restraint [J]. Journal of Computer Applications, 2007, 27(8): 1931-1934.
[9]	. Real-time XML data query process based on relational database [J]. Journal of Computer Applications, 2006, 26(7): 1679-1681.
[10]	. Application of users abnormal behavior detection in security auditing system [J]. Journal of Computer Applications, 2006, 26(7): 1637-1639.
[11]	ZHANG Yuan-yuan,XIA Xue-ting,TAO Hong-cai. Scheme of interfusing relational database based on IIMS [J]. Journal of Computer Applications, 2005, 25(08): 1846-1848.