集成对象代理数据库的科学工作流服务框架中的数据跟踪
王黎维1, 彭智勇2,3, 黄泽谦2 , 罗敏2
（武汉大学国际软件学院1，软件工程国家重点实验室2，武汉大学计算机学院3， 武汉 430072）
摘 要 本文提出了一个集成数据库的科学工作流服务框架，它采用对象代理模型描述一系列科学任务的执行过程，使得工作流管理操作以类似于传统数据库管理操作的方式来完成。同时，基于对象代理数据库中的双向指针机制，本文提出了一种新的数据跟踪方法，该方法能提供比注释或反向查询更高的性能，不仅节省了大量的存储空间，而且减少了额外的计算代价，一种部分物化中间数据的模式也被提出，用于提高数据跟踪的高效性，实验显示它具有较好的系统性能。
关键词 科学工作流；web服务；对象代理模型；数据跟踪
引言
目前，生物、医学、生态等科学领域已经面临信息爆炸，使得这些领域的科学家每天不得不使用各种专业程序处理来自实验室信息管理系统控制的科学实验，大规模计算为中心的模拟或远程传感器实时观测的科学数据，这对自动管理科学实验提出了迫切的需求。为了支持科学家进行高效的数据管理和实验分析，将工作流技术应用于科学领域的科学工作流（Scientific Workflow，SWF）如今已成为在网络基础设施上进行大规模科学计算和协同研究的有效方法。目前在合作环境中进行跨组织的科学实验已经越来越重要。由于该环境中数据和程序资源的分布和异构，使得广泛用于工业界的Web服务技术引入到科学工作流中，用于支持来自不同平台的计算资源的整合，如 [1，2]等。它将程序封装到服务中，并通过服务调用而不是程序调用组成工作流，因此能够跨越技术和组织的边界对流程进行建模。
与以任务为中心的商业工作流相比，科学工作流虽然共享了商业工作流的一些特性，但其主要是以数据为中心[3]，常常涉及大规模科学计算，具有描述科学数据的元数据或者注释。因此，科学工作流实际上是数据管理和流程管理的结合[4]。探索数据库技术用于科学工作流管理已成为当前的研究热点。通常，工作流管理系统(WFMS)使用数据库管理系统(DBMS)来存储任务描述以及工作流数据，并在DBMS之上实现各个工作流功能模块。然而目前一些研究证明[5，6]，大多数WFMS的功能可由DBMS提供，许多成熟的数据库技术，如计划、查询、数据跟踪以及并发控制等均可用于工作流管理系统中。采取DBMS的方式实现科学工作流管理，可以减少实现开销，增加优化的可能性，使其以一种类似于传统数据库操作的方式进行工作流管理。因此，采用以数据库系统为核心的科学工作流管理体系架构，变得非常有意义。
科学工作流最重要的功能是作为识别实验数据的一种方式，称其为数据跟踪（Data Provenance）[7，8]，它用于提供数据的派生历史，解释数据的由来，这对于实验分析，错误诊断以及核实实验结果的有效性很有帮助。另外，当产生实验数据的实验步骤发生改变时，能通过数据的派生历史跟踪实验进程，确定需要重做哪些步骤以便更新实验结果。因此，数据跟踪主要包含两个重要信息：用于产生实验数据的数据源，以及所经历的实验步骤。
目前，数据跟踪的重要性已经被多个科学工作流项目所认可，如GridDB[6]，Chimera[9]，myGRID[10]，CMCS[11]。注释和反向是目前两种主要的数据跟踪方法。注释将一个数据的派生历史搜集起来作为元数据，与数据一起存放在数据库中，用于解释数据的来源。反向方法主要应用逆向查询或者逆向函数，由结果数据溯源到其源数据。但两者都有不足之处，注释不能为细粒度的实验数据提供良好的存储规模，因为记录完整的派生历史可能超过数据本身所需要的存储空间。反向方法从存储的角度来看似乎更好，因为逆向函数或逆向查询能标识某一类数据的派生信息，但每次需要查询数据源时，它需要产生一个逆向函数或逆向查询去计算派生信息，在数据量大的情况下，执行效率较低。
本文，我们首先提出了一个集成对象代理数据库的科学工作流服务框架，并在此框架下着重研究基于对象代理模型的数据跟踪方法，该方法能借助实验数据间的双向指针实现数据跟踪，能提供比注释或反向方法更高的性能，不仅节省了大量的存储空间，而且减少了额外的计算代价。
本文的组织如下：第2节介绍了一个集成对象代理数据库的科学工作流服务框架。第3节提出了基于对象代理模型的数据跟踪方法。第4节给出了实验结果和分析。第5节分析并比较了一些相关工作。最后总结全文并提出下一步需要开展的工作。
集成对象代理数据库的科学工作流服务框架
集成对象代理[12]数据库TOTEM的科学工作流服务框架如图1所示，它将数据管理和工作流管理有效的结合，以对象代理数据库来建模科学工作流，并采用类似SQL语言的方式来执行，管理和监控科学工作流。
图1 集成对象代理数据库的科学工作流服务框架
该框架使用对象代理数据库TOTEM作为科学工作流的运行环境，提供科学工作流所必需的工作流设计和执行功能，从而取代商业工作流引擎的核心位置。工作流设计主要用于定义工作流模式，模式定义通过对象代理数据库中的类和代理类定义工作流中不同科学任务的输入和输出，通过任务输入输出间的对象代理关系实现工作流的自动执行。工作流执行是系统的核心模块，它主要采取数据驱动的方式，使得科学任务调用相应的科学程序对提供的输入数据进行计算，将执行转化为对数据库的插入和更新操作从而实现工作流的自动执行。
其中，科学程序使用web服务描述语言（如，WSDL）将其封装，我们称其为科学服务程序。它仅仅提供程序的接口而不必关心程序的具体实现，隐藏了它们的异构性，使它们能被任何类型的客户端应用程序存取。从图1中我们可以看出，服务提供者使用公共的UDDI注册器注册服务描述，客户端查询UDDI得到服务描述细节，找到所感兴趣的服务，并构造和执行工作流。一旦工作流中的某一任务被触发，它通过UDDI接受服务的输入参数，并向SOAP服务器发送合适的SOAP消息，接受SOAP消息的SOAP服务器触发服务的实际实现，结果被返回到SOAP服务器，再返回给客户端。一个任务的输出可能被直接传递或修改，并作为下一个任务的输入。
工作流建模
科学工作流由科学数据和操作它们的科学任务组成。科学任务具有输入数据与输出数据，我们建模输入、输出数据作为对象代理数据库TOTEM中的类和代理类，其中，科学任务的输入数据是其直接前驱科学任务的输出数据。工作流流程初始科学任务的输入数据用类来定义，构成工作流流程的所有科学任务的输出数据定义为其输入数据的代理类，代理类的类型根据对应工作流模式的不同而有所不同。被科学任务调用的科学服务程序定义为输入数据对象属性上的读方法。
数据声明
定义1工作流流程初始科学任务的输入数据被定义成类C = <O, A>。
O是C的数据对象集。o∈O是C的一个数据对象。
A是C的属性集合。(Ta:a)∈A分别代表一个属性的类型和属性名。数据对象o的属性a的值表示为。对每个属性Ta:a，都有两个基本方法。
read(o, a)↑ ，write(o, a, v) := v。
这里，，↑分别代表激活、结果返回。
定义2 工作流流程除初始科学任务外的其他科学任务的输出数据基于其输入数据来定义，前者称为后者的代理类，后者称为前者的源类。源类中的数据对象与其代理类中的数据对象通过双向指针链接。代理数据对象拥有自己的标识符，并通过切换操作完全或部分共享源数据对象的属性值，同时还可以增加属性。令Cs = <Os, As>是源类，其代理类Cd可以定义为Cd = <Od, Ad∪Ad+>。
代理数据对象Od = {odi | odi → osi | …×osi ×… | {osi}, sp(osi) | jp(…×osi ×…) | gp({osi}) = = true }，其中odi → osi | …×osi ×… |{osi}表示odi是osi，…×osi ×…，或{osi}的代理数据对象，sp，jp和gp分别表示选择，组合和分组谓词。
根据对象代理模型[12]，代理数据对象具有四种类型，分别是Select、Join、Group和Union，用于支持特化，聚集，分组和组合。
Ad∪Ad+是Cd的属性集。
(1) (Tad:ad)∈Ad是从(Tas:as)∈As继承而来的属性。对代理数据对象od的属性值ad的计算通过切换操作最终作用到源数据对象的属性as上。由于更新继承的属性值不符合科学工作流的要求，所以属性ad的写方法不存在，ad读方法的切换操作定义如下：
read(od, ad)↑ fTas→Tad (read(os, as))
(2) (Tad+ : ad+)∈Ad+是增加的属性，其基本方法定义如下：
read(od, ad+)↑ +
write(od, ad+, vd+)+ := vd+
根据该定义，每次查询代理数据对象继承的属性值仍然需要通过访问源数据对象的切换操作来计算。由于科学计算的结果数据可能由运行时间较长的科学程序产生，所以最好物化继承的属性值以避免每次查询时重新计算它们。物化的继承属性的读方法定义被修改如下：
read(od, ad)↑.
即继承的属性值能直接从代理数据对象中读取。
源数据对象上的更新将触发更新迁移过程对代理数据对象进行更新，也就是，如果增加，删除或修改源数据对象，相应的代理数据对象也会被增加，删除或修改。由于源数据对象与其代理数据对象之间存在各种依赖关系和语义约束，其一致性可通过更新迁移进行维护。
流程声明
工作流流程的执行可能需要连接多个科学任务，任何复杂的工作流流程能被简化成在给定数据上按某种顺序执行的科学任务序列。本框架的特点是将工作流流程看成一系列数据的相互连接，将工作流任务间的相互关系转换为任务关联数据间的关系，同时采用对象代理数据库根据不同的工作流模式来建立数据间的关系，利用更新迁移机制触发工作流的自动执行，因此能够支持[13]提出的几种常见的工作流模式，包括：顺序模式，并行分支模式，同步模式，单选模式，简单合并模式，多路合并模式，多路选择模式等。
如图2(a)所示，任务A的输出AOutput定义为任务B的输入，任务B的输出定义为类AOutput的Select型代理类BOutput。任务B对应的科学服务程序作为AOutput中数据对象属性上的读方法，一旦A完成对输入数据的计算，往AOutput中插入结果数据对象时，会触发B的执行，并在BOutput中派生对应代理数据对象。
图2 对象代理模型建模工作流
如图2(b)所示，任务B和C的输出BOutput和COutput分别定义为任务A的输出类AOutput的Select型代理类。对于并行分支模式，一旦A完成对数据的计算，往AOutput中插入一个或多个结果数据对象时，会同时触发B和C的执行，并在BOutput和COutput中派生对应的代理数据对象。
如图2(c)所示，任务A，B的输出分别定义为类AOutput，BOutput；任务C的输出定义为AOutput和BOutput的Join型代理类COutput。对于同步模式，只有当A和B都完成时，在AOutput和BOutput中分别产生数据对象，才会触发C的执行，并在COutput中派生一个代理数据对象。同步模式中的任务同步要求转换为Join型代理类的更新迁移。
如图2(d)所示，任务B和C的输出分别定义为任务A的输出AOutput的Select型代理类BOutput和COutput。对于单选模式，只有一个分支会被执行。当A往AOutput插入数据对象时，数据库会根据BOutput和COutput的代理规则，触发相应分支的执行，并派生相应的代理数据对象到BOutput和COutput中。
如图2(e)所示，任务A与B的输出分别定义为类AOutput和BOutput；任务C的输出COutput定义为AOutput或BOutput的Select型代理类。对于简单合并模式，只有一个分支A或B被触发执行，一旦任务执行完成，往AOutput或BOutput插入数据，触发C的执行，并会在COutput中派生相应的代理数据对象。
如图2(f)所示，任务A与B的输出分别定义为类AOutput和BOutput；任务C的输出COutput定义为AOutput和BOutput的Union型代理类。对于多路合并模式，A和B中任何一个分支执行完，分别往AOutput或BOutput插入数据对象时，都会触发C的执行，并在COutput中派生相应的代理数据对象。
如图2(g)所示，任务B，C和D的输出分别定义为任务A的输出AOutput的Select型代理类BOutput，COutput和DOutput。对于多选模式，至少B，C和D中有一个分支会被执行，当A往AOutput插入数据对象时，数据库会根据BOutput，COutput和DOutput的代理规则，触发任务执行，并派生相应的代理数据对象到BOutput，COutput和DOutput中，从而触发相应分支的执行。
采用对象代理数据库建模工作流，使得与工作流模式相关的控制逻辑由数据库来实现。由于除初始任务外，所有任务的输出都定义为该任务所有直接前驱任务的输出类的代理类，所以一旦前驱任务往其输出数据类中插入数据，更新迁移将根据各个输出类的代理规则，调用后继任务进行计算，派生对应的代理对象到后继任务的输出类中。
. Atlas高能物理工作流的建模与执行
我们引用Atlas高能物理工作流[5]解释构造和执行工作流的过程。如图3(a)所示，Atlas工作流包括三个科学任务，分别执行事件发生器(gen)程序，快速模拟探测器程序(atlfast)和慢速模拟探测器程序(atlsim)。gen接收一种粒子的质量，产生一个event文件<pmas>.evts，该文件描述了粒子的衰变。之后event文件被分别输入到程序atlfast 和atlsim，模拟两种探测器对粒子衰变事件的反应，并且产生包含数值fImas 和sImas 的文件，两个结果数值实际上是粒子衰变而产生的子粒子的质量之和。最后，比较这两个结果。
图3 Atlas工作流建模
图3(b)和3(c)分别描述了Atlas工作流模型及对象代理数据库中对应的数据库模式。对象代理数据库语言[14]建立Atlas工作流如下，其中gen，atlfast和atlsim被封装成三个科学服务程序，分别定义为event、fImas 和sImas的读方法。
第一个科学任务的输入和输出类定义如下：
CREATE CLASS gC (pmas int);
CREATE SELECTDEPUTYCLASS evts AS (SELECT gen(pmas) AS (event int) FROM gC);
类gC的pmas属性表示输入的粒子质量，由类gC派生的代理类evts 存储由科学服务程序gen 产生的event文件，其中event属性表示文件标识符。
执行科学服务程序atlfast和atlsim的科学任务的输出类分别定义为类evts的Select型代理类fC及sC：
CREATE SELECTDEPUTYCLASS fC
AS (SELECT atlfast(event) AS (fImas int) FROM evts);
CREATE SELECTDEPUTYCLASS sC
AS (SELECT atlsim(event) AS (sImas int) FROM evts);
fC及sC分别存放科学服务程序altfast 和atlsim 产生的结果数据 fImas及sImas，它们表示粒子衰变得到的子粒子的质量总和。
类fC和sC的Join型代理类compare比较atlfast和atlsim所产生的结果fImas和sImas。
CREATE JOINDEPUTYCLASS compare AS
(SELECT , FROM fC, sC WHERE fC→ = sC→);
因此，Atlas工作流的建立通过不断的派生代理类组成。向类gC中插入一个数据对象将启动Atlas工作流的自动执行，如：
INSERT INTO gC VALUES (100);
一旦一个pmas值为100的数据对象被插入到gC，根据evts的代理规则，自动触发第一个科学任务，也即科学服务程序gen执行，并在evts类中产生它的代理数据对象evts1，同样，evts1触发科学服务程序atlfast和atlsim的自动执行，并将执行完后的结果分别添加到类fC和sC中，最终导致产生对象compare1。另外，如果gC1的pmas值被修改，所有数据对象包括evt1、fC1、sC1以及compare1将自动的重新计算。
集成对象代理数据库TOTEM的科学工作流服务框架意味着与数据库的紧密结合。工作流的声明和定义使用了类似SQL 的对象代理数据库语言，触发、查询和执行使用SQL来完成。因此，WFMS的管理操作以类似于传统数据管理操作的方式来完成。
基于对象代理模型的数据跟踪
本节在该框架的基础上提出了一种基于对象代理模型的数据跟踪方法。区别于一般的注释和反向等数据跟踪方法，利用对象代理数据库内部对象间的双向指针可以实现高效的数据跟踪。
数据跟踪
该框架使用TOTEM数据库的类、代理类为科学任务的输入数据和输出数据建模，其中，每一个科学任务实现由输入数据到输出数据的映射，输入数据和输出数据通过输入数据类和输出数据类中的数据对象或代理数据对象来表达。每一个数据对象或代理数据对象在数据库中具有唯一的对象标识OID。所以该框架可以基于对象之间的OID双向指针来实现数据跟踪。
对象OID间的双向指针通过TOTEM自身维系的双向指针系统表tt_bipointer来实现，记录了所有对象与代理对象之间的联系。科学任务的输入等于该任务所有直接前驱任务的输出数据类，科学任务的输出定义为该任务的输入数据类的代理类，也就是说，任务的输出数据对象是其直接前驱任务的输出数据对象的代理对象，通过系统维护的数据对象和代理数据对象间的双向指针，可以查询到一个任务的输出数据对象是由其前驱任务的哪些数据对象所生成的。如图4中的tt_bipointer结构所示，SourceClass_oid表示源类的OID，SourceObj_oid表示源对象的OID，DeputyClass_oid表示代理类的OID，DeputyObj_oid表示代理对象的OID，可以通过DeputyObj_oid直接查找到SourceObj_oid。
由于科学任务的输出是其直接前驱科学任务的输出数据类的代理类，因此，一旦前驱任务的输出数据类中产生结果数据，对象代理模型的更新迁移将会自动触发后继任务的执行，并派生代理数据对象到其后继任务的输出数据类中。同时，在系统表tt_bipointer中增加OID映射关系。对于Select和Union代理类中的代理对象，它与源对象在tt_bipointer系统表中具有一个一对一的映射关系；对于Join代理类中的代理对象，由于一个代理对象是由多个源对象产生的，因此，它与源对象具有多条映射关系，其中每一条映射关系表示它和其中一个源对象的对应。
另外，数据跟踪不仅需要找到产生数据的数据源，还需要提供产生这些数据所经历的实验过程[15]。TOTEM数据库将科学服务程序作为对象属性的读方法存放在tt_switching系统表中。如图4中的tt_switching结构所示，Class_oid表示类的OID，Attr表示对象属性，Proc表示科学服务程序，借助tt_bipointer系统表中的DeputyClass_oid域，可以在tt_switching系统表中查找到DeputyObj_oid经过了哪些科学服务程序的计算。
图4 tt_bipointer与tt_switching
图5是Atlas工作流的tt_bipointer与tt_switching内部结构，详细记录了类gC中的数据对象与evts中的代理数据对象及evts中的代理数据对象与fC中代理数据对象的映射关系，其中Class_oid中的1、2和3分别表示类gC、evts和fC。从图中可以看到，类gC中的OID为1的数据对象经过科学服务程序gen的计算，得到evts类中OID为101的数据对象。同时，evts类中OID为101的数据对象经过科学服务程序atlfast和atlsim后在fC类中产生OID为201的代理数据对象。
图5 Atlas的tt_bipointer与tt_switching内部结构
跟踪查询
基于对象代理模型的数据跟踪方法可以根据系统表tt_bipointer与tt_switching查找到数据对象的来源和所经历的科学程序，即找出一个数据对象完整的派生信息，实现数据跟踪。
定义3 opdep表示代理操作，其中opdep分成以下三种：
Select
Cd = select(proc(Cs))是应用操作select到源类Cs中而形成的类，并对选择出的数据对象应用科学程序proc。假定一个对象od∈Cd，根据操作select，我们定义od在类Cs中的派生信息是P(Cs) (od) = select-1 (Cs) (od) = {<os, Cs, proc>}，其中os为od在Cs中的源数据对象。
Union
Cd = union(proc1(C1s),…, procm(Cms))是应用操作union到源类C1s,…,Cms中而形成的类。假定一个数据对象od∈Cd，根据操作union，我们定义od在类C1s,…,Cms中的派生信息是P(C1s,…,Cms)(od) = union-1 (C1s,…,Cms)(od) = {<ois, Cis, proci > |1≦i≦m}，其中，ois为od在Cis中的源数据对象。
Join
Cd = join(proc1(C1s),…, procm(Cms))是应用操作join到源类C1s,…,Cms中而形成的类。假定一个数据对象od∈Cd，根据操作join，我们定义od在类C1s,…,Cms中的派生信息是P(C1s,…,Cms)(od) = join-1 (C1s,…,Cms)(od) = {<o1s, C1s, proc1>,…,<oms, Cms, procm>}，其中o1s,…, oms分别为od在C1s,…,Cms中的源数据对象。
如果Join操作仅仅用于比较实验数据的结果，那么Proc可以允许为空。
定义4 C1b,…, Cnb是基本科学类，Cd是C1b,…, Cnb经过多次opdep操作生成的代理类。考虑数据对象od∈Cd。Cd = opdep(proc1(Deputy1),…, prock(Deput yk))，其中Deputyj是基本科学类C1b,…, Cnb经派生得到的中间代理类，k≧j≧1。假设od’∈Deputyj，od’应用操作opdep派生数据对象od（定义3），并且ob∈Cib，n≧i≧1, 派生od’到Deputyj中（本定义递归），那么ob派生od到Cd中。因此，od在C1b,…,Cnb中的派生信息是P(C1b,…,Cnb)(od) = {C1b*,…,Cnb*}。其中C1b*,…,Cnb*分别是{<o1b, C1b, proc1>},…,{<onb, Cnb, procn>}的子集。
根据定义4，考虑数据对象od∈Cd，PQod,Cd对od在类C1b,…, Cnb中的跟踪查询表示为PQ(od, Cd, (C1b,…, Cnb))，它主要用于查找od在类C1b,…, Cnb中的源数据对象以及经历的科学服务程序。其算法表示如下：
Begin
Cd = opdep (proc1(Deputy1) ,…, prock(Deputyk));
PQ(od, Cd, (Deputy1,…,Deputyk))={Deputy1*,…, Deputyk*}; //其中Deputy1*,…,Deputyk*分别是{<oDeputy1d, Deputy1, proc1>},…,{<oDeputykd, Deputyk, prock>}的子集;
For i =1 to n do
Cib* = Null;
For j=1 to k do
If Deputyj*≠Null
Then {C1b*,…,Cnb*} = {C1b*,…,Cnb*}∪PQ (oDeputyjd, Deputyj, (C1b,…, Cnb)); //oDeputyjd表示od在Deputyj中的源对象;
Return (C1b*,…, Cnb*);
End
PQod,Cd计算od在C1b,…, Cnb中的派生信息，程序首先计算(Deputy1,…,Deputyk)经过一层代理操作得到的派生信息{Deputy1*,…,Deputyk*}，然后不断递归计算每一个Deputyj中oDeputyjd的派生信息。
如图5，如果我们要计算fC类中对象OID为201的数据对象的派生信息，容易发现这个数据对象是evts类中为101的数据对象经过科学服务程序atlfast的计算而得到的代理数据对象，因此，它在evts类中的派生信息是P(evts)(od) = {<101, evts, atlfast >}。同样，evts类中OID为101的数据对象是gC中OID为1的数据对象经过科学服务程序gen的计算而生成的，所以OID为1的数据对象在gC类中的派生信息为P(gC)(od) = {<1, gC, gen>}。由此看出，数据对象的派生信息能通过双向指针直接构造，节约了记录派生信息的存储空间，也不必使用逆向查询或逆向函数进行数据跟踪，提高了查询效率。
数据物化
在跟踪查询过程中，通常需要查询中间数据的属性值，如追踪fC类中OID为201的数据对象在gC中的派生信息时，需要查找evts类中OID为101的数据对象属性值。由于该数据对象是gC类中OID为1的数据对象的代理对象，为了减少额外的存储空间，该数据对象没有存储实际的数值，而是通过切换操作与它的源数据对象共享，因此查询它的属性值时，需要通过查找它的源数据对象的属性值再计算得到。由于该数据对象的属性值是源数据对象的属性值经过复杂的科学程序计算得到，因此，会导致很低的追踪性能。
物化数据可以提高追踪的性能。如果物化evts类中OID为101的数据对象属性值，那么一旦用户提出查询这个数据对象的属性值，该属性值可以立即被找到而不必切换到类gC中OID为1的数据对象，再计算出它的值，因此物化中间数据能帮助直接查询中间结果而不需要重新计算它们，从而增强了追踪性能。然而，如果物化整个中间数据，那么可能造成很大的存储开销和维持代价，同时许多中间数据也许与用户感兴趣的最终数据毫不相关，因此没有必要完全物化它们。
为了减少存贮和维持代价，我们提出一种部分物化中间数据的模式PM，PM只物化具有代理数据对象的中间数据。例如，我们仅仅物化evts类中需要被输入到科学服务程序atlfast 和atlsim的对象，与完全物化evts类中数据对象相比，大大地节省了存储空间。
相对于完全物化或不物化中间数据而言，PM模式也能减少对象更新维持的代价。例如，更新gC中的一个数据对象ogc时，PM首先需要计算evts类中它的代理数据对象oevtsd的值并判断是否引起fC类中oevtsd的代理数据对象ofcd的更新，如果不会导致更新，根据PM的说明，oevtsd一定未被物化，因此系统不需要消耗额外时间将被更新的oevtsd数据对象写入磁盘。此时，如果采用完全物化这种方式，那么系统需要消耗额外时间将被更新的oevtsd对象写入磁盘。这种情况能保证与不物化这种方式相同的维持代价。
如果会导致更新，那么oevtsd一定被物化，因此可根据被更新的oevtsd的值直接更新数据对象ofcd的属性值，这种情况能保证与完全物化这种方式相同的维持代价。此时如果采用不物化这种方式，即oevtsd未被物化，那么就需要根据基本数据对象ogc的属性值重新计算ofcd的属性值，该过程经历了gen和atlfast两个科学服务程序的计算，虽然此时PM需要消耗额外时间将被更新的oevtsd数据对象写入磁盘，但这个时间显然远远少于重新计算数据的时间。因此PM也能有效的减少对象更新维持的代价。
另外，由于最终数据的跟踪查询只与被物化的中间数据相关，因此这种模式并不影响追踪的性能。
性能测试
这个部分测试了PM模式的跟踪性能和维持代价，并与未物化中间数据模式NM进行了比较。
实验模型
实验模型按照图3(b)的结构设计。简单起见，我们假设只有两层代理类，其中第一层代理类evts存储程序gen的结果，并且完全地继承gC中的数据对象；第二层代理类fC存储科学服务程序atlfast的结果，并且继承evts中大约40%的数据对象。为了模拟真实的环境，我们假设gen和atlfast分别运行3 秒和2 秒。模式NM和PM分别描述不物化和部份物化类evts。
我们首先比较随着基本类大小的增加其两种模式在平均追踪查询、对象更新维持代价和存储开销上的性能，基本类的大小从100,000变化到500,000个对象。其次分析基本类数据对象为500,000时，随着查询率的增加，500,000个对象分别所需的追踪查询时间，更新维持时间，以及系统负载。更新维持代价和存储开销分别描述更新维持evts类和fC类的总时间以及它们总共占用的存储空间。追踪查询或更新维持时，我们假设每次操作只追踪或更新一个数据对象，并计算半小时内，成功完成的操作数量。实验环境采用赛扬 CPU，256M内存，Linux操作系统。
实验结果
图6(a)、图6(b)和图6(c)分别显示PM和NM模式的平均对象追踪时间，维持代价和存储开销。图6(d)、图6(e)和图6(f)分别显示在基本类具有500,000个对象时，随查询率的增加，PM和NM模式所需的追踪查询时间，更新维持时间，以及系统负载。
图6 性能测试
图6(a)显示了PM模式比NM模式取得更高的追踪性能，并随基本类大小的增加，NM模式消耗的追踪时间变长。图6(b)显示了随着基本类大小的增加，PM模式和NM模式的更新维持时间都增加，但PM模式有更好的维持性能。图6(c)显示PM模式的存储开销比NM模式大。
图6(d)和图6(e)显示随查询率的增加，追踪查询时间和更新维持时间成比例的增加和减少。图6(f) 显示了PM模式具有更好的系统性能。而NM模式随查询率的增大，所消耗的时间呈上升趋势。
根据上述分析，由此得出在运行时间较长的科学实验中，PM模式显示出比NM模式更好的性能，尤其PM模式在基本类有大量数据对象而最终的数据对象仅有一小部分时显得特别有效。当然，由于PM模式的存储开销比NM模式大，如果存在大量的最终数据对象，并且这些数据对象本身是由运行时间非常短的程序产生，那么NM模式可能也会显示出较好的性能。
相关工作
科学工作流技术研究在近些年得到很好的发展，特别是将web服务技术应用到科学工作流中已引起了广泛关注[1，2，15]，它们通常采用基于XML的语言如WSFL，XLANG，BPEL4WS等表达web服务组合之间的控制流。然而，这些语言主要针对商业流程建模，对于将web服务应用到以数据库为核心的科学工作流系统中的研究几乎没有被探讨。据我们所知，第一个倡导WFMSs和DBMSs相结合的系统是ZOO[5]。ZOO是一个桌面实验管理环境，它使用面向对象语言Moose建模工作流之间的控制流，将其表示为任务与输入数据、输出数据间的关系。通过在关系上安排相应的规则来触发任务的执行。与ZOO类似，GridDB[6]同样基于数据库模式来构建工作流，不同的是，它关注的是网格环境，并使用了更加简单的关系模型来构造工作流。程序的输入和输出被建模为关系表，用户使用功能数据建模语言FDM定义程序以及程序的输入与输出间的关系。通过触发器的使用，在输入表中插入元组能触发程序的执行。文献[16]提出了一种紧密集成WFMS和DBMS的工作流建模语言。初始的输入数据和程序被描述为活动关系表，派生的数据和程序被描述为活动视图，工作流通过不断的定义活动视图而组成，程序的触发和执行通过SQL语句来完成。与ZOO和GridDB一样，集成对象代理数据库的科学工作流服务框架也是基于数据库管理系统为核心来实现科学工作流管理。它使用对象代理模型来建模工作流，表达工作流的控制逻辑，不仅能对同一任务的输入和输出进行建模，还对任务间的数据关系进行建模。最重要的是，利用对象代理数据库内部对象间的双向指针可以实现高效的数据跟踪。
作为一个关键组件，数据跟踪方法已经被很多科学工作流和数据库领域研究了。主要包括注释和反向两种方法。反向方法主要是应用逆向查询或者逆向函数，由结果数据溯源到其源数据。而注释的方法则是将一个数据的派生历史搜集起来作为元数据，对源数据和处理过程进行描述。当前，大多工作流管理系统更依赖于注释[9，10，11]，Chimera[9]分析虚拟数据目录并提出了表示操作序列的抽象有向无环图。一些数据跟踪系统mygird[10], CMCS[11]也使用RDF和OWL提供语义信息以便于实现科学工作流在合作环境中的交互，然而，CMCS对语义信息的支持比较有限，所以真正在数据跟踪信息中提供语义信息的只有myGrid，它将本体概念注释到数据跟踪日志以提供丰富的语义。然而，注释描述数据对象的派生历史，因此，既使数据是粗粒度的，注释信息占用的存储空间也可能比数据本身大。而在基于对象代理模型的数据跟踪方法中，数据对象的派生历史能通过双向指针直接构造，因此节约了大量的存储空间。
反向方法从存储角度看，特别对大量细粒度的数据似乎是更佳的选择，因为逆向函数或查询标识一整类数据的派生信息。许多数据库领域[7，17，18，19]都采取这个方法为用户提供面向数据的数据跟踪服务。Buneman[7]通过反向方法确定了数据跟踪的两种形式，why表示数据产生的原因，而where提供产生数据的源数据。Trio[17]使用反向方法自动地通过视图查询或用户定义的函数确定元组的源数据。任何使用数据库查询和函数构造工作流的系统均可使用这样的技术。然而，并非所有的函数都有逆函数[20]，虽然文献[18]提出一个框架以便根据弱逆向函数计算近似的源，但该文并没有提供产生弱逆向函数的机制。基于对象代理模型的数据跟踪方法与反向方法具有一些相似性，例如，也要求“反向”查询以便找到派生该数据对象的源数据对象，但它不必使用逆向查询或逆向函数计算数据的派生信息。反向方法虽然不会造成存储的开销，但每次一个数据的派生历史被需求时，它需要产生一个逆向函数或逆向查询去计算派生信息，在数据量大的情况下，执行效率较低。文献[21]也表明如果有大量的派生信息需求时，这种计算信息源的方法并不是好的选择。而基于对象代理模型的数据跟踪方法仅仅通过源数据对象与代理数据对象之间的双向指针便可查找到代理数据对象的派生信息，而不需要额外的计算代价。该方法也能有效的避免一些逆向函数不存在或计算不精确的问题。使用反向方法计算的派生信息通常需要存取信息源，而这些信息源可能很遥远或在一段时间内不可取。反向方法通常需要存储额外的辅助信息以便在数据跟踪时减少或避免整个源存取。如通过在数据仓库中存储额外的辅助信息，[19]能减少或完全避免存取信息源。而在基于对象代理模型的数据跟踪方法中，代理数据对象能物化一些来自源数据对象的属性值，从而有效的解决了以上问题。同时，从数据跟踪信息语义丰富程度的角度来考虑，显然反向方法所能给出的派生信息语义是非常有限的，通常只表示信息源极其经历的实验过程。基于对象代理模型的数据跟踪方法能随应用需要在代理类中增加自己的属性，可以更加丰富的表示数据对象的信息，弥补了反向方法表示数据不丰富的缺陷。
无论是哪种数据跟踪方法，一旦源发生改变，那么后续的数据需要使用一种类似于“维持表达式”的方式修改视图。在我们的方法中，如果数据源改变，工作流随后的阶段可能自动地被触发，并自动更新派生的科学对象。然而，无论注释或“反向”方法都不支持这个功能。
结论与展望
本文在分析了目前数据跟踪方法的基础上，研究并提出了一个基于对象代理模型的数据跟踪方法。该方法基于集成对象代理数据库的科学工作流服务框架对科学工作流建模，借助对象之间的OID双向指针来实现数据跟踪，使得数据跟踪能提供比注释或反向查询更高的性能。因为科学工作流的实验方法和实验数据通常需要被共享和重用，如何增强科学工作流的流程重用和数据重用，是我们下一步的工作。
参 考 文 献
[1] Cavalcanti M C, Targino R, Baião F, Rössle S C, Bisch P M, Pires P F, Campos M L M, Mattoso M. Managing structural genomic workflows using web services. Data & Knowledge Engineering, 2005, 53(1): 45~74.
[2] Jaeger E, Altintas I, Zhang J, Ludäscher B, Pennington D, Michener W. A scientific workflow approach to distributed geospatial data processing using web services //Proceeding of the 17th International Conference on Scientific and Statistical Database Management, Santa Barbara, CA, 2005. USA: IEEE Computer Society, 2005: 87~90.
[3] Ludäscher B, Altintas I, Berkley C, Higgins D, Jaeger E, Jones M, Lee E A, Tao J, Zhao Y. Scientific workflow management and the Kepler system. Concurrency and Computation: Practice & Experience, 2005, 18(10): 1039~1065.
[4] Dan M. Dynamic Workflows and Advanced Data Management for Problem Solving Environments. Blacksburg, Virginia: Virginia Tech, 2002.
[5] Ailamaki A, Ioannidisz Y E., Livny M. Scientific workflow management by database management //Proceeding of the 10th International Conference on Scientific and Statistical Database Management, Los Alamitos, CA, 1998. USA: IEEE Computer Society, 1998: 190~199.
[6] Liu David T, Franklin M J. The design of griddb: a data-centric overlay for the scientific grid //Proceeding of the 30th International Conference on Very Large Data Bases, Toronto, Canada, San, 2004. San Mateo, CA, USA: Morgan Kaufmann, 2004: 600~611.
[7] Buneman P, Khanna S, Tan W C. Why and where: a characterization of data provenance //Proceeding of the 8th International Conference on Database Theory, London, UK, 2001. London, UK: Springer-Verlag, 2001: 316~330.
[8] Greenwood M, Goble C, Stevens R, Zhao J, Addis M, Marvin D, Moreau L, Oinn T. Provenance of e-science experiments - experience from bioinformatics //Proceedings of the UK OST e-Science second All Hands Meeting, 2003.
[9] Foster I, Vockler J, Wilde M, Zhao Y. Chimera: a virtual data system for representing, querying, and automating data derivation //Proceeding of the 14th International Conference on Scientific and Statistical Database Management, Edinburgh, Scotland, UK, 2002. USA: IEEE Computer Society, 2005: 37~46.
[10] Zhao J, Goble C A, Stevens R, Bechhofer S. Semantically linking and browsing provenance logs for E-science //Proceeding of the first International IFIP Conference on Semantics of a Networked World, Paris, France, 2004. London, UK: Springer-Verlag, 2004: 158~176.
[11] Pancerella C, Hewson J, Koegler W, Leahy D, et al. Metadata in the collaboratory for multi-scale chemical science //Proceeding of the International Conference on Dublin Core and Metadata Applications, Conference, 2003.
[12] Peng Z Y, Kambayashi Y. Deputy mechanisms for object-oriented databases // Proceeding of the 11th International Conference on Data Engineering, Los Alamitos, CA, 1995. USA: IEEE Computer Society, 1995: 333~340.
[13] Russell N, Hofstede A, Edmond D. Workflow Data Patterns. Brisbane: Queensland University of Technology, QUT Technical report: FIT-TR-2004-01, 2004.
[14] Zhai B X, Shi Y, Peng Z Y. Object deputy database language //Proceedings of the 4th International Conference on Creating, Connecting and Collaborating through Computing, Los Alamitos, CA, 2006. USA: IEEE Computer Society, 2006: 88~95.
[15] Zhang J T, Pennington D, Michener W. Using web services and scientific workflow for species distribution prediction modeling //Proceeding of the 6th International Conference on Advances on Web-Age Information Management, Hangzhou, China, 2005. London, UK: Springer-Verlag, 2005: 610~617.
[16] Shankar S, Kini A, DeWitt D J, Naughton J. Integrating databases and workflow systems. SIGMOD Record, 2005, 34(3): 5~11.
[17] Widom J. Trio: a system for integrated management of data, accuracy, and lineage //Proceeding of the 2nd Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, 2005. San Mateo, CA, USA: Morgan Kaufmann, 2005: 262~276.
[18] Woodruff A, Stonebraker M. Supporting fine-grained data lineage in a database visualization environment //Proceeding of the 13th International Conference on Data Engineering, Birmingham UK, 1997. USA: IEEE Computer Society, 1997: 91~102
[19] Cui Y, Widom J. Practical lineage tracing in data warehouses //Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, 2000. USA: IEEE Computer Society, 2000: 367~378.
[20] Simmhan Y L, Plale B, Gannon D. A survey of data provenance in e-science. SIGMOD Record, 2005, 34(3): 31~36.
[21] Bhagwat D, Chiticariu L, Tan W C, Vijayvargiya G. An annotation management system for relational databases //Proceedings of the 30th International Conference on Very large data bases, Toronto, Canada, 2004. San Mateo, CA, USA: Morgan Kanfmann, 2004: 900~911.
Data Provenance in a Scientific Workflow Service Framework Integrated with Object Deputy Database
WANG Liwei1, PENG Zhiyong2,3, HUANG Zeqian3, LUO Min3
(International School of Software1, Wuhan University, Wuhan 430072;
Computer School2, Wuhan University, Wuhan 430072;
State Key Laboratory of Software Engineering3, Wuhan University, Wuhan 430072;)
Abstract This paper proposed a DB-integrated scientific workflow service framework which adopts object deputy model to describe the execution of a series of scientific tasks, thus allows workflow management operations to be performed in a way analogous to traditional database management operations. Furthermore, based on bi-directional pointer mechanism in object deputy database, this paper introduced a new data provenance method. This approach is much more efficient than annotation or inversion method, which not only save a lot of storage space, but also reduce the cost of the extra computing. A partial materialize data schema is also presented to improve the efficiency of data tracking, and the experiment result shows that it can provide a preferable system performance.
Key words scientific workflow; web service; object deputy model; data provenance
Background
This work is supported by the National Natural Science Foundation of China under grant No 60573095, the New Century Excellent Talents of Education Ministry under grant No NCET-04-0675, the National High Technology Research and Development Program of China under grant No 2006AA12Z210, the Doctoral Foundation of Education Ministry under grant , the Humanities and Social Science research base projects of the Education Ministry in 2005 under grant , the Science and Technology research projects of Education Ministry under grant , and the National Base Research and Development Program of China under grant No 2007CB310806.
The most important function of scientific workflows is the way of recognizing data products, which is called data provenance. Data provenance provides derivation histories and explains the sources for data products. The solutions of determining data provenance in the literature usually involve annotations that comprise of the derivation history of a data product and inversion that generates a “reverse” query to find the origins supplied to derive a data product. Annotations may not scale well for fine-grained data as the complete annotations for the data may outsize the storage space required for the data itself. Inversion seems to be more optimal from a storage perspective since an inverse function or query identifies the provenance for an entire class of data. However, it requires a reverse query or function to be generated and executed to compute provenance every time the provenance of a data product is required.
In order to make up for the shortcomings of the above methods, this paper proposed a new data provenance method based on the bi-directional pointer mechanism of object deputy model. Not only derivation history of a data product can be directly constructed by bi-directional pointers between the data product and its sources, saving a mass of storage space, but also we can directly find source data of derived data by bi-directional pointers without computing provenance using inverse queries or inverse functions, increasing the querying efficiency.
作者简历
王黎维，女，1980年生，博士，讲师，主要研究方向为工作流管理和事务处理。
WANG Liwei, born in 1980, , Lecturer. Her research interests mainly include workflow management and transaction processing.
彭智勇，男，1963年生，教授，博士生导师，主要研究方向为数据模型，先进数据库管理，多媒体数据库，安全数据库，地理信息系统，web信息集成，工作流管理。
PENG Zhiyong, born in 1963, , professor, . His main research interests include data model, advanced database management, multimedia databases, secure databases, geographic information system, web information integration, workflow management.
黄泽谦，男，1984年生，博士研究生，主要研究方向为工作流管理和事务处理。
HUANG Zeqian, born in 1984, . candidate. His research interests mainly include workflow management and transaction processing.
罗敏，男，1981年生，博士研究生，主要研究方向为工作流管理。
LUO Min, born in 1981, . candidate. His research interests mainly include workflow management and transaction processing.
该研究得到了国家自然科学基金项目（60573095）、教育部新世纪优秀人才计划项目(NCET-04-0675)、中国高科技研究发展计划（2006AA12Z210）、教育部博士点基金项目(20050486024)、教育部科学技术研究重点项目（107072）、国家重点基础研究发展计划资助（2007CB310806）资助
PAGE
PAGE 12
A
B
A
A
BOutput
COutput
(a)顺序模式
(b)并行分支模式
A
B
C
BOutput
(c)同步模式
(d)单选模式
A
B
(e)简单合并模式
C
COutput
AInput
A
B
C
AOutput
(f)多路合并模式
(g)多路选择模式
AInput
AOutput
BOutput
AInput
AOutput
Select
B
C
Select
Select
AOutput
BOutput
B
Join
COutput
C
Select
Select
AOutput
BOutput
Select
COutput
AOutput
BOutput
COutput
Union
A
BOutput
COutput
AInput
AOutput
B
C
Select
Select
D
DOutput
Select
tt_switching
Class_oid
Attr
Proc
tt_bipointer
SourceClass_oid
SourceObj_oid
DeputyClass_oid
DeputyObj-oid
(d)
(e)
(f)
(a)
(b)
(c)
SourceClass_oid
SourceObj_oid
DeputyClass_oid
1
1
2
…
…
…
DeputyObj_oid
101
…
1
100
2
200
2
101
3
…
…
…
201
…
2
200
3
300
tt_bipointer
Class_oid
Attr
Proc
1
pmas
null
2
event
gen
3
fImas
atlfast
tt_switching
…
…
…
…
…
…
…
<pmas>
<event>
<fImas>
<sImas>
gen
atlfast
atlsim
compare
gC
evts
fC
sC
compare
gen
atlsim
atlfast
Select
oid
event
101
evts1
…
…
200
evts101
oid
pmas
1
100
…
…
100
200
oid
fImas
201
101
…
…
300
198
oid
sImas
301
100
…
…
400
200
oid
fImas
401
101
…
…
500
198
sImas
100
…
200
gC
evts
fC
sC
gen
compare
atlfast
atlsim
(a)Atlas工作流
(b)Atlas工作流模型
(c)Atlas数据库模式
