Browse Prior Art Database

QUERY PROCESSING USING THE CONSECUTIVE RETRIEVAL PROPERTY

IP.com Disclosure Number: IPCOM000148491D
Original Publication Date: 1984-May-24
Included in the Prior Art Database: 2007-Mar-30
Document File: 32 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Kambayashi, Yahiko: AUTHOR [+3]

Abstract

6 Yahiko Kambayashi 6 Department of Information Science . Kyoto University Sakyo, Kyoto, Japan 2 and Sakti P. Ghosh IBM Research Laboratory San Jose, California 95 193 BOOK OR CHAPTER: This manuswant has been submrttad to a vubllshsr tor RUbllCatlOn as a book or book chaw. Rec~v~entsare advtsed :hat coples have bean dlstrlbuted at the author's rewest for the PUrDOSe 01 d~tor~alrev~aw md internal rntwrnat~on onb. Outr~butlon beyond raclpient or dupltcatlon In whole or In pat IS not authorlzad excevt by express vwrnlsslan of the author. .--- --. Research Division . ,, , , Yorktown Heights, New York San Jose, California Zurich, Switzerland RJ 4302 (47130) 5/24/84 Computer Science QUERY PROCESSING USING THE CONSECUTIVE RETRIEVAL PROPERTY Yahiko Kambayashi Department of Information Science Kyoto University Sakyo, Kyoto, Japan andSakti P. Ghosh IBM Research Laboratory San Jose, California 95 193 ABSTRACT: In this paper, we will discuss procedures to handle multiple queries utilizing the consecutive retrieval property. A set of queries is said to have the consecutive retrieval property if the records pertinent to every qiiery in the set are consecutively located in a linear structure file, so that each query can be processed by a single direct access of the file. The consecutive retrieval property can be used to reduce the computation time as well as the storage space. There are many cases when a given query set does not satisfy the property and we need to develop procedures to handle such cases. One approach is to generalize the file structure. Instead of the linear structure various graph structures can be used. Another approach is to permit multiple accesses for queries with low usage frequencies. We give a greedy algorithm . to construct a consecutive retrieval file where the preference of queries are given by the frequencies of usage. File organizations with different main memory buffer sizes are also discussed, such as the quasi-consecutive retrieval file organization and the buffer-limited quasi-consecutive retrieval file organization. In these organizations records corresponding to each query are not required to be stored consecutively; instead these records are to be located within the size of the buffer. A multiple query processing method for cost reduction by keeping some records in the buffer is also described.*Present address: Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka, Japan.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 32

RJ 4302 (47130) 5/24/84 Computer Science

Research Report

QUERY PROCESSING USING THE CONSECUTIVE RETRIEVAL PROPERTY

6 Yahiko Kambayashi

6

--

Department of Information Science

. Kyoto University
Sakyo, Kyoto, Japan

2 and

Sakti P. Ghosh

IBM Research Laboratory San Jose, California 95 193

BOOK OR CHAPTER:

This manuswant has been submrttad to a vubllshsr tor RUbllCatlOn as a book or book chaw. Rec~v~ents
are advtsed :hat coples have bean dlstrlbuted at the

author's rewest for the PUrDOSe 01 d~tor~al
rev~aw md
internal rntwrnat~on onb. Outr~butlon beyond raclpient or dupltcatlon In whole or In pat IS not

authorlzad excevt by express vwrnlsslan of the author.

.--- --.

----

--- -

- ----
- - -- - - ---

- - --- Research Division

. -

,,

,

, Yorktown Heights, New York San Jose, California Zurich, Switzerland

[This page contains 1 picture or other non-text object]

Page 2 of 32

[This page contains 1 picture or other non-text object]

Page 3 of 32

RJ 4302 (47130) 5/24/84 Computer Science

QUERY PROCESSING USING THE CONSECUTIVE RETRIEVAL PROPERTY

Yahiko Kambayashi *

+ Department of Information Science
Kyoto University

- Sakyo, Kyoto, Japan and
Sakti P. Ghosh

IBM Research Laboratory

San Jose, California 95 193

ABSTRACT: In this paper, we will discuss procedures to handle multiple queries utilizing the consecutive retrieval property. A set of queries is said to have the consecutive retrieval property if the records pertinent to every qiiery in the set are consecutively located in a linear structure file, so that each query can be processed by a single direct access of the file. The consecutive retrieval property can be used to reduce the computation time as well as the storage space. There are many cases when a given query set does not satisfy the property and we need to develop procedures to handle such cases. One approach is to generalize the file structure. Instead of the linear structure various graph structures can be used. Another approach is to permit multiple accesses for queries with low usage frequencies. We give a greedy algorithm . to construct a consecutive retrieval file where the preference of queries are given by the frequencies of usage. File organizations with different main memory buffer sizes are also discussed, such as the quasi-consecutive retrieval file organization and the buffer-limited quasi-consecutive retrieval file organization. In these organizations records corresponding to each query are not required to be stored consecutively; instead these records are to be located within the size of the buffer. A multiple query processing method for cost reduction by keeping some records in the buffer is also described.
*Present address: Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka, Japan.

[This page contains 1 picture or other non-text object]

Page 4 of 32

[This page contai...