基于OPM的數(shù)據(jù)依賴關(guān)系分析研究

董宇超，張文生

基于OPM的數(shù)據(jù)依賴關(guān)系分析研究

董宇超，張文生

如何對(duì)數(shù)據(jù)起源語(yǔ)義信息進(jìn)行分析是數(shù)據(jù)起源追蹤領(lǐng)域的關(guān)鍵問(wèn)題之一?；贠PM，在建立的數(shù)據(jù)起源依賴關(guān)系概念及其操作的基礎(chǔ)上，提出了一種數(shù)據(jù)依賴關(guān)系分析方法，利用細(xì)化操作和合成操作分析數(shù)據(jù)依賴關(guān)系，并具體給出數(shù)據(jù)依賴細(xì)化算法和合成算法。實(shí)驗(yàn)表明，提出的方法，具有完備的語(yǔ)義和多項(xiàng)式級(jí)別的算法復(fù)雜度，存儲(chǔ)耗費(fèi)也有所降低，可以滿足不同用戶對(duì)于不同抽象層次數(shù)據(jù)起源信息查詢的需求，很好地提高了數(shù)據(jù)起源追蹤的有效性和針對(duì)性。

數(shù)據(jù)依賴關(guān)系；數(shù)據(jù)起源；細(xì)化操作；合成操作；數(shù)據(jù)起源開(kāi)放模型

0　引言

近幾年，隨著大數(shù)據(jù)管理的迫切需要，數(shù)據(jù)起源追蹤［1］［2］［3］［4］成為嶄新的國(guó)內(nèi)外研究熱點(diǎn)。數(shù)據(jù)起源又稱為數(shù)據(jù)血統(tǒng)、數(shù)據(jù)世系、數(shù)據(jù)溯源、數(shù)據(jù)譜系、數(shù)據(jù)血緣和數(shù)據(jù)來(lái)源等，是對(duì)數(shù)據(jù)處理的整個(gè)歷史的信息，包括數(shù)據(jù)產(chǎn)生和隨著時(shí)間推移而演變的整個(gè)過(guò)程。在抽象級(jí)別上，起源是一種依賴關(guān)系，描述數(shù)據(jù)產(chǎn)品是如何得到的，相關(guān)的數(shù)據(jù)和過(guò)程的作用是什么，角色是什么。

目前，數(shù)據(jù)起源依賴關(guān)系分析的主流模型之一為OPM（The Open Provenance Model）［5］［6］，OPM是數(shù)據(jù)起源開(kāi)放模型，支持各種起源技術(shù)的互操作。OPM 基于有向無(wú)環(huán)圖，表示數(shù)據(jù)產(chǎn)品和計(jì)算中關(guān)聯(lián)的過(guò)程，以及他們之間的因果依賴關(guān)系。

通過(guò)OPM能夠得到數(shù)據(jù)和數(shù)據(jù)的因果依賴關(guān)系，但是不同的用戶想要看到的因果依賴關(guān)系是不同的，有的想看全局的概貌，有的想看局部的細(xì)節(jié)。為此，本文基于OPM，對(duì)數(shù)據(jù)起源中數(shù)據(jù)依賴關(guān)系進(jìn)行深入分析，引入細(xì)化和合成操作，提出一種數(shù)據(jù)起源中數(shù)據(jù)依賴的分析方法，完成數(shù)據(jù)依賴關(guān)系在全局和不同層次的局部之間靈活轉(zhuǎn)換，形成不同的依賴關(guān)系視圖，滿足不同用戶對(duì)于不同抽象層次數(shù)據(jù)起源信息查詢的需求。具體貢獻(xiàn)包括：

（1）為了有效支撐數(shù)據(jù)依賴關(guān)系分析，針對(duì)數(shù)據(jù)依賴存在的不同情況，定義數(shù)據(jù)依賴、部分?jǐn)?shù)據(jù)依賴、完全數(shù)據(jù)依賴等。在此基礎(chǔ)上，定義數(shù)據(jù)依賴的細(xì)化和合成操作，并進(jìn)一步根據(jù)部分?jǐn)?shù)據(jù)依賴、完全數(shù)據(jù)依賴分別深入定義，完成通過(guò)數(shù)據(jù)依賴關(guān)系分析生成用戶視圖的基礎(chǔ)體系；

