نکته مهم : برای بهره گیری از متن کامل پژوهش یا مقاله می توانید فایل ارجینال آن را از پایین صفحه دانلود کنید. سایت ما حاوی تعداد بسیار زیادی مقاله و پژوهش دانشگاهی در رشته های مختلف می باشد که می توانید آن ها را به رایگان دانلود کنید

با ارزيابي تحقق يافته ،‌نتيجه عمليات بعنوان ارتباط متوفي ذخيره مي گردد. براي مثال، عمليات اتصال مي تواند معاوضه گردد و كل نتيجه بعنوان ارتباط موقتي ذخيره گردد، كه بعد بعنوان ورودي توسط الگاريتمي خوانده مي گردد كه عمليات PROJECT را معاوضه مي كند كه جدول نتيجه پرس و جو را ايجاد مي كند. بعبارت ديگر، با ارزيابي لوله اي شده، همانطوريكه tuple هاي حاصله عمليات ايجاد مي شوند، آنها مستقيماً بسوي عمليات بعدي در توالي پرس و جو پيش مي طریقه. براي مثال، همانطوريكه tuple هاي انتخاب شده از DEPARTMENT توسط عمليات SELECT ايجاد مي شوند، آنها در بافر قرار مي گيرند، الگاريتم عمليات JOIN ، tuple ها را از بافر مصرف ميك ند، و آن tuple هايي كه از عمليات JOIN ناشي مي شوند در الگاريتم عمليات طرح لوله اي مي شوند. مزيت لوله اي كردن، هزينه مقرون بصرفه می باشد كه نتايج واسطه در ديسك و خواندن آنها در عقب براي عمليات بعدي را ندارد.

  1. 18- بكارگيري انتخاب پذيري و برآوردهاي هزينه در بهينه سازي پرس و جو: بهينه ساز پرس و جو نبايد به قوانين ذهني منحصراً وابسته باشد، آن بايد هزينه هاي اجراي پرس و جو را با بهره گیری از استراتژي هاي اجرايي برآورد و مقايسه كند و بايد ، استراتژي را با حداقل برآورد هزينه انتخاب كند. براي كار با اين روش، برآوردهاي هزينه درست لازم مي باشند، تا اينكه استراتژي هاي متفاوتي مقايسه شوند. علاوه بر آن، ما بايد تعداد استراتژي هاي اجرايي در نظر گرفته شده را محدود كنيم، در غير اينصورت، زمان زيادي صرف ايجاد برآوردهاي هزينه براي استراتژيهاي اجرايي ممكن خواهد گردید. از اينرو، اين روش براي پرس و جوهاي كامپايل شده مناسب تر می باشد، جايي كه بهينه سازي در زمان كامپايل انجام مي گردد و كد استراتژي اجرايي حاصله در زمان اجرا مستقيماً ذخيره و اجرا مي گردد. براي پرس و جوهاي تفسير شده، كه كل مرحله نشان داده شده در تصوير 1 .18 در زمان اجرا رخ مي دهد، بهينه سازي در مقياس كامل، زمان واكنش را كند مي كند. بهينه سازي ماهرانه تر براي پرس و جوهاي كامپايل شده تعيين مي گردد، در عوض، بهينه سازي با صرف زمان كمتر، در بهترين حالت براي پرس و جوهاي تفسير شده اقدام مي كند. ما اين روش را بهينه سازي پرس و جو مبتني بر هزينه مي ناميم و آن از تكنيك هاي بهينه سازي سنتي بهره گیری مي كند كه فضاي راه حل و جواب براي مسئله را براي راه حلي جستجو مي كند كه تابع هدفمند و واقعي (هزينه) را به حداقل مي رساند. توابع هزينه بكار رفته در بهينه سازي پرس و جو، برآوردها هستند و توابع هزينه دقيقي نيستند، لذا، بهينه سازي، استراتژي اجرايي پرس و جو را انتخاب مي كند كه مورد بهينه اي نمي باشد. در بخش 1 .4 .18 ما روي مؤلفه هاي هزينه اجرايي پرس و جو بحث مي كنيم، اين اطلاعات در كاتالوگ DBMS حفظ مي گردد. در بخش 3. 4. 18. ما روي مؤلفه هاي هزينه اجرايي پرس و جو بحث مي كنيم، اين اطلاعات در كاتالوگ DBMS حفظ مي گردد. در بخش 3 . 4. 18 ، مثالهايي از توابع هزينه براي عمليات SELECT را ارائه مي دهيم و در بخش 4 .4. 18 ، روي توابع هزينه براي عمليات هاي JOIN دو راهه بحث مي كنيم.

