We hope that this paper will be read by potential users of the Cypress database system. It is certainly required reading for those who want to make use of the system now.

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.

The discussions above were limited to immediate results of the three basic properties. We now deal with some of the more indirect consequences.

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).

In this section, we give an informal description of the Cypress data model. We are dealing with a conceptual data model, the language used to define and access the types of objects and relationships between them. This should be carefully distinguished from a physical data model, the data structuring mechanisms we are given for actual storage and access of data. The physical data model is hidden as much as possible from the database client to facilitate data independence, the guarantee that a user's program will continue to work (perhaps with a change in efficiency) even though the physical data representation is redesigned.

For any particular database using the given conceptual and physical models, the actual specifications of this database using the primitives the models provide are termed the conceptual data schema and physical data schema. Note that a mapping must be provided between the conceptual and physical levels, either automatically or with further instruction from the client; we will do some of both. The logical to physical mapping is intimately associated with the performance of the database system as viewed by the user performing operations at the conceptual level. Performance is generally not a criteria for choosing between conceptual data models, unless there is no known way to map the differing conceptual views into the same or equally efficient implementations.

Three basic primitives are defined in the model: an entity, datum, and relationship. An entity represents an abstract or concrete object in the world: a person, an organization, a document, a product, an event. In programming languages and knowledge representation entities have variously been referred to as atoms, symbols, nodes, and objects. A datum, unlike an entity, represents literal information such as times, weights, part names, or phone numbers. Character strings and integers are possible datum types. Actually, it is a policy decision as to whether something is represented as an entity or merely a datum: e.g., an employee's spouse may be represented in a database system as a datum (the spouse's name), or the spouse may be an entity in itself. The database system provides a higher level of logical integrity checking for entities, as we will see later.

In some programming languages, an entity is just another type of datum, like numbers and strings. To allow more preciseness, we will instead use the term value to refer to something that can be either a datum or entity.

A relationship is a tuple whose elements are [entity or datum] values. In programming languages, a relationship is commonly termed a record. As in most programming languages, we can refer to the elements (fields) of tuples by name instead of position. These names for positions are called attributes.

We also define entity types, datum types, and relationship types: domains, datatypes, and relations, respectively. We make use of these three types through one fundamental type constraint: for every relation, we define the number and types of attributes expected of relationships of that type. That is, every relationship in a given relation must have the same attributes, and the values associated with each attribute must be from a pre-specified domain or datatype. For example, a member relation might specify that a given person is a member of a given organization with a given job title as in the figure following. The person and organization might be entities, while the title might be a string datum. We relax the fundamental type constraint somewhat in allowing a lattice of types of domains: a particular value may then belong to the pre-specified domain or one of its sub-domains. For example, one could be a member of a University, a Company, or any other type of Organization one chooses to define. Other relations, e.g. an "offers-course" relation, might apply only to a University.

<==<ViewFig1.press<

Relationships represent facts about the world. A relation (a set of relationships) represents a kind of relationship in which entities and values can participate. We will schematically represent that John Smith is a member of Acme company with title "manager" by drawing lines for the relationship (labelled with the relation and its attributes), a circle for each entity, and a box for the datum:

<==<ViewFig2.press<

The reader should normally think of relations as types, not sets. A relation can be defined as the set of all relationships of its type, however, and thus can be treated as a relation in the normal mathematical sense. Note that we differ from mathematical convention in another minor point: the use of attributes to refer to tuple elements by name instead of position. Reference by position is therefore not necessary and is in fact not permitted. We can often omit attribute names without ambiguity since the types of participating entities imply their role in a relationship. However, they are necessary in the general case; e.g., a boss relation between a person and a person requires the directionality to define its semantics.

We can summarize the six basic primitives of the data model in tabular form. Familiarity with these six terms is essential to understanding the remainder of this document:

Domains, datatypes, and relations are types but can also be viewed as sets.

The data model also provides primitives to specify uniqueness of relationships and entities. For relationships, this is done with keys, and for entities, with names. A key for a relation is an attribute or set of attributes whose value uniquely identifies a relationship in the relation. No two relationships may have the same values for a key attribute or attribute set. A name acts similarly for a domain. The name of an entity must uniquely specify it in its domain.

Consider a spouse relation, a binary relation between a person and a person. Both of its attributes are keys, because each person may have only one spouse (if we choose to define spouse this way!). For an author relation, neither the person nor the document are keys, since a person may author more than one document and a document may have more than one author. The person and document attributes together would comprise a key, however: there should be only one tuple for a particular person-document pair.

<==<ViewFig3.press<

We have labelled entities with names in the figures. Names are most useful when they are human-sensible tags for the entities represented, e.g. the title for a document, or the name of a person. However, their primary function is as a unique entity identifier, so non-unique human-sensible names must be represented in some other manner (via relations).

Note that the only information about an entity associated directly with the entity is the name; this contrasts with most other data models. A person's age or spouse, for example, would be represented in the Cypress data model via age or spouse relations. Thus the relationships in a database are the information-carrying elements: entities do not have attributes. However the model provide an abbreviation, properties, to access information such as age or spouse in a single operation. We will discuss properties later. In addition, the physical data modelling algorithms can store these data directly with the person entity as a result of the relation key information (since a person can have only one age, a field can be allocated for it in the stored object representing a person.)

A common topic in the database literature is relational normalization (Beeri et al [1978], Codd [1970], Fagin[1977, 1981], Rissanen [1977], Biller[1979], Hall et al[1976]). A relation is normalized by breaking it into two or more relations of lower order (fewer attributes) to eliminate undesirable dependencies between the attributes. For example, one could define a "publication" relation with three attributes:

This relation represents the fact that John and George wrote a book together entitled "Backgammon for Beginners", published in 1978, and Mary wrote two books on the subject of chess, in 1981 and 1982. Alternatively, we could encode the same information in two relations, an author relation and a publication-date relation:

Although the second two relations may seem more verbose than the first one, they are actually representationally better in some sense, because the publication dates of books are not represented redundantly. If one wants to change the publication date of "Backgrammon for Beginners" to 1979, for example, it need only be changed in one place in the publication-date relation but in two places in the publication relation. This latter kind of behavior is called an update anomaly. The second two relations are said to be a normalized form (as it happens, third normal form) of the first relation, and thereby avoid this particular kind of update anomaly.

A variety of successively stricter criteria for normalization have been developed and studied, dependent on the kinds of real-world dependencies between attributes. Relational normalization is not part of the Cypress data model. However the model's operations (and the tools we will develop in the implementation) encourage what we will call functionally irreducible form, in which relations are of the smallest order that is naturally meaningful. This form is in some sense the most fully normalized canonical form that could be defined.

Functionally irreducible normal form cannot be defined simply syntactically, but rather requires resort to the semantics of relations. Specifically, the presence or absence of a relationship in a relation represents the truth of some predicate on the state of the represented world (see Kent [1979]). For example, a "member" relationship represents the fact that a particular person is a member of a particular organization. (The absence of such a relationship may mean falsity of that predicate or lack of knowledge; we fortunately need not concern ourselves with this distinction here). We will formally define irreducible form in Section 3. For informal purposes, it suffices to say that relations should be of the smallest order that is possible without introducing a new artificial domain not otherwise desired (all relations can be reduced to binary by introducing artificial domains). We will allow a slight weakening of irreducible form, called functionally irreducible form, which permits combining two or more irreducible relations that must all be logically present or absent in the real world. For example, a birthday relation between a person, month, day, and year can be combined instead of using three relations. Operationally defined, then, a relation is in functionally irreducible form iff:

The functionally irreducible relations seen by the user are independent of the physical representation chosen by the system for efficiency, so we are concerned only with the logical data access. Note also that the motivation for the functionally irreducible form is a one-to-one correspondence between the relationships in the database and the atomic facts they represent, a canonical form which is in some sense more natural than any other form.

Like some other database models and a few programming languages, the Cypress model is self-representing: the data schema is stored and accessible just as any other data. Thus application-independent tools can be written without coded-in knowledge of the types of data and their relationships, by reading the meta-representation at run-time.

The pre-defined domains are:

The pre-defined relations are the Subtype relation and the Attribute relation. The Subtype relation has one element (relationship) per domain - subdomain relationship, with two attributes referencing the domain and subdomain, respectively. The Attribute relation has one element per client-defined attribute. The Attribute relation's attributes and their values are:

Primitive operations

The data model provides the capability to define and examine the data schema, and perform operations on entities, relationships, and aggregates of entities and relationships.

Five basic operations are defined for entities:

Five basic operations are defined for relationships:

The RelationSubset operation enumerates all the relationships in a relation satisfying specified equality constraints on entity-valued attributes and/or range constraints on datum-valued attributes.

The DomainSubset operation enumerates all the entities in a domain. The list may optionally be sorted by entity name, or restricted to a subset of the entities with a name in a given range.

