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

1- اگر a كليد R باشد، پس ، لذا می باشد.

2- اگر B كليد S باشد، پس لذا می باشد.

داشتن برآورد انتخاب پذيري اتصال براي شرط هاي اتصال رخداده،‌به بهينه ساز پرس و جو امكان مي دهد تا اندازه فايل حاصله را بعد از عمليات اتصال برآورد كند، اندازه هاي دو فايل ورودي را با بهره گیری از فرمول ارائه داده مي گردد. اكنون مي توان توابع هزينه تقريبي نمونه را براي برآورد هزينه بعضي از الگاريتم هاي اتصال ارائه شده در بخش 3 . 2. 18 ارائه كرد. عملياتهاي اتصال بفرم زير هستند.

كه B,A ويژگيهاي حوزه سازگار S , R هستند. فرض كنيد كه R ، bR بلوك دارد و آن S، بلوك دارد:

J1 : اتصال حلقه تو در تو : فرض كنيد كه ما از R براي حلقه بيروني بهره گیری مي كنيم بعد تابع هزينه زير را براي برآورد تعداد دستيابي هاي بلوك براي اين متد، با فرض 3 بافر حافظه بدست مي آوريم. ما فرض مي كنيم كه فاكتور بلوكه كردن براي فايل حاصله ، bfr­RS می باشد،‌و آن انتخاب پذيري اتصال بدين قرار می باشد:

CJ1= bR+

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

J2 : اتصال حلقه تكي : اگر شاخصي براي ويژگي اتصال B از S با سطوح شاخص XB وجود داشته باشد، مي توان هر ثبت s در R را بازيابي كرد و بعد از شاخص براي بازيابي كل ثبت هاي تطبيق پذيري t از S بهره گیری كرد كه t[B]=[A] را برآورده مي سازد. هزينه به نوع شاخص بستگي دارد. براي شاخص ثانويه، جايي كه sB ،‌اصل انتخاب براي ويژگي اتصال B از S می باشد، فرمول زير بدست مي آيد:

براي شاخص خوشه اي سازي جايي كه SB اصل انتخاب B می باشد فرمول زير را داريم:

CJ2b=bR+

براي شاخص اوليه، فرمول زير بدست مي آيد:

CJ2c=bR+

اگر كليد hash براي يكي از دو ويژگي اتصال، B از S ، وجود داشته باشد فرمول زير بدست مي آيد:

CJ2d=bR+(

كه ميانگين تعداد دستيابي هاي بلوك براي بازيابي ثبت با در نظر داشتن مقدار كليدي hash آن می باشد.

J3: اتصال ادغام – مرتب كردن: اگر فايل ها قبلاً روي ويژگيهاي اتصال مرتب شده باشند، تابع هزينه براي اين متد بدين قرار می باشد:

CJ3a=bR+

اگر بايد فايل ها را مرتب كنيم، هزينه مرتب كردن بايد به آن اضافه گردد. مي توان هزينه مرتب كردن را توسط (2*b)+(2*b*log2b) براي فايل از b بلوك تقريب و تخمين زد. از اينرو تابع هزينه زير بدست مي آيد.

CJ3b=(2*bR*

مثال بكارگيري توابع هزينه : فرض كنيد كه فايل Employee توصيف شده در مثال بخش قبلي را داريم ، و فرض كنيد كه فايل Department در تصوير 5. 7 شامل 125 = rD ثبت ذخيره شده در 13= bD بلوك ديسك را داريم. عمليات اتصال زير را در نظر بگيريد:

(op6):

(op7):

فرض كنيد كه شاخص اوليه روي DNUMER از Department با سطح 1= xDnumber و شاخص ثانويه روي Mgrssn از Department با اصل انتخاب 1= SMgssn و سطوح 2= xmgrssn را داريم. فرض كنيد كه انتخاب پذيري براي op6 ، 125/1=Jsop6= (1/1Department) می باشد زیرا DNUMBER كليد Department می باشد. همچنين فرض كنيد كه فاكتور بلوكه كردن براي فايل اتصال حاصله 4= brfED ثبت در هر بلوك می باشد. مي توان هزينه را براي عمليات JOIN در OP6 با بهره گیری از متدهاي عملي J1 و J2 بقرار زير برآورد كرد:

1- بكارگيري متد J1 با Empuyee بعنوان حلقه بيروني:

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

CJ1=bE+

2- بكارگيري متد J1 با Department بعنوان حلقه بيروني

CJ1=bD+

3- بكارگيري متد J2 با Empleyee بعنوان حلقه بيروني:

CJ2c=bc+

4- بكارگيري متد J2 با Department بعنوان حلقه بيروني:

CJLa=bD+(

مورد 4 پايين ترين برآورد هزينه را دارد و انتخاب خواهد گردید. توجه كنيد كه 15 بافر حافظه براي اجراي     بجاي فقط دو تا در دسترس بوده اند، 13 تا از آنها براي حفظ كل ارتباط Department در حافظه بهره گیری گردید، و يكي بعنوان بافر روي نتيجه بهره گیری شده و هزينه براي مورد 2 ، به فقط bE+bD+((Jsop6 *rE*rD) / bfrED) يا 4SB كاهش يافته كه در بخش 3. 2 .18 بحث شده می باشد. بعنوان تمرين خواننده بايد ، تحليل مشابهي را براي op7 انجام دهد.

  1. 4. 18- پرس و جوهاي ارتباط متعدد (چندگانه) و مرتب كردن اتصال: قوانين تغيير شكل جبري در بخش 2 .3 .18 شامل قانون تبادلي و قانون پيوندي براي عمليات اتصال می باشد. با اين قوانين ، بسياري از عبارات اتصال معادل مي توانند ايجاد شوند. در نتيجه ، تعدادي درخت هاي پرس و جوي ديگري بسرعت رشد مي كنند تحت عنوان كه تعداد اتصالات در پرس و جو افزايش مي يابد. بطور كلي، پرس و جويي كه 8 ارتباط را متصل مي كند، N-1 ارتباط اتصال دارند. و از اينرو ، تعداد زياد ترتيب هاي اتصال متفاوت دارد.

تصوير 7. 18- دو درخت پرس و جوي كامل چپ

برآورد هزينه درخت اتصال ممكن براي پرس و جو با تعداد اتصالات زياد ، به ميزان اساسي زمان توسط بهينه ساز پرس و جو نياز دارد. از اينرو، مختصر كردن اين درختان پرس و جوي ممكن لازم مي باشد. بهينه سازيهاي پرس و جو، ساختار درخت پرس و جو را به آن درختان كامل چپ محدود مي سازند. درخت كامل چپ، درخت نيازي می باشد كه بچه راست هر گره بدون برگ هميشه ارتباط مبنا می باشد. بهينه ساز، درخت كامل چپ ويژه را با پايين ترين هزينه برآورد شده انتخاب مي كند. دو مثال از درختان كامل چپ در تصوير 7 .18 نشان داده شده می باشد. با درختان كامل چپ، بچه راست در ارتباط دروني در نظر گرفته مي گردد زماني كه اتصال حلقه تودرتو اجرا مي گردد. يك مزيت درختان كامل چپ (يا كامل راست) در اين می باشد كه آنها براي لوله اي كردن قابل اصلاح هستند، همانطوريكه در بخش 3. 3. 18 بحث گردید. براي مثال، اولين درخت كامل چپ در تصوير 7 .18 را در نظر بگيريد و فرض كنيد كه الگاريتم اتصال ، متد حلقه تكي می باشد، در اين مورد، صفحه ديسك tuple ها در ارتباط بيروني ، براي آزمايش ارتباط براي tuple (ثبت) تطبيق پذير بكار مي رود. همانطوريكه بلوك حاصله از tuple ها از اتصال R1 و R2 ايجاد مي گردد، آن براي آزمايش R3 بهره گیری مي گردد. همانطوريكه صفحه حاصله از tuple ها از اين اتصال ايجاد مي گردد، آن براي آزمايش R4 بهره گیری مي گردد. مزيت ديگر درختان كامل چپ در داشتن ارتباط مبنا بعنوان يكي از ورودي ها در هر اتصال می باشد كه به بهينه ساز امكان مي دهد تا از هر مسير دستيابي روي آن ارتباط بهره گیری كند كه ممكن می باشد در اجراي اتصال مفيد باشد.

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

6.4.18- مثالي براي نشان دادن بهينه سازي پرس و جو مبتني بر هزينه: ما پرس و جوي Q2 و درخت پرس و جوي آنرا در نظر مي گيريم كه در تصوير (a) 4. 18 براي نشان دادن بهينه سازي پرس و جوي هزينه اي ارائه شده می باشد.

تصوير 8. 18

Qz:SELECT

FROM

WHERE

a)

b)

c)

