US5873079A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Filtered index apparatus and method
Assignee: Apple Inc
•
Filing: 1996-11-15
•
Granted: 1999-02-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-31 02:22
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/2448; G06F16/22; G06F16/245; G06F16/30; G06F16/33; G06F16/80; G06F16/83; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
110 words
An 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: a database comprising arbitrarily structured records stored in the memory device; a filtered index definition containing a criterion for selecting records to be indexed; a filtered index, created according to the filtered index definitin, comprising keys corresponding to selected records and stored in the memory device; and a database engine module stored in the memory device to be executable by the processor for creating and maintaining the filtered index using the filtered index definition.
Claim 2
Independent Claim
110 words
An 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: a database comprising arbitrarily structured records stored in the memory device; a filtered index definition containing a criterion for selecting records to be indexed; a filtered index, created according to the filtered index definitin, comprising keys corresponding to selected records and stored in the memory device; and a database engine module stored in the memory device to be executable by the processor for creating and maintaining the filtered index using the filtered index definition.
Claim 3
Dependent Claim
27 words
The apparatus of claim 1, wherein the filtered index is a compound alternate-key filtered index, and the filtered index definition is a compound alternate-key filtered index definition.
Claim 4
Dependent Claim
27 words
The apparatus of claim 1, wherein the filtered index is a simple alternate-key filtered index, and the filtered index definition is a simple alternate-key filtered index definition.
Claim 5
Dependent Claim
54 words
The apparatus of claim 1, further comprising: 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 for building the query structure and using the filtered index to retrieve indicia of records satisfying the query.
Claim 6
Dependent Claim
27 words
The apparatus of claim 4, wherein the filtered index is a compound alternate-key filtered index, and the filtered index definition is a compound alternate-key filtered index definition.
Claim 7
Dependent Claim
27 words
The apparatus of claim 4, wherein the filtered index is a simple alternate-key filtered index, and the filtered index definition is a simple alternate-key filtered index definition.
Claim 8
Dependent Claim
14 words
The apparatus of claim 4, wherein the query structure is a hybrid query structure.
Claim 9
Dependent Claim
20 words
The apparatus of claim 7, wherein a hybrid query structure comprises a full-text selection criterion and a non-full-text selection criterion.
Claim 10
Independent Claim
91 words
A method for implementing a filtered index in a database, the method being implemented in a database engine, the database engine containing arbitrarily structured records and being executable by a processor operably connected to a memory device, and the method comprising: building, in a memory device, a filtered index definition structure containing a list of fields to be indexed and a selection criterion to select candidate arbitrarily structured records for indexing; updating a filtered index, according to the specifications in the filtered index definition structure, whenever a database update operation occurs.
Claim 11
Independent Claim
91 words
A method for implementing a filtered index in a database, the method being implemented in a database engine, the database engine containing arbitrarily structured records and being executable by a processor operably connected to a memory device, and the method comprising: building, in a memory device, a filtered index definition structure containing a list of fields to be indexed and a selection criterion to select candidate arbitrarily structured records for indexing; updating a filtered index, according to the specifications in the filtered index definition structure, whenever a database update operation occurs.
Claim 12
Dependent Claim
22 words
The method of claim 9, wherein the database update operation is selected from deleting, adding, and modifying a record in the database.
Claim 13
Dependent Claim
27 words
The method of claim 9, wherein the filtered index is a compound alternate-key filtered index, and the filtered index definition is a compound alternate-key filtered index definition.
Claim 14
Dependent Claim
27 words
The method of claim 9, wherein the filtered index is a simple alternate-key filtered index, and the filtered index definition is a simple alternate-key filtered index definition.
Claim 15
Independent Claim
121 words
A method of formulating and executing a query against 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 having selection criterion and information defining a query; retrieving indicia of arbitrarily structured records from the database in accordance with the query structure, using a filtered 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 satisfying the selection criterion.
Claim 16
Independent Claim
121 words
A method of formulating and executing a query against 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 having selection criterion and information defining a query; retrieving indicia of arbitrarily structured records from the database in accordance with the query structure, using a filtered 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 satisfying the selection criterion.
Claim 17
Dependent Claim
23 words
The method of claim 13, wherein the filtered index is selected from a compound alternate-key filtered index and a simple alternate-key filtered index.
Claim 18
Dependent Claim
14 words
The method of claim 13, wherein the query structure is a hybrid query structure.
Claim 19
Dependent Claim
20 words
The method of claim 15, wherein a hybrid query structure comprises a full-text selection criterion and a non-full-text selection criterion.
Claim 20
Independent Claim
80 words
An apparatus comprising: a processor for executing instructions contained in executables; a memory device operably connected to the processor and containing data structures including: a database comprising arbitrarily structured records, a filtered index definition containing a criterion for selecting records to be indexed, a filtered index, created according to the filtered index definition, comprising keys corresponding to selected records, and a database engine module executable by the processor to create and maintain the filtered index using the filtered index definition.
Claim 21
Independent Claim
80 words
An apparatus comprising: a processor for executing instructions contained in executables; a memory device operably connected to the processor and containing data structures including: a database comprising arbitrarily structured records, a filtered index definition containing a criterion for selecting records to be indexed, a filtered index, created according to the filtered index definition, comprising keys corresponding to selected records, and a database engine module executable by the processor to create and maintain the filtered index using the filtered index definition.
Claim 22
Dependent Claim
47 words
The apparatus of claim 17, wherein the filtered index is selected from: a compound alternate-key filtered index, wherein the filtered index definition is a compound alternate-key filtered index definition; and a simple alternate-key filtered index, wherein the filtered index definition is a simple alternate-key filtered index definition.
Claim 23
Dependent Claim
50 words
The apparatus of claim 17, wherein the memory device further contains: indicia corresponding to the records; a query structure representing a selection criterion; and a query engine module executable by the processor to build the query structure and use the filtered index to retrieve indicia of records satisfying the query.
Claim 24
Dependent Claim
70 words
The apparatus of claim 19 wherein the query engine contains an executable effective to build in the memory device, the query structure, retrieve indicia of records from the database in accordance with the query structure, using the filtered index to find the indicia, evaluate each of the indicia according to the selection criterion to determine whether the indicia satisfy the selection criterion, and return selected indicia satisfying the selection criterion.
Claim 25
Dependent Claim
14 words
The apparatus of claim 17, wherein the query structure is a hybrid query structure.
Claim 26
Dependent Claim
56 words
The apparatus of claim 17, wherein the filtered index definition structure contains a list of fields to be indexed, the selection criterion is effective to select candidate records for indexing, and the query, and the database engine contains executables to update the filtered index, according to the filtered index definition, whenever a database update operation occurs.
References Cited (Backward Citations)
US4648036A
Cited
US4714995A
Cited
US4845658A
Cited
US4939689A
Cited
US5081608A
Cited
US5442784A
Cited
US5257366A
Cited
US5418943A
Cited
US5412806A
Cited
US5511186A
Cited
US5560007A
Cited
US5666528A
Cited
US5499358A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-15 | 2002-08-17 | 2003-02-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-15 | 2006-08-17 | 2007-02-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-15 | 2010-08-17 | 2011-02-16 | $7700.00 | Window Closed / Lapsed |