Object-oriented temporal database management: Algebra, time-alignment operations and parallel query processing

In our information-oriented society, people make decisions based on not only information of the present but also information of the past and the foreseeable future. There is a definite need for efficient object-oriented database management systems which can support the concepts of time and manage current, historical and expected data of the future to aid human decision-making. Unlike processing nontemporal databases, processing temporal databases involves an additional dimension of complexity due to the need for manipulating complex temporal relationships among real-world complex objects in addition to the manipulation of their data relationships. The development of object-oriented temporal database management systems depends on our ability to achieve the following: (1) the development of an object-oriented temporal algebra which provides a mathematical foundation for manipulating object-oriented temporal databases as well as an implementation platform for high-level query languages, (2) the identification of a set of basic time-interval operations which allows temporal instances with different valid time intervals to be properly and efficiently manipulated (time-interval processing is a fundamental part of every algebraic operation), and (3) the development of parallel temporal query processing strategies which provides a high degree of efficiency in processing very large temporal databases.; In this work, we present a temporal association algebra (TA-algebra) which serves as a formal foundation for processing object-oriented temporal databases. The algebra uses a pattern-based paradigm for processing temporal data. Histories of objects and their associations are uniformly represented by primitive temporal association pattern instances which are then manipulated by a set of algebraic operators. The algebra is capable of operating on heterogeneous as well as homogeneous patterns of object associations. It provides an implementation platform for processing high-level query language constructs. Since all algebraic operators of the algebra involve the processing of valid time intervals associated with temporal instances, a set of basic "time-alignment" operations are defined in this work to support their processing. Furthermore, a time-interval-to-storage mapping (called time-to-memory mapping) technique is introduced for the efficient implementation of the time-alignment operations. This work also introduces asynchronous parallel query processing strategies which exploit both intraquery and interquery parallelism. A parallel temporal query processor which makes use of the identified time-alignment operations and parallel query processing strategies has been implemented on a parallel computer nCUBE2. Some performance evaluation results using a set of benchmark queries are reported in this dissertation.