異構(gòu)模式中關(guān)聯(lián)數(shù)據(jù)的一致性規(guī)則發(fā)現(xiàn)方法

杜岳峰 李曉光 宋寶燕

(遼寧大學(xué)信息學(xué)院 沈陽 110136)duyuefeng@lnu.edu.cn)

數(shù)據(jù)一致性是質(zhì)量管理的一項(xiàng)核心事務(wù)[1]，主要針對數(shù)據(jù)中存在的沖突情況進(jìn)行處理.規(guī)則約束作為數(shù)據(jù)一致性管理的重要技術(shù)，可以從語義層面對數(shù)據(jù)實(shí)體關(guān)系進(jìn)行形式化地抽象，有效地對沖突數(shù)據(jù)進(jìn)行檢測和修復(fù)，比如條件函數(shù)依賴(conditional functional dependencies， CFDs)[2].

隨著信息產(chǎn)業(yè)的發(fā)展和大數(shù)據(jù)的普及，現(xiàn)實(shí)生活中的數(shù)據(jù)呈現(xiàn)出海量數(shù)據(jù)增長和多源多模態(tài)的分布特點(diǎn)，導(dǎo)致大數(shù)據(jù)環(huán)境下的一致性問題變得更加突出.具體表現(xiàn)為：一是數(shù)據(jù)中潛在的錯(cuò)誤更容易產(chǎn)生；二是對異構(gòu)模式數(shù)據(jù)的管理更加復(fù)雜.

Fig. 1 Inconsistencies under heterogeneous schemas圖1 異構(gòu)模式中的數(shù)據(jù)沖突

圖1描述了異構(gòu)模式中的數(shù)據(jù)沖突情況.

T，S是商品銷售記錄的2種關(guān)系模式.版權(quán)分類(Catg)、類型(Type)、名字(Name)、價(jià)格區(qū)間(Price)、出版商(Pub)是T上的5個(gè)屬性.類型(Type)、書名(Title)、價(jià)格區(qū)間(Price)、出版商(Pub)是S上的4個(gè)屬性.IT，IS是T和S上的關(guān)系實(shí)例.其中，黑體部分為錯(cuò)誤數(shù)據(jù)，括號內(nèi)為現(xiàn)實(shí)生活中對應(yīng)的真值情況.

文獻(xiàn)[2]中，CFDs是一種可以根據(jù)元組的特定條件屬性判定數(shù)據(jù)一致性的規(guī)則約束方法.具體地，對于CFDφ:(X→Y,tp)，X→Y是函數(shù)依賴(functional dependencies, FDs)的一般形式，tp是特定的條件屬性模板.對于任意元組u,v，在u[X]=v[X]=tp[X]的情況下，如果u[Y]=v[Y]，則稱u,v是一致的；否則，如果u[Y]≠v[Y]，則稱u,v是不一致的.

φT，φS是T，S上的CFDs.以φS為例，φS描述了在S上，對于所有的文學(xué)作品，它們的名字可以決定它們的價(jià)格區(qū)間.雖然φT和φS表達(dá)的意思相近，但是由于處于異構(gòu)關(guān)系模式，所以對應(yīng)的屬性也不盡相同(如T中Catg與S中的Type對應(yīng)).另外，對于相同的Type屬性，它們在T和S中表達(dá)的含義也不相同，會(huì)造成屬性的二義性.這些都增加了規(guī)則融合的難度.

其次，盡管IT，IS中的記錄都分別滿足φT，φS的一致性要求，比如對于s1，s2，在s1[Type]=s2[Type]=“l(fā)iterature”，s1[Title]=s2[Title]=“Shawshank Redemption”的情況下，有s1[Price]=s2[Price].文學(xué)作品“Shawshank Redemption”的價(jià)格區(qū)間都是50～100元，說明它們在IS中是一致的.但是s1[Price]，s2[Price]與真實(shí)值相不符，使得它們成為一種潛在的錯(cuò)誤.

對于異構(gòu)關(guān)系模式中的潛在錯(cuò)誤數(shù)據(jù)，可以使用如圖2所示的條件包含依賴(conditional inclusion dependencies, CINDs)[3]和內(nèi)容相關(guān)的條件函數(shù)依賴(content-related conditional functional dependencies, CCFDs)[4]來進(jìn)行處理.

η可以根據(jù)特定的文學(xué)作品名字，將T，S模式中的Pub、Price、類型(Catg，Type)、名字(Name，Title)屬性進(jìn)行匹配.現(xiàn)實(shí)生活中的數(shù)據(jù)是相互關(guān)聯(lián)的[5]，可以利用這種關(guān)系將關(guān)聯(lián)數(shù)據(jù)放在一起進(jìn)行檢測.現(xiàn)實(shí)生活中，“Shawshank Redemption”和“Different Seasons (Hope Spring Eternal)”指的是同一本文學(xué)作品，因此，可以把2類數(shù)據(jù)放在一起進(jìn)行檢測.進(jìn)而，可以通過η將模式T，S聯(lián)系到一起，然后使用φT檢測出s1，s2中的潛在錯(cuò)誤.

