Numerical dependencies (NDs) are a type of database constraints in which one limits the number of distinct Y-values that can appear together with any X-value, where both X and Y are sets of attributes. The seminal work by Grant and Minker has shown that NDs are not finitely axiomatizable, which has cut further investigation on this kind of constraints. In this paper we show that, given a set of sound inference rules similar to those used for functional dependencies, the membership problem for NDs is NP-hard, and propose a branch & bound algorithm for efficiently solving the problem. The algorithms adopts a suite of optimization strategies that make it applicable in practice, providing considerable speed-up over a naive approach.

Efficiently bounding cardinality ratios through database constraints

CIACCIA, PAOLO;GOLFARELLI, MATTEO;RIZZI, STEFANO
2010

Abstract

Numerical dependencies (NDs) are a type of database constraints in which one limits the number of distinct Y-values that can appear together with any X-value, where both X and Y are sets of attributes. The seminal work by Grant and Minker has shown that NDs are not finitely axiomatizable, which has cut further investigation on this kind of constraints. In this paper we show that, given a set of sound inference rules similar to those used for functional dependencies, the membership problem for NDs is NP-hard, and propose a branch & bound algorithm for efficiently solving the problem. The algorithms adopts a suite of optimization strategies that make it applicable in practice, providing considerable speed-up over a naive approach.
Atti del Diciottesimo Convegno Nazionale su Sistemi Evoluti Per Basi Di Dati
370
381
P. Ciaccia; M. Golfarelli; S. Rizzi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/96672
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact