SQL-based analytic algorithm for association

• US 6,611,829 B1
• Filed: 10/01/1999
• Issued: 08/26/2003
• Est. Priority Date: 10/02/1998
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Pricer, James Edward, Kerber, Randy Gerard, Anand, Tej, Tate, Brian Don
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): PHAM, HUNG Q
• Application Number:
  US09/410,528
• Time in Patent Office: 1,425 Days
• Field of Search: 707/6, 707/3, 707/509, 707/2, 707/10
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/961 Associative
• 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/99936 Pattern matching access
• 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

Abstract

A method, apparatus, and article of manufacture for performing data mining applications in a relational database management system. An analytic algorithm for association is performed by the relational database management system to measure one or more associations between a plurality of items in a stream of transaction data stored in the relational database, wherein the analytic algorithm for association creates at least one analytic model within an analytic logical data model from data residing in the relational database.

Claims

1. A system for performing data mining applications, comprising:

(a) a computer system having one or more data storage devices connected thereto;

(b) a relational database management system, executed by the computer system, for managing a relational database stored on the data storage devices and

(c) an analytic algorithm for association, performed by the relational database management system, for measuring one or more associations between a plurality of items in a stream of transaction data stored in the relational database, wherein the analytic algorithm for association creates at least one analytic model within an analytic logical data model from data residing in the relational database, and wherein the analytic algorithm for association extracts the transaction data into a base table in the relational database, builds one or more support tables for one or more of the items by joining the base table with itself and performing aggregation, constraint, and grouping functions thereon, and calculates support, confidence and lift by joining the support tables.

2. The system of claim 1, wherein the computer system is a massively parallel processing (MPP) computer system, and the analytic algorithm for association is decomposed into a plurality of steps that are executed concurrently in parallel by the massively processing computer system.

3. The system of claim 1, wherein the analytic algorithm for association further comprises an affinity analysis.

4. The system of claim 1, wherein the associations are relationships between one or more first items in an item group and one or more second items in the item group.

5. The system of claim 4, wherein the analytic algorithm for association further comprises means for analyzing the relationships to determine how they change over time.

6. The system of claim 1, wherein the analytic algorithm for association further comprises:

means for creating a temporary table in the relational database with a single value comprising a count of unique item groups in the base table.

7. The system of claim 1, wherein the base table contains at least a group identifier column and an item identifier column.

8. The system of claim 6, further comprising means for counting the item groups in the base table containing various combinations of items and for dividing the counted item groups by the count of unique item groups in the temporary table to obtain a support for each of the combinations.

9. The system of claim 1, wherein a first support table is a single item support table containing at least an item identifier and a support value for each item in the base table which contains a support value below a minimum specified support value of interest.

10. The system of claim 1, wherein a second support table is built from the base table by selecting only those values that have a certain pre-defined minimum level of support.

11. The system of claim 1, wherein the support tables for two or more items are built in preparation for analyzing combinations of two or more items.

12. The system of claim 4, wherein the support tables are joined using one or more joins selected from a group comprising:

(1) joining the support table matching the first item of the association, (2) joining the support table matching both first and second items of the association, and (3) joining the support table matching the second item of the association.

13. A method for performing data mining applications, comprising:

(a) managing a relational database stored on one or more data storage devices connected to a computer; and

(b) performing an analytic algorithm for association in the relational database management system to measure one or more associations between a plurality of items in a stream of transaction data stored in the relational database, wherein the analytic algorithm for association creates at least one analytic model within an analytic logical data model from data residing in the relational database, and wherein the analytic algorithm for association extracts the transaction data into a base table in the relational database, builds one or more support tables for one or more of the items by joining the base table with itself and performing aggregation, constraint, and grouping functions thereon, and calculates support, confidence and lift by joining the support tables.

14. The method of claim 13, wherein the computer is a massively parallel processing (MPP) computer system, and the analytic algorithm for association is decomposed into a plurality of steps that are executed concurrently in parallel by the massively processing computer system.

15. The method of claim 13, wherein the analytic algorithm for association farther comprises an affinity analysis.

16. The method of claim 13, wherein the associations are relationships between one or more first items in an item group and one or more second items in the item group.

17. The method of claim 16, wherein the analytic algorithm for association further comprises analyzing the relationships to determine how they change over time.

18. The method of claim 16, wherein the support tables are joined using one or more joins selected from a group comprising:

(1) joining the support table matching the first item of the association, (2) joining the support table matching both first and second items of the association, and (3) joining the support table matching the second item of the association.

19. The method of claim 13, wherein the analytic algorithm for association further comprises creating a temporary table in the relational database with a single value comprising a count of unique item groups in the base table.

20. The method of claim 19, further comprising counting the item groups in the base table containing various combinations of items and for dividing the counted item groups by the count of unique item groups in the temporary table to obtain a support for each of the combinations.

21. The method of claim 13, wherein the base table contains at least a group identifier column and an item identifier column.

22. The method of claim 13, wherein a first support table is a single item support table containing at least an item identifier and a support value for each item in the base table which contains a support value below a minimum specified support value of interest.

23. The method of claim 13, wherein a second support table is built from the base table by selecting only those values that have a certain pre-defined minimum level of support.

24. The method of claim 13, wherein the support tables for two or more items are built in preparation for analyzing combinations of two or more items.

25. An article of manufacture comprising logic embodying a method for performing data mining applications, comprising:

(a) managing a relational database stored on one or more data storage devices connected to a computer; and

(b) performing an analytic algorithm for association in the relational database management system to measure one or more associations between a plurality of items in a stream of transaction data stored in the relational database, therein the analytic algorithm for association creates at least one analytic model with an analytic logical data model from data residing in the relational database, and wherein the analytic algorithm for association extracts the transaction data into a base cable in the relational database, builds one or more support tables for one or more of the items by joining the base table with itself and performing aggregation, constraint, and grouping functions thereon, and calculates support, confidence and lift by joining the support tables.

26. The article of manufacture of claim 25, wherein the computer is a massively parallel processing (MPP) computer system, and the analytic algorithm for association is decomposed into a plurality of steps that are executed concurrently in parallel by the massively processing computer system.

27. The article of manufacture of claim 25, wherein the analytic algorithm for association further comprises an affinity analysis.

28. The article of manufacture of claim 25, wherein the associations are relationships between one or more first items in an item group and one or more second items in the item group.

29. The article of manufacture of claim 28, wherein the analytic algorithm for association comprises analyzing the relationships to determine how they change over time.

30. The article of manufacture of claim 28, wherein the support tables are joined using one or more joins selected from a group comprising:

(1) joining the support table matching the first item of the association, (2) joining the support table matching both first and second items of the association, and (3) joining the support table matching the second item of the association.

31. The article of manufacture of claim 25, wherein the analytic algorithm for association further comprises creating a temporary table in the relational database with a single value comprising a count of unique item groups in the base table.

32. The article of manufacture of claim 31, further comprising counting the item groups in the base table containing various combinations of items and for dividing the counted item groups by the count of unique item groups in the temporary table to obtain a support for each of the combinations.

33. The article of manufacture of claim 25, wherein the base table contains at least a group identifier column and an item identifier column.

34. The article of manufacture of claim 25, wherein a first support table is a single item support table containing at least an item identifier and a support value for each item in the base table which contains a support value below a minimum specified support value of interest.

35. The article of manufacture of claim 25, wherein a second support table is built from the base table by selecting only those values that have a certain pre-defined minimum level of support.

36. The article of manufacture of claim 25, wherein the support tables for two or more items are built in preparation for analyzing combinations of two or more items.