{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:49Z","timestamp":1779174829266,"version":"3.51.4"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T00:00:00Z","timestamp":1494547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2017,5,12]]},"abstract":"<jats:p>Many modern applications and real-world problems involve the design of item collections, or packages: from planning your daily meals all the way to mapping the universe. Despite the pervasive need for packages, traditional data management does not offer support for their definition and computation. This is because traditional database queries follow a powerful, but very simple model: a query defines constraints that each tuple in the result must satisfy. However, a system tasked with the design of packages cannot consider items independently; rather, the system needs to determine if a set of items collectively satisfy given criteria.<\/jats:p>\n          <jats:p>In this paper, we present package queries, a new query model that extends traditional database queries to handle complex constraints and preferences over answer sets. We develop a full-fledged package query system, implemented on top of a traditional database engine. Our work makes several contributions. First, we design PaQL, a SQL-based query language that supports the declarative specification of package queries. Second, we present a fundamental strategy for evaluating package queries that combines the capabilities of databases and constraint optimization solvers. The core of our approach is a set of translation rules that transform a package query to an integer linear program. Third, we introduce an offline data partitioning strategy allowing query evaluation to scale to large data sizes. Fourth, we introduce SKETCHREFINE, an efficient and scalable algorithm for package evaluation, which offers strong approximation guarantees. Finally, we present extensive experiments over real-world data. Our results demonstrate that SKETCHREFINE is effective at deriving high-quality package results, and achieves runtime performance that is an order of magnitude faster than directly using ILP solvers over large datasets.<\/jats:p>","DOI":"10.1145\/3093754.3093761","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T12:13:58Z","timestamp":1494850438000},"page":"24-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A Scalable Execution Engine for Package Queries"],"prefix":"10.1145","volume":"46","author":[{"given":"Matteo","family":"Brucato","sequence":"first","affiliation":[{"name":"University of Massachusetts, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Azza","family":"Abouzied","sequence":"additional","affiliation":[{"name":"New York University, Abu Dhabi, UAE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandra","family":"Meliou","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807258"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/01969720601139041"},{"key":"e_1_2_1_3_1","volume-title":"Paragon Decision Technology","author":"Bisschop J.","year":"2006","unstructured":"J. Bisschop . AIMMS Optimization Modeling . Paragon Decision Technology , 2006 . J. Bisschop. AIMMS Optimization Modeling. Paragon Decision Technology, 2006."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904489"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733038"},{"key":"e_1_2_1_6_1","first-page":"75","article-title":"On the complexity of branch and cut methods for the traveling salesman problem","volume":"1","author":"Cook W.","year":"1990","unstructured":"W. Cook and M. Hartmann . On the complexity of branch and cut methods for the traveling salesman problem . Polyhedral Combinatorics , 1 : 75 -- 82 , 1990 . W. Cook and M. Hartmann. On the complexity of branch and cut methods for the traveling salesman problem. Polyhedral Combinatorics, 1:75--82, 1990.","journal-title":"Polyhedral Combinatorics"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810617.1810626"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213592"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_1_10_1","first-page":"144","volume-title":"The primal-dual method for approximation algorithms and its application to network design problems. Approximation algorithms for NP-hard problems","author":"Goemans M. X.","year":"1997","unstructured":"M. X. Goemans and D. P. Williamson . The primal-dual method for approximation algorithms and its application to network design problems. Approximation algorithms for NP-hard problems , pages 144 -- 191 , 1997 . M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. Approximation algorithms for NP-hard problems, pages 144--191, 1997."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50074-4"},{"key":"e_1_2_1_12_1","unstructured":"IBM CPLEX Optimization Studio. http:\/\/www.ibm.com\/software\/commerce\/optimization\/cplex-optimizer\/.  IBM CPLEX Optimization Studio. http:\/\/www.ibm.com\/software\/commerce\/optimization\/cplex-optimizer\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593666"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794378"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213875"},{"key":"e_1_2_1_18_1","volume-title":"NIPS","author":"Mirzasoleiman B.","year":"2013","unstructured":"B. Mirzasoleiman , A. Karbasi , R. Sarkar , and A. Krause . Distributed submodular maximization: Identifying representative elements in massive data . In NIPS , 2013 . B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause. Distributed submodular maximization: Identifying representative elements in massive data. In NIPS, 2013."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1033004"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037661.2037665"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559206.2574794"},{"key":"e_1_2_1_22_1","unstructured":"The Sloan Digital Sky Survey. http:\/\/www.sdss.org\/.  The Sloan Digital Sky Survey. http:\/\/www.sdss.org\/."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750549"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093761","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3093754.3093761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:16Z","timestamp":1750217416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,12]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5,12]]}},"alternative-id":["10.1145\/3093754.3093761"],"URL":"https:\/\/doi.org\/10.1145\/3093754.3093761","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2017,5,12]]},"assertion":[{"value":"2017-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}