research-article

Tiresias: the database oracle for how-to queries

Authors:

Alexandra Meliou,

Dan SuciuAuthors Info & Claims

SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

Pages 337 - 348

https://doi.org/10.1145/2213836.2213875

Published: 20 May 2012 Publication History

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.

References

[1]

GNU Linear Programing Kit. http://www.gnu.org/s/glpk.

[2]

TPC-H benchmark specification. http://www.tpc.org/tpch.

[3]

P. Agrawal, O. Benjelloun, A. D. Sarma, C. Hayworth, S. U. Nabar, T. Sugihara, and J. Widom. Trio: A system for data, uncertainty, and lineage. In VLDB, pages 1151--1154, 2006.

Digital Library

[4]

Y. Amsterdamer, D. Deutch, and V. Tannen. Provenance for aggregate queries. In PODS, pages 153--164, 2011.

Digital Library

[5]

L. Antova, T. Jansen, C. Koch, and D. Olteanu. Fast and simple relational processing of uncertain data. In ICDE, pages 983--992, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[6]

L. Antova, C. Koch, and D. Olteanu. From complete to incomplete information and back. In SIGMOD Conference, pages 713--724, 2007.

Digital Library

[7]

A. Arasu, R. Kaushik, and J. Li. Data generation using declarative constraints. In SIGMOD Conference, pages 685--696, 2011.

Digital Library

[8]

D. Barone, L. Jiang, D. Amyot, and J. Mylopoulos. Composite indicators for business intelligence. In ER, pages 448--458, 2011.

Digital Library

[9]

C. Binnig, D. Kossmann, and E. Lo. Reverse query processing. In ICDE, pages 506--515, 2007.

[10]

A. Bohannon, B. C. Pierce, and J. A. Vaughan. Relational lenses: a language for updatable views. In PODS, pages 338--347, 2006.

Digital Library

[11]

D. Chen, R. Batson, and Y. Dang. Applied Integer Programming: Modeling and Solution. John Wiley & Sons, 2011.

[12]

S. Cohen, W. Nutt, and Y. Sagiv. Containment of aggregate queries. In ICDT, pages 111--125, 2003.

Digital Library

[13]

Y. Cui, J. Widom, and J. L. Wiener. Tracing the lineage of view data in a warehousing environment. ACM Trans. Database Syst., 25(2):179--227, 2000.

Digital Library

[14]

N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. VLDBJ, 16(4):523--544, 2007.

Digital Library

[15]

R. Fagin and A. Nash. The structure of inverses in schema mappings. J. ACM, 57(6):31, 2010.

Digital Library

[16]

T. J. Green, G. Karvounarakis, and V. Tannen. Provenance semirings. In PODS, pages 31--40, 2007.

Digital Library

[17]

T. Imielinski and W. L. Jr. Incomplete information in relational databases. J. ACM, 31(4):761--791, 1984.

Digital Library

[18]

R. Jampani, F. Xu, M. Wu, L. L. Perez, C. M. Jermaine, and P. J. Haas. Mcdb: a monte carlo approach to managing uncertain data. In SIGMOD Conference, pages 687--700, 2008.

Digital Library

[19]

N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The dlv system for knowledge representation and reasoning. ACM Trans. Comput. Log., 7(3):499--562, 2006.

Digital Library

[20]

A. Makhorin. Modeling language GNU MathProg. Structure,(January), 2010.

[21]

A. Meliou, W. Gatterbauer, and D. Suciu. Reverse data management. In VLDB, 2011.

[22]

J. D. Ullman. Principles of Database and Knowledgebase Systems I. Computer Science Press, Rockville, MD 20850, 1989.

Digital Library

[23]

J. D. Ullman. Principles of Database and Knowledgebase Systems II: The New Technologies. Computer Science Press, Rockvill, MD 20850, 1989.

Digital Library

Cited By