فرض كنيد كه اطلاعات آماري در مورد ارتباط هاي نشان داده شده در تصوير 8. 18 داريم. فرمت اطلاعات نمونه كاتالوگ در بخش c 17 را دنبال مي كند آمار Low-value – High- value براي روشن شدن نرمال سازي شده می باشد. درخت در تصوير (a) 4. 18 براي ارائه نتيجه مرحله بهينه سازي ذهني جبري و شروع بهينه سازي مبتني بر هزينه فرض مي گردد. اولين بهينه سازي مبتني بر هزينه براي درنظرگرفتن، مرتب كردن اتصال می باشد. همانطوريكه قبلاً به آن تصریح گردید، فرض مي كنيم بهينه ساز، فقط درختان كامل چپ را در نظر مي گيرد، لذا ترتيب هاي اتصال بالقوه، بدون محصول Cartesian بدين قرارند:

1- Project Department Emplyee

2-

3-

4-

فرض كنيد كه عمليات انتخاب براي ارتباط Project بكار رفته می باشد. روش تحقق پذيرفته شده، (مادي) را در نظر بگيريم، بعد ارتباط موقتي جديدي بعد از هر عمليات اتصال، ايجاد مي گردد. براي بررسي هزينه ترتيب اتصال (1) ، اولين اتصال بين Project, Department قرار دارد. هر دو متد اتصال و متدهاي دستيابي براي ارتباط هاي ورودي بايد مشخص شوند. زیرا Department هيچ شاخصي بر طبق تصوير 8. 18 ندارد، تنها متد دستيابي موجود، پويش جدولاست. ارتباط Project، عمليات انتخاب اجرا شده قبل از اتصال را دارد لذا دو انتخاب هست: پويش جدول يا بكارگيري شاخص Proj-Ploc آن، لذا بهينه ساز بايد هزينه هاي برآورد شده آنها را مقايسه كند. اطلاعات آماري روي شاخص Proj-Ploc تعداد سطوح شاخص x=2 را نشان مي دهد. شاخص غير منحصربفرد می باشد، لذا، بهينه ساز، توابع داده هاي يكنواخت را در نظر مي گيرد و تعداد تصریح گرهاي ثبت براي هر مقدار Plocation در 10 را برآورد مي كند. اين از جداول در تصوير 8. 18 با ضرب Selectivity * Num Rows محاسبه مي گردد، كه Selectivity توسط 1/Num-Distinct برآورد مي گردد. لذا هزينه كاربرد شاخص و دستيابي به ثبت ها تا 12 دستيابي برآورد مي گردد. هزينه پويش جدول تا 100 دستيابي بلوك برآورد مي گردد، لذا دستيابي شاخص در حد انتظار كارآمدتر می باشد.

در روش تحقق يافته، فايل موقتي Temp1 در اندازه 1 بلوك براي حفظ نتيجه عمليات انتخاب ايجاد مي گردد. اندازه فايل با تعيين فاكتور بلوكه كردن با بهره گیری از فرمول Num-Rows/ Blocks محاسبه مي گردد كه 2000/100 يا 20 رديف در هر بلوك را ارائه مي دهد. از اينرو 10 ثبت انتخاب شده از ارتباط Project در بلوك تكي تناسب خواهد يافت. اكنون مي توان هزينه برآورد شده اتصال اول را محاسبه كرد. ما فقط متد اتصال حلقه تو در تو را در نظر مي گيريم، كه ارتباط بيروني، فايل موقتي می باشد، Temp1 ، و ارتباط دروني Department می باشد. زیرا كل فايل temp1 در فضاي بافر موجود تناسب مي يابد، ما به خواندن هر يك از 5 بلوك جدول Department فقط براي يكبار نياز داريم، لذاهزينه اتصال 6 دستيابي بلوك بعلاوه هزينه نوشتن فايل نتيجه موقتي، Temp2 ، بهينه ساز بايد اندازه temp2 را مشخص كند. زیرا ويژگي اتصال Dnumber ، كليدي براي Department می باشد، هر مقدار DNUM از Temp1 مساوي با تعداد رديف ها در temp1 يعني 10 می باشد. بهينه ساز اندازه ثبت را بريا temp2 تعيين مي كند و تعداد بلوكهاي مورد نياز براي ذخيره اين 10 رديف را تعيين مي كند.

