On the complexity of the view-selection problem
Published 1 May 1999Open access
Howard Karloff, Milena Mihail
Citations84
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The results prove (if P#NP) that the viewselection problem is essentially inapproximable for general partial orders, and studies of the Harinarayan, Rajaraman and Ullman framework and its generalizations should focus on special cases of practical significance, such as hypercubes, and on experimental comparison of heuristics.
Abstract
A commonly used and powerful technique for improving query response time over very large databases is to precompute ('Lmaterialize") frequently' asked queries ("views").
Keywords
Computer Science
ACM SIGACT NewsApproximation Algorithms for NP-Hard Problems
3,133 Citations1997Dorit S. Hochba
This book reviews the design techniques for approximation algorithms and the developments in this area since its inception about three decades ago and the "closeness" to optimum that is achievable in polynomial time.
Journal of the ACMA threshold of ln <i>n</i> for approximating set cover
3,122 Citations1998Uriel Feige
Implementing data cubes efficiently
1,166 Citations1996Venky Harinarayan, Anand Rajaraman +1 more
This paper investigates the issue of which cells (views) to materialize when it is too expensive to materialized all views, and presents greedy algorithms that work off this lattice and determine a good set of views to materializing.
Journal of the ACMOn the hardness of approximating minimization problems
890 Citations1994Carsten Lund, Mihalis Yannakakis
It is proved that there is an e > 0 such that Graph Coloring cannot be approximated with ratio n e unless P = NP, and Set Covering cannot be approximation with ratio c log n for any c < 1/4 unless NP is contained in DTIME(n poly log n).
Lecture notes in computer scienceSelection of views to materialize in a data warehouse
447 Citations1997Himanshu Gupta
Index selection for OLAP
425 Citations2002Himanshu Gupta, Venky Harinarayan +2 more
The authors give algorithms that automate the selection of summary tables and indexes, and present a family of algorithms of increasing time complexities, and prove strong performance bounds for them.
Lecture notes in computer scienceSelection of Views to Materialize Under a Maintenance Cost Constraint
216 Citations1999Himanshu Gupta, Inderpal Singh Mumick
This article develops algorithms to select a set of views to materialize in a data warehouse in order to minimize the total query response time under the constraint of a given total view maintenance time and designs an A* heuristic, that delivers an optimal solution.
A threshold of ln <i>n</i> for approximating set cover (preliminary version)
212 Citations1996Uriel Feige
It is proved that (1 - o(1) ln n setcover is a threshold below which setcover cannot be approximated efficiently, unless NP has slightlysuperpolynomial time algorithms.
Knowledge Discovery and Data MiningEfficient implementation of data cubes via materialized views
17 Citations1996Jeffrey D. Ullman
The work reported here is a summary of results appearing in the following two papers: V. Harinarayan, A. Rajaiaman, and J. D. Ullman, "Implementing data cubes efficiently," to appear in 1996 SIGMOD.