Optimization of complex queries in future database systems is a major focus of this work. The applicability of randomized algorithms for query optimization is investigated for several types of database systems, e.g., relational, object- oriented, and parallel systems. Emphasis is placed on identifying the abstract characteristics of cost functions and data models that determine the effectiveness of such algorithms. Of special concern is also the propagation of errors in parameters that affect the query optimizer's decisions. This research leads to developing techniques for query optimization in future systems where current technology is inadequate. Another focus of this work is the study of specialized database systems for managing data from scientific experiments. The emphasis is on graphical user interfaces and semantic heterogeneity. Collaborating scientists from many disciplines provide guidelines for the goalsof this effort based on the needs of their laboratories. This research develops tools that enables such scientists to use database technology effectively for their experiments. Although this work is driven by the specific needs of scientific databases, its results can be applied to solve many similar problems faced by next generation database systems in general.
