Atomic recovery units (ARUs) are a mechanism that allows several logical disk operations to be executed as a single atomic unit with respect to failures. For example, ARUs can be used during file creation to update several pieces of file meta-data atomically. ARUs simplify systems, as they isolate issues of atomicity within the logical disk system, ARUs are designed as part of the Logical Disk (LD), which provides an interface to disk storage that separates file and disk management by using logical block numbers and block lists. This paper discusses the semantics of concurrent ARUs, as well as the concurrency control they require. A prototype implementation in a log-structured logical disk system is presented and evaluated. The performance evaluation shows that the run-time overhead to support concurrent ARUs is negligible for Read and Write operations, and small but pronounced for file creation (4.0%-7.2%) and deletion (17.9%-20.5%) which mainly manipulate meta-data. The low overhead (when averaged over file creation, writing, reading, and deletion) for concurrent ARUs shows that issues of atomicity can be successfully isolated within the disk system.

The Logical Disk (LD) defines a new interface to disk storage that separates file management and disk management by using logical block numbers and block lists. The LD interface is designed to support multiple file systems and to allow multiple implementations, both of which are important given the increasing use of kernels that support multiple operating system personalities.A log-structured implementation of LD (LLD) demonstrates that LD can be implemented efficiently. LLD adds about 5% to 10% to the purchase cost of a disk for the main memory it requires. Combining LLD with an existing file system results in a log-structured file system that exhibits the same performance characteristics as the Sprite log-structured file system.

It is shown how a highly compact representation of binary trees can be used as the basis of two access methods for dynamic files, called BDS-trees and S-trees, respectively. Both these methods preserve key-order and offer easy and efficient sequential access. They are different in the way the compact binary trees are used for searching. With a BDS-tree the search is a digital search using binary digits. Although the S-tree search is performed on a bit-by-bit basis as well, it will appear to be slightly different. Actually, with S-trees the compact binary trees are used to represent separators at low storage costs. As a result, the fan-out, and thus performance, of a B-tree can be improved by using within each index page an S-tree for representing separators efficiently.

This paper describes how to compromise a statistical database which only answers queries about arithmetic means for query sets whose cardinality falls in the range [ k, N - k ], for some k > 0, where N ≥ 2 k is the number of records in the database. The compromise is shown to be easy and to require only a little preknowledge; knowing the cardinality of just one nonempty query set is usually sufficient. This means that not only count and sum queries, but also queries for arithmetic means can be extremely dangerous for the security of a statistical database, and that this threat must be taken into account explicitly by protective measures. This seems quite important from a practical standpoint: while arithmetic means were known for some time to be not altogether harmless, the (perhaps surprising) extent of the threat is now shown.

Question-answering systems must often keep certain information secret. This can be accomplished, for example, by sometimes refusing to answer a query. Here the danger of revealing a secret by refusing to answer a query is investigated. First several criteria that can be used to decide whether or not to answer a query are developed. Then it is shown which of these criteria are safe if the questioner knows nothing at all about what is kept secret. Furthermore, it is proved that one of these criteria is safe even if the user of the system knows which information is to be kept secret.

This paper discusses some high-level language programming constructs that can be used to manipulate the relations of a relational database system efficiently. Three different constructs are described: (1) tuple identifiers that directly reference tuples of a relation; (2) cursors that may iterate over the tuples of a relation; and (3) markings, a form of temporary relation consisting of a set of tuple identifiers. In each case, attention is given to syntactic, semantic, and implementation considerations. The use of these features is first presented within the context of the programming language PLAIN, and it is then shown how these features could be used more generally to provide database manipulation capabilities in a high-level programming language. Consideration is also given to issues of programming methodology, with an important goal being the achievement of a balance between the enforcement of good programming practices and the ability to write efficient programs.