Fix a positive integer n and consider the bipartite graph whose vertices are the 3-element subsets and the 2-element subsets of [ n ] = { 1 , 2 , … , n } , and there is an edge between A and B if A ⊂ B . We prove that the domination number of this graph is n 2 − ⌊ ( n + 1 ) 2 8 ⌋ , we characterize the dominating sets of minimum size, and we observe that the minimum size dominating set can be chosen as an independent set. This is an exact version of an asymptotic result by Balogh, Katona, Linz and Tuza (2021). For the corresponding bipartite graph between the ( k + 1 ) -element subsets and the k -element subsets of [ n ] ( k ⩾ 3 ), we provide a new construction for small independent dominating sets. This improves on a construction by Gerbner, Kezegh, Lemons, Palmer, Pálvölgyi and Patkós (2012), who studied these independent dominating sets under the name saturating flat antichains.

Embedded uniqueness constraints represent unique column combinations embedded in complete fragments of incomplete data. In contrast to SQL UNIQUE constraints, they offer a principled separation of completeness and uniqueness requirements and are capable of exploiting more resource-conscious index structures. The latter help relational database systems to be more efficient in enforcing entity and referential integrity, and in evaluating common types of queries.

Data profiling is an enabler for efficient data management and effective analytics. The discovery of data dependencies is at the core of data profiling. We conduct the first study on the discovery of embedded uniqueness constraints (eUCs). These constraints represents unique column combinations embedded in complete fragments of incomplete data. We showcase their implementation as filtered indexes, and their application in integrity management and query optimization. We show that the decision variant of discovering a minimal eUC is NP-complete and W[2]-complete. We characterize the maximum possible solution size, and show which families of eUCs attain that size. Despite the challenges, experiments with real-world and synthetic benchmark data show that our column(row)-efficient algorithms perform well with a large number of columns(rows), and our hybrid algorithm combines ideas from both. We show how to rank eUCs to help identify relevant eUCs.

Keys allow a database management system to uniquely identify tuples in a database. Consequently, the class of keys is of great significance for almost all data processing tasks. In the relational model of data, keys have received considerable interest and are well understood. However, for efficient means of data processing most commercial relational database systems deviate from the relational model. For example, tuples may contain only partial information in the sense that they contain so-called null values to represent incomplete information. Codd's principle of entity integrity says that every tuple of every relation must not contain a null value on any attribute of the primary key. Therefore, a key over partial relations enforces both uniqueness and totality of tuples on the attributes of the key. On the basis of these two requirements, we study the resulting class of keys over relations that permit occurrences of Zaniolo's null value ‘no-information’. We show that the interaction of this class of keys is different from the interaction of the class of keys over total relations. We establish a finite ground axiomatization, and an algorithm for deciding the associated implication problem in linear time. Further, we characterize Armstrong relations for an arbitrarily given sets of keys; that is, we give a sufficient and necessary condition for a partial relation to satisfy a key precisely when it is implied by a given set of keys. We also establish an algorithm that computes an Armstrong relation for an arbitrarily given set of keys. While the problem of finding an Armstrong relation for a given key set is precisely exponential in general, our algorithm returns an Armstrong relation whose size is at most quadratic in the size of a minimal Armstrong relation. Finally, we settle various questions related to the maximal size of a family of non-redundant key sets. Our results help to bridge the gap between the existing theory of database constraints and database practice.

We present a simple proof of the result published by Karakhanyan [Doklady AN Arm. SSR, LXXIV (1982), pp. 61–65] and Riordan [SIAM J. Discrete Math., 11 (1998), pp. 110–127] concerning the vertex-isoperimetric problem on the n-dimensional torus. The proof method is a reduction of this problem to a similar problem on some $(2n)$-dimensional grid, for which a solution is known [B. Bollobás and I. Leader, J. Combin. Theory, A-56 (1991), pp. 47–62]. We also simplify and clarify the structure of the involved isoperimetric order.