Title :
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
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;
Conference_Titel :
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location :
Espoo, Finland
DOI :
10.1109/ISCAS.1988.14986
