2026-07-22T19:10:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5771 2024-03-06T10:37:01Z ddc:004 open_access

Scale Independence: Using Small Data to Answer Queries on Big Data (Invited Talk) Geerts, Floris Scale independence Access constraints Query processing 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Floris Geerts 2016 Is Part Of LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2016.2 urn:nbn:de:0030-drops-57715 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.2 eng https://creativecommons.org/licenses/by/3.0/legalcode