چکیده
تقاضای تحت رتبه بندی از کاربردی ترین تقاضا بر اساس نیاز کاربران می باشد، مهمترین مسئله در اجرای این تقاضاها در سیستم های توزیع شده، ارسال اطلاعات مورد نیاز تقاضا و بالطبع حداقل زمان اجرا می باشد، برای این منظور از روشهای بهینه سازی تقاضا تحت رتبه بندی استفاده می شود. در اجرای یک تقاضا، هزینه برترین عمل، عمل اتصال بین رابطه ها می باشد به همین دلیل در این تحقیق ابتدا اندازه مورد نیاز رابطه ها را بر اساس K جواب بهتر، به صورت ساسله مراتبی و طبق درخت چپ ژرف برای عمل اتصال تعیین می نماییم، سپس اطلاعات محدود شده را به سیستمی ارسال می کنیم که هزینه ارسال کمینه گردد و در سیستم مقصد اعمال نهایی برای بدست آوردن K جواب بهتر را بر اساس دو استراتژی پیاده سازی کردیم، در استراتژی اول، پس از دریافت اطلاعات مورد نیاز رابطه های محدود شده، عمل اتصال بین رابطه ها را بر اساس ترتیب تعیین شده انجام می دهیم و در نهایت K جواب بهتر را بدست می آوریم. در استراتژی دوم پس از دریافت اطلاعات مورد نیاز، مسئله بهینه سازی را به جستجوی آگاهانه تبدیل کرده و بر اساس ساختار درخت B+ ایجاد شده طبق رابطه های محدود شده، K جواب بهتر را بدست می آوریم. یک پایگاه داده واقعی در نظر گرفتیم و این دو روش را با روش سنتی بدون بهینه سازی و روش طبق جستجوی آگاهانه A* بیان شده در  [۳۱]مقایسه کردیم که براساس نتایج بدست آمده، به طور متوسط دو روش پیشنهادی زمانیکه میزان K در حدود ۲۰ درصد کل جوابها باشد دارای هزینه کمتری نسبت به روش سنتی و روش طبق جستجوی آگاهانه A* [31] می باشد، در ضمن بر اساس مقدار K، هزینه ارسال اطلاعات نیز از ۱۰ تا ۷۰ درصد کاهش یافته است.

چكيده
فصل اول مقدمه 1
1 تشریح مسئله 3
2 چالشها 5
فصل دوم مفاهیم اولیه و کار های پیشین6
1 پردازش تقاضا 7
تجزيه تقاضا7
بهينه سازي تقاضا 7
اجراي تقاضا 8
روشهاي بهينه سازي تقاضا9
تقاضاي تحت رتبه ‌بندي 11
کارهای پیشین 12
یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر 12
4-1-1 مساله مورد بررسی12
4-1-2 معماری کلی روش14
بهینه سازی تقاضای تحت رتبه بندی15
4-2-1 رتبه بندی تجمعی 16
4-2-2 عملگرهای تقاضای اتصال رتبه بندي 16
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
بهینه سازی تقاضای محدود شده بهK26
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
مراجع 94

