Methods for fast progressive evaluation of polynomial range-sum queries on real-time datacubes
Provided are methods, computer programs and systems that optimize database queries using a wavelet transform of the query. Also provided are methods and systems for optimal disk placement for wavelet data.
1. A method for performing a range-sum query on a database of a database system, comprising:
processing at least one query using a wavelet transformation in a computing system of the database system to produce a transformed query, wherein the transformed query comprises k wavelet coefficients; and
the computing system performing a range-sum query on the database of the database system using the transformed query to produce a result.
2. The method of claim 1 , wherein the processing of the query using a wavelets algorithm comprises filtering the query using a plurality of filters to produce a summary query.
3. The method of claim 2 , wherein the summary query is processed using a wavelets algorithm and utilizing a plurality of filters to further refine the summary query to obtain a moment condition.
4. The method of claim 1 , wherein the transformed query comprises a hierarchical list in decreasing order of wavelet coefficients.
5. The method of claim 1 , wherein the database is a d-dimensional database.
6. The method of claim 5 , wherein the d-dimensional database is a data cube.
7. The method of claim 1 , wherein the wavelets algorithm is a modified Haar wavelet algorithm.
8. The method of claim 1 , wherein n wavelet coefficients from the transformed query are used in the range-sum query of the database.
9. The method of claim 8 , wherein n<k and the range-sum query is a progressive result.
10. The method of claim 8 , wherein n=k and the range-sum query is an exact result.
11. The method of claim 1 , wherein the at least one query comprises a plurality of queries.
12. The method of claim 11 , wherein each of the plurality of queries is processed to produce a plurality of transformed queries each comprising k wavelet coefficients.
13. The method of claim 12 , wherein the wavelet coefficients of each transformed query are compared to identify wavelet coefficients between the transformed queries that overlap and identifying the queries that overlap as important coefficients.
14. The method of claim 13 , wherein the wavelet coefficients of the plurality of transformed queries are ranked in a table from most important to least important based upon their values and upon their importance.
15. The method of claim 14 , wherein the range-sum query is performed by obtain a result for each wavelet coefficient in the table in descending order.
16. The method of claim 1 , implemented in accordance with a computer program stored on a computer readable data storage device.
17. A method for performing a range-sum query in a database of a database system, comprising:
a computing system of the database system receiving at least one query comprising at least one requested attribute;
the computing system processing the at least one query to obtain a summary comprising identifying a plurality of coefficients fitting the at least one desired attribute by filtering the query using one or more filters repeating the filtering until a moment condition is obtained whereupon obtaining the moment condition the query is a transformed query;
the computing system generating a transformed query table comprising a plurality of wavelet coefficients (k) comprising values in descending order;
the computing system performing a range-sum query in the database of the database system using wavelet coefficient (n) of the transformed query beginning with the largest, wherein the data in the database includes a plurality of attributes and are represented as a d-dimensional data cube having a plurality of cells, the dimensions of the data cube corresponding respectively to the attributes, each cell having an aggregate value of the corresponding data attribute values, the transformed query defining a subset of the dimensions of the data cube;
the computing system computing a plurality of range-sums based on the values corresponding to the data attributes in the subset; and
the computing system generating an exact range-sum result when n=k or an approximate or progressive result when n<k.
18. The method as recited in claim 17 , wherein the range-sum query corresponds to a d-dimensional region of the data cube.
19. An article of manufacture comprising:
a computer-readable data storage device; and
instructions on the computer-readable data storage device for directing a computer to:
process at least one query using a wavelets algorithm to obtain a transformed query, wherein the transformed query comprises k wavelet coefficients; and
perform a range-sum query on a database using the transformed query to produce a proximate, progressive, and/or exact result.
20. The article of manufacture of claim 19 , wherein the processing of the query using a wavelets algorithm comprises filtering the query using a plurality of filters to produce a summary query.
21. The article of manufacture of claim 20 , wherein the summary query is processed using a wavelets algorithm and utilizing a plurality of filters to further refine the summary query to obtain a moment condition.
22. The article of manufacture of claim 19 , wherein the transformed query comprises a hierarchical list in decreasing order of wavelet coefficients.
23. The article of manufacture of claim 19 , wherein the database is a d-dimensional database.
24. The article of manufacture of claim 23 , wherein the d-dimensional database is a data cube.
25. The article of manufacture of claim 19 , wherein the wavelets algorithm is a modified Haar wavelet algorithm.
26. The article of manufacture of claim 19 , wherein n wavelet coefficients from the transformed query are used in the range-sum query of the database.
27. The article of manufacture of claim 26 , wherein n<k and the range-sum query is a progressive result.
28. The article of manufacture of claim 26 , wherein n=k and the range-sum query is an exact result.
29. The article of manufacture of claim 19 , wherein each of the plurality of queries is processed to produce a plurality of transformed queries each comprising k wavelet coefficients.
30. The article of manufacture of claim 29 , wherein the wavelet coefficients of each transformed query are compared to identify wavelet coefficients between the transformed queries that overlap and identifying the queries that overlap as important coefficients.
31. The article of manufacture of claim 30 , wherein the wavelet coefficients of the plurality of transformed queries are ranked in a table from most important to least important based upon their values and upon their importance.
32. The article of manufacture of claim 31 , wherein the range-sum query is performed by obtaining a result for each wavelet coefficient in the table in descending order.
33. A computer program on computer readable data storage device for causing a computer to:
receive at least one query comprising at least one requested attribute;
process the at least one query to obtain a summary comprising identifying a plurality of coefficients fitting the at least one desired attribute by filtering the query using one or more filters repeating the filtering until a moment condition is obtained whereupon obtaining the moment condition the query is a transformed query;
generate a transformed query table comprising a plurality of wavelet coefficients (k) comprising values in descending order;
perform a range-sum query in a database using wavelet coefficient (n) of the transformed query beginning with the largest, wherein the data in the database includes a plurality of attributes and are represented as a d-dimensional data cube having a plurality of cells, the dimensions of the data cube corresponding respectively to the attributes, each cell having an aggregate value of the corresponding data attribute values, the transformed query defining a subset of the dimensions of the data cube;
compute a plurality of range-sums based on the values corresponding to the data attributes in the subset; and
generate an exact range-sum result when n=k or an approximate or progressive result when n<k.
34. A database system for performing a range-sum query in a database, the database system comprising:
a computer readable data storage device comprising instructions for causing a computer to:
process at least one query using a wavelets algorithm to obtain a transformed query, wherein the transformed query comprises k wavelet coefficients; and
perform a range-sum query on a database using the transformed query to produce a proximate, progressive, and/or exact result.
35. A database system for performing a range-sum query in a database, the database system comprising:
a computer readable data storage device comprising instructions for causing a computer to:
receive at least one query comprising at least one requested attribute;
process the at least one query to obtain a summary comprising identifying a plurality of coefficients fitting the at least one desired attribute by filtering the query using one or more filters repeating the filtering until a moment condition is obtained whereupon obtaining the moment condition the query is a transformed query;
generate a transformed query table comprising a plurality of wavelet coefficients (k) comprising values in descending order;
perform a range-sum query in a database using wavelet coefficient (n) of the transformed query beginning with the largest, wherein the data in the database includes a plurality of attributes and are represented as a d-dimensional data cube having a plurality of cells, the dimensions of the data cube corresponding respectively to the attributes, each cell having an aggregate value of the corresponding data attribute values, the transformed query defining a subset of the dimensions of the data cube;
compute a plurality of range-sums based on the values corresponding to the data attributes in the subset; and
generate an exact range-sum result when n=k or an approximate or progressive result when n<k.