Efficient multidimensional data aggregation operator implementation

Abstract

An efficient implementation of a multidimensional data aggregation operator that generates all aggregates and super-aggregates for all available values in a results set by first generating a minimal number of aggregates at the lowest possible system level using a minimal number of function calls, and second categorizing the aggregate function being applied and applying the aggregate function with the fewest possible function calls. The aggregates are generated from a union of roll-ups of the n attributes to the GROUP BY clause of the SELECT statement. The number of roll-ups are minimized by including a barrel shift of the attributes being rolled up. A scoreboard array of 2.sup.n bits is updated during the roll-up and barrel shifting process to keep track of which roll-ups are complete and with are not yet complete. Generating super-aggregates is further optimized by identifying the type of aggregate function being applied and facilitating the most efficient application of the aggregate function. A lter.sub.-- super() function is implemented to facilitate the most efficient application of algebraic aggregate functions that require access to intermediate aggregate data that heretofore was not available to any algebraic aggregation operator.

Claims

What is claimed is:

1. A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising:

identifying a roll-up string of attributes from said results set;

generating at least one aggregate from said roll-up string by way of a minimum union of roll-up operator calls based on a barrel shift of said roll-up string;

saving said at least one aggregate in said data cube; and

generating at least one super-aggregate from said at least one aggregate by way of a minimum number of aggregation function calls dictated by an aggregation function classification selected from a group of aggregation categories consisting of: distributive, algebraic, and holistic.

2. A method according to claim I wherein said step of generating at least one aggregate includes:

executing a roll-up operation on said roll-up string;

executing said barrel shift of said roll-up string; and

executing a roll-up operation on said barrel shift of said roll-up string.

3. A method according to claim 2 including:

maintaining a scoreboard array of one scoreboard bit entry for each roll-up aggregate on said roll-up string;

examining said scoreboard array to determine when a complete set of said at least one aggregate exists; and

executing a roll-up operation on an attribute string associated with each unset scoreboard bit entry.

4. A method according to claim 3 including:

translating a base 10 scoreboard bit entry position in said scoreboard array to a base 2 equivalent; and

identifying said attribute string associated with said base 10 scoreboard bit entry position by way of said base 2 equivalent wherein a first binary value indicates a presence of an attribute in said attribute string and a second binary setting opposite said first binary value indicates an absence of an attribute in said attribute string.

5. A computer-readable storage device containing instructions for controlling a computer system to perform the steps of claim 4.

6. A method according to claim 1 wherein said step of generating at least one super-aggregate includes:

identifying an aggregate function as an algebraic aggregate function;

assigning a handle to each value presently in said data cube; and

executing at least one iteration of said algebraic aggregate function to fold each of said at least one sub-aggregate into at least one super-aggregate.

7. A computer readable medium containing computer executable instructions to perform a method for generating a data cube from a results set of a database query, said method comprising:

generating at least one aggregate from said results set by way of a minimum union of roll-up operator calls on a barrel shift of an attribute set;

saving said at least one aggregate in said data cube; and

categorizing an applicable aggregation function according to a group of aggregation categories consisting of: distributive, algebraic, and holistic;

assigning a handle to each value presently in said data cube that is subject to aggregation by an algebraic aggregation function; and

generating at least one super-aggregate from said at least one sub-aggregate by way of a minimum number of aggregation function calls dictated by said aggregation function category.

8. A computer-readable storage device containing instructions for controlling a computer system to perform the steps of claim 7.

9. A method according to claim 7 wherein said step of generating at least one aggregate includes:

executing a roll-up operation on said attribute set from said results set;

executing said barrel shift of said attribute set; and

executing a roll-up operation on said barrel shift of said attribute set.

10. A method according to claim 9 including:

maintaining a scoreboard array of one scoreboard bit entry for each roll-up aggregate on said attribute set;

examining said scoreboard array to determine when a complete set of said at least one aggregate exists; and

executing a roll-up operation on an attribute string associated with each unset scoreboard bit entry.

11. A method according to claim 7 wherein said step of generating at least one super-aggregate includes:

executing, in response to said aggregate function being a said algebraic aggregate function, at least one iteration of said algebraic aggregate function to fold each of said at least one sub-aggregate into at least one super-aggregate.

12. A computer readable medium containing computer executable instructions to perform a method comprising:

determine a minimum plurality of aggregate operations required for n attributes of an n-dimensional results set;

executing said minimum plurality of aggregate operations in a manner comprising;

executing an aggregate roll-up operation on said n attributes;

repeatedly generating a unique barrel shift sub-set string of said n attributes and executing said aggregate roll-up operation on said unique barrel shift sub-set string until no unique barrel shift set string of said n attributes exists;

tracking completed aggregations of said aggregate roll-up operation in a scoreboard array;

examining said scoreboard array to verify that a complete set of aggregates exists;

executing a roll-up operation on an attribute string associated with

each unset entry in said scoreboard array; and

generating at least one super-aggregate from said complete set of sub-aggregates dictated by at least one aggregate function selected from a group of aggregate function categories consisting of: distributive, algebraic, and holistic.

13. A method according to claim 12 wherein said step of generating at least one super-aggregate includes:

identifying an aggregate function as an algebraic aggregate function;

assigning a handle to each value presently in said data cube; and

executing at least one iteration of said algebraic aggregate function to fold each of said at least one sub-aggregate into at least one super-aggregate.

14. A computer-readable storage device containing instructions for controlling a computer system to perform the steps of claim 13.

Description

FIELD OF THE INVENTION

The present invention relates to the field of database data aggregation operators, and more particularly to an efficient implementation of a multidimensional generalization of the data aggregation operators.

PROBLEM

Data analysis applications aggregate data across different dimensions of a data set to look for anomalies or unusual patterns in the data set. However, existing Structured Query Language (SQL) aggregate functions and operators, such as the GROUP BY operator have limited usefulness because they produced only zero-dimensional or one-dimensional aggregates. To accommodate maximum data aggregation, an N-dimensional generalization of the existing aggregation operators was created called the CUBE operator. The term CUBE operator is used throughout this document to refer generally to any SQL operator designed as an n-dimensional generalization of at least one existing SQL aggregation operator. The term data cube is used throughout this document to refer generally to any n-dimensional results set generated by a CUBE operator.

The CUBE operator is a switch in the GROUP BY clause of the SELECT statement. The CUBE operator generalizes the histogram, cross-tabulation, roll-up drill-down, and sub-total aggregation constructs of existing data analysis applications to generate aggregates and super-aggregates for all elements within the GROUP BY clause. Because the CUBE operator generates a multi-dimensional data result set called a data cube instead of the typical zero-dimensional or one-dimensional data results set, and because the data cube is relational, the CUBE operator can be imbedded in complex non-procedural data analysis programs.

The CUBE operator is used with an aggregate function to generate additional rows in a results set. Columns, also known as elements, that are specified in a GROUP BY clause are cross-referenced to produce a superset of groups. The aggregate function specified with the CUBE operator is applied to these groups to produce summary values for the additional super-aggregate rows that are added to the results set. The number of extra groups in the results set is determined by the number of elements in the GROUP BY clause. The aggregate function is applied to the cross-referenced elements to generate the super-aggregates. Every possible combination of the elements in the GROUP BY clause is used to generate the super-aggregates. Thus, if there are n elements in the GROUP BY clause, then there are 2.sup.n -1 possible super-aggregate combinations added to the results set. Mathematically, the super-aggregate combinations form an n-dimensional cube, which is how the operator got its name. Examples of aggregate functions that can be used with a CUBE operator include, but are not limited to, AVE, SUM, MAX, MIN, and COUNT.

Applying the CUBE operator to a company sales management report, for example, that records sales personnel, customers, products, and quantities sold of each produce, a SELECT statement used with the COUNT aggregate function produces a result set of how many of each product were sold, to which customers, and by which sales person. By then applying the CUBE operator, the result set is expanded to include a cross-reference of products that particular customers frequently purchase, which sales personnel sell the most of a particular product, and which products are the most popular overall. By using a visualization application or other analysis tool, the data cube results set can be fed into charts and graphs that convey results and relationships that are easily interpreted by the end user.

