Tiresias

A How-To Query Engine

Often users, administrators, and analysts are interested in changing their data in ways that would achieve certain conditions and constraints: "What advertisements will result in the best sales increase, at a cost bounded by X?", "How can I increase my clients' return on investment with the minimum number of trades?". How-to queries define constrained optimization problems over a dataset, and can be solved by dedicated tools, like Linear and Integer Programming solvers. Unfortunately, these tools are currently decoupled from the database systems where the relevant data resides. As a result, decision makers have to either (a) manually explore possible solutions by inflicting changes in their data and observing their effect, or (b) extract the relevant data and manually encode the corresponding optimization problem, which is a tedious and error-prone process.
For a discussion on how-to queries, please refer to the Reverse Data Management project.

Tiresias architecture

The goal of this project is to seamlessly integrate databases with constrained problem solving in a fully-fledged system. We are building a system that allows the user to specify an optimization problem over their data declaratively. The system then translates the declarative input into a mixed integer program that is sent to a dedicated solver. The contributions of this project are 3-fold: (a) a declarative interface for defining how-to queries over a database, (b) translation rules from the declarative statements to the MIP specification, and (c) a suite of data-specific optimizations that allow scaling to large datasets.

Publications

  1. Tiresias: The Database Oracle for How-To Queries
    A. Meliou and D. Suciu
    SIGMOD 2012.
    [ pdf Paper ] [ ppt Slides ] [ pdf Slides ]

  2. Tiresias: A Demonstration of How-To Queries (best demonstration award)
    A. Meliou, Y. Song, and D. Suciu
    SIGMOD 2012.
    [ pdf Paper ] [ pdf Poster ]

  3. The Power of How-To Queries
    A. Meliou
    Presentation at NEDB 2013.
    [ pdf Paper ]


People

Faculty (University of Massachusetts, Amherst)
Faculty (University of Washington)