（2）為了實(shí)現(xiàn)數(shù)據(jù)依賴從概貌到細(xì)節(jié)的轉(zhuǎn)化，針對(duì)部分?jǐn)?shù)據(jù)依賴、完全數(shù)據(jù)依賴不同情況，提出數(shù)據(jù)依賴的細(xì)化規(guī)則，并給出具體細(xì)化算法，形成數(shù)據(jù)依賴關(guān)系從抽象到具體的分析；

（3）為了實(shí)現(xiàn)數(shù)據(jù)依賴從細(xì)節(jié)到概貌的轉(zhuǎn)化，針對(duì)部分?jǐn)?shù)據(jù)依賴、完全數(shù)據(jù)依賴不同情況，提出數(shù)據(jù)依賴的合成規(guī)則，并給出具體合成算法，形成數(shù)據(jù)依賴關(guān)系從具體到抽象的分析；

（4）從語(yǔ)義完備性、存儲(chǔ)耗費(fèi)、提出算法復(fù)雜度三個(gè)方面，與直接使用OPM進(jìn)行數(shù)據(jù)依賴分析進(jìn)行對(duì)比，說(shuō)明提出的分析方法具有優(yōu)勢(shì)。

1　數(shù)據(jù)依賴關(guān)系定義及操作

數(shù)據(jù)起源依賴關(guān)系在本質(zhì)上是數(shù)據(jù)起源的語(yǔ)義信息，本文在前期研究中提出的數(shù)據(jù)起源追蹤架構(gòu)下［7］，基于OPM關(guān)于因果關(guān)系定義的基礎(chǔ)上，給出數(shù)據(jù)起源依賴關(guān)系和數(shù)據(jù)依賴關(guān)系定義，然后，具體定義了數(shù)據(jù)依賴關(guān)系的細(xì)化和合成操作。

1.1數(shù)據(jù)依賴關(guān)系

定義1 數(shù)據(jù)起源依賴關(guān)系 定義為一個(gè)6元組

DP_Dependency=（Data_Set，Process_Set，

Data_Data_Dependency，Data_Process_Dependency，

Process_Data_Dependency，

Process _Process_Dependency），其中

（1）Data_Set是數(shù)據(jù)的集合；

（2）Process_Set是過(guò)程的集合；

（3）Data_Data_Dependency：Data_Set → Data_Set，

是數(shù)據(jù)到數(shù)據(jù)的映射關(guān)系，稱為數(shù)據(jù)依賴關(guān)系；

（4）Data_Process_Dependency：Data_Set → Process _Set，是數(shù)據(jù)到過(guò)程的映射關(guān)系，稱為過(guò)程對(duì)數(shù)據(jù)依賴關(guān)系，即過(guò)程依賴于數(shù)據(jù)，數(shù)據(jù)是過(guò)程的輸入；

（5）Process_Data_Dependency：Process_Set → Data _Set，是過(guò)程到數(shù)據(jù)的映射關(guān)系，稱為數(shù)據(jù)對(duì)過(guò)程依賴關(guān)系，即數(shù)據(jù)依賴于過(guò)程，數(shù)據(jù)是過(guò)程的輸出。過(guò)程對(duì)數(shù)據(jù)依賴關(guān)系和數(shù)據(jù)對(duì)過(guò)程依賴關(guān)系統(tǒng)稱為控制依賴關(guān)系；

（6）Process_Process_Dependency：Process_Set →Pr -ocess_Set，是過(guò)程到過(guò)程的映射關(guān)系，稱為過(guò)程依賴關(guān)系。

對(duì)應(yīng)于OPM，WasGeneratedBy和Used表示的是控制依賴關(guān)系，WasDerivedFrom表示的是數(shù)據(jù)依賴關(guān)系，WasInformedBy表示的是過(guò)程依賴關(guān)系。

