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

针对如何更好地维护关系数据库的数据完整性以及帮助审计员找出违规的报销记录的问题,提出了自动发现聚合代数约束(AAC)的算法AAC-Hunter.AAC是一种定义在数据库中两列的聚合结果之间的模糊约束,作用于大多数而非全部记录上.AAC-Hunter首先枚举连接、分组和代数表达式来产生候选AAC,然后分别计算这些候选AA...

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

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.