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.2015.13
URN: urn:nbn:de:0030-drops-49987
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4998/
Go to the corresponding LIPIcs Volume Portal

Schweikardt, Nicole

Using Locality for Efficient Query Evaluation in Various Computation Models (Invited Talk)

pdf-format:
25.pdf (0.2 MB)

Abstract

In the database theory and logic literature, different notions of locality of queries have been studied, the most prominent being Hanf locality and Gaifman locality. These notions are designed so that, in order to evaluate a local query in a given database, it suffices to look only at small neighbourhoods around tuples of elements that belong to the database.

In this talk I want to give a survey of how to use locality for efficient query evaluation in various computation models. In particular, we will take a closer look at how to enumerate query results with constant delay, and at how to evaluate queries in a map-reduce like setting [Neven et al., ICDT 2015] or in Pregel [Malewicz et al., SIGMOD 2010]. Also, we will have a closer look at how to transform a given local query into a form suitable for exploiting its locality.

BibTeX - Entry

@InProceedings{schweikardt:LIPIcs:2015:4998,
  author =	{Nicole Schweikardt},
  title =	{{Using Locality for Efficient Query Evaluation in Various Computation Models (Invited Talk)}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{13--14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4998},
  URN =		{urn:nbn:de:0030-drops-49987},
  doi =		{10.4230/LIPIcs.ICDT.2015.13},
  annote =	{Keywords: query evaluation, locality}
}

Keywords: query evaluation, locality
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI