Simulation for Generate Efficient Evaluation Plans with Materialized Views

Abstract:

We study the problem of finding efficient equivalent view-based rewritings of relational queries, focusing on query optimization using materialized views under the assumption that base relations cannot contain duplicate tuples. We propose efficient algorithm SRGP for finding approximate optimal rewriting. Our results apply not only to query optimization, but to all areas where the goals is to obtain efficient equivalent view-based query rewritings. Experiments show that our algorithm of generating optimal rewriting has good efficiency and scalability.

• Periodical: Advanced Materials Research (Volume 748)
• Pages: 976-981
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.748.976
• Online since: August 2013
• Authors: Jia Chen, Hong Wei Chen, Xin Rong Hu
• Keywords: Equivalent Rewritings, Gp, Materialized Views

References

[1] A. Levy, A.O. Mendelzon, Y. Sagiv, D. Srivastava, Answering queries using views, in: PODS, 1995, p.95–104.

DOI: 10.1145/212433.220198

[2] R.J. Bayardo Jr., et al., Infosleuth: Semantic integration of information in open and dynamic environments (experience paper), in: SIGMOD, 1997, p.195–206.

[3] S.S. Chawathe, et al., The TSIMMIS project: Integration of heterogeneous information sources, in: IPSJ, 1994, p.7–18.

[4] L.M. Haas, D. Kossmann, E.L. Wimmers, J. Yang, Optimizing queries across diverse data sources, in: Proc. of VLDB, 1997, p.276–285.

[5] D. Theodoratos, T. Sellis, Data warehouse configuration, in: Proc. of VLDB, 1997, p.126–135.

[6] D. Florescu, A. Levy, D. Suciu, K. Yagoub, Optimization of run-time management of data intensive web-sites, in: Proc. of VLDB, 1999, p.627–638.

[7] S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim. Optimizing queries with materialized views. In Proc. ICDE, pages 190–200, (1995).

DOI: 10.1109/icde.1995.380392

[8] M. Zaharioudakis, R. Cochrane, G. Lapis, H. Pirahesh, and M. Urata. Answering complex SQL queries using automatic summary tables. In Proc. SIGMOD, pages 105–116, (2000).

DOI: 10.1145/335191.335390

[9] Goldstein J., Larson P.A. Optimizing queries using materialized views: a practical, scalable solution. In: Proc. of SIGMOD. p.331–342, (2001).

DOI: 10.1145/376284.375706

[10] F. Afrati, C. Li, and J.D. Ullman. Using views to generate efficient evaluation plans for queries. JCSS, 73 (2007) 703–724, (2007).

DOI: 10.1016/j.jcss.2006.10.019

[11] R. Pottinger and A.Y. Halevy. MiniCon: A scalable algorithm for answering queries using views. VLDB Journal, 10(2-3): 182–198, (2001).

DOI: 10.1007/s007780100048

[12] C. Beeri, M. Vardi, A proof procedure for data dependencies, J. ACM 31 (4) (1984) 718–741.

DOI: 10.1145/1634.1636

[12] A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proc. 9th ACM STOC, pages 77–90, (1977).

DOI: 10.1145/800105.803397

[13] Popa L., Deutsch A., Sahuguet A., Tannen V. A chase too far? In: SIGMOD, p.273–284, (2000).

DOI: 10.1145/335191.335421

[13] Koza J.R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press, (1992).

[14] G. Grahne, A.O. Mendelzon, Tableau techniques for querying information sources through global schemas, in: ICDT, 1999, p.332–347.

DOI: 10.1007/3-540-49257-7_21

[15] A. Levy, A. Rajaraman, J.J. Ordille, Querying heterogeneous information sources using source descriptions, in: Proc. of VLDB, 1996, p.251–262.

[16] F.N. Afrati, M. Gergatsoulis, T.G. Kavalieros, Answering queries using materialized views with disjunctions, in: ICDT, 1999, p.435–452.

DOI: 10.1007/3-540-49257-7_27

[17] R. Pottinger, A. Levy, A scalable algorithm for answering queries using views, in: Proc. of VLDB, 2000, p.182–198.

DOI: 10.1007/s007780100048

[18] A.Y. Halevy, Answering queries using views: A survey, VLDB J. 10 (4) (2001) 270–294.

DOI: 10.1007/s007780100054