بخش 5. 4. 18 روي اتصالات چند راهي بحث مي كند و بخش 6. 4. 18 مثالي را ارائه مي دهد.

  1. 4. 18- مؤلفه هاي هزينه براي اجراي پرس و جو: هزينه اجراي پرس و جو شامل مؤلفه هاي زير می باشد:

1- هزينه دستيابي به ذخيره ثانويه : اين هزينه جستجو ، خواندن و نوشتن بلوكهاي داده هايي می باشد كه در ذخيره ثانويه روي ديسك باقي مي ماند. هزينه جستجوي ثبت ها در فايل به نوع ساختارهاي دستيابي روي فايل مثل مرتب كردن،‌hashing ، شاخص هاي اوليه يا ثانويه بستگي دارد. علاوه بر آن، عواملي مثل خواه بلوكهاي فايل روي سيلندر ديسك يكساني اختصاص مي يابند يا روي ديسك پخش مي شوند روي هزينه دستيابي اثر مي گذارد.

2- هزينه ذخيره : اين هزينه ذخيره هر نوع فايل واسطه اي می باشد كه با استراتژي اجرايي براي پرس و جو ايجاد مي گردد.

3- هزينه محاسباتي:‌اين هزينه اجراي عمليات ها در حافظه روي بافرهاي داده ها در طول اجراي پرس و جو مي باشد.

شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید                     

اين عمليات ها شامل جستجو و مرتب كردن ثبت ها ، ادغام ثبت ها براي اتصال، و اجراي محاسبات روي مقادير فيلد می باشد.

4- هزينه كاربرد حافظه : اين هزينه مربوط به تعداد بافرهاي حافظه مورد نياز در طول اجراي پرس و جو مي باشد.

5- هزينه ارتباطات : اين هزينه حمل پرس و جو و نتايج حاصله آن از محل پايگاه اطلاعاتي به سايت يا ترمينال می باشد جايي كه پرس و جو نشأت مي گيرد.

براي پايگاههاي اطلاعاتي بزرگ ، تأكيد اصلي روي به حداقل رساندن هزينه دستيابي به ذخيره ثانويه می باشد. توابع هزينه ساده، عوامل ديگر را ناديده مي گيرند و استراتژي هاي اجرايي پرس و جو متفاوت را در اصطلاحات تعداد انتقال هاي بلوك بين ديسك و حافظه اصلي مقايسه مي نمايند. براي پايگاههاي اطلاعاتي كوچكتر، جايي كه اكثر داروها در فايل هاي موجود در پرس و جو مي توانند كاملاً در حافظه ذخيره شوند، تأكيد روي به حداقل رساندن هزينه محاسباتي می باشد. در پايگاههاي اطلاعاتي توزيع شده، جايي كه بسياري از سايت ها شامل مي شوند، هزينه ارتباطات بايد به حداقل برسند. شامل شدن تمام مؤلفه هاي هزينه در تابع هزينه بعلت شكل جايگزيني اوزان مناسب در مؤلفه هاي هزينه، مشكل می باشد. بدين علت می باشد كه بعضي از توابع هزينه ، فقط عامل تكي، دستيابي ديسك را در نظر مي گيرند. در بخش بعدي روي بعضي از اطلاعاتي بحث مي كنيم كه براي تدوين توابع هزينه لازم مي باشد.

