基于詞嵌入的元組級(jí)數(shù)據(jù)溯源方法

楊 彬,高俊濤,王志寶,李 菲,馬 強(qiáng),江樹濤

(1.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,黑龍江 大慶 163318;2.黑龍江八一農(nóng)墾大學(xué) 信息與電氣工程學(xué)院,黑龍江 大慶 163319)

0 引 言

在大數(shù)據(jù)時(shí)代下數(shù)據(jù)生成規(guī)模激增,原生數(shù)據(jù)經(jīng)過多次復(fù)制、遷移、集成、抽取等操作后形成海量派生數(shù)據(jù),使數(shù)據(jù)來源及衍生路徑表現(xiàn)出多樣化、復(fù)雜化的特點(diǎn)[1]。若原生數(shù)據(jù)的來源模糊不清,則會(huì)極大程度地影響派生數(shù)據(jù)的可靠性[2]。數(shù)據(jù)溯源技術(shù)能夠監(jiān)控與評(píng)估數(shù)據(jù)質(zhì)量,有助于定位錯(cuò)誤根因,追蹤錯(cuò)誤路徑,還可以對(duì)數(shù)據(jù)進(jìn)行安全管控,能夠幫助企業(yè)確定字段敏感信息。數(shù)據(jù)的可靠性和安全性是有效決策的基礎(chǔ),為加強(qiáng)數(shù)據(jù)質(zhì)量,由此產(chǎn)生了數(shù)據(jù)溯源技術(shù)[3]。

目前數(shù)據(jù)溯源在溯源理論、溯源模型以及方法實(shí)踐上都開展了研究工作,但仍有不足,標(biāo)注法的實(shí)現(xiàn)需要為元組保存完整的半環(huán)多項(xiàng)式(即標(biāo)注),由于通過查詢產(chǎn)生的元組依賴于先前查詢的元組,導(dǎo)致半環(huán)多項(xiàng)式的數(shù)量大量增長(zhǎng),存在存儲(chǔ)空間爆炸的問題。因此,國(guó)外學(xué)者Leybovich M等[4]提出基于詞嵌入的元組級(jí)數(shù)據(jù)溯源方法,該方法有效避免存儲(chǔ)數(shù)據(jù)標(biāo)注。文中主要貢獻(xiàn)如下:

(1)在元組向量化編碼機(jī)制的基礎(chǔ)上給出屬性重要性優(yōu)化算法,解決詞嵌入方法中溯源精確率低的問題。

(2)引入近似最近鄰搜索算法后又給出元組過濾優(yōu)化策略,解決時(shí)間消耗長(zhǎng)溯源效率低的問題。

1 相關(guān)工作

目前在數(shù)據(jù)溯源研究中主要有以下幾方面工作。從溯源概念上,Lanter[5]首次提出“Data Lineage”用以描述目標(biāo)數(shù)據(jù)的來源轉(zhuǎn)化過程。Cui等[6]從關(guān)系代數(shù)角度出發(fā),定義了View Data Lineage用來標(biāo)識(shí)數(shù)據(jù)倉(cāng)庫(kù)視圖中目標(biāo)數(shù)據(jù)的源數(shù)項(xiàng)集。Buneman等[7]進(jìn)一步將數(shù)據(jù)溯源進(jìn)行分類,提出了why溯源和where溯源。Green等[8]以半環(huán)多項(xiàng)式的形式提出了how溯源。從溯源粒度上,數(shù)據(jù)溯源被分為3個(gè)不同層次,第1層次是表級(jí)的數(shù)據(jù)溯源,其目標(biāo)是獲得目標(biāo)表與源表之間的轉(zhuǎn)換,是一種粗粒度的數(shù)據(jù)溯源;第2層次是字段級(jí)(列)的數(shù)據(jù)溯源,其目標(biāo)是獲得源表字段和目標(biāo)表字段之間的屬性映射關(guān)系,它是表級(jí)溯源的細(xì)化;第3層次是元組級(jí)(行)的數(shù)據(jù)溯源,其目標(biāo)是獲得目標(biāo)表元組的源元組集合,是一種細(xì)粒度的數(shù)據(jù)溯源[9]。

從溯源模型上,W3C發(fā)布的PROV[10]是目前為止最成功的模型,成為數(shù)據(jù)溯源史上的里程碑。此后,圍繞PROV,專家學(xué)者對(duì)各個(gè)領(lǐng)域進(jìn)行深入更深層次的研究。Niu X等[11]將PROV引入關(guān)系數(shù)據(jù)庫(kù),將溯源信息存儲(chǔ)成PROV-JSON的形式進(jìn)行數(shù)據(jù)溯源。燕楊月[12]將PROV應(yīng)用到物聯(lián)網(wǎng)數(shù)據(jù)場(chǎng)景,實(shí)現(xiàn)對(duì)物聯(lián)網(wǎng)起源信息的描述。楊斐斐等[13]對(duì)PROV進(jìn)行擴(kuò)展,構(gòu)建了面向數(shù)據(jù)融合的溯源模型─PROV-Semi。

從溯源方法上,林悅邦[14]和張苒[15]等對(duì)支持全特性查詢語言的逆置函數(shù)溯源方法進(jìn)行研究。逆置函數(shù)法是指在計(jì)算時(shí)通過逆向查詢或構(gòu)造逆向函數(shù)對(duì)查詢求逆,求逆的結(jié)果就是目標(biāo)數(shù)據(jù)的源數(shù)據(jù)。其優(yōu)點(diǎn)是只需存儲(chǔ)少量的元數(shù)據(jù)就可實(shí)現(xiàn)數(shù)據(jù)溯源;缺點(diǎn)是具有一定局限性,需要提供逆置函數(shù)(并不是所有的函數(shù)都具有可逆性)和相對(duì)應(yīng)的驗(yàn)證函數(shù)。Leybovich M等[4,16]和Hofmann F A等[17]提出一種數(shù)據(jù)溯源的近似總結(jié)方法,其優(yōu)點(diǎn)是可應(yīng)用于派生數(shù)據(jù)更為膨脹的海量數(shù)據(jù)場(chǎng)景;缺點(diǎn)是以丟失一些信息為代價(jià)壓縮表示溯源信息。Pierre Senellar等[18-19]開發(fā)的ProvSQL系統(tǒng)[20]利用標(biāo)注法實(shí)現(xiàn)元組級(jí)數(shù)據(jù)溯源。標(biāo)注法是指記錄數(shù)據(jù)的出處、產(chǎn)生過程、流轉(zhuǎn)信息等作為數(shù)據(jù)標(biāo)注,通過查詢目標(biāo)數(shù)據(jù)的標(biāo)注來獲得數(shù)據(jù)的溯源信息。其優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單,且容易管理;缺點(diǎn)是需要詳細(xì)記錄所有的數(shù)據(jù)轉(zhuǎn)換信息,會(huì)出現(xiàn)元數(shù)據(jù)多于原始數(shù)據(jù)的情況。在實(shí)際應(yīng)用中,細(xì)粒度形式的溯源信息標(biāo)注通常會(huì)產(chǎn)成大容量存儲(chǔ),如何優(yōu)化關(guān)系數(shù)據(jù)庫(kù)下的溯源方法,成為亟待破解的難題[21]。

2 溯源定義及問題描述

2.1 元組級(jí)數(shù)據(jù)溯源

2.2 問題描述

該文的主要內(nèi)容是:研究元組級(jí)數(shù)據(jù)溯源方法,為數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)中元組的存在提供解釋。即給定一個(gè)查詢(Q)和查詢輸出的數(shù)據(jù)元組集合(T),在來源表中找出對(duì)產(chǎn)生每個(gè)元組(t∈T)有貢獻(xiàn)的源數(shù)據(jù)元組集合(S)。

示例1:SQL語句示例用來幫助理解元組級(jí)數(shù)據(jù)溯源定義。

Q: INSERT INTO results(title, rating, timestamp)SELECT m.title,r.rating,r.timestampFROM ratings r,movies mWHERE m.movieId=r.movieIdAND r.userId=4;

表1(a)為執(zhí)行語句Q后獲得的查詢結(jié)果表(results),每個(gè)元組包含userId為4的用戶觀看的電影名,所給評(píng)分及評(píng)價(jià)時(shí)間。表1(b)為評(píng)價(jià)表(ratings),每個(gè)元組包含有關(guān)用戶表達(dá)的電影偏好的信息(0～5星評(píng)分)。表1(c)為電影表(movies),每個(gè)元組包含有關(guān)電影的基本信息。

表1 數(shù)據(jù)統(tǒng)計(jì)表

