|
Title
|
|
|
|
Scale independence : using small data to answer queries on big data (invited talk)
| |
|
Author
|
|
|
|
| |
|
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 DQ of D such that Q(DQ) = Q(D) where the size of DQ is independent of the size of the underlying dataset D. Intuitively, when such a DQ can be found for a query Q, the query is said to be scale independent [1, 2, 9]. 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 [8, 9]. 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 [6, 8], and how these techniques relate to query processing in the presence of access patterns [3, 4, 7]. 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 [5, 6]. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
LIPIcs : Leibniz International Proceedings in Informatics. - Place of publication unknown
| |
|
Source (book)
|
|
|
|
19th International Conference on Database Theory (ICDT 2016) / Martens, Wim [edit.]; et al.
| |
|
Publication
|
|
|
|
Germany
:
Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik
,
2016
| |
|
ISSN
|
|
|
|
1868-8969
| |
|
ISBN
|
|
|
|
978-3-95977-002-6
| |
|
DOI
|
|
|
|
10.4230/LIPICS.ICDT.2016.2
| |
|
Volume/pages
|
|
|
|
48
(2016)
, p. 2:1-2:2
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|
Full text (open access)
|
|
|
|
| |
|