摘要：圖依賴是用于解決圖數(shù)據(jù)的數(shù)據(jù)一致性問(wèn)題的數(shù)據(jù)質(zhì)量規(guī)則。基于圖依賴提升數(shù)據(jù)一致性的過(guò)程通常分為圖依賴定義與形式化、圖依賴自動(dòng)挖掘、基于圖依賴的數(shù)據(jù)一致性提升三步。介紹了針對(duì)數(shù)據(jù)一致性的圖依賴?yán)碚?，并根?jù)拓展類型將圖依賴分為基于結(jié)構(gòu)約束拓展、基于語(yǔ)義約束拓展和基于外部約束拓展的圖依賴；綜述并對(duì)比了從圖數(shù)據(jù)中自動(dòng)挖掘圖依賴及其拓展的算法；分析了應(yīng)用圖依賴提高數(shù)據(jù)一致性的研究現(xiàn)狀；總結(jié)了當(dāng)前研究中仍存在的問(wèn)題，并依據(jù)問(wèn)題展望了圖依賴在數(shù)據(jù)質(zhì)量領(lǐng)域的應(yīng)用前景。

關(guān)鍵詞：圖依賴；數(shù)據(jù)一致性；圖依賴發(fā)現(xiàn)；一致性檢測(cè)；知識(shí)圖譜

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1001-3695（2023）05-004-1312-06doi：10.19734/j.issn.1001-3695.2022.09.0492

隨著大數(shù)據(jù)時(shí)代的來(lái)臨，數(shù)據(jù)的規(guī)模大幅增加，這意味著出現(xiàn)數(shù)據(jù)質(zhì)量問(wèn)題的幾率也隨之增加［1］；而低質(zhì)量的數(shù)據(jù)會(huì)影響數(shù)據(jù)挖掘效果，進(jìn)而影響決策質(zhì)量并降低數(shù)據(jù)應(yīng)用價(jià)值［2，3］。

數(shù)據(jù)一致性作為反映數(shù)據(jù)是否真實(shí)、有效的重要維度之一，是數(shù)據(jù)質(zhì)量的重要研究?jī)?nèi)容［4～6］。數(shù)據(jù)一致性是指在數(shù)據(jù)集合中每個(gè)信息都不包含語(yǔ)義錯(cuò)誤或相互矛盾的數(shù)據(jù)［7］。當(dāng)數(shù)據(jù)庫(kù)中所有元組（子圖）均遵守了特定的規(guī)則（可能是預(yù)先定義或蘊(yùn)涵的）時(shí)，稱其保持了數(shù)據(jù)一致性。而當(dāng)元組（子圖）違反特定的規(guī)則時(shí)，其被稱為不一致數(shù)據(jù)或不一致錯(cuò)誤［8～11］。

函數(shù)依賴（functionaldependency）是解決關(guān)系型數(shù)據(jù)中數(shù)據(jù)一致性問(wèn)題最常用的數(shù)據(jù)質(zhì)量規(guī)則［5，7］。一個(gè)函數(shù)依賴記為X→Y，表示屬性間的語(yǔ)義約束，指屬性X的值決定屬性Y的值。學(xué)者基于函數(shù)依賴提出了多種實(shí)用的擴(kuò)展［8］，如近似函數(shù)依賴、條件函數(shù)依賴、模式函數(shù)依賴等。

圖依賴是函數(shù)依賴基于圖模式的拓展，表示圖模式中對(duì)應(yīng)節(jié)點(diǎn)間蘊(yùn)涵的屬性依賴關(guān)系，往往用于捕獲圖數(shù)據(jù)中的不一致數(shù)據(jù)［9］。相比于其他數(shù)據(jù)質(zhì)量規(guī)則，如圖鍵和圖關(guān)聯(lián)規(guī)則，圖依賴有著更強(qiáng)的語(yǔ)義表達(dá)能力和可拓展性［9～11］。因此圖依賴被認(rèn)為在數(shù)據(jù)質(zhì)量領(lǐng)域中更具研究?jī)r(jià)值［12～16］。

基于圖依賴解決數(shù)據(jù)一致性問(wèn)題通常包括三個(gè)步驟［17～19］：a）了解數(shù)據(jù)之間的語(yǔ)義關(guān)系，定義并形式化相應(yīng)數(shù)據(jù)質(zhì)量規(guī)則；b）針對(duì)數(shù)據(jù)集，提出相應(yīng)數(shù)據(jù)質(zhì)量規(guī)則自動(dòng)挖掘算法；c）根據(jù)數(shù)據(jù)質(zhì)量規(guī)則檢測(cè)或修復(fù)錯(cuò)誤以提高數(shù)據(jù)的數(shù)據(jù)一致性。其中，根據(jù)適用場(chǎng)景的不同，數(shù)據(jù)質(zhì)量規(guī)則可為關(guān)聯(lián)規(guī)則、函數(shù)依賴和條件約束等；根據(jù)數(shù)據(jù)集的不同，數(shù)據(jù)質(zhì)量規(guī)則可分為面向圖數(shù)據(jù)和面向關(guān)系型數(shù)據(jù)的數(shù)據(jù)質(zhì)量規(guī)則。

本文主要對(duì)圖依賴?yán)碚?、圖依賴自動(dòng)挖掘算法和基于圖依賴的數(shù)據(jù)一致性保證方法進(jìn)行詳細(xì)總結(jié)，為相關(guān)研究者了解領(lǐng)域進(jìn)展提供參考。

1針對(duì)數(shù)據(jù)一致性的圖依賴

在給出圖依賴的形式化定義前，先給出一些必要的預(yù)備知識(shí)。

在圖函數(shù)依賴中圖模式Q限定結(jié)構(gòu)約束，依賴中的所有屬性都來(lái)自于Q匹配到的子圖，并以此區(qū)分圖模式中的節(jié)點(diǎn)（屬性）；字面量集合μ包括X和Y兩個(gè)（可能為）集合，形式可以是屬性或常量字面量集合。一個(gè)字面量可表示為x.A=c或x.A=y.B，其中x，y∈μ。為進(jìn)一步擴(kuò)大語(yǔ)義描述，GFD允許Y為布爾變量1；函數(shù)依賴X→Y限定語(yǔ)義約束，其表示單個(gè)屬性（常量）被其他多個(gè)屬性（常量）集合（可能為空）唯一決定。表1中φ1～φ4，為四個(gè)典型的圖依賴。