However, one significant problem persists with existing methods for generating a data cube is that existing CUBE operator implementations consume too much time and processing resources to an extent that adversely impacts end user response time to visualizing the results of a query. Existing methods for generating aggregates in a given dimension include performing a straight forward aggregation operation on each set of elements in each dimension regardless of repeating aggregations. Existing methods for generating super-aggregates in a given dimension or across dimensions include a straight forward aggregation operation on each set of aggregates in each dimension regardless of repeating aggregations. Thus, the time and processing resources required to generate the data cube must be minimized to maintain acceptable end user response times.

SUMMARY

The present invention solves the above stated problem by an efficient implementation of a multidimensional data aggregation operator that generates all aggregates and super-aggregates for all available values in a results set. Efficiently implementing a multidimensional data aggregation operator that generates all aggregates and super-aggregates for all available values in a results set is accomplished by first generating a minimal number of aggregates at the lowest possible system level. For an n-dimensional data cube there are n| possible roll-up strings, however, the minimal number of aggregates for an n-dimensional data cube requires only a series of Binomial(n,n/2) roll-ups. The aggregates are generated from a union of roll-ups of the attributes to the GROUP BY clause of the SELECT statement. To minimize the number of roll-ups required, a barrel shifting scheme is used to generate only the specific additional ones of the roll-up aggregates required for a complete set of aggregates. A scoreboard array of 2.sup.n bits is updated during the roll-up and barrel shifting process to keep track of which roll-ups are complete and which are not yet complete.

Generating super-aggregates is further optimized by identifying the type of aggregate function being applied and facilitating the most efficient application of the aggregate function. In one preferred embodiment the types of aggregate functions are categorized as either distributive, algebraic, or holistic. A new lter.sub.-- super() function is implemented to facilitate the most efficient application of algebraic aggregate functions that require access to intermediate aggregate data that heretofore was not available to any algebraic aggregation operator. The lter.sub.-- super() function has additional application in situations where parallel database processing is involved and/or where a data cube requires partitioning because the entire data cube will not fit concurrently into memory for processing.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates a computing environment for use with the efficient multidimensional data aggregation operator implementation in block diagram form;

FIG. 2 illustrates a results set in standard and data cube form;

FIG. 3 illustrates an overview of the efficient implementation processing steps in flow diagram form;

FIG. 4 illustrates details of the aggregate generating steps in flow diagram form;

FIG. 5 illustrates details of the remaining aggregate cleanup steps in flow diagram form; and

FIG. 6 illustrates details of the super-aggregate generating steps in flow diagram form.

DETAILED DESCRIPTION

Computing Environment--FIG. 1

FIG. 1 illustrates a block diagram example of a computer system 100 for use with the efficient multidimensional data aggregation operator implementation. The efficient operator implementation of the present invention is operable in any database system supporting a multidimensional data aggregation operator on any of several standard computing systems readily available in the industry such as computer system 100. The efficient implementation and the host database are executable on processor 102. Processor 102 stores and/or retrieves programmed instructions and/or data from memory devices that include, but are not limited to, Random Access Memory (RAM) 110 and Read Only Memory (ROM) 108 by way of memory bus 152. Another accessible memory device includes non-volatile memory device 112 by way of local bus 150. User input to computer system 100 is entered by way of keyboard 104 and/or pointing device 106. Human readable output from computer system 100 is viewed on display 114 or in printed form on local printer 115. Alternatively, computer system 100 is accessible by remote users for debugging, input, and/or generating human readable displays in printed and/or display screen output form or any other output form by way of Local Area Network (LAN) 116.

Data Cube Background--FIG. 2

FIG. 2 illustrates a simple example of an aggregate results set 210 from a database 200. FIG. 2 also illustrates the aggregate results set 210 in the form of a full data cube 260. It is useful to compare the aggregate results set 210 to the data cube 260 to illustrate the difference in the amount of aggregate data and to appreciate the magnitude of additional processing required to generate the complete set of aggregates in data cube 260.

The following discussion and illustration is based on an automobile sales database example that contains the model, year, and color for every car sold. A user wishing to view the sales totals for specific models of cars by year and by color might construct a query such as the following:

SELECT Model, Year, Color, SUM(sales) AS Sales

FROM Sales

WHERE Model in (`Ford`, `Chevy`)

AND Year BETWEEN 1990 AND 1992

GROUP BY Model, Year, Color;

Executing the above query generates a results set similar to results set 210 that contains a column 211-213 corresponding to each of the Model, Year, and Color attributes of the SELECT statement, in addition to an aggregate Sales column 214 containing a corresponding sales total by Color and by Year and by Model. However, the results set 210 displays only a few of the available aggregate relationships that a CUBE operator can extract.

A data cube 260 can be generated from the core of the results set 210. Generating data cube 260 requires the set of all subsets of the Sales aggregation column 214. The set of all subsets is also known as the power set. Because the CUBE operator is itself an aggregation operation, a GROUP BY clause in a SELECT statement can be overloaded in a manner such as the CUBE query syntax below:

SELECT Mode, Year, Color, SUM(sales) AS Sales

FROM Sales

WHERE Model in (`Ford`, `Chevy`)

AND Year BETWEEN 1990 AND 1992

GROUP BY CUBE Model, Year, Color;

Executing the above query generates a results set similar to data cube 260 that contains a column 261-263 corresponding to each of the Model, Year, and Color attributes of the SELECT statement. In addition, the CUBE operator aggregates over all possible combinations of attributes of the GROUP BY clause to generate a Sales column 264 containing the corresponding sales total of each Model by Year and by Color similar to the aggregate Sales column 214 of results set 210. The CUBE operator then sums each aggregate while substituting the ALL value in the appropriate aggregation columns. Thus, if there are n attributes in the GROUP BY clause, there will be 2.sup.n -1 super-aggregate values generated. Further, if the cardinality of the n attributes are C.sub.1, C.sub.2, . . . , C.sub.n then the cardinality of the resulting data cube relation is (C.sub.1 +1). The extra value in each domain is the ALL value. For example, the results set 210 contains 2.times.3.times.3=18 rows and the data cube 260 derived from applying the CUBE operator to the results set 210 generates 3.times.4.times.4=48 rows.

Note for example that data cube 260 contains totals in the Sales column 264 for blue, red, and white 1990 Chevy's in rows 270-272. In addition, there is a grand total row 273, for example, for all colors of 1990 Chevy's. Other aggregate relationships in data cube include, but are not limited to, super-aggregate totals for all years of a given Model and Color as in rows 274-276, and a super-superaggregate total row 277 for ALL Models in ALL Years in ALL Colors. Because even in this simple illustration the size of data cube 260 is more than twice the size of the original results set 210, it is important that the CUBE operator be implemented in an efficient manner to maximize processing time and processing resources by minimizing the number and type of function calls that are required to generate then data cube aggregates.

Data Cube Generating Overview--FIG. 3

FIG. 3 illustrates an overview of the efficient implementation data cube generating steps 300 in flow diagram form. The method begins at step 308 and proceeds to generating a query for a target database at step 315 and executing the query at step 321 to extract a results set from the database. If it is determined at decision step 330 that the CUBE operator or its equivalent was specified in the executed query of step 321, then the CUBE operator is applied in steps 338 and 342. Alternatively, if it is determined at decision step 330 that the CUBE operator was not specified in the executed query of step 321, then processing continues at step 350 without applying the CUBE operator.

The two steps 338 and 342 that apply the CUBE operator to the results set from step 321 are central to the efficient multidimensional data aggregation operator implementation of the present invention. At step 338, the basic cumulative aggregates of the results set are generated as a union of a minimum number of roll-up's. Details of the roll-up operational steps are disclosed in the text accompanying FIGS. 4 and 5. At step 342, the super-aggregates are efficiently generated by classifying the type of aggregate function being applied and facilitating an efficient implementation of that aggregate function. Details of the super-aggregate generating steps are disclosed in the text accompanying FIG. 6.

Whether or not the CUBE operator is applied, processing continues at step 350 where the results set is displayed and/or stored as specified by the end user. If it is determined at decision step 356 that additional queries will be processed, then processing continues at step 315 as previously disclosed. If it is determined at decision step 356 that no additional queries will be processed, then processing stops at step 360.

Efficiently Generating Data Cube--FIGS. 4-6

FIG. 4 illustrates the primary roll-up operational steps 400 that form the first phase of efficiently generating a data cube. The roll-up operational steps 400 are the details of step 338 in FIG. 3.

