Improvement Algorithms for Semijoin Query Processing Programs in Distributed Database Systems
- 1 November 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (11) , 959-967
- https://doi.org/10.1109/tc.1984.1676370
Abstract
The problem of optimal query processing in distributed database systems was shown to be NP-hard. This means that heuristic algorithms are necessary to solve the query processing problem. In this paper, we describe algorithms to improve the solutions generated by heuristics. We have identified four properties which optimal semijoin programs for processing tree queries have to satisfy. A semijoin program is represented by an execution graph which specifies the order and the identities of the semijoins to be executed. Given a semijoin program, we can therefore apply these properties to check its optimality. If it does not satisfy these optimality properties, the associated improvement algorithms can be applied to improve this program. No assumptions have been made about the relation size and the selectivity of the semijoins.Keywords
This publication has 8 references indexed in Scilit:
- Optimizing Chain Queries in a Distributed Database SystemSIAM Journal on Computing, 1984
- Optimization Algorithms for Distributed QueriesIEEE Transactions on Software Engineering, 1983
- Tree queriesACM Transactions on Database Systems, 1982
- Query processing in a system for distributed databases (SDD-1)ACM Transactions on Database Systems, 1981
- Power of Natural SemijoinsSIAM Journal on Computing, 1981
- Using Semi-Joins to Solve Relational QueriesJournal of the ACM, 1981
- Query Processing in Distributed Database SystemIEEE Transactions on Software Engineering, 1979
- A relational model of data for large shared data banksCommunications of the ACM, 1970