，2 ，2* ，2

（1.浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310027；2.浙江省大數(shù)據(jù)智能計(jì)算重點(diǎn)實(shí)驗(yàn)室（浙江大學(xué)），杭州 310027）

0 引言

給定一個(gè)關(guān)系數(shù)據(jù)庫，聚合代數(shù)約束（Aggregation Algebraic Constraint，AAC）是一個(gè)定義在該數(shù)據(jù)庫中兩列的聚合運(yùn)算結(jié)果之間的模糊代數(shù)約束。聚合代數(shù)約束僅約束數(shù)據(jù)庫中的大多數(shù)而非全部記錄。

本文研究如何從關(guān)系數(shù)據(jù)庫中自動(dòng)發(fā)現(xiàn)聚合代數(shù)約束。該技術(shù)在智慧審計(jì)領(lǐng)域具有廣泛的應(yīng)用前景?？紤]一個(gè)簡(jiǎn)化的報(bào)銷數(shù)據(jù)表，該表包含5個(gè)字段：（員工，部門，交通費(fèi)，住宿費(fèi)，雜費(fèi)），表中每一條記錄是包含上述5 個(gè)字段信息的報(bào)銷記錄。審計(jì)員希望從該表中找出違規(guī)的報(bào)銷記錄，該審計(jì)過程能夠順利實(shí)施的關(guān)鍵在于審計(jì)員能否發(fā)現(xiàn)報(bào)銷數(shù)據(jù)表中存在的模糊約束，即作用于數(shù)據(jù)表中的大多數(shù)而非全部記錄之間的約束。如果模糊約束的邏輯較簡(jiǎn)單，則一般可以通過專家經(jīng)驗(yàn)給出。例如，如果審計(jì)員通過先驗(yàn)知識(shí)得知大多數(shù)正常的報(bào)銷記錄滿足如下約束：交通費(fèi)+住宿費(fèi)＜1 000，那么該審計(jì)員可以通過標(biāo)準(zhǔn)的結(jié)構(gòu)化查詢語言（Structured Query Language，SQL）找出違反上述約束關(guān)系的記錄集，然后逐一檢查該記錄集每一條記錄是否是違規(guī)報(bào)銷。

然而，如果報(bào)銷數(shù)據(jù)表存在聚合代數(shù)約束，由于聚合代數(shù)約束中包含聚合運(yùn)算且和數(shù)據(jù)表中數(shù)據(jù)的分布高度相關(guān)，審計(jì)員很難通過通用的先驗(yàn)知識(shí)發(fā)現(xiàn)該約束。報(bào)銷數(shù)據(jù)表中的一個(gè)聚合代數(shù)約束c1如下所示：

該聚合代數(shù)約束表明，按照部門字段對(duì)報(bào)銷記錄進(jìn)行分組，大多數(shù)部門的平均住宿費(fèi)和平均雜費(fèi)之和在特定的區(qū)間[1000，2 000]以及[3 000，5 000]內(nèi)。根據(jù)上述c1約束，審計(jì)員應(yīng)該審計(jì)那些平均花費(fèi)不在上述區(qū)間的部門的報(bào)銷記錄。類似c1的聚合代數(shù)約束很難通過先驗(yàn)知識(shí)獲得，這是因?yàn)檫@些聚合代數(shù)約束涉及兩列聚合運(yùn)算結(jié)果（c1中為住宿費(fèi)和雜費(fèi)的聚合運(yùn)算結(jié)果）之間的關(guān)系，該關(guān)系通常和數(shù)據(jù)分布高度相關(guān)。審計(jì)員需要采用數(shù)據(jù)驅(qū)動(dòng)的方法從數(shù)據(jù)庫中自動(dòng)發(fā)現(xiàn)聚合代數(shù)約束。

本文提出了一個(gè)從關(guān)系數(shù)據(jù)庫中高效地發(fā)現(xiàn)聚合代數(shù)約束的算法AAC-Hunter（Aggregation Algebraic Constraints Hunter）。在大數(shù)據(jù)時(shí)代，隨著數(shù)據(jù)體量越來越大，數(shù)據(jù)之間的約束關(guān)系變得越來越復(fù)雜。研究者們逐漸從以專家經(jīng)驗(yàn)為主的約束發(fā)現(xiàn)，轉(zhuǎn)向以數(shù)據(jù)驅(qū)動(dòng)為主的約束發(fā)現(xiàn)，提出了一系列從數(shù)據(jù)庫中自動(dòng)發(fā)現(xiàn)不同類型的約束關(guān)系的技術(shù)，以及根據(jù)約束維護(hù)數(shù)據(jù)一致性的技術(shù)，如：函數(shù)約束［1-4］、條件函數(shù)約束［5-8］、否定約束［9-12］、模式約束［13-14］、唯一約束［15］、代數(shù)約束［16］和時(shí)效規(guī)則［17-18］。然而，本文是第一項(xiàng)研究如何自動(dòng)發(fā)現(xiàn)聚合代數(shù)約束的工作。AAC-Hunter 分兩步生成聚合代數(shù)約束：第一步，AAC-Hunter 根據(jù)數(shù)據(jù)模式信息，生成由全體候選聚合代數(shù)約束組成的候選集合。候選聚合代數(shù)約束中參與聚合運(yùn)算的兩列可以來自同一張數(shù)據(jù)表，也可以來自不同的數(shù)據(jù)表。如果兩列來自不同的數(shù)據(jù)表，AAC-Hunter 自動(dòng)決定兩張數(shù)據(jù)表的連接方法。示例聚合代數(shù)約束c1對(duì)應(yīng)的候選聚合代數(shù)約束為(Avg(住宿費(fèi))+Avg(雜費(fèi)))GroupBy(部門)。第二步，AAC-Hunter 為每條候選聚合代數(shù)約束計(jì)算一個(gè)值域集合，使該值域集合覆蓋數(shù)據(jù)庫中的大多數(shù)記錄，并將該候選聚合代數(shù)約束與計(jì)算出的值域集合輸出為最終的聚合代數(shù)約束 。AAC-Hunter 為c1計(jì) 算 出 的 值 域 空 間 為[1000，2 000]∪[3 000，5 000]。

