{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:07:30Z","timestamp":1789434450334,"version":"build-2803163510"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,3]]},"abstract":"<jats:p>\n            Traditional database queries follow a simple model: they define constraints that each tuple in the result must satisfy. This model is computationally efficient, as the database system can evaluate the query conditions on each tuple individually. However, many practical, real-world problems require a collection of result tuples to satisfy constraints collectively, rather than individually. In this paper, we present\n            <jats:italic>package queries<\/jats:italic>\n            , 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. We prove that PaQL is at least as expressive as integer linear programming, and therefore, evaluation of package queries is in general NP-hard. Second, we present a fundamental evaluation strategy that combines the capabilities of databases and constraint optimization solvers to derive solutions to package queries. 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 S\n            <jats:sc>ketch<\/jats:sc>\n            R\n            <jats:sc>efine<\/jats:sc>\n            , a scalable algorithm for package evaluation, with strong approximation guarantees ((1 \u00b1 \u03b5)\n            <jats:sup>6<\/jats:sup>\n            -factor approximation). Finally, we present extensive experiments over real-world and benchmark data. The results demonstrate that S\n            <jats:sc>ketch<\/jats:sc>\n            R\n            <jats:sc>efine<\/jats:sc>\n            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.\n          <\/jats:p>","DOI":"10.14778\/2904483.2904489","type":"journal-article","created":{"date-parts":[[2016,4,12]],"date-time":"2016-04-12T12:24:41Z","timestamp":1460463881000},"page":"576-587","source":"Crossref","is-referenced-by-count":21,"title":["Scalable package queries in relational database systems"],"prefix":"10.14778","volume":"9","author":[{"given":"Matteo","family":"Brucato","sequence":"first","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan Felipe","family":"Beltran","sequence":"additional","affiliation":[{"name":"New York University, Abu Dhabi, UAE"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Azza","family":"Abouzied","sequence":"additional","affiliation":[{"name":"New York University, Abu Dhabi, UAE"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandra","family":"Meliou","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,3]]},"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","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_4_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_5_1","volume-title":"Scalable package queries in relational database systems. CoRR, abs\/1512.03564","author":"Brucato M.","year":"2015","unstructured":"M. Brucato , J. F. Beltran , A. Abouzied , and A. Meliou . Scalable package queries in relational database systems. CoRR, abs\/1512.03564 , 2015 . M. Brucato, J. F. Beltran, A. Abouzied, and A. Meliou. Scalable package queries in relational database systems. CoRR, abs\/1512.03564, 2015."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733038"},{"key":"e_1_2_1_7_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_8_1","first-page":"35","volume-title":"HyperText","author":"De Choudhury M.","year":"2010","unstructured":"M. De Choudhury , M. Feldman , S. Amer-Yahia , N. Golbandi , R. Lempel , and C. Yu . Automatic construction of travel itineraries using social breadcrumbs . In HyperText , pages 35 -- 44 , 2010 . M. De Choudhury, M. Feldman, S. Amer-Yahia, N. Golbandi, R. Lempel, and C. Yu. Automatic construction of travel itineraries using social breadcrumbs. In HyperText, pages 35--44, 2010."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213592"},{"key":"e_1_2_1_10_1","first-page":"226","volume-title":"KDD","author":"Ester M.","year":"1996","unstructured":"M. Ester , H. Kriegel , J. Sander , and X. Xu . A density-based algorithm for discovering clusters in large spatial databases with noise . In KDD , pages 226 -- 231 , 1996 . M. Ester, H. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, pages 226--231, 1996."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_1_12_1","unstructured":"GNU Bison. https:\/\/www.gnu.org\/software\/bison\/.  GNU Bison. https:\/\/www.gnu.org\/software\/bison\/."},{"key":"e_1_2_1_13_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_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315518"},{"key":"e_1_2_1_15_1","first-page":"100","volume-title":"Algorithm as 136: A k-means clustering algorithm. Applied statistics","author":"Hartigan J. A.","year":"1979","unstructured":"J. A. Hartigan and M. A. Wong . Algorithm as 136: A k-means clustering algorithm. Applied statistics , pages 100 -- 108 , 1979 . J. A. Hartigan and M. A. Wong. Algorithm as 136: A k-means clustering algorithm. Applied statistics, pages 100--108, 1979."},{"key":"e_1_2_1_16_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_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593666"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794378"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"e_1_2_1_20_1","volume-title":"Finding groups in data: an introduction to cluster analysis","author":"Kaufman L.","year":"2009","unstructured":"L. Kaufman and P. J. Rousseeuw . Finding groups in data: an introduction to cluster analysis , volume 344 . John Wiley & Sons , 2009 . L. Kaufman and P. J. Rousseeuw. Finding groups in data: an introduction to cluster analysis, volume 344. John Wiley & Sons, 2009."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213875"},{"key":"e_1_2_1_23_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_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1033004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037661.2037665"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559206.2574794"},{"key":"e_1_2_1_28_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_29_1","unstructured":"The TPC-H Benchmark. http:\/\/www.tpc.org\/tpch\/.  The TPC-H Benchmark. http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1971947"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2904483.2904489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:50:06Z","timestamp":1672224606000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2904483.2904489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3]]},"references-count":30,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["10.14778\/2904483.2904489"],"URL":"https:\/\/doi.org\/10.14778\/2904483.2904489","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,3]]}}}