فهرست
مقدمه 2
2 – ترجمه پرس و جوهاي SQL به پرس و جوهاي رابطهاي: 5
1802- الگاريتم هاي انساني براي اجراي عملياتهاي پرس و جو: 6
1. 2. 18- مرتب كردن خارجي: 7
2. 2. 18- اجرا و پياده‌سازي عمليات SELECT : 9
متدهاي جستجو براي انتخاب ساده: 10
متدهاي جستجو براي انتخاب پيچيده: 11
متدهاي براي اجراي اتصال ها: 15
اجراي اتصال بيروني: 29
تبديل درختان پرس و جو به طرح هاي اجراي پرس و جو: 44
مقدمه
در اين تحقيق ما به تكنيك‌هاي بكار رفته توسط DMBS براي پردازش، بهينهسازي و اجراي پرس و جوهاي سطح بالا مي‌پردازيم.
پرس و جوي بيان شده در زبان پرس‌و جوي سطح بالا مثل 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 : جستجوي خطي (روش برنامه‌سازي پر قدرت): بازيابي هر ثبت در فايل، و تست اينكه آيا مقادير ويژگي آن، شرط انتخاب را براورده مي‌سازد يا خير.
– S2: جستجوي بنيادي (دودويي): اگر شرط انخاب شامل قياس تساوي روي ويژگي كليدي باشد كه روي آن فايل مرتب مي‌شود، جستجوي بنيادي، كه نسبت به جستجوي خطي كارآمدتر است، مي‌تواند بكار رود. مثال OP1 است چنانچه ssn ، ويژگي كليدي با شاخص اوليه( يا كليد hash) باشد، براي مثال، SNN-‘123456789’ در opt، شاخص اوليه يا كليد hosh) براي بازيابي ثبت استفاده مي‌شود، توجه كنيد كه اين شرط، ثبت تكي را بازيابي مي‌كند.
– S4: كاربرد شاخص اوليه براي بازيابي ثبتهاي متعدد: اگر شرط انتخاب شدن قياس تساوي روي ويژگي غير كليدي با شاخص خدشه‌سازي باشد، براي مثال در ، شاخص را براي بازيابي كل ثبت‌ها در برآورده ساختن شرط، استفاده كنيد.
– S6: بكارگيري شاخص ثانويه (درخت ) روي قياس تساوي: اين متد جستجو مي‌تواند براي بازيابي ثبت تكي بكار رود چنانچه فيلد نمايه‌سازي (شاخص‌سازي) كليد باشد يا براي بازيابي ثبتهاي متعدد بكار مي‌رود چنانچه فيلد شاخص‌سازي كليد نباشد، اين مي‌تواند براي مقايساتي شامل يا بكار رود. در بخش 3. 4. 18، ما به چگونگي توسعه فرمول‌هايي مي‌پردازيم كه هزينه‌دستيابي اين متدهاي جستجو را در اصطلاحات تعداد دستيابي‌هاي بلوك و زمان دستيابي برآورد مي‌كند. Method S!براي هر فايلي استفاده مي‌شود ولي تمام متدهاي ديگر به داشتن مسير دستيابي مناسب روي ويژگي‌بكار رفته در شرط انتخاب بستگي دارند. متدهاي S4 و 6، مي‌توانند براي بازيابي ثبت‌ها در دامنه معين بكار روند براي مثال پرس و جوها شامل اين شرط‌ها، پرس وجوهاي دامنه نيامد به ميشوند…
