DIRECTORY RefID USING [ID], Rope USING [ROPE], RPC USING [Conversation]; LoganBerry: CEDAR DEFINITIONS ~ BEGIN ROPE: TYPE ~ Rope.ROPE; AttributeType: TYPE = ATOM; AttributeValue: TYPE = ROPE; Attribute: TYPE = RECORD[ type: AttributeType, value: AttributeValue ]; Entry: TYPE = LIST OF Attribute; LogID: TYPE = [0..255]; activityLog: LogID = FIRST[LogID]; -- default log for updates Cursor: TYPE = RefID.ID; CursorDirection: TYPE = {increasing, decreasing}; OpenDB: TYPE = RefID.ID; SchemaInfo: TYPE = RECORD[ dbName: ROPE, -- name of database schema file keys: LIST OF AttributeType, -- available indices, the primary key is listed first indexNames: LIST OF ROPE, -- names of index files logs: LIST OF LogID, -- logs comprising the database logNames: LIST OF ROPE -- names of log files ]; Conv: TYPE = RPC.Conversation; Error: ERROR [ec: ErrorCode, explanation: ROPE _ NIL]; ErrorCode: TYPE = ATOM; Open: PROC [conv: Conv _ NIL, dbName: ROPE] RETURNS [db: OpenDB]; Describe: PROC [conv: Conv _ NIL, db: OpenDB] RETURNS [info: SchemaInfo]; ReadEntry: PROC [conv: Conv _ NIL, db: OpenDB, key: AttributeType, value: AttributeValue] RETURNS [entry: Entry, others: BOOLEAN]; EntryProc: TYPE = PROC [entry: Entry] RETURNS [continue: BOOL]; EnumerateEntries: PROC [db: OpenDB, key: AttributeType, start: AttributeValue _ NIL, end: AttributeValue _ NIL, proc: EntryProc] RETURNS []; GenerateEntries: PROC [conv: Conv _ NIL, db: OpenDB, key: AttributeType, start: AttributeValue _ NIL, end: AttributeValue _ NIL] RETURNS [cursor: Cursor]; NextEntry: PROC [conv: Conv _ NIL, cursor: Cursor, dir: CursorDirection _ increasing] RETURNS [entry: Entry]; EndGenerate: PROC [conv: Conv _ NIL, cursor: Cursor] RETURNS []; WriteEntry: PROC [conv: Conv _ NIL, db: OpenDB, entry: Entry, log: LogID _ activityLog, replace: BOOLEAN _ FALSE] RETURNS []; DeleteEntry: PROC [conv: Conv _ NIL, db: OpenDB, key: AttributeType, value: AttributeValue] RETURNS []; Close: PROC [conv: Conv _ NIL, db: OpenDB] RETURNS []; BuildIndices: PROC [conv: Conv _ NIL, db: OpenDB] RETURNS []; CompactLogs: PROC [conv: Conv _ NIL, db: OpenDB] RETURNS []; END. )’LoganBerry.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Doug Terry, March 6, 1986 11:11:43 am PST LoganBerry is a simple facility for managing databases. Data is stored in one or more log files and indexed using stable btrees. This "poor man's" database facility is intended to allow various types of data to be stored persistently. A database survives processor crashes, but the data management facility does not provide atomic transactions. Only very simple queries are supported: retrieval by key or key subrange. Databases may be shared by multiple clients and accessed remotely via RPC. Data representation The database is maintained as a collection of entries, where each entry is a set of type:value attributes. Both the type and value of an attribute are simply text strings (i.e. ROPEs). However, the programmer interface treats attribute types as ATOMs. For instance, a database entry pertaining to a person might be [$name: "Doug Terry", $phone number: "494-4427", $workstation: "Lake Champlain"]. Database entries are stored in a collection of logs. A database is updated by appending an entry to the end of a log, log entries are never overwritten (except when a log is compacted or replaced in its entirety). Updating individual attributes of an entry requires rewriting the complete entry. In many cases, all of the logs are readonly except for a single activity log. All updates are applied to the activity log unless the client explicitly controls which logs are written. Access methods Only key-based access methods are supported on a database. These are provided by btrees. A separate btree index exists for each attribute type that serves as a key for the database. A sequence of database entries, sorted in btree order, can be accessed using either an enumerator or generator style of retrieval. Generators employ a cursor to indicate a logical position in the sequence being retrieved. A cursor can be used to traverse a sequence in increasing or decreasing order. Database schema A database must be "opened" before any of its data can be accessed. The Open operation reads a database schema, which contains information about all logs and indices that comprise a database, and returns a handle that identifies the database in subsequent operations. A schema is created by clients of this package and stored in a DF file that can be used to backup the database. Lines of the file starting with "-->" are deemed to contain schema information for the file named in the subsequent line of the DF file or at the end of the same line. The two types of schema entries are as follows: --> log --> index The following is a sample database schema file: ============================ -- SampleDB.df Directory [Indigo]Backups>Top> SampleDB.df!3 12-Aug-85 13:16:12 PDT Directory [Indigo]Backups>SampleDB> --> log 0 readwrite Activity.log!2 12-Aug-85 12:07:24 PDT --> log 1 readonly Readonly.log!1 5-Aug-85 11:50:51 PDT --> index "Name" primary Name.index ============================ Basic operations All of these operations (except EnumerateEntries) can be invoked via RPC. They take a RPC.Conversation as the first argument so that secure remote procedure calls can be made to a LoganBerry database server; see LupineUsersGuide.tioga for information on establishing secure conversations. Errors raised during the execution of an operation indicate uncommon or abnormal conditions. Clients should be prepared to catch these. The possible ErrorCodes are: $BadSchema, -- the schema can not be parsed $CantOpenSchema, -- the schema file could not be opened $BadDBHandle, -- an invalid OpenDB handle was passed to some routine $BadCursor, -- an invalid cursor was passed to some routine $NoIndex, -- the key presented in a read or delete operation has no associated index $NoPrimaryKey, -- a new entry being written does not contain a primary key $ValueNotUnique, -- a new entry being written contains the same primary key value as an existing entry, or the value supplied for a delete does not uniquely specifiy an entry $CantOpenLog, -- a log file could not be opened $BadLogEntry, -- a log entry is of the wrong format $LogReadOnly, -- the specified log can not be updated $InvalidReplace, -- an entry being replaced is in a different log than its replacement $CantOpenIndex, -- a btree file could not be opened $BadIndex, -- a btree index is corrupted $DBClosed, -- the database has been closed $DBNotAvailable, -- the database has been taken out of general service $InternalError -- indicates some miscellaneous internal error Initiates database activity and checks for consistency. This can be called any number of times to get a new OpenDB handle or reopen a database that has been closed. Indices are automatically rebuilt if any are missing or if a partially-completed update left them out-of-date. Errors: CantOpenSchema, BadSchema, CantOpenLog, BadIndex Returns schema information about the database. Errors: BadDBHandle Returns an entry that contains the given attribute value for the given key; returns NIL if none exists. If the key refers to the primary index then the unique entry is returned and `others' is FALSE. If the key is secondary and several entries exist with the same value for the key, then an arbitrary entry is returned and `others' is set to TRUE; use EnumerateEntries to get all of the matching entries. Errors: BadDBHandle, NoIndex, DBClosed, BadIndex, BadLogEntry Calls `proc' for each entry in the specified range of key values. The enumeration is halted when either the range of entries is exhausted or `proc' returns FALSE. A NIL value for `start' represents the least attribute value, while a NIL value for `end' represents the largest attribute value. Thus, the complete database can be enumerated by specifying start=NIL and end=NIL with `key' equal to the primary key. WARNING: THIS ROUTINE CAN NOT BE USED ACROSS AN RPC CONNECTION; USE GenerateEntries INSTEAD. Errors: BadDBHandle, NoIndex, DBClosed, BadIndex, BadLogEntry Similar to EnumerateEntries, but creates a cursor so that entries in the specified range of key values can be retrieved using NextEntry (defined below). Initially, the cursor points to the start of the sequence. A NIL value for `start' represents the least attribute value, while a NIL value for `end' represents the largest attribute value. Thus, the complete database can be enumerated by specifying start=NIL and end=NIL with `key' equal to the primary key. Errors: BadDBHandle, NoIndex Retrieves the next entry relative to the given cursor. The cursor, and thus the sequence of desired entries, must have been previously created by a call to GenerateEntries. The cursor is automatically updated so that NextEntry may be repeatedly called to enumerate entries. NIL is returned if the cursor is at the end of the sequence and dir=increasing or at the start of the sequence and dir=decreasing. Errors: BadCursor, DBClosed, BadIndex, BadLogEntry Releases the cursor; no further operations may be performed using the given cursor. This must be called once for every call to GenerateEntries. Adds a new entry to the database. The entry is added to the activity log unless another log is explicitly requested. The entry must have an attribute for the primary key. The primary attribute value must be unique throughout the database unless replace=TRUE; in this case, an existing entry with the same primary attribute value is atomically replaced with the new entry (both must reside in the same log). Errors: BadDBHandle, NoPrimaryKey, ValueNotUnique, LogReadOnly, InvalidReplace, DBClosed, BadIndex Deletes the entry that contains the given attribute value for the given key. If the key is for a secondary index and the value is not unique then an Error[ValueNotUnique] is raised. Deletes are actually performed by logging the delete request (so that the log can be replayed at a later time) and then updating all of the indices. Errors: BadDBHandle, NoIndex, DBClosed, BadIndex, ValueNotUnique, LogReadOnly, BadLogEntry Terminates database activity and closes all log and index files. Databases are always maintained consistently on disk so it doesn't hurt to leave a database open. The main reason for calling Close is to release the FS locks on the log files so they can be manually edited. WARNING: THIS SHOULD NOT BE CALLED IF THE DATABASE IS BEING SHARED BY MULTIPLE CLIENTS. Errors: BadDBHandle Maintenance operations An important feature of the btree-log design is: the log is the truth! Thus, the database facility need only worry about maintaining a consistent set of logs in the presence of processor crashes. Logs are fully contained. In the event of inconsistencies arising between the logs and their indices, the associated btrees can be easily rebuilt by reading the logs. Rebuilds the indices by scanning the logs and performing WriteEntry or DeleteEntry operations. Removes deleted entries from the logs by enumerating the primary index and writing new logs. Doug Terry August 12, 1985 11:58:15 am PDT created Doug Terry, October 22, 1985 11:26:03 am PDT changes to: DIRECTORY, Cursor, OpenDB Doug Terry, November 19, 1985 10:13:47 pm PST changes to: BuildIndices Doug Terry, November 20, 1985 11:31:42 am PST changes to: DeleteEntry, BuildIndices Doug Terry, November 26, 1985 8:16:02 pm PST changes to: LoganBerry, ErrorCode, ReadEntry, EnumerateEntries, GenerateEntries, NextEntry, WriteEntry, DeleteEntry, Close Doug Terry, January 20, 1986 10:44:06 am PST changes to: Conv, Error, Open, ReadEntry, GenerateEntries, NextEntry, EndGenerate, WriteEntry, DeleteEntry, Close, BuildIndices, CompactLogs, DIRECTORY Doug Terry, January 23, 1986 3:16:08 pm PST changes to: Close, ErrorCode, Open, ReadEntry, EnumerateEntries, NextEntry, WriteEntry, DeleteEntry Doug Terry, February 26, 1986 6:23:04 pm PST changes to: Open Doug Terry, February 27, 1986 7:42:44 pm PST changes to: ErrorCode changed to be ATOMs rather than an enumerated type. Doug Terry, February 28, 1986 4:37:47 pm PST changes to: WriteEntry so that atomic replacement of complete entries is possible. Doug Terry, March 5, 1986 4:54:59 pm PST changes to: SchemaInfo, Describe was introduced so that clients, e.g. the browser, can obtain information about the database schema. Doug Terry, March 6, 1986 11:11:43 am PST changes to: ErrorCode, WriteEntry ส1˜codešœ™Kšœ ฯmœ1™——™Mšœfฯz œF™ทM™šœ˜ฃœ™ฎM™Mšœžœ ˜Mšœžœ˜1——šœ™šœiฃœ™ŒM˜Mšœžœ ˜M˜šœ žœžœ˜Mšœžœข˜.Mšœžœžœข5˜SMšœ žœžœžœข˜2Mšœžœžœ ข˜5Mšœ žœžœžœข˜-M˜——M™šœษ™ษKšœ@™@Kšœ?™?—K™™/K™KšœŒ™ŒK™——šœ™Kšœก™กK™Kšœžœžœ˜K˜K™ˆK˜Kšœžœžœžœ˜6šœ žœžœ˜Kšœ™Kšœ ข™,Kšœข&™8Kšœข6™EKšœ ข/™—K˜š ฯnœžœžœ žœžœ˜AKšœ•™•Kšœ8™8—K˜šคœžœžœžœ˜IK™.Kšœ™—K˜š ค œžœžœ9žœžœ˜‚Kšœ–™–Kšœ=™=—K˜Kš ค œžœžœžœ žœ˜?K˜š คœžœ:žœžœžœ˜ŒKšœž™žKšกDœก ™\Kšœ=™=—K˜š คœžœžœ:žœžœžœ˜šKšœฯ™ฯKšœ™—K™šค œžœžœ5žœ˜mKšœ—™—Kšœ2™2—K˜šค œžœžœžœ˜@Kšœ™—K˜š ค œžœžœ?žœžœžœ˜}Kšœ€žœ–™šKšœb™b—K˜šค œžœžœ9žœ˜gKšœฬ™ฬKšœZ™Z—K˜šคœžœžœžœ˜6K™’KšกX™XKšœ™——šœ™Jšœํ™ํIblock˜šค œžœžœžœ˜=Kšœ^™^—K˜šค œžœžœžœ˜