License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2016.2
URN: urn:nbn:de:0030-drops-57715
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5771/
Geerts, Floris
Scale Independence: Using Small Data to Answer Queries on Big Data (Invited Talk)
Abstract
Large datasets introduce challenges to the scalability of query answering. Given a query Q and a dataset D, it is often prohibitively costly to compute the query answers Q(D) when D is big. To this end, one may want to use heuristics, "quick and dirty" algorithms which return approximate answers. However, in many applications it is a must to find exact query answers. So, how can we efficiently compute Q(D) when D is big or when we only have limited resources?
One idea is to find a small subset D_Q of D such that Q(D_Q)=Q(D) where the size of D_Q is independent of the size of the underlying dataset D. Intuitively, when such a D_Q can be found for a query Q, the query is said to be scale independent (Armbrust et al. 2011, Armbrust et al. 2013, Fan et al. 2014). Indeed, for answering such queries the size of the underlying database does not matter, i.e., query processing is independent of the scale of the database.
In this talk, I will survey various formalisms that enable large classes of queries to be scale independent. These formalisms primarily rely on the availability of access constraints, a combination of indexes and cardinality constraints, on the data (Fan et al. 15, Fan et al. 14). We will take a closer look at how, in the presence of such constraints, queries can often be compiled into efficient query plans that access a bounded amount data (Cao et al. 2014, Fan et al. 2015), and how these techniques relate to query processing in the presence of access patterns (Benedikt et al. 2015, Benedikt et al. 2014, Deutsch et al. 2007). Finally, we illustrate that scale independent queries are quite common in practice and that they indeed can be efficiently answered on big datasets when access constraints are present (Cao et al. 2015, Cao et al. 2014).
BibTeX - Entry
@InProceedings{geerts:LIPIcs:2016:5771,
author = {Floris Geerts},
title = {{Scale Independence: Using Small Data to Answer Queries on Big Data (Invited Talk)}},
booktitle = {19th International Conference on Database Theory (ICDT 2016)},
pages = {2:1--2:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-002-6},
ISSN = {1868-8969},
year = {2016},
volume = {48},
editor = {Wim Martens and Thomas Zeume},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5771},
URN = {urn:nbn:de:0030-drops-57715},
doi = {10.4230/LIPIcs.ICDT.2016.2},
annote = {Keywords: Scale independence, Access constraints, Query processing}
}
|
Keywords: |
|
Scale independence, Access constraints, Query processing |
|
Collection: |
|
19th International Conference on Database Theory (ICDT 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
14.03.2016 |
