دانلود تحقیق بهینه سازی و پردازش پرس و جو

در این فصل، به تکنیک‌های بکار رفته توسط 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.

18 و 4.

02 18 بحث خواهیم کرد.

توجه کنید که مرتب کردن در صورتی که اجتناب می‌شود که شاخص مناسب برای امکان دسترسی مرتب شده به ثبت‌ها وجود دارد.

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

الگاریتم‌ مرتب کردن خارجی نمونه از استراتژی مرتب- ادغام استفاده می‌کند، که با مرتب کردن- فایل‌های فرعی کوچک بنام اجراها در فایل اصلی شروع می‌شود و بعد اجراها مرتب شده ادغام می‌شوند،‌‍ فایل‌های فرعی مرتب شده بزرگتری ایجاد می‌شوند که بترتیب ادغام می‌شوند.

الگاریتم ادغام –مرتب،‌ مثل دیگر الگاریتم های پایگاه اطلاعاتی به فاضی بافر در حافظه اصلی نیاز دارد،‌ جایی که مرتب کردن واقعی و ادغام اجراها انجام می‌ شود.

الگاریتم اصلی (سیبک) شرح داده شده در تصویر 1802 ، شامل دو مرحله است: (1) فاز یا مرحله مرتب کردن و (2) مرحله ادغام.

در مرحله مرتب کردن، اجراهای فایلی که می‌تواند در فضای باز موجود تناسب یابد در حافظه اصلی خوانده می‌شوند و با استفاده از الگاریتم مرتب کردن داخلی مرتب می‌شود عقب دیسک بعنوان فایل‌های فرعی مرتب شده متوفی نوشته می‌شود.

اندازه اجرا و تعداد اجراهای آغازین توسط تعداد بلوکهای فایل (b) و فضای بافر موجود (NB) بیان می‌شود.

برای مثال اگر بلوکو اندازه قایل 1024=b بلوک باشد،‌ بعد یا 205 اجرای آغازین در هر اندازه 5 بلوک است.

از اینرو، بعد از مرحله مرتب کردن، 205 اجرای مرتب شده بعنوان فایل‌های فرعی موقتی روی دیسک ذخیره می‌شوند.

اجرای مرتب شده بعنوان فایل‌های فرعی موقتی و روی دیسک ذخیره می‌شوند.

در مرحله ادغام شدن، اجراهای مرتب شده،‌ در طول یک یا چند گذر ادغام می‌‌شوند.

درجه ادغام شدن تعداد اجراهایی است که می‌توانند با همدیگر در هر گذر ادغام شوند.

در هر گذر، یک بلوک بافر، برای حفظ یک بلوک از هر اجرای ادغام شده نیاز می‌باشد، و یک بلوک برای تشکیل یک بلوک نتیجه ادغام لازم است .

از اینرو،‌ کوچکتر از و است و تعداد گذرها، است.

در مثالها، است.

لذا،‌ 205 اجرای مرتب شده آغازین در 25 تا در پایان اولیه گذر ادغام می‌شود: که بعد به 12، بعد 4 بعد یک اجرا ادغام می‌شوند، که بدین معنی است که چهارگذر لازم می‌باشد.

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

دومین جمله، تعداد دسترسی‌های بلوک برای مرحله ادغام کردن را نشان می‌دهد، با فرض اینکه بدترین مورد از 2 وجود دارد.

بطور کلی، ثبت وقایع در مبنای و عبارت برای تعداد دسترسی‌های بلوک نوین قرار می‌شود: تصویر 1802- شرح الگاریتم ادغام – مرتب کردن برای مرتب کردن خارجی: 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.

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 استفاده می کنیم.

تغییرات اتصال ادغام شدن - مرتب کردن می تواند زمانی بکار رود که شاخص های ثانویه روی هر دو ویژگی های اتصال وجود دارند.

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

تصویر 3.

18: اتصال hash : ثبت های فایل های S,R ،‌هر دو در فایل hash یکسانی ، با استفاده از تابع hashing یکسانی روی ویژگی های اتصالی A از B,R از S بعنوان کلیدهای hash ، hash می شوند.

ابتدا ، گذر تکی از طریق فایل با ثبت های کمتر، ثبت های خود را در مخازن فایل hash ، hash می کند، این مرحله تقسیم کردن (پارتیشن )‌نامیده می شود، چون ثبت های R به مخازن hash تقسیم می شوند.

بقیه تصویر 3 .18: در دومین مرحله بنام مرحله آزمایش، گذر تکی از طریق فایل دیگر (S) هر یک از ثبت های خود را برای آزمایش مخزن مناسب hash می کند و آن ثبت با تمام ثبت های تطبیق پذیر و برابر از R در آن مخزن ترکیب می شود.

این توصیف ساده شده از اتصال hash ،‌فرض می کند که دو فایل کوچکتر کاملاً در مخازن حافظه بعد از اولین مرحله تناسب می یابند.

ما روی تغییرات اتصال - hash بحث می کنیم که به این فرضیه زیر نیازی ندارد.

در محل، تکنیک های J1 تا J4 ،‌با دسترسی به کل بلوکهای دیسک فایل بغیر از ثبت های اختصاصی اجرا می شوند.

بسته به فضای بافر موجود در حافظه ،‌تعداد بلوکهای خوانده شده از فایل می تواند تنظیم گردند.

اثرات فضای بافر موجود و عامل انتخاب اتصال روی عملکرد اتصال: فضای بافر موجود، اثر مهمی روی الگاریتم های گوناگون اتصال دارد.

ابتدا ، روش حلقه تو در تو را در نظر بگیرید (J1) .

دوباره به عملیات OP6 فوق توجه کنید، فرض کنید که تعداد بافرهای موجود در حافظه اصلی برای اجرای اتصال بلوک است.

برای مثال ، فرض کنید که فایل DEPARTMENT شامل بلوک دیسک است و فایل Employee شامل ثبت ذخیره شده در بلوک دیسک است.

این مزیتی در خواندن بلوک های بسیار در حد ممکن در حافظه از فایلی است که ثبت های آن برای حلقه بیرونی استفاده می شوند.

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

این ، کل تعداد دستیابی های بلوک را کاهش می دهد.

بلوک بافر اضافی برای شامل شدن ثبت های حاصله بعد از اینکه بهم متصل می شوند، لازم است و فهرست و محتویات این بلوک بافر در فایل نتیجه ضمیمه می شوند، فایل دیسکی که شامل نتیجه اتصال است، هر زمانی که آن بایگانی می شود.

این بلوک بافر برای حفظ ثبت های نتیجه اضافی مجدداً استفاده می شود.

در اتصال حلقه تودرتو آن تفاوتی را ایجاد می کند که کدام فایل برای حلقه بیرونی انتخاب شود و کدامیک برای حلقه درونی انتخاب شود.

اگر Employee برای حلقه بیرونی بکار رود، هر بلوک Employee یکبار خوانده می شود، که بدین قرار است: کل تعداد بلوکهای دستیابی شده برای فایل بیرونی = bE تعداد دفعات بلوک فایل خروجی بارگیری می شوند = کل تعداد بلوکهای دستیابی شده برای فایل درونی = از اینرو، ما کل تعداد دستیابی های بلوک زیر را بدست می آوریم: بعبارت دیگر، اگر ما از ثبت های DEPARTMENT در حلقه بیرونی استفاده کنیم، با تقارن ، کل تعداد دستیابی های بلوک زیر را بدست می آوریم: الگاریتم اتصالی از بافر برای حفظ ثبت های متصل شده در فایل نتیجه استفاده می کند.

وقتی بافر بایگانی می شود، آن در دیسک نوشته می شود و مجدداً استفاده می شود.

اگر فایل نتیجه عملیات اتصال، بلوک دیسک داشته باشد، هر بلوک یکبار نوشته می شود، لذا ، دستیابی بلوک اضافی باید به فرمول های قبلی، به م نظور برآورد کل هزینه عملیات اتصال، افزوده گردد.

کنترل های یکسانی برای فرمول ها بعداً برای الگاریتم های اتصال دیگر توسعه یافت.

همانطوریکه این مثال نشان می دهد، آن مزیتی برای استفاده فایل با بلوکهای کمتر بعنوان فایل حلقه بیرونی در اتصال حلقه تودرتو است.

عامل دیگری که روی عملکرد اتصال اثر می گذارد ، بویژه متد حلقه تکی J2 ، درصد ثبت ها در فایلی است که با ثبت ها در فایل دیگر متصل می شود.

ما اینرا فاکتور انتخاب اتصال فایل با توجه به شرط اتصال مساوی با فایل دیگر می نامیم.

این فاکتور به شرط اتصال مساوی ویژه بین دوفایل بستگی دارد.

برای نشان دادن این ، عملیات op7 را در نظر بگیرید، که هر ثبت DEPARTMENT را با ثبت Employee برای مدیر آن دپارتمان متصل می کند.

در اینجا، هر ثبت DEPARTMENT انتظار می رود با ثبت تکی employee متصل شده، ولی بسیاری از ثبت های Employee متصل نخواهند شد.

فرض کنید که شاخص های ثانویه در هر دو ویژگی های SSN از Employee و MGRSSN از OEPARTMENT ، با تعداد سطوح شاخص4 = XSSN و 2XMGRSSN = وجود دارد.

ما درو انتخاب برای اجحرای متد J2 داریم.

