Document Server@UHasselt >
Research >
Research publications >

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

Title: Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data
Authors: Ketsman, Bas
Neven, Frank
Issue Date: 2017
Citation: THEORY OF COMPUTING SYSTEMS, 61 (1), p. 233-260
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.
Notes: Ketsman, B (reprint author), Hasselt Univ, Hasselt, Belgium. bas.ketsman@uhasselt.be; frank.neven@uhasselt.be
URI: http://hdl.handle.net/1942/23138
DOI: 10.1007/s00224-016-9719-8
ISI #: 000402462000007
ISSN: 1432-4350
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version582.57 kBAdobe PDF
Peer-reviewed author version903.03 kBAdobe PDF

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