通過分析可以得到,表1(a)中標(biāo)注為q1的元組由表1(b)中標(biāo)注為r1的源元組和表1(c)中標(biāo)注為m1的源元組結(jié)合形成,如圖1所示,以此實(shí)現(xiàn)元組(q1)的一次溯源。

圖1 元組(q1)的溯源過程描述

同理,可以對(duì)目標(biāo)元組(q2,q3,q4)直至qn進(jìn)行溯源。并且可以對(duì)元組(r1,m1)向上溯源,最終形成一個(gè)有向無環(huán)圖,即全鏈路數(shù)據(jù)溯源關(guān)系圖。

3 元組級(jí)數(shù)據(jù)溯源方法

該文在ProvEmb[4]的基礎(chǔ)上增加了精確率優(yōu)化機(jī)制和搜索效率優(yōu)化機(jī)制,設(shè)計(jì)了一種基于詞嵌入技術(shù)的元組級(jí)數(shù)據(jù)溯源改進(jìn)方法(ProvEmb-X),其想法受生物學(xué)“基因”的啟發(fā),使尋找元組的源數(shù)據(jù)類似于通過DNA查找其前輩。

3.1 方法框架

圖2為文中方法的研究框架,該方法支持范圍廣泛的非聚合SQL查詢。輸入數(shù)據(jù)是執(zhí)行SQL后的查詢結(jié)果元組集(即目標(biāo)元組),輸出數(shù)據(jù)是為該條元組返回其源元組id,目的是對(duì)目標(biāo)元組集中的每一條元組進(jìn)行溯源。基本方法首先是通過一組向量來代表每個(gè)元組。其次,通過計(jì)算源表元組向量與目標(biāo)元組向量的相似度,來識(shí)別溯源關(guān)系。再次,對(duì)僅依賴相似度比較導(dǎo)致相似的元組間可能沒有溯源關(guān)系的問題,給出優(yōu)化方案提高精確率,并對(duì)溯源效率進(jìn)行優(yōu)化以減少時(shí)間消耗。最后,與基于詞嵌入的數(shù)據(jù)溯源方法(ProvEmb)進(jìn)行對(duì)比,驗(yàn)證文中方法的優(yōu)化效果。該方法具有以下特點(diǎn):

圖2 ProvEmb-X方法框架

(1)該方法適合大規(guī)模數(shù)據(jù)集。通過分析SQL語句來精準(zhǔn)定位所需要的數(shù)據(jù)庫(kù)表,即便是派生數(shù)據(jù)更為膨脹的海量數(shù)據(jù)場(chǎng)景,仍可以快速過濾無用數(shù)據(jù)。

(2)該方法支持復(fù)雜的數(shù)據(jù)變換。可解決范圍廣泛的非聚合SQL查詢的數(shù)據(jù)溯源問題,通過解析SQL語句中的連接、選擇、分組、投影、集合和排序操作獲取查詢結(jié)果字段(目標(biāo)字段)與數(shù)據(jù)庫(kù)源表字段的對(duì)應(yīng)關(guān)系,進(jìn)而應(yīng)用到方法中的屬性重要性優(yōu)化機(jī)制。

(3)該方法可實(shí)現(xiàn)自動(dòng)化溯源。無論是純手工收集的標(biāo)注法,還是基于SQL的半自動(dòng)標(biāo)注法,都需要進(jìn)行人工標(biāo)注的工作。文中方法可實(shí)現(xiàn)自動(dòng)化,提高溯源效率。

3.2 元組向量化編碼機(jī)制

該文在元組向量化編碼機(jī)制中進(jìn)行目標(biāo)元組向量和源表元組向量的兩部分編碼。該文使用NLP技術(shù),詞向量通過預(yù)訓(xùn)練的多語言詞嵌入模型在基礎(chǔ)文本上獲得。文中元組向量化編碼機(jī)制與ProvEmb不同的是,ProvEmb是將元組中的每個(gè)列的文本組合起來形成一條沒有語義的句子后進(jìn)行詞嵌入,該文是直接將每個(gè)元組中不同列的文本進(jìn)行詞嵌入后再組合,為后續(xù)屬性重要性優(yōu)化機(jī)制提高溯源精確率做準(zhǔn)備。算法1為元組向量生成算法。

算法1:元組向量生成算法(TPVEC)

輸入:預(yù)訓(xùn)練的詞嵌入模型(ST),輸入數(shù)據(jù)表(Ti)

