Efficient evaluation of queries with mining predicates

• US 7,346,601 B2
• Filed: 06/03/2002
• Issued: 03/18/2008
• Est. Priority Date: 06/03/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sarawagi, Sunita, Chaudhuri, Surajit, Narasayya, Vivek
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US10/161,308
• Publication Number:
  US 20030229635A1
• Time in Patent Office: 2,115 Days
• Field of Search: 707/5, 707 2- 4, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A method for evaluating a user query on a database having a mining model that classifies records contained in the database into classes when the query comprises at least one mining predicate that refers to a class of database records. An upper envelope is derived for the class referred to by the mining predicate corresponding to a query that returns a set of database records that includes all of the database records belonging to the class. The upper envelope is included in the user query for query evaluation. The method may be practiced during a preprocessing phase by evaluating the mining model to extract a set of classes of the database records and deriving an upper envelope for each class. These upper envelopes are stored for access during user query evaluation.

Claims

1. A computer implemented method for evaluating a user query on a database having a mining model that classifies records contained in the database into classes and assigns a class label to each record, wherein the query comprises at least one mining predicate that refers to a class label of database records, the method comprising the steps of:

deriving an upper envelope for the class label referred to by the mining predicate wherein the upper envelope is a query predicate of the form M_c({right arrow over (x)}) which corresponds to a query predicate that returns a set of database records that includes all of the database records having that class label assigned thereto; and

including the upper envelope with the user query for query evaluation of the user query on the database records of the database;

wherein the deriving step is performed during a preprocessing phase by;

building a mining model;

evaluating the mining model to extract a set of classes and class labels for the database records;

deriving an upper envelope for each class label while building the model; and

storing the upper envelopes for access during user query evaluation.

2. The computer implemented method of claim 1 comprising the step of forming an upper envelope by combining a plurality of upper envelopes.

3. The computer implemented method of claim 2 wherein the user query seeks to return data records whose class label is a member of a given set of class labels and wherein the upper envelope comprises a disjunct of the upper envelopes for each class label in the set of class labels referred to by the user query.

4. The computer implemented method of claim 2 wherein the database has at least two mining models and wherein the user query seeks to return data records whose class label has been assigned the same class label by all mining models and wherein the upper envelope is formed by enumerating class labels for each of the mining models, finding upper envelopes for each mining model by forming a conjunctive expression of the upper envelope for each class label in the mining model, and taking the disjunction of these conjunctive expressions over all class labels.

5. The computer implemented method of claim 2 wherein the mining model assigns a class label to a data record that predicts the value of a given column in the data record and the user query seeks to return data records in which the predicted value matches the actual value in the data column and wherein the upper envelope for that class is formed by enumerating each class label for the mining model, finding an upper envelope for each class label, forming a conjunctive expression of the upper envelope and a predicate that selects data records where the given column is equal to the class label, and forming a disjunctive expression of these conjunctive expressions over all class labels.

6. The computer implemented method of claim 1 wherein the mining model is a decision tree comprising a root node connected to test nodes having test conditions and leaf nodes having a class label and wherein the upper envelope for a given class label is derived by forming a conjunct of the test conditions between the root and each leaf node having the given class label and forming a disjunct of the conjuncts of the test conditions.

7. The computer implemented method of claim 1 wherein the mining model is a rule based learner comprising a set of if-then rules, each rule having a body comprising conditions on the data attributes and a head comprising one of the class labels and wherein the upper envelope for a given class label is derived by forming a disjunct of the rules having the given class label as the head.

8. The computer implemented method of claim 7 wherein the boundaries are described in terms of ranges of attribute values.

9. The computer implemented method of claim 7 wherein the upper envelope for a given class label is derived by describing an initial region that covers the entire n dimensional space, removing sub-regions that do not contain any data records having the given class label, and describing the resulting region.

10. The computer implemented method of claim 9 wherein a sub-region is removed from the initial region by calculating a probability that the data records in the sub-region have a given class label and removing the sub-region if the probability is below a predetermined threshold.

11. The computer implemented method of claim 10 wherein a probability that data records in the sub-region having a certain class label is calculated for all class labels and the upper envelope for the given class label is derived by removing a sub-region based on a comparison between the probability for the given class label and the probabilities for the other class labels.

12. The computer implemented method of claim 9 wherein sub-regions that contain data records having different class labels are shrunk and re-evaluated to determine if they should be removed.

13. The computer implemented method of claim 9 wherein sub-regions that contain data records having different class labels are split into sub-regions and the split sub-regions are re-evaluated to determine if they should be removed.

14. The computer implemented method of claim 13 wherein the sub-regions are split in a manner that minimizes entropy.

15. The computer implemented method of claim 9 comprising the step of merging sub-regions that have been removed.

16. The computer implemented method of claim 7 wherein the mining model determines each class as a centroid and a region surrounding the centroid and wherein the upper envelope for a given class label is derived by describing a set of rectangular regions that cover the region for the given class label.

17. The computer implemented method of claim 1 wherein the upper envelopes are removed prior to execution of the user query.

18. The computer implemented method of claim 1 wherein the size of the upper envelope is limited to a predetermined number of terms.

