We study the complexity of processing a class of rules called simple binary rule sets. The data referenced by the rules are stored in secondary memory. A necessary and sufficient condition that a simple binary rule set can be processed in a single pass of a file containing the base relations is given. Because not all simple binary rule sets can be processed in a single pass, a necessary and sufficient condition that a simple binary rule set can be processed by a constant number of passes is also given.>

A data structure is used to store materialized generalized transitive closure so that the evaluation of generalized transitive closure queries, deletions, and insertions of tuples can be performed efficiently in centralized and parallel environments. Some techniques to manage materialized transitive closure are presented and generalized to more general recursions. The proposed algorithms and the associated data structures are simple conceptually and in implementation. In a multiprocessor environment, the time complexities for insertion and deletion of the authors schemes are reduced. Only two rounds of communication are needed.>

A data structure is used to store materialized transitive closure such that the evaluation of transitive closure, deletions and insertions of tuples can be performed efficiently. Experiments have been carried out on a Sun/3/180 system. It is verified experimentally and theoretically that it takes on the average O(m") to retrieve the ancestors/descendants of the given node, where m" is the number of ancestors/descendants of the given node, and it takes on the average O(m*m') to perform an insertion or a deletion of a tuple (a,b), where m is the number of ancestors of a+1 and m' is the number of descendants of b+1. It is shown that, when the data types is integer, retrieval of the ancestors/descendants of a given node takes no more than 0.0001 s; insertion/deletion of a tuple and the corresponding update involving m*m"=elements in the data structure takes approximately 0.07 s. When data type is a string of length 20, the corresponding retrieval time and insertion/deletion times are 0.0008 s and 1.5 s respectively.>

A special schema is constructed to represent the data of a binary relation so that the transitive closure can be evaluated efficiently in distributed database systems. The method is economical in communication cost and at the same time preserves the fast access paths for efficient parallel processing of transitive closure at local sites. Updating of data is also discussed.>

A partition-and-replicate strategy for processing distributed queries referencing no fragmented relation is sketched. An algorithm is given to determine which relation and which copy of the relation is to be partitioned into fragments, how the relation is to be partitioned, and where the fragments are to be sent for processing. Simulation results show that the partition strategy is useful for processing queries in fast local network environments. The results also show that the number of partitions does not need to be large. The use of semijoins in the partition strategy is discussed. A necessary and sufficient condition for a semijoin to yield an improvement is provided.>

We propose a scheme to make use of semantic information to process distributed queries locally without data transfer with respect to the join clauses of the query. Since not all queries can be processed without data transfer, we give an algorithm to recognize the "locally processable queries." For nonlocally processable queries, a simple "fragment and replicate" algorithm is used. The algorithm chooses a relation to remain fragmented at the sites where they are situated while replicating the other relations at those sites. Our algorithm determines the chosen relation and the chosen copy of every fragment of the chosen relation such that the minimum response time is obtained. The algorithm runs in linear time. If the fragments of the relation are allowed to be processed in other sites, then the problem is NP hard. Two heuristics are given for that situation. They are compared to the optimal situation. Experimental results show that the strategies produced by the heuristics have small errors relative to the optimal strategy.

We propose new adaptive techniques for distributed query optimization. These techniques are divided into two groups: the ones that improve efficiency of query execution (directly) and the ones that improve cost estimations for query execution strategies. Some of the proposed techniques utilize semantic information and knowledge acquisition to adapt to the environment. The latter, in contrast to the former, is not a well-established idea. This is a disturbing fact since knowledge acquisition can give significant improvements in performance of a query optimization algorithm. Performing analysis manually is extrernely time consuming and tedious. Therefore, some learning capacity should be added to the system. Some knowledge acquisition techniques that result in adaptive (dynamic) adjustment to run-time changes are proposed.