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

Print

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

This document is currently not available here.

Share

COinS