Ko RXiao COnizuka MLin ZHuang Y(2025)Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database SystemsProceedings of the ACM on Management of Data10.1145/37097343:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709734
Campbell FSilberstein AStoyanovich JMoskovitch Y(2024)Query Refinement for Diverse Top-k SelectionProceedings of the ACM on Management of Data10.1145/36549692:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654969
Wu ZMarcus RLiu ZNegi PNathan VPfeil PSaxena GRahman MNarayanaswamy BKraska TBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Stage: Query Execution Time Prediction in Amazon RedshiftCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3653391(280-294)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3653391
Show More Cited By

Index Terms

Tiresias: the database oracle for how-to queries

Recommendations

Tiresias: a demonstration of how-to queries
SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

In this demo, we will present Tiresias, the first how-to query engine. How-to queries represent fundamental data analysis questions of the form: "How should the input change in order to achieve the desired output". They exemplify an important Reverse ...
The Ant Lion Optimizer

The Ant Lion Optimizer inspired by the hunting mechanism of antlions is proposed.The ALO algorithm is benchmarked on 29 well-known test functions.The results on the unimodal functions show the superior exploitation of ALO.The exploratory ability of ALO ...
An upgraded artificial bee colony (ABC) algorithm for constrained optimization problems

Artificial bee colony (ABC) algorithm developed by Karaboga is a nature inspired metaheuristic based on honey bee foraging behavior. It was successfully applied to continuous unconstrained optimization problems and later it was extended to constrained ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

May 2012

886 pages

ISBN:9781450312479

DOI:10.1145/2213836

General Chairs:
K. Selçuk Candan
Arizona State University
,
Yi Chen
Arizona State University
,
Richard Snodgrass
University of Arizona
,
Program Chair:
Luis Gravano
Columbia University
,
Publications Chair:
Ariel Fuxman
Microsoft Research

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '12

Sponsor:

SIGMOD

SIGMOD/PODS '12: International Conference on Management of Data

May 20 - 24, 2012

Arizona, Scottsdale, USA

Acceptance Rates

SIGMOD '12 Paper Acceptance Rate 48 of 289 submissions, 17%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
645
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ko RXiao COnizuka MLin ZHuang Y(2025)Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database SystemsProceedings of the ACM on Management of Data10.1145/37097343:1(1-27)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709734
Campbell FSilberstein AStoyanovich JMoskovitch Y(2024)Query Refinement for Diverse Top-k SelectionProceedings of the ACM on Management of Data10.1145/36549692:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654969
Wu ZMarcus RLiu ZNegi PNathan VPfeil PSaxena GRahman MNarayanaswamy BKraska TBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Stage: Query Execution Time Prediction in Amazon RedshiftCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3653391(280-294)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3653391
Algarni SGlavic BLee SChapman A(2024)Solving Why Not Questions for Aggregate Constraints Through Query Repair2024 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)10.1109/EuroSPW61312.2024.00072(592-596)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSPW61312.2024.00072
Chen ZManolios PRiedewald M(2023)Why Not Yet: Fixing a Top-k Ranking that is Not Fair to IndividualsProceedings of the VLDB Endowment10.14778/3598581.359860616:9(2377-2390)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.14778/3598581.3598606
Makhija NGatterbauer W(2023)A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP RelaxationsProceedings of the ACM on Management of Data10.1145/36267151:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626715
Shen FHeravi KGomez OGalhotra SGilad ARoy SSalimi B(2023)Causal What-If and How-To Analysis Using HypeR2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00293(3663-3666)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00293
Galhotra SGong YFernandez R(2023)Metam: Goal-Oriented Data Discovery2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00213(2780-2793)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00213
Roy S(2022)Toward interpretable and actionable data analysis with explanations and causalityProceedings of the VLDB Endowment10.14778/3554821.355490215:12(3812-3820)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.14778/3554821.3554902
Liu YWu WFlokas LWang JWu E(2022)Enabling SQL-based training data debugging for federated learningProceedings of the VLDB Endowment10.14778/3494124.349412515:3(388-400)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3494124.3494125
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten