{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:56:10Z","timestamp":1759683370900},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>This paper studies, for the first time, the management of type information for an important class of semi-structured data: nested DAGs (Directed Acyclic Graphs) that describe execution traces of business processes (BPs for short). Specifically, we consider here type inference and type checking for queries over BP execution traces. The queries that we consider select portions of the traces that are of interest to the user; the types describe the possible shape of the execution traces in the input\/output of the query.<\/jats:p>\n          <jats:p>We formally define and characterize here three common classes of BP execution traces and their respective notions of type inference and type checking. We study the complexity of the two problems for query languages of varying expressive power and present efficient type inference\/checking algorithms whenever possible. Our analysis offers a nearly complete picture of which combinations of trace classes and query features lead to PTIME algorithms and which to NP-complete or undecidable problems.<\/jats:p>","DOI":"10.14778\/1453856.1453898","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"352-363","source":"Crossref","is-referenced-by-count":14,"title":["Type inference and type checking for queries on execution traces"],"prefix":"10.14778","volume":"1","author":[{"given":"Daniel","family":"Deutch","sequence":"first","affiliation":[{"name":"Tel Aviv University"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_2_1_2_1","volume-title":"Proc. of VLDB","author":"Beeri C.","year":"2006"},{"key":"e_1_2_1_3_1","volume-title":"Proc. of VLDB","author":"Beeri C.","year":"2007"},{"key":"e_1_2_1_4_1","volume-title":"Proc. of VLDB","author":"Benzaken V.","year":"2006"},{"key":"e_1_2_1_5_1","unstructured":"Business Process Execution Language for Web Services. http:\/\/www.ibm.com\/developerworks\/library\/ws-bpel\/.  Business Process Execution Language for Web Services. http:\/\/www.ibm.com\/developerworks\/library\/ws-bpel\/."},{"key":"e_1_2_1_6_1","unstructured":"BPMI. Business process management initiative. http:\/\/www.service-architecture.com\/web-services\/articles\/business_process_query_language_bpql.html.  BPMI. Business process management initiative. http:\/\/www.service-architecture.com\/web-services\/articles\/business_process_query_language_bpql.html."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2006.1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265551"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783534.1783552"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066219"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142364"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265540"},{"key":"e_1_2_1_14_1","first-page":"1","author":"Ginsburg S.","year":"1967","journal-title":"Bracketed context-free languages. J. Computer and System Sciences"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071614"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/647559.730195"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_18"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/128869"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321411"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303998"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335171"},{"key":"e_1_2_1_22_1","volume-title":"MIT Press","author":"Mitchell J. C.","year":"1996"},{"key":"e_1_2_1_23_1","unstructured":"Oracle BPEL Process Manager 2.0 Quick Start Tutorial. http:\/\/www.oracle.com\/technology\/products\/ias\/bpel\/index.html.  Oracle BPEL Process Manager 2.0 Quick Start Tutorial. http:\/\/www.oracle.com\/technology\/products\/ias\/bpel\/index.html."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287445"},{"key":"e_1_2_1_26_1","volume-title":"PWS Publishing Company","author":"Sipser M.","year":"1997"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:10:44Z","timestamp":1672225844000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453898"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453898","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}