The roll-up operational steps 400 begin at step 408 and proceed to step 412 where variables x and n are set to the number of dimensions of the data cube. The number of dimensions of a data cube equals the number of attributes in the SELECT statement. At step 418 the scoreboard is initialized. The scoreboard is an array of 2.sup.n bits where n is the number of attributes of the select statement that are being rolled up. In a preferred embodiment the scoreboard is initially set to all zeros.

At step 425, the roll-up process is initialized by setting a roll-up string to the original n attributes. The ROLL-UP operator is used because it is an aggregate operator that delivers cumulative aggregates for attributes within a GROUP BY clause. A roll-up is the process of aggregating successive subsets of a string to generate an aggregate of each subset. The successive subsets are typically aggregated individually from right to left, and each subset contains one less rightmost attribute than the previous subset. At step 431, the first x attributes in the roll-up string are aggregated. At step 438, the scoreboard is updated by setting a bit in the array that corresponds to the roll-up string.

If at decision step 445 it is determined that x is not less than or equal to 0, then processing continues at step 448 where x is decremented by 1 and the roll-up and scoreboard steps 431 and 438 repeat as previously disclosed. Alternatively, if at decision step 445 it is determined that x is equal to or less than 0, then processing continues at step 453.

At step 453, scratch variable x is reset to equal one less than the original number of n attributes in preparation for a barrel shifted roll-up of additional roll-up strings. At step 458, the roll-up string is set to a barrel shifted roll-up string minus the rightmost attribute. In a preferred embodiment, barrel shifting is the process of left shift rotating the original n attributes by one attribute position so that the previous leftmost attribute is now in a hidden rightmost attribute position. The barrel shift method will identify an additional (n-1)2 roll-ups.

If at decision step 465, it is determined that the present roll-up string attribute order is not equal to the original order of n attributes, then processing continues at step 470. At step 470, the first x attributes of the present roll-up string are aggregated, and the corresponding bit in the scoreboard is set at step 473. At step 478, the scratch variable x is decremented by 1. If at decision step 480, it is determined that x is greater than 0, then processing continues at step 470 as previously disclosed to complete the roll-up on the present roll-up string. Alternatively, if at decision step 480 it is determined that x is equal to or less than 0, then processing continues at step 453 as previously disclosed to set up processing for a roll-up on the next barrel shifted roll-up string.

If at decision step 465, it is determined that the present roll-up string order is equal to the order of the original n attributes, then processing continues at decision step 485. If at decision step 485, it is determined that all 2.sup.n bits are not set in the scoreboard array, then processing continues to step 490 where the remaining unaggregated strings are identified and rolled up. Step 490 has particular significance where n>3 because the ordinary roll-up operational steps 400 will not aggregate all available subset strings from the original n attributes. Details of step 490 are disclosed in the text accompanying FIG. 5. At the completion of step 490, processing continues at step 495. Alternatively, if at decision step 485 it is determined that all 2.sup.n bits of the scoreboard are set, then processing continues to step 495.

Because the typical number of attributes are about or less than 5, an illustration of the roll-up operational steps 400 is useful for five attributes, namely attributes A, B, C, D, and E. Proceeding with this example beginning at step 412, n, and the scratch variable x, are set to equal 5 which is the number of dimensions of a data cube based on the five attributes in the SELECT statement. At step 418, a scoreboard array of 2.sup.5 bits, that is 32 bits, are set to 0. At step 425, the roll-up string is set to equal the original n attributes of A B C D E.

