Efficient algorithms for distributed query processing in star and extended-star networks

Author

Ozawa, Toshihiro ; Katoh, Nobuhiro

Author_Institution

Dept. of Electr. Eng., Kyoto Univ., Japan

fYear

1988

fDate

7-9 June 1988

Firstpage

551

Abstract

Scheduling algorithms for processing queries in a star or extended-star network are presented. A relational database system is assumed, and the data transmission time for joins of attributes is the dominating factor in the query processing. The first algorithm STAR-RT for minimizing the response time of a star query is based on the principle of dynamic programming. The second one, STAR-CT, is an approximation algorithm also for processing a star query, but it aims at minimization of the total communication time. Two optimization subproblems are derived in connection with the query processing and STAR-CT is based on the strategies for solving these subproblems. The above algorithms are extended to those for more general query processing.<>

Keywords

database theory; distributed databases; scheduling; STAR-CT; STAR-RT; approximation algorithm; data transmission time; distributed database systems; distributed query processing; dynamic programming; extended-star networks; optimization subproblems; relational database; scheduling algorithms; star network; Costs; Data communication; Data processing; Database systems; Delay; Dynamic programming; Intelligent networks; Query processing; Relational databases; Scheduling algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1988., IEEE International Symposium on

Conference_Location

Espoo, Finland

Type

conf

DOI

10.1109/ISCAS.1988.14986

Filename

14986