Anish Das Sarma
Hector Garcia-Molina
Jennifer Widom
ABSTRACT
Given a database instance and a corresponding view instance, we address the view definitions problem (VDP): Find the most succinct and accurate view definition, when the view query is restricted to a specific family of queries. We study the tradeoffs among succintness, level of approximation, and the family of queries through algorithms and complexity results. For each family of queries, we address three variants of the VDP: (1) Does there exist an exact view definition, and if so find it. (2) Find the best view definition, i.e., one as close to the input view instance as possible, and as succinct as possible. (3) Find an approximate view definition that satisfies an input approximation threshold, and is as succinct as possible.
- R. Agrawal and R. Srikant. Fast algorithms for mining association rules. pages 487--499, 1994.Google Scholar
- Philip A. Bernstein. Applying model management to classical meta data problems. In CIDR, 2003.Google Scholar
- P. Bohannon, E. Elnahrawy, W. Fan, and M. Flaster. Putting context into schema matching. In VLDB '06. Google ScholarDigital Library
- Robert King Brayton, Alberto L. Sangiovanni-Vincentelli, Curtis T. McMullen, and Gary D. Hachtel. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984.Google ScholarCross Ref
- R. Carr, S. Doddi, G. Konjevod, and M. Marathe. On the red-blue set cover problem. In SODA '00, pages 345--353. Google ScholarDigital Library
- H. G-Molina, J. Widom, and J. D. Ullman. Database Systems: The Complete Book. Prentice-Hall, 2002.Google Scholar
- A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques, and applications. IEEE Data Engineering Bulletin, 18(2), 1995.Google Scholar
- L. Haas. The theory and practice of information integration. In Proc. of ICDT, 2007.Google Scholar
- A. Y. Halevy. Answering queries using views: A survey. VLDB Journal, 4, 2000. Google ScholarDigital Library
- E. J. McCluskey. Minimization of boolean functions. The Bell System Technical Journal, 1956.Google ScholarCross Ref
- P. Miettinen. On the positive--negative partial set cover problem. Inf. Process. Lett., 108(4):219--221, 2008. Google ScholarDigital Library
- T. M. Mitchell. Machine Learning. McGraw-Hill, 1997. Google ScholarDigital Library
- Pierre Senellart and Georg Gottlob. On the complexity of deriving schema mappings from database instances. In Proc. PODS, pages 23--32, Vancouver, Canada, June 2008. Google ScholarDigital Library
- P. N. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison-Wesley, 2006. Google ScholarDigital Library
- Q. T. Tran, C. Y. Chan, and S. Parthasarathy. Query by output. In Proc. of ACM SIGMOD, 2009. Google ScholarDigital Library
- C. Umans, T. Villa, and A. L. Sangiovanni-Vincentelli. Complexity of two-level logic minimization. IEEE Trans. on CAD of Integrated Circuits and Systems, 25(7):1230--1246, 2006. Google ScholarDigital Library
- Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In STOC '82. Google ScholarDigital Library
- V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001. Google ScholarDigital Library
Index Terms
- Synthesizing view definitions from data
Recommendations
GRASP with path relinking for the weighted MAXSAT problem
A GRASP with path relinking for finding good-quality solutions of the weighted maximum satisfiability problem (MAX-SAT) is described in this paper. GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multistart metaheuristic, where, ...
Processing queries on tree-structured data efficiently
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsThis is a survey of algorithms, complexity results, and general solution techniques for efficiently processing queries on tree-structured data. I focus on query languages that compute nodes or tuples of nodes—conjunctive queries, first-order queries, ...
Containment and Optimization of Object-Preserving Conjunctive Queries
In the optimization of queries in an object-oriented database (OODB) system, a natural first step is to use the typing constraints imposed by the schema to transform a query into an equivalent one that logically accesses a minimal set of objects. We ...
Comments