The authors propose a model, called the object request network, for representing the input requests to the optimizer which uniformly captures the main features needed in deductive and object-oriented database management systems (DBMSs). This model allows the recursive definition of derived objects, avoids some rewriting effort when changing the navigation on objects, and supports declarative request languages. The authors consider how the requests are optimized, and show that with the approach adopted it is possible to investigate more general execution plans than in earlier work.>

To efficiently process recursive queries in a DBMS (database management system), a parallel, direct transitive closure algorithm is proposed. Efficiency is obtained by reorganizing the computation order of Warren's algorithm. The number of transfers among processors depends only on the number of processors and does not depend on the depth of the longest path. The evaluation shows an improvement due to the parallelism and the superiority of the proposed algorithm over recent propositions. The speed of the production of new tuples is very high and the volume of transfers between the sites is reduced.>

A method is proposed to store and efficiently retrieve rules in a deductive database. The rules are compiled into an execution model called a PCN (production compilation network). The PCN is stored as a particular relational database which consists of three relations. For a given end-user query the first step of the inference process consists of searching for the relevant rules by traversing the PCN structure. This traversal is computed by a transitive closure of a part of the PCN. The transitive closure is performed by a loop of joins over the relations storing the PCN. In this context, a transitive closure algorithm that is based on a physical clustering of the relations is proposed. This clustering consists of a double hashing technique. It ensures a linear cost for the join operation with weak conditions on the size of the main memory. The approach reduces the number of I/O operations for semi-naive transitive closure operation. This algorithm will be applied to the search for relevant rules and to the transitive computation of linear recursive relations.>

The authors present a clustering method for complex domains. The method is original in that tuples can be clustered using functions applied to complex domain values. Thus, tuples are organized according to a function result. Those functions most often applied to complex values and used in the restriction part of queries can be used as clustering predicates. Hence, they optimize the retrieval of tuples that would otherwise require processing the whole relation. In SABRINA, complex domain processing is made possible by a Lisp language processor designed as an integrated database management system processor. Clustering is determined by a set of predicates defining a recursive partitioning of the relation. These predicates are the Lisp functions, taken from the set of functions applicable to a given domain. The authors demonstrate that by using the same approach for a data manipulation language and a clustering strategy, few modifications of the DBMS program are required and the assertional power of the DBMS is upgraded while respecting performance considerations.>

A new access method, based upon predicate-tree and previously presented in [GARD 83b, VALD 84, GARD 85], presents major possibilities of applications. The basic method which is implemented, allows the clustering of tuples from a relation when they satisfy some predicate. The aim of this paper, is to show the flexibility of this method and the numerous possibilities of extensions. In addition, to the permanent access paths based upon physical clustering, predicate-trees allow the implementation of classical secondary access paths. We give a method to code the values of several secondary attributes by use of secondary predicate-trees. This method requires a less important storage volume than classical secondary indexes. Predicate-trees can also efficiently speed up the join operation. Clustering information is used to limit the join to relevant pairs of partitions. Our evaluation shows that an improvement ratio of 7 or more versus traditional algorithms can be achieved.