WorksComputer Science
A Polynomial Time Approximation for the Minimization of Implication Systems and Horn CNFs
Abstract
An implication system is a collection of rules of the form B \imp H, where the set of Boolean variables is the body of the rule, while is the set of its heads. Such a rule is an aggregate representation of individual implications B\imp h, for which correspond to the clauses of an equivalent CNF representation of a Horn Boolean function. An implication system is body-minimum/clause-minimum if it has the minimum number of bodies/clauses among all logically equivalent implication systems. The corresponding minimization problems appear not only in the context of implication systems, but also as problems for closure systems, directed hypergraphs, representation of dependencies in relational databases, or in Horn CNF minimization. While body-minimization is known to be solvable in polynomial time (and there are several algorithms in the literature that solve this task), clause-minimization is known to be NP-hard. In fact, body-minimization has a particular canonical solution, called the GD-basis of the underlying Horn function that also can be computed efficiently. In this paper, we utilize a known connection between the two minimization problems stating that for every implication system there always exists a logically equivalent clause-minimum implication system which has the same bodies as its canonical GD-basis, see (B{é}rczi and B{é}rczi-Kov{á}cs, 2017), and (Adaricheva and Nation, 2014). We use this fact to design a polynomial time approximation algorithm which for any outputs a -factor approximation of the logically equivalent clause-minimum implication system on variables. This is an improvement from the best known algorithm so far that provides only an -factor approximation, see (Hammer and Kogan, 1993).
Introduction
We consider a finite set of Boolean variables that can take only values true (denoted by 1) or false (denoted by 0). For a given subset and variable , the implication is the logical expression that evaluates to 0 if and only if all variables in have a value 1 and equals 0. We can read it as the statement “if all variables in are 1, then must also be 1” and we say that it is satisfied if it takes value 1. The set is called the body of the implication, while is its head. For subsets we denote by the conjunction
and call it a rule. Note that is always true if , and hence we can assume w.l.o.g. that . To simplify our notation, we write if , and if . An implication system , where , is a collection of rules with for , where the bodies , are assumed to be pairwise distinct and each set of heads , is assumed to be nonempty and disjoint from (see e.g. [26] for more details about implication systems). A truth assignment is a satisfying assignment of if it satisfies all implications of . A Boolean function on variables from is a mapping . Clearly, every implication system represents a Boolean function on variables from where if and only if is a satisfying assignment of . Two implication systems and are equivalent, denoted by , if and only if .
For instance, given four variables we can consider the following set of implications: . This set can be written in a more concise equivalent form as an implication system
Setting variables and to 1, and and to 0 we get a satisfying assignment of , while setting , , and to 1 and to 0 is not satisfying.
Implication systems allow us to extend our knowledge about a partial satisfying assignment. For instance, assume that the variables of a subset are 1 in a satisfying assignment of the implication system , given as above. If there exists an index such that and , then we can conclude that the variables in must also be 1, and hence we can extend to . Repeating this as many times as possible, we arrive to a subset such that for all indices we have either or . Such a subset is called a closed set with respect to . The closure of an arbitrary subset is a minimal closed set with respect to that contains . Note that the closure of a set can be efficiently derived by the above simple procedure, which we call forward chaining following the standard terminology. Furthermore, the closure of a set depends only on the underlying Boolean function, in other words, if and only if for all (see e.g. [8, 20]). In the sequel we call the closure operator of . Furthermore, we denote by the family of closed sets with respect to the implication system . Note again that if and only if . Note also that closed sets are in a one-to-one correspondence with satisfying assignments. Namely, a subset is a closed set with respect to if and only if assigning 1 to variables in and 0 to variables not in is a satisfying assignment of .
By definition of the closure we have for , where some or even all of the containment relations may be strict. For instance, we can represent our small example above also as the equivalent implication system
where e.g., so the containment is strict in for the body , while it is not strict in . Furthermore, we have , while .
Let us recall that implication systems arise naturally in many different applications, and in many different contexts, resulting in different looking representations and terminology. Implication systems are used to describe the structure of relational databases [3, 8, 24], are equivalent to the family of definite Horn Boolean functions [18], and can equivalently be viewed as directed hypergraphs [6, 7]. They arise in formal concept analysis [19], in closure systems [26, 1], in machine learning [4, 5], in the theory of Boolean functions (Horn theory) [22, 25, 14, 17], etc. The family of Boolean functions that can be represented by implication systems is known as definite Horn functions (in some literature called pure Horn functions). The above cited forward chaining procedure that derives the closure of a set is known to run in polynomial time in the size of the input implication system (see e.g. [8, 20]).
Our small examples above (implication systems and ) show that a Boolean function (a closure operator) may be represented by different logically equivalent implication systems. Since the computational time of various tasks, such as computing the closure of a set or answering a query in an expert system, depends on the implication system we use as an input, it is a frequently arising and important problem to find the shortest representation of a given implication system.
Since implication systems are used in the different contexts under different formalisms (e.g. directed hyperarcs, definite horn CNFs) there are numerous natural measures of “size” of an input and hence also numerous notions of “minimality”. Six different measures and the corresponding concepts of minimality were considered for an implication system in [7, 17]:
(B) number of bodies: ,
(BA) body area: ,
(C) number of clauses: ,
(TA) total area: ,
(BC) number of bodies and clauses: , and
(L) number of literals: .
With a slight abuse of notations we shall use (B), (BA), (TA), (C), (BC) and (L) to denote both the measures and the corresponding minimization problems.
The only one of these six minimization problems for which a polynomial time procedure exists to derive a minimum representation is (B). The first such algorithm appeared in database theory literature [24]. Different algorithms for the same task were then independently discovered in hypergraph theory [7], and in the theory of closure systems [19].
For the remaining five measures it is NP-hard to find the shortest representation. There is an extensive literature on the intractability results in various contexts for these minimization problems [24, 7, 20]. It was shown that (C) and (L) stay NP-hard even when the inputs are limited to bodies of size at most two [15], and the same result extends to the remaining three measures. Note that if all bodies are of size one then the above problems become equivalent with the transitive reduction of directed graphs, which is tractable [2]. It should be noted that there exist several other tractable subclasses, see [21, 13]. For the subclass of key-Horn implication systems, it was shown that (BA) becomes tractable while the remaining four problems stay NP-hard [23] but all admit a logarithmic factor approximation [10]. There are also few older heuristic minimization approaches for (C) and (L) [12].
It was shown that (C) and (L) are not only hard to solve exactly but even hard to approximate. More precisely, [11] shows that these problems are inapproximable within a factor assuming , where denotes the number of variables. In addition, [16] shows that they are inapproximable within a factor assuming . It is not difficult to see that the same proof extends to (BC) and (TA) as well. On the positive side, (C), (BC), (BA), and (TA) admit -approximations and (L) has an -approximation [20]. To the best of our knowledge, no better approximations are known.
In this paper, we study problems (B) and (C). As already mentioned above, there are several polynomial time minimization algorithms for (B) in the literature and they can be divided into two types. The ones from database theory [24] and hypergraphs [6, 7] use a local exchange lemma to decrease the number of bodies, utilizing an equivalence relation on the set of bodies. The algorithms from the closure systems literature [19, 4, 5] perform a sequence of steps, called right-saturation, left-saturation, and redundancy elimination to transform the input into an equivalent body-minimum representation. The latter approach produces a unique implication system representing the underlying Boolean function, which is called the GD-basis of the input. This name is derived from the initial letters of the authors’ names of [19].
In this paper we provide a first non-trivial polynomial time approximation algorithm for clause-minimization (problem (C)). Our result has three main components. First, in Section 3, we recall that there always exists a solution to problem (C) that has the same bodies as the unique GD-basis (which is computable in polynomial time). This result from [1, 9] immediately implies that the GD-basis constitutes a polynomial time -factor approximation for the clause minimization problem, matching the bound from [20]. Next, in Section 4, we show that the implication subsystem corresponding to the set of bodies with the same closure can be replaced, without destroying the logical equivalence with the underlying Horn function, by any other form using the same bodies and guaranteeing the same closure for those bodies. Finally, in Section 5 we provide a constructive approach to build such a replacement of ”small” size, yielding a polynomial time approximation algorithm which for any outputs a -factor approximation for problem (C).
Preliminaries
In this section, we introduce more notation to extend the definitions from the previous section, and show complexity results for several basic problems for implication systems.
For an implication system let us denote by the set of bodies appearing in , by the size of , and by the number of individual implications (clauses) in .
An implication is a consequence of an implication system if it is satisfied by every satisfying assignment of the system. The following lemma, cited from the literature without proof, provides a condition for checking this property.
Lemma 2.1 ([20]) Let be an implication and an implication system. Then is a logical consequence of if and only if . Furthermore, the closure can be computed in time for every set .
Recall, that for a given implication system we denote by the set of its closed sets and we have exactly when .
Lemma 2.2 For two implication systems and we have if and only if for all and for all . All these conditions can be tested in time.
Proof. Recall that iff , and analogously, iff . Consequently, the first part of the statement follows by the above definitions and the definition of equivalence. The complexity claim follows by Lemma 2.1 since the above inclusions can be tested in time for every rule in and in time for every rule in .
Functional properties of implication subsystems
For an implication system and subset we say that is an implication subsystem of . We will write and . In other words, we view implication systems as sets of rules.
To an implication system and subset we associate the following implication subsystem
These subsystems have important functional properties, which we show in the following lemmas.
Lemma 3.1 If are equivalent implication systems, then for all subsets we have .
Proof. We are going to prove the claim by Lemma 2.2. Let us consider an arbitrary subset . Since in the claim the role of and are symmetric, it is enough to show that for all rules of we have . By the definition of we have implying that for all rules used in deriving we have implying . Thus we have , where the last equality follows by the equivalence of and . Consequently, all rules of used to derive are also rules of implying . Since by the choice of the rule , the claim follows.
Lemma 3.2. For two implication systems, and we have if and only if holds for all subsets .
Proof. The “if” part of the claim follows by the simple facts that and . The “only if” part follows by an analogous proof as in the previous lemma, replacing all relations in that proof by .
Lemma 3.3. For an implication system and a subset we have for all subsets .
Proof. Note that is an implication subsystem of which is an implication subsystem of , implying by the definition of the closure operator that
for all subsets . Since we also have
by the properties of a closure operator. Consequently for all implications used in deriving we have and consequently by the above relations and the properties of the closure operation we have . The nonequality follows by the definition of , implying , from which it follows that we have equality in the first inequality of (2).
Lemma 3.4. For an implication system and index we define . Then we have .
Proof. We can apply Lemma 2.2 which in this special case implies that we have if and only if . Note next that is an implication subsystem of and thus it is an implication subsystem of . Consequently, we have from which follows by the definition of .
To an implication system we associate
and call it the left-saturation of .
Corollary 3.5. For every implication system we have .
Proof. Follows by the sequential application of Lemma 3.4.
To an implication system we associate
and call it the right-saturation of .
Lemma 3.6. For every implication system we have .
Proof. Immediate by Lemma 2.2.
Let us finally associate to an implication system the implication system obtained from by eliminating the redundant rules. Let us point out that if is an irredundant implication system, then its left saturation will also be irredundant. However, it may contain rules that become redundant after right saturation. More precisely, introducing (where the second equality holds by Lemma 3.3) we may have pairs of rules in such that
In this case, rule can be replaced by rule extended with the heads of rule without losing equivalence with the underlying function. For details and a full proof we refer the reader to [24].
Theorem 3.7 ([19, 4, 5]) For an implication system the associated implication system is a unique body-minimum representation of the underlying Horn function, called its GD-basis.
Note that the GD-basis can be computed in time from any implication system representing the same underlying Horn function, see e.g., [19, 4, 5].
The next theorem plays an important role in our constructive approximation result, and thus, for completeness, we include here a short proof, which utilizes the above structural results of implications subsystems, and is slightly different from the proofs in the literature.
Proof. Let be an arbitrary clause-minimum representation of and define . Note that is an irredundant system, and thus is also irredundant (see e.g., [4, 5]). Then by Corollary 3.5 we have . Furthermore, by the definition of the left-saturation, we have . As we noted above, may contain pairs of rules as in (3). In such a case, we can replace and by which by Lemma 2.2 preserves the equivalence with the underlying function (see also [24]). Since is clause-minimum, we must have , and thus this operation does not change the number of clauses. After eliminating all such pairs, we arrive at an implication system for which we have , and , where the last equality follows by the definition of the GD basis.
Corollary 3.9 ([1, 9]) Given an implication system there exists an equivalent implication system which is both clause-minimum and body-minimum.
Proof. Follows directly by Theorem 3.8.
Decompositions and substitutions
In this section, we provide a number of results about substituting an implication subsystem by another implication system without losing equivalence with the underlying Horn function.
Lemma 4.1 Assume , and are implications systems such that . Then we have .
Proof. Follows directly from the definition of a closed set.
Lemma 4.2 Assume and . Then we have .
Proof. By Lemma 4.1 and our assumptions, we have and from which follows, proving the equivalence as claimed.
Lemma 4.2 shows that an implication subsystem can be replaced by an equivalent expression, preserving equivalence of the implication system. The next lemma shows that certain subsystems can be switched to another expression preserving equivalence of the implication system, even if the switched expressions themselves are not necessarily equivalent.
Lemma 4.3 Assume and . Then for
we have .
Proof. Let us consider . By Lemma 3.2 we have . Then we have , and thus follows by Lemma 3.1.
The next lemma proves the interesting property that a clause minimum implication system is also locally minimum for certain subsystems.
Lemma 4.4 Given an implication system , consider a clause-minimum . Then for every we have
Proof. Assume for a contradiction that there exists a such that for some . Then by Lemma 4.3 the implication system
is equivalent with and has
contradicting the clause-minimality of . This contradiction proves the first equality. The second equality follows by Lemmas 3.2 and 4.2.
Finally, the next lemma proves an exchange property which is crucial for the approximation algorithm in the next section.
Lemma 4.5. Let us consider an implication system , a body and another implication system such that and holds for every . Then
is equivalent to .
Proof. Let us note that by Lemma 3.6, and we have by Lemma 2.2. Thus
by Lemma 4.2, and therefore the claim follows by Lemma 4.3 applied to and .
Approximation for clause minimization
In this section, we present an approximation algorithm for the clause minimization problem. By Theorem 3.8 the clause minimization problem for an implication system is equivalent to finding a clause-minimum implication system, logically equivalent to , the bodies of which are the bodies of the GD-basis of . Since the GD-basis can be computed efficiently, in the rest of this section we assume that is the input to the approximation algorithm. This allows a constructive approach which iteratively replaces subsystems in a way that preserves logical equivalence of the entire implication system. In particular, Lemmas 4.3, 4.4 and 4.5 will be instrumental in our arguments.
To an implication system let us associate the family of body closures:
For we define
Using this notation, can be decomposed into subsystems
In our approximation algorithm, we apply two different constructions to replace each subsystem by another implication system such that . Let us also introduce
If is an arbitrary clause-minimum implication system of , then we have and for all by Lemma 4.4, which also justifies the last equality in the formula above.
Procedure 1
Let us assume that we focus on such a subsystem for some , as defined above. Assume that , is the family of bodies which are of course subsets of . Let for any pair of distinct indices , and define .
Our first procedure is based on the following lemma.
Lemma 5.1 .
Proof. For any , let . Note that these sets form a partition of . We then have
If is even, the right-hand side of (4) is bounded by , which implies the stated inequality.
On the other hand, if is odd, the right-hand side of (4) is bounded by , which again implies the claim.
:::
1st Approximate Clause-Minimum
Input: An implication system .
Step 1: Compute an index such that .
Step 2: Output .
Lemma 5.2 The above procedure computes in time an implication system equivalent to such that
Proof. By its definition, we have for all , consequently follows by Lemma 2.2. Furthermore, by Lemma 5.1 we have
as claimed. Note finally that , since each body of must have at least one head in every equivalent representation, implying the second inequality.
Procedure 2
Since the previous approach may not provide a good enough approximation ratio when is not large enough, we also consider another, much simpler exhaustive procedure.
2nd Approx Clause-Minimum
Input: An implication system and a constant , where we assume that .
Step 1: Search exhaustively for hypergraphs such that
Step 2: If such hypergraphs exist, choose one with the smallest and define , otherwise, define .
Step 3: Output .
Lemma 5.3 The above procedure computes in time an implication system on variables such that and
Proof. It is not difficult to see that Step 1 in the above procedure can be performed by checking many cases. In each case we need to check the stated equivalence, which is equivalent by Lemma 2.2 to check for each if the closure of by the constructed implication form is indeed . For each case this takes time. If there is a solution in Step 1, then by Lemma 4.4 we have by our assumption . On the other hand, if no solution is found in Step 1, then we have again by Lemma 4.4, and thus for the output we have , proving the claim.
Polynomial time approximation algorithm
Now we are ready to state our main approximation result for clause minimization.
Theorem 5.4 Given an implication system on variables and a constant , we can compute in polynomial time an implication system such that
Proof. Let us assume since otherwise we can compute the clause minimum form in constant time.
Assume and let be the GD-basis of . By [4, 5] it can be computed in time from .
Let us consider, as above, the closures of the bodies of the GD-basis, and define
For we compute by the first procedure and obtain by Lemma 5.2 that
For , , we apply the second procedure with to obtain for which by Lemma 5.3 we have
For such that we can choose because then we automatically have
by our assumption .
Since and we get
proving the claimed inequality.
In our computations, the dominant part is the execution of Step 1 in the second procedure, which for and requires time.
References
- [1]K. Adaricheva and J.B. Nation On implicational bases of closure systems with unique critical sets Discrete Applied Mathematics, volume 162, pages 51-69, 2014. doi.org/10.1016/j.dam.2013.08.033DOI
- [2]A.V. Aho, M.R. Garey, and J.D. Ullman The transitive reduction of a directed graph. SIAM Journal on Computing, 1:2, pages 131–137, 1972, SIAM.DOI
- [3]W. W. Armstrong. Dependency structures of database relationships. Proc. IFIP 74. North Holland, Amsterdam, 1974, pp. 580-583.
- [4]M. Arias and J.L. Balcázar. Canonical Horn representations and query learning. In Ricard Gavaldà, Gábor Lugosi, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory, volume 5809 of Lecture Notes in Computer Science, pages 156–170. Springer Berlin Heidelberg, 2009.DOI
- [5]M. Arias and J.L. Balcázar. Construction and learnability of canonical Horn formulas. Machine Learning, 85(3):273–297, 2011.DOI
- [6]G. Ausiello, A. D’Atri, and D. Sacca. Graph algorithms for functional dependency manipulation. J. Assoc. Comp. Mach., 30: 752–766, 1983.
- [7]G. Ausiello, A. D’Atri, and D. Sacca. Minimal representation of directed hypergraphs. SIAM Journal on Computing, 15(2):418–431, 1986.
- [8]C. Beeri and P.A. Bernstein. Computational problems related to the design of normal form relational schemas. ACM Trans Database Syst 4(1): 30–59, 1979.DOI
- [9]K. Bérczi and E.R. Bérczi-Kovács. Directed hypergraphs and Horn minimization. Information Processing Letters 128: 32–37, 2017.DOI
- [10]K. Bérczi, E. Boros, O. Čepek, P. Kučera, and K. Makino. Approximating minimum representations of key Horn functions, SIAM J. Comput. 51: 116–138, 2022.arxiv.org/abs/1811.05160
- [11]A. Bhattacharya, B. DasGupta, D. Mubayi, and G. Turán. On approximate Horn formula minimization. International Colloquium on Automata, Languages, and Programming (ICALP), pages 438–450, 2010, Springer.DOI
- [12]E. Boros, O. Čepek, and A. Kogan. Horn minimization by iterative decomposition. Annals of Mathematics and Artificial Intelligence, 23(3-4):321–343, 1998.
- [13]E. Boros, O. Čepek, A. Kogan, and P. Kučera. A subclass of Horn CNFs optimally compressible in polynomial time. Ann. Math. Artif. Intell., 57(3-4):249–291, 2009.DOI
- [14]E. Boros, O. Čepek, A. Kogan, and P. Kučera. Exclusive and essential sets of implicates of Boolean functions. Discrete Appl. Math., 158(2):81–96, 2010.DOI
- [15]E. Boros, O. Čepek, and P. Kučera. A decomposition method for CNF minimality proofs. Theoretical Computer Science, 510:111–126, 2013.DOI
- [16]E. Boros and A. Gruber. Hardness results for approximate pure Horn CNF formulae minimization. Annals of Mathematics and Artificial Intelligence, 71:4, pages 327–363, 2014, Springer.
- [17]Y. Crama and P.L. Hammer. Boolean Functions: Theory, Algorithms, and Applications. Cambridge (Encyclopedia of Mathematics and its Applications), 2011.
- [18]R. Fagin. Horn clauses and database dependencies. Journal of the Association for Computing Machinery, VoL 29(4), October 1982, pp 952-985.DOI
- [19]J.L. Guigues and V. Duquenne. Familles minimales d´implications informatives résultant d´ une tables de données binaires. Math. Sci. Hum., 95:5–18, 1986.
- [20]P.L. Hammer and A. Kogan. Optimal compression of propositional Horn knowledge bases: complexity and approximation. Artificial Intelligence, 64(1):131–145, 1993.DOI
- [21]P.L. Hammer and A. Kogan. Quasi-acyclic propositional Horn knowledge bases: optimal compression. Knowledge and Data Engineering, IEEE Transactions on, 7(5):751–762, Oct 1995.DOI
- [22]A. Horn. On sentences which are true of direct unions of algebras. Journal of Symbolic Logic, 16:14–21, 1951.DOI
- [23]P. Kučera. Hydras: Complexity on general graphs and a subclass of trees, Theoret. Comput. Sci., 658 (2017), pp. 399–416.DOI
- [24]D. Maier. Minimum covers in relational database model. J. ACM, 27(4):664–674, October 1980.DOI
- [25]J. McKinsey. The decision problem for some classes of sentences without classifiers. Journal of Symbolic Logic, 8:61–76, 1943.DOI
- [26]M. Wild. A theory of finite closure spaces based on implications. Advances in Mathematics, 108(1):118 – 139, 1994.DOI