基于查詢特征表示學(xué)習(xí)的聯(lián)邦復(fù)雜查詢基數(shù)估計(jì)

徐 嬌,田萍芳,顧進(jìn)廣,徐芳芳

(1.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢 430065;2.湖北省智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,湖北 武漢 430065;3.武漢科技大學(xué) 大數(shù)據(jù)科學(xué)與工程研究院,湖北 武漢 430065;4.國(guó)家新聞出版署富媒體數(shù)字出版內(nèi)容組織與知識(shí)服務(wù)重點(diǎn)實(shí)驗(yàn)室,北京 100083)

0 引 言

準(zhǔn)確的基數(shù)估計(jì)是實(shí)現(xiàn)最佳查詢計(jì)劃的關(guān)鍵因素。現(xiàn)有方法大多基于深度學(xué)習(xí)來(lái)解決基數(shù)估計(jì)問(wèn)題,例如,在給定知識(shí)圖譜的情況下,Davitkova A等人[1]提出了LMKG方法來(lái)學(xué)習(xí)和估計(jì)最常用的查詢類型(即星形和鏈形查詢)的基數(shù),通過(guò)將圖模式的基數(shù)估計(jì)問(wèn)題表示為一個(gè)深度學(xué)習(xí)任務(wù),有效地捕獲不同子圖模式之間的相關(guān)性,從而提供非常準(zhǔn)確的估計(jì)結(jié)果。然而,這種基于RDF圖模式的方法專注于具有特定拓?fù)浣Y(jié)構(gòu)的簡(jiǎn)單查詢,適用范圍有限[2-3]。例如,在現(xiàn)實(shí)場(chǎng)景中,帶有FILTER或DISTINCT運(yùn)算符的復(fù)雜SPARQL語(yǔ)句構(gòu)成了一大類頻繁使用的查詢[4],但現(xiàn)有方法缺乏對(duì)這類復(fù)雜查詢的基數(shù)估計(jì)支持。

為了解決以上問(wèn)題,該文提出基于查詢特征表示學(xué)習(xí)的聯(lián)邦復(fù)雜查詢基數(shù)估計(jì)模型,以學(xué)習(xí)和預(yù)測(cè)輸入查詢的基數(shù)。模型包含兩個(gè)方法,基于全連接多層神經(jīng)網(wǎng)絡(luò)(Multi-Layer Perceptron,MLP)來(lái)預(yù)測(cè)結(jié)果。對(duì)于FILTER類查詢,將查詢表示為:頂點(diǎn)集、邊集、連接集和FILTER條件子句集四個(gè)特征,FILTER條件子句集使用新提出的特征化方法編碼,其他三個(gè)特征集則使用SG-Encoding進(jìn)行編碼,將合并的向量集作為參數(shù)輸入模型,模型預(yù)測(cè)查詢基數(shù)。而對(duì)于DISTINCT查詢,使用模型預(yù)測(cè)唯一行的比率。結(jié)果表明,該方法能得到更精確的基數(shù)估計(jì),具有實(shí)際應(yīng)用價(jià)值。

綜上所述,該文的貢獻(xiàn)可以歸納為:

(1)提出了一種FILTER查詢特征化的方法,分為簡(jiǎn)單范圍謂詞編碼和通用合取編碼,將編碼得到的特征向量作為模型的輸入,解決了SPARQL聯(lián)邦查詢向量化問(wèn)題;

(2)提出了一種基于MLP估計(jì)唯一率的方法,以實(shí)現(xiàn)DISTINCT查詢估計(jì)不包含重復(fù)項(xiàng)基數(shù)的功能;

(3)提出了基于查詢特征表示學(xué)習(xí)的聯(lián)邦復(fù)雜查詢基數(shù)估計(jì)模型,該模型可以學(xué)習(xí)并預(yù)測(cè)聯(lián)邦系統(tǒng)中包含F(xiàn)ILTER或DISTINCT關(guān)鍵字的SPARQL查詢。

1 相關(guān)工作

以往的研究表明,在WHERE子句中包含AND,OR和NOT運(yùn)算符的查詢構(gòu)成了一大類頻繁使用的查詢,它們的表達(dá)能力大致相當(dāng)于關(guān)系代數(shù),而在SPARQL系統(tǒng)中,這類查詢通常由FILTER運(yùn)算符進(jìn)行標(biāo)識(shí)和連接。此外,對(duì)于具有DISTINCT以及在計(jì)劃中的查詢,查詢規(guī)劃器需要集合論基數(shù),例如,在考慮排序選項(xiàng)時(shí)。因此,上述兩類查詢的基數(shù)估計(jì)對(duì)于查詢優(yōu)化非常重要[5-7]。另外,對(duì)于深度學(xué)習(xí)的基數(shù)估計(jì)而言,查詢特征化技術(shù)是必要的[8]。

深度學(xué)習(xí)用于基數(shù)估計(jì)在SQL領(lǐng)域已進(jìn)行了深入研究[9-17]。MSCN[7]模型基于神經(jīng)網(wǎng)絡(luò)來(lái)支持具有多個(gè)謂詞的基表和連接大小估計(jì),但其查詢特征化缺乏領(lǐng)域知識(shí)和可解釋性,因?yàn)樵谟?xùn)練過(guò)程中通過(guò)其結(jié)構(gòu)學(xué)習(xí)隱含的黑盒特征。Naru[18]使用自回歸模型來(lái)學(xué)習(xí)點(diǎn)查詢的條件聯(lián)合概率,但會(huì)增加范圍查詢的開銷,因?yàn)樗鼈兊墓烙?jì)是多個(gè)點(diǎn)查詢的總和。DeepDB[19]則在一定程度上依賴于采樣來(lái)尋找匹配的連接屬性構(gòu)建SPN。基于樹型門控循環(huán)單元的方法[20]同時(shí)對(duì)基數(shù)和代價(jià)進(jìn)行估計(jì),能夠有效學(xué)習(xí)計(jì)劃與基數(shù)和代價(jià)之間的高維關(guān)系,進(jìn)而給出精確的估計(jì)結(jié)果。

在SPARQL聯(lián)邦查詢中,SPLENDID[21]使用VOID統(tǒng)計(jì)信息和基于成本的基數(shù)估計(jì)模型為聯(lián)邦查詢選擇執(zhí)行計(jì)劃,但其成本模型沒(méi)有涵蓋分組、聚合和SERVICE子查詢等復(fù)雜查詢場(chǎng)景。Odyssey[22]基于特征集方法,在基數(shù)估計(jì)時(shí)考慮了使用DISTINCT修飾符的查詢,但所使用的共享相同屬性集的實(shí)體相似原則主要適用于星形查詢。CostFed[23]基于數(shù)據(jù)摘要文件來(lái)估計(jì)查詢成本,其中通過(guò)創(chuàng)建資源桶來(lái)考慮資源頻率分布的不對(duì)稱性,以至于對(duì)數(shù)據(jù)集中高頻三元組模式估計(jì)質(zhì)量好,但對(duì)于低頻三元組模式則表現(xiàn)較差。基于查詢特征表示學(xué)習(xí)的聯(lián)邦知識(shí)查詢基數(shù)估計(jì)方法[24]通過(guò)將SPARQL查詢表示為特征向量,使用CEFQR模型學(xué)習(xí)和預(yù)測(cè)查詢中的基數(shù)。雖然該模型在基數(shù)估計(jì)問(wèn)題上表現(xiàn)優(yōu)異,但是如上文所述,該方法缺乏對(duì)復(fù)雜查詢基數(shù)估計(jì)的支持。

受到SQL領(lǐng)域的啟發(fā),筆者認(rèn)為可以將SPARQL復(fù)雜聯(lián)邦查詢的基數(shù)估計(jì)問(wèn)題表示為一個(gè)監(jiān)督學(xué)習(xí)任務(wù),標(biāo)簽是實(shí)際基數(shù),輸入的是查詢特征,輸出的是預(yù)測(cè)的基數(shù)。相較于查詢特征表示學(xué)習(xí)的方法(CEFQR[24]),文中方法具有以下創(chuàng)新:首先,文中方法不再局限于簡(jiǎn)單聯(lián)邦查詢,而是將模型擴(kuò)展為支持復(fù)雜查詢的基數(shù)估計(jì)。相應(yīng)地,提出了復(fù)雜類查詢的編碼技術(shù);其次,文中模型除了預(yù)測(cè)SPARQL查詢的基數(shù)外,還能估計(jì)查詢中不重復(fù)結(jié)果的基數(shù),應(yīng)用范圍更廣泛。總得來(lái)說(shuō),文中模型更具實(shí)用價(jià)值。

