Lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and relative complementation (BUTNOT) are becoming more and more important in programming languages supporting object inheritance. We present a general technique for the efficient implementation of such operations based on an encoding method. The effect of the encoding is to plunge the given ordering into a boolean lattice of binary words, leading to an almost constant time complexity of the lattice operations. A first method is described based on a transitive closure approach. Then a more space-efficient method minimizing code-word length is described. Finally a powerful grouping technique called modulation is presented, which drastically reduces code space while keeping all three lattice operations highly efficient. This technique takes into account idiosyncrasies of the topology of the poset being encoded that are quite likely to occur in practice. All methods are formally justified. We see this work as an original contribution towards using semantic (vz., in this case, taxonomic) information in the engineering pragmatics of storage and retrieval of (vz., partially or quasi-ordered) information.

This report discusses the implementation of a knowledge base for a library information system. It is done using a typed logic programming language—LOGIN—where type inheritance is built in. The knowledge base is structured in a hierarchical taxonomy of library object classes where each class is represented in a FRAME style knowledge structure and inherits the properties of its parents, and where infrastructural inference rules have been established through typed Horn clauses. Also in this document, some programming techniques aimed at using the power of inheritance as taxonomic inference are discussed.

An elaboration of the Prolog language is described in which the notion of first-order term is replaced by a more general one. This extended form of terms allows the integration of inheritance---an IS-A taxonomy---directly into the unification process rather than indirectly through the resolution-based inference mechanism of Prolog. This results in more efficient computations and enhanced language expressiveness. The language thus obtained, called LOGIN, subsumes Prolog, in the sense that conventional Prolog programs are equally well executed by LOGIN.