Publication at Faculty of Mathematics and Physics |
2022
Abstract
Horn functions form an important subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem admitting a 2log1-o(1) n inapproximability bound.
In this paper we consider the natural class of key Horn functions representing keys of relational databases. For this class, the minimization problems for most measures remain NP-hard.
In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all such measures.