Abstract

The efficient implementation of advanced database programming languages calls for investigating novel architectures and algorithms. In this thesis, we discuss our implementation of SchemaLog, a logic-based database programming language, capable of offering a powerful platform for a variety of database applications involving data/meta-data querying and restructuring. Our architecture for the implementation is based on compiling SchemaLog constructs into an extended version of relational algebra called Schema Algebra (${\cal {SA}}$). We modify the new operators in this algebra to suit our implementation, and we illustrate how a SchemaLog program can be evaluated by conversion into an expression in ${\cal {SA}}$. Based on this algebra, we develop a top-down algorithm, using the Rule/Goal Tree method, for evaluating SchemaLog programs. We then discuss three alternative storage structures for the implementation and study their effect on the efficiency of implementation. For each storage structure, we propose strategies for implementing our algebraic operators. We have implemented all these algorithms, using MicroSoft Access DBMS running on Windows 3.1, and have run an extensive set of experiments for evaluating the efficiency of alternative strategies under a varied mix of querying and restructuring operations and varying parameters on the type and size of data. We discuss the results of our experiments and make recommendations on the type of storage structures to be used.