定義2 數(shù)據(jù)依賴對(duì)于一個(gè)給定的源數(shù)據(jù)Source_Data，存在依賴序列s=﹤Source_Data，D1，D2，…Dn，Sink_Data﹥，滿足：

Source_Data，D1， D2， …， Dn， Sink_Data ∈ Data_Set；

（1）有e0，e1，…，en∈ Data_Data_Dependency， ei=Data_Data_Dependency （ei-1）， 0 ≤ i ≤n。

（2）則s為Source_Data的一個(gè)數(shù)據(jù)依賴，即Source_Data由Sink_Data演化而來(lái)。

定義3完全數(shù)據(jù)依賴 對(duì)于給定的數(shù)據(jù)Source_Data和Sink_Data，Source_Data數(shù)據(jù)依賴于Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，如果O1，…，Om→Ii， i ≤ n，則I1，…，In完全依賴于O1，…，Om，即Source_Data完全數(shù)據(jù)依賴于Sink_Data，記作Source_DataSink_Data。

定義4部分?jǐn)?shù)據(jù)依賴 對(duì)于給定的數(shù)據(jù)Source_Data和Sink_Data，Source_Data數(shù)據(jù)依賴于Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，如果Oi→Ij，i≤m，j≤n，則Source_Data的一項(xiàng)數(shù)據(jù)依賴于Sink_Data的一項(xiàng)，稱Source_Data部分?jǐn)?shù)據(jù)依賴于Sink_Data，記作Source_DataSink_Data。

1.2數(shù)據(jù)依賴細(xì)化與合成操作

定義5 數(shù)據(jù)起源依賴關(guān)系細(xì)化操作 DP_Dep1、DP_Dep2是兩個(gè)數(shù)據(jù)起源依賴關(guān)系，定義DP_Dep1的細(xì)化DP_Dep2，記為DP_Dep1﹤DP_Dep2，具體如下：

（1）Data_SetDP_Dep1? Data_SetDP_Dep2

（2）Process_SetDP_Dep1? Process_SetDP_Dep2

（3）Data_Data_DependencyDP_Dep1? Data_Data_DependencyDP_Dep2

（4）Data_Process_DependencyDP_Dep1? Data_Process_DependencyDP_Dep2

（5）Process_Data_DependencyDP_Dep1? Process_Data_DependencyDP_Dep2

（6）Process_Process_DependencyDP_Dep1? Process_Process_DependencyDP_Dep2

定義6 數(shù)據(jù)起源依賴關(guān)系合成操作 DP_Dep1、DP_Dep2是兩個(gè)數(shù)據(jù)起源依賴關(guān)系圖，定義DP_Dep1的合成DP_Dep2，記為DP_Dep1﹥DP_Dep2，具體如下：

（1）Data_SetDP_Dep1? Data_SetDP_Dep2

（2）Process_SetDP_Dep1? Process_SetDP_Dep2

（3）Data_Data_DependencyDP_Dep1? Data_Data_DependencyDP_Dep2

（4）Data_Process_DependencyDP_Dep1? Data_Process_DependencyDP_Dep2

（5）Process_Data_DependencyDP_Dep1? Process_Data_DependencyDP_Dep2

（6）Process_Process_DependencyDP_Dep1? Process_Process_DependencyDP_Dep2

定義7 數(shù)據(jù)依賴的細(xì)化 對(duì)于給定的數(shù)據(jù)Source_Data和Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，如果 Source_Data和Sink_Data滿足完全依賴關(guān)系dep1，Source_Data和Sink_Data滿足部分依賴關(guān)系dep2，那么dep2是dep1的細(xì)化，記作dep1﹤dep2。

定義8 數(shù)據(jù)依賴的合成 給定數(shù)據(jù)依賴關(guān)系圖DGraph=（Node_Set，Edge_Set， Role_Set），通過(guò)完全數(shù)據(jù)依賴的合成和部分?jǐn)?shù)據(jù)依賴合成得到的新的數(shù)據(jù)依賴關(guān)系New_DG，稱New_DG是DGraph的一個(gè)數(shù)據(jù)依賴的合成，記作DGraph﹥New_DG。

定義9完全數(shù)據(jù)依賴的合成 給定數(shù)據(jù)依賴圖DGraph=（Node_Set， Edge_Set， Role_Set），如果?Child_DP ?Dgraph，Child_DP=（N，E，R），N? Node_Set，E ? Edge_Set，R ? Role_Set，滿足N=Ns∪Nf，Ns=｛Ns1，Ns2，…， Nsi｝，是邊起點(diǎn)集合， Nf=｛Nf1，Nf2，…， Nfj｝，是邊終點(diǎn)集合，則圖（N，E）是完全二分有向圖。如果R都是完全數(shù)據(jù)依賴，那么Ns中結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn)s， Nf中結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn)f，集合E中的邊合并成一條邊e=＜s，f＞，記生成的圖Dgraph－Child_DP + （｛s，f｝，e，role）為New_DG，則New_DG是DGraph的一個(gè)完全數(shù)據(jù)依賴的合成，其中role為完全數(shù)據(jù)依賴。

定義10部分?jǐn)?shù)據(jù)依賴的合成 給定數(shù)據(jù)依賴圖DGraph=（Node_Set， Edge_Set，Role_Set），如果?Child_DP?Dgraph，Child_DP=（N，E，R），N ? Node_Set，E ?Edge_Set，R ? Role_Set，滿足N=Ns∪Nf，Ns=｛Ns1，Ns2，…，Nsi｝，是邊起點(diǎn)集合， Nf=｛Nf1，Nf2，…， Nfj｝，是邊終點(diǎn)集合，則圖（N，E）是完全二分有向圖。如果R都是部分?jǐn)?shù)據(jù)依賴，那么Ns中結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn)s， Nf中結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn)f，集合E中的邊合并成一條邊e=＜s，f＞，記生成的圖Dgraph－Child_DP + （｛s，f｝，e， role）為New_DG，則New_DG是DGraph的一個(gè)部分?jǐn)?shù)據(jù)依賴的合成，其中role為部分?jǐn)?shù)據(jù)依賴。

定義11參數(shù) 在一個(gè)過(guò)程Process的執(zhí)行過(guò)程中，如果輸入Parameter是過(guò)程執(zhí)行的參數(shù)，不產(chǎn)生直接對(duì)應(yīng)的輸出數(shù)據(jù)；或者是過(guò)程執(zhí)行的數(shù)據(jù)，產(chǎn)生對(duì)應(yīng)的輸出數(shù)據(jù)，但輸出數(shù)據(jù)只是中間產(chǎn)品。則Parameter不再籠統(tǒng)的稱作輸入數(shù)據(jù)，而是稱作參數(shù)。

2　數(shù)據(jù)依賴關(guān)系分析

則不進(jìn)行任何替換。

算法具體執(zhí)行過(guò)程如表1所示：

表1　數(shù)據(jù)依賴的細(xì)化規(guī)則及算法

針對(duì)不同用戶的不同層次數(shù)據(jù)依賴關(guān)系的需求，提出了一種數(shù)據(jù)依賴關(guān)系分析方法，基于細(xì)化和合成操作，設(shè)計(jì)了一系列數(shù)據(jù)依賴細(xì)化與合成規(guī)則，并且具體給出了細(xì)化與合成算法。

2.1數(shù)據(jù)依賴的細(xì)化規(guī)則及算法

首先定義數(shù)據(jù)依賴的細(xì)化規(guī)則，如下所示。

規(guī)則1 輸入數(shù)據(jù)和參數(shù)規(guī)則 對(duì)于給定的數(shù)據(jù)Source_Data和Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，Source_DataSink_Data，如果有一個(gè)Oi是參數(shù)，i≤m，則將Source_DataSink_Data替換為在參數(shù)Oi的條件下，｛I1，…，In｝｛O1，…，Oi-1，Oi+1，…，Om｝。如果Oi都是輸入數(shù)據(jù)，i≤m，則不進(jìn)行任何處理。

