امروز: جمعه 10 فروردین 1403
دسته بندی محصولات
بخش همکاران
بلوک کد اختصاصی

بررسی بهینه سازی و پردازش پرس و جو

بررسی بهینه سازی و پردازش پرس و جو دسته: کامپیوتر و IT
بازدید: 33 بار
فرمت فایل: doc
حجم فایل: 456 کیلوبایت
تعداد صفحات فایل: 104

در این فصل، به تكنیك‌های بكار رفته توسط DMBS برای پردازش، بهینه‌سازی و اجرای پرس و جوهای سطح بالا می‌پردازیم

قیمت فایل فقط 26,000 تومان

خرید

بهینه‌سازی و پردازش پرس و جو:

در این فصل، به تكنیك‌های بكار رفته توسط DMBS برای پردازش، بهینه‌سازی و اجرای پرس و جوهای سطح بالا می‌پردازیم. 

پرس و جوی بیان شده در زبان پرس‌و جوی سطح بالا مثل SQL ابتدا باید پویش و تجزیه . معتبر شود. پویشگر (اسكنر) علامت هر زبان، مثل لغات كلیدی SQL، اساس ویژگی، و اساس رابطه، را در متن پرس و جو شناسایی می‌كند،‌ در عوض تجربه كننده، ساختار دستوری پرس و جو را برای تعیین اینكه آیا بر طبق قوانین دستوری زبان پرس و جو تدوین می‌شود یا خیر، چك می‌كند. پرس و جو باید همچنین معتبر شود، با چك كردن اینكه تمام اسامی رابطه و ویژگی معتبر هستند و اسامی معنی‌دار در طرح پایگاه اطلاعاتی ویژها‌ی پرس و جو می‌شوند. نمونه داخلی پرس و جو ایجاد می‌شود،‌‌ كه تحت عنوان ساختار داده‌های درختی بنام درخت پرس و جو می‌باشد. ارائه پرس و جو با استفاده از ساختار داده‌های گراف بنام گراف پرس و جو نیز امكان پذیر است. DOMS باید استراتژی اجرایی برای بازیابی نتیجه پرس و جو از فایل‌های پایگاه اطلاعاتی را هدایت كند. پرس و جو استراتژیهای اجرایی بسیاری دارد. و مرحلة انتخاب،‌ مورد مناسبی برای پردازش پرس وجو تحت عنوان بهینه‌سازی پرس و جو شناخته شده است.


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

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

برای زبانهای پایگاه اطلاعاتی (دریایی) جهت‌یابی در سطح پایینتر در سیستم‌های قانونی، مثل شبكه DML شبكه‌ای یا MOML سلسله مراتبی،‌ برنامه نویس باید، استراتی اجرای پذیرش و جو را انتخاب كند ضمن اینكه برنامه پایگاه اطلاعاتی را می‌نویسد. اگر DBMS فقط زیان جهت‌یابی را ارائه دهد. فرصت و نیاز محدودی برای بهینه‌سازی پرس وجوی وسیع توسط DBMS وجود دارد، در عوض به برنامه نویس قابلیت انتخاب استراتژی اجرایی بهینه ارائه می‌شود. بعبارت دیگر، زبان پرس و جو در سطح بالا، مثل SQL  برای DBMSهای رابطه‌ای یا OQL برای DBMS‌های مقصد،‌ در ماهیت تفریطی‌تر است. چون آنچه نتایج مورد نظر پرس و جو است بغیر از شناسایی جزئیات چگونگی بدست آمدن نتیجه،‌ را تعیین می‌كند. بهینه‌سازی پرس و جو برای پرس و جوهایی ضروی است كه در زبان پرس و جوی سطح بالا تعیین می شوند. ما روی توصیف بهینه‌سازی پرس و جو در زمینه ROBMS تمركز می‌كنیم چون بسیاری از تكنیك‌هایی كه توصیف می‌ كنیم برای، برای ODBMSها تطبیق یافته‌اند. DBMS رابطه‌ای باید استراتژیهای اجرای پرس و جوی دیگری را ارزیابی كند و استراتژی بهینه یا كارآمد معقولی را انتخاب كند. هر DBMS ،‌ تعدادی الگاریتم دسترسی به پایگاه اطلاعاتی كلی دارد كه علامتهای رابطه‌ای مثل SELECT یا JOIN یا تركیبی از این عملیات ‌ها را اجرا می‌كند. تنها استراتژیهای اجرایی كه می‌توانند توسط الگاریتم‌های دسترسی DBMS اجرا شوند و برای طراحی پایگاه اطلاعاتی فیزیكی ویژه و پرس و جوی خاص بكار روند،‌ می‌توانند توسط قطعه برنامه بهینه‌سازی پرس و جو در نظر گرفته شوند.

ما در بخش 1801 با بحث كلی چگونگی ترجمه پرس و جوهای SQL به پرس و جوهای جبری رابطه‌ای و در بهینه‌شدن آنها كار را شروع می‌كنیم. بعد ما روی الگاریتم‌ها برای اجرای عملیات‌های رابطه‌ای در بخش 1802 بحث می‌كنیم. بدنبال این مطلب، بررسی از استراتژیهای بهینه‌سازی پرس و جو را ارائه می‌دهیم. دو تكنیك اصلی برای اجرای بهینه‌‌سازی پرس و جو وجود دارد. اولین تكنیك بر اساس قوانین ذهنی جهت ترتیب دادن عملیات‌ها در استراتژی اجرای پرس و جو می‌باشد. ذهن قانونی است كه بخوبی در اكثر موارد عمل می‌كند ولی برای كار مناسب در هر مورد كنش تضمین نمی‌شود. قوانین عملیات‌ها را در درخت پرس وجو مجدداً ترتیب می‌دهند. دومین تكنیك شامل برآورد هزینه استراتژیهای اجرای متفاوت و انتخاب طرح اجرایی با پایین‌ترین هزینه برآورد است. دو تكنیك معمولاً در بهینه ساز پرس و جو (باهم تركیب می‌شوند) بهم ملحق می‌گردند. ما روی بهینه‌سازی ذهنی در بخش 1803 و برآورد هزینه در بخش 1804 بحث می‌كنیم. بعد بررسی مختصری از عوامل در نظر گرفته شده در طول بهینه‌سازی پرس و جو در RDBMS بازرگانی ORACLL= در بخش 1805 را ارائه می‌دهیم. بخش 1806،‌ نوعی بهینه‌سازی پرس و جوی معنایی را ارائه می‌دهد كه در آن محدودیت‌های شناخته شده برای پرداختن به استراتژیهای اجرایی پرس و جوی كارآمد استفاده می‌شوند.

1801 – ترجمه پرس و جوهای SQL به پرس و جوهای رابطه‌ای:

در عمل، SQL زبان پرس وجویی است كه در اكثر RDBMS ‌های بازرگانی استفاده می‌شود. پرس وجوی SQL ، ابتدا به عبارت جبری رابطه‌ای توسعه یافته معادل،‌ نمایانگر ساختار داروهای درخت پرس و جو، ترجمه می‌شود و بعد بهینه‌سازی می‌شود. پرس و جوهای SQL به بلوكهای پرس و جو تجزیه می‌شوند،‌ كه واحدهای اساسی را تشكیل می‌دهند كه می‌توانند به عملكردهای جبری ترجمه شوند و بهینه‌سازی شوند. بلوك پرس و جو شامل عبارت SELECT- FROM-WHERE تكی و بندهای Groop By و HAVING است چنانچه این‌ها بخشی از بلوك باشند. از اینرو،‌ پرس و جوهای تو در تو در پرس و جو بعنوان بلوكهای پرس و جوی مجزا شناسایی می‌شوند. چون SQL شامل عملكردهای گروهی، مثل MAX ،‌ COUNT,SUM می‌باشد، این عملگرها باید در پرس و جوی جبری توسعه یافته‌ای شامل شوند، همانطوریكه در بخش 705 توصیف شد. پرس و جوی SQL در رابطه EMPLOEE در تصویر 705 را در نظر بگیرید:

این پرس و جو شامل، پرس و جوی فرعی تو در تو است و از اینرو به دو بلوك تجزیه می‌شود. بلوك درونی بدین صورت است:

و بلوك بیرونی بدین صورت می باشد:

كه C نمایانگر نتیجه حاصله از بلوك درونی است. بلوك درونی به عبارت جبری رابطه‌ای توسعه یافته زیر ترجمه شده است:

و بلوك بیرونی به عبارت زیر  ترجمه شده است:

بهینه‌ساز پرس و جو، طرح اجرایی را برای هر بلوك انتخاب می‌كند. ما باید اشاره كنیم به در مثال فوق، بلوك درونی نیاز به ارزیابی شدن دارد تنها زمانی كه، حداكثرحقوقی كه بعكار می‌رود كه بعنوان ثابت C، توسط بلوك بیرونی استفاده می‌شود. ما اینرو پرس و جوی تودرتوی غیرمرتبط نامیدیم (در فصل 8). آن برای بهینه‌سازی پرس و جوهای تو در توی مرتبط پیچیده‌تر، خیلی سخت‌تر است، جایی كه متغیر Tuple از بلوك بیرونی در بند WHERE در بلوك درونی ظاهر می‌شود.

1802- الگاریتم های انسانی برای اجرای عملیاتهای پرس و جو:

RDBMS شامل الگاریتم‌هایی برای اجرای انواع مختلف عملیاتهای رابطه‌‌ای است كه می‌توانند در استراتژی اجرای پرس و جو نمایان شوند، این عملیات‌ها شامل عملیاتهای جبری بیسیك (اصلی) و توسعه یافته مورد بحث در فصل 7 ، و در بسیاری موارد، الحاقاتی از این عملیات‌ها می‌باشد. برای هر یك از این عملیات ها یا الحاقی از عملیات‌ها، یك یا چند الگاریتم برای اجرای عملیات‌ها در دسترس قرار دارند. الگاریتم ممكن است فقط برای ساختارهای ذخیره خاص مسیرهای دستیابی بكار روند، در اینصورت ،‌ تنها در صورتی استفاده می‌شود كه فایل های موجود در عملیات شامل این مسیرهای دستیابی هستند. در این بخش، ما به الگاریتم‌های نمونه بكار رفته برای اجرای SEKECT ، JOIN و دیگر عملیاتهای رابطه‌ای می‌پردازیم. ما بحث مرتب كردن خارجی را در بخش 180201 آغاز می‌كنیم كه در قلب عملیاتهای رابطه‌ای قرار دارد كه از استراتژیهای ادغام كردن به مرتب كردن استفاده می‌كند. بعد ما به الگاریتم‌هایی برای اجرای عملیات SELECT در بخش 180202 می‌پردازیم،‌ به عملیات ‌JOIN در بخش 180203 و عملیات PRIJECT و عملیاتهای مجموعه در بخش IE 1802 و عملیات‌های گروهی و جمعی در بخش 2 .2 . 18 می‌پردازیم.

1. 2. 18- مرتب كردن خارجی:

مرتب كردن، یكی از الگاریتم‌های اولیه بكار رفته در پردازش پرس و جو است. برای مثال، ‌به هر وقت پرس و جوی SQL ، بعد ORDER BY را تعیین می‌كند، نتیجه پرس و جو باید مرتب گردد. مرتب كردن، مؤلفه كلیدی در الگاریتم‌های مرتب كردن- ادغام كردن (مرتب-ادغام) بكار رفته برای Join و عملیاتهای دیگر، دور الگاریتم‌های حذف كپی برای عملیات PROYECT است. ما روی بعضی از این الگاریتم‌ها در بخش‌ 3. 2. 18 و 4. 02 18 بحث خواهیم كرد. توجه كنید كه مرتب كردن در صورتی كه اجتناب می‌شود كه شاخص مناسب برای امكان دسترسی مرتب شده به ثبت‌ها وجود دارد.

مرتب كردن خارجی به الگاریتم‌های مرتب كردن اشاره می‌كند كه برای فایل های بزرگ ثبت ‌های ذخیره شده روی دیسك مناسب هستند كه در حافظه اصلی، مثل اكثر فایل های پایگاه اطلاعاتی تناسب نمی‌‌یابد. الگاریتم‌ مرتب كردن خارجی نمونه از استراتژی مرتب- ادغام استفاده می‌كند، كه با مرتب كردن- فایل‌های فرعی كوچك بنام اجراها در فایل اصلی شروع می‌شود و بعد اجراها مرتب شده ادغام می‌شوند،‌‍ فایل‌های فرعی مرتب شده بزرگتری ایجاد می‌شوند كه بترتیب ادغام می‌شوند. الگاریتم ادغام –مرتب،‌ مثل دیگر الگاریتم های پایگاه اطلاعاتی به فاضی بافر در حافظه اصلی نیاز دارد،‌ جایی كه مرتب كردن واقعی و ادغام اجراها انجام می‌ شود. الگاریتم اصلی (سیبك) شرح داده شده در تصویر 1802 ، شامل دو مرحله است: (1) فاز یا مرحله مرتب كردن و (2) مرحله ادغام.

در مرحله مرتب كردن، اجراهای فایلی كه می‌تواند در فضای باز موجود تناسب یابد در حافظه اصلی خوانده می‌شوند و با استفاده از الگاریتم مرتب كردن داخلی مرتب می‌شود عقب دیسك بعنوان فایل‌های فرعی مرتب شده متوفی نوشته می‌شود. اندازه اجرا و تعداد اجراهای آغازین  توسط تعداد بلوكهای فایل (b) و فضای بافر موجود (NB) بیان می‌شود. برای مثال اگر  بلوكو اندازه قایل 1024=b  بلوك باشد،‌ بعد  یا 205 اجرای آغازین در هر اندازه 5 بلوك  است. از اینرو، بعد از مرحله مرتب كردن، 205 اجرای مرتب شده بعنوان فایل‌های فرعی موقتی روی دیسك ذخیره می‌شوند. اجرای مرتب شده بعنوان فایل‌های فرعی موقتی و روی دیسك ذخیره می‌شوند.

در مرحله ادغام شدن، اجراهای مرتب شده،‌ در طول یك یا چند گذر ادغام می‌‌شوند. درجه ادغام شدن  تعداد اجراهایی است كه می‌توانند با همدیگر در هر گذر ادغام شوند. در هر گذر، یك بلوك بافر، برای حفظ یك بلوك از هر اجرای ادغام شده نیاز می‌باشد، و یك بلوك برای تشكیل یك بلوك نتیجه ادغام لازم است . از اینرو،‌ كوچكتر از  و  است و تعداد گذرها،  است. در مثالها،  است. لذا،‌ 205 اجرای مرتب شده آغازین در 25 تا در پایان اولیه گذر ادغام می‌شود: كه بعد به 12، بعد 4 بعد یك اجرا ادغام می‌شوند، كه بدین معنی است كه چهارگذر لازم می‌باشد. حداقل  از 2،‌ عملكرد بدترین مورد الگاریتم را ارائه می‌دهد كه بدین قرار است:

اولین جمله، تعداد دسترسی‌های بلوك برای مرحله مرتب سازی را نشان می‌دهد، چون هر بلوك فایل دو برابر دسترسی می‌شود، یكبار برای خواندن در حافظه،‌ یكبار برای نوشتن ثبت‌ها دیسك بعد از مرتب كردن. دومین جمله، تعداد دسترسی‌های بلوك برای مرحله ادغام كردن را نشان می‌دهد، با فرض اینكه بدترین مورد  از 2 وجود دارد. بطور كلی، ثبت وقایع در مبنای  و عبارت برای تعداد دسترسی‌های بلوك نوین قرار می‌شود:

تصویر 1802- شرح الگاریتم ادغام – مرتب كردن برای مرتب كردن خارجی:

2. 2. 18- اجرا و پیاده‌سازی عملیات SELECT :

تعداد Option‌هایی ( انتخاب‌ها) برای اجرای عملیات SELECT وجود دارد، كه بعضی به فایل دارای مسیرهای دستیابی خاص بستگی دارند و تنها برای انواع معین شرایط انتخاب بكار می‌رود. ما به الگاریتم‌هایی جهت اجرای SELECT در این بخش می‌پردازیم. ما از عملیاتهای زیر استفاده می‌كنیم كه روی پایگاه اطلاعاتی رابطه‌ای در تصویر 507 مشخص شده و بحث ما را روشن می‌سازد:

متدهای جستجو برای انتخاب ساده:

تعدادی الگاریتم های جستجو برای انتخاب ثبت‌ها از فایل امكان‌پذیر می‌باشند،‌ چون ثبت‌‌های فایل نامیده می شوند، چون ثبت‌‌های فایل را برای جستجو و بازیابی ثبت‌هایی كه شرایط انتخاب را برآورده می‌سازند، پویش می‌كنند. اگر الگاریتم جستجو شامل كاربرد شاخص باشد،‌ جستحوی شاخص پویش شاخص نامیده می‌شد. متدهای جستجوی زیر ( 1S تا s6 ) مثالهایی از الگاریتم‌های جستجو هستند كه می‌توانند برای اجرای عملیات انتخاب بكار روند:

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

-  S2: جستجوی بنیادی (دودویی):‌ اگر شرط انخاب شامل قیاس تساوی روی ویژگی كلیدی باشد كه روی آن فایل مرتب می‌شود، جستجوی بنیادی، كه نسبت به جستجوی خطی كارآمدتر است، می‌تواند بكار رود. مثال OP1 است چنانچه ssn ، ‌ویژگی كلیدی با شاخص اولیه‌( یا كلید hash) باشد،‌ برای مثال، SNN-‘123456789’ در opt، شاخص اولیه یا كلید hosh) برای بازیابی ثبت استفاده می‌شود، توجه كنید كه این شرط، ثبت تكی را بازیابی می‌كند.

-  S4: كاربرد شاخص اولیه برای بازیابی ثبت‌های متعدد: اگر شرط انتخاب شدن قیاس تساوی روی ویژگی غیر كلیدی با شاخص خدشه‌سازی باشد،‌ برای مثال   در ، شاخص را برای بازیابی كل ثبت‌ها در برآورده ساختن شرط،‌ استفاده كنید.

-   S6: بكارگیری  شاخص ثانویه (درخت  ) روی قیاس تساوی: این متد جستجو می‌تواند برای بازیابی ثبت تكی بكار رود چنانچه فیلد نمایه‌سازی (شاخص‌سازی) كلید باشد یا برای بازیابی ثبت‌های متعدد بكار می‌رود چنانچه فیلد شاخص‌سازی كلید نباشد،‌ این می‌تواند برای مقایساتی شامل یا  بكار رود. در بخش 3. 4. 18، ما به چگونگی توسعه فرمول‌هایی می‌پردازیم كه هزینه‌دستیابی این متدهای جستجو را در اصطلاحات تعداد دستیابی‌های بلوك و زمان دستیابی برآورد می‌كند. Method S!برای هر فایلی استفاده می‌شود ولی تمام متدهای دیگر به داشتن مسیر دستیابی مناسب روی ویژگی‌بكار رفته در شرط انتخاب بستگی دارند. متدهای S4  و 6،‌ می‌توانند برای بازیابی ثبت‌ها در دامنه معین بكار روند برای مثال   پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به می‌شوند.

متدهای جستجو برای  انتخاب پیچیده:

اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشكیل شود، ‌DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده كند:

S7: انتخاب تقارنی  یا ارتباطی با استفاده از شاخص اختصاص:‌ اگر ویژگی شامل شده در هر شرط ساده متكی در شرط تقارنی، مسیر دستیابی داشته باشد كه به كاربرد یكی از متدهای S2 تا S6 امكان عمل دهد، از آن شرط برای بازیابی ثبت‌های استفاده كنید و بعد كنترل كنید  آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌كند یا خیر.

S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مركب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مركب در فیلدهای مركب وجود داشته باشد، برای مثال اگر شاخص روی كلید مركب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره كرد.

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

محل تقاطع این مجموعه اشاره گرهای ثبت، اشاره گرهای ثبتی را ارائه می دهد كه شرط تقارنی را برآورده می سازد، كه بعد برای بازیابی آن ثبت ها مستقیماً استفاده می شوند. اگر فقط بعضی از شرایط ، شاخص های ثانویه داشته باشند،‌هر ثبت بازیابی شده، برای تعیین اینكه آیا آن شرایط باقیمانده را برآورده می سازد یا خیر، بعداً تست می شود.

هر وقت شرط تكی ، انتخابی مثل OP3, OP2, OP1 را تعیین می كند، می توانیم فقط چك كنیم كه آیا مسیر دستیابی روی ویژگی شامل شده در آن شرط وجود دارد یا خیر. اگر مسیر دستیابی وجود داشته باشد،‌متد مربوط به آن مسیر دستیابی استفاده می شود، در غیر اینصورت،‌روش جستجوی خطی برنامه سازی پرقدرت (boute force) در متد S1 می تواند استفاده شود. بهینه سازی پرس و جو برای عملیات SELECT برای شرایط انتخاب تفاوتی لازم است،‌ هر وقت بیش از یك ویژگی شامل شده در شرطها، دارای مسیر دستیابی می باشند. بهینه ساز باید، مسیر دستیابی را انتخاب كند كه كمترین ثبت ها در كارآمدترین راه با برآورد هزینه های مختلف را بازیابی می كند و متد با حداقل هزینه برآورده شده را انتخاب می كند. وقتی بهینه ساز بین شرط های ساده متعدد در شرط انتخاب تقارنی،‌انتخاب می كند، آن ، انتخاب پذیری هر شرط را در نظر می گیرد. انتخاب پذیری، بعنوان نسبت مقدار ثبت هایی تعریف می شود كه شرط را نسبت به كل تعداد ثبت ها در فایل برآورده می سازد، و لذا تعداد بین صفر و 1 است . انتخاب پذیری صفر بدین معنی است كه هیچ ثبتی ، شرط را برآورده نمی سازد و یك بدین معنی است كه تمام ثبت ها ،‌شرط را برآورده می سازند. گر چه انتخاب پذیری های دقیق تمام شرط ها ممكن است در دسترس نباشند، برآوردهای انتخاب پذیری ها ،‌اغلب در كاتالوگ DBMS حفظ می گردند و توسط بهینه ساز استفاده می شوند. برای مثال، برای شرط تساوی روی ویژگی كلیدی رابطه S=1/|(R)|,(R) است ،‌جایی كه |r(R)| تعداد Tople (ثبت ها)‌در رابطه r(R) است. برای شرط تساوی روی ویژگی با نامقادیر متمایز، S فقط (|,(R)|/i)/|,(R)|| یا 1/i برآورد می شود، با فرض بر اینكه ثبت ها در میان مقادیر متمایز توزیع می شوند. تحت این فرضیه ، |r(R)1/i ثبت ها ،‌شرط انتخاب را با انتخاب پذیری s برآورده می سازد در حالت |r(R)\*s برآورده می شود. هر چه این برآورد كوچكتر باشد، تمایل استفاده از آن اولین شرط برای بازیابی ثبت ها بیشتر است.

در مقایسه با شرط انتخاب تقارنی (ارتباطی) ، شرط گسسته برای پردازش و بهینه سازی سخت تر است.

براث مثال ، opu را در نظر بگیرید.                    (op 49):

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

DBMS متدهای زیادی در دسترس دارد و متدهای اضافی نیز دارد. بهینه ساز پرس و جو باید مورد مناسبی را برای اجرای هر عملیات SELECT در پرس و جو استفاده كند. این بهینه سازی از فرمولی استفاده می كند كه هزینه ها را برای هر متد دستیابی قابل دسترس برآورد می كند،‌همانطوریكه در بخش 1804 بحث می شود بهینه ساز، متد دستیابی را با حداقل هزینه برآورد شده،‌انتخاب می كند.

3. 2. 18 : اجرای عملیات JOIN : عملیات JOIN یكی از طولانی ترین عملیات ها در پردازش پرس و جو است. بسیاری از عملیات های اتصال مواجه شده در پرس و جو، انواع EQUIJOIN ، NATURAL JOIN هستند، لذا فقط این دو تا را در اینجا در نظر می گیریم. برای بقیه فصل، اصطلاح اتصال به EQUIJOIN اشاره می كند. راههای ممكن زیادی برای اجرای اتصال دو راهی وجود دارد، كه اتصال روی دو فایل است. اتصال ها شامل بیش از دو فایل ، اتصالهای چندراهی نامیده می شوند. تعدادی راههای ممكن برای اجرای اتصال های چندراهی بسرعت رشد می كنند. در این بخش، ما روی تكنیك هایی برای اجرای فقط اتصال های دوراهی بحث می كنیم. برای نشان دادن بحث خود، به طرح رابطه ای تصویر 5 .7 در رابطه های PROJECT, DEPARTMENT, EMPLOYEE اشاره می كنیم. الگاریتم هایی كه در نظر می گیریم ، جهت عملیاتهای اتصال بفرم زیر است  كه B,A ویژگیهای R و S حوزه سازگار است. متدهایی كه بحث می كنیم، بفرم كلی تر اتصال توسعه می یابند. ما چهار تا از متداول ترین تكنیك ها را برای اجرای این اتصال ، با استفاده از عملیاتهای مثال زیر نشان می دهیم:

(op6):

(op7):

متدهای برای اجرای اتصال ها:

J1 : اتصال با حلقه تودرتو (برنامه سازی پرقدرت) : برای هر ثبت t در R (حلقه بیرونی) هر ثبت s را از S بازیابی كنید (حلقه درونی) و تست كنید آیا دو ثبت ، شرط اتصال t[A]=s[B] را برآورد می سازند یا خیر.

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

J3 : اتصال مرتب (كردن) - ادغام : اگر ثبت های R و S توسط مقدار ویژگی های اتصال B,A مرتب شوند، می توان اتصال را در كارآمدترین راه ممكن اجرا كرد. هر دو فایل در ترتیب ویژگی های اتصال تطبیق پذیری ثبت هایی پویش می شوند كه دارای مقادیر یكسانی برای B,A داشتند. اگر فایل ها مرتب نشوند، آنها ابتدا با استفاده از مرتب كردن خارجی مرتب می شوند. در این متد، جفت های بلوكهای فایل در بافرهای حافظه در ترتیب كپی می شوند و ثبت های هر فایل تنها یكبار هر یك برای تطبیق پذیری با فایل دیگر، پویش می شوند، مگر اینكه هر دو B,A ویژگیهای غیر كلیدی باشند، كه در آن مورد، متد نیاز به تعدیل شدن دارد. طرح الگاریتم اتصال مرتب كردن - ادغام در تصویر (a) 3 . 18 ارائه شده است. ما از R(i) برای اشاره به ثبت i ام در R استفاده می كنیم.

تغییرات اتصال ادغام شدن - مرتب كردن می تواند زمانی بكار رود كه شاخص های ثانویه روی هر دو ویژگی های اتصال وجود دارند. شاخص ها،‌قابلیت دسترسی به ثبت ها در ترتیب ویژگی های اتصال را ارائه می دهند، ولی ثبت ها در سراسر بلوكهای فایل پخش می شوند، لذا این متد كاملاً غیر كارآمد است، تحت عنوانی كه هر دستیابی به ثبت ممكن است شامل دسترسی به بلوك دیسك متفاوتی باشد.

قیمت فایل فقط 26,000 تومان

خرید

برچسب ها : ترجمه پرس و جوهای SQL به پرس و جوهای رابطه ای , الگاریتم های انسانی برای اجرای عملیاتهای پرس و جو , متدهای جستجو برای انتخاب ساده

نظرات کاربران در مورد این کالا
تا کنون هیچ نظری درباره این کالا ثبت نگردیده است.
ارسال نظر