定義5模式同構(gòu)（patternisomorphic）。模式同構(gòu)指給定模式圖，其所有的邊均能映射到數(shù)據(jù)圖的子圖。具體定義如下，給定圖G=（V，E，Σ，L）與圖模式Q=（VQ，EQ，ΣQ，LQ），若使G與Q模式同構(gòu)，只需存在一個(gè)雙射函數(shù)滿足以下條件：

模式同構(gòu)問(wèn)題是子圖同構(gòu)問(wèn)題［20］的子類問(wèn)題，指不考慮節(jié)點(diǎn)標(biāo)簽的子圖同構(gòu)。圖3展示了基于模式同構(gòu)的圖模式匹配過(guò)程。其中，數(shù)值索引只表示節(jié)點(diǎn)相對(duì)位置，不具有語(yǔ)義信息。

圖依賴主要被用于提高數(shù)據(jù)一致性，根據(jù)不一致數(shù)據(jù)類型不同，學(xué)者們提出了許多基于圖函數(shù)依賴的拓展［11～13，15～17］。根據(jù)其拓展形式不同，可將圖依賴分為基于結(jié)構(gòu)約束拓展、基于語(yǔ)義約束拓展和基于外部約束拓展的圖依賴。

1.3基于結(jié)構(gòu)約束拓展的圖依賴

圖依賴區(qū)別于關(guān)系依賴的一個(gè)關(guān)鍵特點(diǎn)是其面向于半結(jié)構(gòu)化的圖數(shù)據(jù)［14］。相比于結(jié)構(gòu)化的關(guān)系型數(shù)據(jù)以元組為基本單位，其在結(jié)構(gòu)上有著更多的可能性。為在圖依賴中表達(dá)圖結(jié)構(gòu)的拓?fù)湫畔?，一般分為基于路徑模式表示和基于圖模式表示的圖結(jié)構(gòu)兩類。一般情況下，圖依賴默認(rèn)以圖模式表示圖結(jié)構(gòu)。

文獻(xiàn)［13］首次提出以路徑模式定義圖結(jié)構(gòu)，以邊標(biāo)簽表示屬性，第一次將面向關(guān)系表的函數(shù)依賴拓展到圖數(shù)據(jù)，記做δ：Vn（X→Y）。但基于路徑模式的圖依賴需要針對(duì)特定節(jié)點(diǎn)V展開(kāi)，通過(guò)有向邊組合的路徑表達(dá)式記錄以節(jié)點(diǎn)V為中心節(jié)點(diǎn)的n-跳躍圖。根據(jù)定義3可知，其只能表達(dá)形如星型拓?fù)浣Y(jié)構(gòu)的圖結(jié)構(gòu)，表達(dá)拓?fù)浣Y(jié)構(gòu)時(shí)有著天然局限性。

因此，文獻(xiàn)［11］在其基礎(chǔ)上提出用屬性圖來(lái)表示圖結(jié)構(gòu)的圖依賴φ：Q［μ］（X→Y）。屬性圖是一種新提出的圖模式模型，其以實(shí)體與屬性間的鍵值對(duì)形式而非三元組形式表達(dá)值。由于屬性圖是圖模式模型，理論上可以表達(dá)所有的圖結(jié)構(gòu)，即使是有向有環(huán)圖。表1中的φ3是以環(huán)狀圖為圖模式的圖依賴。

1.4基于語(yǔ)義約束拓展的圖依賴

為捕獲圖數(shù)據(jù)中更多錯(cuò)誤，一個(gè)直接的想法是基于關(guān)系依賴的拓展提出對(duì)應(yīng)的圖依賴，如基于近似函數(shù)依賴提出圖近似函數(shù)依賴，基于條件函數(shù)依賴提出圖條件函數(shù)依賴［21］。因此，文獻(xiàn)［13］首次提出基于路徑模式的圖條件函數(shù)依賴，記做δ：Vn（X→Y，tp［X‖Y］），其中tp［X∪Y］為X∪Y上某個(gè)具體的取值，即對(duì)于A∈X∪Y，tp［A］為變量值或A的值域中某個(gè)特定的常量值。

文獻(xiàn)［11］提出的圖函數(shù)依賴也可表現(xiàn)為圖條件函數(shù)依賴，其對(duì)X→Y中屬性進(jìn)行語(yǔ)義擴(kuò)展，形成一種特定的圖條件函數(shù)依賴。在定義4中提到，X或Y的形式可以是屬性集合或常量集合。當(dāng)其為屬性集合時(shí)，GFD表現(xiàn)為圖函數(shù)依賴；當(dāng)其為常量集合時(shí)，GFD表現(xiàn)為圖條件函數(shù)依賴。為比較兩種圖條件函數(shù)依賴的不同，作為示例，表1中的δ1和φ5分別為基于路徑模式和基于圖模式的圖條件函數(shù)依賴，數(shù)據(jù)源于圖2。

數(shù)值型不一致廣泛存在于知識(shí)庫(kù)與社交網(wǎng)絡(luò)中［15，22，23］。為解決該問(wèn)題，文獻(xiàn)［15］基于GFD首次提出面向數(shù)值型不一致的圖函數(shù)依賴，使其包括線性算術(shù)表達(dá)式和內(nèi)嵌比較操作符，并稱為數(shù)值圖依賴（numericgraphdependency，NGD），一般記做φ：Q［μ］（X→Y）。其中，字面量集合μ包括集合X和Y，其包含屬性（如x.A、y.val）、數(shù)值常量（c）或布爾常量（如true、1）。NGD擴(kuò)展了X（Y）的語(yǔ)義范圍，加強(qiáng)了屬性與常量間的語(yǔ)義聯(lián)系，使其形式不局限于表示為屬性與常量的集合，而是表示為以符號(hào)和常量為操作數(shù)的線性算術(shù)表達(dá)式和內(nèi)嵌比較操作符的組合，記做e1e2。其中，e1（e2）為線性算術(shù)表達(dá)式，由屬性、常量和線性算術(shù)符號(hào)（如+、-、×、÷）組成，如e1：x.A+y.B，為內(nèi)嵌比較操作符（如lt;、gt;、≤、≥、≠、=）。

1.5基于外部約束拓展的圖依賴

圖依賴被視為數(shù)據(jù)質(zhì)量規(guī)則的一種，一般由語(yǔ)義約束與結(jié)構(gòu)約束兩種約束組成。為增強(qiáng)圖依賴的語(yǔ)義表示，文獻(xiàn)［16］引入了新的約束條件，提出了基于外部約束擴(kuò)展的圖依賴。

現(xiàn)有圖依賴僅面向于不關(guān)注時(shí)間信息的靜態(tài)圖，而在知識(shí)圖譜中屬性圖往往還帶有時(shí)間信息，稱為動(dòng)態(tài)圖。基于動(dòng)態(tài)圖的圖數(shù)據(jù)不一致問(wèn)題難以被基于語(yǔ)義約束或基于結(jié)構(gòu)約束拓展的圖依賴所捕獲。因此，文獻(xiàn)［16］針對(duì)新型不一致問(wèn)題，引入時(shí)間約束，提出時(shí)序圖函數(shù)依賴（temporalgraphfunctionaldependency，TGFD），一般記做φ：（Q［μ］，Δ，X→Y）。其中，Δ為時(shí)間區(qū)間，表示為（p，q）。引入時(shí)間約束后，在判定圖依賴是否成立時(shí)將不局限于單個(gè)子圖，而是會(huì)判定位于不同時(shí)間點(diǎn)的子圖間是否滿足圖依賴，并且只有當(dāng)子圖間的間隔時(shí)間在時(shí)間區(qū)間內(nèi)時(shí)，該圖依賴才成立。TGFD能很好地捕獲帶有時(shí)間信息的不一致圖數(shù)據(jù)，作為示例，表1中的φ4為時(shí)序圖函數(shù)依賴。

1.6圖依賴分類

圖依賴分類如圖4所示。

綜上，根據(jù)拓展的方式不同，對(duì)現(xiàn)有圖依賴進(jìn)行分類，并將拓展方式的不同歸納為約束的不同，并將現(xiàn)有圖依賴分為基于結(jié)構(gòu)約束拓展的圖依賴、基于語(yǔ)義約束拓展的圖依賴和基于外部約束拓展的圖依賴三類。

圖依賴是為了解決圖數(shù)據(jù)的數(shù)據(jù)一致性問(wèn)題而提出。因此三種圖依賴拓展方式有著不同的應(yīng)用場(chǎng)景。當(dāng)圖數(shù)據(jù)采取了新的存儲(chǔ)方式時(shí)，如從RDF圖到屬性圖，此時(shí)應(yīng)選用基于結(jié)構(gòu)約束拓展的方式定義新的圖依賴；若為捕獲實(shí)體（屬性）間的新型錯(cuò)誤，如需要對(duì)實(shí)體（屬性）進(jìn)行二次計(jì)算，此時(shí)應(yīng)選用基于語(yǔ)義約束拓展的方式定義新的圖依賴；若為捕獲新的不一致錯(cuò)誤，僅憑圖模式和函數(shù)依賴無(wú)法約束，此時(shí)，應(yīng)在原有基礎(chǔ)上引入外部約束，選用基于外部約束拓展的方式定義圖依賴。

若不局限于數(shù)據(jù)一致性問(wèn)題，除圖依賴以外，其余數(shù)據(jù)質(zhì)量規(guī)則在數(shù)據(jù)質(zhì)量領(lǐng)域也有著重要作用，如圖關(guān)聯(lián)規(guī)則和圖鍵。圖關(guān)聯(lián)規(guī)則表示指定節(jié)點(diǎn)所在圖模式?jīng)Q定節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系，往往用于針對(duì)知識(shí)圖譜的補(bǔ)全［10］；圖鍵表示決定指定節(jié)點(diǎn)唯一性的圖模式，往往用于解決面向圖數(shù)據(jù)的實(shí)體分辨［11］。

2經(jīng)典圖依賴挖掘算法

為獲得用于檢測(cè)數(shù)據(jù)一致性的圖依賴，一般有以下三種途徑［7］：a）由業(yè)內(nèi)專家根據(jù)先驗(yàn)知識(shí)指定圖依賴，主要適用于數(shù)據(jù)量少、圖結(jié)構(gòu)簡(jiǎn)單或?qū)＜医?jīng)驗(yàn)可信度較高的場(chǎng)合，但圖依賴數(shù)量往往較少；b）從圖中自動(dòng)挖掘圖依賴集合，主要適用于圖結(jié)構(gòu)復(fù)雜且專家不可得的場(chǎng)合，但往往質(zhì)量不高；c）結(jié)合專家領(lǐng)域知識(shí)，給定先驗(yàn)條件，從圖中挖掘出對(duì)應(yīng)圖依賴集合后，再由專家對(duì)圖依賴集合進(jìn)行篩選，適用于絕大多數(shù)場(chǎng)景。對(duì)于大型圖數(shù)據(jù)而言，僅依靠專家制訂的圖依賴集合的可靠性與數(shù)量難以保證，而圖依賴自動(dòng)挖掘算法從圖中挖掘相應(yīng)的圖依賴集合則不加選擇，因此難免搜索出很多對(duì)實(shí)際需求無(wú)意義的圖依賴。由于一般情況下需要同時(shí)結(jié)合專家知識(shí)和圖依賴自動(dòng)挖掘算法，所以可拓展性強(qiáng)且考慮部分先驗(yàn)知識(shí)的圖依賴自動(dòng)挖掘算法則被認(rèn)為更加可靠。

2.1圖依賴自動(dòng)挖掘框架

圖依賴自動(dòng)挖掘算法的目的是從大規(guī)模圖數(shù)據(jù)中（如至少包含數(shù)萬(wàn)個(gè)三元組的RDF數(shù)據(jù)集）發(fā)現(xiàn)有意義的圖依賴或其拓展集合。圖依賴自動(dòng)挖掘算法一般包含以下三個(gè)步驟：

a）圖模式挖掘算法，給定圖數(shù)據(jù)集，依靠圖模式生成算法或頻繁圖模式挖掘算法得到頻繁圖模式；b）圖模式匹配算法，給定頻繁圖模式和圖數(shù)據(jù)集，依靠圖模式匹配算法得到圖匹配數(shù)據(jù)；c）依賴挖掘算法，給定圖匹配數(shù)據(jù)，依靠依賴挖掘算法從匹配數(shù)據(jù)中發(fā)現(xiàn)對(duì)應(yīng)的圖依賴。

面向不同類型的圖依賴自動(dòng)挖掘算法一般由圖依賴自動(dòng)挖掘框架中不同步驟進(jìn)行區(qū)分。例如，圖條件函數(shù)依賴自動(dòng)挖掘算法與圖近似函數(shù)依賴自動(dòng)挖掘算法之間的區(qū)別在于選擇了不同的依賴挖掘算法。

2.2面向結(jié)構(gòu)約束拓展的圖依賴自動(dòng)挖掘算法

為挖掘出有意義的圖依賴，本文往往選擇頻繁的圖依賴，即在圖中出現(xiàn)頻率大于一定閾值的圖依賴。圖依賴的頻繁度往往由其圖結(jié)構(gòu)的頻繁度決定，而在圖依賴相關(guān)研究中，圖結(jié)構(gòu)有基于路徑模式表示和基于圖模式表示兩種表示方法。

文獻(xiàn)［13，17］以路徑模式表示圖結(jié)構(gòu)，并提出圖—表—圖的三步式轉(zhuǎn)換流程，即將圖結(jié)構(gòu)轉(zhuǎn)換為表結(jié)構(gòu)，之后轉(zhuǎn)換為圖結(jié)構(gòu)。先遍歷圖中每一個(gè)節(jié)點(diǎn)，在得到以各節(jié)點(diǎn)V為中心的n-跳躍圖后，將其轉(zhuǎn)換為以節(jié)點(diǎn)V為標(biāo)識(shí)的表，過(guò)程如圖5所示。其中n為步長(zhǎng)，而n-跳躍圖則表示以節(jié)點(diǎn)V為父節(jié)點(diǎn)及其所有n代內(nèi)子節(jié)點(diǎn)組成的圖。通過(guò)在關(guān)系型數(shù)據(jù)中應(yīng)用廣泛的頻繁模式挖掘算法——FP-growth算法［24］，從表中挖掘得到頻繁模式。由于在FP-growth算法中包括模式匹配算法，所以僅需根據(jù)返回的表格索引即可得到對(duì)應(yīng)匹配數(shù)據(jù)。

由于利用路徑模式表示圖結(jié)構(gòu)存在局限性，所以文獻(xiàn)［11］提出以圖模式表示圖結(jié)構(gòu)。同時(shí)為減少圖模式大量堆積帶來(lái)的內(nèi)存損耗，文獻(xiàn)［18，19］選擇以圖模式生成算法替代圖模式挖掘算法。由于圖模式挖掘算法中隱含一次圖匹配過(guò)程，利用圖模式生成算法得到圖模式可以減少一次圖匹配過(guò)程，從而提升算法效率，但圖模式的頻繁度并不支持反單調(diào)性，即頻繁圖的子圖并非一定頻繁，所以無(wú)法采用剪枝算法提升效率［18，24］。為利用反單調(diào)性保證算法時(shí)間復(fù)雜度，文獻(xiàn)［18］選擇以圖模式中心節(jié)點(diǎn)（pivotnode）的頻繁度替代圖依賴的頻繁度，而中心節(jié)點(diǎn)則由專家從圖模式中指定。

為進(jìn)一步提升算法效率，文獻(xiàn)［18］構(gòu)建GFD生成樹(shù)，算法分為縱向拓展與橫向拓展兩部分，如圖6所示?？v向拓展基于規(guī)模為1的圖模式自底向上生成所有規(guī)模小于k的圖模式；橫向拓展基于圖模式先匹配數(shù)據(jù)，后生成圖依賴，并驗(yàn)證依賴的有效性。在生成圖模式Q1后，根據(jù)圖模式提取相應(yīng)信息并驗(yàn)證該Q1對(duì)應(yīng)的所有圖依賴Q1.lvec。然后通過(guò)添加邊（或節(jié)點(diǎn)）的方式基于圖模式Q1進(jìn)行縱向拓展，直至沒(méi)有相應(yīng)圖模式或達(dá)到規(guī)模上限。該方法可以盡早去除非頻繁圖依賴，大幅減少了內(nèi)存占用，并且盡可能地減少了重復(fù)計(jì)算。

2.3面向語(yǔ)義與外部約束拓展的圖依賴自動(dòng)挖掘算法

圖依賴一般由結(jié)構(gòu)約束和語(yǔ)義約束組成，為獲得新型的圖依賴，通常有兩種方式：a）基于經(jīng)典的關(guān)系依賴（如條件函數(shù)依賴、數(shù)值型依賴）拓展為相應(yīng)的圖依賴（如圖條件函數(shù)依賴、數(shù)值型圖依賴）；b）引入外部約束增強(qiáng)圖依賴的語(yǔ)義表達(dá)能力。為發(fā)現(xiàn)基于語(yǔ)義約束拓展的圖依賴，相應(yīng)的關(guān)系依賴挖掘算法是必須的；為發(fā)現(xiàn)基于外部約束拓展的圖依賴，則需引入新步驟以檢驗(yàn)外部約束。

函數(shù)依賴在關(guān)系型數(shù)據(jù)庫(kù)中有著相當(dāng)多的拓展，關(guān)系依賴自動(dòng)挖掘算法發(fā)展的歷史幾乎與關(guān)系依賴一樣長(zhǎng)，有著相當(dāng)豐富的研究［21，25～33］?，F(xiàn)有關(guān)系依賴自動(dòng)挖掘算法可分為格結(jié)構(gòu)遍歷算法（latticetraversalalgorithms）、否定集和肯定集算法（difference-andagree-setalgorithms）與依賴歸納算法（dependencyinductionalgorithms）［29］三類。

絕大多數(shù)關(guān)系依賴自動(dòng)挖掘算法［30～32］均基于格結(jié)構(gòu)（lattice）搜索空間，其通過(guò)各屬性自頂向下遍歷得到所有候選屬性組合，圖7為基于屬性A、B、C、D建立的格搜索空間。

以自頂向下算法為例，為確定函數(shù)依賴γ：X→Y中的左部X與右部Y，從第1層開(kāi)始，寬度優(yōu)先遍歷節(jié)點(diǎn)Z，指向節(jié)點(diǎn)Z的上一層節(jié)點(diǎn)視做左部X，根據(jù)Y=Z＼{X}得到右部Y，即函數(shù)依賴可寫做γ：X→Z＼{X}。以圖7中虛線部分為例，可得到函數(shù)依賴γ：AC→D?；谠撍阉骺臻g，可以得到所有候選函數(shù)依賴的屬性遍歷組合。

文獻(xiàn)［17］基于條件函數(shù)依賴提出圖條件函數(shù)依賴，其在得到基于頻繁圖模式的圖匹配數(shù)據(jù)后，根據(jù)常量條件函數(shù)依賴挖掘算法CFDMiner［32］從中發(fā)現(xiàn)圖條件函數(shù)依賴。CFDMiner根據(jù)頻繁開(kāi)項(xiàng)集和閉項(xiàng)集，從開(kāi)項(xiàng)集選擇依賴左部，從閉項(xiàng)集選擇依賴右部，組成候選條件函數(shù)依賴，再判斷其是否成立。文獻(xiàn)［15］基于數(shù)值型依賴提出數(shù)值型圖依賴，其對(duì)數(shù)值屬性進(jìn)行單獨(dú)標(biāo)識(shí)使其能組合符合預(yù)定義長(zhǎng)度的線性算術(shù)表達(dá)式，從而使GFD生成樹(shù)［18］的橫向拓展可以匹配線性算術(shù)表達(dá)式。文獻(xiàn)［19］引入時(shí)間約束提出時(shí)序圖函數(shù)依賴，因此在判斷時(shí)序圖函數(shù)依賴是否成立時(shí)，在圖函數(shù)依賴的判定基礎(chǔ)上，其還會(huì)判斷不同子圖間的時(shí)間差是否滿足時(shí)間約束。

2.4圖依賴自動(dòng)挖掘算法優(yōu)化方法

由于圖相比于表有著更復(fù)雜的拓?fù)浣Y(jié)構(gòu)，也帶來(lái)了更大的計(jì)算代價(jià)，并且圖數(shù)據(jù)的規(guī)模越來(lái)越大?，F(xiàn)有圖依賴自動(dòng)挖掘算法主要針對(duì)圖挖掘和圖匹配部分進(jìn)行優(yōu)化，主要分為基于并行計(jì)算和基于圖匹配優(yōu)化。

文獻(xiàn)［18，34］提出了基于并行計(jì)算的圖自動(dòng)挖掘算法。為發(fā)現(xiàn)k-頻繁的圖依賴，做k2次循環(huán)，在每次循環(huán)中都會(huì)伴隨著橫向拓展與縱向拓展兩個(gè)任務(wù)。通過(guò)將任務(wù)分配給不同的處理器，從而達(dá)到提升算法效率的目標(biāo)。

大多數(shù)圖匹配技術(shù)往往在子圖同構(gòu)的基礎(chǔ)上通過(guò)制定剪枝和回溯策略、提取特征作為索引或挖掘數(shù)據(jù)共性保證匹配速度［21，35～37］。文獻(xiàn)［35］提出VF2算法，采用深度優(yōu)先的樹(shù)搜索策略，并使用一系列高效的規(guī)則集合對(duì)搜索樹(shù)進(jìn)行剪枝，并在待匹配的圖中尋找滿足匹配條件的點(diǎn)集，然后判斷新加入的點(diǎn)是否滿足匹配條件，如果滿足則繼續(xù)，否則就回溯。文獻(xiàn)［36］提出GIndex算法，為縮小索引規(guī)模，提取圖中具有強(qiáng)辨別力的頻繁子圖作為特征，并基于該特征對(duì)大規(guī)模多圖數(shù)據(jù)建立索引。文獻(xiàn)［37］則針對(duì)知識(shí)圖譜中RDF圖的特點(diǎn)，將RDF圖分解為多個(gè)語(yǔ)句模式的集合，將語(yǔ)句模式作為匹配的基本單元，匹配效率遠(yuǎn)高于傳統(tǒng)的圖匹配方法。

現(xiàn)有圖匹配技術(shù)往往考慮增量式圖匹配算法，其結(jié)合并行技術(shù)與圖匹配優(yōu)化技術(shù)以提升效率。增量式圖匹配能夠在教據(jù)圖或模式圖發(fā)生變化時(shí)避免重新在整個(gè)數(shù)據(jù)圖上進(jìn)行匹配、減少響應(yīng)時(shí)間，因此成為研究熱點(diǎn)［38］。文獻(xiàn)［39］使用基于子圖同構(gòu)的增量式圖匹配算法對(duì)原圖進(jìn)行處理，通過(guò)邊插入和邊刪除操作將原圖切分成多個(gè)子圖，從而實(shí)現(xiàn)匹配任務(wù)局部化并分配給不同的處理器。文獻(xiàn)［18］則將增量圖匹配思想融入圖依賴自動(dòng)挖掘框架以提升效率。

3基于圖依賴的數(shù)據(jù)一致性提升

數(shù)據(jù)一致性提升的主要任務(wù)是根據(jù)給定的圖依賴提高數(shù)據(jù)的一致性，而目前圖依賴最廣泛的應(yīng)用是數(shù)據(jù)一致性檢測(cè)。

現(xiàn)有基于圖依賴的一致性檢測(cè)的研究往往關(guān)注于結(jié)構(gòu)型不一致錯(cuò)誤和語(yǔ)義型不一致錯(cuò)誤［13，15，17］。結(jié)構(gòu)型不一致錯(cuò)誤往往包含了非法的圖結(jié)構(gòu)，只需利用圖模式匹配算法即可輕松捕獲錯(cuò)誤。語(yǔ)義型不一致錯(cuò)誤是指合法的圖結(jié)構(gòu)中包含了不一致的屬性，為捕獲此類不一致，往往先通過(guò)圖模式匹配算法得到匹配數(shù)據(jù)，再通過(guò)基于關(guān)系依賴的一致性檢測(cè)算法檢測(cè)出不一致數(shù)據(jù)。由于匹配數(shù)據(jù)是關(guān)系型數(shù)據(jù)，所以每一個(gè)匹配可被視做一個(gè)元組。

為提取元組中的屬性，常見(jiàn)的思路是順序掃描數(shù)據(jù)庫(kù)中的每條元組。為提升檢索效率，文獻(xiàn)［33］對(duì)依賴左部建立索引，從而使得算法在大規(guī)模的數(shù)據(jù)庫(kù)中有著更好的表現(xiàn)，而當(dāng)有多條依賴時(shí)，也可以使用并行計(jì)算的算法判斷元組是否違反依賴。文獻(xiàn)［30］通過(guò)等價(jià)類將同一屬性具有相同值的不同元組聚合到一起，縮小搜索空間，在大規(guī)模的數(shù)據(jù)庫(kù)中有著良好的表現(xiàn)。

文獻(xiàn)［15］提出了不局限于等價(jià)關(guān)系的數(shù)值圖依賴，從而捕獲知識(shí)圖譜中節(jié)點(diǎn)間的數(shù)值型不一致。為提高一致性檢測(cè)的效率，通過(guò)增量式一致性檢測(cè)算法。當(dāng)圖更新時(shí)，以邊作為基本單元對(duì)圖的更新部分進(jìn)行劃分，以此進(jìn)行一致性檢測(cè)。

由于多個(gè)圖依賴之間的矛盾關(guān)系難以判定、圖依賴左部所涉及節(jié)點(diǎn)的正確性難以保證，無(wú)標(biāo)準(zhǔn)圖數(shù)據(jù)集用于驗(yàn)證圖依賴有效性等原因，基于圖依賴的數(shù)據(jù)一致性修復(fù)問(wèn)題一直被視為一大挑戰(zhàn)［14，40］?？紤]到以條件函數(shù)依賴為代表的關(guān)系依賴在關(guān)系型數(shù)據(jù)中的良好表現(xiàn)［21，40］，基于圖依賴的一致性修復(fù)問(wèn)題應(yīng)作為重要研究方向?yàn)檠芯咳藛T所關(guān)注。

4現(xiàn)有問(wèn)題與展望

本章總結(jié)圖依賴研究方向中一些尚待解決的問(wèn)題，可作為未來(lái)研究的方向：

a）圖數(shù)據(jù)的一致性修復(fù)問(wèn)題函待解決。數(shù)據(jù)修復(fù)是數(shù)據(jù)質(zhì)量領(lǐng)域的重要研究方向之一，目前基于函數(shù)依賴對(duì)錯(cuò)誤數(shù)據(jù)進(jìn)行修復(fù)主要面向關(guān)系型數(shù)據(jù)庫(kù)［41］。由于圖數(shù)據(jù)庫(kù)有著更復(fù)雜且不規(guī)律的拓?fù)浣Y(jié)構(gòu)，導(dǎo)致只有很少工作聚焦于圖數(shù)據(jù)的修復(fù)工作［42］，并且圖依賴限定條件不夠嚴(yán)格，直接用于數(shù)據(jù)修復(fù)效果欠佳。文獻(xiàn)［42］提出了一種將圖關(guān)聯(lián)規(guī)則推導(dǎo)圖修復(fù)規(guī)則的方法，以達(dá)成數(shù)據(jù)修復(fù)的目的。而圖依賴相比于圖關(guān)聯(lián)規(guī)則有著更豐富的語(yǔ)義，理論上修復(fù)效果更好。因此，未來(lái)的研究方向可嘗試?yán)脠D依賴推導(dǎo)出新的圖修復(fù)規(guī)則，從而解決圖數(shù)據(jù)的一致性修復(fù)問(wèn)題。

b）現(xiàn)有圖依賴類型有限?，F(xiàn)有關(guān)系依賴種類遠(yuǎn)大于圖依賴種類［14，28］，而理論上每一種關(guān)系依賴均可視做函數(shù)依賴基于語(yǔ)義約束的拓展，并且圖依賴類型受限導(dǎo)致其應(yīng)用場(chǎng)景受限，因此未來(lái)的重要研究方向之一即根據(jù)關(guān)系依賴的語(yǔ)義拓展方向提出相應(yīng)的圖依賴，如基于近似函數(shù)依賴提出圖近似函數(shù)依賴。

c）專業(yè)領(lǐng)域應(yīng)用研究方興未艾。目前有關(guān)圖依賴的相關(guān)研究主要關(guān)注于利用圖依賴提高數(shù)據(jù)一致性，僅有少部分研究將圖依賴應(yīng)用于知識(shí)圖譜沖突解決［22］、數(shù)據(jù)庫(kù)拓展［10］和欺騙郵件檢測(cè)［13］，若能使相關(guān)研究落地，將有效推動(dòng)相關(guān)產(chǎn)業(yè)發(fā)展。

d）與前沿領(lǐng)域最新進(jìn)展結(jié)合不足。近年來(lái)，以BERT為代表的嵌入表示模型在知識(shí)圖譜補(bǔ)全任務(wù)中大放異彩，相比于基于規(guī)則推理的補(bǔ)全模型，其可解釋性更弱［43］。文獻(xiàn)［23］將RDF三元組連接成子句，并以子句作為推理目標(biāo)，關(guān)系（邊）作為推理步驟，然后將邊的權(quán)重與特征向量關(guān)聯(lián)構(gòu)建模型。由于基于規(guī)則推理的知識(shí)圖譜補(bǔ)全模型對(duì)規(guī)則依賴性強(qiáng)，而圖依賴?yán)碚撓噍^于其余數(shù)據(jù)質(zhì)量規(guī)則理論有著最豐富的研究。未來(lái)的研究方向可嘗試考慮基于圖依賴的知識(shí)圖譜補(bǔ)全模型。

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

