LoganQuery.mesa
Copyright Ó 1985, 1992 by Xerox Corporation. All rights reserved.
Doug Terry, July 21, 1992 10:07 am PDT
LoganQuery allows more complicated queries to be performed on a LoganBerry database than the simple retrievals provided by the LoganBerry interface. These include multiple-attribute queries and boolean queries. The results of such queries are obtained by retrieving entries one at a time from a cursor. This interface provides operations that generate cursors for complex queries. See LoganQueryClass.mesa for obtaining more basic cursors.
Basic operations
The following two operations are syntactically identical and semantically similar to those provided by LoganBerry. Any errors raised by these operations are generated by LoganBerry.
NextEntry:
PROC [cursor: Cursor, dir: CursorDirection ¬ increasing]
RETURNS [entry: LoganBerry.Entry];
Retrieves the next entry relative to the given cursor. 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: IndexNotOpen, BadIndex, LogNotOpen, BadLogEntry
EndGenerate:
PROC [cursor: Cursor]
RETURNS [];
Releases the cursor; no further operations may be performed using the given cursor. This must be called once for every cursor created.
Attribute-based queries
Following are some operations for dealing with attribute patterns and using them to query a LoganBerry database. Multi-attribute queries are accomplished by cascading one or more filters.
Attribute patterns are lists of LoganBerry attributes that may optionally contain a pattern type. The currently supported types of patterns include "exact", "prefix", "wildcard", "re", "soundex", etc. (see PatternMatchersDoc.tioga). The following data structure is the internal representation of an attribute pattern list. In addition, attribute patterns have an external (character string) representation that can be printed or typed in. A basic LoganBerry attribute is represented in the form:
<attribute type>: <attribute value>
In this case, since a pattern is not explicitly specified, a default pattern is used (currently the default is "DWIM"). The attribute value may be either a token or a rope literal.
An explicit pattern type may be given in parenthesis immediately following the attribute type. Thus, an attribute pattern is given in the form
<attribute type>(<pattern>): <attribute value>
Several of these may be concatenated together to get a list of attribute patterns. For example,
Name: "Douglas B. Terry" Phone(prefix): 494-44 Office(wildcard): 35-2*
PatternType: TYPE = Rope.ROPE;
AttributePattern: TYPE = REF AttributePatternRec;
AttributePatternRec:
TYPE =
RECORD [
attr: LoganBerry.Attribute,
ptype: PatternType ¬ NIL
];
AttributePatterns: TYPE = LIST OF AttributePattern;
SyntaxError: ERROR [explanation: Rope.ROPE ¬ NIL];
ReadAttributePatterns:
PROC [s:
IO.
STREAM]
RETURNS [ap: AttributePatterns];
Reads an externalized list of attribute patterns from the given stream and builds the appropriate data structure. Raises ! SyntaxError if the stream does not contain a validly formed list of attributes.
WriteAttributePatterns:
PROC [s:
IO.
STREAM, ap: AttributePatterns]
RETURNS [];
Writes a list of attribute patterns to the given stream.
PatternsToEntry:
PROC [ap: AttributePatterns]
RETURNS [entry: LoganBerry.Entry];
Converts a list of attribute patterns to a LoganBerry entry by ignoring the pattern type.
EntryToPatterns:
PROC [entry: LoganBerry.Entry]
RETURNS [ap: AttributePatterns];
Converts a LoganBerry entry to a list of attribute patterns with ptype=NIL.
A query plan is given as a list of alternate subplans. When returned by QueryEntries, a query plan has the chosen subplan at the head of the list.
QueryPlan: TYPE = LIST OF SubPlan;
SubPlan: TYPE = REF SubPlanRec;
SubPlanRec:
TYPE =
RECORD[
attr: LoganBerry.Attribute, -- field type and pattern
ptype: PatternType, -- pattern matching used
wasDWIM: BOOLEAN ¬ FALSE, -- ptype was DWIM
filter: LoganQueryClass.MatchProc ¬ NIL, -- match proc
itype: ATOM ¬ $notAnIndex, -- index layout
start, end: ROPE ¬ NIL, -- base range
cost: REAL ¬ 2.0, -- estimated query cost
infoMsg: ROPE ¬ NIL, -- informational message
errMsg: ROPE ¬ NIL -- error in pattern if not NIL
];
QueryEntries:
PROC [db: LoganBerry.OpenDB, patterns: AttributePatterns, baseIndex: LoganBerry.AttributeType ¬
NIL, defaultPattern: PatternType ¬ "DWIM", planOnly:
BOOLEAN ¬
FALSE]
RETURNS [cursor: Cursor, plan: QueryPlan];
Returns a cursor of class $Query. Retrievals using this new cursor match the attribute patterns against entries in the database. The baseIndex parameter governs which attribute type is used as the base index for the query; for baseIndex=NIL, an index is chosen that attempts to optimize the execution of the query (use this unless you really care about the order in which database entries are retrieved). The defaultPattern parameter indicates which type of pattern matching to use if this is not explictly specified in an attribute pattern. The returned query plan provides information about the query. If planOnly is TRUE, then a query plan is formulated and returned, but a cursor for this query is not created.
Boolean attribute-based queries
The following operations support boolean queries over a LoganBerry database. The simplest query is a single attribute pattern:
<attribute type>(<pattern>): <attribute value>
where the pattern specification is optional.
These can be combined using AND, OR, and NOT as well as parenthesis. The AND operator between attribute patterns is optional (for compatibility with the attribute-based queries defined above). The actual grammar for boolean queries is as follows:
query ::= boolexpr | boolexpr query
boolexpr ::= term | term "OR" boolexpr
term ::= factor | factor "AND" term
factor ::= attribute-pattern | "NOT" factor | "(" boolexpr ")"
attribute-pattern ::= attribute-type ":" attribute-value |
attribute-type "(" pattern ")" ":" attribute-value
Boolean queries are parsed into a parse tree that is defined as follows:
ParseTree: TYPE = ParseNode;
ParseNodeTag: TYPE = {and, or, not, ap};
ParseNode: TYPE = REF ParseNodeRec;
ParseNodeRec:
TYPE =
RECORD [
tag: ParseNodeTag,
child1: ParseNode ¬ NIL, -- used if tag in $and .. $not
child2: ParseNode ¬ NIL, -- used if tag in $and .. $or
ap: AttributePattern ¬ NIL -- used if tag = $ap
];
ParseBooleanQuery:
PROC [s:
IO.
STREAM]
RETURNS [tree: ParseTree];
Returns the parse tree for the query read from the given stream. Raises SyntaxError if the query is not a proper boolean query.
BooleanFilterEntries:
PROC [input: Cursor, query: ParseTree, inputOrder: LoganBerry.AttributeType, primaryKey: LoganBerry.AttributeType, defaultPattern: PatternType ¬ "DWIM"]
RETURNS [output: Cursor];
Returns a cursor of class $BooleanFilter. Retrievals using this new cursor match the boolean query against entries returned by the input cursor. The query tree should be the result of ParseBooleanQuery. The inputOrder specifies the attribute by which entries on the input cursor are ordered, while primaryKey indicates the attribute for which these entries have unique values. The defaultPattern parameter indicates which type of pattern matching to use if this is not explictly specified in an attribute pattern. The input cursor could be obtained from QueryEntries (or a variety of operations in LoganQueryClass such as GenerateEntries).
Doug Terry, November 6, 1985 5:15:27 pm PST
changes to: DIRECTORY, ILQuery, ~, Cursor, CursorDirection, CursorClass, CursorClassRec, RetrieveProc, DestroyProc, NextEntry, EndGenerate, GenerateEntries, FilterEntries, MatchResult, FilterProc, MergeEntries
Doug Terry, November 7, 1985 2:59:51 pm PST
changes to: ~, QueryClass, QueryClassRec, ComplexCursor, RetrieveProc, DestroyProc, FilterEntries, FilterProc, MergeEntries, Equal, Prefix, Wildcard, RegularExpression, Soundex, DIRECTORY, NextEntry
Doug Terry, April 14, 1987 3:36:36 pm PDT
Moved FilterProcs to PatternMatch; added $Query class from LoganBerryBrowser.
changes to: FilterEntries, MergeEntries, SyntaxError, QueryWarning, QueryPlan, QueryPlanRec, QueryEntries, END