TEMPORAL ASSOCIATION ALGEBRA - A MATHEMATICAL FOUNDATION FOR PROCESSING OBJECT-ORIENTED TEMPORAL DATABASES

This paper describes an object-oriented temporal association algebra ( called TA-algebra) which is intended to serve as a formal foundation f or supporting a pattern-based query specification and processing parad igm. Different from the traditional table-and-attribute-based paradigm , the pattern-based paradigm views the intension of an object-oriented temporal database as a network of object classes interconnected by di fferent association types and its extension as a network of associated temporal object instances. Consistent with this view, queries can be specified in terms of patterns of temporal object associations or nona ssociations (i.e., linear, tree and network structures of object class es/objects with logical AND and OR branches). TA-algebra provides a se t of algebraic operators for processing these patterns and allows the direct and/or indirect associations and/or nonassociations among tempo ral object instances to be more explicitly represented and maintained during processing than the traditional tabular representation of tempo rary or final query results. TA-algebra operators are based on time-in terval and valid-time semantics and they preserve the closure property . The algebra is capable of operating on heterogeneous as well as homo geneous patterns of object associations. Both homogeneous and heteroge neous patterns are decomposed into a set of primitive temporal pattern instances for uniform treatment. This paper formally defines the TA-a lgebra operators and their mathematical properties. The applications o f these operators in query decomposition and processing are illustrate d by examples.