This paper considers access control for local area computer communication networks. We propose two distributed access control schemes for a bus network. The schemes are simple and asynchronous, and provide for collision-free communication among ports. In addition, one of the schemes provides a bounded, guaranteed time to transmisidon for each port. We also show that this scheme is efficient in the use of the bus bandwidth, in the sense that there is only a small fraction of time during which the bus is idle when there is at least one packet available for transmission.

This paper considers problems in which the object is to add a minimum-weight set of edges to a graph so as to satisfy a given connectivity condition. Simple characterizations of the minimum number of edges necessary to make a directed graph strongly connected and to make an undirected graph bridge-connected or biconnected are given. Efficient algorithms for finding such minimum sets of edges are discussed. It is shown that the weighted versions of these problems are NP-complete.

System R is a database management system which provides a high level relational data interface. The systems provides a high level of data independence by isolating the end user as much as possible from underlying storage structures. The system permits definition of a variety of relational views on common underlying data. Data control features are provided, including authorization, integrity assertions, triggered transactions, a logging and recovery subsystem, and facilities for maintaining data consistency in a shared-update environment. This paper contains a description of the overall architecture and design of the system. At the present time the system is being implemented and the design evaluated. We emphasize that System R is a vehicle for research in database architecture, and is not planned as a product.

This paper defines an integrity subsystem for an integrated data base management system, and shows how integrity is distinguished from the related areas of security, consistency, and reliability. The integrity subsystem guards the data base against semantic errors by permitting users to make assertions which define the correctness of the data base, and to specify actions to be taken when the assertions are not satisfied. Several categories of assertions are considered, including tuple-vs. set-oriented, state- vs. transition-oriented, immediate vs. delayed, and "hard" vs. "soft" assertions. The related areas of data definition facilities, compatibility of data items, and handling of null values are explored. Facilities are specified by means of which a user may create, drop, or examine integrity assertions.

Let $Q = \{ q_1 ,q_2 , \cdots ,q_m \} $ be a family of finite, nonempty sets, and $S = \cup_{q_i \in Q} \{ q_i \} $. Suppose there exists a one-to-one function f that maps elements of S into points in the real line $\mathbb{R}$ such that for each $q_i \in Q$ there is an interval $I_i $ containing images of all elements of $q_i $ but not images of any elements not in $q_i $. Then the function f and the set of intervals $\{ I_1 ,I_2 , \cdots ,I_m \} $ are said to faithfully represent Q. Necessary and sufficient conditions and an algorithm for faithful representation of Q are developed. An important kind of file organization, called the consecutive retrieval file organization, is shown to be a direct application of the property of faithful representation.