Büyük Çoklu Sorgu Eniyileme Problemlerinin Çözülmesi

Year 2009, Volume: 9 Issue: 1, 31 - 40, 01.06.2009

Ahmet Coşar

Abstract

Keywords

-

Büyük Çoklu Sorgu Eniyileme Problemlerinin Çözülmesi

Abstract

Bu çalışmada çoklu sorgu optimizasyonu (ÇSO) için varolan çağdaş ve eniyi optimal çözümler sunulmaktadır. Daha sonra ÇSO problemi için 16 yeni algoritma tasarlanmıştır. Bu önerilen algoritmalar kullanılarak rastgele üretilmiş ÇSO problemleri çözülmüştür. Her bir algoritma farklı 20 ÇSO problemi üzerinde çalıştırılmış ve bunların ortalaması o yöntemin performansı olarak hesaplanmış, ve aynı 20 problem üzerinde bütün algoritmalar çalıştırılarak ortalamaları bulunmuştur. Önerilen algoritmaları karşılaştırmak için ortalama maliyetlerine göre sıralanmış ve en iyi algoritma 1, en kötü algoritma 16 sıralaması verilmiştir. En küçük ortalama sıralamaya sahip olan algoritma en iyi algoritma olarak belirlenmiştir

Keywords

İlişkisel veritabanları, Çoklu sorgu optimizasyonu, A*

References

• T. Sellis. “Multiple query optimization,” ACM Transactions on Database Systems, 13(1), pp. 23- 52 (1988).
• K. Shim, T. Sellis, D. Nau. “Improvements on a heuristic algorithm for multiple-query optimization,” pp. 1-26 (1994).
• A. Cosar, J. Srivastava, S. Shekhar. “On the multiple pattern multiple object (mpmo) match problem,” Int. Conf. On Man. of Data, India (1991).
• F. Polat, A. Coşar, R.Alhajj. “Semantic information-based alternative plan generation for multiple query optimization,” Information Sciences, vol. 137, pp. 103-133 (2001).
• E.F. Codd, “Relational completeness of data base sublanguages,” in R.J. Rustin(ed.), Data Base Systems. Prentice-Hall (1972).
• U.S. Chakravarthy and A. Rosenthal. “Anatomy of a modular multiple query optimizer,” In Proc. Of the VLDB Conf., pp. 230-239 (1988).
• S. Chakravarthy, “Divide and conquer: A basis for augmenting a conventional query optimizer with multiple query-processing capabilities,” in Proc. 7th Int. Conf. Data Eng., Kobe, Japan, , pp. 482-490 (1991).
• A. Cosar. Design and experimental evaluation of a multiple query optimizer. PhD. Thesis, CS Dept, Univ. of Minnesota, Minneapolis (1996).
• P. Roy, S. Seshadri, S.Sudarshan, S. Bhobe. “Efficient and extensible algorithms for multi- query optimization,” SIGMOD Conference, pp. 249-260 (2000).
• H. Mistry, P. Roy, S. Sudarshan, K. Ramamritham. “Materialized view selection and maintenance using multi-query optimization,” SIGMOD Conference (2001).
• A.Y.Halevy. “Answering queries using views: A survey,” VLDB journal, vol.10(4), pp.270-294 (2001).
• C. Liu, A. Ursu. “A framework for global optimization of aggregate queries,” Conference on Information and Knowledge Management(CIKM), pp.262-269 (1997).
• U. Herzog, J. Schlosser, “Global optimization and parallelization of integrity constraint checks,” Int. Conf. on Man. of Data, pp.186-205 (1995).
• N Trigoni, Y. Yao, J. Gehrke, R. Rajaraman, and A. Demers. “Multi-query optimization for sensor networks, Multi-query optimization for sensor networks,” in DCOSS (2005).
• I.H. Toroslu, A Cosar. “Dynamic programming solution for multiple query optimization problem,” Information Processing Letters (2004).
• M.A. Bayir, I. H. Toroslu, and A. Cosar. “Genetic Algorithms for the multiple Query Optimization problem,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol 37, no.1 (2007).
• M. Astrahan et al., “System R: A relational approach to database management,” ACM Trans. Database Syst., vol. 1, no. 2, pp. 97–137 (1976).
• R. Elmasri, S.B. Navathe. Fundamentals of Database Systems, 3ed. (1999).
• J. Pearl. Heuristics. Reading, MA: Addison- Wesley (1984).