Distributed database system technology is one of the major developments in information
technology area. It will continue to have a very significant impact on data processing in the upcoming years
because distributed database systems have many potential advantages over centralized systems for
geographically distributed organizations. The continuing interest in distributed database systems in the
research community and the marketplace and the introduction of many commercial products indicate that
distributed database systems will play a more important role in data processing and eventually will replace
centralized systems as the major database technology in the future. The availability of high speed
communication networks and, especially, the phenomenal popularity of the Internet and the intranets will
undoubtedly speed up the transition process. Some challenging problems must be solved before the full
potential benefits of distributed database technology can be realized. Among them is query processing
(including query optimization), one of the most important issues in distributed database system design. The
query optimization problem in large-scale distributed databases is NP-hard in nature and difficult to solve. In
this study, the query optimization problem is reduced to a join ordering problem similar to a variant of
traveling salesman problem. We explored several heuristics and a genetic algorithm for solving the join
ordering problem. Some computational experiments on these algorithms were conducted and solution
qualities compared. The computation experiments show that heuristics and genetic algorithms are viable
methods for solving query optimization problem in large scale distributed database systems.