Graduate Thesis Or Dissertation

View based, global design of access structures for relational databases

Public Deposited

Downloadable Content

Download PDF


Attribute NameValues
  • In this dissertation we consider the problem of automating the design of access structures for relational database systems. The main considerations are effective and rigorous utilization of the users' usage patterns, global treatment of the whole design and utilizing most of the commonly known access structures. We represent the usage patterns on the access structures as relational algebra views. We transform a view into one or more simple access structures. Using the simple access structures we generate compound access structures. From this set of access structures we choose an approximately optimal set of access structures that process the input views as efficiently as possible and obey the storage space constraint. In developing the transformation methods, we also develop the concepts of aggregation and generalization for access structures, and use them in obtaining compound access structures from simple data items and in integrating several access structures into one access structure. We introduced a general method that shows how any complex access structure is formed from the simple data items using aggregation. In the transformations we consider insertion, deletion, look-up, update, building and storage space costs of access structures and/or views. The access structure types employed are tree, chain, circular chain, pointer array, cluster of tuples and sorting tuples in one or two relations. The access structures associated with a relation may cover different numbers of tuples. For the optimization we separate all access structures into pointer and placement types. We give a 0-1 knapsack problem based approximate optimization algorithm to solve the pointer access structure optimization problem. We formulate the placement access structure optimization as a 0-1 integer programming problem. In the global optimization algorithm, we utilize the placement and pointer optimization algorithms and approximately compensate for the interdependencies between the placement and pointer access structure optimizations.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Academic Affiliation
Non-Academic Affiliation
Rights Statement
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6770A in PDF format. CVista PdfCompressor 5.0 was used for pdf compression and textual OCR.



This work has no parents.

In Collection: