Evaluation of content of a data set using multiple and/or complex queries

• US 5,778,364 A
• Filed: 01/02/1996
• Issued: 07/07/1998
• Est. Priority Date: 01/02/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Verity Incorporated (Healthstream Incorporated)
• Inventors: Nelson, Philip C.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/581,853
• Time in Patent Office: 917 Days
• Field of Search: 395/602, 395/603, 395/601-9, 395/610-30, 707/2, 707/3, 707/4, 707/5, 707/6, 707/100-200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

The invention enables evaluation of the content of a set of data to determine whether the data set satisfies one or more queries. The invention enables rapid evaluation of large numbers of data sets much more rapidly than has previously been possible, even when the number of queries is large and/or the queries are complex. The queries are evaluated using an execution plan of query terms that is constructed from one or more specified queries by translating each query term of each query into one or more evidence descriptors and one or more combination operators, and operably relating each of the combination operators to at least one of the evidence descriptors or other combination operators, such that each query is defined by one or more of the evidence descriptors and one or more of the combination operators that are operably related to each other. Preferably, none of the evidence descriptors or combination operators are duplicated in the execution plan. The invention can be used to evaluate data sets of a variety of types, such as text documents and databases. The invention can be further optimized to achieve rapid evaluation of a data set with respect to the queries in two steps. First, one or more candidate queries that may be satisfied by the data set are identified by approximately evaluating each query. Second, each of the candidate queries is fully evaluated to determine whether the candidate query is satisfied by the data set.

Claims

1. A method for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data capable of being described by one or more pieces of evidence, the queries being arranged in an execution plan of queries in which each query is operably related to one or more other queries, each of the plurality of queries including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, the method comprising the steps of:

comparing each piece of evidence as the data set is received to one or more of the evidence descriptors;

identifying each evidence descriptor that is satisfied by a piece of evidence;

evaluating each query term that includes a satisfied evidence descriptor or another query term that has been satisfied to determine whether the query term is satisfied; and

identifying each query for which all query terms have been satisfied as a query that is satisfied by the set of data.

2. A method as in claim 1, wherein at least one query term is operably related to another query term by sharing at least one evidence descriptor that is part of each of the operably related query terms.

3. A method as in claim 2, wherein the step of comparing further comprises the steps of:

identifying the type of each of the evidence descriptors;

identifying the type of each piece of evidence; and

comparing each piece of evidence to each evidence descriptor that is of the same type as the piece of evidence.

4. A method as in claim 2, further comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

5. A method as in claim 1, wherein the step of comparing further comprises the steps of:

identifying the type of each of the evidence descriptors;

identifying the type of each piece of evidence; and

comparing each piece of evidence to each evidence descriptor that is of the same type as the piece of evidence.

6. A method as in claim 5, further comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

7. A method as in claim 1, further comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

8. A method as in claim 1, wherein the set of data is arranged as a database.

11. A method as in claim 1, wherein a plurality of sets of data are evaluated.

12. A method as in claim 1, wherein the plurality of sets of data are evaluated sequentially.

13. A method as in claim 12, wherein:

the contents of the set of data are capable of being described by one or more pieces of evidence;

each of the plurality of queries includes one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and

at least one query term is operably related to another query term by sharing at least one evidence descriptor that is part of each of the operably related query terms.

14. A method as in claim 13, further comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

15. A method as in claim 12, wherein the plurality of queries are arranged in an execution plan of queries in which each query is operably related to one or more other queries.

16. A method as in claim 1, further comprising establishing a duplication of the plurality of queries for each of the sets of data, and wherein each of the plurality of sets of data are evaluated simultaneously using one of the plurality of queries.

17. A method as in claim 1, wherein the set of data is textual data.

24. A method as in claim 13, wherein the step of identifying further comprises the steps of:

establishing an approximation of one or more of the query terms to create an execution plan of approximated query terms;

evaluating the query terms in the execution plan of approximated query terms to determine which, if any, of the queries in the execution plan of approximated query terms are satisfied by the set of data; and

identifying each query in the execution plan of approximated query terms for which all query terms in the query are satisfied as a candidate query.

25. A method as in claim 13, wherein:

the step of identifying further comprises the steps of;

identifying the type of each evidence descriptor;

identifying the type of each piece of evidence;

comparing each piece of evidence to each evidence descriptor that is of the same type as the piece of evidence; and

identifying each evidence descriptor that is satisfied by a piece of evidence, wherein only a query including a satisfied evidence descriptor can be a candidate query.

26. A method as in claim 25, wherein the step of identifying further comprises the steps of:

establishing an approximation of one or more of the query terms to create an execution plan of approximated query terms;

evaluating the query terms in the execution plan of approximated query terms to determine which, if any, of the queries in the execution plan of approximated query terms are satisfied by the set of data; and

identifying each query in the execution plan of approximated query terms for which all query terms in the query are satisfied as a candidate query.

27. A method as in claim 26, further comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

9. A method for evaluating a set of data to enable identification of, from a plurality of queries that each include at least one evidence descriptor, each candidate query that may be satisfied by the set of data, the method comprising the steps of:

identifying the type of each of the evidence descriptors;

identifying the type of each piece of evidence in the set of data;

comparing each piece of evidence in the set of data to each of the evidence descriptors that are of the same type as the piece of evidence; and

identifying each of the evidence descriptors that is satisfied by a piece of evidence, wherein only a query including a satisfied evidence descriptor can be a candidate query.

10. A method as in claim 9, wherein the step or steps comprising the step of comparing are dependent upon the type of the element and the evidence descriptor being compared.

18. A method for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, each query having a query term and an approximation of the query term, comprising the steps of:

identifying one or more candidate queries that may be satisfied by the set of data using the approximation of the query term; and

evaluating each of the candidate queries using the query term to determine which, if any, of the candidate queries are satisfied by the set of data.

19. A method as in claim 18, wherein:

the contents of the set of data are capable of being described by one or more pieces of evidence;

each of the plurality of queries includes one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and

the step of identifying further comprises the steps of;

identifying the type of each of the evidence descriptors;

identifying the type of each piece of evidence;

comparing each piece of evidence to each evidence descriptor that is of the same type as the piece of evidence; and

identifying each evidence descriptor that is satisfied by a piece of evidence, wherein only a query including a satisfied evidence descriptor can be a candidate query.

20. A method as in claim 19, wherein the step of identifying further comprises:

establishing an approximation of one or more of the query terms to create an execution plan of approximated query terms;

evaluating the query terms in the execution plan of approximated query terms to determine which, if any, of the queries in the execution plan of approximated query terms are satisfied by the set of data; and

identifying each query in the execution plan of approximated query terms for which all query terms in the query are satisfied as a candidate query.

21. A method as in claim 19, further comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

22. A method as in claim 18, wherein the step of identifying further comprises the steps of:

establishing an approximation of one or more of the query terms to create an execution plan of approximated query terms;

evaluating the query terms in the execution plan of approximated query terms to determine which, if any, of the queries in the execution plan of approximated query terms are satisfied by the set of data; and

identifying each query in the execution plan of approximated query terms for which all query terms in the query are satisfied as a candidate query.

23. A method as in claim 18, wherein the plurality of queries includes a plurality of evidence descriptors that can be compared to one or more pieces of evidence that represent a portion of the content of the set of data to ascertain whether a piece of evidence satisfies an evidence descriptor, the method further comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

28. A method for use in evaluating a set of data to determine whether the set of data satisfies one or more queries, the one or more queries including a plurality of evidence descriptors that can be compared to one or more pieces of evidence that represent a portion of the content of the set of data to ascertain whether a piece of evidence satisfies an evidence descriptor, the method comprising the steps of:

defining one or more types of evidence;

identifying the type or types of the evidence descriptors; and

modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

29. A method as in claim 28, further comprising the step of creating one or more pieces of evidence, each piece of evidence being of one of the modified types.

30. A method as in claim 28, wherein the step of modifying further comprises adding a type to the defined types that is identified as a type of one of the evidence descriptors.

31. A method as in claim 28, wherein the step of modifying further comprises deleting a type from the defined types that is not identified as a type of one of the evidence descriptors.

32. A method for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, comprising the steps of:

inputting a plurality of queries; and

operably relating each query to another query.

33. A method as in claim 32, wherein the step of operably relating further comprises identifying each other query that is operably related to the query.

34. A method as in claim 32, further comprising the step of translating each query into one or more query terms, and wherein, for an additional query that is input after one or more previous queries, the step of operably relating further comprises the steps of:

comparing each of the input query terms of the additional query to the query terms that already exist as part of the execution plan to determine which, if any, of the input query terms are different than the existing query terms;

identifying, for each of the different input query terms, one or more relationships to input query terms that are the same as existing query terms; and

adding the different input query terms to the execution plan such that the different input query terms have relationships to existing query terms of the execution plan that are the same as the relationships between the different query terms and corresponding input query terms.

35. A method as in claim 32, further comprising the steps of:

translating each query into one or more query terms; and

removing a query from the execution plan, the step of removing further comprising the steps of;

comparing each of the query terms of the query to be removed to the query terms of other queries that exist as part of the execution plan to determine which, if any, of the query terms of the query to be removed are different than the other existing query terms; and

removing the different query terms from the execution plan.

36. A method as in claim 32, wherein the contents of the set of data are capable of being described by one or more pieces of evidence, the method further comprising the steps of:

translating each query into one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and

operably relating at least one query term to another query term by sharing at least one evidence descriptor that is part of each of the operably related query terms.

37. A method as in claim 36, wherein, for an additional query that is input after one or more previous queries, the step of operably relating further comprises the steps of:

comparing each of the input query terms of the additional query to the query terms that already exist as part of the execution plan to determine which, if any, of the input query terms are different than the existing query terms;

identifying, for each of the different input query terms, one or more relationships to input query terms that are the same as existing query terms; and

adding the different input query terms to the execution plan such that the different input query terms have relationships to existing query terms of the execution plan that are the same as the relationships between the different query terms and corresponding input query terms.

38. A method as in claim 37, further comprising the step of defining, for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator.

39. A method as in claim 36, further comprising the step of defining, for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator.

40. A method as in claim 36, wherein the step of operably relating at least one query term to another query term further comprises sharing at least one combination operator that is part of operably related query terms.

41. A method as in claim 32, wherein the contents of the set of data are capable of being described by one or more pieces of evidence, the method further comprising the steps of:

translating each query into one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and

operably relating each query term to each other query term that includes an equivalent evidence descriptor or combination operator by sharing each equivalent evidence descriptor or combination operator.

42. A method for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, the contents of the set of data capable of being described by one or more pieces of evidence, the method comprising the steps of:

inputting a plurality of queries;

translating each query into one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and

defining, for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator.

43. A method as in claim 42, wherein the step of defining further comprises defining, for each evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator.

44. An execution plan stored within a memory for use in controlling a system for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the execution plan comprising a plurality of independent queries, wherein each of the queries of the execution plan has one or more query terms and each query sharing a query term with another query so that the queries are operably related to another of the queries of the execution plan.

45. An execution plan as in claim 44, wherein each query identifies each other query that is operably related to the query.

46. An execution plan stored in a memory for use in evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data being described by one or more pieces of evidence, the execution plan comprising a plurality of queries, each query including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, wherein at least one evidence descriptor is shared by more than one query term.

47. An execution plan as in claim 46, wherein the execution plan includes at least one combination operator that is shared by more than one query term.

48. An execution plan as in claim 46, wherein, for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator is defined.

49. An execution plan stored in a memory for use in evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data being described by one or more pieces of evidence, the execution plan comprising a plurality of queries, each query including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, wherein each evidence descriptor of a query term that is equivalent to an evidence descriptor of another query term is shared with that query term, and wherein each combination operator of a query term that is equivalent to a combination operator of another query term is shared with that query term.

50. An execution plan stored in a memory for use in evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data capable of being described by one or more pieces of evidence, the execution plan comprising a plurality of queries wherein each query including one or more query terms, each query term including one or more evidence descriptors that can be operably related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, wherein for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator is defined.

51. An execution plan as in claim 50, wherein, for each evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator is defined.

52. A system for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, the contents of the set of data capable of being described by one or more pieces of evidence, the queries being arranged in an execution plan of queries in which each query is operably related to one or more other queries, each of the plurality of queries including one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence, the system comprising:

means for comparing each piece of evidence to one or more of the evidence descriptors as the data set is received;

means for identifying each evidence descriptor that is satisfied by a piece of evidence;

means for evaluating each query term that includes a satisfied evidence descriptor or another query term that has been satisfied to determine whether the query term is satisfied; and

means for identifying each query for which all query terms have been satisfied as a query that is satisfied by the set of data.

53. A system for evaluating a set of data to enable identification of, from a plurality of queries that each include at least one evidence descriptor, each candidate query that may be satisfied by the set of data, the system comprising:

means for identifying the type of each of the evidence descriptors;

means for identifying the type of each piece of evidence in the set of data;

means for comparing each piece of evidence in the set of data to each of the evidence descriptors that are of the same type as the piece of evidence; and

means for identifying each of the evidence descriptors that is satisfied by a piece of evidence, wherein only a query including a satisfied evidence descriptor can be a candidate query.

54. A system for evaluating a set of data to determine whether the set of data satisfies one or more of a plurality of queries, each query having a query term and an approximation of the query term, comprising:

means for identifying one or more candidate queries based on the approximation of the query term that may be satisfied by the set of data; and

means for evaluating each of the candidate queries based on the query term to determine which, if any, of the candidate queries are satisfied by the set of data.

55. A system for use in evaluating a set of data to determine whether the set of data satisfies one or more queries, the one or more queries including a plurality of evidence descriptors that can be compared to one or more pieces of evidence that represent a portion of the content of the set of data to ascertain whether a piece of evidence satisfies an evidence descriptor, the system comprising:

means for defining one or more types of evidence;

means for identifying the type or types of the evidence descriptors; and

means for modifying the one or more types of evidence in response to the identified type or types of evidence descriptors.

56. A system for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, comprising:

means for inputting a plurality of queries; and

means for operably relating each query to another query.

57. A system for constructing an execution plan of queries for use in evaluating a set of data to determine whether the set of data satisfies one or more of the queries, the contents of the set of data capable of being described by one or more pieces of evidence, the system comprising:

means for inputting a plurality of queries;

means for translating each query into one or more query terms, each query term including one or more evidence descriptors that can be related to a combination operator, each evidence descriptor describing a piece of evidence or the characteristics of a piece or pieces of evidence; and

means for defining, for at least one evidence descriptor or combination operator, a corresponding approximation of the evidence descriptor or combination operator.