2 基于查詢特征表示學(xué)習(xí)的聯(lián)邦復(fù)雜查詢基數(shù)估計(jì)模型

2.1 模型概述

模型的整體架構(gòu)如圖1所示。根據(jù)輸入查詢類型的不同,模型輸出相應(yīng)的預(yù)測(cè)值。當(dāng)輸入類型是包含F(xiàn)ILTER關(guān)鍵字的查詢時(shí),模型輸出預(yù)測(cè)基數(shù)Wout,相反,若為DISTINCT類查詢則輸出唯一率Rout。從輸入查詢到模型輸出預(yù)測(cè)結(jié)果主要經(jīng)歷三個(gè)階段:第一階段,將輸入查詢轉(zhuǎn)換成一組向量V,V由多個(gè)集合組成。對(duì)于FILTER類查詢,V=(A,X,E,F),其中A表示鄰接張量,X表示節(jié)點(diǎn)特征矩陣,E表示謂詞特征矩陣,F表示FILTER條件子句特征矩陣;而針對(duì)DISTINCT類查詢,V=(A,X,E)關(guān)于兩類查詢的編碼方式,A,X,E矩陣的特征化表示使用LMKG所提出的SG-Encoding編碼,F條件子句的編碼方式將在2.2節(jié)詳細(xì)介紹。第二階段,給定向量集合V,將V的每個(gè)向量作為MLPout的輸入,MLPmid是全連接的單層神經(jīng)網(wǎng)絡(luò)。然后MLPmid將V中的每個(gè)向量集合連接合并成H維向量Qvec,其中Qvec表示V中所有元素的單個(gè)轉(zhuǎn)換表示的平均值,即:

(1)

圖1 模型架構(gòu)

MLPmid(v)=ReLU(vUmid+bmid)

(2)

其中,Umid∈RLxH,bmid∈RH表示學(xué)習(xí)的權(quán)重和偏差,而v∈RL是輸入行向量。選擇一個(gè)平均值(而不是求和)來(lái)簡(jiǎn)化對(duì)集合V中不同數(shù)量元素的泛化。在第三階段,使用兩層神經(jīng)網(wǎng)絡(luò)MLPout估計(jì)查詢的預(yù)測(cè)基數(shù)Wout或唯一率Rout,對(duì)于FILTER類查詢,Wout=MLPout1(Qvec)。唯一率Rout的計(jì)算過(guò)程將在2.3節(jié)詳細(xì)討論。

模型對(duì)目標(biāo)基數(shù)C進(jìn)行歸一化:首先取對(duì)數(shù)使目標(biāo)值分布更均勻,然后使用從訓(xùn)練集獲得的對(duì)數(shù)化后的最小值和最大值來(lái)歸一化到區(qū)間[0,1]。歸一化是可逆的,因此模型可以對(duì)預(yù)測(cè)結(jié)果Wout∈[0,1]反歸一化得到預(yù)測(cè)基數(shù)。

模型的構(gòu)建包括兩個(gè)步驟。首先,生成一個(gè)隨機(jī)訓(xùn)練集。其次,使用訓(xùn)練集訓(xùn)練該模型,直到平均Q-error開始收斂到其最佳絕對(duì)值,Q-error被定義為估計(jì)值(Y)與真實(shí)值(y)之間的比率,如公式3。在訓(xùn)練階段,使用了早停技術(shù)。此外,實(shí)驗(yàn)使用TensorFlow[25]框架和Adam[26]訓(xùn)練優(yōu)化器來(lái)訓(xùn)練和測(cè)試模型。

(3)

