Data structures for knowledge bases

The research which this thesis describes began as part of a long-term programme to build a deductive database management system, through a complete integration of logic programming and relational database technologies. A fundamental aspect of this integration is the large-scale storage and retrieval of generalised forms of knowledge - logical rules as well as facts. The essence of the problem is the generalisation of scaleable database storage and access techniques from the fixed structures of relational tuples to the variable structures of logical rules.Rules represent the most complex case of the generalised problem of how to index any set of arbitrary data structures which can be expressed as trees. Thus, if the indexing problem for rules can be solved, it may well also serve as the foundation for a new, generic indexing technology i.e. a technology capable of indexing instances of any and variable complex data structures. This realisation broadened the aim of our research into a quest to establish the principles of such a new technology. We recount here our search for these principles, and describe new indexing methods which we have developed along the way - notably BANG indexing, and a powerful new spatial indexing method based on a dual representation of points and spatial extents in a modified BANG index structure.The attempt to develop a generalised discriminator for instances of variable complex structure leads quickly to a recognition that the key to the new technology lies in recursive multi-dimensional indexing. The major theme of this research is therefore the development of a performant and predictable multi-dimensional indexing technique in the form which is extendible to the nested case. This proves to be the central problem, which is itself found to be inescapably dependent on a solution of the long-outstanding n-dimensional B-tree problem - which has been described as "one of the persistent puzzles of computer science." We present a solution of the problem in this thesis.