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

Ketsman, Bas ; Neven, Frank

Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data

pdf-format:
18.pdf (0.5 MB)

Abstract

In a distributed context where data is dispersed over many computing nodes, monotone queries can be evaluated in an eventually consistent and coordination-free manner through a simple but naive broadcasting strategy which makes all data available on every computing node. In this paper, we investigate more economical broadcasting strategies for full conjunctive queries without self-joins that only transmit a part of the local data necessary to evaluate the query at hand. We consider oblivious broadcasting strategies which determine which local facts to broadcast independent of the data at other computing nodes. We introduce the notion of broadcast dependency set (BDS) as a sound and complete formalism to represent locally optimal oblivious broadcasting functions. We provide algorithms to construct a BDS for a given conjunctive query and study the complexity of various decision problems related to these algorithms.

BibTeX - Entry

@InProceedings{ketsman_et_al:LIPIcs:2015:4991,
  author =	{Bas Ketsman and Frank Neven},
  title =	{{Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{291--307},
  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/4991},
  URN =		{urn:nbn:de:0030-drops-49913},
  doi =		{10.4230/LIPIcs.ICDT.2015.291},
  annote =	{Keywords: Coordination-free evaluation, conjunctive queries, broadcasting}
}

Keywords: Coordination-free evaluation, conjunctive queries, broadcasting
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