2.2 FILTER查詢特征化方法

如上所示,該文重點(diǎn)關(guān)注對(duì)FILTER條件子句的編碼。

(1)簡(jiǎn)單范圍謂詞編碼。

對(duì)于匹配單個(gè)變量的范圍謂詞查詢,定義條件子句F=(var,op,val),var表示用于篩選的變量名,在使用SG-Encoding對(duì)(A,X,E)進(jìn)行編碼時(shí),會(huì)對(duì)子圖節(jié)點(diǎn)(主語(yǔ)和賓語(yǔ))和謂語(yǔ)進(jìn)行排序,之后創(chuàng)建Term-ID映射列表,var根據(jù)此列表進(jìn)行One-Hot編碼。op表示比較運(yùn)算符>,=,<中的任意一種,使用長(zhǎng)度為3的二進(jìn)制編碼。val表示比較的文字值,使用公式4將var歸一化為[0,1]范圍的val*。

(4)

在進(jìn)行范圍謂詞編碼時(shí),考慮了值的離散分布,將所有類型的點(diǎn)和范圍謂詞都編碼到封閉區(qū)間。例如,?x=5變成[5,5],?x≤5變成[Min(x),5]。當(dāng)條件子句的開放范圍很大時(shí),只需要對(duì)滿足篩選條件且在變量值域范圍內(nèi)的值進(jìn)行編碼,來(lái)減少特征化過(guò)程的時(shí)間,這對(duì)訓(xùn)練模型是很有益的。例如圖2,在Q1查詢中,給定max(?age)=50,min(?age)=15,對(duì)FILTER(?age<24)子句的編碼過(guò)程為:首先使用Term-ID映射列表將?age編碼為[10],然后根據(jù)變量的值域范圍將篩選謂詞限定為15

圖2 簡(jiǎn)單范圍謂詞編碼過(guò)程

(2)通用合取編碼。

對(duì)于具有多個(gè)變量且每個(gè)變量存在多個(gè)謂詞的范圍查詢,使用通用合取編碼。通過(guò)觀察發(fā)現(xiàn),當(dāng)條件子句中存在多個(gè)變量,且每個(gè)變量具有多個(gè)謂詞時(shí),變量必然屬于主語(yǔ)、謂語(yǔ)或賓語(yǔ)中的一類,那么滿足條件的值則一定存在于對(duì)應(yīng)節(jié)點(diǎn)的值域范圍內(nèi)。因此,編碼步驟簡(jiǎn)述為:(a)對(duì)每類節(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行分區(qū);(b)在特征向量中給每個(gè)分區(qū)一個(gè)條目;(c)給每個(gè)條目分配一個(gè)值,指示它所代表的分區(qū)是否滿足查詢Q中的謂詞,使用0表示沒(méi)有值滿足條件,1/2表示部分滿足,1表示都滿足。其中,每類節(jié)點(diǎn)N(N∈{s,p,o})的最大分區(qū)數(shù)為n(N)=min(n,max(N)-min(N)+1),n表示設(shè)定的最大分區(qū)數(shù)閾值。另外,特征向量中的條目v(v∈N)具有基于零的索引index(v),計(jì)算方式如式5。

(5)

最后,每類節(jié)點(diǎn)特征化的連接產(chǎn)生總的特征向量F。例如圖3,給定查詢Q2中涉及的主語(yǔ)和賓語(yǔ)的最值為:min(S)=-9,max(S)=50,min(O)=0,max(O)=115,并且n=12。對(duì)FILTER (?id<7&& ?age>10 &&?age<30)子句的編碼過(guò)程為:首先,對(duì)于?id<7,因?yàn)?id屬于主語(yǔ),所以計(jì)算它在S分區(qū)中的索引,根據(jù)公式5,index(?id)=3,則在S分區(qū)中第四個(gè)條目設(shè)置為1/2(索引從0開始),左側(cè)的所有條目均為1,表示小于7的值符合條件,相應(yīng)地,右邊的所有條目均設(shè)置為0。同理,按照上述步驟處理?age上的條件。最后得到向量F如圖3所示。