圖依賴是數(shù)據(jù)質(zhì)量領(lǐng)域中重要的研究領(lǐng)域之一，具有巨大的研究?jī)r(jià)值以及發(fā)展前景。本文首先按照拓展方式不同，將常見(jiàn)的圖依賴劃分為三類；隨后根據(jù)三類圖依賴介紹了相應(yīng)圖依賴自動(dòng)挖掘算法的相關(guān)研究，分析了圖依賴在不一致數(shù)據(jù)檢測(cè)任務(wù)中的運(yùn)用，梳理了當(dāng)前研究存在的問(wèn)題；最后對(duì)圖依賴在數(shù)據(jù)質(zhì)量領(lǐng)域的發(fā)展研究提出展望。

本文的主要貢獻(xiàn)有：a）根據(jù)拓展的方式不同，對(duì)圖依賴進(jìn)行分類，并將拓展方式的不同歸納為約束的不同；b）總結(jié)并對(duì)比現(xiàn)有圖依賴挖掘方法，給出針對(duì)圖依賴挖掘的優(yōu)化方法發(fā)展趨勢(shì)；c）根據(jù)現(xiàn)有基于規(guī)則的數(shù)據(jù)修復(fù)方法，展望了基于圖依賴的數(shù)據(jù)修復(fù)，為未來(lái)的研究趨勢(shì)提供參考。

參考文獻(xiàn)：

［1］TalebI，SerhaniMA，BouhaddiouiC，etal.Bigdataqualityframework：aholisticapproachtocontinuousqualitymanagement［J］.JournalofBigData，2021，8（1）：1-41.

［2］ChangsooL，SunhoK，JinwooL，etal.Dataqualityassessmentformanufacturingprocesses［J］.ICICExpressLetters，2019，10（12）：1107-1113.

［3］LoshinD.數(shù)據(jù)質(zhì)量改進(jìn)實(shí)踐指南［M］.曹建軍，江春，許志，譯.北京：國(guó)防工業(yè)出版社，2016：10-12.（LoshinD.Thepractitioner’sguidetodataqualityimprovement［M］.CaoJianjun，JiangChun，XuZhi，Trans.Beijing：NationalDefenseIndustryPress，2016：10-12.）

［4］FanWenfei，GeertsF，TangNan，etal.Conflictresolutionwithdatacurrencyandconsistency［J］.ACMJournalofDataandInformationQuality，2014，5（1-2）：1-37.

［5］FanWenfei，GeertsF，MaShuai，etal.Dataqualityproblemsbeyondconsistencyandduplication［M］//SearchofEleganceintheTheoryandPracticeofComputation.Berlin：Springer，2013：237-249.

［6］FanWenfei，TangNan，GeertsF，etal.Inferringdatacurrencyandconsistencyforconflictresolution［C］//Procofthe29thIEEEInternationalConferenceonDataEngineering.Piscataway，NJ：IEEEPress，2013：470-481.

［7］工業(yè)和信息化部電子第五研究所.質(zhì)量大數(shù)據(jù)白皮書［R］.2022：22-32.（CEPREI.Qualitybigdatawhitepaper［R］.2022：22-32.）

［8］CaruccioL，DeufemiaV，PoleseG.Relaxedfunctionaldependencies—asurveyofapproaches［J］.IEEETransonKnowledgeandDataEngineering，2016，28（1）：147-165.

［9］FanWenfei，WuYinghui，XuJingbo.Functionaldependenciesforgraphs［C］//ProcofInternationalConferenceonManagementofData.NewYork：ACMPress，2016：1843-1857.

［10］FanWenfei，WangXin，WuYinghui，etal.Associationruleswithgraphpatterns［J］.ProcoftheVLDBEndowment，2015，8（12）：1502-1513.

［11］FanWenfei，F(xiàn)anZhe，TianChao，etal.Keysforgraphs［J］.ProcoftheVLDBEndowment，2015，8（12）：1590-1601.

［12］FanWenfei，LuPing.Functionaldependenciesforgraphs［J］.ACMTransonDatabaseSystems，2019，44（2）：1-40.

［13］YuYang，HeflinJ.ExtendingfunctionaldependencytodetectabnormaldatainRDFgraphs［C］//Procofthe10thInternationalConfe-renceontheSemanticWeb.Berlin：Springer，2011：794-809.

［14］FanWenfei.Dependenciesforgraphs：challengesandopportunities［J］.ACMJournalofDataandInformationQuality，2019，1（1）：1-10.

［15］FanWenfei，LiuXueli，LuPing，etal.Catchingnumericinconsistenciesingraphs［J］.ACMTransonDatabaseSystems，2020，45（2）：1-47.

［16］AlipourlangouriM，MansfieldA，ChiangF，etal.Temporalgraphfunctionaldependencies［EB/OL］.（2021-08-19）.https：//arxiv.org/abs/2108.08719v5.

［17］HeBinbin，ZouLei，ZhaoDongyan.UsingconditionalfunctionaldependencytodiscoverabnormaldatainRDFgraphs［C］//ProcofSemanticWebInformationManagement.NewYork：ACMPress，2014：1-7.

［18］FanWenfei，HuChunming，LiuXueli，etal.Discoveringgraphfunctionaldependencies［C］//ProcofInternationalConferenceonMa-nagementofData.NewYork：ACMPress，2018：427-439.

［19］NoronhaL，ChiangF.Discoveryoftemporalgraphfunctionaldepen-dencies［C］//Procofthe30thACMInternationalConferenceonInformationandKnowledgeManagement.NewYork：ACMPress，2021：3348-3352.

［20］劉勇.圖模式發(fā)現(xiàn)技術(shù)的研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2010.（LiuYong.Researchongraphpatterndiscoverytechnology［D］.Harbin：HarbinInstituteofTechnology，2010.）

［21］BohannonP，F(xiàn)anWenfei，GeertsF，etal.Conditionalfunctionaldependenciesfordatacleaning［C］//Procofthe23rdInternationalConferenceonDataEngineering.Piscataway，NJ：IEEEPress，2007：746-755.

［22］MaJiangtao，WangYanjun，ChenXueting，etal.NGDcrm：anumericgraphdependency-basedconflictresolutionmethodforknowledgegraph［J］.HighTechnologyLetters，2021，27（2）：153-162.

［23］WangWY，MazaitisK，LaoNi，etal.Efficientinferenceandlearninginalargeknowledgebase：reasoningwithextractedinformationusingalocallygroundablefirst-orderprobabilisticlogic［J］.MachineLearning，2015，100（1）：101-126.

［24］HanJiawei，PeiJian，YinYiwen，etal.Miningfrequentpatternswithoutcandidategeneration：afrequent-patterntreeapproach［J］.DataMiningandKnowledgeDiscovery，2004，8（1）：53-87.

［25］KivinenJ，MannilaH.Approximatedependencyinferencefromrelations［C］//Procofthe4thInternationalConferenceonDatabaseTheory.NewYork：ACMPress，1992：86-98.

［26］CoddEF.Relationalcompletenessofdatabasesublanguages［J］.ComputerScience，1972，1972：65-98.

［27］CaldersT，RamonJ，DyckVD.Anti-monotonicoverlap-graphsupportmeasures［C］//Procofthe23rdIndustrialConferenceonDataMining.NewYork：ACMPress，2008：73-82.

［28］CaruccioL，DeufemiaV，PoleseG.Relaxedfunctionaldependencies—asurveyofapproaches［J］.IEEETransonKnowledgeandDataEngineering，2016，28（1）：147-165.

［29］PapenbrockT，EhrlichJ，MartenJ，etal.Functionaldependencydiscovery：anexperimentalevaluationofsevenalgorithms［J］.ProcoftheVLDBEndowment，2015，8（10）：1082-1093.

［30］HuhtalaY，KrkkinenJ，PorkkaP，etal.TANE：anefficientalgorithmfordiscoveringfunctionalandapproximatedependencies［J］.ComputerJournal，1999，42（2）：100-111.

［31］FanWenfei，GeertsF，LiJianzhong，etal.Discoveringconditionalfunctionaldependencies［J］.IEEETransonKnowledgeandDataEngineering，2011，23（5）：683-698.

［32］QahtanA，TangN，OuzzaniM，etal.ANMAT：automaticknowledgediscoveryanderrordetectionthroughpatternfunctionaldependency［C］//ProcofInternationalConferenceonManagementofDataEngineering.NewYork：ACMPress，2019：1977-1980.

［33］XiaoRenjie，YuanYA，TanZijing，etal.Dynamicfunctionaldepen-dencydiscoverywithdynamichittingsetenumeration［C］//Procofthe38thIEEEInternationalConferenceonDataEngineering.Pisca-taway，NJ：IEEEPress，2022：286-298.

［34］FanWenfei，LiuXueli，CaoYingjie.Parallelreasoningofgraphfunctionaldependencies［C］//ProcofInternationalConferenceonDataEngineering.Piscataway，NJ：IEEEPress，2018：593-604.

［35］CordellaLP，F(xiàn)oggiaP，SansoneC，etal.A（sub）graphisomorphismalgorithmformatchinglargegraphs［J］.IEEETransonPatternAnalysisandMachineIntelligence，2004，26（10）：1367-1372.

［36］YanXifeng，HanJiawei.gSpan：graph-basedsubstructurepatternmining［C］//ProcofIEEEInternationalConferenceonDataMining.Piscataway，NJ：IEEEPress，2002：721-724.

［37］汪錦嶺，金蓓弘，李京.一種高效的RDF圖模式匹配算法［J］.計(jì)算機(jī)研究與發(fā)展，2005，42（10）：1763-1770.（WangJinling，JinPeihong，LiJing.AnefficientmatchingalgorithmforRDFgraphpatterns［J］.JournalofResearchandDevelopment，2005，42（10）：1763-1770.）

［38］張麗霞，王偉平，高建良，等.面向模式圖變化的增量圖模式匹配［J］.軟件學(xué)報(bào)，2015，26（11）：2964-2980.（ZhangLixia，WangWeiping，GaoJianliang，etal.Patterngraphchangeorientedincrementalgraphpatternmatching［J］.JournalofSoftware，2015，26（11）：2964-2980.）

［39］FanWenfei，LiJianzhong，LuoJizhou，etal.Incrementalgraphpatternmatching［C］//ProcofACMSIGMODInternationalConferenceonManagementofData.NewYork：ACMPress，2014：601-610.

［40］金澈清，劉輝平，周傲英.基于函數(shù)依賴與條件約束的數(shù)據(jù)修復(fù)方法［J］.軟件學(xué)報(bào)，2016，27（7）：1671-1684.（JinCheqing，LiuHuiping，ZhouAoying.Functionaldependencyandconditionalconstraintbaseddatarepair［J］.JournalofSoftware，2016，27（7）：1671-1684.）

［41］QahtanA，TangNan，OuzzaniM，etal.Patternfunctionaldependenciesfordatacleaning［J］.ProcoftheVLDBEndowment，2020，31（5）：684-697.

［42］ChengYurong，ChenLei，YuanYe，etal.Strictandflexiblerule-basedgraphrepairing［J］.IEEETransonKnowledgeandDataEngineering，2022，34（7）：3521-3535.

［43］ChenZhe，WangYuehan，ZhaoBin，etal.Knowledgegraphcompletion：areview［J］.IEEEAccess，2020，8：192435-192456.

［44］于靜，劉燕兵，張宇，等.大規(guī)模圖數(shù)據(jù)匹配技術(shù)綜述［J］.計(jì)算機(jī)研究與發(fā)展，2015，52（2）：391-409.（YuJing，LiuYanbing，ZhangYu，etal.Surveyonlarge-scalegraphpatternmatching［J］.JournalofComputerResearchandDevelopment，2015，52（2）：391-409.）

［45］項(xiàng)英倬，譚菊仙，韓杰思，等.圖匹配技術(shù)研究［J］.計(jì)算機(jī)科學(xué)，2018，45（6）：27-31，45.（XiangYingzhuo，TanJuxian，HanJiesi，etal.Surveyofgraphmatchingalgorithms［J］.JournalofCompu-terScience，2018，45（6）：27-31，45.）