從海量數(shù)據(jù)庫中自動(dòng)發(fā)現(xiàn)聚合代數(shù)約束存在兩方面的性能挑戰(zhàn)：1）全體候選聚合代數(shù)約束組成的候選集合的規(guī)模巨大，難以在有限的時(shí)間內(nèi)處理該候選集合中的每一條候選聚合代數(shù)約束；2）計(jì)算候選聚合代數(shù)約束的值域集合涉及表連接、聚合運(yùn)算等耗時(shí)的數(shù)據(jù)庫操作，代價(jià)高昂。AAC-Hunter提出了一系列優(yōu)化技術(shù)克服了上述兩個(gè)挑戰(zhàn)。本文的核心貢獻(xiàn)如下：

1）提出并形式化了一種新的數(shù)據(jù)庫模糊約束——聚合代數(shù)約束（第2.1節(jié)）。

2）提出了一個(gè)從數(shù)據(jù)庫中自動(dòng)發(fā)現(xiàn)聚合代數(shù)約束的算法AAC-Hunter（第2.2節(jié)）。該算法采用一組啟發(fā)式規(guī)則減小候選聚合代數(shù)約束集合的規(guī)模（第3 章），并提出了兩項(xiàng)優(yōu)化技術(shù)加速候選聚合代數(shù)約束值域集合的計(jì)算（第4章）。

3）在TPC-H 數(shù)據(jù)集和European Soccer 數(shù)據(jù)集上與基線算法的性能對(duì)比實(shí)驗(yàn)驗(yàn)證了所提出優(yōu)化技術(shù)的有效性（第5章）。

1 相關(guān)工作

與本文相關(guān)的工作歸于基于數(shù)據(jù)驅(qū)動(dòng)的約束發(fā)現(xiàn)。依據(jù)發(fā)現(xiàn)的約束關(guān)系的不同，相關(guān)工作分為：函數(shù)約束發(fā)現(xiàn)［1-8］、否定約束發(fā)現(xiàn)［9-12］、復(fù)雜模式約束發(fā)現(xiàn)［13-14］、唯一性約束發(fā)現(xiàn)［15］、簡(jiǎn)單代數(shù)約束發(fā)現(xiàn)［16］和時(shí)效規(guī)則［17-18］。這些已有工作與本文工作的區(qū)別在于發(fā)現(xiàn)的約束關(guān)系不同。已有工作專注于發(fā)現(xiàn)數(shù)據(jù)庫中記錄之間或者列之間的各種約束關(guān)系，而本文工作研究的是兩列聚合運(yùn)算結(jié)果之間的代數(shù)約束關(guān)系而非直接作用于數(shù)據(jù)庫兩列之間的代數(shù)約束關(guān)系。進(jìn)一步，本文研究的聚合代數(shù)約束的候選集合在規(guī)模上也比現(xiàn)有工作研究的約束候選集大很多，需要新的剪枝和優(yōu)化技術(shù)來處理。

2 發(fā)現(xiàn)聚合代數(shù)約束

2.1 聚合代數(shù)約束

聚合代數(shù)約束如定義1所示。

定義1給定關(guān)系數(shù)據(jù)庫D，聚合代數(shù)約束是一個(gè)作用于D中部分記錄上的八元組：

其中：a1、a2是D中的兩個(gè)屬性字段，可以來自同一張數(shù)據(jù)表，也可以來自兩張不同的數(shù)據(jù)表；f1、f2是分別施加在屬性a1、a2上的聚合函數(shù)，本文考慮5 種聚合函數(shù)：Count、Sum、Avg、Max和Min；二元運(yùn)算符⊕是f1(a1)和f2(a2)間的代數(shù)運(yùn)算符，包括+、-、×和/；I=I1∪I2∪…∪Ik為f1(a1)⊕f2(a2)的值域集合，其中Ii∈I是一個(gè)實(shí)數(shù)閉區(qū)間[a，b]，且I中任意兩個(gè)區(qū)間Ii、Ij滿足Ii∩Ij=?；如果a1、a2來自不同數(shù)據(jù)表，配對(duì)規(guī)則p指定數(shù)據(jù)表間的連接條件；g是分組規(guī)則，語義上等同于SQL的Group By 語句，指定與聚合運(yùn)算相關(guān)的分組字段列。定義1 形式化地表明聚合代數(shù)約束是a1、a2在條件p、g下，使用函數(shù)f1、f2進(jìn)行⊕運(yùn)算后產(chǎn)生的值域集合I約束。式（2）進(jìn)一步表示聚合代數(shù)約束中各因子間的關(guān)系：

其中：若a1、a2來自同一張表r，則配對(duì)規(guī)則p為平凡規(guī)則（即不需要表連接），記為p=?r；若a1、a2分別來自兩張表r和s，配對(duì)規(guī)則p指定r和s的連接條件，即其中cols1與cols2分別為表r、s上的連接字段；分組規(guī)則g=d1，d2，…，dn指定分組字段列。圖1 描繪了式（2）的運(yùn)算流程。

圖1 聚合代數(shù)約束運(yùn)算流程Fig.1 Calculation flow of aggregation algebraic constraint

為了更好地解釋聚合代數(shù)約束的含義，此處使用引言中的約束c1和另一個(gè)例子作進(jìn)一步解釋。關(guān)系數(shù)據(jù)庫D1中存在報(bào)銷表（員工，部門，交通費(fèi)，住宿費(fèi)，雜費(fèi)），使用定義1 中的符號(hào)規(guī)范表示約束c1，各元素如下所示：a1=住宿費(fèi)，a2=雜費(fèi)，f1=f2=Avg，p=?報(bào)銷表，g=部門，⊕為+（即加法運(yùn)算），I=[1000，2 000]∪[3 000，5 000]。聚合代數(shù)約束c1表示了各部門報(bào)銷記錄中平均住宿費(fèi)和平均雜費(fèi)的和所符合一定的值域集合。關(guān)系數(shù)據(jù)庫D2儲(chǔ)存了某工廠檢驗(yàn)生產(chǎn)工件的記錄，存在工件表（工件號(hào)，生產(chǎn)批次，倉儲(chǔ)位置）和檢驗(yàn)表（工件號(hào)，外徑，內(nèi)徑），一條聚合代數(shù)約束c2的元素如下所示：a1=外徑，a2=內(nèi)徑，f1=f2=Avg，p=工件表?工件號(hào)=工件號(hào)檢驗(yàn)表，g=生產(chǎn)批次，⊕為/（即除法運(yùn)算），I=[3.123，3.127]。聚合代數(shù)約束c2描述了這個(gè)工廠生產(chǎn)的不同批次工件，各批次平均外徑和平均內(nèi)徑的比值滿足一定的值域集合限制。由c1、c2可知，聚合代數(shù)約束描述了數(shù)據(jù)記錄根據(jù)某個(gè)屬性分組后，含統(tǒng)計(jì)特征的聚合代數(shù)運(yùn)算結(jié)果具有一定的值域限制。

2.2 AAC-Hunter算法概述

AAC-Hunter分兩步從數(shù)據(jù)庫中發(fā)現(xiàn)聚合代數(shù)約束：

1）產(chǎn)生候選聚合代數(shù)約束集合C。根據(jù)數(shù)據(jù)模式信息生成所有形如c=(f1，a1，f2，a2，p，g，⊕)的候選聚合代數(shù)約束。全體候選聚合代數(shù)約束c組成集合C。

2）使用直方圖技術(shù)，為C中的每一個(gè)候選聚合代數(shù)約束c計(jì)算值域集合I，并輸出(c，I)作為發(fā)現(xiàn)的聚合代數(shù)約束。

上述算法簡(jiǎn)單、易實(shí)現(xiàn)，但兩個(gè)原因使該算法無法應(yīng)用于稍大規(guī)模的數(shù)據(jù)庫：1）對(duì)于稍復(fù)雜的數(shù)據(jù)庫，算法第一步將會(huì)產(chǎn)生海量規(guī)模的候選聚合代數(shù)約束集合，無法在有限的時(shí)間內(nèi)處理該集合；2）計(jì)算I需要進(jìn)行表連接和聚合運(yùn)算操作，這些操作都非常耗時(shí)。本文在第3 章和第4 章引入一系列啟發(fā)式優(yōu)化技術(shù)，降低處理代價(jià)，提升AAC-Hunter算法的伸縮性。

3 產(chǎn)生候選聚合代數(shù)約束

AAC-Hunter 算法的第一步是產(chǎn)生候選聚合代數(shù)約束集合C。該步驟進(jìn)一步分為3 個(gè)子步驟：1）產(chǎn)生配對(duì)規(guī)則；2）產(chǎn)生分組規(guī)則和3）產(chǎn)生包含聚合運(yùn)算的代數(shù)表達(dá)式。AACHunter 在每一個(gè)子步驟中引入一些啟發(fā)式剪枝規(guī)則，降低C的規(guī)模，本章詳細(xì)介紹這些實(shí)現(xiàn)細(xì)節(jié)。

3.1 產(chǎn)生配對(duì)規(guī)則

AAC-Hunter 首先產(chǎn)生配對(duì)規(guī)則p，組成集合P。由定義1，若a1、a2分別來自不同的數(shù)據(jù)表r和s，則AAC-Hunter 需要產(chǎn)生配對(duì)規(guī)則p指定表連接的方法。本文考慮兩種類型的表連接：1）若r、s之間存在外鍵約束，則按照外鍵約束連接兩個(gè)表；2）若r、s之間不存在外鍵約束，則AAC-Hunter 將在r、s中找到類外鍵約束的組合字段對(duì)(cols1，cols2)，并通過該組合字段對(duì)連接兩表。第一種類型的表連接比較簡(jiǎn)單，本節(jié)詳細(xì)介紹如何產(chǎn)生第二種類型的表連接。

對(duì)包含a1和a2的表對(duì)(r，s)，AAC-Hunter在表對(duì)(r，s)中尋找所有可以連接的組合字段對(duì)(cols1，cols2)，其中cols1?r，cols2?s，滿足cols1和cols2長(zhǎng)度一致（即，兩個(gè)組合字段cols1和cols2包含相同數(shù)目的字段）且cols1和cols2組合字段中對(duì)應(yīng)位置的字段具有相同的數(shù)據(jù)類型。為了更有目的性地尋找這種組合字段對(duì)，可以參考數(shù)據(jù)庫中定義的索引字段，這些添加了索引的字段往往會(huì)被頻繁查詢且更加重要。這一步在最壞情況下將產(chǎn)生平方級(jí)別數(shù)量的組合字段對(duì)，為降低計(jì)算代價(jià)，AAC-Hunter引入以下兩條剪枝規(guī)則：

1）排除兩表均僅含有少量記錄的配對(duì)規(guī)則。這樣的配對(duì)規(guī)則無法通過后續(xù)計(jì)算分析得到有意義的值域集合。

2）排除由自增字段、NULL 值過多的字段組成類外鍵約束的配對(duì)規(guī)則。經(jīng)驗(yàn)表明這些字段或者與數(shù)據(jù)庫設(shè)計(jì)相關(guān)（即自增字段），或者與數(shù)據(jù)缺失相關(guān)（即NULL 值過多的字段）。這些字段并不存儲(chǔ)具有審計(jì)價(jià)值的數(shù)據(jù)，不是理想的連接字段。

3.2 產(chǎn)生分組規(guī)則

產(chǎn)生配對(duì)規(guī)則p之后，AAC-Hunter 接著生成分組規(guī)則集合G。該集合中的每個(gè)分組規(guī)則g由一個(gè)字段序列d1，d2，…，dn構(gòu)成。AAC-Hunter 只考慮將具有類別屬性的字段（即，該字段只存儲(chǔ)有限數(shù)量的離散值，如部門字段）加入g。

對(duì)于配對(duì)規(guī)則p，假定執(zhí)行連接運(yùn)算r?s后結(jié)果表含有m個(gè)類別字段h1，h2，…，hm，若從中選擇i個(gè)字段（0 ＜i≤m）組成分組規(guī)則，此時(shí)產(chǎn)生Ci m種組合方式作為分組規(guī)則。這種樸素的方法將產(chǎn)生總計(jì)=2m-1 個(gè)符合條件的分組規(guī)則。顯而易見，分組規(guī)則的產(chǎn)生數(shù)目隨m增大而難以接受。AAC-Hunter使用以下方法來限制分組規(guī)則集合的規(guī)模：

1）引入分組序列長(zhǎng)度最大值的超參數(shù)W以避免分組規(guī)則數(shù)過分增長(zhǎng)。此步驟中，分組規(guī)則全集的數(shù)目至多為|G|=

2）分組規(guī)則中排除自增字段、NULL值過多的字段。

3）分組規(guī)則排除存在唯一性約束的字段。

4）分組規(guī)則排除由事實(shí)唯一字段（即，值幾乎各不相同的字段）組成的規(guī)則。

3.3 產(chǎn)生代數(shù)表達(dá)式

本節(jié)構(gòu)造形如fi(ai)⊕fj(aj)的代數(shù)表達(dá)式。在配對(duì)規(guī)則p描述的連接運(yùn)算結(jié)果中，AAC-Hunter 首先尋找可進(jìn)行代數(shù)運(yùn)算的字段作為ai，接著生成與ai的數(shù)據(jù)類型相兼容的聚合函數(shù)fi。本文考慮如下兩條類型兼容規(guī)則：1）對(duì)日期類型的ai，其兼容的聚合函數(shù)為Max、Min 和Count；2）對(duì)數(shù)值類型的ai，其兼容的聚合函數(shù)為Count、Sum、Avg、Max和Min。

對(duì)于按照上述過程產(chǎn)生的fi(ai)，枚舉二元組(fi(ai)，fj(aj))，并選取語義正確的⊕產(chǎn)生代數(shù)表達(dá)式fi(ai)⊕fj(aj)。在選取⊕時(shí)，AAC-Hunter 考慮如下語義約束：1）日期與日期之間僅能做減法運(yùn)算；2）日期和整數(shù)型數(shù)據(jù)可以做加減法運(yùn)算；3）Count函數(shù)無需明確屬性字段且只做乘法運(yùn)算或者除法運(yùn)算。作為特例，枚舉僅含單個(gè)計(jì)算屬性的情況形成代數(shù)表達(dá)式fi(ai)。

假定配對(duì)規(guī)則p產(chǎn)生的結(jié)果表中有l(wèi)個(gè)字段可作為ai，則上述枚舉方案至多產(chǎn)生個(gè)代數(shù)表達(dá)式。AACHunter引入剪枝規(guī)則以減小代數(shù)表達(dá)式空間大?。?/p>

1）排除主鍵字段、自增字段、外鍵字段，以及配對(duì)規(guī)則p、分組規(guī)則g中涉及的字段。

2）排除分組規(guī)則和代數(shù)表達(dá)式相同，但配對(duì)規(guī)則不同的冗余的候選聚合代數(shù)約束。對(duì)于包含相同分組規(guī)則g=d1，d2，…，dn以及相同代數(shù)表達(dá)式fi(ai)⊕fj(aj)的多個(gè)候選聚合代數(shù)約束，AAC-Hunter 保留包含平凡配對(duì)規(guī)則p=?r的候選聚合代數(shù)約束，排除包含非平凡配對(duì)規(guī)則p=r?s的候選聚合代數(shù)約束。

4 產(chǎn)生候選聚合代數(shù)約束的值域集合

本章介紹如何產(chǎn)生候選聚合代數(shù)約束的值域集合I。AAC-Hunter 采用中間結(jié)果復(fù)用和消除平凡候選聚合代數(shù)約束兩項(xiàng)技術(shù)來加速處理候選聚合代數(shù)約束中的代數(shù)表達(dá)式計(jì)算，計(jì)算流程和加速技術(shù)的應(yīng)用如圖2 所示。本章首先介紹這兩項(xiàng)技術(shù)，然后介紹如何從代數(shù)表達(dá)式的結(jié)果生成I。

圖2 計(jì)算流程與加速技術(shù)示意圖Fig.2 Schematic diagram of calculation process and acceleration techniques

4.1 復(fù)用中間結(jié)果

從前文論述中可以推知候選聚合代數(shù)約束集合C中大量候選聚合代數(shù)約束存在公共子操作。例如，如果兩條候選聚合代數(shù)約束中a1和a2都來自相同表對(duì)(r，s) 并進(jìn)行運(yùn)算，那么該連接運(yùn)算就是這兩條候選聚合代數(shù)約束的公共子操作。類似地，如果兩條候選聚合代數(shù)約束包含相同的分組規(guī)則，那么分組操作就是公共子操作。為加速計(jì)算候選聚合代數(shù)約束中的代數(shù)表達(dá)式，AAC-Hunter 將候選聚合代數(shù)約束分類，并從每個(gè)分類中抽取公共連接和公共分組兩類公共子操作。對(duì)于公共子操作，AAC-Hunter 只計(jì)算一次，然后反復(fù)重用這些公共操作的結(jié)果，快速計(jì)算每條候選聚合代數(shù)約束的代數(shù)表達(dá)式。

AAC-Hunter 按照如下步驟對(duì)所有候選聚合代數(shù)約束進(jìn)行歸類：1）將使用相同配對(duì)規(guī)則pi的候選約束歸類，記作2）將使用相同分組規(guī)則gj的候選約束歸類，記作；3）分析候選約束組，收集涉及到的所有分類字段和計(jì)算屬性，分別記作。歸類效果如圖3所示。

圖3 基于歸類的中間結(jié)果復(fù)用示意圖Fig.3 Reusing intermediate results based on classification

AAC-Hunter 采用的中間結(jié)果復(fù)用技術(shù)可以極大地降低計(jì)算代數(shù)表達(dá)式的成本。分析如下，不采用中間結(jié)果復(fù)用的計(jì)算總成本上限為：

其中：n為表的數(shù)目，m為連接結(jié)果表平均的分類字段數(shù)目，l為連接結(jié)果表平均的計(jì)算屬性數(shù)目，k1為配對(duì)規(guī)則描述的連接計(jì)算成本系數(shù)，k2為分組運(yùn)算和代數(shù)表達(dá)式的計(jì)算成本系數(shù)，kp為產(chǎn)生配對(duì)規(guī)則數(shù)量相關(guān)的系數(shù)，W為限制分組規(guī)則序列長(zhǎng)度的超參數(shù)。復(fù)用中間結(jié)果之后，總成本上限降為：

顯而易見，中間結(jié)果復(fù)用后計(jì)算成本得到大幅降低。

4.2 消除平凡候選聚合代數(shù)約束

生成聚合代數(shù)約束的最終目的是為審計(jì)應(yīng)用服務(wù)，因此，生成的聚合代數(shù)約束必須具有代表性，即覆蓋了數(shù)據(jù)庫中絕大多數(shù)記錄；然而，有的候選聚合代數(shù)約束中配對(duì)規(guī)則描述的連接條件過于苛刻，以至于只有很少的記錄才能進(jìn)入連接結(jié)果，無法覆蓋大多數(shù)記錄。類似地，有的候選聚合代數(shù)約束中分組規(guī)則的字段序列選擇不合適，使得結(jié)果集或者僅包含少數(shù)幾個(gè)分組且每個(gè)分組包含大量記錄，或者產(chǎn)生大量分組，但每個(gè)分組只有個(gè)別記錄，從而使結(jié)果集失去了統(tǒng)計(jì)意義。

本文稱至少滿足上述兩個(gè)條件（配對(duì)規(guī)則不合適、分組規(guī)則不合適）之一的候選聚合代數(shù)約束為平凡候選約束。AACHunter引入啟發(fā)式規(guī)則來跳過這些平凡候選約束的計(jì)算。

對(duì)于配對(duì)規(guī)則pi，若發(fā)現(xiàn)連接運(yùn)算的結(jié)果記錄數(shù)較少，或遠(yuǎn)低于參與連接的兩表記錄數(shù)，則意味著pi不是一條合適的配對(duì)規(guī)則。算法將終止接下來的計(jì)算，并從剩余候選約束中剔除所有候選約束組。如圖4（a）所示，假若配對(duì)規(guī)則p1不合適，則與其相關(guān)的候選約束組中所有候選約束均不再繼續(xù)計(jì)算。

對(duì)于分組規(guī)則gj而言，檢驗(yàn)分組字段組合值的占比，僅計(jì)算占比滿足以下公式的分組規(guī)則：

1.2.1 發(fā)病規(guī)律調(diào)查 2015～2017年在試驗(yàn)地對(duì)1～3年生青楊苗木的病害發(fā)病規(guī)律進(jìn)行系統(tǒng)調(diào)查。采取標(biāo)準(zhǔn)地調(diào)查和線路調(diào)查2種方法，每年6月中旬開始，根據(jù)青楊病害歷年發(fā)生情況、扦插密度、樹齡、地形地貌、坡向、交通和管理等條件確定7個(gè)固定標(biāo)準(zhǔn)地，每個(gè)標(biāo)準(zhǔn)地選有代表性的青楊苗木15株，每株樹固定調(diào)查3～5個(gè)枝條，50～100片葉，每5d觀察1次病害發(fā)生情況，做好記錄。線路調(diào)查每10d進(jìn)行1次，根據(jù)目測(cè)情況，每點(diǎn)調(diào)查20株，每株樹調(diào)查3～5個(gè)枝條，50～100片葉，借助80倍解剖鏡觀察葉片病斑發(fā)生情況。

其中：pi=r?s為對(duì)應(yīng)配對(duì)規(guī)則的連接結(jié)果表，α為大于0 的參數(shù)，β為表示分組內(nèi)最大記錄數(shù)量的參數(shù)。

若比值不滿足式（5）的要求，則意味著分組規(guī)則的組內(nèi)記錄太多，或者分組字段序列的值有事實(shí)唯一的特性。若檢驗(yàn)出分組規(guī)則gj無效，則意味著所有包含該分組序列的分組規(guī)則也都是無效的，那么將包含這些分組規(guī)則的平凡約束也一并剔除。如圖4（b）所示，假若分組規(guī)則g2失當(dāng)，同時(shí)分組規(guī)則g3、g5與其共享相同的分組字段，那么它們對(duì)應(yīng)的所有候選約束均被消除。

上述流程以一次計(jì)算成本為代價(jià)實(shí)現(xiàn)對(duì)大量平凡候選聚合代數(shù)約束的排除，這極大地彌補(bǔ)了發(fā)現(xiàn)候選約束階段帶來的計(jì)算空間爆炸的缺陷，減小與候選約束數(shù)量相關(guān)的成本：

其中：q為數(shù)據(jù)集實(shí)際存在的連接關(guān)系數(shù)量，且q≤kpn；u為代數(shù)表達(dá)式組的執(zhí)行次數(shù)，一般u?；k3表示檢驗(yàn)每個(gè)分組規(guī)則字段組合值占比的平均成本，且k3?k2；v表示查詢分組規(guī)則字段占比的次數(shù)，顯然v≥u。

圖4 消除平凡候選聚合代數(shù)約束示意圖Fig.4 Schematic diagram of eliminating trivial candidate AACs

4.3 生成有效值域集合

完成候選約束的代數(shù)表達(dá)式計(jì)算之后，AAC-Hunter 對(duì)結(jié)果進(jìn)行離群值分析，得到正常和異常的值域集合。聚合代數(shù)約束作用于大多數(shù)記錄（指接下來被認(rèn)定為是正常的記錄）而非全部記錄的模糊約束特性在此得以體現(xiàn)。

AAC-Hunter 使用時(shí)間復(fù)雜度為O(n)的直方圖法分析代數(shù)表達(dá)式的結(jié)果，將正常值域集合作為候選聚合代數(shù)約束的值域集合I。理想情況下，數(shù)據(jù)應(yīng)是完全無錯(cuò)的，所形成的約束值域集合應(yīng)當(dāng)是代數(shù)表達(dá)式結(jié)果的全域；然而，即便通過合法渠道進(jìn)行數(shù)據(jù)持久化，也會(huì)產(chǎn)生異常數(shù)據(jù)（如表模式變更、實(shí)際業(yè)務(wù)的復(fù)雜性原因等），此時(shí)約束的值域集合應(yīng)當(dāng)剔除異常的部分，保留有效的大多數(shù)的部分。如圖5 所示，AACHunter 統(tǒng)計(jì)數(shù)值出現(xiàn)的頻度，按分布情況設(shè)定圖中橫線所示的閾值（閾值t=Rows(results) ×φ，超參數(shù)φ為留取比例），頻數(shù)大于閾值的區(qū)間被認(rèn)定為有效區(qū)間，其他區(qū)間為無效區(qū)間，體現(xiàn)適用大多數(shù)而非全部記錄的模糊約束的性質(zhì)。AACHunter 判定圖中結(jié)果序列的值域?yàn)镮=[11，30]∪[35，36]。至此，AAC-Hunter完成發(fā)現(xiàn)一條聚合代數(shù)約束的流程。

圖5 基于直方圖的運(yùn)算結(jié)果分析Fig.5 Histogram analysis for calculation results

僅從數(shù)據(jù)角度看來，AAC-Hunter 所發(fā)現(xiàn)的聚合代數(shù)約束由數(shù)據(jù)驅(qū)動(dòng)產(chǎn)生，具有模糊約束的特征（即僅約束數(shù)據(jù)庫中的大多數(shù)而非全部記錄），通常難以使用專家知識(shí)構(gòu)造，是準(zhǔn)確有效的；然而，并非任意聚合代數(shù)約束都能成為滿足現(xiàn)實(shí)業(yè)務(wù)邏輯的審計(jì)規(guī)則，其原因在于，算法既無法通過降維后的數(shù)據(jù)還原實(shí)際業(yè)務(wù)的場(chǎng)景，又無法準(zhǔn)確判別聚合代數(shù)約束是否能夠作為審計(jì)規(guī)則使用。因此，在程序結(jié)束后，審計(jì)員可以使用領(lǐng)域知識(shí)人工篩選有意義的聚合代數(shù)約束，并對(duì)值域結(jié)果做調(diào)整，使之成為審計(jì)規(guī)則。若認(rèn)為圖5 柱形圖右側(cè)柱形區(qū)間[35，36]有異常的嫌疑，則可以在此程序結(jié)果上作進(jìn)一步調(diào)整。

5 實(shí)驗(yàn)

本文用Python 和SQLite 實(shí)現(xiàn)了AAC-Hunter 算法。本章介紹實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)在CPU 為AMD Ryzen 5 1400、內(nèi)存為8 GB 的工作站上進(jìn)行。實(shí)驗(yàn)采用TPC-H 數(shù)據(jù)集（http：//www.tpc.org/tpch）和European Soccer 數(shù)據(jù)集（https：//www.kaggle.com/hugomathien/soccer），驗(yàn)證AAC-Hunter的各種優(yōu)化技術(shù)。

5.1 實(shí)驗(yàn)設(shè)計(jì)與數(shù)據(jù)集

實(shí)驗(yàn)流程如下：首先加載數(shù)據(jù)庫定義，然后產(chǎn)生候選聚合代數(shù)約束，最后產(chǎn)生候選聚合代數(shù)約束值域集合。根據(jù)經(jīng)驗(yàn)設(shè)計(jì)如下的超參數(shù)：實(shí)驗(yàn)剪枝記錄數(shù)不超過200 條的表（認(rèn)為記錄數(shù)少于200 條的表無發(fā)現(xiàn)聚合代數(shù)約束的價(jià)值），分組規(guī)則字段列長(zhǎng)度上限參數(shù)W設(shè)定為3（即1條配對(duì)規(guī)則至多產(chǎn)生7 條分組規(guī)則），字段NULL 值比率需低于5%。若執(zhí)行連接運(yùn)算后表記錄數(shù)低于100 條或低于原表記錄數(shù)90%，認(rèn)為該連接運(yùn)算涉及的約束是平凡候選聚合代數(shù)約束的，則放棄對(duì)應(yīng)配對(duì)規(guī)則。若檢查分組規(guī)則時(shí)發(fā)現(xiàn)組內(nèi)平均記錄數(shù)低于2 條或大于100 條，認(rèn)為該分組運(yùn)算涉及的約束是平凡候選聚合代數(shù)約束，則放棄該分組規(guī)則。

鑒于AAC-Hunter 算法不言而喻的正確性（即，算法所發(fā)現(xiàn)的聚合代數(shù)約束對(duì)于給定數(shù)據(jù)一定是正確的，但無法判別在現(xiàn)實(shí)業(yè)務(wù)場(chǎng)景下的正確性），實(shí)驗(yàn)關(guān)注AAC-Hunter 各種優(yōu)化技術(shù)的實(shí)際效果，并不考慮所發(fā)現(xiàn)約束的現(xiàn)實(shí)意義。實(shí)驗(yàn)在TPC-H、European Soccer 兩組廣泛使用的數(shù)據(jù)集上評(píng)估效果。TPC-H 是一種用于評(píng)估數(shù)據(jù)庫系統(tǒng)決策支持能力的數(shù)據(jù)集和執(zhí)行標(biāo)準(zhǔn)，提供了商業(yè)銷售場(chǎng)景的表模式和數(shù)據(jù)，廣泛運(yùn)用于數(shù)據(jù)庫系統(tǒng)的測(cè)試。鑒于AAC-Hunter 對(duì)表模式敏感，對(duì)記錄數(shù)量并不敏感（由記錄數(shù)量引入的復(fù)雜性本質(zhì)上是對(duì)數(shù)據(jù)庫系統(tǒng)的性能校驗(yàn)而非對(duì)AAC-Hunter 的優(yōu)化技術(shù)效果校驗(yàn)），實(shí)驗(yàn)使用0.01的規(guī)模因子產(chǎn)生數(shù)據(jù)，整個(gè)數(shù)據(jù)集共計(jì)12個(gè)離散型分類字段。European Soccer 是一種收集于電子游戲的數(shù)據(jù)集，記錄了歐洲國家足球賽事、隊(duì)伍、球員等詳細(xì)信息，數(shù)據(jù)庫文件大小為300 MB。它包含了隊(duì)伍特征和球員屬性兩張寬表（具有較多數(shù)值類型字段），以及五張普通表（具有少量文本和數(shù)值類型字段），其中球員屬性表的記錄數(shù)多達(dá)18萬條，整個(gè)數(shù)據(jù)集共計(jì)20個(gè)離散型分類字段。

5.2 評(píng)估產(chǎn)生候選聚合代數(shù)約束效果

實(shí)驗(yàn)統(tǒng)計(jì)了各數(shù)據(jù)集產(chǎn)生候選約束的效果。結(jié)果如表1所示，其中PR_TBL 表示產(chǎn)生配對(duì)規(guī)則階段剪枝兩表均僅含有少量記錄的配對(duì)規(guī)則，PR_INC、PR_NUL分別表示產(chǎn)生配對(duì)規(guī)則階段剪枝由自增字段、NULL值過多的字段組成類外鍵約束的配對(duì)規(guī)則，GR_INC、GR_NUL 分別表示產(chǎn)生分組規(guī)則階段剪枝由自增字段、NULL 值過多字段組成的分組規(guī)則，GR_IDX 表示產(chǎn)生分組規(guī)則階段剪枝由唯一性約束的字段組成的分組規(guī)則，GR_ATTR 表示剪枝分組字段由事實(shí)唯一字段組成的分組規(guī)則。OP_FAKE 表示代數(shù)表達(dá)式無效的剪枝，OP_RE 表示冗余候選聚合代數(shù)約束的剪枝。從表1 可以看出，一條候選約束可命中多條剪枝規(guī)則，剪枝規(guī)則間效果差異巨大，這與數(shù)據(jù)集特征密切相關(guān)。

表1 不同剪枝規(guī)則效果Tab.1 Effect for different pruning rules

各階段剪枝規(guī)則產(chǎn)生效果對(duì)比如表2 所示。在不剪枝時(shí)樸素的枚舉算法生成了數(shù)量龐大的結(jié)果，使用剪枝規(guī)則時(shí)大幅縮小了候選約束集合規(guī)模。在表2 中，剪枝后的分組規(guī)則數(shù)比配對(duì)規(guī)則數(shù)量更少，是由部分配對(duì)規(guī)則無法產(chǎn)生有效分組規(guī)則導(dǎo)致的。由表可知，即便European Soccer 數(shù)據(jù)集具有更多的列，但是其列大多數(shù)具有唯一性約束或列值具有事實(shí)唯一的特征，因此剪枝后的約束數(shù)量并未多于TPC-H 數(shù)據(jù)集的數(shù)量。此外，分組規(guī)則對(duì)配對(duì)規(guī)則的擴(kuò)張并不明顯，但候選約束對(duì)分組規(guī)則的擴(kuò)張十分顯著，如含有寬表的European Soccer 數(shù)據(jù)集枚舉代數(shù)表達(dá)式時(shí)產(chǎn)生了更多倍數(shù)的結(jié)果，使用剪枝規(guī)則可以收束各階段產(chǎn)生規(guī)則的放大效應(yīng)。

表2 各階段產(chǎn)生候選約束結(jié)果數(shù)量對(duì)比Tab.2 Result number comparison for candidate constraint production at different stages

5.3 評(píng)估產(chǎn)生候選聚合代數(shù)約束值域集合效果

在第3 章介紹的所有剪枝規(guī)則產(chǎn)生候選聚合代數(shù)約束集合的基礎(chǔ)上，實(shí)驗(yàn)對(duì)比了不使用任何優(yōu)化策略（簡(jiǎn)記為baseline）、僅復(fù)用中間結(jié)果（簡(jiǎn)記為RE，4.1 節(jié)）以及同時(shí)復(fù)用中間結(jié)果和消除平凡候選聚合代數(shù)約束（簡(jiǎn)記為RE+EL，4.1節(jié)和4.2節(jié)）三種執(zhí)行方案的效果。

各方案運(yùn)行耗時(shí)結(jié)果如表3 所示?？梢灾庇^地看出，AAC-Hunter 算法設(shè)計(jì)的方案大幅提高了程序的執(zhí)行速度，RE+EL 方案相對(duì)于baseline 方案在TPC-H 和European Soccer數(shù)據(jù)集上分別減小了95.68%和99.94%的約束發(fā)現(xiàn)空間，縮短了96.58%和92.51%的運(yùn)行時(shí)間。通過baseline 和RE 方案實(shí)驗(yàn)結(jié)果的對(duì)比，RE方案明確可以在不改變結(jié)果數(shù)量的前提下提升值域集合計(jì)算的效率，這符合復(fù)用中間結(jié)果技術(shù)的消除公共子操作效果。

表3 不同執(zhí)行方案的運(yùn)行耗時(shí)、結(jié)果數(shù)量對(duì)比Tab.3 Running time and result number comparison of different execution schemes

值得一提的是，表3 中European Soccer 數(shù)據(jù)集中僅使用RE 方案卻比使用RE+EL 復(fù)合方案略微高效，是由于該數(shù)據(jù)集計(jì)算約束值域集合的過程并未受益于可能減少結(jié)果數(shù)的RE+EL 方案（表3 中RE+EL 方案、RE 方案的相同結(jié)果數(shù)說明了這一點(diǎn)），這符合式（6）所表達(dá)的含義。對(duì)于消除平凡候選聚合代數(shù)約束技術(shù)而言，既會(huì)因?yàn)闄z查規(guī)則有效性而進(jìn)行額外計(jì)算，又可能通過消除平凡候選約束間接減少更為耗時(shí)的值域集合計(jì)算，通常收益遠(yuǎn)大于代價(jià)；然而即便應(yīng)用消除平凡候選聚合代數(shù)約束技術(shù)未有收獲，從結(jié)果可以看出，其代價(jià)并非難以接受。

6 結(jié)語

本文提出了AAC-Hunter，一個(gè)從關(guān)系數(shù)據(jù)庫中高效地發(fā)現(xiàn)聚合代數(shù)約束的算法。AAC-Hunter 采用一系列啟發(fā)式規(guī)則減小了候選聚合代數(shù)約束集合的大小，并優(yōu)化了候選聚合代數(shù)約束的值域集合計(jì)算。AAC-Hunter 與基線算法的對(duì)比實(shí)驗(yàn)表明，提出的優(yōu)化技術(shù)顯著縮短了發(fā)現(xiàn)聚合代數(shù)約束所需的計(jì)算時(shí)間。