Design of an Algorithm to Translate Nested Relational Algebra Queries to GENESIS Trace Manager Commands

This thesis describes an algorithm to convert nested relational queries into GENESIS Trace Manager commands. Nested relational algebra is an extension to traditional relational algebra to include multivalued i.e. nested attributes. THe GENESIS Trace Manager is part of the GENESIS database management system being developed at the University of Texas at Austin, Texas. The GENESIS Trace Manager is used to manipulate fields in a record that has been read into a buffer in memory. The algorithm consists of two phases. The first phase of the algorithm is the development of an intermediate data structure to represent the various constructs of the nested relational algebra query. The second phase of the algorithm is the conversion of the intermediate data structure into GENESIS Trace Manager commands. This phase consists of dividing the translation into a number of sub-tasks and providing an algorithm to perform each of these sub-tasks. The GENESIS Trace Manager is limited to working with fields in a record located in a buffer in primary memory. It does not include facilities for reading records from a data base into memory, writing records from memory to a database, or presenting the user with a formated output of the result of the query. Because the GENESIS Trace Manager does not include these facilities, the algorithm does not produce GENESIS commands to perform these functions.