**Tuple sequences and lexicographic indexes**

Serge Abiteboul, Seymour Ginsburg

Pages: 409-422

DOI: 10.1145/5925.5926

The concept of a tuple sequence is introduced in order to investigate structure connected with relational model implementation. Analogs are presented for the relational operations of projection, join, and selection, and the decomposition problem...

**Elimination of intersection anomalies from database schemes**

Catriel Beeri, Michael Kifer

Pages: 423-450

DOI: 10.1145/5925.5927

The desirability of acyclic (conflict-free) schemes is well argued in [8] and [13]. When a scheme is described by multivalued dependencies, acyclicity means that the dependencies do not split each other's left-hand side and do not form...

**Security problems on inference control for SUM, MAX, and MIN queries**

Francis Chin

Pages: 451-464

DOI: 10.1145/5925.5928

The basic inference problem is defined as follows: For a finite set *X* = {*x*_{i},
, *x*_{n}}, we wish to infer properties of elements of *X* on the basis of sets of "queries" regarding subsets of *X*....

**Sort sets in the relational model**

Seymour Ginsburg, Richard Hull

Pages: 465-488

DOI: 10.1145/5925.5929

The notion of sort set is introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways...

**A note on the height of binary search trees**

Luc Devroye

Pages: 489-498

DOI: 10.1145/5925.5930

Let Hn be the height of a binary search tree with n nodes constructed by standard insertions from a random permutation of 1, … , n. It is shown that...

**Reaching approximate agreement in the presence of faults**

Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, William E. Weihl

Pages: 499-516

DOI: 10.1145/5925.5931

This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Boolean values or values from some bounded range, and in which approximate, rather than exact, agreement is the...

**Predicting fill for sparse orthogonal factorization**

Thomas F. Coleman, Anders Edenbrandt, John R. Gilbert

Pages: 517-532

DOI: 10.1145/5925.5932

In solving large sparse linear least squares problems A x ≃ b, several different numeric methods involve computing the same upper triangular factor R of A. It is of interest to be able to...

**A unified approach to approximation algorithms for bottleneck problems**

Dorit S. Hochbaum, David B. Shmoys

Pages: 533-550

DOI: 10.1145/5925.5933

In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is investigated. Each of the algorithms presented here...

**Improved methods for storing and updating information in the out-of-kilter algorithm**

Samar Singh

Pages: 551-567

DOI: 10.1145/5925.5934

Currently, network codes based on the primal simplex algorithm are believed to be computationally superior to those based on other methods. Some modifications of the out-of-kilter algorithm of Ford and Fulkerson are given, together with proofs...

**Asymptotic expansions for closed Markovian networks with state-dependent service rates**

Debasis Mitra, J. McKenna

Pages: 568-592

DOI: 10.1145/5925.5935

A method is presented for calculating the partition function, and from it, performance measures, for closed Markovian stochastic networks with queuing centers in which the service or processing rate depends on the center's state or load. The...

**The performance of a precedence-based queuing discipline**

John N. Tsitsiklis, Christos H. Papadimitriou, Pierre Humblet

Pages: 593-602

DOI: 10.1145/5925.5936

A queuing system with infinitely many servers, and with the following queuing discipline is considered: For any two jobs i and j in the system, such that i arrived later than j,...

**The polynomial-time hierarchy and sparse oracles**

Jose L. Balcázar, Ronald V. Book, Uwe Schöning

Pages: 603-617

DOI: 10.1145/5925.5937

Questions about the polynomial-time hierarchy are studied. In particular, the questions, “Does the polynomial-time hierarchy collapse?” and “Is the union of the hierarchy equal to PSPACE?” are considered, along with...

**Relativizing complexity classes with sparse oracles**

Timothy J. Long, Alan L. Selman

Pages: 618-627

DOI: 10.1145/5925.5938

Baker, Gill, and Solovay constructed sparse sets A and B such that P(A) ≠ NP(A) and NP(B) ≠ co-NP(B). In contrast to their results, we...