A new balanced file-organization scheme of order two for multiple-valued records is presented. This scheme is called HUBMFS 2 (Hiroshima University Balanced Multiple-valued File-organization Scheme of order two). It is assumed that records are characterized by m attributes having n possible values each, and the query set consists of queries which specify values of two attributes. It is shown that the redundancy of the bucket (the probability of storing a record in the bucket) is minimized if and only if the structure of the bucket is a partite-claw. A necessary and sufficient condition for the existence of an HUBMFS 2 , which is composed exclusively of partite-claw buckets, is given. A construction algorithm is also given. The proposed HUBMFS 2 is superior to existing BMFS 2 (Balanced Multiple-valued File-organization Schemes of order two) in that it has the least redundancy among all possible BMFS 2 's having the same parameters and that it can be constructed for a less restrictive set of parameters.

A file organization scheme in an information storage and retrieval system which will be called a generalized Hiroshima University balanced multiple-valued file organization scheme of order two (GHUBMFS2) is presented, where the information about the records is indexed by m attributes having n values. The number of buckets to be organized and the redundancy of the file are the same as those of an inverted file. The number of pointer fields to be attached to the accession number stored in a bucket is reduced to a minimum in this scheme. It can answer for all second order as well as first order queries by the access to one bucket and the traversal of its contents without any set operations.