Incremental Package Queries

A package query returns a multiset of tuples satisfying global constraints and optimizing an objective — a natural formulation of constrained optimization directly within a database. Package queries power prescriptive analytics across finance, healthcare, logistics, and cloud computing.

As underlying data evolves continuously, re-solving from scratch is expensive. Incremental Package Queries develops principled methods to maintain optimal solutions efficiently, updating only what the data changes require.

Example

VM Provisioning

Jordan is a platform engineer provisioning VMs for a data pipeline that requires at least 800 Compute Units (CU). Jordan wants the cheapest bundle meeting this requirement, with practical constraints: at least 8 instances for fault tolerance, at most 12 instances to respect account quotas, and no more than 2 repetitions of a single VM type to avoid over-reliance on one configuration. The cloud provider's catalog contains thousands of VM offers, yet Jordan's package will contain only 8–12 of them. Spot prices fluctuate with supply and demand, so an overpriced option now may become the best choice an hour later, so Jordan must re-optimize frequently. Yet at any moment, most options are obviously poor deals: why consider a 20 CU instance at $2/hr when another offers 40 CU at $1/hr? Jordan suspects most of the catalog is irrelevant, but they need a principled way to identify which options actually matter.

Jordan's requirements can be expressed directly as a package query in PaQL:

SELECT    PACKAGE(*) AS P
FROM      vm_offers
REPEAT    EACH P.offer_id AT MOST 2
SUCH THAT
          SUM(P.compute_units) >= 800 AND
          COUNT(P.*) BETWEEN 8 AND 12
MINIMIZE  SUM(P.cost_per_hour)

Demo

The SKYPQ demo provides an interactive interface for exploring dominance-based data reduction for package queries. Starting from a catalog of 6,500 VM offers, the system reduces the candidate space to a small K-skyband while preserving optimality guarantees. Participants can solve package queries over the reduced space with exact results, trigger what-if scenarios such as price changes and VM discontinuation, and observe the system handling streaming updates without full re-optimization.

To appear at VLDB 2026 (Demonstration Track).

People

Vasileios Vittis

PhD Student, UMass Amherst

Azza Abouzied

Professor, NYU Abu Dhabi

Peter J. Haas

Professor, UMass Amherst

Alexandra Meliou

Professor, UMass Amherst

Publications

SKYPQ: Dominance-Based Data Reduction for Package Queries

Vasileios Vittis, Azza Abouzied, Peter J. Haas, Alexandra Meliou

VLDB 2026 (Demonstration Track)

Paper Demo Screenshot

Incremental Package Maintenance

Vasileios Vittis, Azza Abouzied, Peter J. Haas, Alexandra Meliou

NEDB 2025 (Poster)

Poster

Related Work

This research builds on the foundations of Package Queries:

Code

Source code is available on GitHub under the MIT License.

Acknowledgements

This work was supported by the National Science Foundation under grants 1943971 and 2211918. This work was also supported by NYUAD CITIES, funded by Tamkeen under the Research Institute Award CG001.