5
$\begingroup$

Let us write $\{ A_1, \ldots, A_k\} \rightrightarrows^n \{B_1, \ldots, B_m\}$ for a relation $R$ if for all $\langle a_1, \ldots, a_k\rangle$ we have $\left\lvert \pi_{B_1, \ldots, B_m} \sigma_{\bigwedge_{i = 1}^k A_i = a_i} R\right\rvert \le n$ (and $A_i$, $B_j$ are attributes from the schema of $R$), i.e, for any choice of values for the attributes $A_i$ at most $n$ corresponding tuples of values for $B_j$ can be found in $R$. Then $\{A_1, \ldots, A_k\} \rightrightarrows^1 \{B_1, \ldots, B_m\}$ is just the functional dependency $\{A_1, \ldots, A_k\} \rightarrow \{B_1, \ldots, B_m\}$, and $\emptyset \rightrightarrows^n \{B_1, \ldots, B_m\}$ is an upper bound on the number of possible $B_j$-tuples occurring in $R$ (regardless of any selection).

One may come up with a bunch of possible inference rules similar to Armstrong's axioms, for example

  • reflexivity: $\mathcal{A}' \subseteq \mathcal{A} \implies \mathcal{A} \rightrightarrows^1 \mathcal{A}'$,
  • augmentation: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \implies \mathcal{A} \cup \mathcal{C} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C}$,
  • transitivity: $\mathcal{A} \rightrightarrows^{n_1} \mathcal{B}$, $\mathcal{B} \rightrightarrows^{n_2} \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n_1 n_2} \mathcal{C}$,
  • decomposition: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n} \mathcal{B}$, $\mathcal{A} \rightrightarrows^{n} \mathcal{C}$,
  • composition: $\mathcal{A}_1 \rightrightarrows^{n_1} \mathcal{B}_1$, $\mathcal{A}_2 \rightrightarrows^{n_2} \mathcal{B}_2 \implies \mathcal{A}_1 \cup \mathcal{A}_2 \rightrightarrows^{n_1 n_2} \mathcal{B}_1 \cup \mathcal{B}_2$.

Indeed, by setting $n = n_1 = n_2 = 1$, we obtain Armstrong's axioms.

Let $\Sigma = \{\mathcal{A}_i \rightrightarrows^{n_i} \mathcal{B}_i\}_{i = 1}^N$ be a set of such "cardinality constraints". Again following the conventions from functional dependencies, let us write $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$ if $\mathcal{A} \rightrightarrows^n \mathcal{B}$ holds in every relation $R$ where all constraints in $\Sigma$ hold. Let $\min_\Sigma(\mathcal{A}, \mathcal{B})$ be the smallest $n$ such that we have $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$. How can we compute (or bound) $\min_\Sigma(\mathcal{A}, \mathcal{B})$? Is there a way to minimize $\Sigma$ and obtain (the smallest) $\Gamma$ such that $\min_\Gamma(\mathcal{A}, \mathcal{B}) = \min_\Sigma(\mathcal{A}, \mathcal{B})$ for all sets of attributes $\mathcal{A}$, $\mathcal{B}$?

I'd be interested in references or algorithms regarding the constraints defined above. Have they been studied? What is the standard terminology or notation?

$\endgroup$
2
$\begingroup$

After searching around for paper some more (unfortunately, I found nothing in Ling Liu, M. Tamer Özsu eds. Encyclopedia of Database Systems), I managed to find out that these dependencies are called numerical dependencies. In particular, standard notation for my $\mathcal{A} \rightrightarrows^k \mathcal{B}$ is $\mathcal{A} \xrightarrow{k} \mathcal{B}$, which is also referred to as a $k$-dependency.

Unfortunately, they are not finitely axiomatizable:

John Grant and Jack Minker (1985). Normalization and axiomatization for numerical dependencies. In: Inf. Control 65(1), pp. 1-17. https://doi.org/10.1016/S0019-9958(85)80017-6

The entailment problem is in EXPSPACE. However, there is a sound branch-and-bound algorithm that may be used:

Paolo Ciaccia, Matteo Golfarelli and Stefano Rizzi (2013). Efficient derivation of numerical dependencies. In: Inf. Syst. 38(3) pp. 410-429. https://doi.org/10.1016/j.is.2012.07.007

A general survey of the generalization of functional dependencies is

Loredana Caruccio, Vincenzo Deufemia and Giuseppe Polese (2016). Relaxed Functional Dependencies—A Survey of Approaches. In: IEEE Tran. Knowl. Data Eng. 28(1) pp. 147-165. https://doi.org/10.1109/TKDE.2015.2472010

An extension of numerical dependencies is $\mathit{CFD}^c$, conditional functional dependencies with cardinality constraints. This paper defines them, and gives some algorithms for satisfiability and entailment:

Wenguang Chen, Wenfei Fan and Shuai Ma (2009). Incorporating cardinality constraints and synonym rules into conditional functional dependencies. In: Inf. Process. Lett. 109(14) pp. 783-789. https://doi.org/10.1016/j.ipl.2009.03.021

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.