CN103064923B - A kind of OLAP query spacing computational methods based on dimension hierarchy feature - Google Patents

Abstract

The present invention relates to data warehouse computer technical field, it is specifically related to a kind of method calculating OLAP query spacing by dimension hierarchy feature, the method is with two OLAP query passing through MDX (Multi DimensionalExpressions) language performance for input, obtain OLAP query the most respectively and relate to the cell in data cube, then the hierarchical structure of data cube is pressed, calculate two OLAP query corresponding unit lattice distance on different dimensions, the distance of computing unit compartment again, finally calculate the distance between two OLAP query, the spacing making calculating inquiry becomes the beeline calculated between two point sets, make tolerance more accurate, process to data warehouse is more efficient controlled；Nearest correlation map method is used to solve the shortcoming that Hausdorff distance is sensitive to noise and isolated point to a certain extent.

Description

A kind of OLAP query spacing computational methods based on dimension hierarchy feature

Technical field

The present invention relates to data warehouse computer technical field, be specifically related to one and pass through dimension hierarchy Architectural feature calculates the method for OLAP query spacing.

Background technology

Along with government, constantly integration and the enforcement of data warehouse of business event, based on data bins The Analysis of Policy Making in storehouse becomes and realizes the value-added common requirements of data value.OLAP supports analysis personnel With policymaker from multiple angles data warehouse data carried out quick, consistent, alternatively access.? The data how finding us to need in the data warehouse data of magnanimity are the most therefrom excavated Go out the hiding information that some we never understand and become an important research direction of data mining.? In this research direction, the similitude of the most energetic two OLAP query is a key, and Calculate OLAP query similitude and need OLAP query spacing computational methods.

Existing calculating OLAP query spacing method the most first uses classical Hamming distance from meter Calculate cell spacing from, then use Hausdorff distance calculate inquiry spacing, these methods Simply simple comparing unit lattice member value on different dimensions is the most equal, underuses data In warehouse, data have the feature of level.On same dimension, OLAP can pass through upper volume, under Boring the conversion that operation realizes between member value, Hamming distance is from only judging two member value whether phase Deng and do not consider the hierarchical relationship between two member value, therefore can not fully find member value in dimension Between similitude, and then can not fully find the similitude between two OLAP query.Calculating During inquiry spacing, Hausdorff distance is more sensitive to noise and isolated point, thus is easily caused Range error.

Summary of the invention

The present invention is to overcome above-mentioned weak point, it is therefore intended that provide a kind of new taking into full account In OLAP query, each dimension has the calculating of the OLAP query spacing of hierarchical structure feature Method.

The present invention is to reach above-mentioned purpose by the following technical programs:

A kind of OLAP query spacing computational methods based on dimension hierarchy feature, including with Lower step；

1) cube, dimension, cell and each number of cell set in definition data cube According to structure；

Definition 1 (cube) n ties up cube C=＜ D₁..., D_n, F ＞ may be defined as n+1 Dimension relation, wherein D_iRepresenting i-th dimension, F represents true table.

Definition 2 (dimension) dimension D=(H, ＜), H={h₁..., h_kIt it is the collection of level in this dimension Closing, ＜ is the linear order relation on H, i.e.Or h₂＜ h₁If, h₁＜ h₂, There is ALL ∈ H, forIf h_i≠ ALL, then h_i＜ ALL, i.e. ALL are dimension D In highest level, then claim h₁Less than h₂, dom (D) represents the set of all values in dimension D, Member value r is the value in dimension table, i.e. r ∈ dom (D), for highest level ALL, exist and Only exist a unique member and be worth all ∈ ALL.

The cube C of definition 3 (cells) given n dimension, cell is that a n dimension is first Group ＜ r₁..., r_n＞, for each i ∈ [1, n], has r_i∈dom(D_i)。

The given n of definition 4 (cell set) ties up cube C=＜ D₁..., D_n, F ＞ is right In i ∈ [1, n],N ties up cubical cell collection and is combined into R₁×…×R_n。

2) use MDX resolver that the OLAP query expressed with MDX statement is resolved, Obtain OLAP query and relate to the cell set in data cube；

MDX resolver completes to inquire the parsing of cell set, MDX resolver from MDX Workflow diagram include morphological analysis, syntactic analysis, semantic processes and acquiring unit lattice set four Individual step, introduces each step in turn below:

