How to stay CALM while seeing what is not there
Bas Ketsman · 2014
The CALM1-conjecture, first stated by Hellerstein in his keynote speech at PODS 2010 and proved in its revised form by Ameloot et al. [2] 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. However, if computing nodes can deduce information about missing data (i.e., they can see what is not there), Zinn et al. [3] showed that some nonmonotonic queries become computable in a coordination-free way as well. Hence, contradicting the CALM-conjecture in its original form. This talk will cover two revisions of the CALM-conjecture [1] that complete the story, by showing that even for the later settings, the inherent nature of the CALM-conjecture remains valid. In particular, it is showed that queries computing in a coordination-free way within these settings relate to increasingly weaker notions of monotonicity. If time allows, we will also cover the relation of the above implied query classes with variants of Datalog; thus, providing an effective syntax for these otherwise undecidable classes.