پروژه بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده

فهرست و منابع پروژه بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده

فهرست:

فهرست مطالب                                                                                                  

فهرست شکلها                                                                                                       

فصل اول: مقدمه                                                                                                      

  1: تشریح مسئله                                                                                              

  2: چالشها                                                                                                                  

فصل دوم: مفاهیم اولیه و کار های پیشین                                                                       

  1: پردازش تقاضا                                                                                                    

: تجزیه تقاضا                                                                                                           

:  بهینه سازی تقاضا                                                                                                  

: اجرای تقاضا                                                                                                      

: روشهای بهینه سازی تقاضا                                                                                 

: تقاضای  تحت رتبه ‌بندی                                                                                

: کارهای پیشین                                                                                             

: یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر                 

    4-1-1: مساله مورد بررسی                                                                                                    

    4-1-2: معماری کلی روش                                                                                                   

: بهینه سازی تقاضای تحت رتبه بندی                                                                  

    4-2-1: رتبه بندی تجمعی                                                                                     

    4-2-2: عملگرهای تقاضای اتصال رتبه بندی                                                                               

    4-2-3: بهینه سازی تقاضا بر پایه هزینه                                                                                      17

    4-2-4: طرح شمارش با استفاده از برنامه نویسی پویا                                                                       17

    4-2-5: توسعه فضای شمارشی                                                                                                18

    4-2-6: طرح های هرس                                                                                                       19

: بهینه سازی تطبیقی تقاضا های تحت رتبه بندی در پایگاه داده های رابطه ای                            22

          4-3-1: اجرای تطبیقی تقاضای رتبه‌بندی                                                                                        23

              4-3-2: اصلاح و استفاده‌ی مجدد طرح‌های رتبه‌بندی                                                                   23  

              4-3-3: تغییر طرح بر اساس بهینه‌ساز:                                                                     25

              4-3-4: شیوه طرح اکتشافی تغییر برای تاخیرهای غیرمنتظره                                                  25

: بهینه سازی تقاضای محدود شده بهK                                                                            26

             4-4-1: استنتاج فضای وضعیت ایندکس                                                                                  28

             4-4-2: وضعیت  هدف                                                                                                     29

             4-4-3: الگوریتم *OPT                                                                                                     32

فصل سوم: روش پیشنهادی                                                                                     34

  1: بیان برخی از نقصهای کارهای پیشین                                                                      35

  2: تجزیه کننده تقاضا                                                                                         36

  3: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز                                                  37

  3-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز مبتنی بر هرس کردن ورودی رابطه ها                38

             3-1-1: ساختار کلی الگوریتم                                                                                                         40

   3-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز با الهام گرفتن از جستجوی آگاهانه              48

  4: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده                                              57

  4-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده مبتنی بر هرس کردن ورودی رابطه ها                 61

  4-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده با الهام گرفتن از جستجوی آگاهانه                  72

فصل چهارم: پیاده سازی و آزمایشها                                                                          74                                                                            

  1: پیاده سازی های انجام شده                                                                                75

  2: پایگاه داده های نمونه                                                                                      77

  3: پارامترهای مورد نظر برای مقایسه روشها                                                                 79

  4: آزمایشهای انجام شده                                                                                      80

فصل پنجم: نتایج و پیشنهادها                                                                                   91

  1: نتایج                                                                                                        92

  2: پیشنهادها                                                                                                           92

مراجع                                                                                                                   

منبع:

[1] Bennet, Kristin, “A Genetic Algorithm for Database Query Optimization”, Technical Report, University of Wisconsin,1997.

[2] Bernstein, P. A., N. Goodman, “Query Processing in a System for Distributed Database ”, ACM Transactions Database System, 6(4): 602-625, December 1981.

[3] Bitton, D., H. Boral, D. J. Dewitt, W. K. Wilkinson, “Parallel Algorithms for the Execution of Relational Database Operations”, ACM Transactions Database System, 8(3): 324-353, Sept. 1983.

[4] Chen, Zhiyuan, “Query Optimization in Compressed Database Systems”, In Proceedings of the ACM SIGMOD, May 2001.

[5] Connolly, Thomas, “Database Systems”, 3rd ed., Addison-Wesley, USA, 2002.

[6] Date, C.J., “An Introduction to Database Systems”, 7th ed., Addison-Wesley, USA, 2000.

[7] Graefe, G., D. Dewitt. “The EXODUS optimizer generator”, In Proceedings of the ACM SIGMOD Conference on Management of Data, 160-172, May 1987.

[8] Graefe, G., W. J. Mckenna, “The volcano optimizer generator: Extensibility and efficient search”, In Proceedings of the 9th International Conference on Data Engineering, 209-218, April 1993.

