Data Management Perspectives on Prescriptive Analytics

In prior work, we proposed extensions to the SQL language to allow for the declarative specification of package queries. Using the Package Query Language (PaQL) [6], the portfolio example can be expressed as follows:

This query includes standard selection predicates on individual tuples (i.e., category != ’pharm’), as well as high-order package-level constraints (in the SUCH THAT clause) and objectives (to maximize the total gain). Additional constraints can restrict the package cardinality and repetitions of tuples in a package; see [5] for a complete language specification.

The PackageBuilder system [4, 6] transforms a PaQL specification into an Integer Linear Program (ILP) and uses an off-the-shelf ILP solver to compute the desired package. When, as is typical, the number of database rows is large, direct solution by the solver is infeasible because of the large size of the ILP. In prior work, we developed an iterative approximate solution algorithm called SketchRefine [6] to handle large numbers of rows while providing approximation guarantees. Briefly, the algorithm first partitions the rows into groups, where the rows in each group have similar attribute values, and then computes a representative for each group. A small ILP using only the representatives can be then easily solved – the “sketch”. The sketch is then iteratively “refined” by carefully replacing each representative using the rows that it represents. The process maintains feasibility of the current solution until the final package is obtained. Limiting the size of each group to be a small number of $\tau$ tuples ensures that each refine phase can be executed efficiently and allows for approximation guarantees.

While SketchRefine is computationally efficient for datasets with up to tens of millions of tuples, it has three critical shortcomings:

• $\mathrm{■}$

  False infeasibility: Tight constraints can lead to sketches that are overly restrictive and exclude feasible solutions.

• $\mathrm{■}$

  Suboptimal results: The partitioning results in aggressive pruning that may discard valuable outlier tuples.

• $\mathrm{■}$

  Scalability: With datasets beyond a certain size (about 100 million tuples), SketchRefine can no longer break down the optimization problem effectively, as we will either have too many partitions or too large partitions.

Progressive Shading [16] addresses these issues by making refinement more gradual. It uses a partitioning hierarchy, so we can refine over increasingly finer partitions. During this process, it preserves additional neighboring tuples at every level, to ensure that potentially valuable tuples are not pruned aggressively. The novel Dynamic Low Variance (DLV) partitioning algorithm is highly adaptive, and minimizes attribute variance to improve homogeneity within each partition. Its dynamic nature allows it to efficiently partition datasets with widely varying distributions and sizes. It is not enough, however, to apply higher level database systems concepts such as divide-and-conquer over hierarchical partitions to achieve scalability over billions of tuples. We need to open up the solver black box and bring some novel ideas from optimizations research: with progressive shading, we mimicked LP rounding techniques well-studied in OR to solve simpler LP problems across layers, only applying the ILP at the lowest layer; we also implemented our own custom LP solver that exploits the unique structure of package queries that have billions of decision variables but only a handful of constraints.

Not all data is deterministic; uncertainty is inherent in many application settings, as data may be sampled from predictive models or simulations. Package queries over uncertain data, or stochastic package queries, are more computationally demanding than deterministic package queries, as problems grow not only along the tuple dimension, but also the uncertainty dimension. To solve the stochastic optimization problem specified by a SPaQL query, we can approximate it by a deterministic problem via a Monte Carlo technique called Sample Average Approximation (SAA) [14]. SAA creates numerous scenarios (“possible worlds”), each comprising a sample realization for every stochastic attribute of every tuple in the relation, e.g., a realized gain for every Stock–Sell_After pair as in Figure 3. Such scenarios can be created using the Variable Generation functions of Monte Carlo databases like MCDB [13]. In the SAA approximation, expectations are replaced by averages over scenarios and probabilities are replaced by empirical probabilities. E.g., the SAA approximation to the example query in Figure 3 maximizes the average profit over all the scenarios, with at most 5% of the scenarios having losses over $10.

A large number of scenarios is necessary for SAA to achieve good accuracy, especially if the uncertain attributes have high variance. A higher number of tuples further necessitates an increase in the number of scenarios to maintain accuracy, due to the increase in dimensionality [8]. However, using a large number of scenarios is impractical, as it is not only inefficient to generate them, but they also quickly cause the optimization problem to grow too large. Non-convex optimization problems are notorious for requiring large solver runtimes to optimize, and naive in-memory solvers crash when creating packages from millions of scenarios.

SummarySearch [7] is the first approach for in-database processing of stochastic package queries, and introduced two key ideas. First, it uses a small number (in the order of hundreds) of optimization scenarios to derive a package; then, it validates whether this package satisfies the constraints over a much larger set of validation scenarios. To prevent the optimizer from overfitting to the optimization scenarios and creating packages that will fail validation, SummarySearch combines multiple scenarios into conservative summary scenarios. These conservative summaries have a smaller feasibility region: a package that satisfies the constraints over the conservative summary scenarios is guaranteed to satisfy the constraints over the original scenarios. Thus, the resulting package is more likely to pass validation. The algorithm automatically tunes its level of conservativeness to avoid over-restricting the solution space. However, the optimization problems still remain non-convex, albeit with fewer indicator variables than the naive approach.

RCL-Solve [12] resolves this weakness of SummarySearch by replacing non-convex risk constraints with special “linearized” risk constraints. The resulting optimization problems are thus converted to Integer Linear Programs (ILPs). RCL-Solve automatically adjusts the parameters of the linearized risk constraints to find the closest linear approximation of the original non-convex optimization problem that results in a near-optimal and constraint-satisfying package. Stochastic SketchRefine scales RCL-Solve with respect to the number of tuples using a divide and conquer approach similar to SketchRefine. Like SketchRefine, it consists of the sketch and refine phases, but contains necessary algorithmic modifications that address challenges raised by the stochastic nature of the problem. In particular, partitioning creates groups of tuples with similar values and similar stochastic behavior, and representative tuples are represented by multiple stochastically identical duplicates. The latter allows more flexibility to the optimizer to reduce risk by diversifying packages.

Many datasets are dynamic: values get updated, tuples get added or removed, and the data distribution may shift over time. A key challenge for in-database constraint optimization is that even small changes in the data require computationally intensive package queries to be re-evaluated from scratch. In most practical settings, the overall structure of the constrained optimization problem is likely to remain the same, even if data and perhaps query parameters may change frequently. Re-executing such queries from scratch to maintain results up to date is tedious and computationally expensive, and can render exploratory analysis impractical. We are currently considering several strategies for dealing with evolving data.

• $\mathrm{■}$

  Incremental package maintenance. In this direction, the goal is to update packages without re-engaging the optimizer. For example, if a tuple gets deleted (e.g., if a stock is removed), a package containing that tuple could be heuristically updated by looking for a replacement for that tuple (rather than re-executing the optimization). Similarly, if a new tuple is introduced, we can check if its addition to the package, potentially replacing another tuple, improves the result. These approaches are heuristic, but they are likely to perform well in many cases of small changes.

• $\mathrm{■}$

  Data reduction techniques. In this direction, the goal is to re-execute the optimization, but over a drastically reduced problem dataset. For example, if several new tuples are added to the data, we could update a previous package result by executing the package query on the small dataset comprising of the tuples in the previous package result and the new tuples (rather than executing the query over the entire dataset). Other variants of this approach can be more sophisticated and use carefully crafted subsets of the data seen so far (rather than simply the previous package) since previously non-optimal tuples might become optimal later on. This can be achieved by clever reasoning about the likelihood that a certain datapoint could be in a package result. For example, a stock with high price and poor gain would not be selected by the optimizer for the portfolio query, and thus it need not be included in the optimization. Generalizing this intuition has the potential to achieve significant reductions in the data used in the optimization, thus making re-evaluation of package queries more practical.

How to deal with changing query parameters remains a challenging problem. Optimization theory, specifically the theory of “sensitivity analysis” – see, e.g., [3, Chapter 5] – provides some insights on dealing with, for example, small perturbations in bounding values for constraints, but in general a more sophisticated strategy is needed for deciding which previous data to retain.

Prescriptive analytics plays a key role in a broad variety of domains, but has received relatively little attention from the database community. Package queries model a useful class of optimization problems, but many challenges remain in exploring broader and more general settings.