  A number of extensions to the classical notion of functional dependencies
have been proposed to express and enforce application semantics. One of these
extensions is that of order dependencies (ODs), which express rules involving
order. The article entitled "Discovering Order Dependencies through Order
Compatibility" by Consonni et al., published in the EDBT conference proceedings
in March 2019, investigates the OD discovery problem. They claim to prove that
their OD discovery algorithm, OCDDISCOVER, is complete, as well as being
significantly more efficient in practice than the state-of-the-art. They
further claim that the implementation of the existing FASTOD algorithm
(ours)-we shared our code base with the authors-which they benchmark against is
flawed, as OCDDISCOVER and FASTOD report different sets of ODs over the same
data sets.
  In this rebuttal, we show that their claim of completeness is, in fact, not
true. Built upon their incorrect claim, OCDDISCOVER's pruning rules are overly
aggressive, and prune parts of the search space that contain legitimate ODs.
This is the reason their approach appears to be "faster" in practice. Finally,
we show that Consonni et al. misinterpret our set-based canonical form for ODs,
leading to an incorrect claim that our FASTOD implementation has an error.

Databases