Search

The Jade file system, which provides a uniform way to name and access files in an Internet environment, is introduced. Jade is a logical system that integrates a heterogeneous collection of existing file systems in which underlying file systems support different file access protocols. Because of autonomy, Jade is designed under the restriction that the underlying file systems may not be modified. In order to avoid the complexity of maintaining an Internet-wide, global name space, Jade permits each user to define a private name space. Jade's name space supports two features: it allows multiple file systems to be mounted under one directory, and it permits one logical name space to mount other logical name spaces. A prototype of Jade has been implemented to examine and validate its design. The prototype consists of interfaces to the Unix File System, the Sun Network File System, and the File Transfer Protocol. An overview of Jade's design is reported, and the authors' experiences in designing and implementing a large scale file system are reviewed. >

The problem of multidimensional file partitioning (MDFP) arises in large databases that are subject to frequent range queries on one or more attributes. In an MDFP scheme, the search attribute space is partitioned into cells, which are mapped to physical disk locations. This mapping preserves the order of the search attribute values so that range queries can be answered most efficiently, while maintaining good performance for other types of queries. Recently, MDFP schemes have been suggested to include both dynamic and static file organizations. Optimal and heuristic MDFP algorithms are developed for the static case. The results of extensive computational experiments show that the proposed heuristics perform better than known static ones. It is also shown that incorporating a static algorithm into a dynamic MDFP such as a grid file at conversion and/or periodical reorganization points significantly improves the resulting storage utilization of the data file and decreases the size of the directory file. >

A file server is a utility provided in a computer connected via a local communications network to a number of other computer. File servers exist to preserve material for the benefit of client machines or systems. It is desirable for a file server to be able to support multiple file directory and access management systems, so that the designer of a client system retains the freedom to design the system that best suits him. For example, he may wish to use the rile server to support a predefimed directory structure or as a swapping disk. The paper explores the dedgn issues associated with such a file server and proposes some solutions.

In the past two decades, the increasing usage of databases and integrated information systems has encouraged the development of file structures suited for partial match retrieval. A partial match query is a query with some number of attributes specified and the rest of them unspecified. One interesting file structure proposed and heavily studied recently is called a multikey hashing scheme, but most of the previous results on designing optimal multikey hashing schemes ignored the record distribution of a file. In this paper we show that the problem of designing an optimal multikey hashing scheme taking into consideration the record distribution is computationally intractable (NP-hard). Therefore, a heuristic approach is necessary. In a multikey hashing scheme, although the directory is space efficient and the search algorithm is fast, due to the insufficient information in the directory some accessed buckets may not contain any record satisfying the given query. Thus, certain retrieval effort is wasted. A new class of file structures which combine a multikey hashing scheme and an indexed descriptor technique is introduced in this paper. By adding some extra information (either record descriptors or bucket descriptors) into the directory of a multikey hashing scheme, either only those buckets which contain at least one record satisfying the given query need to be accessed or the number of accessed buckets which do not contain any record satisfying the query is reduced.

This paper results from an attempt to unify several different file system design theories. We define a term "partial match pattern" and show that in order to produce file systems optimal with respect to partial match patterns, both the multikey hashing (MKH) method [16] and the multidimensional directory (MDD) method [11] must be in such a form that the number of subdivisions is the same for all domains of keys. We show the conditions for the string homomorphism hashing (SHH) method [15], the MKH method, and the MDD method to be equivalent to one another. We define the so-called Cartesian product files and show that if all records are present, the records in a Cartesian product file form a shortest spanning path in which the Hamming distance between every pair of consecutive records is 1. Thus the SHH method, the MKH method, the MDD method, and the multikey sorting (MKS) method [10] are linked together. Finally, we show that for both partial and best match queries, the file systems exhibit a common characteristic: similar records are grouped together.

In the study of data storage and retrieval involving secondary storage devices, for example, magnetic disks, a simplified model of storage that is often used is that each access takes a constant amount of time. However, if some information about the accesses is known, the model should take into consideration the inherent characteristics of the storage devices. In this paper, we assume a more refined model of storage that takes into consideration the seek time, the latency time, and the transmission time of disk accesses separately. We analyze the time required to randomly access a set of records residing on a set of consecutive cylinders on a magnetic disk a number of times, say n, for n ≥ 1. This problem may arise, for example, in the processing of queries that involve several relations in a relational database system. We also analyze the more general situations in which the n operations may represent retrievals, insertions, or deletions, or a combination of them. We assume that the dynamic file structure linear hashing is used for locating and organizing the records. A linear hashing file does not employ any directory and its primary data buckets are assumed to be contiguous, therefore the data area of a linear hashing file corresponds closely to the disk space on a set of consecutive cylinders.

A hashing-based dynamic file structure is introduced for partial match retrieval using overflow bucket sharing. The sharing of overflow buckets is dynamic in the sense that an overflow bucket is shared by a varying number of primary buckets according to the local conditions of the file. The use and sharing of overflow buckets defers splitting of the data buckets, thereby increasing the storage utilization. For the same reason, plus the fact that the sharing is dynamic, the growth of the directory is slowed down. Under the proposed organization, the records are stored more compactly in the data buckets, and for those partial match queries in which few attributes are specified, groups of neighboring directory entries have high probability of being referenced together, so that the retrieval costs for these types of partial match queries are reduced. This file organization is found to be space efficient and is also time efficient for queries in which the number of specified attributes is small.