Hybrid query apparatus and method

• US 5,870,739 A
• Filed: 11/15/1996
• Issued: 02/09/1999
• Est. Priority Date: 09/20/1996
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Sanders, Daniel S., Hodgkinson, Andrew A., Pathakis, Scott W., Davis, James R. III, Jensen, Brian L., Bradshaw, W. Brent
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/751,540
• Time in Patent Office: 816 Days
• Field of Search: 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2448 for particular applications; for extensibility, e.g. user defined types
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

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.

Claims

1. An apparatus for formulating and executing a hybrid 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 record of the records comprising a text field of arbitrary size and a database field, pre-defined to contain conventional database data;

the database further comprising a full-text index for identifying the text field and a database index for identifying the database field;

a hybrid query structure, stored in the memory device, having a full-text selection criterion, in a first predicate corresponding to the full-text index, and a non-full-text selection criterion, in a second predicate corresponding to the database index;

a query engine module stored in the memory device to be executable by the processor for building the hybrid query structure and retrieving indicia of records satisfying the query.

2. The apparatus of claim 1, wherein the database further comprises an alternate-key index.

3. The apparatus of claim 2, wherein the alternate-key index is a compound alternate-key index.

4. The apparatus of claim 2, wherein the alternate-key index is a simple alternate-key index.

5. The apparatus of claim 2, wherein the alternate-key index is a simple alternate-key filtered index.

6. The apparatus of claim 2, wherein the alternate-key index is a compound alternate-key filtered index.

7. The apparatus of claim 1, wherein the database further comprises a filtered index.

8. The apparatus of claim 1, wherein the records are arbitrarily structured records.

9. A method of formulating and executing a hybrid 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:

providing records in a database, a record of the records comprising a text field of arbitrary size and a standard database field, pre-defined to contain conventional database data;

the database further comprising a full-text index for identifying the text field and a database index for identifying the database field;

building, in a memory device, a hybrid query structure having a full-text selection criterion corresponding to the text field, a non-full-text selection criterion corresponding to the standard database field, and information defining a hybrid 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.

10. The method of claim 9, wherein the the database comprises and index selected from the group consisting of:

a full-text index;

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.

11. The method of claim 9, wherein the records are arbitrarily structured records.

12. A memory device storing data structures corresponding to a hybrid query, the data structures comprising:

indicia structures containing indicia of records in a database;

the records, further comprising a text field of arbitrary size and a database field, pre-defined to contain conventional database data;

the database further comprising a full-text index for identifying the text field and a database index for identifying the database field;

a hybrid query structure having a full-text selection criterion corresponding to the text field and a non-full-text selection criterion corresponding to the database field;

a query engine structure executable by a processor for building the hybrid query structure and retrieving indicia structures corresponding to selected records satisfying the query.

13. The apparatus of claim 12, wherein the database comprises one or more indices selected from the group consisting of:

a full text index;

an alternate-key index;

compound alternate-key index;

a simple alternate-key index,

simple alternate-key filtered index;

a compound alternate-key filtered index; and

a filtered index.

14. The memory device of claim 12, wherein the records are arbitrarily structured records.

15. The memory device of claim 12, wherein the query engine structure contains executables to build the query structure, retrieve indicia of records from the database in accordance with the query structure, evaluate each of the indicia to determine whether such indicia satisfy the query criterion, and return selected indicia satisfying the criterion, all in an order and repetition determined by the query engine structure during execution thereof.