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

楊 彬,高俊濤,王志寶,李 菲,馬 強,江樹濤

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

0 引 言

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

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

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

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

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ù)據(jù)倉庫視圖中目標(biāo)數(shù)據(jù)的源數(shù)項集。Buneman等[7]進一步將數(shù)據(jù)溯源進行分類,提出了why溯源和where溯源。Green等[8]以半環(huán)多項式的形式提出了how溯源。從溯源粒度上,數(shù)據(jù)溯源被分為3個不同層次,第1層次是表級的數(shù)據(jù)溯源,其目標(biāo)是獲得目標(biāo)表與源表之間的轉(zhuǎn)換,是一種粗粒度的數(shù)據(jù)溯源;第2層次是字段級(列)的數(shù)據(jù)溯源,其目標(biāo)是獲得源表字段和目標(biāo)表字段之間的屬性映射關(guān)系,它是表級溯源的細化;第3層次是元組級(行)的數(shù)據(jù)溯源,其目標(biāo)是獲得目標(biāo)表元組的源元組集合,是一種細粒度的數(shù)據(jù)溯源[9]。

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

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

2 溯源定義及問題描述

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

2.2 問題描述

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

示例1:SQL語句示例用來幫助理解元組級數(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),每個元組包含userId為4的用戶觀看的電影名,所給評分及評價時間。表1(b)為評價表(ratings),每個元組包含有關(guān)用戶表達的電影偏好的信息(0～5星評分)。表1(c)為電影表(movies),每個元組包含有關(guān)電影的基本信息。

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

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

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

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

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

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

3.1 方法框架

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

圖2 ProvEmb-X方法框架

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

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

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

3.2 元組向量化編碼機制

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

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

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

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

1. list vectort//存儲每列文本的詞向量

2. list tuplevector //存儲生成的元組向量集

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

4.vectort=create(t) //調(diào)用對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)化機制

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

4.1 近似最近鄰搜索

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

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

(1)如果L(q1,q2)

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

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

H(V)=sign(V·R)

(1)

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

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

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

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

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

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

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

1.list tuplevector

2.list vectort

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

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)建時間戳。

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

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

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

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

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

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

以示例1所示的查詢語句為例,遍歷抽象語法樹后得到的可視化關(guān)系如圖3(a)所示。由圖3(b)可知結(jié)果表(results)中title來自于movies表,rating和timestamp來自于ratings表。因此在movies表中元組向量生成時,應(yīng)該為title賦予比movies表中其他屬性要高的權(quán)重,說明title更能代表movies中元組的特征。同樣,results中的title權(quán)重也要加大。因此對每個屬性進行詞嵌入,將詞向量加權(quán)平均生成元組向量后,再計算相似度從而提高匹配的精確率。權(quán)重計算公式如下所示(對于?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表中的元組向量生成時,需要為rating和timestamp賦予較高的權(quán)重,且results表中也要加大其對應(yīng)的權(quán)重,權(quán)重計算公式如下所示(對于?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)表屬性和源表屬性的對應(yīng)關(guān)系用attribute_r_list存放,即應(yīng)賦予高權(quán)重的重要屬性。后執(zhí)行算法1(TPVEC),并更改由算法3(PREUP)生成的重要屬性的weight值。

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

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

輸出:目標(biāo)表屬性與源表屬性的對應(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) //對根節(jié)點為r的抽象語法樹(QT)進行遍歷

7.ifR(r)≠?then

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

9.String source_table

10.String results_attribute

11. forcin childs do //對節(jié)點進行類型判斷

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

5 實 驗

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

5.1 實驗數(shù)據(jù)

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

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

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

5.2 實驗結(jié)果及分析

5.2.1 精確率對比

(1)精確率評價指標(biāo)。

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

Precision(t)=

(2)

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

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

由表3的精確率對比結(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)的增長情況也可得知PREUP算法表現(xiàn)較好。最終結(jié)果顯示,在Movielens數(shù)據(jù)集上精確率整體提高了2.35%,在固井作業(yè)數(shù)據(jù)集上精確率提高了10.08%,在Olist電子商務(wù)數(shù)據(jù)集上精確率提高了3.53%。

圖4 對比實驗結(jié)果

表3 消融實驗結(jié)果

5.2.2 溯源效率對比

(1)溯源效率評價指標(biāo)。

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

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

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

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

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

5.2.3 存儲開銷對比

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

表4 存儲開銷相對比例

5.2.4 溯源結(jié)果展示

該文只對表1(a)中tid=8的元組results(Monty Python's Life of Brian (1979),3.5,1 573 944 005)進行溯源結(jié)果展示。由于文章篇幅限制,在相關(guān)表中各取相似度排名較高的前7個元組,并對其在ProvSQL中進行比較,最終實驗結(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實驗結(jié)果

6 結(jié)束語

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

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