Fig. 2 CINDs and CCFDs under heterogeneous schemas圖2 異構(gòu)模式中的CINDs和CCFDs

但是，由于人們對領(lǐng)域和專業(yè)知識的局限，缺乏對數(shù)據(jù)關(guān)系的深層理解，使用人工方法進(jìn)行規(guī)則發(fā)現(xiàn)有可能出現(xiàn)規(guī)則缺失、混淆和沖突的情況.在耗費(fèi)大量人力資源的情況下還無法得到可靠的結(jié)果，這就需要一種可靠高效的自動(dòng)規(guī)則發(fā)現(xiàn)方法.本文在進(jìn)行異構(gòu)模式一致性規(guī)則發(fā)現(xiàn)的研究過程中遇到的挑戰(zhàn)有：

1) 異構(gòu)模式中的屬性關(guān)系復(fù)雜，存在不同屬性之間的匹配問題，在規(guī)則中混合CINDs進(jìn)行規(guī)則發(fā)現(xiàn)會(huì)對一致性規(guī)則的發(fā)現(xiàn)問題產(chǎn)生影響，可能造成屬性對應(yīng)關(guān)系的混亂.

2) 在使用CINDs對一致性規(guī)則進(jìn)行融合和規(guī)則發(fā)現(xiàn)時(shí)，由于CINDs的屬性之間存在包含問題，這會(huì)對融合后的一致性規(guī)則的條件范圍產(chǎn)生影響.

針對上述問題，本文利用CINDs對CCFDs進(jìn)行異構(gòu)關(guān)系模式下的規(guī)則發(fā)現(xiàn)，具體貢獻(xiàn)為：

1) 對使用CINDs進(jìn)行異構(gòu)關(guān)系模式下CCFDs規(guī)則發(fā)現(xiàn)問題進(jìn)行分析，解釋規(guī)則發(fā)現(xiàn)的可滿足性、蘊(yùn)含性和可驗(yàn)證性問題.

2) 提出了一種使用CINDs進(jìn)行異構(gòu)模式和實(shí)例的融合方法.

3) 設(shè)計(jì)了一種基于2級lattice結(jié)構(gòu)的CCFDs規(guī)則發(fā)現(xiàn)方法，對所有規(guī)則空間進(jìn)行搜索.

4) 通過在NBA數(shù)據(jù)和豆瓣數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)，驗(yàn)證本方法的有效性和高效性.

1 相關(guān)工作

數(shù)據(jù)質(zhì)量管理是數(shù)據(jù)庫領(lǐng)域研究的一個(gè)經(jīng)典問題.本文主要研究異構(gòu)模式關(guān)聯(lián)數(shù)據(jù)中一致性規(guī)則的發(fā)現(xiàn)問題.目前與本文研究最為密切的相關(guān)工作包括3個(gè)方面：

1) 規(guī)則約束.規(guī)則約束是數(shù)據(jù)質(zhì)量管理的一個(gè)重要技術(shù)，包含很多種類，如條件函數(shù)依賴(CFDs)[2]、擴(kuò)展條件函數(shù)依賴(extended conditional functional dependencies, eCFDs)[6]、內(nèi)容相關(guān)的條件函數(shù)依賴(CCFDs)[4]、條件包含依賴(CINDs)[3]等.特別地，文獻(xiàn)[7]提出了一種圖函數(shù)依賴(graph entity dependencies, GEDs)，可以對圖上的實(shí)體數(shù)據(jù)進(jìn)行一致性分析.

通常，不同類型的規(guī)則可以混合使用，同時(shí)解決多類數(shù)據(jù)質(zhì)量的混合問題.文獻(xiàn)[3]使用CINDs對特定條件的異構(gòu)模式數(shù)據(jù)進(jìn)行匹配，并分析了CINDs與CFDs之間的相互作用關(guān)系.文獻(xiàn)[8]提出了一種針對實(shí)體一致性的鏈接算法.

2) 規(guī)則發(fā)現(xiàn).規(guī)則發(fā)現(xiàn)是對規(guī)則約束進(jìn)行形式化語義抽象的自動(dòng)發(fā)現(xiàn)方法.具體地，Huhtala等人在文獻(xiàn)[9]中基于lattice結(jié)構(gòu)提出了一種用于FDs規(guī)則發(fā)現(xiàn)的TANE方法.基于此，鐘評等人在文獻(xiàn)[10]提出了一種基于置信度的FDs規(guī)范發(fā)現(xiàn)方法.再者，Chiang等人在文獻(xiàn)[11]中提出了一種CFDs規(guī)則方法，可以搜索特定條件下的函數(shù)依賴.此外，文獻(xiàn)[12-13]提出了GEDs和OFDs(ontology functional dependencies)的規(guī)則發(fā)現(xiàn)方法.

