Algorithms for provisioning queries and analytics

Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

Provisioning is a technique for avoiding repeated expensive computations in what-if analysis. Given a query, an analyst formulates k hypotheticals, each retaining some of the tuples of a database instance, possibly overlapping, and she wishes to answer the query under scenarios, where a scenario is defined by a subset of the hypotheticals that are "turned on". We say that a query admits compact provisioning if given any database instance and any k hypotheticals, one can create a poly-size (in k) sketch that can then be used to answer the query under any of the 2k possible scenarios without accessing the original instance. In this paper, we focus on provisioning complex queries that combine relational algebra (the logical component), grouping, and statistics/analytics (the numerical component). We first show that queries that compute quantiles or linear regression (as well as simpler queries that compute count and sum/average of positive values) can be compactly provisioned to provide (multiplicative) approximate answers to an arbitrary precision. In contrast, exact provisioning for each of these statistics requires the sketch size to be exponential in k. We then establish that for any complex query whose logical component is a positive relational algebra query, as long as the numerical component can be compactly provisioned, the complex query itself can be compactly provisioned. On the other hand, introducing negation or recursion in the logical component again requires the sketch size to be exponential in k. While our positive results use algorithms that do not access the original instance after a scenario is known, we prove our lower bounds even for the case when, knowing the scenario, limited access to the instance is allowed.

Original languageEnglish (US)
Title of host publication19th International Conference on Database Theory, ICDT 2016
EditorsThomas Zeume, Wim Martens
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770026
DOIs
StatePublished - Mar 1 2016
Externally publishedYes
Event19th International Conference on Database Theory, ICDT 2016 - Bordeaux, France
Duration: Mar 15 2016Mar 18 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume48
ISSN (Print)1868-8969

Conference

Conference19th International Conference on Database Theory, ICDT 2016
Country/TerritoryFrance
CityBordeaux
Period3/15/163/18/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximate Query Answering
  • Data Compression
  • Provisioning
  • What-if Analysis

Fingerprint

Dive into the research topics of 'Algorithms for provisioning queries and analytics'. Together they form a unique fingerprint.

Cite this