اولی هر ثبت Empyzb را بازیابی می کند و بعد از شاخص روی MGRSSN از DEPARTMGNT برای یافتن ثبت تطبیق پذیری DEPARTMGNT برای یافتن ثبت تطبیق پذیری DEPARTMGNT استفاده می کند.

در این مورد، هیچ ثبت تطبیق پذیری برای کارمندانی که بر دپارتمان مدیریت نمی کنند، مشاهده نمی شود.

تعداد دستیابی های بلوک برای این مورد تقریباً بدین قرار است: دومین انتخاب هر ثبت DEPARTMGNT را بازاریابی می کند و بعد از شاخص روی EMPLOYEE برای یافتن ثبت EMPLOYEE میر تطبیق پذیری استفاده می کند.

در این خصوص، هر ثبت DEPARTMGNT، یک ثبت تطبیق پذیری Empoyee دارد.

تعداد دستیابی های بلوک برای این مورد، بدین قرار میشود: دومین انتخاب کارآمدتر است چون فاکتور انتخاب اتصال DEPARTMGNT با توجه به شرط اتصال SSN=MGRSSN ، یک است، در عوض فاکتور انتخاب اتصال Employee با توجه به همان شرط اتصال یکسان (S0/S000) یا 01/0 است.

برای متد J2 ، یا فایل کوچکتر از فایلی که برای هر ثبت تطبیق و برابری دارد، باید در حلقه اتصال (بیرونی) استفاده شود.

این برای ایجاد شاخص برای اجرای عملیات اتصال امکان پذیر است اگر یک وجود نداشته باشد.

اتصال ادغام - مرتب کردن J3، کاملاً کارآمد است چنانچه هر دو فایل توسط ویژگی اتصال خود مرتب شوند.

فقط گذر تکی از طریق هر فایل ایجاد می شود.

از اینرو تعداد بلوکهای دستیابی شده، ؟؟

با مجموع تعداد بلوک ها در هر دو فایل است.

برای این متد، هر دو op7, op6 به دستیابی های بلوک نیاز دارند.

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

اگر هزینه مرتب کردن فایل خارجی را با (blog2b) دستیابی بلوک برآورد کنیم و اگر هر دو فایل نیاز به مرتب شدن داشته باشند، کل هزینه اتصال ادغام - مرتب کردن می تواند توسط برآورد شود.

اتصال hash پارتیشن و اتصال hash دو رگه :‌متد اتصال hash ، J4 نیز کاملاً متفاوت است.

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

اگر جدول hash برای کوچکتر از دو فایل در حافظه اصلی بتواند بعد از hashing روی ویژگی اتصال آن حفظ گردد، اجرا بسادگی صورت می گیرد.

بهر حال اگر بخشهایی از فایل hash روی دیسک ذخیره شوند، متد پیچیده تر می شود، و تعدادی تغییرات برای بهبود کارآیی پیشنهاد شده است.

ما روی دو تکنیک بحث می کنیم: اتصال hash پارتیشن ، و تغییراتی بنام اتصال hash دو رگه ، که کاملاً کارآمد نشان داده شده است.

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

بعد هر جفت پارتیشن ها متصل می شوند.

برای مثال ، فرض کنید رابطه های S,R را روی ویژگیهای اتصال S.B , R.A متصل می کنیم: در مرحله تقسیم کردن ، R به M پارتیشن به M پارتیشن تقسیم می شود.

ویژگی هر جفت پارتیشن های متناظر در این است که ثبت ها در Ri فقط به متصل شدن با ثبت ها در Si نیاز دارند و برعکس.

این ویژگی با استفاده از همان تابع hash برای تقسیم کردن هر دو فایل روی ویژگیهای اتصال آنها، ویژگی A برای R و ویژگی B برای S ، تضمین می گردد.

حداقل تعداد بافرهای مورد نیاز حافظه برای مرحله تقسیم کردن، M تا است.

هر فایل S,R بطور مجزایی تقسیم می شوند.

برای هر پارتیشنی ، بافر در حافظه تکی ، که اندازه آن یک بلوک دیسک است، برای ذخیره ثبت هایی تخصیص می یابد که نسبت به این پارتیشن hash می باشد.

هر وقت بافر در حافظه برای پارتیشن پر می شود، محتویات آن به فایل فرعی دیسک ضمیمه می گردند که این پارتیشن را ذخیره می کند.

مرحله تقسیم کردن دو تکرار دارد.

بعد از اولین تکرار ، اولین فایل R ،‌به فایل های فرعی تقسیم می شود، که تمام ثبت هایی که به همان بافر hash شدند، در همان پارتیشن قرار دارند.

بعد از دومین تکرار، دومین فایل S بطور مشابه تقسیم می شود.