19. The method of claim 1 wherein the data records have n attributes and the mining model assigns class labels to each data record and each class label of each data record is assigned a position based on attribute values in an n dimensional space having a dimension for each attribute and wherein the upper envelope for a given class label is derived by forming a disjunct of boundaries of regions that cover all data records having the given class label.

20. A computer readable medium having computer executable instruction stored thereon for performing method steps for evaluating a user query on a database having a mining model that classifies records contained in the database into classes and assigns a class label to each record, wherein the query comprises at least one mining predicate that refers to a class label of database records, the method steps comprising:

deriving an upper envelope for the class label referred to by the mining predicate wherein the upper envelope is a query predicate of the form M_c({right arrow over (x)}) which corresponds to a query predicate that returns a set of database records that includes all of the database records having that class label assigned thereto; and

including the upper envelope with the user query for query evaluation of the user query on the database records of the database;

wherein the deriving step is performed during a preprocessing phase by;

building a mining model;

evaluating the mining model to extract a set of classes and class labels for the database records;

deriving an upper envelope for each class label while building the model; and

storing the upper envelopes for access during user query evaluation.

21. The computer readable medium of claim 20 wherein the method steps comprise the step of forming an upper envelope by combining a plurality of upper envelopes.

22. The computer readable medium of claim 21 wherein the user query seeks to return data records whose class label is a member of a given set of class labels and wherein the upper envelope comprises a disjunct of the upper envelopes for each class label in the set of class labels referred to by the user query.

23. The computer readable medium of claim 21 wherein the database has at least two mining models and wherein the user query seeks to return data records whose class label has been assigned the same class label by all mining models and wherein the upper envelope is formed by enumerating class labels for each of the mining models, finding upper envelopes for each mining model by forming a conjunctive expression of the upper envelope for each class label in the mining model, and taking the disjunction of these conjunctive expressions over all class labels.

24. The computer readable medium of claim 21 wherein the mining model assigns a class label to a data record that predicts the value of a given column in the data record and the user query seeks to return data records in which the predicted value matches the actual value in the data column and wherein the upper envelope for that class is formed by enumerating each class label for the mining model, finding an upper envelope for each class label, forming a conjunctive expression of the upper envelope and a predicate that selects data records where the given column is equal to the class label, and forming a disjunctive expression of these conjunctive expressions over all class labels.

25. The computer readable medium of claim 21 wherein the mining model is a decision tree comprising a root node connected to test nodes having a test condition and leaf nodes having a class label and wherein the upper envelope for a given class label is derived by forming a conjunct of the test conditions between the root and each leaf node having the given class label and forming a disjunct of the conjuncts of the test conditions.

26. The computer readable medium of claim 20 wherein the mining model is a rule based learner comprising a set of if-then rules, each rule having a body comprising conditions on the data attributes and a head comprising one of the class labels and wherein the upper envelope for a given class label is derived by forming a disjunct of the rules having the given class label as the head.

27. The computer readable medium of claim 20 wherein the data records have n attributes and the mining model assigns class labels to each data record and each class label of each data record is assigned a position based on attribute values in an n dimensional space having a dimension for each attribute and wherein the upper envelope for a given class label is derived by forming a disjunct of boundaries of regions that cover all data records having the given class label.

28. The computer readable medium of claim 27 wherein the boundaries are described in terms of ranges of attribute values.

29. The computer readable medium of claim 27 wherein the upper envelope for a given class label is derived by describing an initial region that covers the entire n dimensional space, removing sub-regions that do not contain any data records having the given class label, and describing the resulting region.

30. The computer readable medium of claim 29 wherein sub-regions that contain data records having different class labels are shrunk and re-evaluated to determine if they should be removed.

31. The computer readable medium of claim 29 wherein sub-regions that contain data records having different class labels are split into sub-regions and the split sub-regions are re-evaluated to determine if they should be removed.

32. The computer readable medium of claim 29 wherein the method steps comprise the step of merging sub-regions that have been removed.

33. The computer readable medium of claim 27 wherein the mining model determines each class as a centroid and a region surrounding the centroid and wherein the upper envelope for a given class label is derived by describing a set of rectangular regions that cover the region for the given class label.

34. An apparatus for evaluating a user query on a database having a mining model that classifies records contained in the database into classes and assigns a class label to each record, wherein the query comprises at least one mining predicate that refers to a class label of database records, the apparatus comprising:

means for deriving an upper envelope for the class label referred to by the mining predicate wherein the upper envelope is a query predicate of the form M_c({right arrow over (x)}) which corresponds to a query predicate that returns a set of database records that includes all of the database records having that class label associated therewith; and

means for including the upper envelope with the user query for query evaluation of the user query on the database records of the database;

wherein the means for deriving an upper envelope does so during a preprocessing phase by;

building a mining model;

evaluating the mining model to extract a set of classes and class labels for the database records;

deriving an upper envelope for each class label while building the model; and

storing the upper envelopes for access during user query evaluation.

35. The apparatus of claim 34 comprising means for forming an upper envelope by combining a plurality of upper envelopes.