The first roll-up begins at step 431 on the original n roll-up string A B C D E as set forth in Table 1 below.

                  TABLE 1
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    ABCDE        00000      0
    ABCD         00001      1
    ABC          00011      3
    AB           00111      7
    A            01111      15
                 11111      31
    ______________________________________

                  TABLE 2
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    BCDE         10000      16
    BCD          10001      17
    BC           10011      19
    B            10111      23
    ______________________________________

                  TABLE 3
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    CDEA         01000       8
    CDE          11000      24
    CD           11001      25
    C            11011      27
    ______________________________________

                  TABLE 4
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    DEAB         00100       4
    DEA          00110      12
    DE           11100      28
    D            11101      29
    ______________________________________

                  TABLE 5
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    EABC         00010       2
    EAB          00110       6
    EA           01110      14
    E            11110      30
    ______________________________________

                  TABLE 6
    ______________________________________
    Binary Representation
                      Bit Position
                                Value
    ______________________________________
    00000              0        1
    00001              1        1
    00010              2        1
    00011              3        1
    00100              4        1
    00101              5        0
    00110              6        1
    00111              7        1
    01000              8        1
    01001              9        0
    01010             10        0
    01011             11        0
    01100             12        1
    01101             13        0
    01110             14        1
    01111             15        1
    10000             16        1
    10001             17        1
    10010             18        0
    10011             19        1
    10100             20        0
    10101             21        0
    10110             22        0
    10111             23        1
    11000             24        1
    11001             25        1
    11010             26        0
    11011             27        1
    11100             28        1
    11101             29        1
    11110             30        1
    11111             31        1
    ______________________________________

                  TABLE 7
    ______________________________________
    Bit           Binary
    Position      Representation
                             Attributes
    ______________________________________
    5             00101      A,B,D
    ______________________________________

                  TABLE 8
    ______________________________________
    Permutation  Roll-ups
    ______________________________________
    ABD          1
    ADB          2
                 (maximum possible)
    ______________________________________

                  TABLE 9
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    ADB          00101       5
    AD           01101      13
    ______________________________________

                  TABLE 10
    ______________________________________
    Bit           Binary
    Position      Representation
                             Attributes
    ______________________________________
    9             01001      A,C,D
    ______________________________________

                  TABLE 11
    ______________________________________
    Permutation  Roll-ups
    ______________________________________
    ACD          2
                 (maximum possible)
    ______________________________________


              TABLE 12
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    ACD          01001       9
    AC           01011      11
    ______________________________________

                  TABLE 13
    ______________________________________
    Bit           Binary
    Position      Representation
                             Attributes
    ______________________________________
    10            01010      A,C,E
    ______________________________________

                  TABLE 14
    ______________________________________
    Permutation  Roll-ups
    ______________________________________
    ACE          1
    AEC          1
    CAE          1
    CEA          2
                 (maximum possible)
    ______________________________________

                  TABLE 15
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    CEA          01010      10
    CE           11010      26
    ______________________________________

                  TABLE 16
    ______________________________________
    Bit           Binary
    Position      Representation
                             Attributes
    ______________________________________
    18            10010      B,C,E
    ______________________________________

                  TABLE 17
    ______________________________________
    Permutation  Roll-ups
    ______________________________________
    BCE          1
    BEC          2
                 (maximum possible)
    ______________________________________

                  TABLE 18
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    BEC          10010      18
    BE           10110      22
    ______________________________________

                  TABLE 19
    ______________________________________
    Bit           Binary
    Position      Representation
                             Attributes
    ______________________________________
    20            10100      B,D,E
    ______________________________________

                  TABLE 20
    ______________________________________
    Permutation  Roll-ups
    ______________________________________
    BDE          2
                 (maximum possible)
    ______________________________________

                  TABLE 21
    ______________________________________
    Roll-up      Binary     Scoreboard
    String       Representation
                            Bit Position
    ______________________________________
    BDE          10100      20
    BD           10101      21
    ______________________________________

                  TABLE 22
    ______________________________________
    Data Cube on N Dimensions
    N Dimensions   Optimal Present Invention
    ______________________________________
    1               1       1
    2               2       2
    3               3       3
    4               6       6
    5              10      10
    6              20      20
    7              35      37
    8              70      71
    9              126     129
    10             252     252
    11             462     478
    12             924     926
    13             1716    1784
    ______________________________________

• Inventors
  Gray, Jim; Reichart, Donald C.;
• Assignee
  Microsoft Corporation (Redmond, WA)
• Published
  Oct-13-1998
• Current US Classes:
  701/2
  701/4
  701/5
  707/3
  715/526
• Application #
  768105
• International Classes
  G06F 017/30
• Field of Search
  707/526 707/4 707/2 707/523 707/101 707/8 707/1 707/104 707/103 707/3 707/5 707/100 1/1
• Examiner
  Black; Thomas G.
• Agent
  Duft, Graziano & Forest, PC
• US Patent References:
  5359724
  5412804
  5511190
  5598559
  5713020