Heterogeneous record search apparatus and method

• US 6,167,393 A
• Filed: 11/15/1996
• Issued: 12/26/2000
• Est. Priority Date: 09/20/1996
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Hodgkinson, Andrew A., Jensen, Brian L., Bradshaw, W. Brent, Sanders, Daniel S., Pathakis, Scott W., Davis, James R. III
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Jung, David Yiuk
• Application Number:
  US08/749,575
• Time in Patent Office: 1,502 Days
• Field of Search: 707/1-206, 364/282.1-283.4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

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 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.

2. The apparatus of claim 1, wherein the query structure defines a hybrid query.

3. 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.

4. The apparatus of claim 1, wherein the query engine is programmed to satisfy the query by using an index.

5. The apparatus of claim 4, wherein the index is an alternate-key index.

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

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

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

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

10. The apparatus of claim 4, wherein the index is a filtered index.

11. 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.

12. 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.

13. 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.

14. The apparatus of claim 12 wherein the operator is selected from the group consisting of unary operators and binary operators.

15. The apparatus of claim 1, wherein the query engine is programmed to evaluate an operator having an operand of unknown value.

16. 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.

17. 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.

18. The apparatus of claim 17, wherein the operator is an aggregrator operator.

19. The apparatus of claim 18, wherein the aggregator operator is a universal quantifier operator.

20. The apparatus of claim 18, wherein the aggregator operator is an existential quantifier operator.

21. The apparatus of claim 17, wherein the operator is a selector operator.

22. The apparatus of claim 21, wherein the selector operator is a FIRST operator.

23. The apparatus of claim 21, wherein the selector operator is a LAST operator.

24. The apparatus of claim 21, wherein the selector operator is an NTH occurrence operator.

25. The apparatus of claim 17, wherein the operator is a field existence operator.

26. The apparatus of claim 25, wherein the field existence operator is explicitly stated in the selection criterion.

27. The apparatus of claim 25, wherein the field existence operator is implied by the selection criterion.

28. 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.

29. The method of claim 28, wherein the query structure represents a hybrid query.

30. 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.

31. The method of claim 28, wherein retrieving further comprises using an index to find the indicia of records.

32. 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.

33. 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.

34. 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.

35. 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.

36. The method of claim 34 wherein the operator is selected from the group consisting of unary operators and binary operators.

37. The method of claim 28, wherein the evaluating step further comprises evaluating an operator having an operand of unknown value.

38. 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.

39. 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.

40. The method of claim 39, wherein the operator is an aggregrator operator.

41. The method of claim 40, wherein the aggregator operator is selected from a universal quantifier operator and an existential quantifier operator.

42. The method of claim 39, wherein the operator is a selector operator.

43. 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.

44. The method of claim 39, wherein the operator is a field existence operator.

45. The method of claim 44, wherein the field existence operator is explicitly stated in the selection criterion.

46. The method of claim 44, wherein the field existence operator is implied by the selection criterion.

47. 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.

48. 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.

49. 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.

50. 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.

51. 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.