{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:22:12Z","timestamp":1759134132910,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS0845647IIS-0740129IIS-0915438IIS 1039376IIS 0629846"],"award-info":[{"award-number":["IIS0845647IIS-0740129IIS-0915438IIS 1039376IIS 0629846"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n            Workflow views abstract groups of tasks in a workflow into high level composite tasks, in order to reuse subworkflows and facilitate provenance analysis. However, unless a view is carefully designed, it may not preserve the dataflow between tasks in the workflow, that is, it may not be\n            <jats:italic>sound<\/jats:italic>\n            . Unsound views can be misleading and cause incorrect provenance analysis.\n          <\/jats:p>\n          <jats:p>This article studies the problem of efficiently identifying and correcting unsound workflow views with minimal changes, and constructing minimal sound and elucidative workflow views with a set of user-specified relevant tasks. In particular, two related problems are investigated. First, given a workflow view, we wish to split each unsound composite task into the minimal number of tasks, such that the resulting view is sound. Second, given a workflow and a set of user specified relevant tasks, we generate a sound view, such that each composite task contains at most one relevant task, and the total number of tasks is minimized. We prove that both problems are NP-hard by reduction from independent set. We then propose two local optimality conditions (weak and strong) for each problem, and design polynomial time algorithms for both problems to meet these conditions. Experiments show that our proposed algorithms are reasonably effective and efficient. The proposed techniques are useful for view analysis\/construction for not only workflows, but general networks as well.<\/jats:p>","DOI":"10.1145\/1929934.1929940","type":"journal-article","created":{"date-parts":[[2011,3,17]],"date-time":"2011-03-17T12:40:16Z","timestamp":1300365616000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Generating sound workflow views for correct provenance analysis"],"prefix":"10.1145","volume":"36","author":[{"given":"Ziyang","family":"Liu","sequence":"first","affiliation":[{"name":"Arizona State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Susan B.","family":"Davidson","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Chen","sequence":"additional","affiliation":[{"name":"Arizona State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292555"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/998688.1007097"},{"key":"e_1_2_1_3_1","first-page":"51","article-title":"Workflow soundness verification based on structure theory of Petri nets","volume":"5","author":"Barkaoui K.","year":"2007","unstructured":"Barkaoui , K. , Ayed , R. B. , and Shai , Z. 2007 . Workflow soundness verification based on structure theory of Petri nets . Int. J. Comput. Inform. Sci. 5 , 1, 51 -- 56 I. Barkaoui, K., Ayed, R. B., and Shai, Z. 2007. Workflow soundness verification based on structure theory of Petri nets. Int. J. Comput. Inform. Sci. 5, 1, 51--6I.","journal-title":"Int. J. Comput. Inform. Sci."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497516"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514931"},{"volume-title":"Proceedings of the 5th International Conference on Business Process Management. 88--95","author":"Bobrik R.","key":"e_1_2_1_6_1","unstructured":"Bobrik , R. , Reichert , M. , and Bauer , T . 2007. View-based process visualization . In Proceedings of the 5th International Conference on Business Process Management. 88--95 . Bobrik, R., Reichert, M., and Bauer, T. 2007. View-based process visualization. In Proceedings of the 5th International Conference on Business Process Management. 88--95."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.v20:5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376715"},{"key":"e_1_2_1_9_1","first-page":"22","article-title":"Program slicing and data provenance.IEEE Data","volume":"30","author":"Cheney J.","year":"2007","unstructured":"Cheney , J. 2007 . Program slicing and data provenance.IEEE Data Eng. Bull. 30 , 4, 22 -- 28 . Cheney, J. 2007. Program slicing and data provenance.IEEE Data Eng. Bull. 30, 4, 22--28.","journal-title":"Eng. Bull."},{"volume-title":"Proceedings of the International Symposium on Database Programming Languages. 138--152","author":"Cheney J.","key":"e_1_2_1_10_1","unstructured":"Cheney , J. , Ahmed , A. , and Acar , U. A . 2007. Provenance as dependency analysis . In Proceedings of the International Symposium on Database Programming Languages. 138--152 . Cheney, J., Ahmed, A., and Acar, U. A. 2007. Provenance as dependency analysis. In Proceedings of the International Symposium on Database Programming Languages. 138--152."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ITEM.0000031580.57966.d4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11799511_24"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2008.73"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376772"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2007.07.003"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376716"},{"volume-title":"Proceedings of the International Conference on Business Process Management. 235--253","author":"Kindler E.","key":"e_1_2_1_17_1","unstructured":"Kindler , E. , Martens , A. , and Reisig , W . 2000. Inter-operability of workflow applications: Local criteria for global soundness . In Proceedings of the International Conference on Business Process Management. 235--253 . Kindler, E., Martens, A., and Reisig, W. 2000. Inter-operability of workflow applications: Local criteria for global soundness. In Proceedings of the International Conference on Business Process Management. 235--253."},{"volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications. 260--267","author":"Liu D.-R.","key":"e_1_2_1_18_1","unstructured":"Liu , D.-R. and Shen , M . 2001. Modeling workflows with a process-view approach . In Proceedings of the International Conference on Database Systems for Advanced Applications. 260--267 . Liu, D.-R. and Shen, M. 2001. Modeling workflows with a process-view approach. In Proceedings of the International Conference on Database Systems for Advanced Applications. 260--267."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(02)00028-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920958"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth361"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341811.1341823"},{"volume-title":"Proceedings of the Conference on Advanced Information Systems Engineering. 195--209","author":"Sadiq W.","key":"e_1_2_1_23_1","unstructured":"Sadiq , W. and Orlowska , M. E . 1999. Applying graph reduction techniques for identifying structural conflicts in process models . In Proceedings of the Conference on Advanced Information Systems Engineering. 195--209 . Sadiq, W. and Orlowska, M. E. 1999. Applying graph reduction techniques for identifying structural conflicts in process models. In Proceedings of the Conference on Advanced Information Systems Engineering. 195--209."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2005.573"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454193"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401964"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2008.06.005"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.89"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841760_13"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICWS.2006.5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth021"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559903"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687606"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/647778.734905"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74974-5_4"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the International Conference on Software Engineering. 439--449","author":"Weiser M.","year":"1981","unstructured":"Weiser . M. 1981 . Program slicing . In Proceedings of the International Conference on Software Engineering. 439--449 . Weiser. M. 1981. Program slicing. In Proceedings of the International Conference on Software Engineering. 439--449."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929934.1929940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1929934.1929940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:32Z","timestamp":1750278392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929934.1929940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1929934.1929940"],"URL":"https:\/\/doi.org\/10.1145\/1929934.1929940","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2010-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}