Abstract
Provisioning is a technique for avoiding repeated expensive computations in whatif 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 polysize (in k) sketch that can then be used to answer the query under any of the 2^k 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.
BibTeX  Entry
@InProceedings{assadi_et_al:LIPIcs:2016:5787,
author = {Sepehr Assadi and Sanjeev Khanna and Yang Li and Val Tannen},
title = {{Algorithms for Provisioning Queries and Analytics}},
booktitle = {19th International Conference on Database Theory (ICDT 2016)},
pages = {18:118:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770026},
ISSN = {18688969},
year = {2016},
volume = {48},
editor = {Wim Martens and Thomas Zeume},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5787},
URN = {urn:nbn:de:0030drops57877},
doi = {10.4230/LIPIcs.ICDT.2016.18},
annote = {Keywords: Whatif Analysis, Provisioning, Data Compression, Approximate Query Answering}
}
Keywords: 

Whatif Analysis, Provisioning, Data Compression, Approximate Query Answering 
Seminar: 

19th International Conference on Database Theory (ICDT 2016) 
Issue Date: 

2016 
Date of publication: 

29.02.2016 