The joy of implications, aka pure Horn functions: mainly a survey <s> 4.5.3 <s> Table of Contents * Introduction * An Overview of Database Design * The Entity-Relationship Model * The Relational Model * Object-Oriented Data Models * Design Principles * Integrity Constraints and Dependencies * Properties of Relational Schemas * Axiomatizations for Dependencies * Algorithms for Design Problems * Mappings between ER-Diagrams and Relational Database Schemas * Schema Transformations * Efficient Algorithms for Design Problems * Use of Example Databases in Design * Dependency Inference <s> BIB001 </s> The joy of implications, aka pure Horn functions: mainly a survey <s> 4.5.3 <s> Recently concept lattices became widely used tools for intelligent data analysis. In this paper, several algorithms that generate the set of all formal concepts and diagram graphs of concept lattices are considered. Some modifications of wellknown algorithms are proposed. Algorithmic complexity of the algorithms is studied both theoretically (in the worst case) and experimentally. Conditions of preferable use of some algorithms are given in terms of density/sparseness of underlying formal contexts. Principles of comparing practical performance of algorithms are discussed. <s> BIB002
An analogue of the Guigues-Duquenne base (3.2) is introduced in [AB] for general Horn functions h. It is shown that a well known query leraning algorithm of Angluin et al. in fact always produces this base, independently of the counterexamples it receives. 5 Omitted proofs and various expansions Expansion 1. We note that F c as defined in (3) is a closure system even when c is not idempotent. See [W7, Expansion 1] for details. Expansion 2. As to the algorithmic complexity of calculating c(Σ, S), let us merely look at the partial problem of calculating S from S. If |E| = m then it costs time O(m) to check whether or not A i ⊆ E for some fixed index i. Thus for Σ as in (5) it costs O(nm) to get S from S in the "naive way" suggested by definition (6). If we think of the premises A i as the rows of a n × m matrix M with entries 0 and 1, then the naive way amounts to process M row-wise. It isn't hard to see [W1, p.114 ] how a column-wise processing of M also yields S . The theoretic cost is the same, i.e. O(mn) = O(nm), but in practise the column-wise way is the better the larger n/m. For instance, it takes more time to process a million sets of cardinality 100 (since they need to be "fetched" individually) than to process only 100 sets albeit each of cardinality a million. This trick, known as vertical layout in the Frequent Set Mining community (also observed in [W1] ), often works when many but small sets need to be manipulated. In the Relational Database community the algorithm LinClosure BIB001 to calculate c(Σ, S) has become the standard. Whether LinClosure or vertical layout or something else is best, depends on the shape of Σ and a smart implementation of vertical layout. Expansion 3. Recall from Boolean logic (or other logic frameworks) that a formula ψ is a "consequence" of a formula φ (written φ ψ) if every "structure" that satisfies φ also satisfies ψ. This is the semantic level. It contrasts with the syntactic level where a formula ψ is "derivable" from a formula φ (written φ ψ) if ψ can be obtained from φ with certain "inference rules" in a step-by-step manner. Two pages of details can be found in  Expansion 3] . One benefit of NextClosure is that it doesn't matter in which way the closure operator c is provided. Thus c could be given as c(U ) = {S ∈ H : S ⊇ U } where H is a ∩-generating set of F (first way), or c(U ) = c(Σ, U ) where Σ is an implication base (second way), or any other way. In fact c itself can be a certain selfmap of P(E) more general than a closure operator, see [GR] . As to the first way, apart from NextClosure and Dowling's algorithm (2.1.1), many other methods to construct F(H) from H are evaluated in BIB002 . As to the second way, it usually cannot compete with the compressed calculation of F(Σ) in Section 4.4. However, the issue (3.6.3) is often how to find an implication base Σ of F in the first place. Another popular application of NextClosure is attribute exploration  p.85] . This particular kind of Query Learning strives to compute the canonical base Σ GD of some hidden closure system F. Unfortunately, as a not always welcome side product, the whole of F gets calculated one by one along the way. Impressive strides to avoid this succeed for the kind of "modern" attribute exploration proposed in [RDB] and  . Expansion 5 A non-independent set is dependent, and minimal dependent sets are circuits. This terminology [W3] is motivated by the established use of "circuit" for matroids (4.1.4) and convex geometries (4.1.5). Let now K be a circuit of c. Since K is dependent there is at least one e ∈ K with e ∈ c(K\{e}). The minimality of K implies that U := K\{e} is a stem with root e. Thus if roots(K) := {e ∈ K : e ∈ c(K\{e}) }, then |roots(K)| ≥ 1 and each e ∈ roots(K) induces a root-stem-partition K = {e} ∪ U . Observe that an arbitrary root e with stem U need not yield a circuit K = U ∪ {e}. For instance, let c be the closure operator induced by the implications {1, 2} → {3} and {3} → {2}. Then {1, 2} is a stem for the root 3 but {1, 2, 3} is no circuit because it contains the proper dependent subset {2, 3}. Open Problem 2: Develop a theory for those closure operators (e.g. their optimum bases), for which each root-stem-partition U ∪ {e} is a circuit. Most prominently, matroids and convex geometries belong to this class of closure operators. In the first case each circuit K has roots(K) = K, in the second case |roots(K)| = 1. Expansion 6 It is easy to see that neither a properly quasiclosed set Q needs to contain a θ-equivalent stem X, nor is a stem X necessarily contained in a θ-equivalent proper quasiclosed set. Nevertheless, those stems X that coincide with a properly quasiclosed set can be characterized neatly. For starters, since each stem X is independent and a proper subset of an independent set has a strictly smaller closure, we see that: (37) Each stem which is properly quasiclosed is in fact pseudoclosed. This raises the problem to grasp the "pcst-sets" which by definition are pseudoclosed and a stem (i.e. belong to Σ GD and Σ cd ). If P is pseudoclosed then one can decide whether P is pcst as follows: For all e ∈ c(P )\P check whether P is minimal with the property that e ∈ c (P ) . No better description of the pcst-sets within the family of all pseudoclosed sets seems to be known. In contrast, the pcst-sets look neat within the family of all stems: Theorem 7: For each stem X of a closure operator c : P(E) → P(E) the following properties are equivalent: (ii) X is inclusion-minimal among all stems of c. (iii) X is a strong stem in the sense that roots(X) = c(X)\X. Proof of Theorem 7. As to (i) ⇔ (ii), we show that ¬(i) ⇔ ¬(ii), i.e. that