این پروپوزال در قالب فرمت word قابل ویرایش ، آماده پرینت و ارائه به عنوان پروژه پایانی میباشد
چکیده
تقاضای تحت رتبه بندی از کاربردی ترین تقاضا بر اساس نیاز کاربران می باشد، مهمترین مسئله در اجرای این تقاضاها در سیستم های توزیع شده، ارسال اطلاعات مورد نیاز تقاضا و بالطبع حداقل زمان اجرا می باشد، برای این منظور از روشهای بهینه سازی تقاضا تحت رتبه بندی استفاده می شود. در اجرای یک تقاضا، هزینه برترین عمل، عمل اتصال بین رابطه ها می باشد به همین دلیل در این تحقیق ابتدا اندازه مورد نیاز رابطه ها را بر اساس 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.
بهینه سازی تقاضا یکی از مسائل مهم در سیستمهای مدیریت پایگاه داده می باشد. در سالهای اخیر بهینه سازی تقاضا از جنبه های مختلفی مورد بررسی قرار گرفته است که به تفصیل در فصل ۲ بیان شده است. مقوله اي كه مورد بررسي قرار داديم بهينه سازي تقاضا تحت رتبه بندي مي باشد كه براي بدست آوردن K جواب بهتر در یک تقاضا است که K توسط تقاضا تعیین می شود.
پدیدار شدن برنامه های کاربردی که وابسته به تقاضاهای رتبه بندی هستند، پشتيباني كاراي تقاضاهای رتبه بندی را در سیستم های مدیریت پایگاه داده در دنیای واقعی طلب می کنند. پشتیبانی تقاضاهای رتبه بندی به سیستم های پایگاه داده توانایی پاسخ دادن کارا به تقاضاهای بازیابی اطلاعات را می دهد.
در سالهای اخیر، ترکیب مزایای سیستم های بازیابی اطلاعات و پایگاه داده یک هدف اصلی برای خیلی از محققان بوده است. سیستم های پایگاه داده، مدیریت داده را با جامعیت قوی و تضمين سازگاری فراهم می آورند. از طرف دیگر سیستم های بازیابی اطلاعات مکانیزم هایی برای بازیابی کارا و رتبه بندی فازی که برای کاربر مطلوب است، فراهم می نمایند.
موضوع مهم در اين زمينه تعيين اندازه مورد نياز ورودي ها در N رابطه براي پاسخگويي به تقاضاي تحت رتبه بندي مي باشد تا بدين وسيله بتوان K جواب بهتر مورد نظر را بدست آورد. درمجتمع سازي اطلاعات در مقياس بالا، انتخاب جوابهاي رتبه بندي K جواب بهتر ازچندين منبع خيلي حياتي مي باشد و در كمينه كردن هزينه انتقال نقش اساسي دارد. زيرا هر چه اندازه رابطه ها كوچكتر باشد، هزينه كمتري براي انتقال صرف مي گردد. علاوه براین انتخاب روش مناسب برای تعیین اندازه ورودی مورد نیاز رابطه ها تاثیر چشم گیری در هزینه کل پردازش دارد بر اساس این مزیت روشهای مختلفی برای بهینه سازی تحت رتبه بندی ارائه شده است که مهمترین آنها را در فصل ۲ مورد بررسی قرار دادیم. روشهای بیان شده در زمینه بهینه سازی تقاضا تحت رتبه بندی غالبا در مقوله سیستمهای شخصی بیان شده اند، در حالیکه کاربرد عملی این تقاضاها در سیستمهای تحت وب و توزیع شده می باشد. بر این اساس تصمیم گرفتیم این روشها را برای سیستم توزیع شده بسط دهیم.
بهینه سازی تقاضا یکی از مسائل مهم در سیستمهای مدیریت پایگاه داده می باشد. در سالهای اخیر بهینه سازی تقاضا از جنبه های مختلفی مورد بررسی قرار گرفته است که به تفصیل در فصل 2 بیان شده است. مقوله اي كه مورد بررسي قرار داديم بهينه سازي تقاضا تحت رتبه بندي مي باشد كه براي بدست آوردن Kجواب بهتر در یک تقاضا است که K توسط تقاضا تعیین می شود.
پدیدار شدن برنامه های کاربردی که وابسته به تقاضاهای رتبه بندی هستند، پشتيباني كاراي تقاضاهای رتبه بندی را در سیستم های مدیریت پایگاه داده در دنیای واقعی طلب می کنند. پشتیبانی تقاضاهای رتبه بندی به سیستم های پایگاه داده توانایی پاسخ دادن کارا به تقاضاهای بازیابی اطلاعات را می دهد.
در سالهای اخیر، ترکیب مزایای سیستم های بازیابی اطلاعات و پایگاه داده یک هدف اصلی برای خیلی از محققان بوده است. سیستم های پایگاه داده، مدیریت داده را با جامعیت قوی و تضمين سازگاری فراهم می آورند. از طرف دیگر سیستم های بازیابی اطلاعات مکانیزم هایی برای بازیابی کارا و رتبه بندی فازی که برای کاربر مطلوب است، فراهم می نمایند.
موضوع مهم در اين زمينه تعيين اندازه مورد نياز ورودي ها در N رابطه براي پاسخگويي به تقاضاي تحت رتبه بندي مي باشد تا بدين وسيله بتوان K جواب بهتر مورد نظر را بدست آورد. درمجتمع سازي اطلاعات در مقياس بالا، انتخاب جوابهاي رتبه بندي K جواب بهتر ازچندين منبع خيلي حياتي مي باشد و در كمينه كردن هزينه انتقال نقش اساسي دارد. زيرا هر چه اندازه رابطه ها كوچكتر باشد، هزينه كمتري براي انتقال صرف مي گردد. علاوه براین انتخاب روش مناسب برای تعیین اندازه ورودی مورد نیاز رابطه ها تاثیر چشم گیری در هزینه کل پردازش دارد بر اساس این مزیت روشهای مختلفی برای بهینه سازی تحت رتبه بندی ارائه شده است که مهمترین آنها را در فصل 2 مورد بررسی قرار دادیم. روشهای بیان شده در زمینه بهینه سازی تقاضا تحت رتبه بندی غالبا در مقوله سیستمهای شخصی بیان شده اند، در حالیکه کاربرد عملی این تقاضاها در سیستمهای تحت وب و توزیع شده می باشد. بر این اساس تصمیم گرفتیم این روشها را برای سیستم توزیع شده بسط دهیم.
1- تشریح مسئله
هنگامیکه یک تقاضا تحت رتبه بندی داریم که هدف بدست آوردن K جواب بهترمی باشد، در این حالت به تمامی رکورد های جدول نیاز نداریم، بر اساس مقدار K تعدادی از رکوردها در رابطه ها که امتیاز کمی دارند در نتیجه نهایی نقشی ندارند و بهتر است آنها هرس شوند و برای محاسبات و انتقال اطلاعات زمانی را برای این رکوردها تلف نکنیم. ابتدا تعریفی از یک تقاضای تحت رتبه بندی را در زیر بیان می کنیم.
در تقاضای تحت رتبه بندی، تقاضا بر روی M صفت A1، A2، ... ، AN و N رابطه به صورت R1، R2، ... ، RN تعریف می شود که هر Ai(i=1:M) متعلق به یک رابطه Rj (j=1:N) می باشد. هر یک از صفتها نسبت به نوع شان دارای دامنه خاصی می باشند. R1، R2، ... ، RN در M سیستم به صورت توزیع شده قرار دارند به صورتیکه هر رابطه به طور کامل بر روی یک سیستم قرار دارد. به عبارت دیگر عمل قسمت بندی بر روی رابطه ها را در پایگاه توزیع شده بین سیستمها را در این تحقیق نداریم.
با توجه به تقاضا یکسری از صفتهای این رابطه ها برای عمل پرتو بکار می روند که به عنوان صفتهایی می باشند که در رکوردهای حاصل مورد استفاده قرار می گیرند. یکسری از صفتهای این رابطه ها برای عمل انتخاب بکار می روند که در واقع شرط های منطقی هستند که بر روی رکوردهای رابطه ها اعمال می شوند و رکودهایی دارای این محدودیتها می باشند می توانند برای مراحل بعدی مورد استفاده قرار بگیرند. برخی از صفتها برای عمل اتصال مورد استفاده قرار می گیرد، هنگامیکه چند رابطه داریم برای اینکه عمل اتصال بین آنها را بر قرار کنیم، می بایست صفتهای اتصال را برای هر یک از روابط تعیین نماییم. اگر برای دو رابطه Ri و Rj صفتی برای اتصال وجود نداشته باشد، SQL به جای عمل اتصال، ضرب دکارتی را بین این دو رابطه انجام می دهد. در تقاضا ها ی تحت رتبه بندی بخشی برای رتبه بندی داریم که برخی از صفتهای رابطه ها به صورت یک عبارت رتبه بندی بیان می شود که به آن تابع رتبه بندی گفته می شود.
تابع رتبه بندی f به صورت ترکیبی از M' صفت تشکیل شده است که درآن M M' می باشد. فرضی که برای تابع رتبه بندی f داریم این است که تغییرات تابع رتبه بندی نسبت به کل رابطه ها یکنواخت باشد. البته در تابع رتبه بندی مورد نظر تغییرات تابع نسبت به هر رابطه می تواند غیر یکنواخت باشد علاوه براین در تقاضاها ی تحت رتبه بندی تعداد جوابهای مطلوب نیز تعیین می شود که همان K جواب بهتر می باشد. نمونه ای از یک تقاضای تحت رتبه بندی در مثال 1 بیان شده است.
مثال1: يك خانواده مايل به خريد خانه‌اي در نزديكي يك مدرسه مي‌باشد و هدف آنها كاهش هزينه‌هاي كلي‌شان مي‌باشد. يك تابع رتبه بندی ساده كه مجموع قيمت خانه و هزينه شهریه 5 سال مدرسه را برآورد می كند در نظر بگيريد. می بایست عمل جستجو در دو رابطه خانه و مدرسه در پايگاه داده، بر اساس تقاضای شکل 1-1 صورت گیرد.
SELECT *
FROM House, School
WHERE ( DISTANCE (House.Location , School.Location) < d)
ORDER BY ( House.Price + 5 * School.Tuition )
Top 10
شکل 1-1: تقاضای نمونه
رابطه های House و School می توانند در یک سیستم توزیع شده بر روی یک یا دو سیستم وجود داشته باشند. البته از هر رابطه فقط یک نمونه وجود دارد یعنی عمل تکرار نیز در سیستم مورد بررسی نداریم. در این تقاضا خانواده تنها حداكثر به 10 نتيجه بجاي همه نتايج ممكن احتیاج دارد که از بین این 10 نتیجه تصمیم گیری نماید و خانه مطلوب را انتخاب نماید. راه حل سنتی این است که ابتدا همه رابطه های مورد نیاز تقاضا در صورت عدم وجود به سیستم اجرا کننده تقاضا به طور کامل ارسال می شوند سپس عمل اتصال بر روي دو رابطه انجام می شود، کلیه جوابها محاسبه شده و در نهایت بر اساس تابع رتبه بندي جوابها مرتب شده و 10 تای اول انتخاب می شوند. در حالتیکه رابطه ها بزرگ و تعداد جوابها زیاد باشد، هزینه محاسبات و انتقال اطلاعات نسبتا زیاد می باشد. البته برای K های بزرگ روش سنتی هزینه محاسباتی کمتری نسبت به روشهایی که اندازه ورودی را تخمین می زنند، دارد اما در این حالت نیز مشکل هزینه انتقال اطلاعات نسبتا زیاد می باشد.
در این تحقیق به جای اینکه در ابتدا رابطه ها را به طور کامل به سیستم تقاضا کننده ارسال کنیم، ابتدا بهینه سازی محلی را بر روی رابطه ها اعمال می کنیم و آنها را بر اساس عبارتیکه صفتهای رتبه بندی آنها در تابع رتبه بندی دارند، مرتب می کنیم، سپس ورودی های مورد نیاز برای ورودی ها را برای بدست آوردن K جواب بهتر تعیین می نماییم، هزینه های انتقال را بررسی کرده و میزان اطلاعاتی از رابطه ها را می بایست منتقل شود به سیستمی با کمترین هزینه ارسال می نماییم، در نهایت بر روی رابطه های نهایی عمل اتصال را انجام داده و نتایج نهایی را بدست می آوریم یا در این حالت به جای عمل اتصال با الهام گرفتن از الگوریتمهای جستجوی آگاهانه، مسئله بهینه سازی را تبدیل به جستجوی آگاهانه کرده سپس توسط این رابطه های نهایی گراف را برای جستجو بر اساس صفتها و تابع رتبه بندی تشکیل داده و K جواب بهتر را بدست می آوریم.
2- چالشها
برخی مشکلات برای انجام این تحقیق شامل موارد زیر می باشند:
1- تعیین اندازه ورودی N رابطه بر اساس اندازه خروجی مورد نظر آنها: تا به حال روشهای ارائه شده الگوریتمی را برای N رابطه ارائه نداده اند فقط الگوریتمها برای تعیین اندازه ورودی دو رابطه می باشد.
2- اعمال الگوریتمی برای سیستم توزیع شده: روشهای بررسی شده برای بهینه سازی تقاضای تحت رتبه بندی، در سیستم های محلی هستند، بکار بردن الگوریتم در سیستم توزیع شده باعث می شود که یکسری محدودیتها را ماهیت سیستم توزیع شده بر روی الگوریتم تحمیل کند، در واقع پارامترهایی که در انتقال اطلاعات بین سیستمها موثرند بر روی روش پیشنهادی تاثیر می گذارند. کنترل ارسال و دریافت اطلاعات و نوع پروتکل نیز در الگوریتم کلی تاثیر گذارند.
3- برای تبدیل مسئله بهینه سازی تقاضا به جستجوی آگاهانه : در این حالت البته روشهای کارایی ارائه شده است که چالش اصلی در آنها ساختن شاخصها بر روی رابطه ها بر اساس عبارتی که صفتهای رتبه بندی آنها در تابع رتبه بندی دارند و در نهایت ایجاد گراف حاصل از تمامی شاخصها بر اساس تابع رتبه بندی و جستجو بر روی آن می باشد. در ایجاد گراف و جستجو بر روی آن می بایست شرایط جستجوی آگاهانه را در نظر گرفت.