بطور اختصار ، فرض كنيد كه فاكتور بلوكه كردن براي Temp2 ، 5 رديف در هر بلوك می باشد، لذا كل دو بلوك براي ذخيره temp2 لازم مي باشند. بالاخره ، هزينه آخرين اتصال لازم می باشد برآورد گردد.

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

ما مي توانيم از اتصال حلقه تكي روي temp2 بهره گیری كنيم زیرا در اين مورد ، شاخص Emp-SSN مي تواند براي آزمايش و قرارگيري ثبت هاي برابري از employee بكار رود. از اينرو، متد اتصال شامل خواندن در هر بلوك temp2 و جستجو هر 5 مقدار mGRSSN با بهره گیری از شاخص EMP-SSN می باشد. هر جستجوي شاخصي به دستيابي ريشه، دستيابي برگها، و دستيابي بلوك داده ها نياز دارد. لذا ، 10 جستجو به 30 دستيابي بلوك نياز دارد. افزودن دو دستيابي بلوك براي temp2 ، كل 32 دستيابي بلوك براي اين اتصال را فراهم مي آورد. براي طرح نهايي، فرض كنيد لوله اي كردن براي ايجاد نتيجه نهايي بهره گیری مي گردد، كه به دستيابي هاي بلوك اضافي نيازي ندارد، لذا، كل هزينه براي ترتيب اتصال (1) بعنوان مجموع هزينه هاي قبلي برآورد مي گردد. بهينه ساز هزينه ها را در حالت مشابه براي 3 ترتيب اتصال ديگر برآورد مي كند و يكي را با حداقل برآورد انتخاب مي كند. ما اين را بعنوان تمرين براي خواننده ارائه مي دهيم.

  1. 18- مرور و بررسي بهينه سازي پرس و جو در ORACLE : ORACLE DBMS (نسخه 7 ) دو روش متفاوت را براي بهينه سازي پرس و جو ارائه مي كند. روش مبتني بر قانون و مبتني بر هزينه، با روش مبتني بر قانون ، بهينه ساز، طرح هاي اجرايي مبتني بر عمليات هاي طبقه بندي شده را انتخاب مي كند. ORACLE جدول 15 مسير دستيابي طبقه بندي شده (درجه بندي شده) را حفظ مي كند كه درجه بندي پايين تر دلالت بر روش كارآمدتر دارد. مسيرهاي دستيابي از دستيابي جدول تا RawID رديف مي گردد، جايي كه ROWID ، آدرس فيزيكي ثبت را تعيين مي كندتا شامل فايل داده ها ، بلوك داده ها و offset رديف در بلوك براي پوشش كامل جدول می باشد، كه كل رديف ها در جدول با خواندن چند بلوكي جستجو مي شوند. بهر حال ، روش مبتني بر قانون ، بواسطه روش مبتني بر هزينه مرحله بندي مي گردد كه بهينه ساز، مسيرهاي دستيابي ديگري و الگاريتم هاي عملگر را بررسي مي كند و طرح اجرايي را با حداقل هزينه برآورد شده انتخاب مي كند. جداول كاتالوگ شامل اطلاعات آماري درحالت مشابهي بهره گیری مي شوند، همانطوريكه در بخش 6. 4. 18 بحث شده می باشد. هزينه پرس و جوي برآورد شده به تناسب زمان (منقضي) سپري شدهمورد انتظار و مورد نياز براي اجراي پرس و جو با طرح اجرايي مورد نظر می باشد. بهينه ساز ORACLE اين هزينه را براساس كاربرد برآورد گردید، منابع مثل I/O ، زمان Cpu و حافظه مورد نياز ، محاسبه مي كند. هدف بهينه سازي مبتني بر هزينه ORACLE به حداقل رساندن زمان (منقضي) سپري شده براي پردازش كل پرس و جو می باشد.

