A view selection algorithm with performance guarantee

ABSTRACT

A view selection algorithm takes as input a fact table and computes a set of views to store in order to speed up queries. The performance of view selection algorithm is usually measured by three criteria: (1) the amount of memory to store the selected views, (2) the query response time and (3) the time complexity of this algorithm. The two first measurements deal with the output of the algorithm. No existing solutions give good trade-off between amount of memory and queries cost with a small time complexity. We propose in this paper an algorithm guaranteeing a constant approximation factor of queries response time with respect to the optimal solution. Moreover, the time complexity for a D-dimensional fact table is O (D * 2^D) corresponding to the fastest known algorithm. We provide an experimental comparison with two other well known algorithms showing that our approach also gives good performance in terms of memory.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Kamel Aouiche , Daniel Lemire, A comparison of five probabilistic view-size estimation techniques in OLAP, Proceedings of the ACM tenth international workshop on Data warehousing and OLAP, November 09-09, 2007, Lisbon, Portugal [doi>10.1145/1317331.1317335]
• 3: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 4: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 5: Karam Gouda , Mohammed J. Zaki, GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets, Data Mining and Knowledge Discovery, v.11 n.3, p.223-242, November 2005 [doi>10.1007/s10618-005-0002-x]
• 6: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 7: Dimitrios Gunopulos , Roni Khardon , Heikki Mannila , Sanjeev Saluja , Hannu Toivonen , Ram Sewak Sharma, Discovering all most specific sentences, ACM Transactions on Database Systems (TODS), v.28 n.2, p.140-174, June 2003 [doi>10.1145/777943.777945]
• 8: Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Index Selection for OLAP, Proceedings of the Thirteenth International Conference on Data Engineering, p.208-219, April 07-11, 1997
• 9: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 10: Howard Karloff , Milena Mihail, On the complexity of the view-selection problem, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-173, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303993]
• 11: Xiaolei Li , Jiawei Han , Hector Gonzalez, High-dimensional OLAP: a minimal cubing approach, Proceedings of the Thirtieth international conference on Very large data bases, p.528-539, August 31-September 03, 2004, Toronto, Canada
• 12: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281]
• 13: H. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules. In KDD Workshop, 1994.
• 14: K. Satoh and T. Uno. Enumerating maximal frequent sets using irredundant dualization. In Discovery Science conference proceedings, 2003.
• 15: Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton, Materialized View Selection for Multidimensional Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.488-499, August 24-27, 1998
• 16: Zohreh Asgharzadeh Talebi , Rada Chirkova , Yahya Fathi , Matthias Stallmann, Exact and inexact methods for selecting views and indexes for OLAP performance improvement, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353383]