輸出:為Ti中的每個(gè)元組(t)計(jì)算其元組向量(vectort)并存在tuplevector中

1. list vectort//存儲(chǔ)每列文本的詞向量

2. list tuplevector //存儲(chǔ)生成的元組向量集

3. fort∈Ti.tuples do //遍歷Ti中的每個(gè)元組

4.vectort=create(t) //調(diào)用對(duì)t構(gòu)造元組向量方法

5.tuplevector.append(vectort)

6.end for

7. return tuplevector

8. function create(t) //定義構(gòu)造元組向量方法

9. list wordvector

10. list tuplevector

11.//w是t中的每列文本,[]為構(gòu)造wordvector列表

12. wordvector=[ST(w)|w∈t]

13. vectort=weight(wordvector)

14. return vectort

4 溯源方法優(yōu)化機(jī)制

由于僅依賴目標(biāo)元組向量與源元組向量的相似性,會(huì)出現(xiàn)兩者間并無溯源關(guān)系,卻還是錯(cuò)誤地將該元組識(shí)別為溯源結(jié)果的情況。因此,該文提出了改進(jìn)方案,通過以下4個(gè)步驟使算法在溯源精確率和效率上有較大的提升。(1)使用局部敏感哈希算法(LSH)提高溯源效率。(2)通過解析查詢語句中FROM條件直接定位源表,初次過濾無關(guān)元組集合。(3)利用時(shí)間戳過濾目標(biāo)元組的派生元組,再次過濾無關(guān)元組集合。(4)對(duì)于元組中的關(guān)鍵屬性,采用加強(qiáng)其特征再組合的方式,形成獨(dú)有的遺傳密碼“基因”,從而提高溯源精確率。

4.1 近似最近鄰搜索

在進(jìn)行實(shí)驗(yàn)時(shí)發(fā)現(xiàn),暴力窮舉式掃描對(duì)源表元組向量和目標(biāo)元組向量進(jìn)行相似度比較時(shí),時(shí)間復(fù)雜度為O(dN),當(dāng)數(shù)據(jù)的維度(d)以及數(shù)據(jù)的規(guī)模很大時(shí),巨大的計(jì)算量與存儲(chǔ)需求使得該搜索方式難以在效率上滿足需求。

針對(duì)此問題,為滿足大規(guī)模數(shù)據(jù)場(chǎng)景下的最近鄰搜索任務(wù)需求,該文采用局部敏感度哈希算法(LSH)進(jìn)行高維向量近似最近鄰搜索(ANN),在損失一定精度的條件下,能夠有效平衡精度與資源消耗,以更快的搜索速度和更少的內(nèi)存負(fù)載得到查詢項(xiàng)的近似精確甚至精確的搜索結(jié)果。LSH的基本思想是將原高維空間的點(diǎn)都映射至1個(gè)或多個(gè)哈希表的不同位置(桶),原高維空間內(nèi)距離較近的點(diǎn)會(huì)以較大概率映射至同一桶內(nèi),從而可直接在該桶內(nèi)搜索元素,大大提高搜索效率。當(dāng)哈希函數(shù)(h)滿足以下兩個(gè)條件,稱h為局部敏感哈希函數(shù)[22]:

(1)如果L(q1,q2)

(2)如果L(q1,q2)>d2,則P[h(q1)=h(q2)]≥p2。

條件(1)保證2個(gè)相似點(diǎn)以較高概率被映射進(jìn)同一個(gè)哈希桶;條件(2)保證2個(gè)不相似的點(diǎn)以較低概率映射進(jìn)同一個(gè)哈希桶。其中,d1,d2,p1,p2是給定的常數(shù),d1

H(V)=sign(V·R)

(1)

其中,R是一個(gè)隨機(jī)向量,V·R可以看作是將V向R上進(jìn)行投影操作,其是(d1,d2,(180-d1)/180,(180-d2)/180)敏感。

4.2 元組過濾優(yōu)化機(jī)制

在對(duì)目標(biāo)元組溯源時(shí),源表中存在許多無關(guān)元組,若對(duì)這些無關(guān)元組也進(jìn)行詞嵌入生成元組向量,會(huì)浪費(fèi)大量時(shí)間。因此,在本節(jié)中通過2個(gè)步驟過濾無關(guān)元組,加快搜索效率并提高溯源的精確率。