規(guī)則2 完全數(shù)據(jù)依賴規(guī)則 對(duì)于給定的數(shù)據(jù)Source_Data和Sink_Data， Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝， Source_DataSink_Data。如果滿足Oi→Ij，i≤m， j≤n，則將Source_DataSink_Data替換為Source_DataSink_Data。如果不滿足Oi→Ij，i≤m，j≤n，則不進(jìn)行任何替換。

規(guī)則3 部分?jǐn)?shù)據(jù)依賴規(guī)則 對(duì)于給定的數(shù)據(jù)Source_Data和Sink_Data， Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝， Source_DataSink_Data，

1. 初始化數(shù)據(jù)變量Source_Data和Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝， i ≤m， j ≤ n；

2. 初始化Dep=Data_Data_Dependency－｛Source_Data→Sink_Data｝；

3. 初始化變量role；

4. 初始化變量i=1；

//細(xì)化階段

5. do ｛

6. do ｛

7. if （Oi是parameter） 根據(jù)規(guī)則1處理；

8. i=i + 1；

9. ｝While （i ≤ m）

10. switch （role類型） ｛

11. case 完全數(shù)據(jù)依賴：根據(jù)規(guī)則2處理；break；

12. case 部分?jǐn)?shù)據(jù)依賴：根據(jù)規(guī)則3處理；break；

13. ｝

14. Dep=Dep－｛Source_Data→Sink_Data｝；

15. 將數(shù)據(jù)依賴圖中下一個(gè)依賴關(guān)系的數(shù)據(jù)存放在變 量Source_Data和Sink_Data中；

16. 初始化變量role；

17. 初始化變量i=1；

18.｝While （Dep不為空）

return 得到細(xì)化數(shù)據(jù)依賴圖。

2.2數(shù)據(jù)依賴的合成規(guī)則及算法

首先定義數(shù)據(jù)依賴的合成規(guī)則，如下所示。

規(guī)則4完全數(shù)據(jù)依賴合成規(guī)則 數(shù)據(jù)集合｛I1，…，In｝和｛O1，…，Om｝，滿足完全依賴，i≤m， j≤n。如果記Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝， 則原依賴關(guān)系替換成Source_DataSink_Data。

規(guī)則5部分?jǐn)?shù)據(jù)依賴合成規(guī)則 對(duì)于數(shù)據(jù)集合｛I1，…，In｝和｛O1，…，Om｝，部分依賴滿足，i≤m， j≤n。如果記Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，則原依賴關(guān)系替換成Source_DataSink_Data。

算法具體執(zhí)行過(guò)程如表2所示：

表2　數(shù)據(jù)依賴的合成規(guī)則及算法

Node_Set=Data_Set；Edge_Set=Data_Data_Dependency；Role_Set=｛完全數(shù)據(jù)依賴，部分?jǐn)?shù)據(jù)依賴｝；Data_Data_Dependency Data_Set×Data_Set。輸出：細(xì)化的數(shù)據(jù)依賴圖//初始化階段1. 初始化數(shù)據(jù)依賴圖Data_Data_Dependency_ Graph，包括Data_Set， Data_Data_Dependency和Role_Set ；2. 初始化數(shù)據(jù)變量Source_Data；3. 初始化Dep=Data_Data_Dependency；4. 初始化變量role；//合成階段5. do｛6. 取數(shù)據(jù)依賴圖中與Source_Data有完全依賴關(guān)系的結(jié)點(diǎn)，根據(jù)規(guī)則4處理；7. 數(shù)據(jù)依賴圖中與Source_Data有部分依賴關(guān)系的結(jié)點(diǎn)，根據(jù)規(guī)則5處理；8. 取下一個(gè)結(jié)點(diǎn)存入Source_Data；9.｝While （數(shù)據(jù)依賴圖沒(méi)有遍歷完）10. 得到合成數(shù)據(jù)依賴圖。