3) 異構(gòu)數(shù)據(jù)清洗.異構(gòu)數(shù)據(jù)清洗主要針對異構(gòu)模式的數(shù)據(jù)和語義2方面內(nèi)容進(jìn)行質(zhì)量管理.具體地，馬茜等人在文獻(xiàn)[14]中提出了一種針對多源多模態(tài)數(shù)據(jù)的動(dòng)態(tài)感知方法.Dallachiesa等人在文獻(xiàn)[15]中提出了一種自動(dòng)商業(yè)數(shù)據(jù)清洗系統(tǒng)，可以對多種類型的語義規(guī)則進(jìn)行管理.文獻(xiàn)[16-19]對質(zhì)量管理的評價(jià)標(biāo)準(zhǔn)和可擴(kuò)展的大規(guī)模數(shù)據(jù)質(zhì)量管理等內(nèi)容進(jìn)行了相關(guān)研究.

此外，時(shí)序數(shù)據(jù)[20]、知識圖譜、圖數(shù)據(jù)[21]、實(shí)體數(shù)據(jù)質(zhì)量管理的研究內(nèi)容正在逐漸升溫，成為數(shù)據(jù)質(zhì)量管理的研究熱點(diǎn).其中，樊文飛等人通過長期對數(shù)據(jù)質(zhì)量的研究，在文獻(xiàn)[7,22]中著重描述了未來數(shù)據(jù)質(zhì)量管理的研究和發(fā)展方向.Ortona等人在文獻(xiàn)[23]中對使用知識圖譜進(jìn)行規(guī)則發(fā)現(xiàn)的相關(guān)內(nèi)容進(jìn)行了研究.

2 異構(gòu)關(guān)聯(lián)數(shù)據(jù)的一致性問題

本節(jié)針對異構(gòu)模式關(guān)聯(lián)數(shù)據(jù)的一致性規(guī)則發(fā)現(xiàn)問題，首先對CINDs和CCFDs進(jìn)行介紹，然后給出了規(guī)則發(fā)現(xiàn)問題的相關(guān)概念及分析.

本文使用R=(tid,A1,A2,…,AN)形式的關(guān)系模式，其中tid表示記錄編號；A1,A2,…,AN表示R上的屬性，dom(A)表示屬性A的定義域，R上的所有屬性集合記作attr(A)，|attr(A)|表示集合中的屬性個(gè)數(shù).

2.1 規(guī)則約束

定義1.內(nèi)容相關(guān)的條件函數(shù)依賴(CCFDs)[4,24].CCFDs是一種可以同時(shí)對多個(gè)條件之進(jìn)行一致性檢測的完整性約束.關(guān)系R上的CCFD記作

φ:(C|Y→A,Sc=∪Sci),

(1)

其中，C為條件屬性集合，Y為變量屬性集合，C和Y由“|”分隔，并且C,Y?attr(R)，C∩Y=?，C，Y合稱為規(guī)則左部，記作lhs(φ)，單屬性A稱為規(guī)則右部，記作rhs(φ)；Y→A是一個(gè)標(biāo)準(zhǔn)函數(shù)依賴；Sci是關(guān)于C的屬性值集合，Sci?dom(C)，Sc是Sci的集合，即Sc=∪Sci.并且，對于任意元組ti，tj，如果ti[C]，tj[C]∈Sci，ti和tj需要放在一起進(jìn)行檢測.圖2中的φT就是模式T上的一條CCFD規(guī)則.

定義2.條件包含依賴(CINDs)[3].CINDs是一種可以對異構(gòu)模式進(jìn)行屬性匹配的規(guī)則約束.關(guān)于模式Ra，Rb的CIND記作

η:(Ra[X;Xk]?Rb[Y;Yk],Tk=∪tk),

(2)

其中，X,Xk?attr(Ra)，X∩Xk=?，同理有Y,Yk?attr(Rb)，Y∩Yk=?；Ra[X]?Rb[Y]是一個(gè)標(biāo)準(zhǔn)包含依賴；Tk是條件屬性集合的模板，Tk=∪tk，tk是條件屬性值的對應(yīng)情況，tk=(tk[Xk]‖tk[Yk])，tk[Xk]∈dom(Xk)，tk[Yk]∈dom(Yk)，使用“‖”進(jìn)行分割.圖2中的η就是關(guān)于T，S的一條CIND規(guī)則.

2.2 異構(gòu)模式下CCFDs發(fā)現(xiàn)問題

本文主要針對異構(gòu)關(guān)聯(lián)數(shù)據(jù)中的一致性規(guī)則發(fā)現(xiàn)問題進(jìn)行研究,使用CINDs對CCFDs進(jìn)行異構(gòu)模式下的規(guī)則發(fā)現(xiàn)，其問題描述如下：

定義3.異構(gòu)模式下CCFDs發(fā)現(xiàn)問題.給定關(guān)系模式Ra，Rb下的實(shí)例Ia，Ib以及對應(yīng)的CINDs規(guī)則集合Γ，找到模式融合Ra⊕ΓRb上所有CCFDs的最小性規(guī)則集合Σ.

1) 異構(gòu)模式融合并不簡單等同于模式和實(shí)例的合并，具體的異構(gòu)融合過程Ra⊕ΓRb將在3.1節(jié)中進(jìn)行介紹.

3) 對于發(fā)現(xiàn)得到的CCFDs規(guī)則集合需要滿足Armstrong最小性和規(guī)則數(shù)量最小性[4]要求.

本文對CCFDs規(guī)則的可滿足性、蘊(yùn)含性和可驗(yàn)證性3個(gè)基本問題進(jìn)行分析.

定理1.CCFDs規(guī)則的可滿足性、蘊(yùn)含性和可驗(yàn)證性問題分別屬于NP-complete，coNP-complete，PTIME.

證明. CCFDs是在CFDs的基礎(chǔ)上，對關(guān)聯(lián)數(shù)據(jù)的條件值進(jìn)行合并得到的一種特殊情況，這里以CCFDs規(guī)則可滿足性為例進(jìn)行說明.Fan等人在文獻(xiàn)[25]中使用合取范式γ:X1∨X2∨…∨Xn(其中，Xi都是由小項(xiàng)合取得到的)對MAXGSAT(maximum generalized satisfiability)問題[26]進(jìn)行規(guī)約，證明CFDsφ的可滿足性問題是屬于NP-complete的.具體地，MAXGSAT是MAXSAT(maximum satisfiability)的一般問題，描述了最大可滿足性問題的一般形式，被證明是滿足NP-complete的.其中，X1,X2,…,Xn∈lhs(φ)，Xi滿足l1∧l2∧l3的形式，l1,l2,l3是Xi在條件值tp下的取值情況，Xi的定義域?yàn)閐om(Xi,tp)，進(jìn)而判定γ:X1∨X2∨…∨Xn的真值情況.對于CCFDs而言，其證明過程滿足CFDs證明的基本過程，區(qū)別在于l1,l2,l3是Xi在條件值Sci下的取值情況，Xi的定義域?yàn)閐om(Xi,Sci).這樣可以在O(|Sci|)時(shí)間內(nèi)將CCFDs可滿足性問題轉(zhuǎn)化為CFDs可滿足性問題，其中|Sci|表示Sci中包含的條件值的個(gè)數(shù).因此，可以把CCFDs可滿足性問題看作是CFDs可滿足性的等價(jià)問題.所以，CCFDs規(guī)則的可滿足性問題是屬于NP-complete的.同理，可以將CCFDs規(guī)則的蘊(yùn)含性問題和可驗(yàn)證問題等價(jià)轉(zhuǎn)化成CFDs規(guī)則的蘊(yùn)含性問題和可驗(yàn)證性問題，并且CFDs規(guī)則的這2個(gè)問題在文獻(xiàn)[3]中被證明是分別屬于coNP-complete，PTIME的.因此，CCFDs規(guī)則的蘊(yùn)含性問題和可驗(yàn)證問題也分別屬于coNP-complete，PTIME的.

證畢.

需要說明的是，對于CCFDs和CINDs混合規(guī)則的可滿足性、蘊(yùn)含性、可驗(yàn)證性問題滿足文獻(xiàn)[3]描述的情況，均屬于不確定性問題.

3 異構(gòu)模式下的CCFDs規(guī)則發(fā)現(xiàn)方法

針對2.2節(jié)中提出的CCFDs發(fā)現(xiàn)問題，本節(jié)將從異構(gòu)模式融合、搜索結(jié)構(gòu)和規(guī)則發(fā)現(xiàn)方法的設(shè)計(jì)這3個(gè)方面對規(guī)則發(fā)現(xiàn)的實(shí)現(xiàn)過程進(jìn)行描述.

3.1 異構(gòu)模式融合

在異構(gòu)關(guān)系模式中，由于關(guān)系模式的差別，一種關(guān)系模式上的規(guī)則集合很難在另一種關(guān)系模式上產(chǎn)生作用.這樣一方面會(huì)降低規(guī)則的復(fù)用率和作用效果，另一方面也會(huì)影響規(guī)則對整體數(shù)據(jù)進(jìn)行歸納抽象.因此，首先需要對異構(gòu)數(shù)據(jù)進(jìn)行融合.但是，異構(gòu)融合不能等同于簡單的模式和實(shí)例合并.針對這一問題，對于給定異構(gòu)關(guān)系模式Ra，Rb下的實(shí)例Ia，Ib以及CINDs規(guī)則集合Γ，本文提出了一種異構(gòu)模式融合和異構(gòu)實(shí)例融合的概念.

對于η∈Γ，η:(Ra[X;Xk]?Rb[Y;Yk],Tk=∪tk)，本文首先給出Ra，Rb關(guān)于η的模式融合形式：

Ra⊕ηRb=(X⊕ηY,Xk⊕ηYk,
attr(Ra)-lhs(η),attr(Rb)-rhs(η)),

(3)

其中，X⊕ηY(或者Xk⊕ηYk)表示屬性X和Y(或者Xk和Yk)融合后組成的新的模式屬性，dom(X⊕ηY)=dom(X)∪dom(Y)，dom(Xk⊕ηYk)同前.lhs(η)表示η的左部屬性集合，即lhs(η)=X∪Xk.這樣，原來異構(gòu)模式中能夠通過η進(jìn)行匹配的屬性將被放在一起，共同作為融合模式中的一個(gè)屬性；不能被匹配的屬性仍然單獨(dú)保留在融合后的模式中.并且，對于融合后的屬性值，其閾值為2個(gè)屬性的并集.

定義4.異構(gòu)模式融合Ra⊕ΓRb.Ra⊕ΓRb表示整個(gè)異構(gòu)模式空間中的模式融合形式，融合過程為

(4)

規(guī)則發(fā)現(xiàn)問題通常是從實(shí)例中對語義關(guān)系進(jìn)行抽象.模式融合會(huì)對關(guān)系屬性進(jìn)行擴(kuò)展，這樣也會(huì)對關(guān)系實(shí)例產(chǎn)生變化，進(jìn)而對規(guī)則發(fā)現(xiàn)產(chǎn)生影響.接下來給出異構(gòu)實(shí)例融合的概念.

定義5.異構(gòu)實(shí)例融合Ia⊕ΓIb.Ia⊕ΓIb表示在融合模式下合并得到的關(guān)系實(shí)例，構(gòu)建過程為

(5)

其中，Ib[y]*表示對于Rb中原本不存在的屬性，使用“*”值進(jìn)行填充.需要說明的是，“*”值是一個(gè)特殊值，既不是空值，也不是實(shí)值，不能用“*”值來表示數(shù)據(jù)的真實(shí)情況，但是認(rèn)為“*”值與任何數(shù)據(jù)都不沖突，即對于?t,s∈Ia⊕ΓIb，如果t[A]=“*”或者s[A]=“*”，則t[A]=s[A].這種情況在實(shí)際數(shù)據(jù)中是不允許的.但是，規(guī)則發(fā)現(xiàn)作為數(shù)據(jù)分析的一個(gè)中間過程，“*”值不會(huì)對規(guī)則發(fā)現(xiàn)造成影響，是可以接受的.表1給出了融合后的Ra⊕ΓRb及Ia⊕ΓIb.

Table 1 Fusion Instance Ia⊕ΓIb on Fusion Schema Ra⊕ΓRb表1 融合后Ra⊕ΓRb模式的Ia⊕ΓIb

3.2 2級lattice結(jié)構(gòu)

函數(shù)依賴FDs、條件函數(shù)依賴CFDs、擴(kuò)展函數(shù)依賴eCFDs是進(jìn)行數(shù)據(jù)一致性管理的重要技術(shù).在關(guān)系模式R中，F(xiàn)Ds可以表示為γ:X→A，屬性集合X,A∈R.對于R上的實(shí)例I，γ表示X在I上的屬性值可以唯一決定A的屬性值，即對于?u,v∈I，如果u,v是一致的，那么有u[X]=v[X]，u[A]=v[A].文獻(xiàn)[8]提出了一種用于FDs規(guī)則發(fā)現(xiàn)的lattice搜索結(jié)構(gòu)，可以根據(jù)屬性個(gè)數(shù)從左部屬性和右部屬性對規(guī)則空間進(jìn)行劃分，直到遍歷所有的搜索空間，可以有效對FDs進(jìn)行發(fā)現(xiàn)，圖3(a)是一個(gè)lattice結(jié)構(gòu)實(shí)例，其中邊(AB，ABC)就表示FDγ:AB→C的規(guī)則空間.

對于CFDs和eCFDs，由于在FDs規(guī)則的基礎(chǔ)上，在規(guī)則左部中對條件屬性進(jìn)行了劃分，在進(jìn)行規(guī)則發(fā)現(xiàn)的過程中就需要分別考慮條件屬性和變量屬性的情況.特別地，CCFDs是CFDs和eCFDs的一種特殊情況，規(guī)則將CFDs和eCFDs中具有關(guān)聯(lián)關(guān)系的規(guī)則進(jìn)行了合并.基于lattice結(jié)構(gòu)的基礎(chǔ)原理，本文提出了一種異構(gòu)模式的2級lattice結(jié)構(gòu)，如圖3所示.在進(jìn)行規(guī)則發(fā)現(xiàn)時(shí)，從|AB→C開始，經(jīng)過A|B→C，B|A→C直到AB|→C結(jié)束.圖2中的φT就是在Catg,Name|→Price層次中對條件值進(jìn)行合并得到的CCFD.

Fig. 3 2-level lattice圖3 2級lattice結(jié)構(gòu)

3.3 CCFDs規(guī)則發(fā)現(xiàn)方法

本文使用Ra⊕ΓRb對異構(gòu)關(guān)系模式進(jìn)行融合，然后使用2級lattice結(jié)構(gòu)構(gòu)建CCFDs的搜索空間，對于滿足相同形式C|Y→A的條件值進(jìn)行合并，得到對應(yīng)的CCFD.但是，并不是所有的條件值都能進(jìn)行合并，有的條件值之間是相互沖突的.因此，本文提出了一種用于條件值沖突的判定方法，如定理2所示.

定理2.一條CCFDφ:(C|Y→A,Sc=∪Sci)關(guān)于實(shí)例Ia⊕ΓIb是不沖突的當(dāng)且僅當(dāng):

對于?Sci∈Sc，有

證畢.

需要說明的是，定理2從條件值沖突的角度對規(guī)則合并進(jìn)行分析，也可以使用定理2對規(guī)則是否成立進(jìn)行判定，進(jìn)而用于CCFDs的規(guī)則發(fā)現(xiàn).

對于2.2節(jié)描述的規(guī)則最小性問題.本文研究的條件值合并是在滿足Armstrong最小性的CFDs上進(jìn)行的，因此合并后的CCFDs仍然滿足Armstrong最小性.文獻(xiàn)[4]中證明CCFDs規(guī)則數(shù)量最小性是最大子團(tuán)的一個(gè)等價(jià)問題，屬于NP-complete.對于本文所描述的異構(gòu)關(guān)系模式下的CCFDs規(guī)則發(fā)現(xiàn)問題，通過CINDs將Ra，Rb進(jìn)行融合成Ra⊕ΓRb，其條件屬性可以在PTIME內(nèi)轉(zhuǎn)化成Ra和Rb的條件屬性，使得異構(gòu)模式下的CCFDs規(guī)則發(fā)現(xiàn)的數(shù)量最小性問題仍然是一個(gè)NP-complete問題.

對于給定層次形式C|Y→A，需要合并候選條件值集合C及樣本實(shí)例Ia⊕ΓIb，本文提出一種啟發(fā)式的條件值合并方法，如算法1所示.

4 實(shí)驗(yàn)分析

對于異構(gòu)模式下關(guān)聯(lián)數(shù)據(jù)的CCFDs規(guī)則發(fā)現(xiàn)問題，本文通過在2組真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)來驗(yàn)證方法的有效性和高效性.

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

硬件方面，本實(shí)驗(yàn)使用Intel Core i5-7400 (3.00 GHz) CPU，搭載8 GB RAM主機(jī)進(jìn)行實(shí)現(xiàn)，程序設(shè)計(jì)使用Java語言進(jìn)行實(shí)現(xiàn).

實(shí)驗(yàn)數(shù)據(jù)集，本文使用NBA數(shù)據(jù)和豆瓣數(shù)據(jù)進(jìn)行融合，并使用融合后的數(shù)據(jù)進(jìn)行規(guī)則發(fā)現(xiàn).

1) NBA數(shù)據(jù).隊(duì)員數(shù)據(jù)Players和賽季比賽統(tǒng)計(jì)信息Stat是從體育信息數(shù)據(jù)庫(1)https://www.rotowire.com/basketball/上抽取得到的真實(shí)數(shù)據(jù).Players數(shù)據(jù)包含14個(gè)屬性、超過11 000的信息記錄.Stat數(shù)據(jù)包含11個(gè)屬性、超過200 000的比賽信息.以球隊(duì)作為條件設(shè)計(jì)使用30條CINDs對Players和Stat進(jìn)行融合，例如η:Players(player,pos,season,min,drafted,pts,team=“HOU”)?Stat(player,pos,lea,min,no,pts,tname=“HOU”).

2) 豆瓣(Douban)數(shù)據(jù).豆瓣電影Movie和豆瓣讀書Book是從豆瓣網(wǎng)站(2)https://www.douban.com/上抽取得到的部分真實(shí)數(shù)據(jù).Movie數(shù)據(jù)中包含10個(gè)屬性，元組數(shù)為50 000條.Book數(shù)據(jù)中包含12個(gè)屬性，元組數(shù)為47 000條.并且，對Movie和Book融合后得到的數(shù)據(jù)包含62 000條元組和14個(gè)屬性.

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

本文從規(guī)則發(fā)現(xiàn)方法的基本性能和擴(kuò)展性2個(gè)方面進(jìn)行驗(yàn)證和分析.

4.2.1 基本性能

首先從運(yùn)行時(shí)間和規(guī)則數(shù)量對整體性能進(jìn)行評價(jià)，然后給出規(guī)則發(fā)現(xiàn)的部分實(shí)例，其中，豆瓣數(shù)據(jù)使用合并元組9 332條，包含3 112條電影實(shí)體.

圖4(a)給出了NBA和Douban數(shù)據(jù)集中，規(guī)則發(fā)現(xiàn)過程融合階段(fusion)、2級lattice下CFDs發(fā)現(xiàn)階段(2-lattice)、規(guī)則合并階段(h-CCFD)的運(yùn)行時(shí)間情況.

