Database schema translation and optimization.

Abstract

The proliferation of different database system architectures in heterogeneous environments has limited the portability of data and applications between database systems. The objective of this research is to provide a methodology for the translation of a database schema from one architecture to another, particularly from the hierarchical and network architectures to relational, and to investigate whether usage optimization of the schema is feasible during this translation. A model of data is developed that facilitates the incorporation of multiple external views of data into a common conceptual and logical model, and leads to the direct translation of schemas between database architectures. A graphic approach is used to obtain a series of mappings whose properties determine conditions under which the information content is preserved across the mapping. The common data model forms the basis for the database schema optimization problem, the minimization of a nonlinear, constrained objective function through the constrained selection of relationship implementations. This problem is decomposed into a linear problem contained within a nonlinear one. The common conceptual and logical models are used to show that the linear database schema optimization problem is, in general, NP-complete. The existence of real-world performance constraints and nonlinear pricing of services leads to the identification of a class of nonlinear optimization problems superimposed on the linear database schema optimization problem. A technique is described which solves this problem, provided that the linear database schema optimization problem for the same performance measures can be solved.