首先,解析SQL語句中的FROM條件進(jìn)行篩選,因?yàn)镕ROM條件可以直接定位來源表,縮小查找范圍。然后,在篩選后的元組中使用算法2元組過濾算法(TPFIL),通過元組創(chuàng)建時(shí)間戳過濾元組,能夠幫助過濾掉非常相似但非源數(shù)據(jù)的元組,解決了完全依靠相似度的弊端,對(duì)查詢遠(yuǎn)距離數(shù)據(jù)溯源尤其重要且加快了源元組的搜索效率。

算法2:元組過濾算法(TPFIL)

輸入:源數(shù)據(jù)表(Ti),查詢結(jié)果表(R)

輸出:經(jīng)過where條件和時(shí)間戳過濾后的元組向量集(tuplevector)

1.list tuplevector

2.list vectort

4.//對(duì)每條查詢結(jié)果元組在源表中進(jìn)行時(shí)間戳過濾

5.fort∈R.tuples do

7. ift'.timestamp>t.timestamp

8. //調(diào)用構(gòu)造元組向量方法,將t作為參數(shù)傳入

9. vectort=create(t)

10. tuplevector.append(vectort)

11. end if

12. end for

13.end for

14.return tuplevector

(1)跟蹤元組的創(chuàng)建時(shí)間戳。

①如果元組(t)被直接插入到DB,則t.timestamp是其插入時(shí)間。

②如果元組(t)是通過查詢計(jì)算的,則t.timestamp是查詢的執(zhí)行時(shí)間。