2 .4. 18- اطلاعات كاتالوگ بكار رفته در توابع هزينه:‌براي برآورد هزينه هاي استراتژيهاي گوناگون اجرايي، ما بايد مسير هر نوع اطلاعاتي را حفظ كنيم كه براي توابع هزينه لازم مي باشد. اين اطلاعات ممكن می باشد در كاتالوگ DBMS ذخيره شوند، جايي كه توسط بهينه ساز پرس و جو دستيابي مي گردد. اول اينكه، ما بايد اندازه هر فايل را بدانيم. براي فايلي كه ثبت هاي آن، همگي از نوع يكساني هستند، تعداد ثبت ها tuple) ها ) () ،‌اندازه ثبت (ميانگين ) (R) ،‌و تعداد بلوك ها (b) لازم مي باشند. فاكتور يا عامل بلوكه كردن (bf) براي فايل ممكن می باشد لازم باشد. ما بايد مسير متد دستيابي اوليه و ويژگيهاي دستيابي اوليه را براي هر فايل حفظ كنيم. ثبت هاي فايل ممكن می باشد مرتب نشوند يا توسط ويژگي با يا بدون شاخص خوشه اي سازي يا اوليه يا hash روي ويژگي كليدي مرتب شوند. اطلاعات روي تمام شاخص هاي ثانويه و ويژگيهاي شاخص دهي حفظ مي شوند. تعداد سطوح (x) هر شاخص چند سطحي، براي توابع هزينه اي نياز می باشد كه تعداد دستيابي هاي بلوك را برآورد مي كند كه در طول اجراي پرس و جو رخ مي دهد، در بعضي از توابع هزينه ، تعداد بلوكهاي شاخص يك سطحي (bI1) لازم مي باشد.

پارامتر مهم ديگر، تعداد مقادير متمايز (d) ويژگي و انتخاب پذيري آن (Sl) می باشد، كه كد ثبت هايي می باشد كه شرط تساوي روي ويژگي را برآورده مي سازد. اين به برآورد اصليت انتخاب (S=sl*r) ويژگي امكان اقدام مي دهد كه ميانگين تعداد ثبت هايي می باشد كه شرط انتخاب تساوي روي آن ويژگي را برآورده مي سازد. براي ويژگي كليدي ، S=1 , d=1 , SL=1/r می باشد. براي ويژگي غير كليدي، با ايجاد فرضيه اي كه مقادير متمايز d ، در ميان ثبت ها بطور يكنواختي توزيع مي شوند، ما SL=(1/d) را برآورد مي كنيم و لذا S=(r/d) می باشد. اطلاعاتي از قبيل تعداد سطوح شاخص براي حفظ آسان می باشد زیرا آن اغلب تغيير نمي كند. بهر حال ، اطلاعات ديگري ممكن می باشد مكرراً تغيير كند، براي مثال، تعداد ثبت ها r در فايل هر زمان كه ثبت درج يا پاك مي گردد، تغيير مي كند. بهينه ساز پرس و جو به بستن نياز دارد ولي ضرورتاً به مقادير بيش از دقيقه اين پارامترها براي بهره گیری در برآورد هزينه استراتژيهاي اجرايي گوناگون نياز نمي باشد.

در دو بخش بعدي، ما چگونگي بهره گیری اين پارامترها در توابع هزينه براي بهينه ساز پرس و جو مبتني بر هزينه را بررسي مي كنيم.

3 . 4. 18 – مثالهاي توابع هزينه براي SELECT : اكنون توابع هزينه را براي الگاريتم هاي انتخاب Sy تا S8 بحث شده در بخش 2 . 2. 18 در اصطلاحات تعداد انتقال هاي بلوك بين حافظه و ديسك ارائه مي دهيم. اين توابع هزينه، برآوردهايي هستند كه زمان محاسباتي، هزينه ذخيره، و عوامل ديگر را ناديده مي گيرند.