圖3 通用合取編碼過(guò)程

2.3 估計(jì)唯一率

對(duì)于DISTINCT類查詢,首先,給出唯一率的定義:如果SPARQL查詢Q在RDF數(shù)據(jù)集D上的執(zhí)行結(jié)果行(包含重復(fù))中有x%是唯一的,那么查詢Q在數(shù)據(jù)集D上的唯一率等于x%,計(jì)算公式為:

(6)

其中,QD表示Q在D上的基數(shù),運(yùn)算符‖ ‖返回去除重復(fù)的基數(shù), | |返回包含重復(fù)項(xiàng)的基數(shù)。

使用完全連接的雙層神經(jīng)網(wǎng)絡(luò)MLPout來(lái)計(jì)算輸入查詢的預(yù)測(cè)唯一率Rout。首先,MLPout將大小為H的Qvec向量作為輸入,然后使用第一層將輸入向量轉(zhuǎn)換為大小為0.5H向量,最后使用第二層將0.5H向量轉(zhuǎn)換為表示唯一率的單個(gè)值Rout,計(jì)算方式如下所示:

Rout=MLPout2(Qvec2)

(7)

MLPout2(v)=Sigmoid(ReLU(vUout1+bout1)Uout2+bout2)

(8)

其中,Rout是估計(jì)的唯一率,Uout1∈RHx0.5H,bout1∈R0.5H和Uout2∈R0.5Hx1,bout1∈R1是學(xué)習(xí)的的權(quán)重和偏差。

如上所述,使用經(jīng)驗(yàn)性強(qiáng)且快速的ReLU激活函數(shù)來(lái)評(píng)估所有神經(jīng)網(wǎng)絡(luò)中隱含層單元,唯一率的值分布在[0,1]范圍內(nèi)。在預(yù)測(cè)唯一率Rout時(shí),應(yīng)用第二層中的Sigmoid激活函數(shù)來(lái)輸出該范圍內(nèi)的浮點(diǎn)值。特別地,不對(duì)Rout做任何特征化,并且使用真實(shí)唯一率的值來(lái)訓(xùn)練模型,而不需要任何中間的特征化步驟。

值得注意的是,本模型對(duì)于DISTINCT類查詢,預(yù)測(cè)唯一行的比率是基于以下目的:希望在不改變現(xiàn)有基數(shù)估計(jì)模型的情況下擴(kuò)展模型以支持DISTINCT查詢。例如,給定SPARQL查詢Q,任意有限基數(shù)估計(jì)模型(估計(jì)結(jié)果中包含重復(fù)行的模型)M,設(shè)基數(shù)C=M(Q),C包含重復(fù)項(xiàng),通過(guò)執(zhí)行Rout·C即可得到集合論基數(shù)(不包含重復(fù)項(xiàng)基數(shù))。

2.4 訓(xùn)練數(shù)據(jù)