فهرست شکلها
شکل 1-1 تقاضای نمونه 4
شكل2-1 مراحل پردازش تقاضا7
شكل2-2 مقایسه کلی ساختار بهينه سازي تقاضا سنتی و تطبيقی 10
شكل2-3 ارزیابی هزینه I/O دو طرح مرتب سازی و اتصال رتبه بندي 12
شکل 2-4 مثالی از روش هرس کردن برای تقاضاها یی با K جواب بهتر 13
شکل 2-5 معماری کلی روش 15
شکل2-6 الگوریتم برای انتخاب K چند تایی بهتر 15
شكل 2-7 شمارش طرح تقاضاي تحت رتبه بندي 19
شكل2-8 دو طرح شمارش 20
شكل2-9 نمايش دو طرحpold, pnew 24
شکل 2-10 الگوریتم جستجوی OPT* 31
شکل 3-1 تعیین ورودی های مورد نیاز برای بدست آوردن K جواب بهتر در دو رابطه R2 , R1 38
شکل 3-2 انواع ساختار درخت اتصال39
شکل3-3 درخت خطی 39
شکل 3-4 ساختار سلسله مراتبی بالا – پایین، تعیین اندازه ورودی رابطه ها 40
شکل 3-5 ایجاد شاخص41
شکل3-6 جزئیات تابع Prepare_Input_Size 42
شکل3-7 جزئیات تابع Min_Item 42
شکل3-8 جزئیات رویه Prepare_Left_Deep_Tree 43
شکل3-9 جابجایی و انتخاب مقادیر بدست آمده در مرحله جاری برای استفاده مرحله بعدی 45
شکل3-10 زیر برنامه Swap_Item 46
شکل3-11 جزئیات تابع بهبود یافته Prepare_Input_Size 46
شکل3-12 جزئیات تابع بهبود یافته Min_Item47
شکل3-13 جزئیات رویه بهبود یافته Prepare_Left_Deep_Tree 47
شکل3-14 زیر برنامه Compute_Bounds 50
شکل3-15 ساختار داخلی هر گره50
شکل3-16 جزئیات تابع Create_Tree 51
شکل3-17 جزئیات زیر برنامه Create_Interleaving52
شکل3-18 جزئیات زیر برنامه Assign_Tuples_To_Leaf 52
شکل3-19 جزئیات تابع Create_Gneral_Tree 53
شکل3-20 جزئیات زیربرنامه Create_Neighbors_in_Leafs 54
شکل3-21 جزئیات زیربرنامه Achieve_TOPK_Result56
شکل3-22 طرح های پايگاه داده توزيع شده 57
شکل3-23 نحوه محاسبه تاخیر انتها به انتها 58
شکل 3-24 جزئیات زیربرنامه Recognize_Location_for_Relations 60
شکل 3-25 جزئیات زیربرنامه هایی برای انجام عملهای انتخاب، پرتو و مرتب سازی62
شکل 3-26 جزئیات تابع Prepare_Input_Size1 64
شکل 3-27 جزئیات تابع Prepare_Input_size_In_Relation 65
شکل 3-28 جزئیات زیربرنامه Prepare_Input_size_In_Relations 65
شکل 3-29 جزئیات زیربرنامه Prepare_Input_sizeCommand 66
شکل 3-30 جزئیات زیربرنامه Prepare_Left_Deep_Tree67
شکل 3-31 جزئیات ارسال اطلاعات اندازه ورودی و خروجی مورد نیاز رابطه ها به سیستمهای دیگر 68
شکل 3-32 جزئیات تابع Obtain_Transfer_cost 68
شکل 3-33 جزئیات زیربرنامه های Obtain_Transfer_cost_In_SystemsوObtain_Transfer_costCommand 69
شکل 3-34 جزئیات زیر برنامه Send_Structure_Local_Tables 70
شکل 3-35 جزئیات زیر برنامه Structure_Table_for_CreateCommand 70
شکل 3-36 جزئیات زیربرنامه Save_Relation_To_File 71
شکل 3-37 جزئیات زیربرنامه Receive_Data71
شکل 3-38 جزئیات زیربرنامه Get_FileCommand 72
شکل 3-39 کلیات زیربرنامه Select_TOPK 72
شکل 4-1 نمایی از سیستم طراحی شده 77
شکل 4-2 تنظیمات آدرس IP سیستم ها77
شکل 4-3 جزئیات رابطه های پایگاه داده NGDB2 79
شکل 4-4 سه تقاضای نمونه از پایگاه داده سیستم تولیدکننده81
شکل 4-5 هزینه زمانی اجرای تقاضای 1 در سیستم متمرکز 82
شکل 4-6 هزینه زمانی اجرای تقاضای 1 در سیستم توزیع شده 83
شکل 4-7 میزان اطلاعات ارسالی تقاضای 1 در سیستم توزیع شده 83
شکل 4-8 نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای1 84
شکل 4-9 هزینه زمانی اجرای تقاضای 2 را در سیستم متمرکز 85
شکل 4-10 هزینه زمانی اجرای تقاضای 2 را در سیستم توزیع شده 85
شکل 4-11 میزان اطلاعات ارسالی تقاضای 2 در سیستم توزیع شده 86
شکل 4-12 نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای286
شکل 4-13 هزینه زمانی اجرای تقاضای 3 را در سیستم متمرکز 87
شکل 4-14 هزینه زمانی اجرای تقاضای 3 را در سیستم توزیع شده 87
شکل 4-15 میزان اطلاعات ارسالی تقاضای 3 در سیستم توزیع شده 88
شکل 4-16 نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای388
شکل 4-17 یک تقاضای نمونه از پایگاه داده NGDB2 89
شکل 4-18 هزینه زمانی اجرای تقاضای 4 را در سیستم متمرکز89
شکل 4-19 هزینه زمانی اجرای تقاضای 4 را در سیستم توزیع شده 90
شکل 4-20 میزان اطلاعات ارسالی تقاضای 4 در سیستم توزیع شده 90
شکل 4-21 نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای4 91

مراجع

[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.