Fig. 4 Performance of rules discovery圖4 規(guī)則發(fā)現(xiàn)的基本性能

其中，模式和實(shí)例的融合時(shí)間(fusion)最短，分別為2.6 s和0.8 s，只占整個(gè)運(yùn)行時(shí)間的極小比例.同樣情況下，使用文獻(xiàn)[15]中的規(guī)則融合方法(f-NAD)需要14.1 s和8.8 s，這是因?yàn)閒-NAD需要對規(guī)則中的各個(gè)屬性進(jìn)行拆分，然后使用統(tǒng)一的形式進(jìn)行表達(dá).

CFDs作為CCFDs合并的候選規(guī)則.在進(jìn)行候選規(guī)則發(fā)現(xiàn)過程的實(shí)驗(yàn)中，如2-lattice所示，在2級lattice結(jié)構(gòu)下對CFDs規(guī)則進(jìn)行發(fā)現(xiàn)的時(shí)間最長，相比較文獻(xiàn)[2]中使用的freeset-closedset方法，對應(yīng)圖4(a)中的CFD方法，時(shí)間要超過1倍左右.但是，該方法不利于對規(guī)則進(jìn)行C|Y→A形式劃分并用于CCFDs合并，所以這里仍推薦使用2級lattice結(jié)構(gòu)進(jìn)行CCFDs規(guī)則發(fā)現(xiàn).OFD-Gen是在fusion的基礎(chǔ)上，對每個(gè)實(shí)體使用1級lattice方法進(jìn)行候選規(guī)則發(fā)現(xiàn)的過程，但是由于實(shí)體的數(shù)量較多，增加了整體的運(yùn)行時(shí)間.對于NBA和Douban數(shù)據(jù)，由于融合的屬性個(gè)數(shù)基本相同，所以構(gòu)成的2級lattice空間的大小也基本相同.

在對規(guī)則進(jìn)行合并的過程中，h-CCFD在2-lattice結(jié)構(gòu)發(fā)現(xiàn)CFDs的基礎(chǔ)上，使用啟發(fā)式方法對候選條件值進(jìn)行合并，可以在較短時(shí)間內(nèi)完成.OFD-Min在進(jìn)行規(guī)則發(fā)現(xiàn)的過程中首先對實(shí)體進(jìn)行判定和識別，然后根據(jù)實(shí)體的內(nèi)容、屬性及相互關(guān)系進(jìn)行規(guī)則發(fā)現(xiàn)，需要大量的運(yùn)行時(shí)間，在NBA和Douban數(shù)據(jù)上分別需要520s和387s，是h-CCFD方法的3.8和6.2倍.并且，OFD方法(OFD-Gen與OFD-Min之和)要高于CCFD方法(2-lattice與h-CCFD之和)分別為6%和25%，具體會(huì)受到實(shí)際數(shù)據(jù)分布的影響.

圖4(b)給出了NBA和Douban數(shù)據(jù)中規(guī)則發(fā)現(xiàn)的數(shù)量情況.其中，CCFD-1和CCFD-2指在2個(gè)數(shù)據(jù)集中分別在未融合情況下進(jìn)行規(guī)則發(fā)現(xiàn)的情況，比如NBA中CCFD-1指單獨(dú)在Players數(shù)據(jù)中發(fā)現(xiàn)CCFD的規(guī)則數(shù)量，CCFD-2指單獨(dú)在Stat數(shù)據(jù)中發(fā)現(xiàn)CCFD的規(guī)則數(shù)量.其中，NBA數(shù)據(jù)集中，CCFD-1，CCFD-2、CCFD合并得到的規(guī)則數(shù)量分別為1 009，8 028，8 238條，并且有878條來自Players和Stat的規(guī)則合并到了一起，合并的比率為10.7%.在Douban數(shù)據(jù)集中，合并的數(shù)量是425條，比率為28.3%,這是因?yàn)楹喜⒌那闆r會(huì)受到實(shí)際數(shù)據(jù)分布的影響.

從CFD對CCFD的規(guī)則數(shù)量情況來看，由于NBA中各個(gè)隊(duì)伍的整體差別不是很明顯，所以各個(gè)隊(duì)伍可以合并在一起，并且平均每2.7條規(guī)則就可以合并成1條規(guī)則.特別地，現(xiàn)實(shí)生活中條件值的合并情況由數(shù)據(jù)的實(shí)際分布情況來決定.OFD使用同義詞進(jìn)行實(shí)體識別，將同一指向的規(guī)則合并到一起，分別在NBA和Douban上得到16 132條和2 237條規(guī)則，但是合并的效果不如CCFD明顯.