افزودن جذابيت به بهينه ساز پرس و جوي ORACLE ، قابليت براي توسعه دهنده برنامه كاربردي جهت تعيين اشارهها براي بهينه ساز می باشد. ايده اين می باشد كه توسعه دهنده برنامه كاربردي،‌اطلاعات بيشتري در مورد داده ها نسبت به بهينه ساز دارد. براي مثال ، جدول Employee نشان داده شده در تصوير 5 .7 را در نظر بگيريد. ستون Sex آن جدول فقط دو مقدار متمايز دارد. اگر 10000 كارمند وجود داشته باشد، بعد بهينه ساز برآورد مي كند كه نيمي زن و نيمي مرد هستند، با فرض توزيع داده هاي يكنواخت. اگر شاخص ثانويه وجود داشته باشد، بيشتر از مورد بكار رفته نمي باشد. بهر حال ، اگر توسعه دهنده برنامه كاربردي بداند كه فقط 100 كارمند مرد هست تصریح در پرس و جوي SQL مشخص مي گردد و شرط بند WHERE آن Sex=M می باشد تا اينكه شاخص مربوط در پردازش پرس و جو بكار رود. تصریح هاي گوناگوني مشخص مي شوند كه بدين قرارند:

– روش بهينه سازي براي بيانيه SQL

– مسير دستيابي براي جدول دستيابي شده بيانيه

– ترتيب اتصال براي بيانيه اتصال

– عمليات اتصال ويژه در بيانيه اتصال

بهينه سازي مبتني برهزينه ORACLE8 ، مثال خوبي از روش مهم و برجسته در نظر گرفته شده براي بهينه سازي پرس و جوهاي SQL در RDBMS هاي بازرگاني می باشد.

  1. 18- بهينه سازي پرس و جوي معنايي: روش متفاوت براي بهينه سازي پرس و جو ، بنام بهينه سازي پرس و جوي معنايي، پيشنهاد شده می باشد. اين تكنيك كه ممكن می باشد درت ركيب با تكنيك هاي بحث شده قبلي بكار رود،‌از محدوديت هاي تعيين شده روي طرح پايگاه اطلاعاتي مثل ويژگيهاي منحصر بفرد و محدوديت هاي پيچيده تر ديگر، به مقصود تعديل يك پرس و جو به پرس و جوي ديگر كه براي اجرا كارآمدتر می باشد، بهره گیری مي كند. ما روي اين روش به تفضيل بحث نمي كنيم ولي فقط با مثال ساده اي آنرا روشن مي سازيم. پرس و جوي SQL را در نظر بگيريد.

SELECT

FROM

WHERE

اين پرس و جو ، اسامي كارمنداني را بازيابي مي كند كه بيشتر از ناظرين و سرپرستان خود عايدي بدست مي آورند. فرض مي گردد كه ما محدوديتي روي طرح پايگاه اطلاعاتي داشتيم كه بيان كرده كه هيچ كارمندي نمي تواند بيشتر از سرپرست خود عايدي بدست آورد. اگر بهينه ساز پرس و جوي معنايي موجوديت اين محدوديت را چك كند، به اجراي پرس و جو ابداً نيازي نمي باشد زیرا مي داند كه نتيجه پرس و جو خالي و تهي خواهد بود.

اين زمان قابل ملاحظه اي را صرف مي كند چنانچه كنترل محدوديت بطور كارآمدي بتواند انجام گردد. بهرحال، جستجواز طريق محدوديت هاي بسيار در يافتن آنهايي كه عملي هستند براي پرس و جوي ارائه شده و بهينه سازي مي شوند، مي تواند ضامن صرف زمان باشد. با در نظر داشتن قوانين فعال در سيستم هاي پايگاه اطلاعاتي، تكنيك هاي بهينه سازي پرس و جوي معنايي در DBMS هاي درآينده به ثبت مي رسند.

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

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