Removal of redundant outer joins is essential for the reassociation of outer joins with other binary operations. We present a set of comprehensive algorithms that employ the properties of strong predicates along with the properties of aggregation, intersection, union, and except operations to remove redundant outer joins from a query. For the purpose of query simplification, we generate additional projections by determining the keys. Our algorithm for generating keys is based on a novel concept of weak bindings that is essential for queries containing outer joins. Our algorithm for converting outer joins to joins is based on a novel concept of join-reducibility.

Complex queries containing outer joins are, for the most part, executed by commercial DBMS products in an "as written" manner. Only a very few reorderings of the operations are considered and the benefits of considering comprehensive reordering schemes are not exploited. This is largely due to the fact there are no readily usable results for reordering such operations for relations with duplicates and/or outer join predicates that are other than "simple." Most previous approaches have ignored duplicates and complex predicates; the very few that have considered these aspects have suggested approaches that lead to a possibly exponential number of, and redundant intermediate joins. Since traditional query graph models are inadequate for modeling outer join queries with complex predicates, we present the needed hypergraph abstraction and algorithms for reordering such queries with joins and outer joins. As a result, the query optimizer can explore a significantly larger space of execution plans, and choose one with a low cost. Further, these algorithms are easily incorporated into well known and widely used enumeration methods such as dynamic programming.

Transaction time is used for time stamping object values to record their database history and formulate a zero information loss model for database transactions. The model consists of three components, a data history store, an update store, and a query store. In such a model, the effect of a past transaction (a query or an update) can be determined at any time. Additionally, the update and query stores make it possible to reconstruct the circumstances of updates and the information divulged in queries. Such a model is suitable for the design of secure, easy-to-audit database systems.>