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

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

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

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

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

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

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

2 – ترجمه پرس و جوهاي 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 : جستجوي خطي (روش برنامه‌سازي پر قدرت): بازيابي هر ثبت در فايل، و تست اينكه آيا مقادير ويژگي آن،‌ شرط انتخاب را براورده مي‌سازد يا خير.