Method and system for performing partial-sum queries on a data c

Details Method and system for performing partial-sum queries on a data c Method and system for performing partial-sum queries on a data c

1997-05-09

1999-03-30

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

707 1, 707 2, 707 3, 707 4, 707 6, 707100, 707200, 707503, 707504, 354342, 3642821, 3642823, G06F 1730

Patent

active

058901515

ABSTRACT:
Disclosed is a method and system for performing a partial-sum query in a database in which the data is represented as a multi-dimensional data cube. The data cube is partitioned into multi-dimensional blocks. One or more covering codes are then selected for each block, and a group of partial-sums is computed for each block based on its covering codes. At query time, the query result is generated by combining the partial-sums for those blocks that intersect with the query subset. To improve the query response time and reduce system storage requirements, the covering codes are preferably augmented as single-weight extended covering codes or composition-extended covering codes. Also, a second partial-sum may also be computed for each block to efficiently find its partial sum, based on the block's first partial-sums and the bit-position differences between selected codewords for the block and bit strings representing the cell indexes of the blocks intersecting with the query subset.

REFERENCES:
patent: 5257365 (1993-10-01), Powers et al.
patent: 5359724 (1994-10-01), Earle
patent: 5404512 (1995-04-01), Powers et al.
patent: 5404513 (1995-04-01), Powers et al.
patent: 5799300 (1998-08-01), Agrawal et al.
patent: 5799311 (1998-08-01), Agrawal et al.
J. Srivastava et al., TBSAM: An access method for efficient processing of statistical queries. IEEE Transactions on Knowledge and Data Engineering, 1 (4), 1989.
P. M. Vaidya, Space-time tradeoffs for orthogonal range queries. In Proc. 17th Annual ACM Symp. on Theory of Comput., pp. 169-174, 1985.
A. Yao, On the complexity of maintaining partial sums. SIAM J. Computing, 14(2): 277-288, May 1985.
G. D. Cohen, et al., Covering radius 1985-1994. Appeared in Journal of Applicable Algebra in Engineering, Communication and Computing, special issue, 1996.
G. D. Cohen, et al. Further results on the covering radius of codes. IEEE Trans. Information Theory, IT-32(5):680-694, Sept. 1986.
R. L. Graham et al., On the covering radius of codes. IEEE Trans. Information Theory, IT-31(3):385-401, May 1985.
C. T. Ho et al., Range Queries in OLAP Data Cubes, IBM Research Report, To be presented at 1997 ACM SIGMOD Internation Conference on Management of Data, May 13, 1997-May 15, 1997 at Tucson, Az.
B. Chazelle et al., Computing partial sums in multidimensional arrays. In Proc. of the ACM Symp. on Computational Geometry, pp. 131-139, 1989.
S. Chaudhuri et al., Including group-by in query optimization. In Proc. of the 20th Int'l Conference on Very Large Databases, pp. 354-366, Santiago, Chile, Sep. 1994.
J. Gray et al., Data Cube: A relational aggregation operator generalizing group-by cross-tabs and sub-totals. In Proc. of the 12th Int'l Conference on Data Engineering, pp. 152-159, 1996. (also published as a Microsoft Technical Report, as submitted herewith.
A. Gupta et al., Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21st VLDB Conf. Zurich, Switzerland, 1995, pp. 358-369.
V. Harinarayan et al., Implementing data cubes efficiently. In Proc. of the ACM SIGMOD Conference on Management of Data, Jun. 1996.
S. Agarwal et al., On the computation of Multidimentional Aggregates. In Proc. of the 22nd Int'l Conference on Very Large Databases, pp. 506-521, Mumbai (Bombay), India, Sep. 1996.
E. F. Codd, Providing OLAP (on-line Analytical Processing) to user Analysis: An IT mandate. Technical report, E.F. Codd and Associates, 1993.
A. Shukla et al., Storage estimation for multidimensional aggregates in the presence of hierarchies. In Proc. of the 22nd Int'l Conference on Very Large Databases, pp. 522-531, Mumbai (Bombay), India, Sep. 1996.

Affiliated with

Also associated with

Rating

Method and system for performing partial-sum queries on a data c does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for performing partial-sum queries on a data c, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing partial-sum queries on a data c will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1225533