article

Free access

Query optimization in star computer networks

Editor: Robert W. Taylor Authors:

Larry Kerschberg,

S. Bing YaoAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 7, Issue 4

Pages 678 - 711

https://doi.org/10.1145/319758.319778

Published: 01 December 1982 Publication History

Abstract

Query processing is investigated for relational databases distributed over several computers organized in a star network. Minimal response-time processing strategies are presented for queries involving the select, project, and join commands. These strategies depend on system parameters such as communication costs and different machine processing speeds; database parameters such as relation cardinality and file size; and query parameters such as estimates of the size and number of tuples in the result relation. The optimal strategies specify relation preparation processes, the shipping strategy, serial or parallel processing, and, where applicable, the site of join filtering and merging. Strategies for optimizing select and join queries have been implemented and tested.

References

[1]

ASTRAHAN, M.M., AND CHAMBERLIN, D.D. Implementation of a structured English query language. Comrnun. ACM 18, 10 (Oct. 1975), 580-588.

Digital Library

[2]

BERNSTEIN, P. A., AND CHIU, D.W. Using semi-joins to solve relational queries. Tech. Rep. 7901-7901, Computer Corporation of America, Boston, 1979.

[3]

CHAN, A., AND NIAMIR, B. On estimating the cost of accessing records in blocked database organizations. Comput. J., to be published.

[4]

CODD, E.F. A relational model of data for large shared data banks. Commun. ACM 13, 6 (June 1970), 377-387.

Digital Library

[5]

EPSTEIN, R., STONEBRAKER, M., AND WONG, E. Distributed query processing in a relational data base system. Memor. UCB/ERL M78/18, Electronics Research Lab., Univ. of California, Berkeley, April 1978.

[6]