[9] Ilyas, I. F., W. G. Aref, A. K. Elmagarmid, H. G. Elmongui, R. Shah and J. S.Vitter, “Adaptive Rank-aware Query Optimization in Relational Databases”, ACM Transactions on Database Systems, 2006.

[10] Ilyas, I. F., R. Shah, W. G. Aref, J. S. Vitter, and A. K. Elmagarmid, “Rank-aware query optimization”, In Proceedings ACM SIGMOD International Conference on Management of Data, 203–214, 2004.

[11] Ilyas, I. F., W. G. Aref, A. K. Elmagarmid, “Supporting Top-k Join Queries in Relational Databases”, In Proceedings 29th International Conference on Very Large Data Bases, 754–765, 2003.

[12] Ilyas, I. F., C. Li, K. Chang and S. Song, “Ranksql: Query algebra and optimization for relational top-k queries”, In Proceedings ACM SIGMOD International Conference on Management of Data, 2005.

[13]Ioannidis, Y. E., Y. C. Kang, “Randomized algorithms for optimizing large join queries”, In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 312-321, May 1990.

[14] Jarke, Matthlas, Jijrgen Koch, “Query Optimization in Database Systems”, ACM Computing Surveys, 16(2), June 1984.

[15] Kossmann Donnald, Konrad Storcker, “Iterative Dynamic Programming: A New Class of Query Optimization Algorithms”, ACM Transactions on Database Systems, 25(1): 43–82, March 2000.

[16] Lanzelotte, R., P. Valduries, M Zait, “On the effectiveness of optimization search strategies for parallel execution spaces”, In Proceedings of the Conference on Very Large Data Bases, 493-504, Auguest 1993.

[17] Lee, S.G., “Identifying element constraints for semantic Query Optimization”, Information and Software Technology 42, 2000.

[18] Legaria, Galindo, C. Pellenkoft, A. Kersten, M. Fast, “randomized join-order selection why use transformations”, In Proceedings of the 20th International Conference on Very Large Data Bases, 85-95, September 1994.

[19] Liu, Jie, Liang Feng, and Yunpeng Xing, “A Pruning-based Approach for Supporting Top-K Join Queries”, ACM Transactions on Database Systems, Edinburgh, Scotland, May 2006.

[20] Ono, K., G. Lohman, “Measuring the complexity of join enumeration in query optimization”, In Proceedings of the 16th International Conference on Very Large DataBases, 314-325, August 1990.

[21] Palermo, F. P., “A data base search problem”, In Information Systems COINS IV, 67-101, 1974.

[22] Ramakrishnan, Raghu, “Database Management Systems”, WCB/Mc Graw Hill, Singapore, 1999.

[23] Selinger, P. G., M. M. Astrahan, R. A. Lorie, T. G. Price, “Access path selection in a relational database management system”, In Proceedings of the ACM SIGMOD International Conference on Management of Data, 23-34, May-June 1979.

 [24] Shekita, E., H. Young, K. Tan, “Multi-join optimization for symmetric multiprocessors”, In   

      Proceedings Conference on Very Large Data Bases, 479-492, Auguest 1993.

[25] Silberschatz, Henry F., “Database System Concepts”, 3th ed., WCB/Mc Graw Hill, USA, 1999.

[26] Sloan Jan, Christopher D. Henry, Melanie Hopkins and Steve Ludington, “National  

     Geochronological Database”, Geological Survey,1999.

[27] Steinbrunn, M., G. Moerkotte, A. Kemper, “Heuristic and randomized optimization for the join  

     ordering problem”, 191-208, Auguest 1997.

[28] Swami, A., “Optimization of large join queries: Combining heuristics and combinational  

     techniques", In Proceedings of the ACM Conference on Management of Data, 367-376, May 1989.

[29] Tanenbaum, Andrew S., Maarten VanSteen, “Distributed System principles and paradigms”, 2th

     ed., Prentice Hall,USA,  2002.

[30] Wang, Jiunn-Chin, Jorng-Tzong Horng, Yi-Ming Hsu, “A genetic algorithm for set query

     optimization in distributed database systems”, IEEE International Conference on Systems, Man,  

     and Cybernetics, 3: 14-17, October 1996.

[31] Zhang, Z., S.Hwang, K. ChenChuan, Ch.M. Wang, Ch. A. Lang, Y. Chang, “Boolean + Ranking:  

     Querying a Database by KConstrained Optimization”, In Proceedings of the ACM SIGMOD,

     Chicago, Illinois, USA, June 2006.

]32[ روحانی رانکوهی، سید محمد تقی، ”سیستمهای مدیریت پایگاه داده(مفاهیم و تکنیکها “، چاپ اول، انتشارات جلوه، تهران، 1383.

]33[ روحانی رانکوهی، سید محمد تقی، ”سیستم و ساختار فایلها“، چاپ دوازدهم، انتشارات جلوه، تهران، 1381.