US6044366A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Use of the UNPIVOT relational operator in the efficient gathering of sufficient statistics for data mining
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-03-16
•
Granted: 2000-03-28
•
Expires: 2018-03-16
Abstract
Abstract The invention concerns a method and apparatus for generating a tabulation of counts of occurrences of value combinations of a set of attributes over a relation consisting of a set of database records. The gathered counts (also referred to as sufficient statistics) of attribute occurrences or correlation counts is most preferably used in building a classification or density estimation model from the database records that can be used to predict some attribute values based on other attribute values. A new SQL operator designated the `UNPIVOT` operator operates by scanning the database records and for each record reorganizes that data to form an UNPIVOTED data record that include the combinations of attribute name, attribute value and the values for one or more selected class attributes. The UNPIVOTED table can be used to produce the desired sufficient statistics in one scan of the data using standard database engines. While materialization of UNPIVOTED table would cause a large added scan cost overhead, the UNPIVOT operator allows us to achieve the counts without the added cost by combining the UNPIVOT operator with other SQL `select` and `group by` operators the UNPIVOTED table can be counted without the need for materializing it. The result is a guaranteed one pass algorithm that does not incur the added scan cost factor. The savings in scan cost can extend to several orders of magnitude compared to other methodologies for getting the counts supported by current database engines. The sufficient statistics so gathered can be used to drive a variety of data mining algorithms.
Inventors
- 👤 Goetz Graffe
- 👤 Usama Fayyad
- 👤 Surajit Chaudhuri
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:24
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/283; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99936; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
124 words
A method of generating a tabulation of occurrences of one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) scanning the database records; b) for each scanned database record, reformatting the data within said record from a first record format that includes attribute values for one or more attribute names and values for a selected one or more class attributes into a second record format with records that include combinations of attribute names, attribute values and the values for the selected one or more class attributes; and c) grouping combinations of data that are scanned from the database to build statistics for the one or more class attributes.
Claim 2
Independent Claim
124 words
A method of generating a tabulation of occurrences of one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) scanning the database records; b) for each scanned database record, reformatting the data within said record from a first record format that includes attribute values for one or more attribute names and values for a selected one or more class attributes into a second record format with records that include combinations of attribute names, attribute values and the values for the selected one or more class attributes; and c) grouping combinations of data that are scanned from the database to build statistics for the one or more class attributes.
Claim 3
Dependent Claim
26 words
The method of claim 1 wherein the steps of reformatting and grouping are performed without materializing a complete table of reorganized records on a storage device.
Claim 4
Dependent Claim
21 words
The method of claim 1 wherein the steps of reformatting and grouping are performed in parallel in a multiprocessor computing system.
Claim 5
Dependent Claim
22 words
The method of claim 1 wherein to perform the steps of scanning and reformatting an SQL language processor processes an UNPIVOT command.
Claim 6
Independent Claim
141 words
A method of generating a tabulation of occurrences of selected one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) scanning the database records; b) for each scanned database record, reformatting the data within said record into records that include combinations of attribute name, attribute value and the selected one or more class attributes, the SQL language processor processes the UNPIVOT command to reformat the data; and c) grouping combinations of data that are scanned from the database to build statistics for the one or more class attributes, the scanning performed by an SQL language processor that processes an UNPIVOT command the UNPIVOT command is combined with a SELECT and a GROUP BY SQL command to provide a counts table without producing an UNPIVOTED table.
Claim 7
Independent Claim
141 words
A method of generating a tabulation of occurrences of selected one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) scanning the database records; b) for each scanned database record, reformatting the data within said record into records that include combinations of attribute name, attribute value and the selected one or more class attributes, the SQL language processor processes the UNPIVOT command to reformat the data; and c) grouping combinations of data that are scanned from the database to build statistics for the one or more class attributes, the scanning performed by an SQL language processor that processes an UNPIVOT command the UNPIVOT command is combined with a SELECT and a GROUP BY SQL command to provide a counts table without producing an UNPIVOTED table.
Claim 8
Dependent Claim
40 words
The method of claim 5 wherein the SQL processor performs an SQL query of the form: Select AttrName AttrVal, Class, Count(*) From Table1.UNPIVOT(AttrVal for AttrName in Attr -- 1, . . . Attr -- m) Group by AttrName, AttrVal, Class.
Claim 9
Dependent Claim
18 words
The method of claim 1 wherein the steps of reformatting and grouping are performed in a pipelined process.
Claim 10
Dependent Claim
26 words
The method of claim 1 wherein more than one class attribute is evaluated to build a statistical counts table with each scan of the database records.
Claim 11
Independent Claim
160 words
A method of generating a tabulation of occurrences of selected one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) scanning the database records, the scanning performed by an SQL language processor that processes an UNPIVOT command; b) for each scanned database record, reformatting the data within said record into records that include combinations of attribute name, attribute value and the selected one or more class attributes, the reformatting performed by the SQL language processor that processes the UNPIVOT command; and c) grouping combinations of data that are scanned from the database to build statistics for more than one class attributes and more than one class attribute is evaluated to build a database classifier and wherein a statistical count table is built during the process of building the database classifier by means of multiple invocations of the UNPIVOT operator to data in the database.
Claim 12
Independent Claim
160 words
A method of generating a tabulation of occurrences of selected one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) scanning the database records, the scanning performed by an SQL language processor that processes an UNPIVOT command; b) for each scanned database record, reformatting the data within said record into records that include combinations of attribute name, attribute value and the selected one or more class attributes, the reformatting performed by the SQL language processor that processes the UNPIVOT command; and c) grouping combinations of data that are scanned from the database to build statistics for more than one class attributes and more than one class attribute is evaluated to build a database classifier and wherein a statistical count table is built during the process of building the database classifier by means of multiple invocations of the UNPIVOT operator to data in the database.
Claim 13
Independent Claim
138 words
A method of generating a tabulation of occurrences of selected one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) reorganizing the database records into a specified format by causing an SQL language processor to execute a PIVOT SQL command; b) scanning the database records the scanning performed by an SQL language processor that processes an UNPIVOT command; c) for each scanned database record, reformatting the data within said record into records that include combinations of attribute name, attribute value and the selected one or more class attributes, the reformatting performed by the SQL language processor that processes the UNPIVOT command; and d) grouping combinations of data that are scanned from the database to build statistics for one or more class attributes.
Claim 14
Independent Claim
138 words
A method of generating a tabulation of occurrences of selected one or more class attributes of database records as a combination of other attributes and attribute values in the database records comprising the steps of a) reorganizing the database records into a specified format by causing an SQL language processor to execute a PIVOT SQL command; b) scanning the database records the scanning performed by an SQL language processor that processes an UNPIVOT command; c) for each scanned database record, reformatting the data within said record into records that include combinations of attribute name, attribute value and the selected one or more class attributes, the reformatting performed by the SQL language processor that processes the UNPIVOT command; and d) grouping combinations of data that are scanned from the database to build statistics for one or more class attributes.
Claim 15
Dependent Claim
29 words
The method of claim 1 wherein the one or more attributes are duplicated to form the class attributes of a table of records prior to beginning the scanning step.
Claim 16
Independent Claim
150 words
A method for use with a database classifier on a computer including a computer storage device for storing the database; said database classifier processing statistical data from the records of the database, said method characterized by the steps of: a) scanning records of a database and reformatting each scanned record into a set of records that are based on the contents of the database record attributes so that each of the database records provides multiple records containing combinations of attribute names with attribute types for that record along with the contents of a classifier variable; b) counting instances of the classifier variable for each of the records in the set of records; c) grouping the results of the counting step into a count table for use by the classifier; and d) scanning the database for other records to iteratively build a complete count table for use by the database classifier.
Claim 17
Independent Claim
150 words
A method for use with a database classifier on a computer including a computer storage device for storing the database; said database classifier processing statistical data from the records of the database, said method characterized by the steps of: a) scanning records of a database and reformatting each scanned record into a set of records that are based on the contents of the database record attributes so that each of the database records provides multiple records containing combinations of attribute names with attribute types for that record along with the contents of a classifier variable; b) counting instances of the classifier variable for each of the records in the set of records; c) grouping the results of the counting step into a count table for use by the classifier; and d) scanning the database for other records to iteratively build a complete count table for use by the database classifier.
Claim 18
Dependent Claim
20 words
The method of claim 12 wherein the computer includes a processor that executes software for processing multiple database records simultaneously.
Claim 19
Dependent Claim
25 words
The method of claim 12 wherein the count table is built incrementally for each record without maintaining a tabulation of the re-organized set of records.
Claim 20
Independent Claim
134 words
A method for use with a database classifier; said database classifier processing statistical data from the records of the database; said method characterized by the steps of: a) scanning a database record and creating multiple associated records in a temporary store where the contents of each of the associated records contains a combination of a record attribute and an attribute value of the database record and a classifier variable of said database record; b) determining a count of the combinations of record attribute name and attribute values for each value or value range of the classifier variable; and c) scanning other records from the database and determining counts for the other records; and d) preparing a tabulation of the counts that are grouped by attribute name, attribute value and classifier value or value range.
Claim 21
Independent Claim
134 words
A method for use with a database classifier; said database classifier processing statistical data from the records of the database; said method characterized by the steps of: a) scanning a database record and creating multiple associated records in a temporary store where the contents of each of the associated records contains a combination of a record attribute and an attribute value of the database record and a classifier variable of said database record; b) determining a count of the combinations of record attribute name and attribute values for each value or value range of the classifier variable; and c) scanning other records from the database and determining counts for the other records; and d) preparing a tabulation of the counts that are grouped by attribute name, attribute value and classifier value or value range.
Claim 22
Dependent Claim
28 words
The method of claim 15 wherein multiple database records are scanned into a computer memory and the determining step is performed in parallel on said multiple database records.
Claim 23
Dependent Claim
135 words
Apparatus for use in creating a database classifier; said database classifier processing statistical data from the records of the database; the apparatus comprising: a) data access means for reading database records from the database; b) memory means for storing temporary data records based on the data in a database record; and c) processor means for creating temporary data records in said memory means where the contents of each of said temporary records contains a combination of an attribute name and an attribute value of the database record for different classifier attribute values of said database; said processor means including means for determining combinations of attribute name and attribute value for the temporary records; and preparing a tabulation of the counts that are grouped by attribute name, attribute value and classifier value from the temporary records.
Claim 24
Dependent Claim
135 words
Apparatus for use in creating a database classifier; said database classifier processing statistical data from the records of the database; the apparatus comprising: a) data access means for reading database records from the database; b) memory means for storing temporary data records based on the data in a database record; and c) processor means for creating temporary data records in said memory means where the contents of each of said temporary records contains a combination of an attribute name and an attribute value of the database record for different classifier attribute values of said database; said processor means including means for determining combinations of attribute name and attribute value for the temporary records; and preparing a tabulation of the counts that are grouped by attribute name, attribute value and classifier value from the temporary records.
Claim 25
Dependent Claim
185 words
Apparatus for use in creating a database classifier, said classifier processing statistical data from the records of the database; the apparatus comprising: a) data access means for reading database records from the database; b) memory means for temporarily storing data records based on the data in a database record; and c) processor means for creating temporary data records in said memory means where the contents of each of the temporary records contains a combination of an attribute name and an attribute value of the database record for different classifier variable values of said database; said processor means including access means for accessing multiple records from the database and determining combinations of attribute name and attribute value for the other records; and preparing a tabulation of the counts that are grouped by attribute name, attribute value and classifier value; the processor means comprises means for processing SQL commands and wherein an UNPIVOT SQL command reformats the data of a data table which in combination with SQL SELECT and GROUP BY commands creates combinations of attributes and attribute values in a tabulated form in said memory means.
Claim 26
Dependent Claim
185 words
Apparatus for use in creating a database classifier, said classifier processing statistical data from the records of the database; the apparatus comprising: a) data access means for reading database records from the database; b) memory means for temporarily storing data records based on the data in a database record; and c) processor means for creating temporary data records in said memory means where the contents of each of the temporary records contains a combination of an attribute name and an attribute value of the database record for different classifier variable values of said database; said processor means including access means for accessing multiple records from the database and determining combinations of attribute name and attribute value for the other records; and preparing a tabulation of the counts that are grouped by attribute name, attribute value and classifier value; the processor means comprises means for processing SQL commands and wherein an UNPIVOT SQL command reformats the data of a data table which in combination with SQL SELECT and GROUP BY commands creates combinations of attributes and attribute values in a tabulated form in said memory means.
Claim 27
Dependent Claim
27 words
The apparatus of claim 17 wherein the processor means tabulates multiple class variables in terms of each other as well as in terms of other non-class variables.
Claim 28
Dependent Claim
20 words
The apparatus of claim 17 wherein the processor means comprises multiple central processing units for parallel processing of database records.
Claim 29
Dependent Claim
29 words
The apparatus of claim 17 wherein the processor means includes a pipeline processor for simultaneously executing the fetching of data and the reformatting of the data in the database.
References Cited (Backward Citations)
US5201047A
Cited
US5713020A
Cited
US5819282A
Cited
US5511190A
Cited
US5966139A
Cited
US5710915A
Cited
US5748905A
Cited
US5878426A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-28 | 2003-09-27 | 2004-03-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-28 | 2007-09-27 | 2008-03-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-28 | 2011-09-27 | 2012-03-28 | $7700.00 | Window Closed / Lapsed |