پاورپوینت بهینه سازی پرسش

بخشی از پاورپوینت

اسلاید 1 :

بسم الله الرحمن ا لرحیم

اسلاید 2 :

فصل هفتم :
بهینه سازی پرسش

اسلاید 3 :

بهینه سازی پرسش : فعالیتی که طی آن یک استراتژی کارا برای اجرای پرسش تولیدی می شود.سیستمدر این مرحله ، از بین تعدادی طرح اجرا بهترین را بر می گزیند به گونه ای که اجرای پرسش کاربر ، کمترین هزینه، بویژه هزینه عملیات.I/o را داشته باشد.

به بیان دیگر، اگرS مجموعه استراتژیهای ممکن برای اجرای پرسش qباشد، هر عضو S مثلا s دارای یک هزینه (از نظر زمان cpu و زمان I/o )است . اگر این هزینه را با (s)C نمایش دهیم ، هدف هر استراتژی بهینه سازی یافتن عضوی از s مثلا s0 است به نحونی که
C(s0) = min c (s)
sєs

اسلاید 4 :

مراحل کلی پردازش پرسش :

اسلاید 5 :

تجزیه پرسش :
در این مرحله کارهای زیر انجام می شود:
1-تحلیل نحوی
2- نرمال سازی
3-تحلیل معنایی
4- ساده سازی
1-تحلیل نحوی :در این فاز با استفاده لز تکنیک های کامپایلری ، پرسش کاربر تحیلیل نحوی می شو. در این تحلیل ، وجود نام صفات و رابطه ها در شما ی پایگاه داده های وارسی می شود. بعلاوه در پایان این فز ، پرسش کاربر به یک فرم درونی مناسب برای پردازش تبدیل می شود.
درخت پرسشی این فرم به صورت زیر ساخته می شود :
• یک گره برگ برای هر رابطه مبنا در پرسش ،ایجاد می شود.
• یک گره نابرگ برای هر رابطه بینا بینی حاصل از اجرای هر عملگر سیر رابطه ای ایجاد می شود.
• ریشه درخت نمایشگر نتیجه اجرای پرسش است.
• قوای عملیات، از برگ ها به سوی ریشه است.

اسلاید 6 :

مثال : پرسش زیر را در نظر میگیریم : Q :مشخصات تمام درس های گروه آموزشی D111 در ترم اول سال تحصیلی 82-81 را بدهید.
این پرسش در SQL از جمله چنین نوشته می شود:

درخت پرسش به صورت زیر است:

به این درخت ، درخت جبر رابطه ای و گاه درخت پردازش هم گفته می شود.

اسلاید 7 :

2- نرمالتر سازی :در این فاز ، پرسش به یک فرم نرمال که اسانتر پردازش می شود در می آید.
می توان پرسش نوشته شده به SQL را به یکی از دو نرمال در آورد :
• فرم نرمال عطفی (CNF)
• فرم نرمال فصلی (DNF)

در فرم نرمال عطفی، اولویت به عمل AND داده می شود و گزاره موجود در کلاز ( فراکرد) WHERE به صورت CNF نوشته می شود.
در فرم نرمال فصلی اولویت به عمل OR داده می شود و گزارخ به صورت DNF نوشته می شود.
قواعد تبدیل یک عملگر AND و OR و NOT عبارتند از

اسلاید 8 :

در شکل DNF، می توان حکم رت به چند حکم فرعی با گزلره های جدا شده داراری ترکیب کلی فصلی تبدیل و جوابهای حاصل را با هم اجتماع کرد . ولی این کار سیر بروز JOIN و SELECT های تکراری می شود ، زیرا گزاره ها اکثرا با عملکرد AND بهم پیوند داده می شوند.
مثال :

اسلاید 9 :

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

برای تشخیص تناقص در پرسش ، می توان از روش رسم گراف اتصال نرمال شده صفات استفاده کرد.

اسلاید 10 :

4- ساده سازی : در این فاز ، شرایط افزونه در پرسش ، بازشناسی شده و زیر عبارات مشترک حذف می گردند در واقع در قسمت شرط SQLممکن است گزاره های هم ارزی وجود داشته باشند که کاری را بطور تکراری انجام برای منظور از قواعد زیر استفاده می شوند.

اسلاید 11 :

مثال )
گزاره های تبدیل شده در این حکم ، پس از ساده سازی ، تبدیل به یک گزاره می شود و حکم ساده شده چنین است SELECT COTITLE
FROM COT
WHERE CREDIT = “2”;

اسلاید 12 :

پیاده سازی عملیات جبر رابطه ای :
خواهیم دید که پیش نوشته شده به زبان سطح بالا ( مثلا SQL) به یک عبارت جبر رابطه ای تبدیل می شود . در چنین عبارتی تعدادی عملگیر جبر رابطه ای وجود دارد که باید اجرا شوند.
در استراتژیهای پیاده سازی عملگیر رابطه ای ، در اساس سه رده الگوریتم وجود دارد:

• الگوریتم های تک مرحله ای : سیستم داده ها را فقط یکبار از دیسک می خواند لازمه این کار وجود بافر کافی است.

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

• الگوریتم های چند مرحله ای : داده ها سه یا بیش از سه بار خوانده می شوند. در این الگوریتم ها محدودیتی برای حجم داده ها، مثلا کار دینالیتی رابطه ها وجود ندارد.

اسلاید 13 :

