"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 \vDa

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

StackExchange Computer Science Q#104181, answer score: 2