Apparatus and method for compound on-line analytical processing in databases

Abstract

A method executed by a computer under the control of a program includes the step of establishing a compound structure in the form of a virtual unit of multi-dimensional storage. The compound structure includes a rack with a horizontal arrangement of target structures linked by an alias backbone representing a dimension of information. The horizontal arrangement of target structures selectively includes further compound structures and base structures containing data, in any combination. The compound structure is referenced to obtain information. The method is particularly useful in On-Line Analytical Processing (OLAP).

Claims

What is claimed is:

1. A method executed by a computer under the control of a program, said method comprising the steps of:

providing a view of a compound structure in the form of a virtual unit of multi-dimensional storage, said compound structure including a rack with a horizontal arrangement of target structures linked by an alias backbone representing a dimension of information, wherein said horizontal arrangement of target structures includes at least one nested compound structure, said compound structure referencing data in physical memory without combining said data in physical memory in the manner represented in said view; and

referring to said compound structure to obtain information associated therewith.

2. The method of claim 1 wherein said providing includes establishing a compound structure with a stack defining a vertical arrangement of racks linked by said alias backbone.

3. The method of claim 2 wherein said providing includes establishing a top level rack wherein said target structures have read and write functionality.

4. The method of claim 2 wherein said providing includes establishing a bottom level rack wherein said target structures have read-only functionality.

5. The method of claim 1 further comprising using said alias backbone as an index during said referring.

6. The method of claim 1 wherein providing includes providing a horizontal arrangement of target structures including at least one compound structure and a base structure.

7. The method of claim 6 wherein providing includes providing a base structure of multi-dimensional storage.

8. A method executed by a computer under the control of a program, said method comprising the steps of:

providing a view of a compound structure in the form of a virtual unit of multi-dimensional storage, said compound structure including a rack with a horizontal arrangement of target structures linked by an alias backbone representing a dimension of information, wherein said horizontal arrangement of target structures includes at least one nested compound structure, said virtual unit of multi-dimensional storage representing said compound structure as a combination of target structures that does not exist in physical memory in the manner in which said view of said compound structure is represented in said virtual unit of multi-dimensional storage; and

referencing said compound structure to obtain information associated therewith.

9. The method of claim 8 wherein said providing includes establishing a compound structure with a stack defining a vertical arrangement of racks linked by said alias backbone.

10. The method of claim 9 wherein said providing includes establishing a top level rack wherein said target structures have read and write functionality.

11. The method of claim 9 wherein said providing includes establishing a bottom level rack wherein said target structures have read-only functionality.

12. The method of claim 8 further comprising using said alias backbone as an index during said referencing.

13. The method of claim 8 wherein providing includes providing a horizontal arrangement of target structures including at least one compound structure and a base structure.

14. The method of claim 13 wherein providing includes providing a base structure of multi-dimensional storage.

15. A computer readable memory to direct a computer to function in a specified manner, comprising:

executable instructions to provide a view of a compound structure in the form of a virtual unit of multi-dimensional storage, said compound structure including a rack with a horizontal arrangement of target structures linked by an alias backbone representing a dimension of information, wherein said horizontal arrangement of target structures includes at least one nested compound structure, said compound structure referencing data in physical memory without combining said data in physical memory in the manner represented in said view; and

executable instructions to refer to said compound structure to obtain information associated therewith.

16. The computer readable memory of claim 15 further including executable instructions to establish a compound structure with a stack defining a vertical arrangement of racks linked by said alias backbone.

17. The computer readable memory of claim 16 further including executable instructions to establish a top level rack wherein said target structures have read and write functionality.

18. The computer readable memory of claim 16 further including executable instructions to establish a bottom level rack wherein said target structures have read-only functionality.

19. The computer readable memory of claim 15 further comprising executable instructions to use said alias backbone as an index.

20. The computer readable memory of claim 15 further comprising executable instructions to establish a horizontal arrangement of target structures including at least one compound structure and a base structure.

21. The computer readable memory of claim 20 further comprising executable instructions to establish a base structure of multi-dimensional storage.

22. A computer readable memory to direct a computer to function in a specified manner, comprising:

executable instructions to provide a view of a compound structure in the form of a virtual unit of multi-dimensional storage, said compound structure including a rack with a horizontal arrangement of target structures linked by an alias backbone representing a dimension of information, wherein said horizontal arrangement of target structures includes at least one nested compound structure, said virtual unit of multi-dimensional storage representing said compound structure as a combination of target structures that does not exist in physical memory in the manner in which said view of said compound structure is represented in said virtual unit of multi-dimensional storage; and

executable instructions to reference said compound structure to obtain information associated therewith.

23. The computer readable memory of claim 22 further including executable instructions to establish a compound structure with a stack defining a vertical arrangement of racks linked by said alias backbone.

24. The computer readable memory of claim 23 further including executable instructions to establish a top level rack wherein said target structures have read and write functionality.

25. The computer readable memory of claim 23 further including executable instructions to establish a bottom level rack wherein said target structures have read-only functionality.

26. The computer readable memory of claim 22 further including executable instructions to use said alias backbone as an index.

27. The computer readable memory of claim 22 further comprising executable instructions to establish a horizontal arrangement of target structures including at least one compound structure and a base structure.

28. The computer readable memory of claim 27 further comprising executable instructions to establish a base structure of multi-dimensional storage.

Description

BRIEF DESCRIPTION OF THE INVENTION

This invention relates generally to computer databases. More particularly, this invention relates to a technique for organizing data in databases using compound structures and On-Line Analytical Processing.

BACKGROUND OF THE INVENTION

On-Line Analytical Processing (OLAP) generally refers to a technique of providing fast analysis of shared multi-dimensional information stored in a database. OLAP systems provide a multi-dimensional conceptual view of data, including full support for hierarchies and multiple hierarchies. This framework is used because it is the most logical way to analyze businesses and organizations.

Unfortunately, it is difficult to handle large volumes of multi-dimensional information in a computer. The first problem is one of size. While small volumes of multi-dimensional data can be handled in Random Access Memory (RAM), this technique does not work for large problems. Multi-dimensional information is typically very large. Because OLAP is used for interactive analysis, it must respond very rapidly to queries, even when the data volumes grow.

The second problem is that multi-dimensional data is almost always sparse. In fact, in large multi-dimensional applications, it is not unusual to have only one cell populated for every million cells that are defined.

The sparsity problem discourages the storage of data in simple, uncompressed arrays, except in certain special cases. The simplest way of dealing with sparse data might seem to be to store only cells containing data in some indexed form. However, this approach has two problems. First, the index and keys are likely to take much more space than the data. Moreover, it is relatively time consuming to search them. Second, access will be inefficient because multi-dimensional data is often clustered, consisting of regions of relatively dense data separated by large, extremely sparse or totally empty sections. As a result, related data cells are unlikely to be placed physically close to each other.

A typical prior art approach to these problems is to break the data into smaller, denser multi-dimensional objects. Some techniques do this implicitly, presenting all the data to the user in what is known as a "hyper-cube" format in which all the data in the application appears to be in a single multi-dimensional structure. Other techniques do it explicitly in what is known as the "multi-cube" approach, in which the multi-dimensional database consists of a number of separate objects, usually with different dimensions. That is, the database is segmented into a set of multi-dimensional structures, each of which is composed of a subset of the overall number of dimensions in the database. Each segmented structure might be, for example, a set of variables or accounts, each dimensioned by just the dimensions that apply to that variable. It is also possible to identify two main types of multi-cubes. Block multi-cubes use orthogonal dimensions so there are no special dimensions at the data level. A cube may consist of any number of the defined dimensions, and both measures and time are treated as ordinary dimensions, just like any other. Series multi-cubes treat each variable as a separate cube (often a time series), with its own set of distinct dimensions.

In general, multi-cubes are more versatile, but hyper-cubes are easier to understand. End-users relate better to hyper-cubes because of their higher level view. Multi-cubes provide greater tunability and flexibility. In addition, multi-cubes are a more efficient way of storing very sparse data.

It would be highly desirable to develop an OLAP technique that combines the conceptual benefits of hyper-cubes with the processing benefits (e.g., versatility, tunability, and flexibility) of multi-cubes.

SUMMARY OF THE INVENTION

A method executed by a computer under the control of a program includes the step of establishing a compound structure in the form of a virtual unit of multi-dimensional storage. The compound structure includes a rack with a horizontal arrangement of target structures linked by an alias backbone representing a dimension of information. The horizontal arrangement of target structures selectively includes further compound structures and base structures containing data, in any combination. The compound structure may also include a stack with a vertical arrangement of racks linked by the alias backbone. The top level rack of the stack has read and write functionality, while the bottom level of the stack has read-only functionality. The compound structure is referenced to obtain information.

