Expressing frequent itemset counting operations

• US 20050044094A1
• Filed: 08/18/2003
• Published: 02/24/2005
• Est. Priority Date: 08/18/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Li, Wei, Mozes, Ari, Huang, Jiansheng
• Granted Patent: US 8,655,911 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2448 for particular applications; for extensibility, e.g. user defined types
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Techniques are provided for (1) extending SQL to support direct invocation of frequent itemset operations, (2) improving the performance of frequent itemset operations by clustering itemset combinations to more efficiently use previously produced results, and (3) making on-the-fly selection of the occurrence counting technique to use during each phase of a multiple phase frequent itemset operation. When directly invoked in an SQL statement, a frequent itemset operation may receive input from results of operations specified in the SQL statement, and provide its results directly to other operations specified in the SQL statement. By clustering itemset combinations, resources may be used more efficiently by retaining intermediate information as long as it is useful, and then discarding it to free up volatile memory. Dynamically selecting an occurrence counting technique allows a single frequent itemset operation to change the occurrence counting technique that it is using midstream, based on cost considerations and/or environmental conditions.

Claims

1. A method for performing a frequent itemset operation, the method comprising the steps of:

within a database server that supports a particular database language, parsing a database statement to detect within the database statement a construct that extends the particular database language;

in response to detection of said construct, the database server performing a frequent itemset operation as part of execution of the database statement.

2. The method of claim 1 wherein the particular database language is SQL.

3. The method of claim 1 wherein the construct is a table function.

4. The method of claim 1 wherein:

the database statement includes a first indication of a first input format;

the frequent itemset operation operates on input that conforms to said first input format; and

the method further comprises the steps of;

parsing a second database statement to detect within the second database statement the construct that extends a database language, wherein the second database statement includes a second indication of a second input format that is different from said first input format; and

in response to detection of said construct in said second database statement, the database server performing a second frequent itemset operation as part of execution of the second database statement, wherein the second frequent itemset operation operates on input that conforms to said second format.

5. The method of claim 4 wherein the first indication is identification of a first table function and the second indication is identification of a second table function.

6. The method of claim 1 wherein the frequent itemset operation uses, as input, a row source that is generated during execution of other operations specified in said database statement.

7. The method of claim 1 wherein the frequent itemset operation produces, as output, a row source that is used as input for other operations specified in said database statement.

8. The method of claim 1 wherein:

the database statement specifies a frequency threshold; and

the step of performing the frequent itemset operation includes performing the frequent itemset operation based on the frequency threshold specified in the database statement.

9. The method of claim 1 wherein:

the database statement specifies a minimum length; and

the step of performing the frequent itemset operation includes performing a frequent itemset operation whose results exclude all item sets that include fewer items than the minimum length specified in the database statement.

10. The method of claim 1 wherein:

the database statement specifies a maximum length; and

the step of performing the frequent itemset operation includes performing a frequent itemset operation whose results exclude all item sets that include more items than the maximum length specified in the database statement.

11. The method of claim 1 wherein:

the database statement specifies a set of one or more included items; and

the step of performing the frequent itemset operation includes performing a frequent itemset operation whose results exclude all itemsets that do not include all items in said set of one or more included items.

12. The method of claim 1 wherein the step of performing the frequent itemset operation includes performing a frequent itemset operation whose results identify

frequent itemsets, and

for each of the frequent itemsets, a count of how many item groups included the frequent itemset.

13. The method of claim 1 wherein the step of performing the frequent itemset operation includes performing a frequent itemset operation whose results identify

frequent itemsets, and

for each of the frequent itemsets, a count of how items are in the frequent itemset.

14. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

15. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

16. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

17. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

18. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

19. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

20. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

21. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

22. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

23. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

24. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

25. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

26. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.