[Table of Contents | Previous Section | Next Section]
3.7 Type-1 and type-101 Queries
This section specifies procedures when Query-type is 1 (or 101; see Note 2 below). Type-1 is the "Reverse Polish Notation" (RPN) query. It has the following structure:
RPN-Query ::= Argument
| Argument + Argument + Operator
Argument ::= Operand | RPN-Query
operand ::= AttributeList + Term
| ResultSetId | Restriction
Restriction ::= ResultSetId + AttributeList
operator ::= AND | OR | AND-NOT | Prox
The notation above is used as follows:
::= means "is defined as"
| means "or"
+ means "followed by", and + has precedence over | (i.e., + is evaluated before |).
A Z39.50-conforming target must support the type-1 query, but support of the type-1 query does not imply support of any of the defined operators or operands.
The target designates what query types it supports, and which operators and operands.
Note: The target designates this information either through the Explain facility or through some mechanism outside of the standard.
If the target claims support for the Prox operator, the target should also designate whether it supports the extended result set model for proximity (the extended result set model for searching as described in 3.1.6 and its specialization for proximity as described in 220.127.116.11). If the target claims support for the Restriction operand, then it must also support the extended result set model for restriction (the extended result set model for searching and its specialization for restriction as described in 3.7.3).
Note: Only in certain circumstances (detailed below) does support of the Prox operator require support of the extended result set model for proximity. However, support of the Restriction operand always requires support of the extended result set model for Restriction.
3.7.1 Representation and Evaluation of the Type-1
and Type-101 Queries
At the origin, the query is represented by a tree. Each subtree represents an operand, either a simple operand or a complex operand. Each leaf node represents a simple operand: Result-set-id, AttributeList+ Term, or Restriction. Each non-leaf node represents a complex operand: a subtree whose root is an operator, and which contains two subtrees, a left operand and a right operand.
The origin traverses the tree according to a left post-order traversal, to produce a sequence of (simple) operands and operators, which is transmitted to the target.
At the target, evaluation of the sequence of operands and operators is illustrated by the use of a stack. Whenever an operand is encountered, it is put on the stack. Whenever an operator is encountered, the last two objects that have been put on the stack are pulled off and the operator is applied as follows.
Each operand represents a set of database records. Each is one of the following:
(a) AttributeList+term -- in which case it represents the set of database records obtained by evaluating the specified attribute-set and term against the collection of databases specified in the Search request.
(b) ResultSetId -- in which case it represents the set of database records represented by the transient result set identified by ResultSetId.
(c) Restriction operand (ResultSetId+AttributeList): in which case it represents the set of database records represented by the result set identified by ResultSetId, restricted by the specified attribute set (see 3.7.3).
Note: if the Restriction operand occurs the target must support the extended result set model for restriction; otherwise the query is in error.
(d) An intermediate result set (resulting from a previous evaluation placed on the stack) -- in which case it represents the records identified by that result set.
Let S1 and S2 be the sets represented by the left and right operand respectively. Let S be defined as follows:
An intermediate result set is created, which represents the records in the set S, and is put on the stack. When evaluation of the query is complete (i.e. all query-terms have been processed) there will be one object remaining on the stack (otherwise the query is in error), representing a set of database records, which is the result of the query.
18.104.22.168 The Proximity Test
The proximity test, ProxTest, includes a Distance, Relation, Unit, and two boolean flags: Ordered and Exclusion.
Example: suppose A and B respectively specify "personal name = 'McGraw,J.' " and "personal name= 'Stengel, C.' ," and:
Then the result is the set of records in which both of the personal names occur within the same paragraph. Using the same example, if the Exclusion flag is set to 'true,' the result is the set of records in which the two personal names never both occur within the same paragraph.
If the Ordered flag is set to 'true' (and Exclusion flag to 'false') then the result is the set of records in which the personal name 'McGraw, J.' occurs within the same paragraph as, but before, the personal name 'Stengel, C.'.
If distance is instead 1 ('ordered' and 'exclusion' flag 'false') the result is the set of records in which the two personal names occur in adjacent paragraphs. If, in addition, Relation-type is 'less-than-or-equal' the result is the set of records in which the two names occur within the same or adjacent paragraphs.
22.214.171.124 Extended Result Set Model for Proximity
In the extended result set model for proximity, the target maintains positional information, in the form of one or more position vectors, associated with each record represented by the result set, which may be used in a proximity operation as a surrogate for the search that created the result set.
Let R1 and R2 be result sets produced by type-1 query searches on the terms 'cat' and 'hat'. In the extended result set model for proximity, the target maintains sufficient information associated with each entry in R1 and with each entry in R2 so that the proximity operation "R1 near R2" would be a result set equivalent to the result set produced by the proximity operation "cat near hat" ("near" is used here informally to refer to a proximity test).
The manner in which the target maintains this information is not prescribed by the standard. Appendix 13 ERS (non-normative) provides examples.
3.7.3 Restriction and the Extended Result Set Model
The Restriction operand specifies a result-set-id and a set of attributes, and it represents the set of database records identified by the specified result set, restricted by the specified attributes.
Let R be the result set produced by a search on the term 'cat,' representing three records:
Then "R restricted to 'author'" might produce the result set consisting of the entries 2 and 3 of R.
In the extended result set model for restriction, the target maintains information associated with each record represented by the result set, that may be used in the evaluation of a restriction operand as a surrogate for the search that created the result set. The manner in which the target maintains this information is not prescribed by the standard. Appendix 13 ERS (non-normative) provides examples.[Table of Contents | Previous Section | Next Section]