(2)當(dāng)將一個(gè)元組(t)與一組其他元組(T')進(jìn)行比較時(shí),該文在計(jì)算元組向量生成之前進(jìn)行判斷:如果t'.timestamp>t.timestamp (t'∈T'),則t'比t更新,并且不能成為其源元組的一部分。

4.3 屬性重要性優(yōu)化機(jī)制

由于TPVEC生成的元組向量不具備其本身特征,因此會(huì)導(dǎo)致溯源結(jié)果的精確率不高。為提高精確率,對(duì)數(shù)據(jù)庫(kù)表結(jié)構(gòu)進(jìn)行研究發(fā)現(xiàn),某些屬性可能比其他屬性更重要。例如,主鍵、外鍵或者是某些參與了數(shù)據(jù)庫(kù)查詢的重要屬性。這意味著可以通過給這些屬性的詞向量賦予較高權(quán)重的方法來加強(qiáng)此元組向量的特征,進(jìn)而提高相似度匹配的精確率。

該文通過解析SQL語句的方式尋找真正參與SQL運(yùn)算的源屬性和目標(biāo)屬性。解析SQL語句的主要步驟為:首先,對(duì)SQL查詢語句進(jìn)行詞法分析和語法分析得到抽象語法樹。然后,遍歷以Root為節(jié)點(diǎn)的抽象語法樹,得到INSERT INTO target_table(target_attribute_list)目標(biāo)表(目標(biāo)屬性)、SelectList源屬性、FromClause源表,再遍歷WhereClause沒有聚合函數(shù)的選擇操作、GroupClause分組操作、HavingClause有聚合函數(shù)的選擇操作、SortClause排序操作等節(jié)點(diǎn),從中獲得目標(biāo)屬性和源屬性的對(duì)應(yīng)關(guān)系,以此來為目標(biāo)屬性和源屬性的詞向量加大權(quán)重。

以示例1所示的查詢語句為例,遍歷抽象語法樹后得到的可視化關(guān)系如圖3(a)所示。由圖3(b)可知結(jié)果表(results)中title來自于movies表,rating和timestamp來自于ratings表。因此在movies表中元組向量生成時(shí),應(yīng)該為title賦予比movies表中其他屬性要高的權(quán)重,說明title更能代表movies中元組的特征。同樣,results中的title權(quán)重也要加大。因此對(duì)每個(gè)屬性進(jìn)行詞嵌入,將詞向量加權(quán)平均生成元組向量后,再計(jì)算相似度從而提高匹配的精確率。權(quán)重計(jì)算公式如下所示(對(duì)于?wi都有0≤wi≤1):

圖3 屬性權(quán)重獲取流程

(1)moviesvectort=w1×movieId+w2×title (w1

(2)resultsvectort=w1×title+w2×rating+w3×timestamp (w1>w2,w1>w3且w1+w2+w3=1)

在ratings表中的元組向量生成時(shí),需要為rating和timestamp賦予較高的權(quán)重,且results表中也要加大其對(duì)應(yīng)的權(quán)重,權(quán)重計(jì)算公式如下所示(對(duì)于?wi都有0≤wi≤1):

(1)ratingsvectort=w1×userId+w2×movieId+w3×rating+w4×timestamp(w3=w4>w1,w3=w4>w2且w1+w2+w3+w4=1)

(2)resultsvectort=w1×title+w2×rating+w3×timestamp(w1

算法3為屬性權(quán)重獲取算法,該算法結(jié)合深度優(yōu)先搜索的思想,遞歸調(diào)用visit方法獲取目標(biāo)表屬性和源表屬性的對(duì)應(yīng)關(guān)系用attribute_r_list存放,即應(yīng)賦予高權(quán)重的重要屬性。后執(zhí)行算法1(TPVEC),并更改由算法3(PREUP)生成的重要屬性的weight值。

算法3:屬性權(quán)重獲取算法(PREUP)

輸入:數(shù)據(jù)庫(kù)語句(Q)

輸出:目標(biāo)表屬性與源表屬性的對(duì)應(yīng)關(guān)系attribute_r_list

1.Procedure AnalyzeDatalineage(Q)

2.List results_r_list //存放目標(biāo)表的表名和目標(biāo)屬性的關(guān)系

3.List source_r_list //存放源表表名和源表屬性的關(guān)系

4.List attribute_r_list //存放目標(biāo)表屬性和源表屬性的關(guān)系

5.QT←generateSQLAST(Q); //根據(jù)語句(Q),生成抽象語法樹(QT)

6.Function visit(r) //對(duì)根節(jié)點(diǎn)為r的抽象語法樹(QT)進(jìn)行遍歷

7.ifR(r)≠?then

8.String results_table //初始化,定義變量string型

9.String source_table

10.String results_attribute

11. forcin childs do //對(duì)節(jié)點(diǎn)進(jìn)行類型判斷

12. //如果節(jié)點(diǎn)c是結(jié)果表類型

14.results_table←c//記錄結(jié)果表表名

17.results_r_list←([results_table,c])

19.source_table←c//記錄源表表名

24.attribute_r_list←([results_attribute,c] )

25. Else ifR(r)≠? then

26.visit(c)

27. End if

28. End for

29.End if

30. Return attribute_r_list

綜上所述,文中方法在第1階段元組過濾優(yōu)化機(jī)制時(shí),FROM過濾源表的時(shí)間復(fù)雜度為O(m),共m個(gè)源表,每個(gè)表有k個(gè)元組n個(gè)屬性。時(shí)間戳過濾元組的時(shí)間復(fù)雜度為O(i·k·m'),表示進(jìn)行i·k·m'次比較,i為目標(biāo)元組數(shù),m'為FROM過濾后的源表數(shù)量;在第2階段屬性重要性優(yōu)化機(jī)制的時(shí)間復(fù)雜度為O(max(m'·n'+j'+1)),n'為遍歷抽象語法樹得到的源表的重要屬性,j'為遍歷抽象語法樹得到的目標(biāo)表的重要屬性(j為目標(biāo)表的所有屬性);在第3階段元組向量生成時(shí)的時(shí)間復(fù)雜度為O(i·j'+k'·n'·m'),k'為時(shí)間戳過濾后得到的元組;在第4階段近似近鄰搜索的時(shí)間復(fù)雜度為O(i·j')。因此,ProvEmb-X的時(shí)間復(fù)雜度為O(max(m'·k'·n'+i·m'·k)),而ProvEmb為O(max(m·k·n+i·m·k)),m'·k'·n'遠(yuǎn)遠(yuǎn)小于m·k·n。由此可知,文中方法能夠有效降低時(shí)間復(fù)雜度。

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

基于提出的ProvEmb-X元組級(jí)數(shù)據(jù)溯源方法,在3種不同的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),并與精確溯源系統(tǒng)ProvSQL[20]進(jìn)行對(duì)比,驗(yàn)證ProvEmb-X的精確率;與ProvEmb[4]進(jìn)行對(duì)比,驗(yàn)證ProvEmb-X的優(yōu)化效果;最后展示對(duì)比實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)環(huán)境為:Intel(R) Core(TM)i7,16 GB內(nèi)存,Windows 10操作系統(tǒng)。

