A generalized database directory for nondense attributes

摘要

Inverted file directories are known to support query optimization by providing efficient data access paths for nondense attributes. This article describes a generalized index system for nondense attributes which is based on the inverted file structure while providing additional improvements and options. This generalized inverted index is more efficient and flexible than the standard inverted file. A comprehensive set of file directory construction algorithms to implement the generalized inverted index system is presented. Taken as a whole, these algorithms provide the database designer with a great deal of flexibility in optimizing overall space and time efficiency and in best handling the trade-offs involved.