scientific article; zbMATH DE number 1355186

Publication date 31 October 1999

balanced graph branching dependency closure functional dependency relational database

Extremal set theory (05D05) Database theory (68P15) Combinatorics in computer science (68R05)

This paper studies the so called \((p, q)\)-dependencies, in the context of relational databases, and their properties. Let \(R\) be a relational schema, \(A \subseteq R\), and let \(b \in R\), \(b\;(p, q)-\)depends on \(A\) in a legal relation \(r\) based on \(R\), in case there do not exist \(q+1\) tuples in \(r\), such that there are at most \(p\) distinct values for each \(a \in A\), but all the values for the attribute \(b\) are different. This notion clearly generalizes the well-known function dependency cf. [\textit{A. Silberschatz, H. Korth} and \textit{S. Sudarshan}, Database System Concepts (1997; Zbl 0910.68066)], since the latter is simply a \((1, 1)\)-dependency. Furthermore, let \(\Omega\) be the collection of attributes occurring in \(R\), an operator, \({\mathcal J}_r^{pq},\) is defined as, when applied to \(A \subseteq \Omega,\) the set of all the \(b\)'s such that \(b\;(p, q)-\)depends on \(A.\) A notion of closure operator associated with the \((p,q)\)-dependency is naturally derived, as the ``closed increasing-monotone operator on \(\Omega.\) This paper then asks the question that when such a closure operator, \({\mathcal N}\), can be \((p,q)\) represented with some relational schema, \(R,\) namely, for all \(A \subseteq \Omega,\) \({\mathcal N}(A)={\mathcal J}_r^{pq}(A).\) Building on some initial results obtained by \textit{J. Demetrovics, G. O. H. Katona} and \textit{A. Sali}, [Discrete Appl. Math. 40, 139-153 (1992; Zbl 0767.68030)], this paper presents some additional, and more complete answers to the aforementioned question in a special case when \(p=q,\) for one such closure operator, \({\mathcal C}_n^k(X),\) \(n=| \Omega| ,\) which is defined as follows: \({\mathcal C}_n^k(X) = X\) if \( | X| < k\) and \( =\Omega\) otherwise. Proofs of the results are carried out in graph theory, combinatorics. The main result of this paper can be paraphrased as follows: Let \(n(=| \Omega|) \geq k^2(k-1).\) Then \({\mathcal C}_n^k\) can be \((p,p)-\)represented when \(1 \leq p \leq k-1,\) or, for some natural number \(s,\) \(p+1- \lceil \frac{p+1}{s} \rceil = k-1.\)

Recommendations

Cited in

(13)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4269397)