Boolean lattices of nested relations as a foundation for rule-based database languages

摘要

In this paper rule-based languages over partially ordered nested relations are considered. Starting with ideas of Bancilhon's and Koshafian's Object Calculus we define a class of purely lattice-based languages each of them depending on a fixed partial order. We show that for each ordering the semantics of a program can be equivalently defined by a minimal model or by a least fixpoint. Thus, our approach is semantically first order. Two well-known orderings — inclusion order and object order — and the corresponding languages are compared in detail. In order to combine the advantages of these two orderings we present a formalism to express more general orderings over so-called Generalized Partitioned Normal Form instances. Then we define the meta-concept modularization that enables us to express operations being non-monotone with respect to each of these orderings. It is comparable to stratification in other approaches, but the basic idea is different. Finally, we show how the semantics of negation can be defined in a theoretically well-founded way for partial orders corresponding to a Boolean lattice.