چکیده فارسی :

رایانش ابری سخت افزار یک سیستم پایگاه داده رابطه ای معمولی را قادر می سازد تا به صورت پویا بر اساس حجم کار پرس و جو، عملکرد و محدودیت های زمانی، تنظیم شود. در واقع می توان مقدار زیادی از منابع را برای یک مدت زمان کوتاه به منظور اجرای پرس و جو های پیچیده به صورت موثر بر روی داده های در مقیاس بزرگ با خوشه های ماشین مجازی، اجاره کرد. پرس و جو های پیچیده معمولا حاوی زیرعبارت های مشترک، در یک پرس و جوی واحد یا در میان چندین پرس و جو هستند که به عنوان یک دسته ارسال می شوند. زیرعبارت های مشترک روابط یکسانی را اسکن می کنند، کارهای مشابهی را محاسبه م کنند (الحاق کردن، مرتب کردن، و غیره)، و / یا داده های مشابهی را در میان رایانه های مجازی جابجا می کنند. زمان کلی صرف شده برای پرس و جو ها را می توان با اجرای این وظایف مشترک تنها یک بار کاهش داد. در این مطالعه، ما مجموعه طرح های اجرای پرس و جو را به منظور کاهش زمان اجرای کل ساخته و استفاده کرده ایم. این یک مسئله ی NP-سخت می باشد بنابراین، مجموعه ای از الگوریتم های ابتکاری مقاوم، Branch-and-Bound ، Genetic ، HillClimbing ، و Hybrid Genetic-Hill Climbing ، را برای پیدا کردن طرح های اجرای پرس و جوی بهینه و به حداکثر رساندن مزایا پیشنهاد داده شده اند. زمان بهینه سازی هر الگوریتم را برای شناسایی طرح های اجرای پرس و جو و کیفیت این طرح ها توسط آزمایش های گسترده مورد بررسی قرار گرفته است.

کلمات کلیدی: پایگاه داده ابر رابطه ای، بهینه سازی پرس و جوی چندگانه، محاسبات تکاملی، Branch-and-Bound، Hill Climbing

چکیده انگلیسی:

tCloud computing enables a conventional relational database system’s hardware to be adjusted dynami-cally according to query workload, performance and deadline constraints. One can rent a large amountof resources for a short duration in order to run complex queries efficiently on large-scale data with vir-tual machine clusters. Complex queries usually contain common subexpressions, either in a single queryor among multiple queries that are submitted as a batch. The common subexpressions scan the samerelations, compute the same tasks (join, sort, etc.), and/or ship the same data among virtual computers.The total time spent for the queries can be reduced by executing these common tasks only once. In thisstudy, we build and use efficient sets of query execution plans to reduce the total execution time. Thisis an NP-Hard problem therefore, a set of robust heuristic algorithms, Branch-and-Bound, Genetic, HillClimbing, and Hybrid Genetic-Hill Climbing, are proposed to find (near-) optimal query execution plansand maximize the benefits. The optimization time of each algorithm for identifying the query executionplans and the quality of these plans are analyzed by extensive experiments.

Keywords : Relational cloud database ; Multiple-query optimization ; Evolutionary computing ; Branch-and-Bound ; Hill Climbing