The invention provides the benefits of both multi-cubes and hyper-cubes. That is, the invention allows versatile, tunable, flexible and space efficient multi-cubes to be joined together into a compound structure that can be easily comprehended and manipulated by application developers and end users. The invention allows the underlying design of the structures to be changed without disturbing the view of the data which is accessed at the higher level. Another advantage of this architecture is that it provides a completely scalable and adaptable infrastructure. The complete scalability arises from the freedom to divide a multi-dimensional problem into manageable base structures, and then to efficiently process those structures in series or in parallel. That is, the processing of the base structures can be spread over many processors, either inside a single multi-processor system or across a loosely clustered network of machines. Because each of the underlying physical structures can be accessed and manipulated independently, it is possible for each of them to be sent to a different CPU for processing before recombination through the compound structure.

Another advantage of this architecture is that compound structures act as high level indices into the underlying data, which in turn relieves some of the pressure on the indices inside the target structures and gives improved performance. In general, the better management of sparsity and more logical organization of the multi-dimensional storage possible with the invention leads to improved performance.

BRIEF DESCRIPTION OF THE DRAWINGS

For a better understanding of the invention, reference should be made to the following detailed description taken in conjunction with the accompanying drawings, in which:

FIG. 1 illustrates a single computer constructed in accordance with an embodiment of the invention.

FIG. 2 illustrates a client/server computer network constructed in accordance with an embodiment of the invention.

FIG. 3 illustrates a compound structure and associated backbone forming a "rack" in accordance with an-embodiment of the invention.

FIG. 4 illustrates a compound structure in accordance with an embodiment of the invention.

FIG. 5 illustrates the creation of a compound structure in the context of the architecture of FIG. 4.

FIG. 6 illustrates a "rack" and "stack" compound structure in accordance with an embodiment of the invention.

FIG. 7 illustrates the read/write functionality of a "rack" and "stack" compound structure of the invention.

FIG. 8 illustrates a tuple block in accordance with an embodiment of the invention.

FIG. 9 illustrates an alias descriptor in accordance with an embodiment of the invention.

FIG. 10 illustrates a vector of descriptors in accordance with an embodiment of the invention.

Like reference numerals refer to corresponding parts throughout the drawings.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1 illustrates a computer 20 constructed in accordance with an embodiment of the invention. The computer 20 includes a Central Processing Unit (CPU) 22 that communicates with a set of input/output devices 24 over a system bus 26. The input/output devices 24 include a keyboard, mouse, video monitor, printer, etc. The CPU 22 is also connected to a memory (primary and/or secondary) 28 via the bus 26. The interactions between CPUs 22, input/output devices 24, system buses 26, and memories 28 are known in the art. The present invention is directed toward the operation of these components in connection with a database 30 stored in memory 28 and a compound On-Line Analytical Processor (OLAP) 32 stored in memory 28. The database 30 is constructed and manipulated using the compound OLAP processor 32.

FIG. 2 illustrates a client/server computer network 40 constructed in accordance with an embodiment of the invention. The network 40 includes a client computer 42 that communicates with a server computer 44 over a network channel 46. The network 40 may include a large number of client computers 42 and server computers 44.

Each client computer 40 includes a CPU 50 and network interface circuit 52, which communicate over a system bus 54. The client computer 50 also includes a graphical user interface 56 stored in memory 58. As known in the art, the graphical user interface 56 runs in conjunction with the CPU 50 to allow a user to select queries and view results of the queries.

Each server computer 44 includes a network interface circuit 60 and a CPU 62 that communicate over a system bus 64. The server computer 44 also includes a memory 66, which stores the database 30 and the compound OLAP processor 32. Queries from the client computer 42 to the server computer 42 are processed by the OLAP processor 32 and database 30, with the results being passed back to the client computer 42.

Possible architectures in which the database 30 and compound OLAP processor 32 of the invention may operate have now been described. Attention presently turns to a discussion of the particular processing executed by the compound OLAP processor 32 of the invention.

The database 30 stores and the OLAP processor 32 manipulates novel data structures constructed in accordance with the invention. In particular, the invention utilizes a compound structure. A compound structure is a virtual unit of multi-dimensional storage which ultimately points to real data. The compound structure is implemented with a multi-structure alias. A multi-structure alias is a language element that defines the configuration of a compound structure and thereby causes it to be built. In the prior art, an alias is typically associated with a sub-set of information from a single source. The present invention establishes a multi-structure alias describing a set of target structures. In other words, a target structure of the invention is a hierarchical subset of a compound structure. A target structure may be a compound structure itself or a base structure. A base structure is a multi-dimensional storage unit that exists as physical data (e.g., data in RAM-based storage, or data in Disk-based storage).