SELINGER, P. (}., ASTRAHAN, M.M., CHAMBERLIN, D.D., LORIE, I:{.A., AND PRICE, T.G. Access path selection in a relational database management system. ACM-SIGMOD Int. Conf. Management of Data (Boston, May 30-June 1), ACM, New York, 1979, pp. 23-34.

Digital Library

[7]

HEVNER, R., AND YAO, S.B. Query processing on a distributed database. In Proc. 1978 Berkeley Workshop on Distributed Data Management and Computer Networks (Aug. 1978), NTIS, Washington, D.C.

[8]

HEVNER, R., AND YAO, S.B. Query processing in distributed database systems. IEEE Trans. Soflw. Eng. SE-5, 3 (May 1979).

[9]

KERNIGHAN, B.W., AND RITCHIE, D.M. The C Programming Language. Prentice-Hall, Englewood Cliffs, N.J., 1975.

Digital Library

[10]

KLEINROCK, L. Queueing Systems, vol. 1: Theory. Wiley, New York, 1975.

Digital Library

[11]

KSUTH, D.E. The Art of Computer Programming, vol. 3. Addison-Wesley, Reading, Mass., 1973, pp. 396-398.

Digital Library

[12]

MERRETT, W., AND OTOO, E. Distribution models of relations. In Proc. 5th Int. Conf. Very Large Data Bases (Rio de Janeiro, Oct. 3-5), ACM, New York, 1979, pp. 418-425.

[13]

NIAMIR, B. Attribute partitioning in a self-adaptive relational database system. Tech. Rep. MIT/LCS/TR-192, and AD-A053292, M.I.T., Cambridge, Mass., 1978.

Digital Library

[14]

OZKARAHAN, E.A., SCHUSTER, S.A., AND SEVCIK, K.C. Performance evaluation of a relational associative processor. ACM Trans. Database Syst. 2, 2 (June 1977), 175-195.

Digital Library

[15]

TING, P.D., AND TSICHRITZIS, D.C. A Micro-DBMS for a distributed data base. In Proc. 4th Int. Conf. Very Large Data Bases (West Berlin, Sept. 13-15), ACM, New York, 1978, pp. 200-206.

[16]

TONG, E. Retrieving dispersed data from SDD-I: A system for distributed databases. In Proc. 1977 Berkeley Workshop on Distributed Data Management and Computer Networks (May 1977}, NTIS, Washington, D.C.

[17]

YAO, S.B. Approximating block accesses in database organizations. Commun. ACM 20, 4 (April 1977), 260-261.

Digital Library

[18]

YAO, S.B. On block accesses in database organizations. Commun. ACM 20, 8 (Aug. 1977), 609.

Digital Library

[19]

YAO, S.B. Optimization of query evaluation algorithms. ACM Trans. Database Syst. 4, 2 (June 1979}, 133-155.

Digital Library

Cited By

Yazdi SSavari SKramer G(2011)Network Coding in Node-Constrained Line and Star NetworksIEEE Transactions on Information Theory10.1109/TIT.2011.214645057:7(4452-4468)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1109/TIT.2011.2146450
Sadegh SYazdi TSavari SKramer G(2008)Network coding in star networks2008 IEEE International Symposium on Information Theory10.1109/ISIT.2008.4595001(325-329)Online publication date: Jul-2008
https://doi.org/10.1109/ISIT.2008.4595001
Kerschberg LWaisanen A(2005)A cooperative approach to query processing: Integrating historical, structural, and behavioral knowledge sourcesArtificial Intelligence and Symbolic Mathematical Computing10.1007/3-540-57322-4_15(214-223)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57322-4_15
Show More Cited By

Index Terms

Recommendations

Query Optimization for Ontology-Mediated Query Answering
WWW '24: Proceedings of the ACM Web Conference 2024

Ontology-mediated query answering (OMQA) consists in asking database queries on knowledge bases (KBs); a KB is a set of facts called the KB's database, which is described by domain knowledge called the KB's ontology. A widely-investigated OMQA technique ...
Optimizing large star-schema queries with snowflakes via heuristic-based query rewriting
CASCON '03: Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research

User queries have been becoming increasingly complex (e.g., involving a large number of joins) as database technology is applied to some application domains such as data warehouses and life sciences. Query optimizers in existing database management ...
An Optimal Algorithm for Processing Distributed Star Queries

The problem of optimal query processing in distributed database systems was shown to be NP-hard. However, for a special type of queries called star queries, we have developed a polynomial optimal algorithm. Semijoin tactics are applied for query ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 7, Issue 4

Dec. 1982

203 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/319758

Editor:
Robert W. Taylor
IBM Research Lab, San Jose, CA

Issue’s Table of Contents

Copyright © 1982 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1982

Published in TODS Volume 7, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
578
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)12

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yazdi SSavari SKramer G(2011)Network Coding in Node-Constrained Line and Star NetworksIEEE Transactions on Information Theory10.1109/TIT.2011.214645057:7(4452-4468)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1109/TIT.2011.2146450
Sadegh SYazdi TSavari SKramer G(2008)Network coding in star networks2008 IEEE International Symposium on Information Theory10.1109/ISIT.2008.4595001(325-329)Online publication date: Jul-2008
https://doi.org/10.1109/ISIT.2008.4595001
Kerschberg LWaisanen A(2005)A cooperative approach to query processing: Integrating historical, structural, and behavioral knowledge sourcesArtificial Intelligence and Symbolic Mathematical Computing10.1007/3-540-57322-4_15(214-223)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57322-4_15
Willard D(2005)Sampling algorithms for differential batch retrieval problems (extended abstract)Automata, Languages and Programming10.1007/3-540-13345-3_48(514-526)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-13345-3_48
Stocker KKossmann DBraumandi RKemper A(2001)Integrating semi-join-reducers into state-of-the-art query processorsProceedings 17th International Conference on Data Engineering10.1109/ICDE.2001.914872(575-584)Online publication date: 2001
https://doi.org/10.1109/ICDE.2001.914872
Bandyopadhyay SSengupta AUrban J(2000)A robust protocol for parallel join operation in distributed data basesProceedings of the first international symposium on Databases in parallel and distributed systems10.5555/62597.62610(97-106)Online publication date: 1-Jan-2000
https://dl.acm.org/doi/10.5555/62597.62610
Claussen JKemper AMoerkotte GPeithner KSteinbrunn M(2000)Optimization and Evaluation of Disjunctive QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/69.84226512:2(238-260)Online publication date: 1-Mar-2000
https://dl.acm.org/doi/10.1109/69.842265
Yu MSheu P(1997)Adaptive Join Algorithms in Dynamic Distributed DatabasesDistributed and Parallel Databases10.1023/A:10086197050795:1(5-30)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.1023/A%3A1008619705079
Steinbrunn MPeithner KMoerkotte GKemper A(1995)Bypassing Joins in Disjunctive QueriesProceedings of the 21th International Conference on Very Large Data Bases10.5555/645921.673167(228-238)Online publication date: 11-Sep-1995
https://dl.acm.org/doi/10.5555/645921.673167
Ciaccia PMaio D(1995)Domains and Active DomainsIEEE Transactions on Knowledge and Data Engineering10.1109/69.4040357:4(641-655)Online publication date: 1-Aug-1995
https://dl.acm.org/doi/10.1109/69.404035
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents