An Evolutionary Genetic Algorithm for Optimization of Distributed Database Queries

2011-05-01
Sevinc, Ender
Coşar, Ahmet
High-performance low-cost PC hardware and high-speed LAN/WAN technologies make distributed database (DDB) systems an attractive research area where query optimization and DDB design are the two important and related problems. Since dynamic programming is not feasible for optimizing queries in a DDB, we propose a new genetic algorithm (GA)-based query optimizer (new genetic algorithm (NGA)) and compare its performance with random and optimal (exhaustive) algorithms. We perform experiments on a synthetic database with replicated relations, but no horizontal or vertical fragmentation. Network links are assumed to be gigabit ethernet. Comparisons with optimal results show that our NGA formulation performs only 20% of the optimal results and we have achieved 50% improvement over a previous GA-based algorithm.
COMPUTER JOURNAL

Suggestions

A generalized expert system for database design
Doğaç, Asuman; Yürüten, Betigül; Spaccapietra, Stefano (Institute of Electrical and Electronics Engineers (IEEE), 1989-4)
Generalized Expert System for Database Design (GESDD) is a compound expert system made up of two parts: (1) an expert system for generating methodologies for database design, called ESGM; and (2) an expert system for database design, called ESDD. ESGM provides a tool for the database design expert to specify different design methodologies or to modify existing ones. The database designer uses ESDD in conjunction with one of these methodologies to design a database starting from the requirement specification...
An efficient transitive closure algorithm for distributed databases
Toroslu, İsmail Hakkı (1993-01-01)
© 1993 IEEE.Because most of the recognizable queries in deductive databases can be transformed into transitive-closure (TC) problem, the development of efficient algorithms to process the different forms of TC problems within the context of large database systems has recently attracted a large amount of research efforts. However, the parallelization of the computation of TC is still a new issue and there are only a few and recent parallel TC algorithms. Most of these parallel algorithms mere developed for s...
The strong partial transitive-closure problem: Algorithms and performance evaluation
Toroslu, İsmail Hakkı (1996-08-01)
The development of efficient algorithms to process the different forms of transitive-closure (To) queries within the context of large database systems has recently attracted a large volume of research efforts. In this paper, we present two new algorithms suitable for processing one of these forms, the so called strong partially instantiated transitive closure, in which one of the query's arguments is instantiated to a set of constants and the processing of which yields a set of tuples that draw their values...
A Cost-Aware Strategy for Query Result Caching in Web Search Engines
Altıngövde, İsmail Sengör; Ulusoy, Oezguer (2009-01-01)
Search engines and large scale IR systems need to cache query results for efficiency and scalability purposes. In this study, we propose to explicitly incorporate the query costs in the static caching policy. To this end, a query’s cost is represented by its execution time, which involves CPU time to decompress the postings and compute the query-document similarities to obtain the final top-N answers. Simulation results using a large Web crawl data and a real query log reveal that the proposed strategy impr...
An Efficient Metaheuristic Algorithm for Engineering Optimization: SOPT
Hasançebi, Oğuzhan (2012-06-01)
Metaheuristic algorithms are well-known optimization tools which have been employed for solving a wide range of optimization problems so far. In the present study, a simple optimization (SOPT) algorithm with two main steps; namely exploration and exploitation, is provided for practical applications. Aside from a reasonable rate of convergence attained, the ease in its implementation and dependency on few parameters only are among the advantageous characteristics of the proposed SOPT algorithm. The efficienc...
Citation Formats
E. Sevinc and A. Coşar, “An Evolutionary Genetic Algorithm for Optimization of Distributed Database Queries,” COMPUTER JOURNAL, pp. 717–725, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/29939.