Information retrieval in files described using sets
James W. Welch, J. Wesley Graham · 1975
A number of file structures (e.g., inverted files and multilist files) can be modelled as a collection of records whose contents are described using sets. With each of these sets is associated a definition which is stated as a Boolean expression of attributes. The contents of a set logically consist of all records in the file for which the associated definition is true. A common application is to determine all records in the file which satisfy a given query (stated as a Boolean expression of attributes).We consider this retrieval problem in a general manner. A method is developed whereby the descriptive sets are combined, using the conventional set-theoretic operations, to obtain a superset of the required collection of records. This superset can be shown to minimal, with regard to the given query and the given collection of descriptive sets. For an arbitrary query, some of the descriptive sets may be irrelevant and can be ignored when constructing this superset. We present a method whereby the descriptive sets can be partitioned into classes and we show how some of these partitions need not be considered when constructing the superset.A general model of the file structure, called Set-Theoretical Descriptive Storage (SeTDS), is formulated and used to analyze the retrieval problem. The minimal superset, obtained in the basic construction, may not be the best superset to process in order to determine the exact collection of records (complementation, for example, may be a prohibitively expensive operation). Because of these considerations we present a number of methods to construct supersets which are constrained in different ways (e.g., complementation of sets is not allowed).