US5884304A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Alternate key index query apparatus and method
Assignee: Apple Inc
•
Filing: 1996-11-15
•
Granted: 1999-03-16
•
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-10-29 23:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/2448; G06F16/22; G06F16/30; G06F16/33; G06F16/80; G06F16/83; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
111 words
An apparatus for formulating and executing a query on 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: the records stored in the memory device; a query structure stored in the memory device and representing a selection criterion; an alternate-key index stored in the memory device; and a query engine module stored in the memory device to be executable by the processor for building the query structure and using the alternate-key index to retrieve indicia of records satisfying the query.
Claim 2
Independent Claim
111 words
An apparatus for formulating and executing a query on 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: the records stored in the memory device; a query structure stored in the memory device and representing a selection criterion; an alternate-key index stored in the memory device; and a query engine module stored in the memory device to be executable by the processor for building the query structure and using the alternate-key index to retrieve indicia of records satisfying the query.
Claim 3
Dependent Claim
14 words
The apparatus of claim 1, wherein the alternate-key index is a compound alternate-key index.
Claim 4
Dependent Claim
14 words
The apparatus of claim 1, wherein the alternate-key index is a simple alternate-key index.
Claim 5
Dependent Claim
15 words
The apparatus of claim 1, wherein the alternate-key index is a simple alternate-key filtered index.
Claim 6
Dependent Claim
15 words
The apparatus of claim 1, wherein the alternate-key index is a compound alternate-key filtered index.
Claim 7
Dependent Claim
12 words
The apparatus of claim 1, wherein the records are arbitrarily structured records.
Claim 8
Dependent Claim
14 words
The apparatus of claim 1, wherein the query structure contains a disjunctive selection criterion.
Claim 9
Dependent Claim
23 words
The apparatus of claim 7, wherein the query engine is programmed to optimize evaluation of the disjunctive selection criterion using the alternate-key index.
Claim 10
Dependent Claim
22 words
The apparatus of claim 1, wherein the query engine is programmed to optimize evaluation of the selection criterion using the alternate-key index.
Claim 11
Dependent Claim
14 words
The apparatus of claim 1, wherein the query structure is a hybrid query structure.
Claim 12
Dependent Claim
20 words
The apparatus of claim 10, wherein the hybrid query structure comprises a full-text selection criterion and a non-full-text selection criterion.
Claim 13
Dependent Claim
36 words
The memory device of claim 1, wherein the alternate-key index is selected from the group consisting of: a compound alternate-key index; a simple alternate-key index; a simple alternate-key filtered index; and a compound alternate-key filtered index.
Claim 14
Independent Claim
118 words
A method of formulating and executing a query against 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 having selection criterion and information defining a query; retrieving indicia of records from the database in accordance with the query structure, using an alternate-key index to find the indicia; 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 15
Independent Claim
118 words
A method of formulating and executing a query against 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 having selection criterion and information defining a query; retrieving indicia of records from the database in accordance with the query structure, using an alternate-key index to find the indicia; 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 16
Dependent Claim
35 words
The method of claim 13, wherein the alternate-key index is selected from the group consisting of: a compound alternate-key index; a simple alternate-key index; a simple alternate-key filtered index; and a compound alternate-key filtered index.
Claim 17
Dependent Claim
12 words
The method of claim 13, wherein the records are arbitrarily structured records.
Claim 18
Dependent Claim
14 words
The method of claim 13, wherein the query structure contains a disjunctive selection criterion.
Claim 19
Dependent Claim
24 words
The method of claim 16, further comprising using the alternate-key index to optimize the retrieving step to find records satisfying the disjunctive selection criterion.
Claim 20
Dependent Claim
14 words
The method of claim 13, wherein the query structure is a hybrid query structure.
Claim 21
Dependent Claim
20 words
The method of claim 18, wherein a hybrid query structure comprises a full-text selection criterion and a non-full-text selection criterion.
Claim 22
Dependent Claim
72 words
A memory device storing data structures comprising: records having indicia associated therewith; a query structure representing a selection criterion corresponding to a query; an alternate-key index reflecting the indicia of the records; and a query engine module stored in the memory device to be executable by a processor operably connected to the memory device for building the query structure and using the alternate-key index to retrieve indicia of records satisfying the query.
Claim 23
Dependent Claim
72 words
A memory device storing data structures comprising: records having indicia associated therewith; a query structure representing a selection criterion corresponding to a query; an alternate-key index reflecting the indicia of the records; and a query engine module stored in the memory device to be executable by a processor operably connected to the memory device for building the query structure and using the alternate-key index to retrieve indicia of records satisfying the query.
Claim 24
Dependent Claim
13 words
The memory device of claim 20 wherein the records are arbitrarily structured records.
Claim 25
Dependent Claim
15 words
The memory device of claim 20, wherein the query structure contains a disjunctive selection criterion.
Claim 26
Dependent Claim
26 words
The memory device of claim 22, wherein the query engine contains an executable effective to optimize evaluation of the disjunctive selection criterion using the alternate-key index.
Claim 27
Dependent Claim
15 words
The memory device of claim 20, wherein the query structure is a hybrid query structure.
References Cited (Backward Citations)
US4648036A
Cited
US4714995A
Cited
US4939689A
Cited
US5081608A
Cited
US5594899A
Cited
US5584026A
Cited
US5168444A
Cited
US5442784A
Cited
US5257366A
Cited
US5418943A
Cited
US5301317A
Cited
US5412806A
Cited
US5511186A
Cited
US5499358A
Cited
US5664172A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-15 | 2002-09-14 | 2003-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-15 | 2006-09-14 | 2007-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-15 | 2010-09-14 | 2011-03-16 | $7700.00 | Window Closed / Lapsed |