More complex queries are implemented by a query language based on these primitive query mechanisms.

As well as the basic operations described in the previous sub-sections, four more convenient but specialized operations may be defined in terms of these by an implementation of the data model:

As an example of the use of properties, consider the following database, consisting of two member relationships and an age relationship:

<==<ViewFig4.press<

On this database, the GetProperty and SetProperty operations work as follows:

A view is a relation whose relationships are not actually stored. Instead, the primitive retrieval and storage operations on a view invoke procedures defined by a database client who defines the view. Arbitrary procedures may be defined, and views can therefore be used for a variety of purposes:

The implementor of a view must define all of the operations on a relation. Unlike view mechanisms in some database systems, views may be defined directly in the underlying programming language. In our case, this is Cedar Mesa, and the operations the implementation must export are defined as a Cedar Mesa interface exported by the view. The view can be dynamically loaded when required at run-time. The operations the view provides are the same as those for relations:

When a query language is defined, a view may be defined at a higher level rather than the underlying programming language; this simplifies the definition of views as well as allowing some kinds of optimizations that need no longer treat a view as a "black box" implementation of an access definition.

Views are so-called because they provide a database client a different view of the database than what was originally stored. View definitions and implementations are stored in a database as any other data, being automatically retrieved when required by the database system.

Partial augments correspond to what we call level 1 augments. These are the augments described in the implementation section.

Augments provide a mechanism to divide and re-combine databases to give different perspectives or subsets of the data to different users or application programs. An augment is a set of entities and relationships that a database client chooses to treat as one logical context or state of the world. The data in an augment is stored in an underlying file physically independent from other augments, perhaps on another machine. However we will see that the entities of a domain may logically be in more than one augment, and the entities in an augment may be from more than one domain. Relations and relationships behave similarly.

Augments may be used for four purposes:

We will re-examine these four goals (database distribution, database independence, additive databases, and versions) later. First we examine partial augments, which satisfy some but not all of these goals.

The data model provides the following operations on augments:

We now extend the DeclareDomain and DeclareRelation operations to have an additional argument, namely the augment in which the defined domain or relation will reside. The entity representing a domain or relation now represents data in a particular augment. However, a logical correspondence is maintained by the system between relations or domains with the same name in two or more augments in the currently open augment list. We define the namesake in augment Q of a domain or relation as the domain or relation with the same name in Q. The namesake in a particular augment may of course be non-existent. Similarly, we define the namesake in augment Q of an attribute A to be the attribute of A's relation's namesake in Q with the same name as A. All of the namesakes of a relation must have attributes identical in name, type, and uniqueness or an error is generated on the first attempt to use that relation. Finally, we will refer to the namesake of any entity E in an augment Q as the entity with the same name in E's domain's namesake in Q.

The effect of the namesake equivalence will be the very useful property that a relation or domain may logically span two or more augments while the augments remain physically independent.

With the addition of augments to the data model, we redefine the semantics of basic access operations as follows.

Full augments correspond to what we call level 3, or subtractive, augments. They are included for future interest, but their implementation is not described.

Note that augments as defined thus far provide some aid to a database application in allowing relations and domains to cross segment boundaries, but do not carry this illusion through to completion. We will refer to these as partial augments. The merit of partial augments over a more complete illusion is that they are simpler to understand and have good performance in an implementation. They satisfy only the first two of the purposes of augments outlined at the beginning of the previous section, however. The third and fourth uses of augments could of course be satisfied by writing application programs which simulate these effects: public / private databases, in which a relation may have private and public relationships, are relatively easy to simulate in this way. However we will also define a higher level of aspiration, namely simulating in the data model relations and domains that appear to span augment boundaries, and can even be updated in a different augment than the data is defined. We will call these augments full augments.

An implementation of the database model with full augments has the same properties and definitions just enumerated for partial augments with the following modifications:

Full augments also act specially upon relations upon which keys have been defined:

The net effect of our definition of full augments is that a user or program may make arbitrary modifications to data in an underlying augment, in a fashion which appears exactly as if a single augment contains all the data. The underlying augment, however, is completely unchanged. The unmodified data may concurrently be examined by another user, or appear to be modified through another user's augment. Furthermore, the modifications made by the same user over time can be separated and later removed. Full augments thus satisfy all four of the purposes of augments set out at the beginning of the previous section.

Note that two augments can be merged in a straightforward way to produce an augment that behaves as the two in the same order in the same place in the current augment list. The augments are merged by combining the elements of the relations and domains in the first augment and their namesakes in the other augment, discarding entities and anti-entities which match and relationships and anti-relationships which match.

Augments are not related in definition or implementation to the atomic transactions which an implementation of the model also provides. However, the reader might find it informative to think of a transaction as a [full] augment defined on top of the current data, which is automatically merged with the data when the transaction is committed. Transactions thus serve as "short-term" augments. The two are useful for entirely different purposes, however.

In this subsection we describe the most important types in the interface. Less pervasive types are treated at the point where they are first used.

An Entity or Relship is not the actual database entity or relationship; they are handles for the actual database objects. All accesses to database objects are performed by calling interface procedures with the handles as parameters. Even comparisons of two entities for equality must be done in this way. The Entity and Relship handles are allocated from storage and automatically freed by the garbage collector when no longer needed.

Storing Mesa data values in tuples presents several problems. First, since we would like to define a single operation to store a new value into a specified attribute of a Relship (for instance), there must be a single type for all values that pass through this "store-value" procedure. This is the type Value above, represented as untyped REFs in Cedar (a REF is a garbage-collected pointer in Cedar). The DataTypes will be discussed in the next section. Entities, strings, integers, and booleans are the types of values the system currently recognizes and allows as attribute values. More precisely, these four types are Entity, ROPE (Cedar strings), REF INT (a REF is a garbage-collectable pointer), and REF BOOL. In the case of an entity-valued attribute, an attribute's type may be AnyDomainType or a specific domain may be specified. The latter is highly preferred, as AnyDomainType is a loophole in the type mechanism and limits the kinds of operations that can be performed automatically by the database system or associated tools. We currently provide no mechanism to store more complex Cedar data structures such as arrays, lists, or records in a database; the database system's data structuring mechanisms should be used instead. (The database system can only provide useful query and update mechanisms if it has knowledge of the data's structure.)

Many procedures in the DBView interface take parameters that describe the type or portion of a data item to be manipulated. The permanent repository of such data about user-defined data in a database is the database's data schema, represented by dictionary entities and their properties. Dictionary entities are members of one of the pre-defined system domains:

Every client-defined domain, relation, or attribute contains a representative entity in these domains. Client-defined datatypes are not currently permitted, so the only entities in this domain are the pre-defined IntType, StringType, and BoolType declared above.

The information about the client-defined domains and attributes are encoded by relationships in the database. Domains participate in the system relation SubTypeRelation, which encodes a domain type hierarchy:

The SubTypeRelation has one element per direct domain - subdomain relationship, it does not contain the transitive closure of that relation. However, it is guaranteed to contain no cycles. That is, the database system checks that there is no set of domains d1, d2, ... dN, N>1, such that d1 is a subtype of d2, d2 is a subtype of d3, and so on to dN, and d1=dN.

The information about attributes is available through use of the pre-defined system attribute relation:

The AttributeRelation and SubTypeRelation can be queried with the ordinary data query operations we will define.

The data schema representation of attributes, relations, domains, and their properties may only be read, not written by the database client. They are written indirectly through the use of procedures for their creation: DeclareDomain, DeclareRelation, DeclareAttribute, and DeclareSubtype. The semantics of the system domains and relations we have discussed will be deferred to the discussion of these procedures later in this section.

B-tree indexes are automatically maintained for domains; that is, an index contains entries for all of the entities in a domain keyed by their name so that sorting or lookup by entity name is quick. Key comparisons are performed in the usual lexicographic fashion. B-Tree indexes are also maintained for relations if explicitly requested by the client.

That completes our description of the system-defined domains, relations, and properties. These contain all of the accessible data about the user-defined data in a database. A client program can read this data using the same interface that the program uses for all other data. Attempts to perform updates through this interface results in an ERROR DictionaryUpdate; all updates are performed explitly by client calls to procedures defined in the next subsections, in order to ensure the consistency of this data.

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 data retrieval and updates, 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 that two transactions may deadlock, in which case one of them must be aborted. So the price paid for concurrent access is that programs be prepared to retry aborted transactions.

One requirement of transactions is that packages used in conjunction with the database can group their operations into the same transaction when this is appropriate. Of course, when this is done the interactions among packages must be understood, since one package might commit the transaction while the other had some persistent data structure in an inconsistent state.

The database system provides the capability to access a database stored on the same machine as the database client, using the Pilot file system (Redell et al [1979]), or on Juniper file servers (Israel et al [1978]). (Juniper will be replaced by Alpine, a new transaction-based file server, when that project is completed.) There is currently only one public and one private transaction per instance of the database software on a client machine. All data on a server is accessed via the public transaction; all data on the client's machine via the private one. This single-transaction scheme is a major simplification of the package itself, and also removes the need to pass a Transaction on every call to procedures in the interface.

This is how the database package uses transactions. An OpenDatabase and OpenTransaction call start the database session. A transaction is either passed in by the client, or created by the database package (the latter is just a convenience feature). The operation MarkTransaction below forms the end of a database transaction and the start of a new one; this is implemented by executing a "checkpoint" (commit and hold read locks) on the Juniper file server, or by closing and re-opening the transaction on the Pilot file system. The operation AbortTransaction may be used to abort a transaction. The public and private transactions supported by the database system are independently opened, committed, or aborted. The segments in which data are stored may not be opened for use until the appropriate transaction (local or remote, depending on the location of the segment) has been opened. The operation CloseDatabase commits all transactions, closes all segments, and kills any transactions created by the package.

Clients must decide when to tell the system that a transaction is complete, and must be prepared to deal with unsolicited notification that the current transaction has been aborted because of system failure or lock conflict. Note that when the database package cooperates with other packages under the same transaction, a database transaction may be forced to abort because of the failure of some activity in the other package that is part of the same transaction.

The client's interaction with the database system begins with a call to OpenDatabase and ends with a call to CloseDatabase:

OpenDatabase informs the database system of the clients name and password, and various system parameters: nCachePages tells the system how many pages of database to keep in virtual memory on the client's machine, nBytesInitial is the initial size to assign to segments, and nBytesPerExtent is the incremental increase in segment size used when a segment is full. OpenDatabase should be called before any other operation in the interface. CloseDatabase closes the database session, commiting and destroying any open transactions and closing any open database files.

If useTrans is NIL then OpenTransaction establishes a new connection and transaction with the corresponding (local or remote) file system. Otherwise it uses the supplied transaction. In either case, OpenDatabase returns the resulting transaction. If a transAbort procedure is passed to OpenTransaction then it is called when the transaction is spontaneously aborted (currently, the local transaction is never spontaneously aborted). Any database operations after a transaction abort will invoke the ABORTED signal. The client's transAbort procedure should block any further database operations and wait for completion of any existing ones. Then it may re-open the aborted transaction by calling OpenTransaction again. When the remote transaction is successfully re-opened, the client's remote database operations may resume. Operations on data in local segments may proceed even when the remote transaction has been aborted or is not open, and vice versa.

In addition to the opening and closing of transactions by OpenTransaction and CloseDatabase, transactions may be manipulated by the procedures:

AbortTransaction aborts the current database transaction, either local and remote. The effect on the database is as if the transactions had never been started, the state is as it was just after the OpenTransaction call or most recent MarkTransaction call. A call to OpenTransaction is necessary to do more database operations, and all user variables referencing database items created or retrieved under the corresponding transaction must be re-initialized (they may reference entities or relationships that no longer exist, and in any case they are marked invalid by the database system).

MarkTransaction commits the current database transaction, and immediately starts a new one. User variables which reference database entities or relationships are still valid. When the local or remote transaction is committed, the other is unaffected.

After an OpenDatabase and OpenTransaction, but before database operations may be invoked, the client must open the file(s) in which the data are stored. Database files are called segments. Segments are represented as Cedar ATOMs whose name is the full path name of the data file, minus the implicit extension ".database". If the file is on the local file system, its name is preceded by "[Local]". For example, "[Local]Foo" refers to a segment file on the local disk named Foo.database; "[Juniper]<CedarDB>Baz refers to a segment named Baz.database on the <CedarDB> directory on the Juniper server. It is generally a bad idea to access database files other than through the database interface. However, because segments are physically independent and contain no references to other files by file identifier or explicit addresses within files, the segment files may be moved from machine to machine or renamed without effect on their contents. If a segment file in a set that comprise a client database is deleted, the others may still be opened to produce a database missing only that segment's entities and relationships.

An segment is opened or closed by the operations OpenSegment and CloseSegment:

The version parameter to OpenSegment defaults to OldOnly to open an existing file. The signal FileNotFound is generated if it does not exist, and the signal IllegalFileName is generated if the directory or machine name is missing from fileName. For the convenience of the client, OpenSegment returns the Cedar ATOM which represents the segment in future database operations (the client can also use Atom.MakeAtom to create the same, but the segment must still be opened before use). If the version NewOnly is passed, a new segment file will be created, erasing any existing one. In this case, a number assigned to the segment by the database administrator must also be passed. The client program can pass version=NewOrOld to open a new or existing segment file; in this case the segment number must also be passed, of course.

A simple client program using the database system might have the form, then:

The definition of the client's data schema is done through a procedural interface, although the schema can be read through the normal data operations defined later. In general, any of the data schema may be extended or changed at any time; i.e., data operations and data schema definition may be intermixed. However, there are a few specific ordering constraints on schema definition we will note shortly. Also, the database system optimizes for better performance if the entire schema is defined before any data are entered. An interactive schema editing tool described in the Squirrel documentation allows the schema to be changed without regard for ordering constraints, by recreating schema items and copying data invisibly to the user when necessary.

All the data schema definition operations take a Version parameter which specifies whether the schema element is a new or existing one. The version defaults to allowing either (NewOrOld): i.e., the existing entity is returned if it exists, otherwise it is created. This feature avoids separate application code for creating the database schema the first time the application program is run.

DeclareDomain defines a domain with the given name and returns its representative entity. The domain is declared to exist in the given segment, or a default local one if none is given. The parameter estRelations may be used to estimate the largest number of relations in which entities of this domain may participate. Currently, an error will be generated at run time if this estimate is exceeded. If the domain already exists and version=NewOnly, the signal AlreadyExists is generated. If the domain does not already exist and version=OldOnly, then NIL is returned. The client may define one domain to be a subtype of another by calling DeclareSubType. This permits entities of the subdomain to participate in any relations in which entities of the superdomains may participate. All client DeclareSubType calls should be done before declaring relations on the superdomains (to allow some optimizations). The error WrongSegment is generated if the sub-domain and super-domain are not in the same segment.

DeclareRelation defines a new or existing relation with the given name and returns its representative entity. The relation is declared to exist in the given segment, or the default one if none is given. If the relation already exists and version=NewOnly, the signal AlreadyExists is generated. If the relation does not already exist and version=OldOnly, then NIL is returned.

DeclareAttribute is called once for each attribute of the relation, to define their names, types, and uniqueness. If version=NewOrOld and the attribute already exists, the database system checks that the new type, uniqueness, and length match the existing attribute. The error WrongExistingAttribute is generated if there is a discrepancy.

The attribute type should either be one of the pre-defined types (IntType, StringType, BoolType, AnyDomainType) or the entity representative for a client-defined domain. For pre-defined types, the actual values assigned to attributes of the relationship instances of the relation must have the corresponding type: REF INT, ROPE, REF BOOL, or Entity. If the attribute has a client-defined domain as type, the attribute values must be entities of the client-defined domain or some sub-domain thereof.

The attribute uniqueness indicates whether the attribute is a key of the relation. If its uniqueness is NonKey, then the attribute is not a key of the relation. If its uniqueness is OptionalKey, then the system will ensure that no two relationships in r have the same value for this attribute (if a value has been assigned). The ERROR NonUniqueKeyValue is generated if a non-unique key value results from a SetP, SetF, SetFS, or CreateRelship call. Key acts the same as OptionalKey, except that in addition to requiring that no two relationships in r have the same value for the attribute, it requires that every entity in the domain referenced by this attribute must be referenced by a relationship in the relation: the relationships in the relation and the entities in the domain are in one-to-one correspondence. Finally, if an attribute's uniqueness is KeyPart, then the system will ensure that no two relationships in R have the same value for all key attributes of R, though two may have the same values for some subset of them. KeyPart is not yet implemented.

Relations, domains, and subdomain relationships may be destroyed by calls to the above procedures. Destroying a relation destroys all of it relationships. Destroying a domain destroys all of its entities and also any relationships which reference those entities. Destroying a sub-domain relationship has no effect on existing domains or their entities; it simply makes entities of domain sub no longer eligible to participate in the relations in which entities of domain super can participate. Existing relations and domains may only be modified by destroying them with the procedures above, with one exception: the operation SetName (described later) may be used to change the name of a relation or domain.

DeclareIndex has no logical effect on the database; it is a performance hint, telling the database system to create a B-Tree index on the given relation for the given indexedAttributes. The index will be used to process queries more efficiently. Each index key consists of the concatenated values of the indexedAttributes in the relationship the index key references. For entity-valued attributes, the value used in the key is the string name of the entity. The version parameter may be used as in DeclareDomain and other schema definition procedures, to indicate a new or existing index. If any of the attributes are not attributes of the given relation then the signal IllegalIndex is generated. Multiple indices on one relation are not implemented.

DeclareProperty provides a shorthand for definition of a binary relation between entities of the domain "of" and values of the specified type. The definitions of type and uniqueness are the same as for DeclareAttribute. A new relation relationName is created, and its attributes are given the names "of" and "is". The "is" attribute is returned, so that it can be used to represent the property in GetP and SetP described later.

Since attributes, domains, and relations are all entities, and datum values are represented as REF ANYs, all type checking must currently be done at run-time. The procedures below indicate illegal arguments by generating the signals IllegalAttribute, IllegalDomain, IllegalRelation, IllegalValue, IllegalEntity, and IllegalRelship, according to the type of argument expected.

DeclareEntity finds or creates an entity in domain d with the given name. The name may be omitted if desired, in which case an entity with a unique name is automatically created. If version is OldOnly and an entity with the given name does not exist, NIL is returned. If version is NewOnly and an entity with the given name already exists, the signal NonUniqueEntityName is generated.

DeclareRelship finds or creates a relship in r with the given attribute values. If version is NewOnly, a new relship with the given attribute values is generated. If version is OldOnly, the relship in r with the given attribute values is returned if it exists, otherwise NIL is returned. If version is NewOrOld, the relship with the given attribute values is returned if it exists, otherwise one is created. If the creation of a new relship violates the key constraints specified by DeclareAttribute, the signal NonUniqueAttributeValue is generated.

DestroyEntity removes e from its domain, destroys all relationships referencing it, and destroys the entity representative itself. Any client variables that reference the entity automatically take on the null value (Null[e] returns TRUE), and cause ERROR NullifiedArgument if passed to database system procedures.

DestroyRelship removes rel from its relation, and destroys it. Any client variables that reference the relationship automatically take on the null value, and will cause ERROR NullifiedArgument if subsequently passed to database system procedures.

SetF assigns the value v to attribute a of relationship rel. If the value is not of the same type as the attribute (or a subtype thereof if the attribute is entity-valued), the ERROR WrongAttributeValueType is generated. If a is not an attribute of rel's relation, IllegalAttribute is generated. If v is an entity from a different segment than rel, it is mapped to its namesakes in rel's segment. That is, v is replaced with the entity with the same name in the domain with the same name in rel's segment. Mapping v may create a new entity in rel's segment. It may also create new domains and subtype relationships in rel's segment, as necessary to make v conform to the domain with the same name as a's type in v's segment.

GetF retrieves the value of attribute a of relationship rel. If a is not an attribute of rel's relation, ERROR IllegalAttribute is generated. The client should use the V2x routines described in the next section to coerce the value into the expected type.

These procedures provide a convenient veneer on top of GetF and SetF that provide the illusion that all relation attributes are string-valued. The effect is something like the Relational data model, and is useful for applications such as a relation displayer and editor that deal only with strings. The semantics of GetFS and SetFS depend upon the actual type of the value v of attribute a:

The same signals generated by GetFS and SetFS, such as IllegalAttribute, can also be generated by these procedures. The signal NotFound is generated in the last case above if no entity with the given name is found.

GetName and SetName retrieve or assign the name of an entity, respecitvely. They may generate the signal NotAnEntity if e is null or not an entity.

DomainOf and RelationOf can be used to find the entity representative of an entity's domain or a relationship's relation, respectively. The signal NotAnEntity is generated if e is null or not an entity. The signal NotARelship is generated if r is null or not a relship.

SegmentOf returns the segment in which an entity or relship is stored. It can be applied to domain, relation, or attribute entities.

Eq returns TRUE iff the same database entity is referenced by e1 and e2. This is not equivalent to the Mesa expression "e1 = e2", which computes Cedar Mesa REF equality. If e1 and e2 are in different segments, Eq returns true iff they have the same name and their domains have the same name.

Null returns TRUE iff its argument has been destroyed, is NIL, or has been invalidated by abortion of the transaction under which it was created.

GetP and SetP are convenience routines for a common use of relships, to represent "properties" of entities. Properties allow the client to think of values stored in relships referencing an entity as if they are directly accessible fields (or "properties") of the entity itself. See the figure on page 10 illustrating properties. GetP finds a relship whose from attribute is equal to e, and returns that relship's to attribute. The from attribute may be defaulted if the relation is binary, it is assumed to be the other attribute of to's relation. If it is not binary, the current implementation will find the "first" other attribute, where "first" is defined by the order of the original calls calls to DeclareAttribute. SetP defaults the from attribute similarly to GetP, but operates differently depending on whether from is a key of the relation. If it is a key, any previous relship that referenced e in the from attribute is automatically deleted. In either case, a new relship is created whose from attribute is e and whose to attribute is v. SetP returns the relship it creates for the convenience of the client. GetP and SetP can generate the same errors as SetF and GetF, e.g. if e is not an entity or to is not an attribute. In addition, GetP and SetP can generate the error IllegalProperty if to and from are from different relations. GetP generates the error WrongPropertyCardinality if more than one relship references e in the from attribute; if no such relships exist, it returns a null value of the type of the to attribute. SetP allows any number of existing relships referencing e; it simply adds another one (when from is a key, of course, there will always be one existing relship).

GetPList and SetPList are similar to GetP and SetP, but assume that any number of relships may reference e with their from attribute. They generate the signal WrongPropertyCardinality if this is not true, i.e. the from attribute is a key. GetPList returns the list of values of the to attributes of the relships that reference e with their from attribute. SetPList destroys any existing relships that reference e with their from attribute, and creates Length[vl] new ones, whose from attributes reference e and whose to attributes are the elements of vl. GetPList and SetPList may generate any of the errors that GetF and SetF may generate, and the error IllegalProperty if to and from are from different relations.

Examples of the use of the property procedures for data access can be found at the end of the previous section. Properties are also useful for obtaining information about the data schema. For example, GetP[a, aRelationIs] will return the attribute a's relation, and GetPList[d, aTypeOf] will return all the attributes that can reference domain d.

The x2V routines convert the various Mesa types to Values. The conversion is not normally required for ropes and entities since the compiler will widen these into the REF ANY type Value.

The V2x routines convert Values to the various Mesa types. The WrongValueType error is raised if the value is of the wrong type. It is recommended that these routines be used rather than user-written NARROWs, as the representation of Values may change. Also, NARROWs of opaque types don't work in the current Cedar compiler.

The basic query operation is RelationSubset. It returns a generator of all the relationships in relation r which satisfy a constraint list of attribute values. The relationships are enumerated by calling NextRelship repeatedly; it returns NIL when there are no more relationships. ReleaseRelshipSet should be called when the client is finished with the query.

The constraint list may be NIL, in which case all of the relationships in r will be enumerated. Otherwise, relationships which satisfy the conjuction of constraints on attributes in the list will be enumerated. If an index exists on some subset of the attributes, the relationships will be enumerated sorted on the concatenated values of those attributes. For a StringType or IntType attribute a of r, the contraint list may contain a record of the form [a, b, c] where the attribute value must be greater or equal to b and less than or equal to c to satisfy the constraint. For any type of attribute, the list may contain a record of the form [a, b] where the value of the attribute must exactly equal b. The special values infString and minfString are defined in the DBView interface, and represent an infinitely large and infinitely small string value, respectively. The signal WrongAttributeValueType is generated by RelationSubset if one of the low or high values in the list is of a different type than its corresponding attribute.

If searchSegments is TRUE, relations in all open segments with the same name as r are searched. The attributes and entity values in avl are automatically mapped to their namesakes in other segments.

DomainSubset enumerates all the entities in a domain. If lowName and highName are NIL, the entire domain is enumerated, in no particular order. Otherwise, only those entities whose names are lexicographically greater than lowName and less than highName are enumerated, in lexicographic order. If searchSubDomains is TRUE, subdomains of d are also enumerated. Each subdomain is sorted separately. If searchSegments is TRUE, d and domains with the same name in all open segments are enumerated.

Just as with relation enumeration, NextEntity is used to enumerate the entities satisfying the DomainSubset, and ReleaseEntitySet should be called upon completion.

This procedures returns a list of all attributes, of any relation defined in d's segment, which reference domain d or one of its superdomains. The list does not include AnyDomainType attributes, which can of course reference any domain. GetDomainRefAttributes is implemented via queries on the data schema. GetDomainRefAttributes is useful for application-independent tools; most specific applications can code-in the relevant attributes.

This procedure returns a list of all attributes in which some existing relship actually references e, including AnyDomainType attributes. This is currently not implemented as specified; the list may include key attributes that do not actually reference e. The ones that actually reference e must be determined by RelationSubset.