Tiresias: The Database Oracle for How-To Queries
by Alexandra Meliou, Dan Suciu
Abstract:
How-To queries answer fundamental data analysis questions of the form: ``How should the input change in order to achieve the desired output''. As a Reverse Data Management problem, the evaluation of how-to queries is harder than their ``forward'' counterpart: hypothetical, or what-if queries. In this paper, we present Tiresias, the first system that provides support for how-to queries, allowing the definition and integrated evaluation of a large set of constrained optimization problems, specifically Mixed Integer Programming problems, on top of a relational database system. Tiresias generates the problem variables, constraints and objectives by issuing standard SQL statements, allowing for its integration with any RDBMS. The contributions of this work are the following: (a) we define how-to queries using possible world semantics, and propose the specification language TiQL (for Tiresias Query Language) based on simple extensions to standard Datalog. (b) We define translation rules that generate a Mixed Integer Program (MIP) from TiQL specifications, which can be solved using existing tools. (c) Tiresias implements powerful ``data-aware'' optimizations that are beyond the capabilities of modern MIP solvers, dramatically improving the system performance. (d) Finally, an extensive performance evaluation on the TPC-H dataset demonstrates the effectiveness of these optimizations, particularly highlighting the ability to apply divide-and-conquer methods to break MIP problems into smaller instances.
Citation:
Alexandra Meliou and Dan Suciu, Tiresias: The Database Oracle for How-To Queries, in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2012, pp. 337–348.
Bibtex:
@inproceedings{DBLP:conf/sigmod/MeliouS12,
    Abstract = {How-To queries answer fundamental data analysis questions of
    the form: ``How should the input change in order to achieve the desired
    output''. As a Reverse Data Management problem, the evaluation of how-to
    queries is harder than their ``forward'' counterpart: hypothetical, or
    what-if queries. In this paper, we present Tiresias, the first system that
    provides support for how-to queries, allowing the definition and
    integrated evaluation of a large set of constrained optimization problems,
    specifically Mixed Integer Programming problems, on top of a relational
    database system. Tiresias generates the problem variables, constraints and
    objectives by issuing standard SQL statements, allowing for its
    integration with any RDBMS. The contributions of this work are the
    following: (a) we define how-to queries using possible world semantics,
    and propose the specification language TiQL (for Tiresias Query Language)
    based on simple extensions to standard Datalog. (b) We define translation
    rules that generate a Mixed Integer Program (MIP) from TiQL
    specifications, which can be solved using existing tools. (c) Tiresias
    implements powerful ``data-aware'' optimizations that are beyond the
    capabilities of modern MIP solvers, dramatically improving the system
    performance. (d) Finally, an extensive performance evaluation on the TPC-H
    dataset demonstrates the effectiveness of these optimizations,
    particularly highlighting the ability to apply divide-and-conquer methods
    to break MIP problems into smaller instances.},
    Author = {Alexandra Meliou and Dan Suciu},
    Booktitle = {Proceedings of the ACM SIGMOD International Conference on
                   Management of Data (SIGMOD)},
    doi = {10.1145/2213836.2213875},
    Pages = {337-348},
    Title = {\href{http://people.cs.umass.edu/ameli/projects/tiresias/papers/Tiresias.pdf}{Tiresias: {T}he Database Oracle for How-To Queries}},
    Venue = {SIGMOD},
    address = {Scottsdale, AZ},
    month = {May},
    Year = {2012}
}