Efficient derivation of numerical dependencies

Numerical dependencies (NDs) are database constraints that limit the number of distinct Y-values that can appear together with any X-value, where both X and Y are sets of attributes in a relation schema. While it is known that NDs are not finitely axiomatizable, there is no study on how to efficiently derive NDs using a set of sound (yet necessarily incomplete) rules. In this paper, after proving that solving the entailment problem for NDs using the chase procedure has exponential space complexity, we show that, given a set of inference rules similar to those used for functional dependencies, the membership problem for NDs is NP-hard. We then provide a graph-based characterization of NDs, which is exploited to design an efficient branch & bound algorithm for ND derivation. Our algorithm adopts several optimization strategies that provide considerable speed-up over a naïve approach, as confirmed by the results of extensive tests we made for efficiency and effectiveness using six different datasets.

► Entailment of numerical dependencies is decidable using a chase in exponential space.
► The derivation problem for numerical dependencies is NP-hard.
► The derivation rules are complete except for the value of the minimal weight.
► Numerical dependencies with minimal weight admit a graph-based representation.
► Numerical dependencies can be efficiently derived using a branch & bound algorithm.