[_CD8_]<cedardocs>database>c+f1.memo!2

Abstract:The Cypress database system is intended to provide a convenient, high-performance data management facility for use by clients of the Cedar programming environment. The goal of Cypress is an integrated, unified representation of data across programs and machines, aiding information exchange and avoiding repeated implementations of specialized data management facilities. We present the basic concepts and capabilities of the Cypress database system, and describe the programmer’s interface to the system.

CSL needs a database system. A database system provides many data management facilities that are currently re-invented by program after program, and thereby eliminate a large duplication of effort. It also provides a capability that is needed by many programs but actually implemented by very few: a means of sharing information among programs that are distributed around the network.

This paper begins by developing database concepts that are necessary to put the Cypress database facilities in perspective. We do not expect most people in CSL to become familiar with database jargon, or to read a Mesa interface, in order to discover whether or not the database system can be useful to them. Thus we begin (Section 2) by defining the scope of the general database problem, and measuring our ambitions relative to this standard. We also describe some current and potential applications of our system.

The main body of this paper describes the interface to the Cypress database system. We first give an overview (Section 3), then present the full story (Section 4). This requires defining the class of data structures that can be stored in a database, and then describing the procedures for manipulating these data structures. For illustration, we present a short Mesa program that manipulates a database (Section 5). We then give an example of how a particular real-world information structure might be represented as a database, and discuss design tradeoffs (Section 6).

The form of our database system has evolved and will continue to evolve with experience with database applications in CSL. The Cypress database system described here incorporates two major changes to the original Cedar Database System (Brown, Cattell, Suzuki [1981]), motivated by early experience with applications: a more powerful file system (Alpine, by Brown et al [1982]), and more powerful data structuring mechanisms (DBView, by Cattell [1982]). Also, some database tools have been developed (Squirrel, see Donahue [1982]). We plan to build other tools and interfaces on top of the one described here, and eventually to integrate some set of database facilities into the Cedar Mesa language. Because other documents discuss these longer range plans, however, we shall give such discussions secondary status in this paper. We do wish to emphasize that we are open to suggestions concerning what the future facilities should look like; it is certain that our earliest and most energetic clients will have the greatest influence on the evolution of the system.

As mentioned earlier, applications of the original Cedar database system were helpful in it revision. These applications included a database of Mesa programs, the CSL notebook, and a personal database browser. These applications were experiments, though it is expected they will be carried over into the Cypress system in the coming year.

At the time of this writing, three major application programs run in the Cypress database system. The first is Walnut, providing facilities in the Cedar programming environment to read, send, and organize electronic mail in a database. The second is Hickory, which manages an appointment calendar database and provides an alarm mechanism in Cedar to remind the user of meetings, seminars, etc. The third application is Squirrel, which provides facilities to edit, organize, and browse a personal database of any type of data. In addition to these application-independent data manipulation facilities, Squirrel provides facilities to application programs such as Hickory and Walnut. Cypress clients planning to build application programs should consult the Squirrel documentation (Donahue [1982]) to see if these facilities are useful for the envisioned application.

Other database applications are planned but have not yet been undertaken due to manpower limitations. Most of these are public databases such as the CSL notebook and the "Whitepages" database of people, phone numbers, and addresses.

Before discussing the facilities to be provided in the Cypress database system, we must address the question "what properties make something a database system?" We shall often contrast databases with more familiar data structures, such as Mesa record structures.

We find it useful to give a few definitions here. A client is a program using some facility, such as a database system. A user, on the other hand, is a human using a facility, such as an interactive interface to a database system. A database query is the operation of reading information from a database; depending on the type of interface provided, a query may be limited to reading one item or may involve thousands. An update is a write operation on a database.

Information in a long-lived database can become more valuable than the programs that manipulate it. A database may exist long enough to be operated on by several different generations of the same application program, or to be used for applications that were not anticipated when the database was first designed. Thus the gradual evolution of the database becomes a concern analogous to the well-known problems of evolving programs.

The continued soundness of a persistent database is important. Soundness in the face of physical mishaps such as disk head crashes or tape vault fires is called physical integrity. A guarantee of perfect physical integrity is impossible, but a database system should reduce the probability of disaster to a level that is acceptable in light of the value of information in the database.

A much more difficult problem comes in maintaining the logical integrity of a database. A database is generally used to model some real-world state of affairs, such as the structure of a Mesa system, the layout of a document, or the contents of a person’s appointment schedule. Logical integrity means the correct correspondence between a database and the real-world situation being modeled. A database may be damaged in a logical sense by the keying of incorrect input data, or the running of an incorrect program. These two examples should make it clear that perfect logical integrity is an ideal that cannot be guaranteed; unfortunately, the loss of confidence caused by errors in a database can be just as damaging as a catastrophic physical failure (Hoare [1975]).

One simple form of insurance for the logical integrity of a database is always provided in a database system. This is the persistent storage and enforced use of data that tells how to interpret the representation of the database. This data is somewhat analogous to the type declarations required in Mesa programs that use data structures. It should be clear that using the wrong declarations when accessing the database could lead to disaster. Some database systems go beyond this, allowing the user to state more application-specific properties that his data should satisfy. These are sometines called integrity constraints or integrity assertions.

Of course, there was long-lived information before there were any database systems: this information was stored in file systems. But file systems at best gave some assistance in preserving the physical integrity of stored data, and were no help with any of the other problems associated with persistence. Hence these problems were solved in an ad hoc manner by various applications.

One aspect of sharing is consistent concurrent access to data by programs. Here "concurrent access" does not mean that the programs’ commands to read or update the database are actually executed at the same instant of time, but rather that the precise order in which these commands are executed from different programs is unpredictable.

In general, consistency of a database can only be defined with respect to an application: we say that a database state is consistent if it satisfies a certain application-specific invariant. For instance, an accounting system might have as an invariant the property that the total debits and credits in the system are equal. In some database systems a transaction facility is provided to help applications maintain consistency invariants. Briefly, a transaction is a sequence of read and write commands. The system supports the property that the entire sequence of commands executes atomically with respect to all other transactions, that is, the transaction executes as if no other transactions were in progress at the same time. Because there may in fact be other transactions accessing the same data at the same time, it is possible (in most systems) that two transactions may deadlock, in which case one of them must be aborted. So the price paid for concurrent access is the necessity that programs be prepared to retry aborted transactions.

An example of an application in which concurrent access capability is necessary is an interactive reservation system, say for CSL meeting rooms. By structuring the reservation system’s database accesses into transactions, it should be possible to ensure that the database will remain consistent despite reservations entered concurrently from different machines on the network. The consistency invariants in this case would include having each time period for each room reserved at most once.

Another aspect of sharing is the integration of information into a single database. Integration means that information is kept in a consistent form in one database, even if this is not strictly necessary for the purposes of existing applications. Integration allows new problems to be solved more easily because all of the necessary information is maintained in the same database. It also encourages sharing of information at a more macroscopic level than in the reservation system example above, since it provides a set of uniform naming conventions and access methods for all users. In principle, integration makes logical integrity easier to maintain, because there is less of a tendency to duplicate data for use by different applications.

Unfortunately, sharing introduces new possibilities for logical damage to a database. For instance, one user’s undebugged program can mistakenly modify the data of another user. A database’s protection system is designed to make such damage less likely by requiring an authorization check before querying or updating the database. Some database systems provide elaborate protection facilities that give fine-grained control over access to information; this is especially necessary if sensitive information is to be shared through the database.

In principle, largeness is independent of persistence. In practice, largeness generally implies persistence, but not the other way around: it is quite common to require small data objects to survive between the executions of a program.

Because of the shared, persistent nature of a database, its usage changes with time. To provide good performance as the access pattern shifts, it is necessary to change the database representation to keep the most common operations inexpensive. Because of the value of existing applications software, the database system should make these programs functionally immune to changes in the storage structure used in representing the database. That is, such changes should at most affect a program’s performance, and not the results that it gives.

