{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:29Z","timestamp":1750307009669,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100004863","name":"New York State Foundation for Science, Technology and Innovation","doi-asserted-by":"publisher","award":["C050061"],"award-info":[{"award-number":["C050061"]}],"id":[{"id":"10.13039\/100004863","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0534404, IIS-0911036"],"award-info":[{"award-number":["IIS-0534404, IIS-0911036"]}],"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":[[2012,8]]},"abstract":"<jats:p>\n            Many data-driven social and Web applications involve collaboration and coordination. The vision of\n            <jats:italic>Declarative Data-Driven Coordination<\/jats:italic>\n            (D3C), proposed in Kot et al. [2010], is to support coordination in the spirit of data management: to make it data-centric and to specify it using convenient declarative languages. This article introduces\n            <jats:italic>entangled queries<\/jats:italic>\n            , a language that extends SQL by constraints that allow for the coordinated choice of result tuples across queries originating from different users or applications.\n          <\/jats:p>\n          <jats:p>\n            It is nontrivial to define a declarative coordination formalism without arriving at the general (NP-complete) Constraint Satisfaction Problem from AI. In this article, we propose an efficiently enforceable syntactic\n            <jats:italic>safety<\/jats:italic>\n            condition that we argue is at the sweet spot where interesting declarative power meets applicability in large-scale data management systems and applications. The key computational problem of D3C is to match entangled queries to achieve coordination. We present an efficient matching algorithm which statically analyzes query workloads and merges coordinating entangled queries into compound SQL queries. These can be sent to a standard database system and return only coordinated results. We present the overall architecture of an implemented system that contains our evaluation algorithm. We also describe a proof-of-concept Facebook application we have built on top of this system to allow friends to coordinate flight plans. Finally, we evaluate the performance of the matching algorithm experimentally on realistic coordination workloads.\n          <\/jats:p>","DOI":"10.1145\/2338626.2338629","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T22:21:06Z","timestamp":1347402066000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Entangled queries"],"prefix":"10.1145","volume":"37","author":[{"given":"Nitin","family":"Gupta","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucja","family":"Kot","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudip","family":"Roy","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Bender","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Gehrke","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,9,6]]},"reference":[{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering. 574--581","author":"Alonso G.","key":"e_1_2_1_1_1","unstructured":"Alonso , G. , Agrawal , D. , Abbadi , A. E. , Kamath , M. , G\u00fcnth\u00f6r , R. , and Mohan , C . 1996. Advanced transaction models in workflow contexts . In Proceedings of the IEEE International Conference on Data Engineering. 574--581 . Alonso, G., Agrawal, D., Abbadi, A. E., Kamath, M., G\u00fcnth\u00f6r, R., and Mohan, C. 1996. Advanced transaction models in workflow contexts. In Proceedings of the IEEE International Conference on Data Engineering. 574--581."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2003.1167337"},{"key":"e_1_2_1_3_1","unstructured":"Dechter R. 2003. Constraint Processing. Morgan Kaufmann.   Dechter R. 2003. Constraint Processing. Morgan Kaufmann."},{"volume-title":"Proceedings of the Conference on Innovative Data Systems Research. 104--113","author":"Finkelstein S.","key":"e_1_2_1_4_1","unstructured":"Finkelstein , S. , Heinzel , T. , Brendle , R. , Nassi , I. , and Roggenkemper , H. U . 2011. Transactional intent . In Proceedings of the Conference on Innovative Data Systems Research. 104--113 . Finkelstein, S., Heinzel, T., Brendle, R., Nassi, I., and Roggenkemper, H. U. 2011. Transactional intent. In Proceedings of the Conference on Innovative Data Systems Research. 104--113."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38742"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_1_7_1","unstructured":"Gupta N. and Rastogi P. Betanything. http:\/\/apps.facebook.com\/betanything.  Gupta N. and Rastogi P. Betanything. http:\/\/apps.facebook.com\/betanything."},{"key":"e_1_2_1_8_1","unstructured":"IBM Corporation. Web services transactions specification (WS-T). www.ibm.com\/developerworks\/library\/ws-coor\/.  IBM Corporation. Web services transactions specification (WS-T). www.ibm.com\/developerworks\/library\/ws-coor\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237794"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860706"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Larus J. R. and Rajwar R. 2007. Transactional Memory. Morgan and Claypool.  Larus J. R. and Rajwar R. 2007. Transactional Memory. Morgan and Claypool.","DOI":"10.1007\/978-3-031-01719-3"},{"key":"e_1_2_1_12_1","unstructured":"Leskovec J. and Pavlisic A. Slashdot data. http:\/\/snap.stanford.edu\/data\/soc-Slashdot0902.html.  Leskovec J. and Pavlisic A. Slashdot data. http:\/\/snap.stanford.edu\/data\/soc-Slashdot0902.html."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90014-9"},{"volume-title":"Communicating and Mobile Systems: the Pi-Calculus","author":"Milner R.","key":"e_1_2_1_14_1","unstructured":"Milner , R. 1999. Communicating and Mobile Systems: the Pi-Calculus . Cambridge University Press . Milner, R. 1999. Communicating and Mobile Systems: the Pi-Calculus. Cambridge University Press."},{"key":"e_1_2_1_15_1","volume-title":"IEEE International Conference on Data Engineering.","author":"Mohan Kamath K. R.","year":"1998","unstructured":"Mohan Kamath , K. R. 1998 . Failure handling and coordinated execution of concurrent workflows . In IEEE International Conference on Data Engineering. Mohan Kamath, K. R. 1998. Failure handling and coordinated execution of concurrent workflows. In IEEE International Conference on Data Engineering."},{"volume-title":"Proceedings of the 16th International Conference on Very Large Data Bases, D. McLeod, R. Sacks-Davis, and H.-J. Schek, Eds. Morgan Kaufmann, 83--94","author":"Nodine M. H.","key":"e_1_2_1_16_1","unstructured":"Nodine , M. H. and Zdonik , S. B . 1990. Cooperative transaction hierarchies: A transaction model to support design applications . In Proceedings of the 16th International Conference on Very Large Data Bases, D. McLeod, R. Sacks-Davis, and H.-J. Schek, Eds. Morgan Kaufmann, 83--94 . Nodine, M. H. and Zdonik, S. B. 1990. Cooperative transaction hierarchies: A transaction model to support design applications. In Proceedings of the 16th International Conference on Very Large Data Bases, D. McLeod, R. Sacks-Davis, and H.-J. Schek, Eds. Morgan Kaufmann, 83--94."},{"volume-title":"Proceedings of 14th International Conference on Very Large Data Bases, F. Bancilhon and D. J. DeWitt, Eds. Morgan Kaufmann, 26--37","author":"Pu C.","key":"e_1_2_1_17_1","unstructured":"Pu , C. , Kaiser , G. E. , and Hutchinson , N. C . 1988. Split-Transactions for open-ended activities . In Proceedings of 14th International Conference on Very Large Data Bases, F. Bancilhon and D. J. DeWitt, Eds. Morgan Kaufmann, 26--37 . Pu, C., Kaiser, G. E., and Hutchinson, N. C. 1988. Split-Transactions for open-ended activities. In Proceedings of 14th International Conference on Very Large Data Bases, F. Bancilhon and D. J. DeWitt, Eds. Morgan Kaufmann, 26--37."},{"key":"e_1_2_1_18_1","unstructured":"Python Software Foundation. Stackless python. http:\/\/zope.stackless.com.  Python Software Foundation. Stackless python. http:\/\/zope.stackless.com."},{"volume-title":"Concurrent Programming in ML","author":"Reppy J.","key":"e_1_2_1_19_1","unstructured":"Reppy , J. 1999. Concurrent Programming in ML . Cambridge University Press . Reppy, J. 1999. Concurrent Programming in ML. Cambridge University Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/108798.108806"},{"key":"e_1_2_1_21_1","unstructured":"Roberts J. and Srinivasan K. 2001. The tentative hold protocol. W3C Note www.w3.org\/TR\/tenthold-1\/.  Roberts J. and Srinivasan K. 2001. The tentative hold protocol. W3C Note www.w3.org\/TR\/tenthold-1\/."},{"key":"e_1_2_1_22_1","volume-title":"-L","author":"Sikl\u00f3ssy L.","year":"1982","unstructured":"Sikl\u00f3ssy , L. and Lauri\u00e8re , J . -L . 1982 . Removing restrictions in the relational data base model: An application of problem solving techniques. In Association for the Advancement of Artificial Intelligence. 310--313. Sikl\u00f3ssy, L. and Lauri\u00e8re, J.-L. 1982. Removing restrictions in the relational data base model: An application of problem solving techniques. In Association for the Advancement of Artificial Intelligence. 310--313."},{"key":"e_1_2_1_23_1","unstructured":"Virding R. Wikstr\u00f6m C. and Williams M. 1996. Concurrent Programming in ERLANG (2nd ed.). Prentice Hall International (UK) Ltd. Hertfordshire UK.   Virding R. Wikstr\u00f6m C. and Williams M. 1996. Concurrent Programming in ERLANG (2nd ed.). Prentice Hall International (UK) Ltd. Hertfordshire UK."},{"key":"e_1_2_1_24_1","volume-title":"Eds","author":"Widom J.","year":"1995","unstructured":"Widom , J. and Ceri , S. , Eds . 1995 . Active Database Systems: Triggers and Rules for Advanced Database Processing. Morgan Kaufmann . Widom, J. and Ceri, S., Eds. 1995. Active Database Systems: Triggers and Rules for Advanced Database Processing. Morgan Kaufmann."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2338626.2338629","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2338626.2338629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:00Z","timestamp":1750236540000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2338626.2338629"}},"subtitle":["Enabling declarative data-driven coordination"],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2338626.2338629"],"URL":"https:\/\/doi.org\/10.1145\/2338626.2338629","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}