Unique key Horn functions (Q2672584)

The concept of Horn functions has been widely investigated under different guises such as directed hypergraphs in graph theory and combinatorics [\textit{G. Ausiello} et al., SIAM J. Comput. 15, 418--431 (1986; Zbl 0602.68056); CISM Courses Lect. 284, 125--157 (1984; Zbl 0571.68087)], as implication systems in machine learning [\textit{M. Arias} and \textit{J. L. Balcázar}, Mach. Learn. 85, No. 3, 273--297 (2011; Zbl 1237.68106); Lect. Notes Comput. Sci. 5809, 156--170 (2009; Zbl 1262.68059)], database theory [\textit{W. W. Armstrong}, in: Information processing 74. Proceedings of IFIP congress 74. Amsterdam etc.: North-Holland Publishing Company; New York: American Elsevier Publishing Company. 580--583 (1974; Zbl 0296.68038); \textit{D. Maier}, J. Assoc. Comput. Mach. 27, 664--674 (1980; Zbl 0466.68085)], where the set of all functional dependencies defines a unique pure Horn function associated to the given database, and as lattices and closure systems in algebra and concept lattice analysis [\textit{N. Caspard} and \textit{B. Monjardet}, Discrete Appl. Math. 127, No. 2, 241--269 (2003; Zbl 1026.06008); \textit{J. L. Guigues} and \textit{V. Duquenne}, Math. Sci. Hum. 95, 5--18 (1986; Zbl 1504.68217)]. Horn functions form a fundamental subclass of Boolean functions endowed with interesting structural and computational properties. The satisfiability problem can be solved in linear time, while the equivalence of such formulas can be decided in polynomial time [\textit{W. F. Dowling} and \textit{J. H. Gallier}, J. Log. Program. 1, 267--284 (1984; Zbl 0593.68062)]. A \textit{key} in a relational database is a set of attributes whose values determine uniquely the values of all other attributes. A pure Horn function is called \textit{key Horn} if the body of any of its implicates is a key of the function. Key Horn functions are a generalization of \textit{hydra functions} introduced in [\textit{R. H. Sloan} et al., Theor. Comput. Sci. 658, Part B, 417--428 (2017; Zbl 1357.68151)], where a \(2\)-approximation algorithm was given, while the minimization remains NP-hard even in this special case [\textit{P. Kučera}, Theor. Comput. Sci. 658, Part B, 399--416 (2017; Zbl 1357.68150)]. Finding a shortest conjunctive normal form of a given Horn function with respect to multiple relevant measures (number of clauses, number of literals, etc.) is computationally hard. The authors provided logarithmic factor approximation algorithms for general key Horn functions with respect to the above-mentioned measures in [SIAM J. Comput. 51, No. 1, 116--138 (2022; Zbl 1504.68052)]. This paper is concerned with the structure of the keys of a pure Horn function, being in particular interested in finding Sperner hypergraphs \(\mathcal{B}\) that form the set of minimal keys of a pure Horn function, where \(\mathcal{B}\) is called a \textit{unique key hypergraph}, while the corresponding Horn function \(h_{\mathcal{B}}\) is called a \textit{unique key Horn function}. The synopsis of the paper goes as follows. \begin{itemize} \item[\S 2] is concerned with definitions and notations. \item[\S 3] gives a characterization of unique key hypergraphs and unique key Horn functions, showing particularly that cuts of a matroid form a unique key hypergraph. \item[\S 4] addresses the special case when every hyperedge has size two, showing that recognizing unique key graphs is co-NP-complete. Subsequently, several classes of graphs for which the recognition problem is to be decided in polynomial time are identified. \item[\S 5] provides an algorithm generating all minimal keys of a pure Horn function with polynomial delays, which is to be used to generate all candidate keys of a relation, improving results in [\textit{C. L. Lucchesi} and \textit{S. L. Osborn}, J. Comput. Syst. Sci. 17, 270--279 (1978; Zbl 0395.68025); \textit{M. Hermann} and \textit{B. Sertkaya}, Lect. Notes Comput. Sci. 4933, 158--168 (2008; Zbl 1131.68537)]. Furthermore, it is shown that the problem of finding a minimum key of a pure Horn function and that of finding a minimum target set of a graph are closely related. The algorithm can be used to generate all minimal target sets with polynomial delay provided that the thresholds are bounded by a constant. \end{itemize}