董宇超，张文生

基于OPM的数据依赖关系分析研究

董宇超，张文生

如何对数据起源语义信息进行分析是数据起源追踪领域的关键问题之一。基于OPM，在建立的数据起源依赖关系概念及其操作的基础上，提出了一种数据依赖关系分析方法，利用细化操作和合成操作分析数据依赖关系，并具体给出数据依赖细化算法和合成算法。实验表明，提出的方法，具有完备的语义和多项式级别的算法复杂度，存储耗费也有所降低，可以满足不同用户对于不同抽象层次数据起源信息查询的需求，很好地提高了数据起源追踪的有效性和针对性。

数据依赖关系；数据起源；细化操作；合成操作；数据起源开放模型

0　引言

近几年，随着大数据管理的迫切需要，数据起源追踪［1］［2］［3］［4］成为崭新的国内外研究热点。数据起源又称为数据血统、数据世系、数据溯源、数据谱系、数据血缘和数据来源等，是对数据处理的整个历史的信息，包括数据产生和随着时间推移而演变的整个过程。在抽象级别上，起源是一种依赖关系，描述数据产品是如何得到的，相关的数据和过程的作用是什么，角色是什么。

目前，数据起源依赖关系分析的主流模型之一为OPM（The Open Provenance Model）［5］［6］，OPM是数据起源开放模型，支持各种起源技术的互操作。OPM 基于有向无环图，表示数据产品和计算中关联的过程，以及他们之间的因果依赖关系。

通过OPM能够得到数据和数据的因果依赖关系，但是不同的用户想要看到的因果依赖关系是不同的，有的想看全局的概貌，有的想看局部的细节。为此，本文基于OPM，对数据起源中数据依赖关系进行深入分析，引入细化和合成操作，提出一种数据起源中数据依赖的分析方法，完成数据依赖关系在全局和不同层次的局部之间灵活转换，形成不同的依赖关系视图，满足不同用户对于不同抽象层次数据起源信息查询的需求。具体贡献包括：

（1）为了有效支撑数据依赖关系分析，针对数据依赖存在的不同情况，定义数据依赖、部分数据依赖、完全数据依赖等。在此基础上，定义数据依赖的细化和合成操作，并进一步根据部分数据依赖、完全数据依赖分别深入定义，完成通过数据依赖关系分析生成用户视图的基础体系；

（2）为了实现数据依赖从概貌到细节的转化，针对部分数据依赖、完全数据依赖不同情况，提出数据依赖的细化规则，并给出具体细化算法，形成数据依赖关系从抽象到具体的分析；

（3）为了实现数据依赖从细节到概貌的转化，针对部分数据依赖、完全数据依赖不同情况，提出数据依赖的合成规则，并给出具体合成算法，形成数据依赖关系从具体到抽象的分析；

（4）从语义完备性、存储耗费、提出算法复杂度三个方面，与直接使用OPM进行数据依赖分析进行对比，说明提出的分析方法具有优势。

1　数据依赖关系定义及操作

数据起源依赖关系在本质上是数据起源的语义信息，本文在前期研究中提出的数据起源追踪架构下［7］，基于OPM关于因果关系定义的基础上，给出数据起源依赖关系和数据依赖关系定义，然后，具体定义了数据依赖关系的细化和合成操作。

1.1数据依赖关系

定义1 数据起源依赖关系 定义为一个6元组

DP_Dependency=（Data_Set，Process_Set，

Data_Data_Dependency，Data_Process_Dependency，

Process_Data_Dependency，

Process _Process_Dependency），其中

（1）Data_Set是数据的集合；

（2）Process_Set是过程的集合；

（3）Data_Data_Dependency：Data_Set → Data_Set，

是数据到数据的映射关系，称为数据依赖关系；

（4）Data_Process_Dependency：Data_Set → Process _Set，是数据到过程的映射关系，称为过程对数据依赖关系，即过程依赖于数据，数据是过程的输入；

（5）Process_Data_Dependency：Process_Set → Data _Set，是过程到数据的映射关系，称为数据对过程依赖关系，即数据依赖于过程，数据是过程的输出。过程对数据依赖关系和数据对过程依赖关系统称为控制依赖关系；

（6）Process_Process_Dependency：Process_Set →Pr -ocess_Set，是过程到过程的映射关系，称为过程依赖关系。

对应于OPM，WasGeneratedBy和Used表示的是控制依赖关系，WasDerivedFrom表示的是数据依赖关系，WasInformedBy表示的是过程依赖关系。

定义2 数据依赖对于一个给定的源数据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的一个数据依赖，即Source_Data由Sink_Data演化而来。

定义3完全数据依赖 对于给定的数据Source_Data和Sink_Data，Source_Data数据依赖于Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，如果O1，…，Om→Ii， i ≤ n，则I1，…，In完全依赖于O1，…，Om，即Source_Data完全数据依赖于Sink_Data，记作Source_DataSink_Data。

定义4部分数据依赖 对于给定的数据Source_Data和Sink_Data，Source_Data数据依赖于Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，如果Oi→Ij，i≤m，j≤n，则Source_Data的一项数据依赖于Sink_Data的一项，称Source_Data部分数据依赖于Sink_Data，记作Source_DataSink_Data。

1.2数据依赖细化与合成操作

定义5 数据起源依赖关系细化操作 DP_Dep1、DP_Dep2是两个数据起源依赖关系，定义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

定义6 数据起源依赖关系合成操作 DP_Dep1、DP_Dep2是两个数据起源依赖关系图，定义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 数据依赖的细化 对于给定的数据Source_Data和Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，如果 Source_Data和Sink_Data满足完全依赖关系dep1，Source_Data和Sink_Data满足部分依赖关系dep2，那么dep2是dep1的细化，记作dep1﹤dep2。

定义8 数据依赖的合成 给定数据依赖关系图DGraph=（Node_Set，Edge_Set， Role_Set），通过完全数据依赖的合成和部分数据依赖合成得到的新的数据依赖关系New_DG，称New_DG是DGraph的一个数据依赖的合成，记作DGraph﹥New_DG。

定义9完全数据依赖的合成 给定数据依赖图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｝，是边起点集合， Nf=｛Nf1，Nf2，…， Nfj｝，是边终点集合，则图（N，E）是完全二分有向图。如果R都是完全数据依赖，那么Ns中结点合并成一个结点s， Nf中结点合并成一个结点f，集合E中的边合并成一条边e=＜s，f＞，记生成的图Dgraph－Child_DP + （｛s，f｝，e，role）为New_DG，则New_DG是DGraph的一个完全数据依赖的合成，其中role为完全数据依赖。

定义10部分数据依赖的合成 给定数据依赖图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｝，是边起点集合， Nf=｛Nf1，Nf2，…， Nfj｝，是边终点集合，则图（N，E）是完全二分有向图。如果R都是部分数据依赖，那么Ns中结点合并成一个结点s， Nf中结点合并成一个结点f，集合E中的边合并成一条边e=＜s，f＞，记生成的图Dgraph－Child_DP + （｛s，f｝，e， role）为New_DG，则New_DG是DGraph的一个部分数据依赖的合成，其中role为部分数据依赖。

定义11参数 在一个过程Process的执行过程中，如果输入Parameter是过程执行的参数，不产生直接对应的输出数据；或者是过程执行的数据，产生对应的输出数据，但输出数据只是中间产品。则Parameter不再笼统的称作输入数据，而是称作参数。

2　数据依赖关系分析

则不进行任何替换。

算法具体执行过程如表1所示：

表1　数据依赖的细化规则及算法

针对不同用户的不同层次数据依赖关系的需求，提出了一种数据依赖关系分析方法，基于细化和合成操作，设计了一系列数据依赖细化与合成规则，并且具体给出了细化与合成算法。

2.1数据依赖的细化规则及算法

首先定义数据依赖的细化规则，如下所示。

规则1 输入数据和参数规则 对于给定的数据Source_Data和Sink_Data，Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，Source_DataSink_Data，如果有一个Oi是参数，i≤m，则将Source_DataSink_Data替换为在参数Oi的条件下，｛I1，…，In｝｛O1，…，Oi-1，Oi+1，…，Om｝。如果Oi都是输入数据，i≤m，则不进行任何处理。

规则2 完全数据依赖规则 对于给定的数据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，则不进行任何替换。

规则3 部分数据依赖规则 对于给定的数据Source_Data和Sink_Data， Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝， Source_DataSink_Data，

1. 初始化数据变量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；

//细化阶段

5. do ｛

6. do ｛

7. if （Oi是parameter） 根据规则1处理；

8. i=i + 1；

9. ｝While （i ≤ m）

10. switch （role类型） ｛

11. case 完全数据依赖：根据规则2处理；break；

12. case 部分数据依赖：根据规则3处理；break；

13. ｝

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

15. 将数据依赖图中下一个依赖关系的数据存放在变 量Source_Data和Sink_Data中；

16. 初始化变量role；

17. 初始化变量i=1；

18.｝While （Dep不为空）

return 得到细化数据依赖图。

2.2数据依赖的合成规则及算法

首先定义数据依赖的合成规则，如下所示。

规则4完全数据依赖合成规则 数据集合｛I1，…，In｝和｛O1，…，Om｝，满足完全依赖，i≤m， j≤n。如果记Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝， 则原依赖关系替换成Source_DataSink_Data。

规则5部分数据依赖合成规则 对于数据集合｛I1，…，In｝和｛O1，…，Om｝，部分依赖满足，i≤m， j≤n。如果记Source_Data=｛I1，…，In｝，Sink_Data=｛O1，…，Om｝，则原依赖关系替换成Source_DataSink_Data。

算法具体执行过程如表2所示：

表2　数据依赖的合成规则及算法

Node_Set=Data_Set；Edge_Set=Data_Data_Dependency；Role_Set=｛完全数据依赖，部分数据依赖｝；Data_Data_Dependency Data_Set×Data_Set。输出：细化的数据依赖图//初始化阶段1. 初始化数据依赖图Data_Data_Dependency_ Graph，包括Data_Set， Data_Data_Dependency和Role_Set ；2. 初始化数据变量Source_Data；3. 初始化Dep=Data_Data_Dependency；4. 初始化变量role；//合成阶段5. do｛6. 取数据依赖图中与Source_Data有完全依赖关系的结点，根据规则4处理；7. 数据依赖图中与Source_Data有部分依赖关系的结点，根据规则5处理；8. 取下一个结点存入Source_Data；9.｝While （数据依赖图没有遍历完）10. 得到合成数据依赖图。

3　性能分析

本文从实现层上对OPM进行细化，利用细化或合成操作，分析数据依赖关系，满足不同用户对于数据起源追踪不同视图的需求。本文提出的数据依赖关系分析方法具体有如下3个方面的优势：

（1）语义性

本文基于依赖关系分析的需求，进行数据起源语义信息的标注，标注的结果即是数据起源的控制依赖关系，从控制依赖关系着手，根据规则，得到数据依赖。所以，其数据依赖语义性是完备的。例如图1所示：

图1　控制依赖图

控制依赖图，得到数据依赖图。如图2所示：

图2　数据依赖图

（2）存储耗费

本文针对数据起源依赖关系分析，进行数据起源信息的标注（标注的结果即为控制依赖关系），与OPM中数据起源信息的标注相比，需要的存储空间相对减少了。例如图1所示的控制依赖图，为了起源依赖关系分析，其存储耗费为S=Data_Store + Process_Store + Data_Process_Store

=8+6+14=28，而OPM存储耗费为S=Data_Store + Process_Store + Data_Process_Store + Data_Data_Store + Process_ Process_Store=8+6+14+8+6=42，则本文方法与OPM方法的存储耗费百分比为28/42=2/3，具体如图3所示：

图3　存储空间耗费比较

（3）算法复杂度

本文方法依据OPM中因果依赖关系，利用细化或合成操作进行分析，获得数据起源追踪中数据依赖的不同视图，满足用户不同层次起源信息的需求。方法中不论是细化算法还是合成算法，其算法复杂度都是多项式级别的，具体为：

细化依算法采用每两个结点进行比较的思路，假设有n个结点的数据依赖图Dep_Graph，则对两个结点的依赖关系进行细化。当Dep_Graph每两个结点都有边的情况下，是需要计算最多的时候。而在这种情况下，算法的复杂情况是，所以算法的复杂度是O（n2）。

合成算法采用广度优先搜索来搜索到每一个结点的相邻结点，进行是否是二分图判断，根据判断的三种情况分别进行完全依赖合成、部分依赖合成和不合成处理。算法的复杂度由广度优先搜索、二分图判断和合成处理三部分组成。如果在一个图中得到最优的数据依赖的合成，即得到最大的二分图，那么复杂度是NP-hard的。如果采用只是对一个结点搜索相邻结点，然后进行判断处理的方式，则算法的复杂度是多项式级别的。

4　总结

本文基于OPM，从依赖关系的角度，定义了数据起源的语义信息，提出了一种数据起源追踪中数据依赖关系分析的方法，利用细化和合成操作进行具体分析，给出了具体的规则和算法。最后，通过分析说明，本文提出的方法具有完备的语义，耗费的存储空间较少，算法复杂度是多项式级别的，有效提高了数据起源追踪的有效性和针对性。

［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］ 高明， 金澈清， 王晓玲， 等. 数据世系管理技术研究综述［J］. 计算机学报， 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）

国家科技支撑计划项目（编号：2013BAB06B04）、中国华能集团公司总部科技项目（编号：HNKJ13-H17-04）、江苏水利科技项目（No.2013025）资助.

董宇超（1989-），男，山西省朔州市，河海大学，计算机与信息学院，硕士，研究方向：大数据管理、Web服务、数据挖掘，南京，211100张文生（1969-），男，华东宜兴出水蓄能有限公司，学士，研究方向：电力系统信息通信，宜兴，214205