5.1 實(shí)驗(yàn)數(shù)據(jù)

MovieLens數(shù)據(jù)集描述MovieLens電影[23]推薦系統(tǒng)網(wǎng)站中人們對(duì)電影的喜愛程度,數(shù)據(jù)集中的每部電影都有一個(gè)唯一標(biāo)識(shí)符movieId。固井作業(yè)數(shù)據(jù)集來自中國(guó)石油冀東油田公司實(shí)際固井?dāng)?shù)據(jù),數(shù)據(jù)集中的每個(gè)井筒都有唯一標(biāo)識(shí)符wellbore_id。Olist電子商務(wù)數(shù)據(jù)集[24]來自巴西市場(chǎng)上最大的百貨商店Olist,數(shù)據(jù)集中的每個(gè)訂單都有一個(gè)唯一標(biāo)識(shí)符order_id。

數(shù)據(jù)集統(tǒng)計(jì)信息如表2所示。

表2 數(shù)據(jù)集統(tǒng)計(jì)信息

5.2 實(shí)驗(yàn)結(jié)果及分析

5.2.1 精確率對(duì)比

(1)精確率評(píng)價(jià)指標(biāo)。

ProvSQL是基于標(biāo)注的方法,由Pierre Senellart等人開發(fā)的開源項(xiàng)目,支持范圍廣泛的非聚合SQL查詢,是目前為止較為精確的數(shù)據(jù)溯源系統(tǒng)。因此,該文使用公式(2)來計(jì)算實(shí)驗(yàn)結(jié)果的精確率,ApproxLineage(t)是該文實(shí)驗(yàn)結(jié)果元組的集合。ExactLineage(t)是由ProvSQL系統(tǒng)返回的關(guān)于t的精確源元組集合。Precision(t)代表返回的近似溯源結(jié)果與精確溯源結(jié)果的重合占比,該文將所得到的重合占比結(jié)果作為精確率的評(píng)價(jià)指標(biāo)。

Precision(t)=

(2)

(2)精確率優(yōu)化消融實(shí)驗(yàn)。

在3種數(shù)據(jù)集上分別對(duì)70條SQL語句的查詢結(jié)果進(jìn)行溯源,將平均精確率作為實(shí)驗(yàn)結(jié)果。

由表3的精確率對(duì)比結(jié)果可知,ProvEmb-X在3種數(shù)據(jù)集上的精確率均優(yōu)于ProvEmb(baseline)。在Movielens數(shù)據(jù)集和Olist電子商務(wù)數(shù)據(jù)集上的精確率優(yōu)化效果不如固井作業(yè)數(shù)據(jù)集明顯,是由于固井作業(yè)數(shù)據(jù)集中屬性數(shù)量較多,由w/o PREUP與完整的ProvEmb-X相差0.07左右可以看出,PREUP算法在極大程度地發(fā)揮作用提高精確率。由圖4(a)的增長(zhǎng)情況也可得知PREUP算法表現(xiàn)較好。最終結(jié)果顯示,在Movielens數(shù)據(jù)集上精確率整體提高了2.35%,在固井作業(yè)數(shù)據(jù)集上精確率提高了10.08%,在Olist電子商務(wù)數(shù)據(jù)集上精確率提高了3.53%。

圖4 對(duì)比實(shí)驗(yàn)結(jié)果

表3 消融實(shí)驗(yàn)結(jié)果

5.2.2 溯源效率對(duì)比

(1)溯源效率評(píng)價(jià)指標(biāo)。

該文將單條元組的溯源消耗時(shí)間作為溯源效率的評(píng)價(jià)指標(biāo),單位為分鐘。

(2)溯源效率優(yōu)化消融實(shí)驗(yàn)。

在3種數(shù)據(jù)集上分別對(duì)70條SQL語句的查詢結(jié)果進(jìn)行溯源,最后將單條平均耗時(shí)作為實(shí)驗(yàn)結(jié)果。

由表3溯源效率對(duì)比結(jié)果可知,ProvEmb-X在3種數(shù)據(jù)集上的時(shí)間消耗均小于ProvEmb。由w/o FROM與完整的ProvEmb-X差值得知“FROM定位”表現(xiàn)最為突出,其次是LSH算法。

