云计算环境下一种面向科学工作流不确定数据源的视图构造方法

doi:10.3969/j.issn.1000-0801.2013.03.017

摘要/Abstract

摘要：

科学工作流的数据源视图根据数据源中任务间的数据流关系，将它们划分为多个复合模块，并在此基础上进行数据抽象与封装，从而可有效降低科研工作者的数据分析工作量并节省数据查询时间。然而在云计算环境中开发与应用科学工作流系统时，由于受数据采集的准确度和服务器的可靠性影响，将会导致工作流数据源图的不确定性，因此需要提供有效的机制在不确定数据源图中构建合理性视图。针对此方面，首先给出了不确定数据源图及其合理性视图的定义，在此基础上提出了一种检测不合理视图的方法；还进一步分析了数据源图中任务节点与其一阶前序节点之间存在的多种数据流关系及复合任务的局部期望支持度，给出了合理视图的构造方法。设计了相应的多项式时间算法，并分析算法的时间复杂度。最后，对相关方法给出示例，并进行实验分析，验证了其可行性与有效性。

关键词: 云计算, 科学工作流, 数据源, 视图

Abstract:

The view of data provenance in scientific workf1ow provides an approach of data abstraction and encapsu1ation by partitioning tasks in the data provenance graph（DPG）into a set of composite modu1es due to the data f1ow re1ations among them, so as to efficient1y decrease the work1oad consumed by researchers making ana1ysis on the data provenance and the time needed in doing data querying.Neverthe1ess, deve1oping and app1ying the scientific workf1ow systems in c1oud computing environments suffers the prob1em of uncertainty brought by the inaccuracy of data co11ection and unre1iabi1ity of data servers distributed in the internet.Concentrating on this scenario, the definitions of uncertain DPG and its sound view were presented first1y, and then a method for detecting the unsound view of DPG was proposed.A1so, a method for constructing sound and high-support view was presented, which is based on the data f1ow re1ations among the tasks and their first-order preceding tasks in the graph, and the 1oca1 expected support of the composite modu1es.A po1ynomia1-time a1gorithm was designed, and its maxima1 time comp1exity was a1so ana1yzed.Additiona11y, an examp1e and conduct comprehensive experiments were given to show the feasibi1ity and effectiveness of the method.

Key words: c1oud computing, scientific workf1ow, data provenance, view

胡海洋,刘占晨,胡华. 云计算环境下一种面向科学工作流不确定数据源的视图构造方法[J]. 电信科学, 2013, 29(3): 90-100.

Haiyang Hu,Zhanchen Liu,Hua Hu. Constructing View of Uncertain Data Provenance for Scientific Workflow in Cloud Computing[J]. Telecommunications Science, 2013, 29(3): 90-100.

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 24

1	IBM Blue Cloud Solution.
2	Sun Cloud Architecture Introduction White Paper.
3	Barroso LA , Dean J , Holzle U . Web search for a planet：the Google cluster architecture. IEEE Micro, 2003， 23(2): 22～28
4	International Telegraph Union（ITU）.
5	Organization for the Advancement of Structured Information Standards（OASIS）.
6	冯登国，张敏，张妍等. 云计算安全研究. 软件学报， 2011， 22(1): 71～83
7	郑湃，崔立真，王海洋等. 云计算环境下面向数据密集型应用的数据布局策略与方法. 计算机学报， 2010， 33(8): 1472～1480
8	Oinn T , Addis M , Ferris J , et al. Taverna:a tool for the composition and enactment of bioinformatics workf1ows. Bioinformatics, 2004, 20>(17): 3045～3054.
9	A1tintas I , Berkley C , Jaeger E , et al. Kepler：an extensible system for design and execution of scientific workflows. Proceedings of the 16th International Conference on Scientific and Statistical Database Management, Santorini Island，Greece 2004: 423～424.
10	Biton O , Boulakia S C , Davidson S B , et al. Querying and managing provenance through user views in scientific workflows. Proceedings of the 24th International Conference on Data Engineering, Cancun, Mexico 2008: 1072～1081.
11	Biton O , Davidson S B , Khanna S , et al. Optimizing user views for workflows. Proceedings of the 12th International Conference on Database Theory, St, Petersburg, Russia 2009: 310～323.
12	Cohen S , Boulakia S C , Davidson S B . Towards a model of provenance and user views in scientific workf1ows, Proceedings of Lecture Notes in Computer Science Data Integration in the Life Sciences, Hinxton, UK 2006: 264～279.
13	Shao Q , Chen Y , Tao S , et al. Easy Ticket:a ticket routing recommendation engine for enterprise problem resolution. Proceedings of the VLDB Endowment, Auckland 2008: 1436～1439.
14	Shao Q , Chen Y , Tao S , et al. Efficient ticket routing by resolution sequence mining. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas 2008: 605～613.
15	Shao Q , Sun P , Chen Y . Efficiently discovering critical workflows in scientific exp.lorations. Future Generation Computer System, 2009,25(5): 577～585.
16	Sun P , Liu Z Y , Susan D , et al. Detecting and resolving unsound workflow views for correct provenance analysis. Proceedings of the ACM SIGMOD International Conference on Management of Data, Rhode Island 2009: 549～562.
17	邹兆年，李建中，高宏等. 从不确定图中挖掘频繁子图模式. 软件学报， 2009， 20(11)： 2965～2976.
18	Chui C K , Kao B , Hung E . Mining frequent itemsets from uncertain data. Proceedings of the 11th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, Nanjing 2007: 47～58.
19	Zhou S G , Yu Z C , Jiang H L . Concepts, issues, and advances of searching in graph structured data. Communication, 2007,3(8): 59～65.
20	Shasha D , Wang T L , Guigno R . Algorithmic and applications of tee and graph searching. Proceedings of the 21st ACM SIGMOD-SIGART Symposium on Principles of Database Systems, Madison 2002: 39～52.
21	Yan X , Yu P S , Han J . Graph indexing:a frequent structure based approach. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris 2001: 335～346.
22	Hintsanen P , Toivonen H . Finding reliab1e subgraphs from large probabilistic graphs. Data Mining and Knowledge Discovery, 2008,17(1): 3～23.
23	Cheng J , Yu J , Lin X . Fast computing reachability labelings for large graphs with high compression rate. Proceedings of 11th International Conference on Extending Database Technology, Nantes 2008: 193～204.
24	Jin R , Hong H , Wang HX , et al. Computinglabel-constraint reachability in graph databases. Proceedings of the ACM SIGMOD International Conference on Management of Data, Indianapolis，Indiana 2010: 123～134.

[1]	韩雪. 基于电力大数据的电力骨干通信网络毁伤韧性评估方法[J]. 电信科学, 2023, 39(5): 136-143.
[2]	邬江兴. 论网络技术体制发展范式的变革——网络之网络[J]. 电信科学, 2022, 38(6): 3-12.
[3]	邢文娟, 雷波, 赵倩颖. 算力基础设施发展现状与趋势展望[J]. 电信科学, 2022, 38(6): 51-61.
[4]	邓平科, 张同须, 施南翔, 张童, 邵天竺, 郑韶雯. 星算网络——空天地一体化算力融合网络新发展[J]. 电信科学, 2022, 38(6): 71-81.
[5]	马焜, 徐玲玉, 沈晓萍, 龚志城, 蓝建平, 陈双喜, 钱钧. 云计算中基于Shapley值改进遗传算法的虚拟机调度模型[J]. 电信科学, 2022, 38(12): 1-10.
[6]	刘志勇, 何忠江, 阮宜龙, 单俊峰, 张超. 大数据安全特征与运营实践[J]. 电信科学, 2021, 37(5): 160-169.
[7]	许剑,靳莉. 一种可量化的云计算平台安全评估模型[J]. 电信科学, 2020, 36(7): 163-167.
[8]	罗斯宁,王化龙,李弘宇,彭蔚. 基于改进蚁群算法的云计算用户任务调度算法[J]. 电信科学, 2020, 36(2): 95-100.
[9]	雷波, 刘增义, 王旭亮, 杨明川, 陈运清. 基于云、网、边融合的边缘计算新方案：算力网络[J]. 电信科学, 2019, 35(9): 44-51.
[10]	高永梅,程冠杰. 基于边缘计算的数据密集型服务部署[J]. 电信科学, 2019, 35(7): 87-99.
[11]	鲁泽霖,李强治. 电子商务平台的演化逻辑和运营机理[J]. 电信科学, 2019, 35(7): 152-158.
[12]	黄志兰,樊勇兵,樊宁,陈楠,吴林泽,林宝洪. 云资源池集成虚拟防火墙方案及关键技术[J]. 电信科学, 2019, 35(5): 140-148.
[13]	朱友康,乐光学,杨晓慧,刘建生. 边缘计算迁移研究综述[J]. 电信科学, 2019, 35(4): 74-94.
[14]	吴国威,樊宁,汪来富,王帅,沈军,金华敏. 云环境下基于属性加密体制算法加速方案[J]. 电信科学, 2019, 35(11): 101-107.
[15]	张云勇. 5G将全面使能工业互联网[J]. 电信科学, 2019, 35(1): 1-8.