LoganBerryDoc.tioga
Doug Terry, February 26, 1986 6:19:36 pm PST
LOGANBERRY
CEDAR 6.0 — FOR INTERNAL XEROX USE ONLY
LoganBerry
a simple data management facility
Doug Terry
© Copyright 1985 Xerox Corporation. All rights reserved.
Abstract: LoganBerry is a simple facility for managing databases. Data is stored in one or more log files and indexed using btrees. The LoganBerry package supports retrieval by key or key subrange. An additional package, LoganQuery, allows more complex queries to be formulated, such as those involving filters and mergers. The LoganBerry Browser permits one to browse a LoganBerry database interactively.
Created by: Doug Terry
Maintained by: Doug Terry <Terry.pa>
Keywords: database, logs, btrees, browsing
XEROX  Xerox Corporation
   Palo Alto Research Center
   3333 Coyote Hill Road
   Palo Alto, California 94304

For Internal Xerox Use Only
LoganBerry
Data representation
A LoganBerry 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 (log 0) 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. 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.
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 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 <logID> <readOnly or readWrite> <optional CR> <filename>
--> index <key> <primary or secondary> <optional CR> <filename>
The following is a sample database schema file:
============================
-- SampleDB.df

Directory [Indigo]<LoganBerry>Backups>Top>
SampleDB.df!3 12-Aug-85 13:16:12 PDT

Directory [Indigo]<LoganBerry>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
See the interface, LoganBerry.mesa, for a description of the basic operations.
Editing logs
Logs are human readable and may be edited or created using facilites outside of LoganBerry, such as the Tioga text editor. You should do so cautiously. In particular, logs must be of the following format: 1) attribute types and values are text strings separated by a `:'; thus, attribute types may not contain colons; 2) attributes are terminated by a CR; attribute values may contain CR's if the complete value is enclosed in double-quotes `"', i.e. the attribute value looks like a ROPE literal; 3) entries are terminated by a CR; 4) the end of the log must be the character 377C. Do not delete or change entries in a log that has entries of the form: DELETED: number, since the number is a pointer into the log. It is always safe to add entries to the end of a log (right before the 377C character) or edit a log after it has been compacted. You must remember to run LoganBerry.BuildIndices after manually editing a log!
The following is a sample log file (containing a single entry with three attributes):
============================
Name: Doug Terry
Phone number: 494-4427
Workstation: "Lake
Champlain"

ÿ
============================
LoganQuery
LoganQuery allows more complicated queries to be performed on a LoganBerry database than the simple retrievals provided by the LoganBerry interface. Database queries of various classes can be registered; retrieval operations are class-specific. For instance, the $Filter class returns database entries that match a particular pattern, while the $Merger class merges the entries returned by two independent queries. Filters can be cascaded to perform multiple-attribute queries. The predefined $Simple class permits operations identical to those provided by LoganBerry. Clients are free to create their own class of queries.
LoganBerry Browser
Basics
A tool exists for interactively browsing LoganBerry databases. Currently, the browser tool does not allow interactive updates to be performed. So databases must be created using either the LoganBerry programmer's interface or the editor to create log files. To run the browser, type:
Bringover -p /Cedar/CedarChest®/Top/LoganBerry.df
LoganBerryBrowser some-database-schema-name
The browser reads the database schema to discover what indices exist for the database. It then builds an input form in which values for the various attribute keys can be entered. These values are treated as patterns against which database entries are compared.
User interface
The LoganBerry Browser Tool displays the following menu buttons:
STOP!: terminates a currently executing database query.
Browse: initiates a database query to retrieve all entries matching the input form. That is all database entries whose attribute values match the correponding pattern in the input form (according to some criteria, see below) are displayed in the output viewer of the browser. Various types of pattern matching are supported:
Details: toggles whether or not the details that govern how a query is performed are displayed.
History: toggles whether or not the history of part queries is displayed. This is not currently implemented.
The details viewer include a choice button for each field of the input form specifying the kind of pattern matching that applies to that field:
exact: values must match exactly;
prefix: the pattern must be a prefix of the database entry's attribute value;
wildcard: the pattern may contain zero or more wildcards (the character "*") that match anything;
regular expression: the pattern is taken to be a regular expression as defined in RegularExpressionDoc.tioga;
soundex: the form value's Soundex code is compared with that of a database entry's attribute value, i.e. values match in they "sound" alike; for instance, Johnson, Jansen, and Johansen have identical Soundex codes.
A choice button also exists that allows users to select on which attribute the output should be ordered. Fine point: to speed up queries it is best to order the output on some attribute that has a well-specified pattern.