DOI: 10.1145/3299881

Scalable Computation of High-
Order Optimization Queries

By Matteo Brucato, Azza Abouzied, and Alexandra Meliou

Abstract

Constrained optimization problems are at the heart of significant applications in a broad range of domains, including finance, transportation, manufacturing, and healthcare. Modeling and solving these problems has relied on application-specific solutions, which are often complex, error-prone, and do not generalize. Our goal is to create a domain-independent, declarative approach, supported and powered by the system where the data relevant to these problems typically resides: the database. We present a complete system that supports package queries, a new query model that extends traditional database queries to handle complex constraints and preferences over answer sets, allowing the declarative specification and efficient evaluation of a significant class of constrained optimization problems—integer linear programs (ILP)—within a database.

1. INTRODUCTION

Traditional database queries follow a simple model: they define constraints, in the form of selection predicates, that each tuple in the result must satisfy. This model is computationally efficient, as the database system can evaluate each tuple individually to determine whether it satisfies the query conditions. However, many practical, real-world problems require a collection of result tuples to satisfy constraints collectively, rather than individually.

Example 1 (Meal planner). A dietitian needs to design a daily meal plan for a patient. She wants a set of three gluten-free meals, between 2000 and 2500 calories in total, and with a low total intake of saturated fats.

Similar scenarios, requiring complex, high-order constraints arise frequently, and in many practical settings. A broad set of domains have applications that boil down to modeling and solving constrained optimization problems, for example, coordinating fleet and crew assignments in airline scheduling to reduce delays and costs, 19 managing delinquent consumer credit to minimize losses, 14 optimizing organ transplant allocation and acceptance, 1 and planning of cancer radiotherapy treatments. 20, 21 A significant class of constrained optimization problems are integer linear programs (ILP). ILP solutions alone account for billions in US dollars of projected benefits within each of these and other industry sectors. 7

Modeling and solving these problems has relied on
application-specific solutions, 2, 9, 13, 17, 23, 18 which can often
be complex and error-prone, and fail to generalize. Our goal
is to create a domain-independent, declarative approach,
supported and powered by the system where the data
The original version of this paper is entitled "Scalable
Package Queries in Relational Database Systems” and
was published in the Proceedings of the VLDB Endowment,
Vol. 9, No. 7 (2016), 576–587.

relevant to these problems typically resides: the database. We present a complete system that supports package queries, a new query model that extends traditional database queries to handle complex constraints and preferences over answer sets, allowing the declarative specification and efficient evaluation of a significant class of constrained optimization problems—ILP—within a database. Package queries are defined over traditional relations, but return packages. A package is a collection of tuples that (a) individually satisfy base predicates (traditional selection predicates), and (b) collectively satisfy global predicates (package-specific predicates). Package queries are combinatorial in nature: the result of a package query is a ( potentially infinite) set of packages, and an objective criterion can define a preference ranking among them.

Extending traditional database functionality to provide support for packages, rather than supporting packages at the application level, is justified by two reasons: First, the features of packages and the algorithms for constructing them are not unique to each application; therefore, the burden of package support should be lifted off application developers, and database systems should support package queries like traditional queries. Second, the data used to construct packages typically reside in a database system, and packages themselves are structured data objects that should naturally be stored in and manipulated by a database system.

Our work addresses three important challenges. The first challenge is to support declarative specification of packages. SQL enables the declarative specification of properties that result tuples should satisfy. In Example 1, it is easy to specify the exclusion of meals with gluten using a regular selection predicate in SQL. However, it is difficult to specify global constraints (e.g., total calories of a set of meals should be between 2000 and 2500 calories). Expressing such a query in SQL requires either complex self-joins that explode the size of the query, or recursion, which results in extremely complex queries that are hard to specify and optimize. Our goal is to maintain the declarative power of SQL, while extending its expressiveness to allow for the easy specification of packages.

The second challenge relates to the evaluation of package queries. Due to their combinatorial complexity, package queries are harder to evaluate than traditional database queries. 10 Package queries are in fact as hard as ILP. 5 Existing database technology is ineffective at