使用專門的查詢生成器獲得初始訓(xùn)練語(yǔ)料庫(kù)。生成初始語(yǔ)料庫(kù)分為兩個(gè)步驟。第一步,生成兩種類型的圖模式。對(duì)于星型子圖模式,隨機(jī)選取一個(gè)起始節(jié)點(diǎn),然后從該起始節(jié)點(diǎn)模擬一個(gè)隨機(jī)步長(zhǎng)m次,得到大小為m的星形圖模式。類似地,對(duì)于鏈模式,從隨機(jī)選擇的節(jié)點(diǎn)開始游走,并在大小達(dá)到n后停止。其中m和n的大小由縮小采樣的比例因子來(lái)決定。第二步,將圖模式轉(zhuǎn)換為示例查詢。示例查詢由三重模式,條件子句和查詢結(jié)果的真實(shí)基數(shù)構(gòu)成。首先,生成足夠數(shù)量的子圖模式后,將圖模式中包含的所有主語(yǔ)、謂語(yǔ)、賓語(yǔ)按行轉(zhuǎn)換成三重模式。在迭代轉(zhuǎn)換過(guò)程中,對(duì)于每個(gè)三重模式中未綁定的變量,將其加入候選變量集。其次,生成查詢的條件子句,條件子句由(var,op,val)組成,其中var從候選變量集中隨機(jī)生成一個(gè)變量,op則由操作符集{>,=,<}隨機(jī)生成單個(gè)操作符,val的值根據(jù)子圖中對(duì)應(yīng)的主語(yǔ)、謂語(yǔ)、賓語(yǔ)的值域隨機(jī)生成。特別地,當(dāng)某個(gè)三重模式的候選變量集的大小大于1時(shí),為該三重模式生成多個(gè)條件子句(≤候選變量集的大小),多個(gè)條件子句之間用&&連接。最后,發(fā)送由三重模式組成的SPARQL查詢獲取真實(shí)基數(shù),如果真實(shí)基數(shù)為0,則表示生成的查詢不合法,將其丟棄。第三步,樣本分類。執(zhí)行完上述步驟后,將所有包含條件子句的示例查詢加入語(yǔ)料庫(kù)1,用于訓(xùn)練 FILTER查詢的基數(shù)。其余查詢加入到語(yǔ)料庫(kù)2,用于估計(jì)唯一率。語(yǔ)料庫(kù)2的訓(xùn)練樣本由三重模式,查詢結(jié)果的真實(shí)唯一行比率組成。通過(guò)以上步驟,最終得到了文中模型的初始訓(xùn)練集。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

使用LUBM[27]數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。為模擬SPARQL聯(lián)邦查詢,首先將LUBM的1 700萬(wàn)條數(shù)據(jù)按謂詞數(shù)12,12,11劃分為三個(gè)數(shù)據(jù)集(LUBM謂詞總數(shù)為35),然后通過(guò)隨機(jī)選取最終得到15個(gè)謂詞,劃分后每個(gè)數(shù)據(jù)集的三元組總數(shù)依次為9 101 646,11 507 508,7 082 141。最后在劃分得到的數(shù)據(jù)集上生成30萬(wàn)個(gè)具有0到2個(gè)連接的隨機(jī)查詢和1 000個(gè)物化樣本作為訓(xùn)練數(shù)據(jù),并且將訓(xùn)練數(shù)據(jù)分為90%的訓(xùn)練樣本和10%的驗(yàn)證樣本。使用訓(xùn)練數(shù)據(jù)來(lái)訓(xùn)練模型并得到對(duì)應(yīng)的真實(shí)基數(shù)。

此外,為了驗(yàn)證模型的基礎(chǔ)能力和擴(kuò)展能力,在劃分的數(shù)據(jù)集上合成了4種不同的工作負(fù)載:(1)FilterCrd_1,具有4 500個(gè)唯一查詢,用于驗(yàn)證模型關(guān)于范圍篩選的估計(jì)能力;(2)FilterCrd_2,具有500個(gè)唯一查詢,旨在驗(yàn)證模型能否擴(kuò)展到2個(gè)以上連接;(3)DistinctCrd_1,具有4 500個(gè)唯一查詢,用于驗(yàn)證模型估計(jì)唯一率的基礎(chǔ)能力;(4)DistinctCrd_2,具有500個(gè)唯一查詢,旨在驗(yàn)證模型能否擴(kuò)展到2個(gè)以上連接。表1顯示了不同工作負(fù)載中連接數(shù)量的分布。以下將該文用于聯(lián)邦復(fù)雜查詢的基數(shù)估計(jì)模型(Cardinality Estimation of Federated Complex Queries,CEFCQ)記為CEFCQ,同時(shí)實(shí)驗(yàn)將CostFed[23]和CEFQR[24]作為對(duì)比基線。

表1 4種工作負(fù)載的連接分布

3.2 估計(jì)質(zhì)量

在兩個(gè)查詢工作負(fù)載FilterCrd_1和DistinctCrd_1上驗(yàn)證CEFCQ模型的基礎(chǔ)估計(jì)能力,圖4展示了實(shí)驗(yàn)結(jié)果,其中盒須圖中方框邊界位于第25/75百分位,水平“胡須”線標(biāo)記為中位數(shù)位置。總體而言,CEFCQ的兩個(gè)方法都優(yōu)于CostFed和CEFQR,并且CEFCQ表現(xiàn)得更穩(wěn)健,同時(shí)具有更低的尾部誤差。首先,相較于CEFQR,CEFCQ的提升雖然不是很明顯,但其在擴(kuò)展了查詢類型的基礎(chǔ)上仍能表現(xiàn)出優(yōu)于CEFQR的估計(jì)質(zhì)量,說(shuō)明了CEFCQ的實(shí)用價(jià)值;其次,CEFQR能提供較CostFed更精確的估計(jì),這是由于CEFQR不依賴于從SPARQL端點(diǎn)收集的統(tǒng)計(jì)信息,使用監(jiān)督學(xué)習(xí)模型能更準(zhǔn)確地估計(jì)連接基數(shù);另外,隨著連接數(shù)量的增加,模型的估計(jì)質(zhì)量在下降,這是因?yàn)楣烙?jì)多連接(連接數(shù)大于0)查詢時(shí),基數(shù)值是累加的,可見(jiàn)CEFCQ對(duì)0個(gè)連接的查詢估計(jì)質(zhì)量最優(yōu)。

圖4 模型在不同工作負(fù)載上的估計(jì)誤差盒須圖

為了提供更多詳細(xì)信息,在表2和表3中分別顯示了三個(gè)模型在以上工作負(fù)載上中位數(shù)、百分位數(shù)、最大Q-error和平均Q-error。結(jié)果表明CEFCQ在各項(xiàng)指標(biāo)上均表現(xiàn)優(yōu)秀。

表2 各模型在工作負(fù)載FilterCrd_1上的估計(jì)誤差

表3 各模型在工作負(fù)載DistinctCrd_1上的估計(jì)誤差

3.3 擴(kuò)展到更多連接

實(shí)驗(yàn)的目標(biāo)是驗(yàn)證CEFCQ是否能夠推廣到連接數(shù)比訓(xùn)練時(shí)多的查詢。因此,使用查詢工作負(fù)載FilterCrd_2和DistinctCrd_2(見(jiàn)表1)來(lái)驗(yàn)證CEFCQ模型中兩個(gè)方法的泛化能力。值得注意的是,在實(shí)驗(yàn)過(guò)程只使用具有0到2個(gè)連接的查詢來(lái)訓(xùn)練CEFCQ。圖5的實(shí)驗(yàn)結(jié)果表明:整體來(lái)看,當(dāng)連接數(shù)量大于訓(xùn)練時(shí)的最大連接數(shù)2時(shí),CEFCQ中兩個(gè)方法的估計(jì)質(zhì)量都有所下降,但是對(duì)比CostFed,本模型仍然具有更好的可擴(kuò)展性。

圖5 各模型在不同工作負(fù)載上的估計(jì)誤差(展示CEFCQ如何泛化到具有更多連接的查詢)

首先,在FilterCrd_2上驗(yàn)證模型中FILTER特征化方法的擴(kuò)展性,當(dāng)連接數(shù)大于2時(shí),由于CEFCQ需要學(xué)習(xí)更多術(shù)語(yǔ)和圖模式之間的相關(guān)性,從而降低了估計(jì)精度。連接數(shù)從2到3時(shí),第95百分位的Q-error從5.7增加到9.8,對(duì)比CostFed在相同查詢上,第95百分位的Q-error為94.3。當(dāng)連接數(shù)為4,第95個(gè)百分位數(shù)Q-error進(jìn)一步增加到了17.21(CostFed:560.3)。

其次,在DistinctCrd_2上驗(yàn)證CEFCQ學(xué)習(xí)唯一率的泛化能力,當(dāng)連接數(shù)大于2時(shí),CEFCQ容易受到異常值的影響,雖然在訓(xùn)練模型時(shí)對(duì)數(shù)據(jù)進(jìn)行了歸一化和縮放,但偏度的影響仍然存在。連接數(shù)從2到3時(shí),第95百分位的Q-error從7.7增加到15.42(CostFed:133.2)。當(dāng)連接數(shù)為4,第95個(gè)百分位數(shù)Q-error增加到28.34(CostFed:631.8)。作為參考,DistinctCrd_2中的500個(gè)查詢中有48個(gè),超過(guò)了訓(xùn)練期間的最大唯一率。其中32個(gè)查詢有3個(gè)連接,另有16個(gè)查詢有4個(gè)連接。剔除這些異常值后,連接數(shù)為3和4的查詢上,第95個(gè)百分位數(shù)的Q-error分別降至10.2和24.5。

為了提供更多的細(xì)節(jié),表4給出了CEFCQ和CostFed在兩個(gè)工作負(fù)載上Q-error的中位數(shù)、最大值和平均值。可以看到CEFCQ在各個(gè)指標(biāo)上均優(yōu)于CostFed。

表4 各模型在工作負(fù)載FilterCrd_2和DistinctCrd_2上的估計(jì)誤差

3.4 超參數(shù)和模型成本

為了優(yōu)化CEFCQ的性能,搜索了超參數(shù)空間,考慮了不同的設(shè)置,其中改變了批次大小的數(shù)量(16,32,64,…,2 048)、隱藏層大小(16,32,64,…,1 024)和學(xué)習(xí)率(0.001,0.01)。檢查了所有得到的112個(gè)不同的超參數(shù)組合。結(jié)果表明,隱藏層的大小對(duì)CEFCQ在驗(yàn)證測(cè)試中的準(zhǔn)確性影響最大。在達(dá)到最佳結(jié)果之前,隱藏層的大小越大,CEFCQ在驗(yàn)證測(cè)試中就越準(zhǔn)確。之后,由于過(guò)度擬合,質(zhì)量下降。此外,學(xué)習(xí)率和批次大小主要影響訓(xùn)練的收斂行為,而不是模型精度。在驗(yàn)證集上平均運(yùn)行5次,最佳配置是:批次大小為128、隱藏層大小512和0.001的學(xué)習(xí)率。因此,在文中模型評(píng)估中使用這些設(shè)置。在此設(shè)置下,CEFCQ在訓(xùn)練集上運(yùn)行大約200次后,在驗(yàn)證集上收斂到大約3.7的平均Q-error(見(jiàn)圖6)。平均運(yùn)行5次,200個(gè)輪次(epochs)的訓(xùn)練階段大約耗時(shí)48分鐘。

圖6 平均Q-error的收斂

4 結(jié)束語(yǔ)

該文提出了一種基于查詢特征表示學(xué)習(xí)的聯(lián)邦復(fù)雜查詢基數(shù)估計(jì)模型方法。具體來(lái)說(shuō),主要考慮兩類復(fù)雜查詢,即FILTER條件篩選查詢和DISTINCT查詢。把估計(jì)這類查詢基數(shù)的問(wèn)題看做一個(gè)監(jiān)督學(xué)習(xí)任務(wù),提出一種在聯(lián)邦查詢中的監(jiān)督學(xué)習(xí)模型。對(duì)于FILTER查詢,提出一種FILTER特征化的技術(shù),目的是將編碼得到的特征向量作為模型的輸入。在估計(jì)DISTINCT類查詢時(shí),模型輸出估計(jì)的唯一率。對(duì)于這兩種方法,進(jìn)行了大量實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,相較于之前的工作,該模型在基礎(chǔ)估計(jì)能力和泛化能力上都得到了很大提升。結(jié)合現(xiàn)有工作的不足,未來(lái)研究將集中在兩個(gè)方向。首先,擴(kuò)展該模型以支持更多查詢類型,例如帶有Top-k,GROUP BY,OPTIONAL等操作符的查詢。其次,由于該模型在估計(jì)結(jié)果時(shí)是基于RDF數(shù)據(jù)集是靜態(tài)的假設(shè)下,但真實(shí)的RDF數(shù)據(jù)集是不定時(shí)更新的,因此當(dāng)原始數(shù)據(jù)集發(fā)生變化時(shí)模型只能使用新的查詢訓(xùn)練集重新訓(xùn)練,這會(huì)極大地增加計(jì)算成本。因此,下一步計(jì)劃優(yōu)化模型以支持?jǐn)?shù)據(jù)集的增量更新。