Savantis Systems' dbSwitch™ is an innovative commercial product providing database server virtualization and advancing a database utility model. The dbSwitch enables a new architecture, called a Database Area Network (DAN), which pools database server resources and shares them among multiple database applications. Specific benefits of the DAN architecture for enterprise data centers include server consolidation, improved utilization, high availability and capacity management. We describe the major components of the dbSwitch, namely routing of application requests to database instances, optimization of database server resources and capacity visualization and manipulation. We also relate dbSwitch to recent work on utility and grid computing.

DTL's DataSpot is an advanced, programming-free tool that lets Web designers and database developers automatically publish their databases for Web browser access. DataSpot enables non-technical end users to explore a database using free-form plain language queries combined with hypertext navigation, in a fashion similar to using search engines such as Alta Vista to search text files on the Internet.

Extended transaction models in databases were motivated by the needs of complex applications such as CAD and software engineering. Transactions in such applications have diverse needs, for example, they may be long lived and they may need to cooperate. We describe ASSET, a system for supporting extended transactions. ASSET consists of a set of transaction primitives that allow users to define custom transaction semantics to match the needs of specific applications. We show how the transaction primitives can be used to specify a variety of transaction models, including nested transactions, split transactions, and sagas. Application-specific transaction models with relaxed correctness criteria, and computations involving workflows, can also be specified using the primitives. We describe the implementation of the ASSET primitives in the context of the Ode database.

We present a comprehensive performance evaluation of transitive closure (reachability) algorithms for databases. The study is based upon careful implementations of the algorithms, measures page I/O, and covers algorithms for full transitive closure as well as partial transitive closure (finding all successors of each node in a set of given source nodes). We examine a wide range of acyclic graphs with varying density and “locality” of arcs in the graph. We also consider query parameters such as the selectivity of the query, and system parameters such as the buffer size and the page and successor list replacement policies. We show that significant cost tradeoffs exist between the algorithms in this spectrum and identify the factors that influence the performance of the algorithms.An important aspect of our work is that we measure a number of different cost metrics, giving us a good understanding of the predictive power of these metrics with respect to I/O cost. This is especially significant since metrics such as number of tuples generated or number of successor list operations have been widely used to compare transitive closure algorithms in the literature. Our results strongly suggest that these other metrics cannot be reliability used to predict I/O cost of transitive closure evaluation.

Ode, a database system and environment based on the object paradigm, is discussed. Ode is defined, queried and manipulated using the database programming language O++, which is based on C++. The O++ compiler translates O++ programs into C++ programs that contain calls to the Ode object manager. The implementation of O++, the Ode object manager, and the translation of the database facilities in O++ are described. The problems encountered in the implementation and their resolutions are reviewed.>

Abstract C++ objects of types that have virtual functions or virtual base classes contain volatile (‘memory’) pointers. We call such pointers ‘hidden pointers’ because they were not specified by the user. If such C++ objects are made persistent, then these pointers become invalid across program invocations. We encountered this problem in our implementation of O++, which is a database language based on C++. O++ extends C++ with the ability to create and access persistent objects. In this paper, we describe the hidden pointers problem in detail and present several solutions to it. Our solutions are elegant in that they do not require modifying the C++ compiler or the semantics of C++. We also discuss another problem that arises because C++ allows base class pointers to point to derived class objects. C++ has emerged as the de facto standard language for software development, and database systems based on C++ have attracted much attention. We hope that the details and techniques presented will be useful to database researchers and to implementors of object‐oriented database systems based on C++.

We present SQL/TC, an extension of SQL, to allow the expression of generalized transitive closure queries. The extension permits the user to pose queries that compute paths between two points and information associated with these paths. Such queries may specify selections on arcs, paths, or sets of paths, The output of a query may include the aggregation of information for different paths between the same endpoints. Our notation is declarative, preserves the spirit of SQL, and allows a declarative and concise formulation of transitive closure queries.>

The authors present a transitive closure algorithm that maintains a spanning tree of successors for each node rather than a simple successor list. This spanning tree structure promotes sharing of information across multiple nodes and leads to more efficient algorithms. An effective relational implementation of the spanning tree storage structure is suggested, and it is shown how blocking can be applied to reduce the input/output cost of the algorithm. The algorithm can handle path problems also. Analytical and experimental evidence is presented that demonstrates the utility of the algorithm, especially in a graph with many alternate paths between the nodes. The spanning tree storage structure can be compressed and updated incrementally in response to changes in the underlying graph.>

Two complementary techniques for optimizing generalized transitive closure queries are presented: (i) selections on paths are applied during the closure computation, so that paths that are not in the result and that are not needed to compute the result are pruned as early as possible and (ii) paths that are in the result, or needed to compute the result, are represented in a condensed form. The condensed representation holds the minimal information that is necessary for the specified label computations and selections to be performed. The combined impact of these techniques is that the number of paths generated during the closure computation and the storage required for each such path are both greatly reduced.>

We present new algorithms for computing transitive closure of large database relations. Unlike iterative algorithms, such as the seminaive and logarithmic algorithms, the termination of our algorithms does not depend on the length of paths in the underlying graph (hence the name direct algorithms). Besides reachability computations, the proposed algorithms can also be used for solving path problems. We discuss issues related to the efficient implementation of these algorithms, and present experimental results that show the direct algorithms perform uniformly better than the iterative algorithms. A side benefit of this work is that we have proposed a new methodology for evaluating the performance of recursive queries.

The authors argue for implementing composition as a primitive operation and present a single-sided composition algorithm that performs join protection and duplicate elimination as one unified operation. They report experimental results that show an operating region in which this algorithm outperforms composition by the standard method. This operating region is characterized by a join result many times larger than the source relations, and many duplicates after projection over the nonjoin attributes. This occurs, for example, in deductive databases when computing transitive closures of dense graphs.>