下面給出在實(shí)驗(yàn)過程中發(fā)現(xiàn)的部分規(guī)則實(shí)例.NBA數(shù)據(jù)集中發(fā)現(xiàn)的規(guī)則實(shí)例分別為CCFDφ1:(player⊕player|team⊕tname→drafted⊕no,Sc)Sc{Sc0{“Jordan”,“MJ”,“Air Jordan”}}和OFDρ1:(player⊕player|team⊕tname→{‘Jordan’,‘MJ’}drafted⊕no).同樣，Douban數(shù)據(jù)集中發(fā)現(xiàn)的規(guī)則實(shí)例分別為CCFDφ2:(Title⊕Name|Type⊕Catg→Writer⊕Writer,Sc)Sc{Sc0{“Shawshank Redemption”,“Different Seasons”}}和OFDρ2:(Title⊕Name|Type⊕Catg→{‘月黑高飛’,‘肖申克的救贖’}Writer⊕Writer).

4.2.2 可擴(kuò)展性

本節(jié)將從模式屬性和元組數(shù)量2個(gè)方面考量規(guī)則發(fā)現(xiàn)方法的可擴(kuò)展性.具體地，通過分別改變屬性個(gè)數(shù)和元組個(gè)數(shù)，觀察運(yùn)行時(shí)間和規(guī)則數(shù)量的變化情況.

1) 屬性數(shù)量變化.Douban數(shù)據(jù)集使用9 332條合并元組，包含3 112條電影實(shí)體.圖5給出了屬性數(shù)量變化情況下規(guī)則發(fā)現(xiàn)過程的時(shí)間變化和規(guī)則數(shù)量的變化情況.CFDs和h-CCFD的運(yùn)行時(shí)間和規(guī)則數(shù)量都隨屬性數(shù)量呈指數(shù)增長趨勢，這是因?yàn)?級lattice結(jié)構(gòu)是一種隨屬性個(gè)數(shù)而呈指數(shù)變化的結(jié)構(gòu).OFD中雖然使用的是1級lattice結(jié)構(gòu)，但是需要對每一個(gè)實(shí)體都進(jìn)行識別和規(guī)則發(fā)現(xiàn)，所以整體運(yùn)行時(shí)間更長.

另外，圖5(b)所示的規(guī)則數(shù)量指數(shù)增長緩慢，是因?yàn)樾略鰧傩灾g關(guān)系較弱，不易形成新的規(guī)則約束，這是屬性結(jié)構(gòu)和數(shù)據(jù)分布所決定的.特別地，規(guī)則數(shù)量呈現(xiàn)指數(shù)增長，這反映了規(guī)則發(fā)現(xiàn)的實(shí)際計(jì)算情況.但是，這種增長的速度過快，不是一個(gè)有利因素，尤其是對于大數(shù)據(jù)計(jì)算和實(shí)時(shí)計(jì)算而言，這種計(jì)算代價(jià)難以接受.因此，還需要針對這一問題設(shè)計(jì)剪枝方法、線性代價(jià)的近似方法，甚至亞線性方法.

2) 元組數(shù)量變化.圖6給出了元組數(shù)量變化情況下規(guī)則發(fā)現(xiàn)過程的時(shí)間變化和規(guī)則數(shù)量的變化情況.CFDs，h-CCFD，OFD的運(yùn)行時(shí)間和規(guī)則數(shù)量都隨屬性數(shù)量呈線性增長趨勢，而且變化比較平緩，這是因?yàn)樵陔S著元組數(shù)量增加的過程中，元組中包含的不同值也在均勻增加.當(dāng)NBA數(shù)據(jù)大于150 000，Douban數(shù)據(jù)大于40 000時(shí)，隨著元組數(shù)量的增加，新增元組所包含的不同值的數(shù)量卻沒有明顯增加，所以規(guī)則數(shù)量增加的情況也會(huì)變得更加平緩.

Fig. 5 Scalability on attributes圖5 屬性變化情況下的可擴(kuò)展性

Fig. 6 Scalability on tuples圖6 元組變化情況下的可擴(kuò)展性

通過上述實(shí)驗(yàn)，說明本文提出的方法可以有效對異構(gòu)數(shù)據(jù)進(jìn)行融合，并且可以通過數(shù)據(jù)關(guān)聯(lián)關(guān)系快速、準(zhǔn)確地對CCFDs進(jìn)行規(guī)則發(fā)現(xiàn).

5 結(jié)束語

本文通過對異構(gòu)關(guān)聯(lián)數(shù)據(jù)的一致性問題進(jìn)行分析研究，提出一種異構(gòu)模式下一致性規(guī)則約束的發(fā)現(xiàn)方法，并對規(guī)則發(fā)現(xiàn)的可滿足性、蘊(yùn)含性和可驗(yàn)證性問題進(jìn)行了分析.具體地，本文使用CINDs對異構(gòu)模式進(jìn)行融合，提出一種基于2級lattice結(jié)構(gòu)的CCFDs規(guī)則發(fā)現(xiàn)方法，最后通過實(shí)驗(yàn)驗(yàn)證了本文所提方法的有效性和高效性.