The target descriptions may also include calculated values from the target structures. Each target structure can be specified and manipulated separately. Thus, the multi-structure alias used by the compound structure of the invention provides functionality that is analogous to prior art multi-cubes.

There are a number of benefits associated with the compound structure of the invention. First, there is no upper limit on the amount of data that can be manipulated and viewed in a single compound structure. As discussed below, a single compound structure may include a nesting of other compound structures.

Next, one can execute fully-parallel consolidations and calculations across multiple target structures. In addition, a brand new mechanism for multi-dimensional transaction control is supported. Compound structures enable unlimited data volumes to be addressed via a single structure object, while retaining the flexibility to populate, calculate, or consolidate the target structures independently, and possibly in parallel.

As discussed above, the invention produces a compound structure with a multi-structure alias. The compound structure includes a "rack" with a horizontal arrangement of target structures linked by an alias backbone representing a dimension of information. The compound structure may also include a "stack" with a vertical arrangement of racks linked by the alias backbone. The top level rack of the stack has read and write functionality, while the bottom level rack of the stack has read-only functionality.

Observe that the compound structure is based on several other structures. The compound structure contains no data itself, but points to parts of the target structures, which may be of different types. A single compound structure of the invention can contain all available data and calculated results. It is not feasible to implement such a structure at the physical level. That is, processor and memory limitations prohibit the required physical combination of all data associated with the compound structure. Therefore, the data of the invention is combined in a manner that is analogous to the use of "Joins" in a relational database. That is, the rack and stack features of the compound structure operate as a type of join operator as used in a relational database.

The invention does not limit the type of rack and stack configurations that may be used. Therefore, there is great flexibility in achieving tailored characteristics for a given application. For example, certain elements in a rack may be stored in primary storage (i.e., RAM-based memory), other elements may be stored in secondary storage (i.e., disk-based memory), and others may be stored in remote external databases, either relational or OLAP. This ability to combine different elements in different relationships is novel. Another novel feature of the invention is that a compound structure can contain other compound structures, repeated to any required depth.

The features and benefits of the invention are more fully appreciated with reference to some examples. FIG. 3 illustrates a compound structure 70 associated with a set of target structures 72A-72N via an alias backbone 74. The target structures 72A-72N associated with the alias backbone 74 constitute a rack 78.

The compound structure 70 of FIG. 3 includes a first dimension that is the alias backbone 74. Computer code syntax to implement the structure of FIG. 3 needs to account for each alias field on the alias backbone 74. A series of STRUCTURE sub-blocks having the following general form may be used:

[TOP] STRUCTURE structure_or_tuple [ON d1.field_list.vertline.BY NAME]

mappings for d2 to dn

END STRUCTURE

The ON clause provides an association by field position, within the given field list. The BY NAME clause (which is the default) provides an association by field name. The FOR keyword will be accepted as synonymous with ON. The implications of having a single backbone for the joining is that each target structure must have a number of dimensions greater than or equal to that in the parent alias, minus one. That is, ndim_target>=dim_alias-1 (in the absence of a REPEAT clause).

The structure_or_tuple clause must evaluate to a 0-D or 1-D tuple. As discussed below, a tuple is used by the compound OLAP processor as both a data-locator and a data-iterator. It provides a field specification for every dimension in the structure object. The structure_or_tuple clause may assess a scalar or a vector quantity. A structure name on its own is handled identically to a tuple in the form of struct_name{}. For instance:

        strl ON dl.fl                        !Same as strl { }
        struct{a1,b1,c1}  ON d1.f2           !0-D tuple
        struct{a1,b1:b10} FOR d1.f1:fl0      !1-D tuple

• Inventors
  Proctor, Anthony Charles;
• Assignee
  Crystal Decisions, Inc. (Palo Alto, CA)
• Published
  Dec-3-2002
• Current US Classes:
  707/10
  707/100
  707/102
  707/2
  707/3
• Application #
  894212
• International Classes
  G06F 017/30
• Field of Search
  707/102 707/100 707/2 707/3 707/10
• Examiner
  Homere; Jean R.
• Agent
  Cooley Godward LLP
• US Patent References:
  5905985
  5926818
  5926820
  5940818
  5943668
  5943677
  5978788
  5978796
  5983215
  5983232
  6003036
  6006216
  6073140
  6094651
  6122628
  6122636
  6205447