由圖4(b)的4次對(duì)比實(shí)驗(yàn)可知,ProvEmb的窮舉式掃描對(duì)所有元組都進(jìn)行元組向量生成,計(jì)算量巨大導(dǎo)致消耗時(shí)間也相對(duì)較長(zhǎng)。因此,使用FROM+LSH算法將范圍固定在少部分相關(guān)元組中。但是在實(shí)驗(yàn)中發(fā)現(xiàn)耗時(shí)仍然過大,繼而使用TPVEC+LSH+TPFIL算法過濾非源數(shù)據(jù)的元組,再次縮短時(shí)間消耗。最終結(jié)果顯示,在Movielens數(shù)據(jù)集上耗時(shí)減少了13.13%,在固井作業(yè)數(shù)據(jù)集上減少了13.33%,在Olist電子商務(wù)數(shù)據(jù)集上減少了13.36%。

5.2.3 存儲(chǔ)開銷對(duì)比

該文采用計(jì)算ProvSQL/ProvEmb(-X)相對(duì)比例的方式,對(duì)比標(biāo)注法與詞嵌入法的存儲(chǔ)開銷,等于1代表存儲(chǔ)開銷一樣,小于1代表詞嵌入法開銷大,大于1代表標(biāo)注法開銷大,計(jì)算結(jié)果如表4所示。由結(jié)果可知標(biāo)注法與詞嵌入法的存儲(chǔ)比較相差較小,是因?yàn)槲闹袑?shí)驗(yàn)設(shè)備能力有限,實(shí)驗(yàn)數(shù)據(jù)體量相對(duì)較小且SQL語句數(shù)量較少,導(dǎo)致數(shù)據(jù)標(biāo)注占用的存儲(chǔ)空間不大,若是在大規(guī)模數(shù)據(jù)集上則會(huì)有較大的差異。且ProvEmb-X的存儲(chǔ)開銷比ProvEmb稍高,是由于在屬性重要性優(yōu)化機(jī)制階段對(duì)解析SQL語句得到的JSON進(jìn)行了存儲(chǔ)。

表4 存儲(chǔ)開銷相對(duì)比例

5.2.4 溯源結(jié)果展示

該文只對(duì)表1(a)中tid=8的元組results(Monty Python's Life of Brian (1979),3.5,1 573 944 005)進(jìn)行溯源結(jié)果展示。由于文章篇幅限制,在相關(guān)表中各取相似度排名較高的前7個(gè)元組,并對(duì)其在ProvSQL中進(jìn)行比較,最終實(shí)驗(yàn)結(jié)果如表5所示。其中,results表中tid=8的元組的直系源數(shù)據(jù)是由movies表中tid=1 053的元組和ratings表中tid=817的元組組合而成。其他元組為tid=8的元組的間接源元組,如圖5所示,可以清晰地展現(xiàn)tid=8的流轉(zhuǎn)路徑。

圖5 tid=8的元組溯源關(guān)系

表5 results表中tid=8實(shí)驗(yàn)結(jié)果

6 結(jié)束語

為解決傳統(tǒng)方法中存儲(chǔ)開銷大的問題,該文提出了基于詞嵌入的元組級(jí)數(shù)據(jù)溯源改進(jìn)方法,并通過實(shí)驗(yàn)證明了該方法的有效性和普適性。該方法可應(yīng)用于派生數(shù)據(jù)更為膨脹的海量數(shù)據(jù)場(chǎng)景,能夠有效追溯元組級(jí)數(shù)據(jù)的來源,并通過溯源方法優(yōu)化機(jī)制提高溯源精確率和時(shí)間效率,能夠作為元組級(jí)數(shù)據(jù)溯源的有效方法。

目前數(shù)據(jù)溯源領(lǐng)域的研究成果相對(duì)較少,基于詞嵌入的元組級(jí)數(shù)據(jù)溯源方法研究現(xiàn)仍然存在一些問題。通過計(jì)算相似度,以丟失一些信息為代價(jià)來壓縮海量信息,最終實(shí)現(xiàn)元組級(jí)數(shù)據(jù)溯源。下一步研究?jī)?nèi)容為如何進(jìn)一步提高精確率,以此來減少有用信息的丟失。并且目前在國(guó)內(nèi)外關(guān)于元組級(jí)數(shù)據(jù)溯源方法的研究中,都沒有解決聚合查詢的溯源問題,下一步也可由此展開研究,從而提高方法的適用范圍。