US 7,467,127 B1Granted

View selection for a multidimensional database

AssigneeHyperion Solutions Corporation

InventorsJonathan M. Baccash, Igor Nazarenko, Uri Rodny, Ambuj Shatdal

Life of this patent

Estimating the term…

Loading patent…

Abstract

Selection of certain views of a multidimensional database to materialize may be accomplished using an efficient and effective solution. A set of all potential views may be stored in a structure. A path in the structure may then be traversed in an indicated direction through the structure, the path including two or more potential views and beginning at an indicated view. Then two or more immaterialized views in the path may be compared to each other to determine which immaterialized view is the optimum choice for maximizing benefit if selected to be materialized. Then the traversing and comparing may be continually iterated through, each iteration utilizing an indicated direction different than the last, each iteration also utilizing an indicated view set at the optimum choice determined by the last iteration, the iterating continuing until it converges on a single view. That single view may then be selected for materialization.

Claims51

Dependent claims

A method for selecting a view to be materialized for a multidimensional database, the method comprising:

(a) selecting a first node of a plurality of nodes of a multidimensional structure, each node of the plurality of nodes representing a potential view of the multidimensional database;
(b) performing, in multiple iterations, the steps of:
(1) based on a particular node, determining a particular path of nodes in a particular direction through the multidimensional structure, the particular path of nodes comprising the particular node;
(2) determining a materialization benefit for each of two or more non-materialized views represented by nodes in the particular path of nodes;
(3) selecting a new node in the particular path of nodes, the new node representing a non-materialized view of the two or more non-materialized views having a higher materialization benefit than any other of the two or more non-materialized views;
wherein, for a first iteration of steps (1)-(3), the particular node is a first node, the particular direction is a first direction, and the particular path of nodes is a first particular path of nodes;
wherein, for each iteration of one or more iterations of steps (1)-(3), each iteration being subsequent to the first iteration, the new node of an immediately preceding iteration becomes the particular node, a new direction becomes the particular direction, and a new path of nodes becomes the particular path of nodes;
wherein the new path of nodes is different from the particular path of nodes of the immediately preceding iteration, and the new direction is different from the particular direction of the immediately preceding iteration;
(c) determining that, over multiple iterations of steps (1)-(3), selection of the new node in step (3) has converged upon a single node;
and,
(d) in response to step (c), materializing a particular view represented by the single node.

8 more elements

A machine-readable storage medium for selecting a view to be materialized for a multidimensional database, tangibly embodying a set of instructions that, when executed by the machine, causes the machine to perform the steps of:

(a) selecting a first node of a plurality of nodes of a multidimensional structure, each node of the plurality of nodes representing a potential view of the multidimensional database;
(b) performing, in multiple iterations, the steps of:
(1) based on a particular node, determining a particular path of nodes in a particular direction through the multidimensional structure, the particular path of nodes comprising the particular node;
(2) determining a materialization benefit for each of two or more non-materialized views represented by nodes in the particular path of nodes;
(3) selecting a new node in the particular path of nodes, the new node representing a non-materialized view of the two or more non-materialized views having a higher materialization benefit than any other of the two or more non-materialized views;
wherein, for a first iteration of steps (1)-(3), the particular node is a first node, the particular direction is a first direction, and the particular path of nodes is a first particular path of nodes;
wherein, for each iteration of one or more iterations of steps (1)-(3), each iteration being subsequent to the first iteration, the new node of an immediately preceding iteration becomes the particular node, a new direction becomes the particular direction, and a new path of nodes as becomes the particular path of nodes;
wherein the new path of nodes is different from the particular path of nodes of the immediately preceding iteration, and the new direction is different from the particular direction of the immediately preceding iteration;
(c) determining that, over multiple iterations of steps (1)-(3), selection of the new node in step (3) has converged upon a single node;
and,
(d) in response to step (c), materializing a particular view represented by the single node.

8 more elements

An apparatus for selecting a view to be materialized for a multidimensional database, the apparatus including one or more processors coupled to a memory being configured to perform each of the following steps:

(a) selecting a first node of a plurality of nodes of a multidimensional structure, each node of the plurality of nodes representing a potential view of the multidimensional database;
(b) performing, in multiple iterations, the steps of:
(1) based on a particular node, determining a particular path of nodes in a particular direction through the multidimensional structure, the particular path of nodes comprising the particular node;
(2) determining a materialization benefit for each of two or more non-materialized views represented by nodes in the particular path of nodes;
(3) selecting a new node in the particular path of nodes, the new node representing a non-materialized view of the two or more non-materialized views having a higher materialization benefit than any other of the two or more non-materialized views;
wherein, for a first iteration of steps (1)-(3), the particular node is a first node, the particular direction is a first direction, and the particular path of nodes is a first particular path of nodes;
wherein, for each iteration of one or more iterations of steps (1)-(3), each iteration being subsequent to the first iteration, the new node of an immediately preceding iteration becomes the particular node, a new direction becomes the particular direction, and a new path of nodes as becomes the particular path of nodes;
wherein the new path of nodes is different from the particular path of nodes of the immediately preceding iteration, and the new direction is different from the particular direction of the immediately preceding iteration;
(c) determining that, over multiple iterations of steps (1)-(3), selection of the new node in step (3) has converged upon a single node;
and,
(d) in response to step (c), materializing a particular view represented by the single node.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/863,870Filed 7 Jun 2004 · us provisional application
Priority: 27 Feb 2004
Granted: 16 Dec 2008
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 16/283
Databases characterised by their database models, e.g. relational or object models: multi-dimensional databases or data warehouses, e.g. MOLAP or…
Y10S 707/99932
Database or file accessing: access augmentation or optimizing
G06F
Computing and data processing
Y10S
Technical subjects covered by former uspc cross-reference art collections [xracs] and digests