نوع فایل: word
قابل ویرایش 110 صفحه
مقدمه:
بهینه سازی تقاضا یکی از مسائل مهم در سیستمهای مدیریت پایگاه داده می باشد. در سالهای اخیر بهینه سازی تقاضا از جنبه های مختلفی مورد بررسی قرار گرفته است که به تفصیل در فصل 2 بیان شده است. مقوله ای که مورد بررسی قرار دادیم بهینه سازی تقاضا تحت رتبه بندی می باشد که برای بدست آوردن Kجواب بهتر در یک تقاضا است که K توسط تقاضا تعیین می شود.
پدیدار شدن برنامه های کاربردی که وابسته به تقاضاهای رتبه بندی هستند، پشتیبانی کارای تقاضاهای رتبه بندی را در سیستم های مدیریت پایگاه داده در دنیای واقعی طلب می کنند. پشتیبانی تقاضاهای رتبه بندی به سیستم های پایگاه داده توانایی پاسخ دادن کارا به تقاضاهای بازیابی اطلاعات را می دهد.
در سالهای اخیر، ترکیب مزایای سیستم های بازیابی اطلاعات و پایگاه داده یک هدف اصلی برای خیلی از محققان بوده است. سیستم های پایگاه داده، مدیریت داده را با جامعیت قوی و تضمین سازگاری فراهم می آورند. از طرف دیگر سیستم های بازیابی اطلاعات مکانیزم هایی برای بازیابی کارا و رتبه بندی فازی که برای کاربر مطلوب است، فراهم می نمایند.
موضوع مهم در این زمینه تعیین اندازه مورد نیاز ورودی ها در N رابطه برای پاسخگویی به تقاضای تحت رتبه بندی می باشد تا بدین وسیله بتوان K جواب بهتر مورد نظر را بدست آورد. درمجتمع سازی اطلاعات در مقیاس بالا، انتخاب جوابهای رتبه بندی K جواب بهتر ازچندین منبع خیلی حیاتی می باشد و در کمینه کردن هزینه انتقال نقش اساسی دارد. زیرا هر چه اندازه رابطه ها کوچکتر باشد، هزینه کمتری برای انتقال صرف می گردد. علاوه براین انتخاب روش مناسب برای تعیین اندازه ورودی مورد نیاز رابطه ها تاثیر چشم گیری در هزینه کل پردازش دارد بر اساس این مزیت روشهای مختلفی برای بهینه سازی تحت رتبه بندی ارائه شده است که مهمترین آنها را در فصل 2 مورد بررسی قرار دادیم. روشهای بیان شده در زمینه بهینه سازی تقاضا تحت رتبه بندی غالبا در مقوله سیستمهای شخصی بیان شده اند، در حالیکه کاربرد عملی این تقاضاها در سیستمهای تحت وب و توزیع شده می باشد. بر این اساس تصمیم گرفتیم این روشها را برای سیستم توزیع شده بسط دهیم.
فهرست مطالب:
فصل اول: مقدمه
1: تشریح مسئله
2: چالشها
فصل دوم: مفاهیم اولیه و کار های پیشین
1: پردازش تقاضا
تجزیه تقاضا
بهینه سازی تقاضا
اجرای تقاضا
روشهای بهینه سازی تقاضا
تقاضای تحت رتبه بندی
کارهای پیشین
یک دستاورد مبتنی بر هرس کردن برای پشتیبانی اتصال تقاضاها یی با K جواب بهتر
4-1-1: مساله مورد بررسی
4-1-2: معماری کلی روش
بهینه سازی تقاضای تحت رتبه بندی
4-2-1: رتبه بندی تجمعی
4-2-2: عملگرهای تقاضای اتصال رتبه بندی
4-2-3: بهینه سازی تقاضا بر پایه هزینه
4-2-4: طرح شمارش با استفاده از برنامه نویسی پویا
4-2-5: توسعه فضای شمارشی
4-2-6: طرح های هرس
بهینه سازی تطبیقی تقاضا های تحت رتبه بندی در پایگاه داده های رابطه ای
4-3-1: اجرای تطبیقی تقاضای رتبه‌بندی
4-3-2: اصلاح و استفاده‌ی مجدد طرح‌های رتبه‌بندی
4-3-3: تغییر طرح بر اساس بهینه‌ساز:
4-3-4: شیوه طرح اکتشافی تغییر برای تاخیرهای غیرمنتظره
بهینه سازی تقاضای محدود شده بهK
4-4-1: استنتاج فضای وضعیت ایندکس
4-4-2: وضعیت هدف
4-4-3: الگوریتم *OPT
فصل سوم: روش پیشنهادی
1: بیان برخی از نقصهای کارهای پیشین
2: تجزیه کننده تقاضا
3: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز
3-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز مبتنی بر هرس کردن ورودی رابطه ها
3-1-1: ساختار کلی الگوریتم
3-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم متمرکز با الهام گرفتن از جستجوی آگاهانه
4: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده
4-1: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده مبتنی بر هرس کردن ورودی رابطه ها
4-2: بهینه سازی تقاضای تحت رتبه بندی در سیستم توزیع شده با الهام گرفتن از جستجوی آگاهانه
فصل چهارم: پیاده سازی و آزمایشها
1: پیاده سازی های انجام شده
2: پایگاه داده های نمونه
3: پارامترهای مورد نظر برای مقایسه روشها
4: آزمایشهای انجام شده
فصل پنجم: نتایج و پیشنهادها
1: نتایج
2: پیشنهادها
مراجع
فهرست اشکال:
فصل اول
شکل 1-1: تقاضای نمونه
فصل دوم
شکل2-1: مراحل پردازش تقاضا
شکل2-2: مقایسه کلی ساختار بهینه سازی تقاضا سنتی و تطبیقی
شکل2-3: ارزیابی هزینه I/O دو طرح مرتب سازی و اتصال رتبه بندی
شکل 2-4: مثالی از روش هرس کردن برای تقاضاها یی با K جواب بهتر
شکل 2-5: معماری کلی روش
شکل2-6: الگوریتم برای انتخاب K چند تایی بهتر
شکل 2-7: شمارش طرح تقاضای تحت رتبه بندی
شکل2-8: دو طرح شمارش
شکل2-9: نمایش دو طرحpold, pnew
شکل 2-10: الگوریتم جستجوی OPT*
فصل سوم
شکل 3-1: تعیین ورودی های مورد نیاز برای بدست آوردن K جواب بهتر در دو رابطه R2 , R1
شکل 3-2: انواع ساختار درخت اتصال
شکل3-3: درخت خطی
شکل 3-4: ساختار سلسله مراتبی بالا – پایین، تعیین اندازه ورودی رابطه ها
شکل 3-5: ایجاد شاخص
شکل3-6: جزئیات تابع Prepare_Input_Size
شکل3-7: جزئیات تابع Min_Item
شکل3-8: جزئیات رویه Prepare_Left_Deep_Tree
شکل3-9: جابجایی و انتخاب مقادیر بدست آمده در مرحله جاری برای استفاده مرحله بعدی
شکل3-10: زیر برنامه Swap_Item
شکل3-11: جزئیات تابع بهبود یافته Prepare_Input_Size
شکل3-12: جزئیات تابع بهبود یافته Min_Item
شکل3-13: جزئیات رویه بهبود یافته Prepare_Left_Deep_Tree
شکل3-14: زیر برنامه Compute_Bounds
شکل3-15: ساختار داخلی هر گره
شکل3-16: جزئیات تابع Create_Tree
شکل3-17: جزئیات زیر برنامه Create_Interleaving
شکل3-18: جزئیات زیر برنامه Assign_Tuples_To_Leaf
شکل3-19: جزئیات تابع Create_Gneral_Tree
شکل3-20: جزئیات زیربرنامه Create_Neighbors_in_Leafs
شکل3-21: جزئیات زیربرنامه Achieve_TOPK_Result
شکل3-22: طرح های پایگاه داده توزیع شده
شکل3-23: نحوه محاسبه تاخیر انتها به انتها
شکل 3-24: جزئیات زیربرنامه Recognize_Location_for_Relations
شکل 3-25: جزئیات زیربرنامه هایی برای انجام عملهای انتخاب، پرتو و مرتب سازی
شکل 3-26: جزئیات تابع Prepare_Input_Size1
شکل 3-27: جزئیات تابع Prepare_Input_size_In_Relation
شکل 3-28: جزئیات زیربرنامه Prepare_Input_size_In_Relations
شکل 3-29: جزئیات زیربرنامه Prepare_Input_sizeCommand
شکل 3-30: جزئیات زیربرنامه Prepare_Left_Deep_Tree
شکل 3-31: جزئیات ارسال اطلاعات اندازه ورودی و خروجی مورد نیاز رابطه ها به سیستمهای دیگر
شکل 3-32: جزئیات تابع Obtain_Transfer_cost
شکل 3-33: جزئیات زیربرنامه های Obtain_Transfer_cost_In_SystemsوObtain_Transfer_costCommand
شکل 3-34: جزئیات زیر برنامه Send_Structure_Local_Tables
شکل 3-35: جزئیات زیر برنامه Structure_Table_for_CreateCommand
شکل 3-36: جزئیات زیربرنامه Save_Relation_To_File شکل 3-37: جزئیات زیربرنامه Receive_Data
شکل 3-38: جزئیات زیربرنامه Get_FileCommand
شکل 3-39: کلیات زیربرنامه Select_TOPK
فصل چهارم
شکل 4-1: نمایی از سیستم طراحی شده
شکل 4-2: تنظیمات آدرس IP سیستم ها
شکل 4-3: جزئیات رابطه های پایگاه داده NGDB2
شکل 4-4: سه تقاضای نمونه از پایگاه داده سیستم تولیدکننده
شکل 4-5: هزینه زمانی اجرای تقاضای 1 در سیستم متمرکز
شکل 4-6: هزینه زمانی اجرای تقاضای 1 در سیستم توزیع شده
شکل 4-7: میزان اطلاعات ارسالی تقاضای 1 در سیستم توزیع شده
شکل 4-8: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای1
شکل 4-9: هزینه زمانی اجرای تقاضای 2 را در سیستم متمرکز
شکل 4-10: هزینه زمانی اجرای تقاضای 2 را در سیستم توزیع شده
شکل 4-11: میزان اطلاعات ارسالی تقاضای 2 در سیستم توزیع شده
شکل 4-12: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای2
شکل 4-13: هزینه زمانی اجرای تقاضای 3 را در سیستم متمرکز
شکل 4-14: هزینه زمانی اجرای تقاضای 3 را در سیستم توزیع شده
شکل 4-15: میزان اطلاعات ارسالی تقاضای 3 در سیستم توزیع شده
شکل 4-16: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای3
شکل 4-17: یک تقاضای نمونه از پایگاه داده NGDB2
شکل 4-18: هزینه زمانی اجرای تقاضای 4 را در سیستم متمرکز
شکل 4-19: هزینه زمانی اجرای تقاضای 4 را در سیستم توزیع شده
شکل 4-20: میزان اطلاعات ارسالی تقاضای 4 در سیستم توزیع شده
شکل 4-21: نسبت اندازه ورودی تعیین شده به اندازه ورودی مورد نیاز واقعی برای تقاضای4
منابع ومأخذ:
[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
, 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[ روحانی رانکوهی، سید محمد تقی، ”سیستم و ساختار فایلها“، چاپ دوازدهم
پروژه بهینه سازی تقاضا تحت رتبه بندی در سیستم های توزیع شده. doc