2.1) morphological analysis: MDX statement is from left to right scanned by lexical analyzer, by morphology Rule identifies word symbol, and produces the terminal symbol stream for syntactic analysis；Filter out MDX Annotation in statement and blank；The positional information of the MDX character string of record input, is used for When there is morphology or syntax error, error handling processing module can report that input MDX statement is wrong Particular location by mistake.

2.2) syntactic analysis: syntax analyzer reads in terminal symbol stream from lexical analyzer, and from terminal symbol Stream identifies all kinds of grammatical item, according to the MDX syntax of design, finds out MDX statement Structure thus detect the syntax error in MDX statement.If be detected that mistake, then adjust With makeing mistakes, module processes；If syntactically correct, then generated according to syntax analyzer The syntax tree of action sequence structure MDX statement and symbol table, it is provided that to semantic processes parts Use.

2.3) semantic processes: semantic processes is to check the correctness of grammer and confirm that statement is meaningful, language Justice analyzer reads in each symbol, creates node according to semantic rules, generates a semanteme Correct syntax tree.

2.4) acquiring unit lattice set: after MDX statement generative grammar tree, is also not enough to obtain dimension All information of member value on degree, by accessing metadata information, process function evaluation, Rear acquiring unit lattice set.

3) computing unit lattice beeline between member value on different dimensions:

Given dimension D and its hierarchical relationship H, x ∈ dom (D), y ∈ dom (D), x, y For two member value of dimension D, the distance between x and y is member value spacing, uses d_member(x, Y) representing, member value spacing is according to computational methods based on hierarchical structure: given dimension D and Its hierarchical relationship H, l_xAnd l_yFor two levels on H, member value x ∈ l_x, y ∈ l_y, they Nearest public ancestors use lca (x, y) represent, then lca (x, y) is expressed as:

Wherein z and z ' represents member value, l_zAnd l_z’For two levels on H,Represent x At l_zThe ancestors of level.

The spacing of member value x and y is represented by:

$d_{member}(x,y)=\frac{w_x\×\left|path(x,lca(x,y)\right)|+w_y\×|path(y,lca(x,y)\left)\right|}{(w_x+w_y)\×\left|path\right(ALL,L_1\left)\right|}---\left(2\right)$

Wherein lca (x, y) represent x and y nearest public ancestors, | path (x, lca (x, y)) | represent member X is to member value lca (x, shortest path length y), w for value_xRepresent | path (x, lca (x, y)) | weight, | path (y, lca (x, y)) | expression member value y to member value lca (x, shortest path length y), w_yTable Show | path (y, lca (x, y)) | weight, if hierarchical relationship H={L₁..., ALL}, and have L₁＜ ... ＜ ALL, | path (ALL, L₁) | lowest level L in representational level H₁In member value r Unique member in highest level ALL is worth the shortest path length of all.

What member value spacing calculated comprises the following steps:

3.1) dimension member value is obtained: two cells after MDX resolver resolves divide Wei r_i=＜ d_i1..., d_in＞ and r_j=＜ d_j1..., d_jn＞, can obtain its two for kth dimension Individual member value is d_ikAnd d_jk；

3.2) nearest public ancestors are found: all member value of identical dimensional form a multiway tree, Two member value d_ikAnd d_jkFor two nodes in multiway tree, for two nodes of multiway tree, Formula (1) is utilized to find their nearest public ancestors；

3.3) shortest path is calculated: obtaining two member value d_ikAnd d_jkNearest public ancestors it After, there is a shortest path in two member value and their nearest public ancestors, then distinguishes Calculate this two shortest paths；

3.4) spacing of member value is calculated: after obtaining two shortest paths, application formula (2) Two shortest paths are done weighted average and can obtain the spacing of member value.

4) distance between member value in each dimension is weighted averagely, calculate acquiring unit lattice it Between distance；

Given n ties up cube, two cell r_i=＜ d_i1..., d_in＞ and r_j=＜ d_j1..., d_jn＞, r_i, r_jThe spacing that spacing is cell, use d_cell(r_i, r_j) represent.Use weighted average method meter Calculate the spacing of cell, for cell r_i, r_j, weighted average distance formula is expressed as:

$d_{cell}(r_i,r_j)=\frac{{\mathrm{\Σ}}_{k=1}^n{w}_k{d}_{member}(d_{ik},d_{jk})}{{\mathrm{\Σ}}_{k=1}^n{w}_k}---\left(3\right)$

Wherein w_kRepresent dimension D_kWeight when the spacing of computing unit lattice, d_member(d_ik, d_ik) Represent the spacing of member value.

The flow process using the spacing of weighted average method computing unit lattice is as follows:

4.1) n member value spacing is obtained: given n ties up cube, two cell r_i=＜ d_i1..., d_in＞ and r_j=＜ d_j1..., d_jn＞, first obtains the distance between member value, i.e. profit in n dimension By step 3) obtain d_ikAnd d_jkSpacing；

4.2) weighted value of n dimension is obtained: different dimensions has different weights for calculating distance Want degree, give different weights to respectively n dimension according to the significance level of dimension；

4.3) computing unit compartment distance: obtaining spacing and their weight of n member value Afterwards, the distance that formula (3) is calculated between cell is utilized.

5) nearest correlation map method is used to be calculated OLAP query spacing

Two inquiry q on n dimension cube_i, q_j, their spacing is inquiry distance, uses d_query(q_i, q_j) represent, use nearest correlation map method to carry out inquiring about spacing and calculate.Nearest correlation map Main thought is by q_iIn each cell c_ikIt is mapped to q one by one_jIn cell c_jMake d_cell(c_ik, c_j) distance minimum, q_iTo q_jMapping distance d_mapping(q_i, q_j) it is represented by:

$d_{mapping}(q_i,q_j)=\frac{{\mathrm{\Σ}}_{k=1}^m\left(d_{cell}\right(C_{ik},C_j))}{m}\∀c_j|d_{cell}(c_{ik},c_j)=\min \{d_{cell}(c_{ik},c_j)\}---\left(4\right)$

Wherein m represents inquiry q_iIn the cell quantity that comprises.

In like manner can obtain d_mapping(q_j, q_i), then distance d between inquiry_query(q_i, q_j) can be with table It is shown as:

$d_{query}(q_i,q_j)=\frac{w_{ij}\×d_{mapping}(q_i,q_j)+w_{ji}\×d_{mapping}(q_j,q_i)}{(w_{ij}+w_{ji})}---\left(5\right)$

Wherein q_i, q_jRepresent two inquiries, w_ij, w_jiRepresent d respectively_mapping(q_i, q_j), d_mapping(q_j, q_i) weight.

It is as follows that nearest correlation map method carries out inquiring about spacing calculation flow chart:

5.1) acquiring unit lattice set: utilize the MDX resolver in step 1 will inquire about q_i, q_j Resolve to cell set；

5.2) q is calculated_iTo q_jMapping: calculate q_iIn each cell c_ikTo q_jIn each unit The distance of lattice, utilizes formula 4 to obtain q_iTo q_jMapping distance d_mapping(q_i, q_j)；

5.3) q is calculated_jTo q_iMapping: calculate q_jIn each cell c_jlTo q_iIn each unit The distance of lattice, utilizes formula 4 to obtain q_jTo q_iMapping distance d_mapping(q_j, q_i)；

5.4) inquiry spacing is calculated: obtaining d_mapping(q_i, q_j) and d_mapping(q_j, q_iAfter), root Being respectively them according to both significance levels and give different weighted values, recycling formula 5 obtains q_i, q_jThe spacing of inquiry.

The beneficial effects of the present invention is:

1) present invention is input by the OLAP query of MDX language performance, obtains the most respectively OLAP query relates to the cell in data cube, then presses the hierarchical structure of data cube, Calculate two OLAP query corresponding unit lattice distance on different dimensions between member value, then calculate The distance of unit compartment, finally calculates the distance between two OLAP query, makes between calculating inquiry Distance becomes the beeline calculated between two point sets, makes tolerance more accurate, to data bins The process in storehouse is more efficient controlled；

2) nearest correlation map method is used to solve Hausdorff distance to a certain extent to noise The shortcoming sensitive with isolated point.

Accompanying drawing explanation

Fig. 1 is system flow chart；

Fig. 2 is the Location dimension figure of MDX inquiry；

Fig. 3 is the Location dimension hierarchy figure of MDX inquiry；

Fig. 4 is inquiry spacing calculation flow chart；

Fig. 5 is inquiry analysis result schematic diagram；

Fig. 6 is inquiry mapping result schematic diagram.

Detailed description of the invention

Below in conjunction with being embodied as example, the present invention is described further, but the protection of the present invention Scope is not limited to that:

As it is shown in figure 1, a kind of OLAP query spacing based on dimension hierarchy feature calculates Method, comprises the following steps；

1) cube, dimension, cell and each number of cell set in definition data cube According to structure；

2) use MDX resolver that the OLAP query expressed with MDX statement is resolved, Obtain OLAP query and relate to the cell set in data cube.

Such as, a basic MDX inquiry is as follows:

Select{ [Measures]. [Unit Sales] } ON COLUMNS, Crossjoin ([Time]. [Year]. [1997], [Time]. [Year]. [1998] }, ([Location]. [Country]. [USA], [Product]. [Product Family]. [Drink]) }) ON ROWS from[Sales]。

This MDX inquiry can be resolvable to two cells ＜ 1997, USA, Drink ＞, ＜ 1998, USA, Drink ＞ }, wherein " 1997 ", " USA ", " Drink " represents the member in dimension Value, ＜ 1997, USA, Drink ＞ and ＜ 1998, USA, Drink ＞ represents cell.

3) computing unit lattice beeline between member value on different dimensions, such as Fig. 2, Fig. 3 Shown in, above-mentioned MDX inquiry Location dimension comprise four levels City, State Province, Country, ALL}, and have partial ordering relation City ＜ State Province ＜ Country ＜ ALL, The nearest ancestors of " CA " and " OR " are " USA ", and maximum layer time height is 3, then d_member(CA, OR)=(| path (CA, USA) |+| path (OR, USA) |)/(2 × | path (ALL, City) |)= (1+1)/(2 × 3)=1/3.

4) distance between member value in each dimension is weighted averagely, calculate acquiring unit lattice it Between distance

As above-mentioned two MDX inquiry resolve after comprise two cells ＜ 1997, USA, Drink ＞, ＜ 1998, USA, Drink ＞ }, ＜ 1997, USA, Drink ＞ and ＜ 1998, USA, Drink ＞, obtains d first with distance calculating method between member value_member(1997,1998)=1/3, d_member(USA, USA)=0, d_member(Drink, Drink)=0.Take the weighted average power of each dimension It is heavily 1/3, then the spacing of cell is d_cell(＜ 1997, USA, Drink ＞, ＜ 1998, USA, Drink ＞)=(1/3 × d_member(1997,1998)+1/3 × d_member(USA, USA)+1/3 × d_member(Drink, Drink))/(1/3+1/3+1/3)=1/9.

5) nearest correlation map method is used to be calculated OLAP query spacing

Inquiry spacing calculation flow chart as shown in Figure 4, inquires about q for two₁, q₂Resolve to cell As it is shown in figure 5, it is secondary highly as 3 to set Time dimension maximum layer, Location dimension maximum layer is second highest Degree is 3, and Product dimension maximum layer time height is 4, when computing unit lattice distance, and Mei Gewei The weighted average weight of degree is 1/3, can obtain d according to cell spacing from computational methods_cell(c₁, c₃)=7/36, d_cell(c₁, c₄)=5/18, d_cell(c₁, c₅)=13/36, d_cell(c₂, c₃)=2/9, d_cell(c₂, c₄)=1/6, d_cell(c₂, c₅)=1/4.Minimum distance maps as shown in Figure 6, d_mapping(q₁, q₂)=(d_cell(c₁, c₃)+d_cell(c₂, c₄))/2=13/72, d_mapping(q₂, q₁)=(d_cell(c₁, c₃)+d_cell(c₂, c₄)+d_cell(c₂, c₅))/3=11/54, then the spacing using nearest correlation map method to inquire about is d_query(q₁, q₂)=(d_mapping(q₁, q₂)+d_mapping(q₂, q₁))/2=83/432.

It is the specific embodiment of the present invention and the know-why used, Ruo Yiben described in Yi Shang The change that the conception of invention is made, function produced by it is still without departing from specification and accompanying drawing institute Contain spiritual time, protection scope of the present invention must be belonged to.

Claims (2)

1. OLAP query spacing computational methods based on dimension hierarchy feature, its feature comprises the following steps；

1) cube, dimension, cell and cell assembling individual data structure in definition data cube；

Define 1 n and tie up cube C=< D₁..., D_n, F > and may be defined as n+1 dimension relation, wherein D_iRepresenting i-th dimension, F represents dimension table；

Define 2 dimensions D=(H, ＜), H={h₁..., h_kIt is the set of level in this dimension, ＜ is the linear order relation on H, i.e.h₂∈H→h₁＜ h₂Or h₂＜ h₁If, h₁＜ h₂, there is ALL ∈ H, forIf h_i≠ ALL, then h_i＜ ALL, i.e. ALL are the highest level in dimension D, then claim h₁Less than h₂, dom (D) represents the set of all values in dimension D, and member value r is the value in dimension table, i.e. r ∈ dom (D), for highest level ALL, exists and only exists a unique member and be worth all ∈ ALL；

Definition 3 gives the cube C of a n dimension, and cell is that a n ties up tuple < r₁..., r_n>, for each i ∈ [1, n], there is r_i∈dom(D_i)；

Definition 4 gives a n and ties up cube C=< D₁..., D_n, F >, for i ∈ [1, n],N ties up cubical cell collection and is combined into R₁×...×R_n；

2) use MDX resolver that the OLAP query expressed with MDX statement is resolved, obtain OLAP query and relate to the cell set in data cube；

3) based on step 1) defined in hierarchical relationship computing unit lattice beeline between member value on different dimensions: given dimension D and its hierarchical relationship H, x ∈ dom (D), y ∈ dom (D), x, y is two member value of dimension D, distance between x and y is member value spacing, uses d_member(x, y) represents, member value spacing is according to computational methods based on hierarchical structure: given dimension D and its hierarchical relationship H, l_xAnd l_yFor two levels on H, member value x ∈ l_x, y ∈ l_y, their nearest public ancestors use lca (x, y) represent, then lca (x, y) is expressed as:

Wherein z and z ' represents member value, l_zAnd l_{z ’}For two levels on H, anc^lzX () represents that x is at l_zThe ancestors of level；

The spacing of member value x and y is represented by:

Wherein lca (x, y) represents the nearest public ancestors of x and y, | path (x, lca (x, y)) | represent that member value x is to member value lca (x, shortest path length y), w_xRepresent | path (x, lca (x, y)) | weight, | path (y, lca (x, y)) | represent that member value y is to member value lca (x, shortest path length y), w_yRepresent | path (y, lca (x, y)) | weight, if hierarchical relationship H=(L₁..., ALL}, and have L₁＜ ... ＜ ALL, | path (ALL, L₁) | lowest level L in representational level H₁In member value r be worth the shortest path length of all to the unique member in highest level ALL；Comprise the following steps:

3.1) dimension member value is obtained；

Two cells after MDX resolver resolves are respectively r_i=< d_i1..., d_in> and r_j=< d_j1..., d_jn>, two member value that can obtain it for kth dimension are d_ikAnd d_jk；

3.2) nearest public ancestors are found；

All member value of identical dimensional form a multiway tree, two member value d_ikAnd d_jkFor two nodes in multiway tree, for two nodes of multiway tree, formula (1) is utilized to find their nearest public ancestors；

3.3) shortest path is calculated；

Obtaining two member value d_ikAnd d_jkNearest public ancestors after, there is a shortest path in two member value and their nearest public ancestors, calculates this two shortest paths respectively；

3.4) shortest path is done weighted average and obtains the spacing of member value；

After obtaining two shortest paths, two shortest paths are done weighted average and can obtain the spacing of member value by application formula (2)；

4) distance between member value in each dimension is weighted averagely, calculates the distance between acquiring unit lattice；

5) nearest correlation map method is used to be calculated OLAP query spacing.

A kind of OLAP query spacing computational methods based on dimension hierarchy feature the most according to claim 1, it is characterized in that, step 2) described in the workflow of MDX resolver include morphological analysis, syntactic analysis, semantic processes and four steps of acquiring unit lattice set.