Publication
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)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Record
Identifier
Creation 06.12.2018
Last edited 17.06.2024
To cite this reference