An Evolutionary Genetic Algorithm for Optimization of Distributed Database Queries

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.


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...
A C++ distributed database select - project - join query processor on a HPC cluster
Ceran, Erhan; Coşar, Ahmet; Department of Computer Engineering (2012)
High performance computer clusters have become popular as they are more scalable, affordable and reliable than their centralized counterparts. Database management systems are particularly suitable for distributed architectures; however distributed DBMS are still not used widely because of the design difficulties. In this study, we aim to help overcome these difficulties by implementing a simulation testbed for a distributed query plan processor. This testbed works on our departmental HPC cluster machine and...
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...
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: