Browse Prior Art Database

Serial Logical Search Mechanism With Multiple Carries

IP.com Disclosure Number: IPCOM000035193D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 52K

Publishing Venue

IBM

Related People

Ouchi, NK: AUTHOR

Abstract

Disclosed is a mechanism for searching formatted data on sequential storage devices, such as rotating disks or tape and selecting records based on user-defined search expressions. A Structured Query Language, SQL, is an example of a source of search expressions. Since the data are read serially from the device, it may not be possible to parse the parameters of the search expression to match the serial sequence of the data or, parameters may be repeated in different sub-expressions or compared with data read from the device rather than predefined con- stants.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 3

Serial Logical Search Mechanism With Multiple Carries

Disclosed is a mechanism for searching formatted data on sequential storage devices, such as rotating disks or tape and selecting records based on user-defined search expressions. A Structured Query Language, SQL, is an example of a source of search expressions. Since the data are read serially from the device, it may not be possible to parse the parameters of the search expression to match the serial sequence of the data or, parameters may be repeated in different sub-expressions or compared with data read from the device rather than predefined con- stants. The disclosed mechanism teaches that a carry bit can convey the result of evaluating a sub-expression out of serial sequence for use later in the evaluation, that data values may be saved for repeated use in multiple sub-expressions and that multiple passes through the serial data using carry bits and saved values can be used to evaluate expressions that exceed the capacity of the search hardware.

Modern data bases allow filtering of vast amounts of data to extract the requested information. This is performed in the Central Processing Unit, CPU, for most data bases. There is a class of machines given the name "Data Base Machines" where the data are distributed across several DASD devices are scanned by separate special programmed peripheral processors to perform the scan in parallel. Because the data are read serially from the device, the scanning is, in general, program controlled searches in the processor storage. The disclosed mechanism is an engine to scan the data directly at the device data rate.

Unlike processor storage, the data in a serial storage device must be scanned in the serial order in which they were stored. To retrieve them out of order requires another pass through the data. It is an objective to minimize the number of passes through the data. To simplify the examples, let the letters A, B, C,... represent the data in serial sequence, let @n, n=1, 2, 3,... represent a logical or arithmetic relationship such as AND, OR, NOT, GREATER THAN, EQUAL, etc., let Kn, n=1, 2, 3,... represent user-supplied arguments in the search expression. Thus, the expression: A@1K1 has the value true or false depending on the relationship @1 of A to K1. Parentheses are used to clarify grouping of sub-expressions. Thus, the expression: (A@1K1)@2(B@3K2) means the sub-expressions A@1K1 and B@3K2 are evaluated and their logical values are used with @2 to derive the logical value of the complete expression.

A simple serial search engine can be described for a subset of the possible search expressions. This is illustrated in Fig. 1. It consists of a latch, a serial compare circuit, and control logic. The compare circuit can compare character strings by character or against "?" or "*" as DON'T CARE characters or strings as defined by SQL or directory searches. The compare circuit can also compare numeric data against two possible limit...