LoganBerryStructure.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Doug Terry, February 26, 1986 8:20:02 pm PST
This module contains defintions for the various data structures and formats used by LoganBerry.
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. The database must survive processor crashes, but the data management facility does not provide atomic transactions or concurrency control. Moreover, only very simple queries are supported: retrieval by key or key subrange.
DIRECTORY
BTreeSimple USING [PathStk, Tree],
FS USING [OpenFile],
IO USING [STREAM],
RefTab USING [Ref],
Rope USING [ROPE],
LoganBerry;
LoganBerryStructure: CEDAR DEFINITIONS
~
BEGIN
OPEN LoganBerry;
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;
Logs and btrees
Logs store a time-ordered sequence of database entries separated by end-of-entry markers. An update-complete marker should always be the last byte of a log.
LogAddress: TYPE = INT;
EndOfEntry: CHAR = '\n;
UpdateComplete: CHAR = 377C;
Within a btree index, each btree entry contains an attribute value (the key for the btree), as well as a log identifier and byte offset into the given log. The byte offset indicates the first byte of a database entry containing the particular attribute.
IndexEntry:
TYPE =
RECORD [
log: LogID,
firstByte: LogAddress
];
IndexPtr: TYPE = LONG POINTER TO IndexEntry;
Cursors
Cursors contain the information needed to access a sequence of database entries in btree order.
CursorInfo: TYPE = REF CursorRecord;
CursorRecord:
TYPE =
RECORD[
dbinfo: OpenDBInfo,
key: AttributeType,
start, end: AttributeValue,
index: IndexInfo,
current: AttributeValue,
pathStk: BTreeSimple.PathStk
];
Database schema
Since not all attribute types need to be keys, i.e. have btree indices maintained for them, the database schema must contain a list of attribute types that should serve as keys. Associated with each key is the name of the file storing the btree for that key. Two types of btree indices are supported: primary and secondary. A primary index must have unique attribute values for the associated attribute type, whereas secondary indices need not have unique values. (The implementation generates artifically unique btree keys for secondary indices.)
IndexInfo: TYPE = REF IndexInfoRecord;
IndexInfoRecord:
TYPE =
RECORD[
key: AttributeType,
type: {primary, secondary},
filename: ROPE,
openfile: FS.OpenFile,
btree: BTreeSimple.Tree
];
IndexSet: TYPE = RefTab.Ref; --AttributeType <-> IndexInfo
Logs are maintained as file streams that are either read only or can be updated by appending entries to them. Currently, only textual logs containing lists of attributes are supported, though, some day, logs might store pickled Cedar data structures
LogInfo: TYPE = REF LogInfoRecord;
LogInfoRecord:
TYPE =
RECORD[
id: LogID,
format: {textual, pickled},
access: {readOnly, readWrite},
filename: ROPE,
stream: STREAM
];
LogSet: TYPE = REF LogSetRecord;
LogSetRecord: TYPE = RECORD[seq: SEQUENCE size: LogID OF LogInfo];
A database schema contains information about all logs and indices that comprise a database. Once a database has been opened the schema information is maintained in a OpenDBRecord. This may be a misnomer since the OpenDBRecord for a database remains in existence even if the database is closed. Database operations are monitored so that several processes can share a database. Operations by remote clients are disabled if the remoteAccess flag is FALSE.
OpenDBInfo: TYPE = REF OpenDBRecord;
OpenDBRecord:
TYPE =
MONITORED RECORD[
dbName: ROPE,
isOpen: BOOLEAN,
remoteAccess: BOOLEAN,
statusMsg: ROPE,
indices: IndexSet,
primaryIndex: IndexInfo,
logs: LogSet
];
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 <logID> <readOnly or readWrite> <optional CR> <filename>
--> index <key> <primary or secondary> <optional CR> <filename>
SchemaChars: REF READONLY TEXT; -- currently the string "- - >"
END.
Doug Terry, December 20, 1985 3:49:26 pm PST
Type declarations extracted from LoganBerryImpl.mesa
, OpenDBRecord
Doug Terry, January 23, 1986 4:17:03 pm PST
changes to: OpenDBRecord
Doug Terry, February 26, 1986 6:47:11 pm PST
changes to: LogInfoRecord, IndexInfoRecord, type, OpenDBRecord