آمارهای پایگاهی :
بهینه ساز برای تصمیم گیری در مورد الگوریتم پیاده سازی هر عملکرد جبر رابطه ای و تولید طرح اجرای بهینه ، از مجموعه ای از اطلاعات آماری استفاده می کند.
معمولا آمارهای پایگاهی بطور متناوب و در زمانی که بار کار سیستم کم باشد بهنگام درمی آید.
البته معمولا این آمارها در زمان کامپایل جمع آوری می شوند و از این رو بهینه سازی حالت راستیا دارد.
درحالیکه این آمارها می توانند در فاصله بین زماناجرا تغییر کنند.
می توان بعضی پارامترهای تغییر کننده در زمان اچرا در ارزیابی طرحها دخالت داد و بدینسان ، بهینه سازی حالت پویا پیدا می کند.

اسلاید 14 :

تفاوت های دیگر حالت پویا و ایستا :
ایستا : اجرای پرسش بهینه سازی شده غالبا چندان بهینه نیست.
پویا : طح های تولید شده انسجام و ثبات بیشتری دارند و مجموع زمان I/₀ و زمان cpu دراین حالت بطور قابل ملاحظه ای از حالت ایستا کمتر است.

پارامترهایی از هر رابطه که باید در مورد آن ها آمارهای لازم در کاتالوگ سیستم نگهداری می شوند عبارتند از :
• تعداد تاپهای رابطه : n
• تعداد بلاک های حاوی تاپل های رابطه : b
• اندازه تاپل رابطه :T
• فاکتور بلاک بندی رابطه : Bf وداریم:
• تعداد مقادیر متمایز صفت A در رابطه : VA
•مشخص است این تعداد برابر است با کاردنیالیتی پرتو رابطه روی صفت A :

و اگر صفت A ، کلید باشد ، داریم : VA=n

اسلاید 15 :

میانگین کار دینالیتی رابطه روی صفت A با شرط تساوی داده شده باشد ، یعنی:

را با SA نشان می دهیم می توان چنین بر نهاد :

اگر صفت A کلید باشد داریم : SA=1

اسلاید 16 :

• مقدار مینیمم و مقدار ماکزیمم صفت A : Max (A) و Min (A)
• در خیلی از سیستم ها ، اطلاعاتی در مورد چگونگی توزیع داده ها در یک ستون ، معمولا با استفاده از هیستوگرام نگهداری می شود.
 
تابع هزینه اجرای یک پرسش شامل چندین فقره هزینه است از جمله :
• هزینه دستیابی • هزینه حافظه ای (حافظه جانبی)
•هزینه پردازش • هزینه حافظه اصلی ( تعداد با فرهای مورد نیاز حین اجرا)
• هزینه ارتباط ( بین یک مانه (سایت) و مانه دیگر یا یک پایانه با یک مانه)

اسلاید 17 :

پیاده سازی عمل گزینش :
بسته به ساختار فایلی که رابطه در آن ذخیره می شود و نیز شیوه دستیابی به رکوردهای فایل چندین استراتژی وجود دارد:
• جستجوی خطی
• جستجوی باینری
• جستجو با در همسازی و شرط مساوی
• جستجوی با شاخص روی کلید اصلی و شرط تساوی
• جستجو با شاخص روی کلید اصلی و شرط عدم تساوی
• جستجوی با شاخص خوشه ساز و شرط مساوی
• جستجو با شاخص خوشه ساز و شرط عدم تساوی
• جستجو با شاخص ثانوی B –Tree

اسلاید 18 :

پیاده سازی عمل پیوند:
برای پیاده سازی عمل پیوند ، استراتژی های زیر وجود دارد:
• پیوند از طریق حلقه های تو در تو
• پیونداز طریق حلقه های تو در تو بلاکی
• پیوند از طریق حلقه های تو در تو و با شاخص
• پیوند از طریق مرتب سازی – ادغام
•پیوند از طریق در همسازی
قبل از شرح هر یک از این استراتژی ها ، ببینیم چگونه می توان کاردینالیتی رابطه حاصل از پیوند دو رابطه را تخمین زد.

اسلاید 19 :

پیوند از طریق حلقه های تو در تو :
الگوریتم انجام عمل:

بر دو حلقه مبتنی است. در حلقه بیرونی، تاپلها رابطه R1 ،( رابطه بیرونی ) و در حلقه بیرونی ، تاپلهای رابطه R2 ( رابطه درونی )پیمایش می شوند. به ازا . هر تاپل از R1 ،چنانچه تاپل پیوند شدنی در R2 وجود داشته باشد، دو تاپل بهم پیوند شده ، تاپلی از R بدست می آید.
در این روش از اشخاص استفاده نمی شود و روشی است پر هزینه .
هزینه این عملیات بستگی به تعداد بافرها دارد:
در بدترین حالت اگر بافر فقط گنجایش یک بلاک را داشته باشد، تعداد دفعات دستیابی برابر است با:

در بهترین حالت، اگر هر دو رابطه به تمامی در بافرها جای گیرند . به دفعات دستیابی :
2 bR + bR1

اسلاید 20 :

پیوند از طریق حلقه های تو در توی بلاکی:
-این روش بهبود یافته روش قبلی است.
-اگر گنجایش بافرها به اندازه ی کافی نباشد که هر دو رابطه در آن ها جا می گیرند می توان از این روش تعداد دفعات دستیابی را کاهش داد.
-در این روش به جای دو حلقه تو در تو ، چهار حلقه تو در تو داریم.
-به ازاء هر بلاک از رابطه بیرونی(R1)، تمام بلاک های رابطه درونی (R2) بررسی می شود .
-تعداد دفعات I/₀ در بدترین حالت : bR1×bR2+bR1
-در روش بلاکی، چنانچه به جای استفاده از بلاک دیسک، از اندازه بزرگتر، مثلات باکت استفاده شودکارایی بیشتر می یابد، زیرا دفعات پیمایش رابطه درونی کاهش می یابد.