DataQuest: A comparative analysis of heuristic query optimization algorithms
Date of Publication
1994
Document Type
Bachelor's Thesis
Degree Name
Bachelor of Science in Computer Science
Subject Categories
Computer Sciences
College
College of Computer Studies
Department/Unit
Computer Science
Abstract/Summary
The thesis is an implementation and study on query optimization for a single-user database system. The general objective is to show whether applying query optimization in a single-user interpretative relational DBMS is justifiable. The specific objectives are: to implement a prototype relational database management system, and to implement and analyze two query optimization algorithms. The prototype DBMS is an interpretative system and is based on the relational model. Its main function is to process ad-hoc queries. An SQL interface provides commands for data definition (CREATE, DROP, COPY and SORT) and data manipulation (INSERT and SELECT). Database information and statistics are stored and maintained by the system catalog manager. The system uses two storage structures: heap files, hash files and b+tree indices. Relational operations using different kinds of access paths are implemented. Two query optimization algorithms are implemented for the study. The algebraic manipulation technique is a heuristic algorithm and is based on the relational algebra tree. It applies transformation rules to optimize the tree. The optimized tree is then submitted to a relational algebra tree processor which performs the query. The decomposition technique is a heuristic algorithm which applies detachment and tuple substitution strategies to optimize the query. It dynamically processes the query during optimization. Aside from these algorithms, a query processing strategy without optimization is also implemented. A sample database is created for the analysis. Query response time is the parameter used for comparison.
Abstract Format
html
Language
English
Format
Accession Number
TU08533
Shelf Location
Archives, The Learning Commons, 12F, Henry Sy Sr. Hall
Physical Description
3 v. (various pagings) ; Computer print-out.
Keywords
Database management; Mathematical optimization; Query (Information retrieval system); System analysis--Data processing
Recommended Citation
Lanuza, M. L., Motas, A. R., Nerona, L. V., & Zalatar, W. F. (1994). DataQuest: A comparative analysis of heuristic query optimization algorithms. Retrieved from https://animorepository.dlsu.edu.ph/etd_bachelors/6899