{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:23:38Z","timestamp":1771025018323,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            This paper considers the problem of efficiently answering reachability queries over\n            <jats:italic>views<\/jats:italic>\n            of provenance graphs, derived from executions of workflows that may include recursion. Such views include composite modules and model fine-grained dependencies between module inputs and outputs. A novel\n            <jats:italic>view-adaptive<\/jats:italic>\n            dynamic labeling scheme is developed for efficient query evaluation, in which view specifications are labeled statically (i.e. as they are created) and data items are labeled dynamically as they are produced during a workflow execution. Although the combination of fine-grained dependencies and recursive workflows entail, in general, long (linear-size) data labels, we show that for a large natural class of workflows and views, labels are\n            <jats:italic>compact<\/jats:italic>\n            (logarithmic-size) and reachability queries can be evaluated in constant time. Experimental results demonstrate the benefit of this approach over the state-of-the-art technique when applied for labeling multiple views.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350240","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1208-1219","source":"Crossref","is-referenced-by-count":8,"title":["Labeling workflow views with fine-grained dependencies"],"prefix":"10.14778","volume":"5","author":[{"given":"Zhuowei","family":"Bao","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Susan B.","family":"Davidson","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"947","volume-title":"SODA","author":"Alstrup S.","year":"2002","unstructured":"S. Alstrup and T. Rauhe . Improved labeling scheme for ancestor queries . In SODA , pages 947 -- 953 , 2002 . S. Alstrup and T. Rauhe. Improved labeling scheme for ancestor queries. In SODA, pages 947--953, 2002."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/998688.1007097"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807244"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989375"},{"key":"e_1_2_1_7_1","first-page":"343","volume-title":"VLDB","author":"Beeri C.","year":"2006","unstructured":"C. Beeri , A. Eyal , S. Kamenkovich , and T. Milo . Querying business processes . In VLDB , pages 343 -- 354 , 2006 . C. Beeri, A. Eyal, S. Kamenkovich, and T. Milo. Querying business processes. In VLDB, pages 343--354, 2006."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497516"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543648"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938554"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796544"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007634"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376716"},{"key":"e_1_2_1_14_1","volume-title":"Taverna: a tool for building and running workflows of services. Nucleic Acids Research, 34(Web-Server-Issue):729--732","author":"Hull D.","year":"2006","unstructured":"D. Hull , K. Wolstencroft , R. Stevens , C. A. Goble , M. R. Pocock , P. Li , and T. Oinn . Taverna: a tool for building and running workflows of services. Nucleic Acids Research, 34(Web-Server-Issue):729--732 , 2006 . D. Hull, K. Wolstencroft, R. Stevens, C. A. Goble, M. R. Pocock, P. Li, and T. Oinn. Taverna: a tool for building and running workflows of services. Nucleic Acids Research, 34(Web-Server-Issue):729--732, 2006."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301380"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89965-5_31"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007686"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2008.06.010"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/28.1.5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559903"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989419"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559921"},{"issue":"1","key":"e_1_2_1_24_1","first-page":"276","article-title":"GRAIL: Scalable reachability index for large graphs","volume":"3","author":"Yildirim H.","year":"2010","unstructured":"H. Yildirim , V. Chaoji , and M. J. Zaki . GRAIL: Scalable reachability index for large graphs . PVLDB , 3 ( 1 ): 276 -- 284 , 2010 . H. Yildirim, V. Chaoji, and M. J. Zaki. GRAIL: Scalable reachability index for large graphs. PVLDB, 3(1):276--284, 2010.","journal-title":"PVLDB"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:26:22Z","timestamp":1672226782000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":23,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350240"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350240","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}