هزينه براي متد Si به دستيابي هاي بلوك CSi تصریح مي كند.

S1= روش جستجوي خطي (برنامه سازي پرقدرت) : ما تمام بلوكهاي فايل را براي بازيابي تمام ثبت ها در برآورده ساختن شرط انتخاب جستجو مي كنيم و Csta=b می باشد براي شرط تساوي روي كليد، تنها نيمي از بلوكهاي فايل در حد ميانگين جستجو مي شوند قبل از يافتن ثبت لذا CS1b=(b/2) چنانچه ثبت نظاره گردد، چنانچه هيچ ثبتي، شرط را برآورده نسازد، Cs1b=b می باشد.

S2 = جستجوي بنيادي:‌اين جستو تقريباً به بلوك فايل دستباي پيدا مي كند. اين به log2b كاهش مي يابد در صورتي كه شرط تساوي روي ويژگي منحصر بفرد (كليدي) قرار داشته باشد، زیرا در اين مورد s=1 می باشد.

S3 : بكارگيري شاخص اوليه (s3a) يا كليد (s3b) hash براي بازيابي ثبت تكي:‌براي شاخص اوليه ، يك بلوك بيشتر از تعداد سطوح شاخص بازيابي مي گردد از اينرو می باشد. براي hashing ، تابع هزينه تقريباً براي hashing استاتيك يا hashing خطي Cs3b=1 می باشد و آن براي hashing قابل توسعه 2 مي باشد.

S4 : بكارگيري شاخص مرتب كردن براي بازيابي ثبت هاي متعدد :‌اگر شرط قياس >=,> ، < يا = < روي فيلد كليدي با شاخص مرتب كردن باشد، نيمي از ثبت هاي فايل، شرط را برآورده مي سازند. اين تابع هزينه را ارائه مي دهد. اين برآورد سختي می باشد،‌گر چه در حد ميانگين درست می باشد، در موارد اختصاصي كاملاً نادرست می باشد.

شما می توانید تکه های دیگری از این مطلب را در شماره بندی انتهای صفحه بخوانید              

S5 = بكارگيري شاخص خوشه اي سازي براي بازيابي ثبت هاي متعدد : با در نظر داشتن شرط تساوي، S ثبت شرط را برآورده مي سازد، جايي كه s ، اصلي بودن انتخاب ويژگي شاخص دهي می باشد. بدين معني می باشد كه به [(s/bfr)] بلوك فايل دسترسي پيدا مي گردد و Cs5=x+[(s/bfr)] ارائه مي گردد.

S6 : بكارگيري شاخص ثانويه :‌روي قياس تساوي، s ثبت، شرط را برآورده مي كند، جاييكه s ، اصليت انتخاب ويژگي شاخص دهي می باشد. بهر حال ، زیرا شاخص،‌غير خوشه اي مي گردد، هر يك از ثبت ها روي بلوك متفاوتي باقي مي مانند،‌لذا برآورد هزينه (بدترين مورد) ، می باشد. اين تا x+1 براي ويژگي كليدي شاخص دهي كاهش مي يابد. اگر شرط قياس >=,> يا <= باشد و نيمي از ثبت هاي فايل براي برآورده ساختن شرط فرض گردد، بعد نيمي از بلوكهاي شاخص اوليه سطح بعلاوه نيمي از ثبت هاي فايل از طريق شاخص دستيابي مي شوند. برآورد هزينه براي اين مورد،‌تقريباً می باشد. فاكتور r/2 مي تواند اصلاح گردد چنانچه برآوردهاي انتخاب پذيري بهتري در دسترس باشند.

S7 = انتخاب تقارني (همبستگي ) : ما مي توانيم از s1 يا يكي از متدهاي S2 تا S6 فوق بهره گیری كنيم.

