Scale independence : using small data to answer queries on big data (invited talk)
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].
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.
Germany : Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik , 2016
48 (2016) , p. 2:1-2:2
Full text (Publisher's DOI)
Full text (open access)
Research group
Publication type
Publications with a UAntwerp address
External links
Creation 06.12.2018
Last edited 15.07.2021
To cite this reference