Partial match file design in multidisk systems

Abstract

In some modern applications, the increasing usage of databases and integrated information retrieval systems has encouraged the development of file structures suited for partial match retrieval. A partial match query is a query with some number of attbutes specified and the rest of them unspecified. In partial match retrievel, the central problems are the partial match file design and the multidisk allocation. The partial match file design problem involves finding a way to arrange a given set of multiattribute records into buckets such that the average number of buckets to be examined, over all possible partial match queries, is minimized. The multidisk problem is a file allocation problem among multiple independently accessible disks so that, for all possible partial match queries, maximal disk access concurrency can be obtained. Since both problems are known to be NP-hard, many heuristic methods are proposed. Some methods are intended to utilize replication of files to obtain attractive improvements in performance. File designs for partial match queries are considered first. The objective of the first problem is to allocate query-related records in the same bucket. The file systems developed as a result of these efforts are largely based on cartesian product files, which have been shown to be very effective for partial match queries. We are concerned about the file designs based on cartesian product files with the use of replication to improve average performances. Our contribution is to give a method of fold tries, which uses trie structure to map partial match queries onto fold addresses. Two fold design is considered first and then a generalized design is developed. We propose a fold generation algorithm and show that optimal files can be constructed by the algorithm. The performance formula for the algorithm is derived. The results of experiments show that it is possible to improve average performances with modest redundancy. Recently, many file design sch...