Optimal implicational bases for finite modular lattices

Abstract

Each finite closure system, whence each finite lattice, can be described in terms of “implicational bases” (called “covers of functional dependencies” in relational database theory). Although a NP - complete problem in general, it turns out that for modular lattices an optimal implicational base can be computed in polynomial time.

Keywords: modular lattices, NP-complete, relational databases, functional dependencies

Quaestiones Mathematicae 23(2000), 153–161