sPaQL TooLs is a Stochastic Package Query Interface for Scalable Constrained Optimization. The system extends traditional query engines to support package generation - finding collections of items that satisfy constraints defined over the entire collection, not just individual items. For example, given uncertain predictions for future stock prices, sPaQL TooLs finds a set of trades that maximizes expected future gain while ensuring losses only happen with a certain probability.

This project won Best Demonstration Award at VLDB’20, one of the top conferences in database systems, recognizing both the technical innovation in scalable constrained optimization and the practical applicability of the system to real-world problems.

Use Cases

The system solves real-world constrained optimization problems:

Investment Portfolio: A broker constructs a portfolio for a client with $50K budget, requiring at least 30% in technology stocks and a balance of short-term and long-term options. Traditional queries evaluate stocks individually; sPaQL TooLs finds stock packages satisfying all constraints collectively.

Meal Planner: An athlete needs three high-protein, gluten-free meals totaling 2000-2500 calories. While gluten-free can be checked per meal, calorie and protein totals require collective verification across the entire meal package.

Technical Architecture

Building sPaQL TooLs required developing a complete query engine extension with sophisticated optimization algorithms and an interactive user interface:

• Backend Query Engine: Extended PostgreSQL with custom package query operators, implementing scalable constraint satisfaction algorithms that handle both deterministic and stochastic constraints
• Optimization Algorithms: Developed novel algorithms for constrained optimization under uncertainty, balancing solution quality with computation time for interactive response
• Frontend Stack: Built with React and D3.js, providing an intuitive interface for specifying complex constraints and visualizing feasible solution spaces
• Stochastic Modeling: Implemented support for uncertain data attributes with multiple distribution types (Geometric Brownian, Normal, etc.), enabling probability-based constraint specifications
• Query Language Design: Created the sPaQL query language syntax, extending SQL with package operations like SUCH THAT for collective constraints and MAXIMIZE for optimization objectives

The system architecture handles the challenge of scaling constrained optimization to real-world dataset sizes while maintaining interactive query response times.

Publications