Access Path Optimization for Network Database Retrieval (Query, Relational, Codasyl)

116 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984.In evaluating a query using a network database, the links need to either be followed or be saved. Most of the previous approaches follow the links in evaluating a query using a network database. Actually, it is not always necessary to follow the links in answering a query using a network database, nor does it always result in the fewest disk page accesses. Two new data retrieval methods are presented so that the links are saved in a database relation for later use. The methods proposed combine traditional relational and network retrieval methods. In many cases, these new methods show substantial performance improvement in evaluating queries using network databases {CK84a}. The proposed methods are useful for database retrieval from network databases as well as from relational databases implemented with links {CK84b}.A network database system without a high-level query interface is very difficult for naive users to use. Therefore, a high-level query interface is usually provided to translate a user's queries into efficient network queries. The query optimization algorithms for such a system are presented in a stepwise fashion by beginning with finding an optimal access path for a given access tree using the proposed methods as well as the traditional method of database retrieval. The algorithm for enumerating all possible access trees to answer a query is then presented. A heuristic method is also presented for processing more complex queries that can only be answered by joining the results of two or more access trees.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD