# “Functional dependencies” with cardinality constraints

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?

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