## 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 language | English (US) |
---|---|

Title of host publication | 19th International Conference on Database Theory, ICDT 2016 |

Editors | Thomas Zeume, Wim Martens |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770026 |

DOIs | |

State | Published - Mar 1 2016 |

Externally published | Yes |

Event | 19th International Conference on Database Theory, ICDT 2016 - Bordeaux, France Duration: Mar 15 2016 → Mar 18 2016 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 48 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 19th International Conference on Database Theory, ICDT 2016 |
---|---|

Country/Territory | France |

City | Bordeaux |

Period | 3/15/16 → 3/18/16 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

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