ACM Transactions on Database Systems · 2015 · 13 citations · 34 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationNatural Language ProcessingDirected Acyclic GraphsQuery ProcessingRelational AlgebraData Distribution StrategiesDatalog
The CALM-conjecture, first stated by Hellerstein [2010] and proved in its revised form by Ameloot et al. [2013] within the framework of relational transducer networks, asserts that a query has a coordination-free execution strategy if and only if the query is monotone. Zinn et al. [2012] extended the framework of relational transducer networks to allow for specific data distribution strategies and showed that the nonmonotone win-move query is coordination-free for domain-guided data distributions. In this article, we extend the story by equating increasingly larger classes of coordination-free computations with increasingly weaker forms of monotonicity and present explicit Datalog variants that capture each of these classes. One such fragment is based on stratified Datalog where rules are required to be connected with the exception of the last stratum. In addition, we characterize coordination-freeness as those computations that do not require knowledge about all other nodes in the network, and therefore, can not globally coordinate. The results in this article can be interpreted as a more fine-grained answer to the CALM-conjecture.
34
Optimizing joins in a map-reduce environment
Foto Afrati, Jeffrey D. Ullman · 2010 · 331 citations · Full text
Boon Thau Loo, Tyson Condie, Minos Garofalakis et al. · 2006 · 267 citations
Consistency Analysis in Bloom: a CALM and Collected Approach
Peter Alvaro, Neil Conway, Joseph M. Hellerstein et al. · 2011 · 157 citations
ILOG: declarative creation and manipulation of object identifiers
Richard Hull, Masatoshi Yoshikawa · 1990 · 155 citations
Communication steps for parallel query processing
Paul Beame, Paraschos Koutris, Dan Suciu · 2013 · 153 citations