This data independence can be achieved by ensuring that the interface used by programmers to specify algorithms involving the database refers to a model of data, the conceptual model, that is a useful abstraction of stored structures (independent of their precise form). Ideally the database system would then choose a good underlying representation based on its knowldege of the user’s programs, or adaptively based on execution statistics. This remains a research problem: no existing system can perform such optimizations automatically. An alternative is for the system to accept advice from the user on pragmatic matters (such as the use of internal indexes), where this advice takes the form of declarations that cannot affect the semantics of an application program.

Another consequence of the more fundamental database properties above is that database structures should be kept simple and regular. Persistence argues for simplicity because if a structure is not simple, it is difficult for different programs to maintain it in a consistent and accurate way over time. Regular structures are easier to share for the same reason, and also because they tend to contain larger meaningful substructures, that can serve as the units for locking. With a large, irregular structure it is very likely that consecutive accesses to data will seem uncorrelated from the system’s point of view, meaning that a disk access is required for each one. In more regular structures the access pattern often involves scanning data in an order that is meaningful to the system, so that caching and prefetching will increase performance.

By structuring a database in a very regular fashion, we make it feasible to operate on it with very concise high-level languages. This approach was first demonstrated with the relational model of data (Date [1977]), which is probably the simplest model with respect to the mechanisms it provides for expressing relationships among data items. The use of such high-level languages makes it very easy to develop new applications that mainly involve queries, even when the queries use portions of the database that were developed independently. These high-level languages may also help somewhat in avoiding programming errors and maintaining the logical integrity of the database.

Because databases represent real-world objects and relationships, changes in the world (or in our preferred abstraction of it) may force a change in the structure of an existing database. For example, we may have to add a new field to each record of a given type, or delete an existing field. A stronger form of data independence holds when any application that isn’t necessarily affected by some alteration in the conceptual model mentioned above is functionally immune to the change. (It is impossible for a nontrivial application to be immune to all possible alterations, because some of the data that it interprets may be expunged in a change of the conceptual model.) This degree of data independence requires a layer of mapping between the conceptual model and the external model presented to an application. Such a map is called a view. There may be many views that involve the same underlying data; views also allow different external models to be used while keeping a common conceptual model. It is not generally possible to perform an update through a view unless the view is very simple.

Is it productive to view the data structures and variables found in normal Mesa programming as database variables that don’t happen to be persistent, shared, or large? To be more concrete, is the distinction between Mesa records and database objects really necessary?

To some extent this is a function of our aspirations. If we consider persistence to be the primary goal, with sharing and largeness being much less important, then we may be satisfied with a database that is essentially a long-term Mesa virtual memory. If the typing of data objects in this memory could be preserved automatically over long periods, the results would have some of the character of a database.

JaM, Interlisp and Smalltalk are examples of existing systems at PARC that support this kind of persistent virtual memory. Databases built in these environments can be very flexible by normal database standards. The user is able to create arbitrarily complex data structures and is able to bind procedures to individual data objects, giving a programmable view mechanism (in the sense of the section above). JaM, Interlisp and Smalltalk do not have a conventional database system’s facilities for ensuring integrity, do not allow concurrent access, and don’t support large databases (by the standards of "Business Data Processing" applications).

Physical integrity is aided by storing data on the Alpine file system (or Juniper, which we use right now). Declarations live in the database, and are read using the same interface as the rest of the database. (This commonality of interface is not true for updates, for consistency reasons).

Concurrent access will be provided by using page-level locking on Alpine. Since this does not allow the locking of logical units of data, it will perhaps not support very high degrees of concurrent access efficiently; we won’t know any more about this without getting some experience. We expect the database to be used in an integrated way (although probably not at first, until confidence is built up.) The initial protection mechanism will be based on file protection. This is not ideal, but the best way to improve it may be to build finer-grained protection at a level above the interface we are now developing.

The database may get large in the sense that it occupies a large portion of a disk volume, but we do not expect that 24 hour real-time performance will be necessary. Thus we will be satisfied with fairly crude algorithms for responding to restructuring requests that appear to affect large volumes of data (but in principle could be handled by a more sophisticated incremental algorithm.) We do not plan to use very sophisticated algorithms to gain good performance for queries involvong huge amounts of data. We shall assume that the amount of data used to process a query will just about fit in main storage. We are primarily concerned with interactive systems rather than "data processing" applications that might involve scanning a huge database. Our performance aspirations are also limited by the bandwidth available to our file server (though we shall do local caching of file pages to reduce this traffic).

This is true in our system to a large extent. The presence or absence of indexes ("inverted files") is not reflected in the statement of algorithms. Declarations are used to specify indexes, which are then maintained automatically by the system. The model does contain a form of pointer, but much of its underlying mechanism is abstracted away.

The model of data is a simple extension of the relational data model. It consists of records, integers, strings, and atoms. Cypress helps maintain the logical integrity of the data by checking type constraints on these data. One goal of this document is to explain how to represent information within the Cypress data model in a well-structured way.

These are part of the next phase of development of Cypress. Our current interface allows only one-at-a-time operations on data that are explicitly stored; this functionality is quite adequate for many applications. We shall build aggregate operations and multiple views of data on top of this interface.

A database is a time-varying collection of data, all of which is stored as relationships and entities. A relationship is the database analogue of a Cedar record, and an entity is the database analogue of a Cedar atom. Fields of relationships are called attributes. Attributes may take on integer, string, boolean, and entity values. We do not allow any analogue of variant records for relationships. We also exclude the possibility of a "repeating" attribute, that is, an attribute whose value is a sequence of data values.

The database package provides operations for creating new relationships and entities of a specified type, and for destroying them. Other operations allow the value associated with any particular attribute of a given relationship to be fetched or updated.

We can contrast database relationships with Mesa records as follows. First, in the database model there is a mechanism that allows all relationships of a given type to be retrieved. This means that no tuple ever becomes "garbage", since there is always an access path to it. With a Mesa record, once the last user-maintained pointer to a record disappears the record is truly inaccessible. Second, it is possible to locate all of the tuples that reference a given atom or have a given range of integer or string values; this is not true with Mesa records. Third, nesting of relationships is not allowed; a Mesa record may contain a component that is also a Mesa record, or a pointer to one. Fourth, there is no analogue of variant records for tuples in the phase one implementation, although there is a hierarchy of types of entities (atoms).

A database is represented as a collection of files. A file in database format is called a segment. The segments comprising a database are identified by the client of the system. The set of segments may dynamically change, the segments are physically independent and may be independently opened, closed, and modified.

All of the relationships or entities of some client-created type lie in a single segment, which must be specified when the type is defined. This partitioning provides a crude mechanism for clustering related data, and may reduce the potential for conflict in concurrent accesses to a database by different applications. A default segment is provided for clients who don’t care about segment structure.

The phase two Cypress system is not integrated with Mesa; the data manipulation operations sketched above are implemented as Mesa procedures in the interface. This leaves the problem of declarations: how do we create new relations and domains, or access existing ones? The answer is to define a small number of system entities to contain information about types.

This technique for storing the "data dictionary" type information has the advantage that the same interface is used for data dictionary retrieval as for normal data retrieval. We do not extend the commonality of interface to updates, since the consistency of the types of the stored data is difficult to ensure without constraints on the type updates.

The database package uses the notion of transaction to structure database accesses. Clients can ensure the logical integrity of their databases, even in the face of concurrent access, by proper grouping of queries and updates into transactions.

Transactions do not always succeed. Sometimes this is due to hardware or software failures, and sometimes due to conflicts in concurrent accesses. Concurrent updates to data in different segments almost never cause a conflict; data within the same segment are also arranged to minimize the potential for conflicts. But all clients must be prepared for the possibility of an aborted transaction. By far the simplest response to a transaction abortion is to restart the transaction from the beginning (though this may be painful when the updates were performed manually).

Database protection is limited to the protection provided for segments by the file system. This has its strong and weak points. On the positive side, file protection is a robust mechanism. Since it is implemented on a remote host, the malfunction of a user program cannot breach it. Users in our environment have experience with file protection and they trust it.

The Cypress system uses Alpine or the local Pilot file system to store the database. All of the database software will run in the client machine; thus the system’s speed may depend a great deal upon the amount of main memory available on the client machine for caching database pages, as well as on the raw speed of the client machine.