Systems and methods of generating data marks in data visualizations
11550803 · 2023-01-10
Assignee
Inventors
Cpc classification
G06F16/283
PHYSICS
G06F3/04842
PHYSICS
Y10S707/99944
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
Y10S707/99942
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
Y10S707/956
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
Y10S707/99945
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
Y10S707/959
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
G06F16/282
PHYSICS
G06F3/04847
PHYSICS
G06F16/252
PHYSICS
Y10S707/954
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
Y10S707/99943
GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
International classification
G06F16/00
PHYSICS
G06F16/25
PHYSICS
G06F16/28
PHYSICS
G06F3/04842
PHYSICS
Abstract
An example method of displaying a data visualization includes displaying a plurality of selectable fields and receiving user selections of two different fields from the plurality of selectable fields. The method also includes generating, in accordance with the received user selections, data marks to be displayed in a data visualization, each data mark corresponding to a respective retrieved tuple of data from a multidimensional database, where (i) each data mark has an x-position defined according to data for a first field in the respective tuple and (ii) each data mark has a y-position defined according to data for a second field in the respective tuple. The method also includes displaying the data visualization that includes the generated data marks.
Claims
1. A method, comprising: at a computer having a display, one or more processors, and memory storing one or more programs configured for execution by the one or more processors: displaying, in a graphical user interface, a plurality of selectable fields from a multidimensional database that includes at least one data hierarchy, wherein (i) one or more first fields of the plurality of selectable fields are categorical fields, and (ii) one or more second fields of the plurality of selectable fields are quantitative fields; and receiving a first user selection of a respective first field from the one or more first fields; receiving a second user selection, distinct from the first user selection, of a respective second field from the one or more second fields; after receiving the first and second user selections: generating, in accordance with the received user selections, a plurality of data marks to be displayed in a data visualization, each data mark corresponding to a respective retrieved tuple of data from the multidimensional database and each retrieved tuple including the respective first field and the respective second field, wherein: (i) each data mark has an x-position defined according to data for the respective first field in the respective tuple, and (ii) each data mark has a y-position defined according to data for the respective second field in the respective tuple; and displaying, in the graphical user interface, the data visualization, wherein the data visualization includes the plurality of data marks.
2. The method of claim 1, further comprising: displaying a first label for the respective first field in a first region of the graphical user interface, after receiving the first user selection; and displaying a second label, different from the first label, for the respective second field in the first region of the graphical user interface, after receiving the second user selection.
3. The method of claim 2, wherein the data visualization is displayed in a second region, different from the first region, of the graphical user interface.
4. The method of claim 3, wherein the first and second regions are adjacent to each other in the graphical user interface.
5. The method of claim 1, wherein: the respective first field is a first level of the at least one data hierarchy; and the method further comprises: receiving a user action to drill into a second level of the at least one data hierarchy, the second level being associated with a respective third field of the one or more first fields; and in response to receiving the user action, updating display of the data visualization in accordance with the received user action.
6. The method of claim 5, wherein the user action to drill is (i) a drill down operation or (ii) a drill up operation.
7. The method of claim 1, further comprising, before generating the plurality of data marks to be displayed in the data visualization: receiving a third user selection, distinct from the first and second user selections, of a respective third field from the one or more first fields; wherein each data mark is further defined according to data for the respective third field in the respective tuple.
8. The method of claim 7, wherein each data mark has a z-position defined according to data for the respective third field in the respective tuple.
9. The method of claim 7, wherein each data mark has a shape, size, or color defined according to data for the respective third field in the respective tuple.
10. The method of claim 7, wherein each data mark is broken down and colored according to the data for the respective third field in the respective tuple.
11. The method of claim 7, wherein each data mark has a label, displayed as part of the data visualization, defined according to data for the respective third field in the respective tuple.
12. The method of claim 1, wherein receiving the first and second user selections comprises detecting two distinct drag-and-drop operations.
13. A computer system for generating data visualizations, comprising: a display; one or more processors; memory; and one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs comprising instructions for: displaying, in a graphical user interface, a plurality of selectable fields from a multidimensional database that includes at least one data hierarchy, wherein (i) one or more first fields of the plurality of selectable fields are categorical fields, and (ii) one or more second fields of the plurality of selectable fields are quantitative fields; and receiving a first user selection of a respective first field from the one or more first fields; receiving a second user selection, distinct from the first user selection, of a respective second field from the one or more second fields; after receiving the first and second user selections: generating, in accordance with the received user selections, a plurality of data marks to be displayed in a data visualization, each data mark corresponding to a respective retrieved tuple of data from the multidimensional database and each retrieved tuple including the respective first field and the respective second field, wherein: (i) each data mark has an x-position defined according to data for the respective first field in the respective tuple, and (ii) each data mark has a y-position defined according to data for the respective second field in the respective tuple; and displaying, in the graphical user interface, the data visualization, wherein the data visualization includes the plurality of data marks.
14. The computer system of claim 13, wherein the one or more programs further comprise instructions for: displaying a first label for the respective first field in a first region of the graphical user interface, after receiving the first user selection; and displaying a second label, different from the first label, for the respective second field in the first region of the graphical user interface, after receiving the second user selection.
15. The computer system of claim 14, wherein the data visualization is displayed in a second region, different from the first region, of the graphical user interface.
16. The computer system of claim 15, wherein the first and second regions are adjacent to each other in the graphical user interface.
17. The computer system of claim 13, wherein: the respective first field is a first level of the at least one data hierarchy; and the one or more programs further comprise instructions for: receiving a user action to drill into a second level of the at least one data hierarchy, the second level being associated with a respective third field of the one or more first fields; and in response to receiving the user action, updating display of the data visualization in the second region in accordance with the received user action.
18. The computer system of claim 17, wherein the user action to drill is (i) a drill down operation or (ii) a drill up operation.
19. The computer system of claim 13, wherein the one or more programs further comprise instructions for, before generating the plurality of data marks to be displayed in the data visualization: receiving a third user selection, distinct from the first and second user selections, of a respective third field from the one or more first fields; wherein each data mark is further defined according to data for the respective third field in the respective tuple.
20. A non-transitory computer-readable storage medium storing one or more programs configured for execution by a computer system having a display, one or more processors, and memory, the one or more programs comprising instructions for: displaying, in a graphical user interface, a plurality of selectable fields from a multidimensional database that includes at least one data hierarchy, wherein (i) one or more first fields of the plurality of selectable fields are categorical fields, and (ii) one or more second fields of the plurality of selectable fields are quantitative fields; and receiving a first user selection of a respective first field from the one or more first fields; receiving a second user selection, distinct from the first user selection, of a respective second field from the one or more second fields; after receiving the first and second user selections: generating, in accordance with the received user selections, a plurality of data marks to be displayed in a data visualization, each data mark corresponding to a respective retrieved tuple of data from the multidimensional database and each retrieved tuple including the respective first field and the respective second field, wherein: (i) each data mark has an x-position defined according to data for the respective first field in the respective tuple, and (ii) each data mark has a y-position defined according to data for the respective second field in the respective tuple; and displaying, in the graphical user interface, the data visualization, wherein the data visualization includes the plurality of data marks.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
DETAILED DESCRIPTION OF THE INVENTION
(22) The present invention provides a method for exploiting the hierarchical information present in databases in order to facilitate exploration of such databases. The present invention uses a novel formalism to accomplish this task. A user is allowed to enter a search query that is consistent with the novel formalism of the present invention. When such a search query is constructed, the systems and methods of the present invention take advantage of the formalism and the hierarchical information associated with the target database to service the query using fewer existence scans and other time consuming database functions than are found in known data exploration programs and techniques. Additional features and advantages of the present invention are disclosed in the following sections.
1.5 Overview of an Exemplary System
(23)
(24) System 500 preferably comprises a computer 502 that includes: a central processing unit 522; a main non-volatile storage unit 534, preferably including one or more hard disk drives, for storing software and data, the storage unit 534 typically controlled by disk controller 532; a system memory 538, preferably high speed random-access memory (RAM), for storing system control programs, data, and programs, including programs and data loaded from non-volatile storage unit 534; system memory 538 may also include read-only memory (ROM); a user interface 524, including one or more input devices, such as a mouse 526, a keypad 530, and a display 528; an optional network interface card 536 for connecting to any wired or wireless communication network; and an internal bus 533 for interconnecting the aforementioned elements of the system.
(25) Operation of computer 502 is controlled primarily by operating system 540, which is executed by central processing unit 522. Operating system 540 can be stored in system memory 538. In addition to operating system 540, a typical 5 implementation of system memory 538 includes: file system 542 for controlling access to the various files and data structures used by the present invention; database hierarchy module 544 for interpreting the hierarchy of a database 558 (e.g., by interpreting the database schema); user interface module 546 for obtaining a visual specification (specification) from the user (for constructing a visual table, comprised of one or more panes, by obtaining from a user a specification that is in a language based on the hierarchical structure of database 558); data interpreter module 552 for formulating database queries based on the specification (for querying database 558 to retrieve a set of tuples in accordance with the specification); and visual interpreter module 556 for processing database query results and displaying these results in accordance with the specification (for associating a subset of the set of tuples with a pane in the one or more panes).
(26) In a preferred embodiment, user interface module 546 includes: a database hierarchy 548 that corresponds to the hierarchy of a database 558; and a visual specification 550 that specifies a formalism that can be used to determine the exact analysis, query, and drawing operations to be performed by the system.
(27) In a preferred embodiment, data interpreter module 552 includes: one or more query descriptions 554 that are used to query databases; a query cache 555 that is used to store database query results; and a pane-data-cache 557 that is used to store a separate data structure for each pane 722 (
(28) System 500 includes one or more databases 558. In one embodiment, a database 558 is OLAP data that can be viewed conceptually as a multidimensional data cube. See, for example, Section 5.3. More generally, database 558 is any form of data storage system, including but not limited to a flat file, a relational database (SQL), and an OLAP database (MDX and/or variants thereof). In some specific embodiments, database 558 is-a hierarchical OLAP cube. In some specific embodiments, database 558 comprises star schema that is not stored as a cube but has dimension tables that define hierarchy. Still further, in some embodiments, database 558 has hierarchy that is not explicitly broken out in the underlying database or database schema (e.g., dimension tables are not hierarchically arranged). In such embodiments, the hierarchical information for the respective database 558 can be derived. For example, in some instances, database hierarchy module 544 reads database 558 and creates a hierarchy representing data stored in the database. In some embodiments, this external program is run with user input. In some embodiments, there is only a single database 558.
(29) In typical embodiments, one or more of databases 558 are not hosted by computer 502. Rather, in typical embodiments, databases 558 are accessed by computer 502 using network interface 536. In some embodiments, an attribute file 580 is associated with each database 558. Attributes are discussed in Section 5.3.6, below.
(30) It will be appreciated that many of the modules illustrated in
(31) Now that an overview of a system 500 in accordance with one embodiment of the present invention has been described, various advantageous methods in accordance with the present invention will now be disclosed in the following sections.
1.6 Exemplary Method
(32) Referring to
(33) Step 602. In step 602, the hierarchy for each selected database 558 is characterized. In embodiments in which selected databases 558 have a schema 560 that includes such hierarchical information; the schema 560 can be read directly by database hierarchy module 544 and the database hierarchy 562 in this schema 560 can be characterized. Section 5.3 discusses illustrative types of database hierarchy 562 and database organization. In some embodiments, a plurality of databases 558 is analyzed concurrently. In such embodiments, database schema 560 of each of the plurality of databases 558 is read directly by database module 544 and characterized. In some embodiments, selected databases 558 do not have a hierarchy that is explicitly defined in the underlying respective databases 558. In such embodiments, database hierarchy module 544 analyzes each selected database 558 and constructs database hierarchical information for each of the respective databases. In some instances, this analysis is assisted by input from a user and/or requires an analysis of the data stored in the database.
(34) In some embodiments, the hierarchical structure of a database 558 is derived from a database schema for the database 558. This database schema comprises schema fields. In some embodiments each schema field has a type (e.g., a base type or an array type). Representative base types include, but are not limited to, character strings, integer, short integer, double integer, single precision floating number, double precision floating point number, and object handle. Representative array types include, but are not limited to an array of long integers, an array of short integers, an array of single precision floating point numbers, an array of double precision floating point numbers and an array of object handles.
(35) Step 604. In step 604, a visual specification (specification) 550 is obtained from the user by user interface module 546. In a preferred embodiment, visual specification 550 is created using a drag-and-drop interface provided by user interface module 546. An exemplary user interface module 546 is illustrated in
(36) Schema box 702 of
(37) A user can drop any dimension level into the interface of shelves 708. However, the dimensions 704 cannot be dragged into the shelves. Shelves 708-4 and 708-5 are the axis shelves. The operands placed on shelves 708-4 and 708-5 (e.g., year, quarter, month, producttype, product, market, state) determine the structure of visual table 720 and the types of graphs that are placed in each pane 722 of visual table 720. For example, in
(38) The configuration of operands on shelves 708 (
x:C*(A+B)
y:D+E
z:F
and the level of detail within each pane 722 is set to:
(39) level of detail: G
(40) In some embodiments, a user can specify any of the algebra (e.g., ordinal concatenation, etc.) described in Section 5.4. In some embodiments, a user types in the algebra directly using a user interface such as the one illustrated in
(41) In some embodiments, each shelf 708 that represents an axis of visual table 720 is translated into corresponding expressions in an automated manner. For example the contents of the shelf 708 that represents the x-axis is translated into an expression that represents the x-axis of visual table 720, the shelf 708 that represents the y-axis is translated into an expression that represents the y-axis of visual table 720, and the shelf 708 that represents layers is translated into an expression that represents the z-axis of visual table 720. The contents of each axis shelf 708 is an ordered list of database field names. In some embodiments, the order of the database field names is constrained such that all nominal and ordinal fields precede all quantitative fields in the shelf Exemplary nominal fields include, but are not limited to products, regions, account numbers or people. Exemplary ordinal fields include, but are not limited to, dates or priority rankings. Exemplary quantitative fields include, but are not limited to, profit, sales, account balances, speed or frequency. In embodiments where the order of the database field names is constrained such that all nominal and ordinal fields precede all quantitative fields in the shelf 708, the nominal fields are assigned an ordering and treated as ordinal. This ordering is either a natural ordering (e.g., alphabetic, numeric) or an ordering specified by the user. Then, the list of fields in a respective shelf are transformed into an expression of the form
(O.sub.1×O.sub.2 . . . ×O.sub.n)×(Q.sub.1×Q.sub.2 . . . ×Q.sub.m)
In addition, if any two adjacent categorical fields represent levels of the same dimension then the cross “×” operator (see Section 5.4.22) between them is replaced with a dot “.Math.” operator (see Section 5.4.2.4). The specification is used to map data values from a database 558 to visual properties by visual interpreter module 556. Further shelves labeled “Group4 in panes by” (not shown) and “Sort in panes by” (708-3,
(42) In some embodiments, the specification is written in a language that is based on the metadata (e.g., hierarchical structure) of the one or more databases 558 that were characterized in step 602. At a minimum, this language comprises all or a portion of the dimension levels that make up the hierarchies of the one or more databases 558. Examples of dimension levels (e.g., year, quarter, month, etc.) have been described. Typically, these dimensional levels are displayed on user interface 524 as illustrated in
(43) In a preferred aspect of the present invention, visual specification 550 organizes panes 722 into a plurality of rows and a plurality of columns. In embodiments in accordance with this aspect of the invention, visual specification 550 includes a first algebraic expression for the plurality of rows and a second algebraic expression for the plurality of columns. Both the first algebraic expression and the second algebraic expression each represent an operation on the metadata of a database 558 (e.g., hierarchical structure) that was characterized in step 602. In some instances in accordance with this aspect of the invention, the specification further organizes one or more panes 722 into a plurality of layers. To accomplish this, the specification 550 further comprises a third algebraic expression for the plurality of layers. The third algebraic expression represents an operation on the metadata of one or more of the databases 558 that were characterized in step 602. For example, the first two algebraic expressions could cover revenue for all products whereas the third algebraic expression could add the dimension “State” such that each layer represents the revenue by product for each state.
(44) Using the methods of the present invention, each visual specification 550 can be interpreted to determine the exact analysis, query, and drawing operations to be performed by system 500. In a preferred embodiment, drawing operations are performed independently in each pane 722 of visual table 720.
(45) Visual table 720 includes three axes. The x and y axes are respectively determined by shelves 708-5 and 708-4, as discussed above. The z axis is determined by shelf 708-1 (
(46) Step 606. In step 606, a set of efficient queries is formed by data interpreter module 552 based on specification 550. Before generating database specific queries, data interpreter module 552 generates a set of one or more abstract query descriptions 554 that describe the required queries using the values specified in visual specification 550 (e.g., values placed on shelves 708-1; 708-4, and 708-5). Query descriptions 554 precisely describe the desired filtering, sorting, and grouping of tuples from database 558.
(47) The number of distinct query descriptions 554 that are generated for a single visual specification 550 is determined by the level of detail specified in visual specification 550. For example, visual table 720 (
(48) Although it is possible for each pane 722 to correspond to a different level of detail, and thus a different query, the common situation is for a larger number of panes 722 (
(49) To illustrate the sum-of-terms reduction of each axis, consider exemplary visual specification 550 in
x:C*(A+B)
y:D+E
z:F
and the level of detail within each pane 722 is set to G. Crossing these expressions, in accordance with the table algebra specified in Section 5A, below, and then reducing to a sum-of-terms form yields:
(A*C*D*F*G)+(A*C*E*F*G)+(B*C*D*F*G)+(B*C*E*F*G)
Thus, in this example, the following four database queries are made:
(A*C*D*F*G) Query 1
(A*C*E*F*G) Query 2
(B*C*D*F*G) Query 3
(B*C*E*F*G) Query 4
(50) Most typical multidimensional query languages provide a mechanism for generating queries of the form found in queries 1-4. For example, each of queries 1-4 can be a single multidimensional expressions (MDX) query. MDX (Microsoft, Redmond Wash.), is a syntax that supports the definition and manipulation of multidimensional objects and data. MDX is similar to the structured query language (SQL) syntax, but is not an extension of the SQL language. As with an SQL query, each MDX query requires a data request (SELECT clause), a starting point (FROM clause), and a filter (WHERE clause). These and other keywords provide the tools used to extract specific portions of data from a hierarchical database (e.g., a cube) for analysis. In summary, each query can map to a relational algebra operator such as an SQP query or to a datacube query (e.g., an MDX query).
(51) Now that an overview of how visual specification 550 is reduced to an efficient set of queries has been presented, a detailed algorithm used in one embodiment of the present invention will be described. The algorithm is set forth in the following pseudo code:
(52) 101: x-terms=List of terms from the sum-of-terms form of the x-axis expression
(53) 102: y-terms=List of terms from the sum-of-terms form of the y-axis expression
(54) 103: z-terms=List of terms from the sum-of-terms form of the z-axis expression
(55) 104: for each layer {
(56) 105: for each x-term in x-terms {
(57) 106: for each y-term in y-terms {
(58) 107: for each z-term in z-terms {
(59) 108: p-lookup PaneLookupDescriptor(x-term, y-term, z-term)
(60) 109: p-spec=The PaneSpecification that applies to p-lookup
(61) 110: qd=new QueryDescription
(62) 111: Add to qd all fields in x-term
(63) 112: Add to qd all fields in y-term
(64) 113: Add to qd all fields in x-term
(65) 114: Add to qd all level of detail fields in p-spec
(66) 115: Add to qd all drawing order fields in p-spec
(67) 116: Add to qd all encoding fields in p-spec
(68) 117: Add to qd all selection (brushing tooltips) fields in p-spec
(69) 118: Add to qd all filters in the visual specification involving the fields in qd
(70) 119: if (qd matches data in data-cache)
(71) 120: results=retrieve data from data-cache
(72) 121: else
(73) 122: results=retrieve data from database server
(74) 123: add results to data-cache indexed by qd
(75) 124: group-tic=create GroupingTransform
(76) 125: run group-tsf
(77) 126: Add each output data structure from group-tsf to pane-data-cache }}}}
(78) Lines 101 through 103 of the pseudo code represent the case in which each axis of visual specification 550 is reduced to the sum-of-terms. Then, lines 104 through 107 are used to individually consider each of the terms i. Individually, each term i describes either a set of rows, a set of columns, or a set of layers in visual table 720. Together, the terms define a set of panes 722 that appears as “for each x-term, y-term, z-term combination”.
(79) Lines 108 and 109 are used to find the pane specification, which defines the marks, encodings, etc., for the panes 722 defined by a particular x-term, y-term, z-term combination. This is done by testing p-lookup against the selection criteria predicate in each pane specification in the visual specification.
(80) Lines 110 through 118 build a query for the particular x-term, y-term, z-term combination. Line 110 creates the variable “qd” to hold the query and lines 111 through 113 add all the fields in the x-term, the y-term, and the z-term in the particular x-term, y-term, z-term combination. Lines 114 through 118 add additional terms from visual specification 550, such as level of detail, to the query.
(81) Next, in lines 119 through 122, a determination is made as to whether a query of the form built by lines 110 through 118 already exists in the data-cache (query cache 555,
(82) The data retrieved in the processing steps above can contain data for a set of panes 722. When this is the case, the data is partitioned into a separate data structure for each pane 722 using a grouping transform (lines 124-125) that is conceptually the same as a “GROUP BY” in SQL except separate data structures are created for each group rather than performing aggregation. In line 126, each output data structure from group-tsf is added to pane-data-cache 557 (
(83) Step 608. In step 608, the queries developed in step 608 are used to query one or more databases 558. Such databases 558 can be stored in memory 548. However, in a more preferred embodiment, these databases 558 are stored in a remote server.
(84) Step 610. In step 610, visual interpreter module 556 processes queries that have been generated by data interpreter module 552. A number of steps are performed in order to process these queries. An overview of these steps is illustrated in
(85) Step 612—reduction of the visual specification to the normalized set form. In step 604, visual specification 550 was obtained by user interface module 546. The visual specification 550 comprises the values of shelves 708 that have been populated by the user. In step 612, visual specification 550 is used to construct algebraic expressions that define how visual table 720 is partitioned into rows, columns, and layers, and additionally defines the spatial encodings within each pane 722 of visual table 720. In this way, visual specification 550 organizes one or more panes 722 into a plurality of rows and a plurality of columns. In some embodiments, the plurality of rows and plurality of columns is hierarchically organized. Further, in some embodiments specification 550 also organizes the one or more panes 722 into a plurality of layers that are optionally hierarchically organized. Further still, in some embodiments, the specification organizes the one or more panes 722 into separate pages that are, optionally, hierarchically organized.
(86) A complete algebraic expression of visual table 720 is termed a “table configuration.” In other words, in step 612, the three separate expressions of visual specification 550 that respectively define the x, y, and z axes of visual table 720 are normalized to set form (set interpreted) in order to partition the row, columns and layers of visual table 720. To produce the normalized set form, each operand in the three separate expressions is evaluated to set form. The operators in each expression define how to evaluate each set within an expression. Thus, normalization to set form results in a single set (the normalized set form), where each element in the normalized set form corresponds to a single row, column, or layer of visual table 720. In some embodiments, this normalization process is extended to yet another dimension, termed “pages”.
(87) Recall that each expression in the three separate expressions of visual specification 550 that define the x, y, and z axis are drawn from operands (e.g., fields) in the database schema. The algebra used to produce the normalized set form characterizes each of the operands in a database schema (or some other representation of database structure) into two types: dimension levels and measure. Whether an operand is a dimensional level or a measure depends on the type of the operand. The set interpretation of an operand consists of the members of the order domain of the operand. The set interpretation of the measure operand is a single-element set containing the operand name. For example, the set interpretation of the “Profit” operand is {Profit}.
(88) The assignment of sets to the different types of operands reflects the difference in how the two types of operands are encoded into the structure of visual table 720. Dimensional level operands partition the table into rows and columns, whereas measure operands are spatially encoded as axes within table panes. Examples of the set interpretations and resulting table structures for representative expressions are illustrated in
(89) A valid expression in the algebra used in the present invention is an ordered sequence of one or more operands with operators between each pair of adjacent operands. The operators in this algebra, in order of precedence are cross (x), nest (/), and concatenation (+). Parentheses can be used to alter the precedence. Because each operand is interpreted as an ordered set, the precise semantics of each operator is defined in terms of how they combine two sets (one each from the left and right operands) into a single set, as illustrated in
(90) Thus, every expression in visual specification 550 can be reduced to a single set, with each entry in the set being an ordered concatenation of zero or more dimension level values followed by zero or more measure operand names. For example, the normalized set form of the expression “Month×profit” is {(January, Profit), (February, Profit), . . . , (December, Profit)}. The normalized set form of an expression determines one axis of visual table 720. The table axis is partitioned into columns (or rows or layers) so that there is a one-to-one correspondence between columns and entries in the normalized set.
(91) Now that an overview of step 612 has been described, an example will be given. Consider the exemplary visual specification 550 of
x:C*(A+B)
y:D+E
z:F
(92) Computation of the normalized set form of this visual specification, in accordance with step 612 provides:
x:{(c.sub.1,a.sub.1) . . . (c.sub.k,b.sub.j)}
y:{(d.sub.1), . . . ,(d.sub.1),(e.sub.1), . . . ,(e.sub.m)}
z:{(f.sub.1), . . . (f.sub.n)}
(93) Advantageously, the algebraic formalisms of the present invention can make use of an operator, termed the dot operator, that is specifically designed to work with dimension levels. Thus, the algebraic formalisms provide direct support for the use and exploration of database hierarchy in the present invention. One of the advantages of the dot operator is that it can deduce hierarchical information without analyzing database fact tables. Further advantages of the dot operator are discussed in Section 5.4.2.4, below.
(94) Step 614—construction of visual table 720 using the normalized set form. In step 614 (
(95)
(96) As illustrated in
(97) In some embodiments, the normalized set form generated in step 612 is more formally defined as p-entries and p-tuples. The set interpretation of an operand is a 0 finite (possibly empty) sequence of heterogeneous p-tuples. Each p-tuple in a set interpretation defines a row (or column or layer) of visual table 720. In other words, each p-tuple maps to a row, a column, or a layer in visual table 720. A p-tuple is a finite sequence of p-entries. A single p-tuple defines a single row (or column or layer). The entries of a p-tuple define the spatial encoding (axis) within the row and the selection criteria on the fact table of a database 558. A p-entry is an ordered “tag-value” pair where the tag defines the meaning and possible values of the value member of the pair. A p-entry will be written as tag:value; e.g., field:Profit. A tag can be a field, constant, or field name, as discussed in further detail in Section 5.4. In some embodiments, the panes 722 of the row, column, or layer to which an N:t ordered set of tuples (p-tuple) is mapped are ordered within the row, column, or layer in visual table 720 in the same order that is presented in the p-tuple.
(98) In summary, each axis of visual table 720 is defined by an expression from visual specification 550 that has been rewritten in normalized set form. The cardinality of this normalized set determines the number of rows (or columns or 5 layers) along the axis, with the exception of when the normalized set is the empty sequence. In a preferred embodiment, when the normalized set is an empty sequence, a single row or column is created rather than zero rows or columns. Each p-tuple within the normalized set defines a row (or column or layer). The p-entries within each p-tuple define both a selection criterion on the database 558 fact table, selecting tuples to be displayed in the row, and the spatial encoding in the row, defining the positions of the graphical marks used to visualize the database tuples. More information on the set interpretation is found in Section 5.4, below.
(99) In some embodiments visual table 720 is presented as a web interface. In some embodiments, all or portions of user interface Module 546 are run and displayed on a remote user computer in order to facilitate the presentation of visual table 720 as a web interface.
(100) Step 616—partition query results into tuples corresponding to panes 722 in visual table 720. In step 616 (
(101) 201: x-set compute normalized set form of x-axis expression
(102) 202: y-set compute normalized set form of y-axis expression
(103) 203: z-set compute normalized set form of z-axis expression
(104) 204: for each x-entry in x-set {
(105) 205: for each y-entry in y-set {
(106) 206: for each z-entry in z-set {
(107) 207: p-lookup=new PaneLookupDescriptor(x-entry, y-entry, z-entry)
(108) 208: p-spec=The PaneSpecification that applies to p-lookup
(109) 209: create the pane graphic
(110) 210: create the primitive object for rendering tuples
(111) 211: create the encoding objects for the visual properties and add to primitive object
(112) 212: create the per-pane transform that sorts tuples into drawing order
(113) 213: retrieve the data from the pane-data-cache using p-lookup
(114) 214: bind the data from the pane-data-cache using p-lookup
(115) 215: bind the pane to the data} } }
(116) Lines 201 through 203 are performed in step 612 (
(117) In lines 207 and 208, the pane specification for pane i is located. The pane specification is ultimately derived from visual specification 550. The pane specification for pane i defines the mark, encodings, etc., for the pane.
(118) In lines 209-212, the pane graphic of pane i is created using the pane specification that applies to pane i, in line 210, primitive objects for rendering triples within pane i are created. An example of a pane primitive object is a bar in a bar chart. In line 211, the encoding objects for the visual properties of each respective primitive object created in line 210 are created and added to the corresponding primitive objects. Exemplary encoding objects in the case of a bar are color and size of the bar. In line 212, the per-pane transform that sorts tuples into drawing order is applied. In other words, the per-pane transform is used to describe how tuples will be displayed in pane i.
(119) In line 213, the data for pane i is retrieved from pane-data-cache 557 using p-lookup. In lines 214-215, the data (e.g., a subset of the set of tuples that were retrieved from a query of database 558) for pane i is bound to pane i. In this way, data from a query of database 558 is bound to visual table 720 by visual interpreter module 556.
(120) In other words, in lines 209-212 a tuple in a subset of tuples associated with pane i is encoded as a graphical mark. In some instances, the tuple in the subset of tuples comprises a field that is then mapped to a graphical attribute (e.g., a color, a value, a size, a shape, a phrase, or a symbol). In some embodiments, the field is classified as quantitative or ordinal and (i) when the field is classified as quantitative, it is mapped to a first graphical attribute and (ii) when the field is classified as ordinal it is mapped to a second graphical attribute. In some embodiments the field is classified as independent or dependent and (i) when the field is classified as independent, it is mapped to a first graphical attribute and (ii) when the field is classified as dependent it is mapped to a second graphical attribute. The first and second attribute are each independently a color, a value, a size, a shape, a phrase or a symbol.
(121) In some embodiments, the subset of tuples associated with pane i is determined by a selection function. In some embodiments, the selection function uses an identity of a schema field that is present in the metadata of the database 558 characterized in step 602 to form the subset of tuples. For example, the specification may assign all tuples that belong to a specific schema field type to pane i. In some embodiments, the selection function uses a relational operator (e.g., a selection operator or a grouping operator) to form the subset of tuples associated with pane i. Further, the ordering of rows and columns in visual table 720 can be controlled and filtered as well.
(122) The algorithm described in lines 201 through 215 assumes that each query of 558 is available in a pane-data-cache 557. Recall that an important advantage of the present invention is that queries are typically grouped across several panes. Thus, queries need to be partitioned into a separate table for each pane and then placed in the pane-data-cache 557. While the present invention imposes no limitation on which software module performs this grouping transformation, in one embodiment of the present invention, the grouping transformation is performed by data interpreter module 552 as part of a generalized algorithm for querying databases 558. See, for example, the algorithm described in step 606, above.
(123) In some embodiments of the present invention, step 608 returns a set of tuples. Next, in step 610 a new tuple is derived from the set of tuples. This new tuple is then incorporated into the set of tuples for possible association with one or more panes 722 in the graphic that is specified by visual specification 550. In some instances a relational operator (e.g., a sorting operator, an aggregation operator, or a transforming operator) is used to create the new tuple. An example of this is an additional transformation that is performed to augment the query language. For example, it is known that an MDX query can easily aggregate all twelve months of a year into year total and then, say, aggregate multiple years into a multi-year total because this aggregation occurs up and down the hierarchy. But MDX cannot easily aggregate across a hierarchy (e.g., the totals for all Januaries regardless of the year). The present invention allows for aggregation across a hierarchy by applying one or more local transformations to a set of returned tuples (e.g., a set of tuples returned from one or more MDX queries). For example, in order to obtain totals for all Januaries regardless of year, one or more MDX queries are made to obtain the relevant tuples and then the month of January is aggregated across respective years in the MDX query results.
(124) In some embodiments of the present invention, step 608 returns a set of tuples. A group is formed using all or a portion of the tuples in the set of tuples. Then a graphic based on the group is formed. Such embodiments are useful in instances where a multi-pane graphic is constructed. Examples of such graphics include a line that connects each tuple in a group or an area that encloses each tuple in the group.
(125) In some embodiments, specification 550 organizes one or more panes 722 into a plurality of layers and each layer in the plurality of layers is assigned a tuple from a different database 558 that was characterized in step 602. In some embodiments, the specification 550 organizes one or more panes 722 into a plurality of columns and a plurality of rows and each column in the plurality of columns is assigned a tuple from a different database 558 that was characterized in step 602. In still other embodiments, the specification organizes the one or more panes into a plurality of columns and a plurality of rows and each row in the plurality of rows is assigned to a tuple from a different database 558 that was characterized in step 602. In still further embodiments, the specification organizes the one or more panes into a plurality of pages and each page in the plurality of pages is assigned to a tuple from a different database 558 that was characterized in step 602.
(126) An overview of the steps performed in accordance with one embodiment of the present invention has been provided. The invention is highly advantageous because it takes advantage of the underlying hierarchy of one or more target database 558 in order to allow a user to more efficiently explore databases 558. A user can rapidly drill down hierarchical layers within each target database 558. For example, in one embodiment of the invention, the interface includes a “.Math.” icon (
1.7 Illustrative Types of Database Hierarchy and Database Organization
(127) The present invention provides visualization techniques for the exploration and analysis of multidimensional analytic data stored in databases 558. One form of databases 558 is a data warehouse. Data warehouses are typically structured as either relational databases or multidimensional data cubes. In this section, aspects of relational databases and multidimensional data cubes that are relevant to the present invention are described. For more information on relational databases and multidimensional data cubes, see Berson and Smith, 1997, Data Warehousing, Data Mining and OLAP, McGraw-Hill, New York; Freeze, 2000, Unlocking OLAP with Microsoft SQL Server and Excel 2000, IDG Books Worldwide, Inc., Foster City, Calif.; and Thomson, 1997, OLAP Solutions: Building Multidimensional Information Systems, Wiley Computer Publishing, New York. In addition, it will be appreciated that in some embodiments database 558 does not have a formal hierarchical structure. In such embodiments, hierarchical structure for the database is derived by analyzing the database using user interface module 544.
(128) 1.7.1 Data Organization
(129) Databases have typically been used for operational purposes (OLTP), such as order entry, accounting and inventory control. More recently, corporations and scientific projects have been building databases, called data warehouses or large on line analytical processing (OLAP) databases, explicitly for the purposes of exploration and analysis. The “data warehouse” can be described as a subject-oriented, integrated, time-variant, nonvolatile collection of data in support of management decisions. The key aspect of the data warehouse is that it is a repository for analytic data rather than transactional or operational data. The data contained in the data warehouse usually represents historical data, e.g., transactions over time, about some key interest of the business or project. This data is typically collected from many different sources such as operational databases, simulations, data collection tools (e.g., tqdump), and other external sources.
(130) Data warehouses are built using both relational databases and specialized multidimensional structures called data cubes. In this subsection, the organization of the data within these databases, such as the database schemas, the use of semantic hierarchies, and the structure of data cubes, is explained. In the next subsection, the difference between the organization of OLAP databases and OLTP databases is described.
(131) 1.7.2 Relational Databases
(132) Relational databases organize data into tables where each row corresponds to a basic entity or fact and each column represents a property of that entity. For example, a table may represent transactions in a bank, where each row corresponds to a single transaction, and each transaction has multiple attributes, such as the transaction amount, the account balance, the bank branch, and the customer. The table is referred to as a relation, a row as a tuple, and a column as an attribute or field. The attributes within a relation can be partitioned into two types: dimensions and measures. Dimensions and measures are similar to independent and dependent variables in traditional analysis. For example, the bank branch and the customer would be dimensions, while the account balance would be a measure. A single relational database will often describe many heterogeneous but interrelated entities. For example, a database designed for a coffee chain might maintain information about employees, products, and sales. The database schema defines the relations (tables) in a database, the relationships between those relations, and how the relations model the entities of interest.
(133) 1.7.3 Hierarchical Structure
(134) Most dimensions in a database have a hierarchical structure. This hierarchical structure can be derived from the semantic levels of detail within the dimension or generated from classification algorithms. The systems and methods of the present invention use these hierarchies to provide tools that an analyst can use to explore and analyze data at multiple levels of detail calculated from the fact table. For example, rather than having a single dimension “state”, a hierarchical dimension “location” that has three levels, one each for country, state, and county, can be used. Then, the analyst can aggregate the measures of interest to any of these levels. The aggregation levels are determined from the hierarchical dimension, which is structured as a tree with multiple levels. The highest level is the most aggregated and the lowest level is the least aggregated. Each level corresponds to a different semantic level of detail for that dimension. Within each level of the tree, there are many nodes, with each node corresponding to a value within the domain of that level of detail of that dimension. The tree forms a set of parent-child relationships between the domain values at each level of detail. These relationships are the basis for aggregation, drill down, and roll up operations within the dimension hierarchy.
(135) 1.7.4 Data Cubes
(136) A data warehouse can be constructed as a relational database using either a star or snowflake schema and will provide a conceptual model of a multidimensional data set. However, the typical analysis operations such as summaries and aggregations are not well supported by the relational model. The queries are difficult to write in languages such as SQL and the query performance is not ideal. As a result, typically, the fact tables and dimension tables are not used directly for analysis but rather as a basis from which to construct a multidimensional database called a data cube.
(137) Each axis in the data cube corresponds to a dimension in the relational schema and consists of every possible value for that dimension. For example, an axis corresponding to states would have fifty values, one for each state. Each cell in the data cube corresponds to a unique combination of values for the dimensions. For example, if there are two dimensions, “State” and “Product”, then there would be a cell for every unique combination of the two, e.g., one cell each for (California, Tea), (California, Coffee), (Florida, Tea), (Florida, Coffee), etc. Each cell contains one value per measure of the data cube. So if product production and consumption information is needed, then each cell would contain two values, one for the number of products of each type consumed in that state, and one for the number of products of each type produced in that state.
(138) Dimensions within the data warehouse are often augmented with a hierarchical structure. The systems and methods of the present invention use these hierarchies to provide tools that can be used to explore and analyze the data cube at multiple meaningful levels of aggregation. Each cell in the data cube then corresponds to the measures of the base fact table aggregated to the proper level of detail. If each dimension has a hierarchical structure, then the data warehouse is not a single data cube but rather a lattice of data cubes, where each cube is defined by the combination of a level of detail for each dimension (
(139) 1.7.5 OLAP Versus OLTP
(140) The previous section described how both relational databases and data cubes could be organized and used for analytical purposes (OLAP). Traditionally, however, relational databases have been used for day-to-day operational purposes. These OLTP databases address different issues than OLAP databases or data warehouses and, as a result, have schemas and usage patterns that are quite different. It is necessary to understand the differences between these two types of databases in order to understand the issues affecting the design of OLAP visualization tools.
(141) OLTP databases are optimized for performance when processing short transactions to either query or modify data, possibly interfacing with more than one system and supporting many simultaneous connections. Furthermore, query performance is typically secondary to issues like avoiding data redundancy and supporting updates. Typical OLTP queries retrieve a few dozen tuples from only a few relations and then update some of the tuples. For example, a typical query might retrieve a single customer's record based on their account number, or add a single transaction to a sales relation when a sale occurs. Database schema definitions for operational databases focus on maximizing concurrency and optimizing insert, update, and delete performance. As a result, the schema is often normalized, resulting in a database with many relations, each describing a distinct entity set.
(142) In contrast, rather than being used to maintain updateable transaction data, users need to be able to interactively query and explore OLAP databases. The queries for OLAP are very different in that they typically retrieve thousands of rows of information and modify none of them. The queries are large, complex, ad hoc, and data-intensive. Because an operational schema separates the underlying data into many relations, executing these analytical queries on a database based on an operational schema would require many expensive join computations. Since analysis databases are typically read-only, and because query performance is the primary concern, OLAP databases sacrifice redundancy and update performance to accelerate queries, typically by denormalizing the database into a very small number of relations using a star or snowflake schema. External tools can typically view an OLAP database as either a data cube or a single large relation (table).
(143) 1.7.6 Multidimensional Analysis Operations
(144) In some embodiments database 558 is typically quite large, consisting of many dimensions each with hierarchical structure and often many members. To navigate the resulting lattice of data cubes and perform dimensional reduction to extract data for analysis, there are a number of multidimensional analysis operations that are used. This section describes such operations.
(145) Drill down refers to the process of navigating through the lattice of data cubes in the direction of more detail. It is the technique used to break one piece of information into smaller and more detailed parts. Roll up is the inverse of drill down, aggregating detailed data into coarser elements. Projection (illustrated in
(146) Where projection reduces dimensionality via aggregation, slicing (illustrated in
(147) 1.7.7 Data Characterization for Visualization
(148) Having described how the OLA data used by some embodiments of the present invention is organized, additional data characterization used to support some visualization processes of the present invention is now discussed. For the purposes of visualization, more about an attribute than is usually captured by a database system is needed. Databases typically provide limited information about a field, such as its name, whether a field is a dimension or measure, and its type (e.g., time, integer, float, character).
(149) In some embodiments of the present invention, a determination is made as to whether a database field (operand) is nominal, ordinal, or quantitative in order to determine how to encode the field in a visual table using visual properties. Representative visual properties include, but are not limited to, color, size, or position. This characterization is based on a simplification of Stevens' scales of measurement. See Stevens, On the theory of scales of measurement, In Science, (103), pp. 677-680. In some embodiments, this characterization is further simplified depending on if the context emphasizes tire difference between discrete data and continuous data or if the context emphasizes whether the field has an ordering. In one example, when encoding a field spatially, the emphasis is on whether a field has discrete values. Furthermore, when a field is assigned to an axis, it has an ordering. Thus, in this context, nominal fields that do not normally have an ordering are assigned one and then treated as an ordinal field in some embodiments of the present invention. The resulting characterization is called categorical. In contrast, when assigning visual properties such as color to a field, then the important distinguishing characterization is order. In this context, the ordinal and quantitative fields are treated as a single characterization and nominal fields are considered separately, in some embodiments of the present invention. In addition, attributes have associated units and semantic domains. For example, attributes can encode time, geographic units such as latitude, or physical measurements. If this information is available, it can also be used to generate more effective visual encodings and aid in determining the geometry (e.g., aspect ratio) of a visual table 720. For example, knowing that the x and y axis of a visual table 720 correspond to latitude and longitude, rather than profit and sales, will affect the determination of the appropriate geometry.
(150) Databases also typically only store the current domain of a field—the values that currently exist within the database without any ordering. However, for analysis it is important to understand the actual domain of a field, such as the possible values and their inherent (if applicable) ordering. To encode an attribute as an axis of a visual table 720, all possible values and their ordering need to be determined so that an indication of when data is missing can be made and to present data within its semantic context rather than using some arbitrary ordering, e.g., alphabetic. In some embodiments, this additional data characterization is captured in an attributed file 580 (e.g., an XML, document) that is associated with database 558 (
1.8 Algebra
(151) As discussed above, a complete table configuration consists of three separate expressions. Two of the expressions define the configuration of the x- and y-axes of a visual table 720, partitioning the table into rows and columns. The third expression defines the z-axis of visual table 720, which partitions the display into layers of x-y tables that are composited on top of one another. This section sets forth an algebra, including its syntax and semantics, that is used in these three expressions in some embodiments of the present invention. As discussed above, each expression in the algebra used in some embodiments of the invention is composed of operands connected by operators. Operands and operators will be discussed in turn in the following sections.
(152) 1.8.1 Operands
(153) The operands in the table algebra described in this section are the names of the fields (field operands) of the database 558 and the names of predefined constant sequences of p-tuples (constant operands). In some embodiments, the categorization of field types is reduced to ordinal and quantitative by assigning a default alphabetic ordering to all nominal fields and then treating them as ordinal. Thus, in such embodiments, there are three classes of operands: (1) ordinal field operands, (2) quantitative field operands, and (3) constant operands. Throughout the remainder of this section, the terms A and B represent ordinal field operands, P and Q represent quantitative field operands, C represents a constant operand, and X, Y, and Z represent expressions.
(154) 1.8.1.1 Set Interpretations
(155) Set interpretations are assigned to each operand symbol in the following manner. Ordinal fields are assigned the members of the ordered domain of the field. Quantitative fields are assigned the single element set containing the field name. Constant operands are assigned their predefined set interpretation.
A=domain(A)=>(A:a), . . . ,(A:a.sub.n)>
P=<(field:P)>
C=<(constant:c), . . . ,(constant:c.sub.m)>
(156) For simplicity of exposition, tags are not included in the remaining set interpretations within this section except where necessary.
(157) The assignment of sets to field operands reflects the difference in how the two types of fields will be encoded in the structure of visual tables 720. Ordinal fields partition visual table 720 (and the database triples) into rows and columns, whereas quantitative fields are spatially encoded as axes within panes 722.
(158) 1.8.1.2 Constant Operands
(159) Constant operands define neither selection criteria nor spatial encodings. Instead, they can be used to generate additional rows without partitioning database tuples. This facilitates the layering of heterogeneous databases. In some embodiments, constant operands are treated as ordinal field operands by defining a virtual fact table and then defining operators relative to this virtual fact table. Let (C, . . . , Cn) be a set of constant operands, Rc be a relation with a single attribute (Ci) whose domain corresponds to the predefined set interpretation of Ci, and FT be the fact table for database 558. The virtual fact table VFT is defined relative to the given set of constant operands as:
VFT=FT×R.sub.c, . . . ,×R.sub.ci
(160) This algebra contains one predefined constant operand, the empty sequence.
(161) 1.8.1.3 Filtering and Sorting of Field Operands
(162) If a field is to be filtered (or sorted), the filtered and sorted domain is listed directly after the field operand in the expression, in effect specifying a set interpretation for the operand. Given an ordinal field A with domain (A)=<(a), . . . (an)>, the operand can be filtered and sorted within an expression by stating the filtered and sorted domain (<b, . . . , bj>, bi>ε domain (A)) directly after the ordinal operand and the set interpretation is the listed domain:
A[(b, . . . ,b.sub.j]=<(b), . . . ,(b.sub.j)>
Similarly, a filtered domain can be specified for a quantitative field by listing the minimum and maximum values of the desired domain. This information is included in the generated set interpretation:
P[min,max]=<(field: P[min,max])>
Having defined the operands and the generation of their set interpretations, the four operators in the algebra of the present invention can be defined.
(163) 1.8.2 Operators
(164) As stated above, a valid expression in the algebra is an ordered sequence of one or more operands with operators between each pair of adjacent operands. The operators in this algebra, in order of precedence, are dot (.), cross (x), nest (/), and concatenation (+). Parentheses can be used to alter precedence. Because each operand is interpreted as a sequence, the precise semantics of each operator is defined in terms of how it combines two sequences (one each from the left and right operands) into a single sequence. Definitions of the dot, cross, nest and concatenation operators are provided below. The exact definitions provides below are merely exemplary and other definitions that are consistent with the features of each operator are within the scope of the present invention.
(165) 1.8.2.1 Concatenation
(166) The concatenation operator performs an ordered union of the set interpretations of the two operands and can be applied to any two operands or expressions:
(167)
(168) The only algebraic property that holds for the concatenation operator is associatively:
(169)
(170) The concatenation operator is not commutative because the ordered union of two sequences is not commutative.
(171) 1.8.2.2 Cross
(172) The cross operator performs a Cartesian product of the sets of the two symbols:
(173)
(174) Quantitative fields and expressions may appear only as right-hand side operands when the cross operator is applied. The cross operator is also associative but not commutative (because the ordered Cartesian product is not commutative):
(175)
(176) 1.8.2.3 Nest
(177) The nest operator is similar to the cross operator, but it only creates set entries for which there exist database tuples with the same domain values. If VFT is defined to be the virtual fact table of the database being analyzed relative to all constant operands in the expressions X and Y, t to be a tuple, and t(X . . . Xa) to be the values of the fields X through X, for the tuple 1, then the nest operator can be defined as follows:
(178)
(179) The ordering of the p-tuples in a sequence generated by application of the nest operator is the same as it would be in the sequence generated by the application of the cross operator to the same operands.
(180) The intuitive interpretation of the nest operator is “B within A”. For example, given the fields Quarter and Month, the expression Quarter/Month would be interpreted as those months within each quarter, resulting in three entries for each quarter (assuming data exists for all months in the fact table). In contrast Quarter×Month would result in 12 entries for each quarter. The nest operator may only be applied to ordinal operands and expressions. Nest is an associative operator.
(181) 1.8.2.4 Dot
(182) The cross and nest operators provide tools for generating ad hoc categorical hierarchies. However, data warehouses often contain dimensions with explicit semantic hierarchies. The dot operator provides a mechanism for exploiting these hierarchical structures in the algebra of the present invention. The dot operator is similar to the nest operator but is “hierarchy-aware”.
(183) If DT is defined to be a relational dimension table defining a hierarchy that contains the levels A and B, and A precedes B in the schema of DT, then:
A.Math.B<(a,b)|∃tεDT st t(A)=a&t(8)=b>
(184) Similarly, dot can be defined relative to an expression X involving only the dot operator and levels from the same dimension hierarchy. DT is defined to be the relational dimension table defining the dimension that contains all levels in X and the dimension level A. In addition, all levels in X must appear in the schema of DT in the order they appear in X and they must precede A in the schema of DT Then:
X.Math.A=<(x, . . . ,x.sub.n,a)|∃tεDT st t(X, . . . ,X.sub.n)=(x, . . . ,x.sub.n)& t(A)=a>
The dot operator is also associative but not commutative.
(185) Nest could be used for drilling down into a hierarchy but this usage would be flawed. The nest operator is unaware of any defined hierarchical relationship between the dimension levels; instead, it derives a relationship based on the tuples in the fact table. Not only is this approach inefficient, as fact tables are often quite large, but it can also yield incorrect results. For example, consider the situation where no data was logged for November. Application of the nest operator to Quarter and Month would result in an incorrectly derived hierarchy that did not include November as a child of Quarter 4.
(186) The dot operator provides a particularly advantageous method for working with database 558 hierarchy. This is because the dot operator uses the hierarchical information that is either (i) defined in database 558 dimension tables or (ii), in instances where database 558 does not have dimension tables, is constructed by database hierarchy module 544 (with possible user intervention). In contrast, the nest operator is unaware of the defined hierarchical relationship between dimension levels and/or the hierarchy that is constructed by database hierarchy module 542. Instead, the nest operator works by deriving hierarchical type relationships within the database based on existence scans of tuples in database 558 fact tables. This is an inefficient way of deriving hierarchical information because the fact tables can be quite large. Advantageously, the dot operator does not derive hierarchical type relationships within the database based on existence scans. Rather, the dot operator uses the metadata associated with the database 558 that defines the database hierarchy. The form of this metadata will be dependent upon the exact nature of databases 558. In some instances the metadata will comprise, for example a star schema. In instances where the database 558 does not have such defined hierarchical relationships (for example in the case where database 558 is a flat file) the metadata will be constructed by database hierarchy module.
(187) 1.8.2.5 Summary
(188) Using the above set semantics for each operator, every expression in the algebra can be reduced to a single set with each entry in the set being an ordered p-tuple. We call this set evaluation of an expression the normalized set form. The normalized set form of an expression determines one axis of the table: the table axis is partitioned into columns (or rows or layers) so that there is a one-to-one correspondence between set entries in the normalized set and columns:
(189) 1.8.3 Algebraic Properties
(190) In the present invention, an algebraic expression is interpreted as a set for two purposes (i) to determine the underlying tabular structure of a visual table 720 and (ii) to determine the tuples to be retrieved from database 558. In the former case, the ordering of the p-tuples in the normalized set form is meaningful because it determines the ordering of the columns, rows, and layers of visual table 720. As a result, the only algebraic property that holds for our operators is associativity. Commutative or distributive operators would allow algebraic manipulations that change the ordering of the normalized set form. However, when performing interpretation to determine which database tuples to retrieve, these constraints on the properties of the operators can be relaxed since the ordering of the p-tuples in the set interpretation is not meaningful in the context of database queries. Specifically, for this purpose only, the set interpretations are treated as bags instead of sequences (thus discarding ordering) and allow the following algebraic properties:
(191) Associative
(A+B)+C=A+(B+C)
(A.Math.B).Math.C=A.Math.(B.Math.C)
(A×B)×C=A×(B×C)
(AB)/C=A/(B/C)
(192) Distributive
A×(B+C)(A×B)+(A×C)
A/(B+C)=(A/B)+(A/C)
(193) Commutative
A+B=B+A
A×B=B×A
A/B=B/A
(194) If the operators are changed to allow these algebraic properties, they can be used to quickly determine the database queries or data cube projections required to generate a visual table 720.
(195) 1.8.4 Syntax Revisited
(196) In the previous sections, the syntax of an algebra in accordance with the present invention was defined as a sequence of operands separated by operators. Some constraints on the applications of the operators were also provided. In this section, the syntax is made precise by using a grammar. To define a grammar, four things are defined: a set of terminal symbols, a set of non-terminals, a set of production rules, and a start symbol. As such, the grammar in accordance with the present invention has ten terminal symbols:
(197) TABLE-US-00001 Symbol Definition q.sub.field The name of a quantitative field O.sub.field The name of an ordinal field q.sub.dim The name of a quantitative dimensional level O.sub.dim The name of an ordinal dimensional level C A constant operand .x/+ The operators of the algebra ( ) Parentheses
(198) The following are the production rules for the grammar (E is the start symbol):
E.fwdarw.O.sub.expr/Q.sub.expr
O.sub.expr.fwdarw.(O.sub.expr)/Q.sub.expr+Q.sub.expr/O.sub.expr×O.sub.expr/O.sub.expr/O
Q.sub.expr.fwdarw.(O.sub.expr)/E+Q.sub.expr/O.sub.expr+E/(O.sub.expr×O.sub.expr/Q
O.fwdarw.Q.sub.hter/O.sub.field/c
O.sub.hter.fwdarw.Q.sub.hter.Math.O.sub.dim/O.sub.dim
Q.fwdarw.Q.sub.hter/O.sub.field
Q.sub.hter.fwdarw.Q.sub.hter.Math.q.sub.dim/q.sub.dim
(199) The following are the main syntactic constraints on the operators that are expressed in this grammar:
(200) Cross: Quantitative operands, or expressions containing quantitative operands, can only be right-hand side operands of the cross operator.
(201) Nest: The nest operator can only be applied to ordinal operands or expressions.
(202) Dot: The dot operator can only be applied to dimension levels. Furthermore, a quantitative field can only appear as the right-most operand of a dot operator, since quantitative dimension levels are only possible as the leaf level of a dimension hierarchy.
(203) Concatenate: Concatenate can be applied to any operand.
(204) Thus far, how the algebraic expressions partition tables into rows and columns has been discussed. How the algebraic expressions handle layers will now be discussed.
(205) 1.8.5 Layers
(206) In the present invention a layer in a visual table 720 is a single x-y table whose structure is defined by the x- and y-axes expressions. Every layer in a specification is composited together back-to-front to form the final visualization. A single visualization can combine multiple data sources. Each data source is mapped to a distinct layer or set of layers. While all data sources and layers share the same configuration for x- and y-axes of the table, each data source can have a different expression (the z-axis) for partitioning its data into layers. Layering of multiple data sources and the partitioning of layers are illustrated in
(207) Constant operands are an important aspect of layering. A single visualization may be composed of multiple heterogeneous databases 558, each mapped to a distinct layer, and all layers must share the same expressions for the x- and y-axes. However, sometimes it is desirable to include ordinal fields in the x- and y-axes expressions that exist in only a subset of the visualized databases. When this occurs, constant operands are generated for the other layers with a predefined set interpretation that matches the domain of the ordinal field in the layer in which the field does appear, Thus, the expressions can be properly evaluated for each layer.
(208) The z-axis expression for a data source is more constrained than the expressions for the x and y-axes. Specifically, since layering must be discrete, a z-axis expression can contain only ordinal operands; not quantitative operands. In other words, a z-axis expression is constrained to the O.sub.expr production rule in the grammar of the present invention.
(209) 1.8.6 Summary
(210) The algebra of the present invention provides a succinct yet powerful notation for describing the underlying structure of visual tables 720. The algebraic expressions define how the table is partitioned into rows, columns, and layers, and additionally defines the spatial encodings within each pane 722 of the table.
(211) At this point, it is useful to consider the conceptual data flow. As well as defining visual table 720's structure, the algebraic expressions of the visual specification (formed on shelves 708-1, 708-4, and 708-5) define which tuples of the database 558 should be selected and mapped into each pane 722. When a specification is interpreted, one or more queries are generated to retrieve topics from the database (
1.9 Exemplary Visual Specification
(212) To understand the advantages of the dot operator, the problems that dimension levels create will be explained. Consider the Month dimensional level in the time hierarchy illustrated in
(213) The solution to the problem of how to reduce a dimensional level to a single set is the dot (“.”) operator. If DT is defined to be the dimensional table defining the hierarchy that contains the levels A and B, and A precedes B in the schema of DT, then:
A.Math.B−{(a.Math.b)|∃rεDrstA(r)−a & B(r)−b}
where r is a record and A(r) is the value of operand A for record r. Thus, the dot produces a set of single-valued tuples, each containing a qualified value. If the two operands are not levels of the same dimension hierarchy (or set interpretations of operations on levels of the same hierarchy), or A does not precede B in the schema of DT (e.g., A must be an ancestor level in the tree defined by DT), then the dot operator evaluates to the empty set. With this definition, the two expressions “Month” and “Year.Month” are not equivalent “Month” is interpreted as (January, February, . . . , December) whereas “Year.Month” is interpreted as (1998.January, 1998.February, . . . , 1999.December). With a fully populated fact table, Year.Month is equivalent to Year/Month (where “r is the nest operator” defined in Section 5.4).
1.10 Examples
(214) Each of the following examples demonstrates how database analysis can progress from a high level of abstraction to detailed views of the data. Furthermore, each example shows the importance of being able to easily change the data being viewed, pivot dimensions, and drill down database hierarchy during the analysis process.
(215) 1.10.1 Example 1—Mobile Network Usage
(216)
(217) To start the analysis, the analyst first sees if any patterns in time can be spotted by creating a series of line charts in
(218) Given this broad understanding of traffic patterns, the next question posed by the analyst is how the application mix varies depending on the research area. The analyst pivots the display to generate a single line chart of packet count per research area over time, broken down and colored by application class (
(219) Curious, the analyst then drills down further to see the individual project groups (
(220) 1.10.2 Example 2—Year 2000 Presidential Election Results
(221)
(222) In
(223) 1.10.3 Example 3—Historical Profit/Sales for a Coffee Chain
(224) The example is illustrated in
(225) The first visualization created,
(226) In the final visualization,
(227) 1.11 References Cited
(228) All references cited herein are incorporated herein by reference in their entirety and for all purposes to the same extent as if each individual publication or patent or patent application was specifically and individually indicated to be incorporated by reference in its entirety for all purposes.
(229) 1.12 Alternative Embodiments
(230) The present invention can be implemented as a computer program product that comprises a computer program mechanism embedded in a computer readable storage medium. For instance, the computer program product could contain the program modules shown in
(231) Many modifications and variations of this invention can be made without departing from its spirit and scope, as will be apparent to those skilled in the art. The specific embodiments described herein are offered by way of example only, and the invention is to be limited only by the terms of the appended claims, along with the full scope of equivalents to which such claims are entitled.