US6167393A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Heterogeneous record search apparatus and method
Assignee: Apple Inc
•
Filing: 1996-11-15
•
Granted: 2000-12-26
•
Expires: 2016-11-15
Abstract
Abstract A method and apparatus disclosed may be implemented in a digital computer to query a set of arbitrarily structured records. Arbitrarily structured records are structured differently from each other. A query engine, query structure, operators of conventional and non-conventional types may be used in formulating a query. The apparatus may evaluate records having missing fields, repeating fields, or an UNKNOWN value arising from a missing field, division by zero, modulo by zero, or the like. New aggregator (e.g. universal quantifier and existential quantifier) and selector operators (e.g., first, last, nth) may distill multiple values to return a single value. To evaluate a query, the search engine may implement filtered indices, alternate-key indices, compound alternate-key indices, hybrid queries having both full-text and non-full text operands, and joinder of records. Certain of these features may be implemented for evaluating records from both prior art databases and heterogeneous databases of arbitrarily structured records.
Inventors
- 👤 James R. Davis, III
- 👤 Daniel S. Sanders
- 👤 Scott W. Pathakis
- 👤 W. Brent Bradshaw
- 👤 Brian L. Jensen
- 👤 Andrew A. Hodgkinson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 12:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99936; Y10S707/99937; Y10S707/99941; Y10S707/99942; Y10S707/99943; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
95 words
An apparatus for querying a database comprising records, the apparatus comprising a digital computer having a processor operably connected to a memory device storing modules executable on the processor and data structures containing data associated with the modules, the modules and data structures comprising: arbitrarily structured records stored in the memory device; a query structure stored in the memory device and representing a selection criterion; and a query engine module stored in the memory device to be executable by the processor to build the query structure and to retrieve indicia of records satisfying the query.
Claim 2
Independent Claim
95 words
An apparatus for querying a database comprising records, the apparatus comprising a digital computer having a processor operably connected to a memory device storing modules executable on the processor and data structures containing data associated with the modules, the modules and data structures comprising: arbitrarily structured records stored in the memory device; a query structure stored in the memory device and representing a selection criterion; and a query engine module stored in the memory device to be executable by the processor to build the query structure and to retrieve indicia of records satisfying the query.
Claim 3
Dependent Claim
13 words
The apparatus of claim 1, wherein the query structure defines a hybrid query.
Claim 4
Dependent Claim
25 words
The apparatus of claim 2, wherein the hybrid query corresponds to a hybrid query structure having a full-text selection criterion and a non-full-text selection criterion.
Claim 5
Dependent Claim
19 words
The apparatus of claim 1, wherein the query engine is programmed to satisfy the query by using an index.
Claim 6
Dependent Claim
12 words
The apparatus of claim 4, wherein the index is an alternate-key index.
Claim 7
Dependent Claim
14 words
The apparatus of claim 5, wherein the alternate-key index is a compound alternate-key index.
Claim 8
Dependent Claim
14 words
The apparatus of claim 5, wherein the alternate-key index is a simple alternate-key index.
Claim 9
Dependent Claim
15 words
The apparatus of claim 5, wherein the alternate-key index is a simple alternate-key filtered index.
Claim 10
Dependent Claim
15 words
The apparatus of claim 5, wherein the alternate-key index is a compound alternate-key filtered index.
Claim 11
Dependent Claim
12 words
The apparatus of claim 4, wherein the index is a filtered index.
Claim 12
Dependent Claim
31 words
The apparatus of claim 1, wherein the query engine is programmed to join at least two heterogeneous sets of arbitrarily structured records to form another heterogeneous set of arbitrarily structured records.
Claim 13
Dependent Claim
32 words
The apparatus of claim 1, wherein the query engine is programmed to evaluate an operator having a multi-valued operand, having one or more values corresponding thereto and arising from a single record.
Claim 14
Dependent Claim
31 words
The apparatus of claim 12, wherein the operator is selected from the group consisting of logical operators, comparison operators, quantifier operators, aggregator operators, selector operators, field existence operators, and arithmetic operators.
Claim 15
Dependent Claim
20 words
The apparatus of claim 12 wherein the operator is selected from the group consisting of unary operators and binary operators.
Claim 16
Dependent Claim
21 words
The apparatus of claim 1, wherein the query engine is programmed to evaluate an operator having an operand of unknown value.
Claim 17
Dependent Claim
31 words
The apparatus of claim 15, wherein the operator is selected from the group consisting of logical operators, comparison operators, quantifier operators, aggregator operators, selector operators, field existence operators, and arithmetic operators.
Claim 18
Dependent Claim
40 words
The apparatus of claim 1, wherein the query engine is programmed to evaluate an operator effective to distill a multi-value operand, having one or more values corresponding thereto and a rising from a single record, into a single result value.
Claim 19
Dependent Claim
12 words
The apparatus of claim 17, wherein the operator is an aggregrator operator.
Claim 20
Dependent Claim
14 words
The apparatus of claim 18, wherein the aggregator operator is a universal quantifier operator.
Claim 21
Dependent Claim
14 words
The apparatus of claim 18, wherein the aggregator operator is an existential quantifier operator.
Claim 22
Dependent Claim
12 words
The apparatus of claim 17, wherein the operator is a selector operator.
Claim 23
Dependent Claim
13 words
The apparatus of claim 21, wherein the selector operator is a FIRST operator.
Claim 24
Dependent Claim
13 words
The apparatus of claim 21, wherein the selector operator is a LAST operator.
Claim 25
Dependent Claim
14 words
The apparatus of claim 21, wherein the selector operator is an NTH occurrence operator.
Claim 26
Dependent Claim
13 words
The apparatus of claim 17, wherein the operator is a field existence operator.
Claim 27
Dependent Claim
17 words
The apparatus of claim 25, wherein the field existence operator is explicitly stated in the selection criterion.
Claim 28
Dependent Claim
16 words
The apparatus of claim 25, wherein the field existence operator is implied by the selection criterion.
Claim 29
Independent Claim
108 words
A method of querying arbitrarily structured records in a database, the method being implemented in a query engine, the query engine being executable by a processor operably connected to a memory device, and the method comprising the following steps executed in an order and repetition determined by the query engine: building, in a memory device, a query structure containing a selection criterion and information defining a query; retrieving indicia of records from the database in accordance with the query structure; evaluating each of the indicia according to the selection criterion to determine whether the indicia satisfy the selection criterion; and returning selected indicia that satisfy the selection criterion.
Claim 30
Independent Claim
108 words
A method of querying arbitrarily structured records in a database, the method being implemented in a query engine, the query engine being executable by a processor operably connected to a memory device, and the method comprising the following steps executed in an order and repetition determined by the query engine: building, in a memory device, a query structure containing a selection criterion and information defining a query; retrieving indicia of records from the database in accordance with the query structure; evaluating each of the indicia according to the selection criterion to determine whether the indicia satisfy the selection criterion; and returning selected indicia that satisfy the selection criterion.
Claim 31
Dependent Claim
13 words
The method of claim 28, wherein the query structure represents a hybrid query.
Claim 32
Dependent Claim
25 words
The method of claim 29, wherein the hybrid query corresponds to a hybrid query structure having a full-text selection criterion and a non-full-text selection criterion.
Claim 33
Dependent Claim
18 words
The method of claim 28, wherein retrieving further comprises using an index to find the indicia of records.
Claim 34
Dependent Claim
40 words
The method of claim 31, wherein the index is selected from the group consisting of: an alternate-key index; a compound alternate-key index; a simple alternate-key index; a simple alternate-key filtered index; a compound alternate-key filtered index; and a filtered index.
Claim 35
Dependent Claim
59 words
The method of claim 28, further comprising, in an order and repetition determined by the query engine, joining indicia corresponding to at least two arbitrarily structured records to form composite indicia of a composite arbitrarily structured record, and wherein: the evaluating step evaluates the composite indicia; and the returning step returns selected composite indicia that satisfy the selection criterion.
Claim 36
Dependent Claim
31 words
The method of claim 28, wherein the evaluating step further comprises evaluating an operator having a multi-valued operand, having one or more values corresponding thereto and arising from a single record.
Claim 37
Dependent Claim
31 words
The method of claim 34, wherein the operator is selected from the group consisting of logical operators, comparison operators, quantifier operators, aggregator operators, selector operators, field existence operators, and arithmetic operators.
Claim 38
Dependent Claim
20 words
The method of claim 34 wherein the operator is selected from the group consisting of unary operators and binary operators.
Claim 39
Dependent Claim
20 words
The method of claim 28, wherein the evaluating step further comprises evaluating an operator having an operand of unknown value.
Claim 40
Dependent Claim
31 words
The method of claim 37, wherein the operator is selected from the group consisting of logical operators, comparison operators, quantifier operators, aggregator operators, selector operators, field existence operators, and arithmetic operators.
Claim 41
Dependent Claim
38 words
The method of claim 28, wherein the evaluating step further comprises evaluating an operator effective to distill a multi-value operand, having one or more values corresponding thereto and arising from a single record, into a single result value.
Claim 42
Dependent Claim
12 words
The method of claim 39, wherein the operator is an aggregrator operator.
Claim 43
Dependent Claim
21 words
The method of claim 40, wherein the aggregator operator is selected from a universal quantifier operator and an existential quantifier operator.
Claim 44
Dependent Claim
12 words
The method of claim 39, wherein the operator is a selector operator.
Claim 45
Dependent Claim
27 words
The method of claim 42, wherein the selector operator is selected from the group consisting of a FIRST operator, a LAST operator, and an NTH occurrence operator.
Claim 46
Dependent Claim
13 words
The method of claim 39, wherein the operator is a field existence operator.
Claim 47
Dependent Claim
17 words
The method of claim 44, wherein the field existence operator is explicitly stated in the selection criterion.
Claim 48
Dependent Claim
16 words
The method of claim 44, wherein the field existence operator is implied by the selection criterion.
Claim 49
Dependent Claim
84 words
A memory device storing data structures containing executables, and data associated therewith, the executables being effective to be executed by a processor operably connected to the memory device, the data structures comprising: arbitrarily structured records stored in the memory device; a query structure stored in the memory device and representing a selection criterion; and a query engine data structure stored in the memory device to be executable by the processor to build the query structure and to retrieve indicia of records satisfying the query.
Claim 50
Dependent Claim
84 words
A memory device storing data structures containing executables, and data associated therewith, the executables being effective to be executed by a processor operably connected to the memory device, the data structures comprising: arbitrarily structured records stored in the memory device; a query structure stored in the memory device and representing a selection criterion; and a query engine data structure stored in the memory device to be executable by the processor to build the query structure and to retrieve indicia of records satisfying the query.
Claim 51
Dependent Claim
27 words
The memory device of claim 47, wherein the query structure further comprises a hybrid query data structure containing a full-text selection criterion and a non-full-text selection criterion.
Claim 52
Dependent Claim
58 words
The memory device of claim 47 further comprising an index effective to be used by the query engine data structure during execution thereof to satisfy the query, the index being selected from the group consisting of: a compound alternate-key index; a simple alternate-key index; a simple alternate-key filtered index; a compound alternate-key filtered index; and a filtered index.
Claim 53
Dependent Claim
48 words
The memory device of claim 47 further comprising operator data structures corresponding to operators selected from the group consisting of: logical operators; comparison operators; quantifier operators; aggregator operators; selector operators; field existence operators; arithmetic operators; unary operators; binary operators; existential quantifier operators; universal quantifier operators; and distilling operators.
Claim 54
Independent Claim
124 words
An apparatus for querying arbitrarily structured records in a database, the apparatus comprising: a processor for executing a query engine; a memory device, operably connected to the processor, the memory device containing the query engine, a query structure associated therewith, a selection criterion, and information defining a query corresponding to the selection criterion; a storage device operably connected to the memory device and containing arbitrarily structured records in a heterogeneous database; the memory device containing indicia corresponding to the arbitrarily structured records in the heterogeneous database; the processor, wherein the query engine is effective to evaluate each of the indicia according to the selection criterion to determine whether the indicia satisfy the selection criterion; and to return selected indicia that satisfy the selection criterion.
Claim 55
Independent Claim
124 words
An apparatus for querying arbitrarily structured records in a database, the apparatus comprising: a processor for executing a query engine; a memory device, operably connected to the processor, the memory device containing the query engine, a query structure associated therewith, a selection criterion, and information defining a query corresponding to the selection criterion; a storage device operably connected to the memory device and containing arbitrarily structured records in a heterogeneous database; the memory device containing indicia corresponding to the arbitrarily structured records in the heterogeneous database; the processor, wherein the query engine is effective to evaluate each of the indicia according to the selection criterion to determine whether the indicia satisfy the selection criterion; and to return selected indicia that satisfy the selection criterion.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-26 | 2004-06-26 | 2004-12-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-26 | 2008-06-26 | 2008-12-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-26 | 2012-06-26 | 2012-12-26 | $7700.00 | Window Closed / Lapsed |