@article{BrucatoBAM2016,
  author    = {Matteo Brucato and 
               Juan Felipe Beltran and 
               Azza Abouzied and
               Alexandra Meliou},
  title     = {\href{http://www.vldb.org/pvldb/vol9/p576-brucato.pdf}{Scalable Package Queries in Relational Database Systems}},
  abstract  = {
  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 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. 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 SketchRefine, a scalable algorithm
  for package evaluation, with strong approximation guarantees
  ((1±ε)^6-factor approximation). Finally, we present extensive experiments
  over real-world and benchmark data. The 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.
  },
  journal   = {PVLDB},
  volume    = {9},
  number    = {7},
  year      = {2016},
  pages     = {575--587},
  venue     = {PVLDB},
  doi       = {10.14778/2904483.2904489},
  comment      = {<span class="emphasis">[Best papers of VLDB 2016]</span>},
}