Dominance-Based Data Reduction for Package Queries

Abstract

Prescriptive analytics workloads often require solving package queries over data that changes continuously. A package query (PQ) returns a multiset of tuples satisfying global constraints and optimizing a given objective, a natural formulation of constrained optimization within a database. When each attribute in the query has a clear "better" direction, e.g., lower cost and higher performance, most candidate tuples are irrelevant: they are strictly worse than others on every dimension and can never appear in an optimal solution. Yet, keeping solutions current as data evolves remains challenging: re-solving from scratch is slow, warm-starting helps only modestly, and solver preprocessing achieves only limited data reduction. We demonstrate SKYPQ, a system that employs a novel, dominance-based data reduction method for such package queries under updates. The key idea is to maintain a K-skyband index , a small, correctness-preserving subset of candidates, and apply a resolve checker to skip re-optimization when updates cannot affect the optimal package. The index can be shared by multiple PQs. Via an interactive interface, participants visualize the candidate space collapsing to the K-skyband, solve PQs over the reduced space with exact results, explore what-if scenarios, and observe the system efficiently handling batch updates. Participants experience firsthand how K-skyband reduction provides both speed and correctness for constrained optimization over evolving data.