3　性能分析

本文從實(shí)現(xiàn)層上對(duì)OPM進(jìn)行細(xì)化，利用細(xì)化或合成操作，分析數(shù)據(jù)依賴關(guān)系，滿足不同用戶對(duì)于數(shù)據(jù)起源追蹤不同視圖的需求。本文提出的數(shù)據(jù)依賴關(guān)系分析方法具體有如下3個(gè)方面的優(yōu)勢(shì)：

（1）語(yǔ)義性

本文基于依賴關(guān)系分析的需求，進(jìn)行數(shù)據(jù)起源語(yǔ)義信息的標(biāo)注，標(biāo)注的結(jié)果即是數(shù)據(jù)起源的控制依賴關(guān)系，從控制依賴關(guān)系著手，根據(jù)規(guī)則，得到數(shù)據(jù)依賴。所以，其數(shù)據(jù)依賴語(yǔ)義性是完備的。例如圖1所示：

圖1　控制依賴圖

控制依賴圖，得到數(shù)據(jù)依賴圖。如圖2所示：

圖2　數(shù)據(jù)依賴圖

（2）存儲(chǔ)耗費(fèi)

本文針對(duì)數(shù)據(jù)起源依賴關(guān)系分析，進(jìn)行數(shù)據(jù)起源信息的標(biāo)注（標(biāo)注的結(jié)果即為控制依賴關(guān)系），與OPM中數(shù)據(jù)起源信息的標(biāo)注相比，需要的存儲(chǔ)空間相對(duì)減少了。例如圖1所示的控制依賴圖，為了起源依賴關(guān)系分析，其存儲(chǔ)耗費(fèi)為S=Data_Store + Process_Store + Data_Process_Store

=8+6+14=28，而OPM存儲(chǔ)耗費(fèi)為S=Data_Store + Process_Store + Data_Process_Store + Data_Data_Store + Process_ Process_Store=8+6+14+8+6=42，則本文方法與OPM方法的存儲(chǔ)耗費(fèi)百分比為28/42=2/3，具體如圖3所示：

圖3　存儲(chǔ)空間耗費(fèi)比較

（3）算法復(fù)雜度

本文方法依據(jù)OPM中因果依賴關(guān)系，利用細(xì)化或合成操作進(jìn)行分析，獲得數(shù)據(jù)起源追蹤中數(shù)據(jù)依賴的不同視圖，滿足用戶不同層次起源信息的需求。方法中不論是細(xì)化算法還是合成算法，其算法復(fù)雜度都是多項(xiàng)式級(jí)別的，具體為：

細(xì)化依算法采用每?jī)蓚€(gè)結(jié)點(diǎn)進(jìn)行比較的思路，假設(shè)有n個(gè)結(jié)點(diǎn)的數(shù)據(jù)依賴圖Dep_Graph，則對(duì)兩個(gè)結(jié)點(diǎn)的依賴關(guān)系進(jìn)行細(xì)化。當(dāng)Dep_Graph每?jī)蓚€(gè)結(jié)點(diǎn)都有邊的情況下，是需要計(jì)算最多的時(shí)候。而在這種情況下，算法的復(fù)雜情況是，所以算法的復(fù)雜度是O（n2）。

合成算法采用廣度優(yōu)先搜索來(lái)搜索到每一個(gè)結(jié)點(diǎn)的相鄰結(jié)點(diǎn)，進(jìn)行是否是二分圖判斷，根據(jù)判斷的三種情況分別進(jìn)行完全依賴合成、部分依賴合成和不合成處理。算法的復(fù)雜度由廣度優(yōu)先搜索、二分圖判斷和合成處理三部分組成。如果在一個(gè)圖中得到最優(yōu)的數(shù)據(jù)依賴的合成，即得到最大的二分圖，那么復(fù)雜度是NP-hard的。如果采用只是對(duì)一個(gè)結(jié)點(diǎn)搜索相鄰結(jié)點(diǎn)，然后進(jìn)行判斷處理的方式，則算法的復(fù)雜度是多項(xiàng)式級(jí)別的。

