Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/19791

Title: Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data
Authors: Ketsman, Bas
Neven, Frank
Issue Date: 2015
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Citation: Arenas, Marcelo; Ugarte, Martín (Ed.). 18th International Conference on Database Theory, p. 291-307
Series/Report: LIPIcs
Series/Report no.: 31
Abstract: In a distributed context where data is dispersed over many computing nodes, monotone quer- ies 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 broad- cast 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.
URI: http://hdl.handle.net/1942/19791
DOI: 10.4230/LIPIcs.ICDT.2015.291
ISBN: 978-3-939897-79-8
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A568.05 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.