در مورد دومي ،‌از يك شرط براي بازيابي ثبت ها و بعد كنترل بافر حافظه بهره گیری مي كنيم كه آيا هر ثبت بازيابي شده، شرايط باقيمانده در ارتباط را برآورده مي سازد يا خير.

S8 = انتخاب تقارني (همبستگي) با بهره گیری ازشاخص مركب :‌در همان S3ap ، S5 يا S6a به نوع شاخص بستگي دارد.

مثال بكارگيري توابع هزينه: در بهينه ساز پرس و جو، شمارش استراتژي هاي ممكن گوناگون براي اجراي پرس و جو و برآورد هزينه براي استراتژيهاي مختلف متداول می باشد. تكنيك بهينه سازي،‌مثل برنامه نويسي پويا، براي يافتن برآورد هزينه بهينه (حداقل) بهره گیری مي گردد، بدون درنظرگرفتن تمام استراتژيهاي اجرايي ممكن.

ما روي الگاريتم هاي بهينه سازي در اينجا بحث نمي كنيم، ما از مثال ساده اي براي نشان دادن چگونگي بهره گیری از برآوردهاي هزينه ، بهره گیری مي كنيم. فرض كنيد كه فايل Employee در تصوير F.S ، rE=10000 ثبت ذخيره شده در bE=2000 بلوك ديسك با فاكتور بلوكه كردن bfrE=5 ثبت / بلوك دارد و مسيرهاي دستيابي بقرار زير مي باشد:

1- شاخص خوشه اي سازي روي SALARY ، با سطوح و ميانگين اصليت انتخاب می باشد.

2- شاخص ثانويه روي ويژگي كليدي SSN ، با می باشد.

3- شاخص ثانويه روي ويژگي غير كليدي DNO ، با و بلوكهاي شاخص سطح اول می باشد.

مقادير متمايز براي DNO هست،‌لذا اصليت انتخاب می باشد.

4- شاخص ثانويه روي SEX ، با می باشد. مقادير براي ويژگي sex (جنسيت) هست، لذا ميانگين اصلي انتخاب می باشد.

ما كاربرد توابع هزينه را با مثالهاي زير نشان مي دهيم:

(op1):

(op2):

(op3):

(op4):

هزينه انتخاب جستجوي خطي S1 بعنوان يا برآورد خواهد گردید. براي op1 ، مي توان از متد s1 يا متد S6a بهره گیری كرد، برآورد هزينه بريا Sba ، می باشد و روي متد S1 انتخاب مي گردد، كه هزينه ميانگين آن ، CS1b=1000 می باشد. براي op2 مي توان از متد s1 يا متد S6b بهره گیری كرد، لذا روش جستجوي خطي را براي op2 انتخاب مي كنيم.

براي op3 ، مي توان از متد s1 يا متد Sba بهره گیری كرد، لذا متد Sba را انتخاب مي كنيم.

بالاخره، op4 را در نظر بگيريد كه شرط انتخاب همبستگي (تقارني) دارد. ما به برآورد هزينه با كاربرد هر يك از 3 مؤلفه در شرط انتخاب براي بازيابي ثبت ها ، بعلاوه روش جستجوي خطي نياز داريم. دومي، برآورد هزينه Cs1a=2000 را ارائه مي دهد. بكارگيري شرط اول (DNO=5) ، برآورد هزينه Csba=82 را ارائه مي دهد. بكارگيري شرط اول SALARY>30,000 برآورد هزينه را ارائه مي دهد. بكارگيري شرط اول( (SEX=F برآورد هزينه را ارائه م يدهد. بهينه ساز، متد Sba را روي شاخص ثانويه روي DNO انتخاب مي كند زیرا پايين ترين برآورد هزينه را دارد. شرط (DNO=S) براي بازيابي ثبت ها بكار مي رود، و بخش باقيمانده شرط همبستگي (تقارني) براي هر ثبت انتخاب شده چك مي گردد بعد از اينكه در حافظه بازيابي مي گردد.


دیدگاهتان را بنویسید