4　總結(jié)

本文基于OPM，從依賴關(guān)系的角度，定義了數(shù)據(jù)起源的語(yǔ)義信息，提出了一種數(shù)據(jù)起源追蹤中數(shù)據(jù)依賴關(guān)系分析的方法，利用細(xì)化和合成操作進(jìn)行具體分析，給出了具體的規(guī)則和算法。最后，通過(guò)分析說(shuō)明，本文提出的方法具有完備的語(yǔ)義，耗費(fèi)的存儲(chǔ)空間較少，算法復(fù)雜度是多項(xiàng)式級(jí)別的，有效提高了數(shù)據(jù)起源追蹤的有效性和針對(duì)性。

［1］ Y. L. Simmhan， B. Plale， D. Gannon， A Survey of Data Provenance Techniques， Technical Report TR-618，Com -puter［J］ Science Department， Indiana University， 2005

［2］ Freire， Juliana， David Koop， and Luc Moreau， eds. Provenance and Annotation of Data and Processes： Second International Provenance and Annotation Workshop［C］，IPAW 2008， Salt Lake City， UT， USA， June 17-18， 2008. Vol. 5272. Springer， 2008.

［3］ 高明， 金澈清， 王曉玲， 等. 數(shù)據(jù)世系管理技術(shù)研究綜述［J］. 計(jì)算機(jī)學(xué)報(bào)， 2010， 33（3）： 373-389.

［4］ Glavic Boris， Dittrich Klaus. Data provenance： A categorization of existing approaches// Proceedings of the 6th MMC Workshop of BTW 2007［J］. Aachen， Germany，2007：227-241.

［5］ Luc Moreau，Natalia Kwasnikowska， Jan Van den Bussche，The Foundations of the Open Provenance Model［M］，Technical report， University of Southampton， April 2009

［6］ Moreau L， Clifford B， Freire J， et al. The open provenance model core specification （v1. 1）［J］. Future Generation Computer Systems， 2011， 27（6）： 743-756.

［7］ Xu Guoyan， Wang Zhijian，Yang Li. Tracking Framework of Data Provenance Based on Semantic Annotation .2012 International Conference on Computer Science and Service System， CSSS 2012， 406-409［J］.

Research on Data Dependency Analysis Based on OPM

Dong Yuchao1， Zhang Wensheng2
（1. Computer and Information College， HoHai University， Nanjing 211100， China；2. East China Yixing Pumped Storage Power Co. Ltd.， Yixing 214205， China）

How to analyze semantic information of data provenance is one of the key issues in the field of data provenance tracking. In this paper， according to the OPM， a data dependency analysis method is put forward based on introducing the concept and operation of data provenance dependency. Data dependencies are analyzed using refinement operation and synthetic operation in the proposed method， and in detail refinement algorithm and synthetic algorithm are given. Experiment shows that the method proposed has the perfect level of semantics， the algorithm complexity of polynomial， and reduced storage cost. The proposed method can satisfy different users query demand for different levels of abstraction data provenance information. The effectiveness of data provenance tracking is well improved.

Data Dependency； Data Provenance； Refinement Operation； Synthetic Operation； OPM

TP311

A

1007-757X（2016）06-0003-05

2016.02.10）

國(guó)家科技支撐計(jì)劃項(xiàng)目（編號(hào)：2013BAB06B04）、中國(guó)華能集團(tuán)公司總部科技項(xiàng)目（編號(hào)：HNKJ13-H17-04）、江蘇水利科技項(xiàng)目（No.2013025）資助.

董宇超（1989-），男，山西省朔州市，河海大學(xué)，計(jì)算機(jī)與信息學(xué)院，碩士，研究方向：大數(shù)據(jù)管理、Web服務(wù)、數(shù)據(jù)挖掘，南京，211100張文生（1969-），男，華東宜興出水蓄能有限公司，學(xué)士，研究方向：電力系統(tǒng)信息通信，宜興，214205