الگوريتم هاي تخصيص داده پويا در سيستم هاي پايگاه داده توزيعي

استاد : جناب آقاي دکتر رهگذر نگارش : کاوه پاشائي زمستان 84 مقدمه پيشرفت در تکنولوژيهاي شبکه و پايگاه داده در دهه هاي اخير منجر به ايجاد سيستم هاي پايگاه داده توزيع شده گشته است .يک سيستم پايگاه داده توزيع شده مجموعه اي از سايتها مي باشد که از طريق شبکه به هم متصل شده اند که هر کدام از سايت ها پايگاه داده مخصوص به خود دارد اما مي توانند با يکديگر کار کنند بنابراين هر کاربري در هر سايتي مي تواند به همه داده هاي موجود در شبکه دسترسي داشته باشد درست مانند اينکه همه داده ها در سايت کاربر ذخيره شده است . دغدغه اصلي سيستم هاي پايگاه داده توزيع شده قطعه قطعه کردن[ Fragmentation] و تخصيص[ Allocation] پايگاه داده اصلي مي باشد واحد قطعه داده مي تواند يک فايل باشد که در اين حالت موضوع تخصيص همان تخصيص فايل خواهد بود مشکل تخصيص داده يک مسئله NP-complete مي باشد بنابراين نياز به هيوريستيکهاي سريع براي توليد راه حل هاي موثر مي باشد علاوه بر اينها تخصيص بهينه اشيا پايگاه داده به طور شديد بستگي به استراتژي اجراي پرس وجو [ Query] که به وسيله پايگاه داده توزيع شده پياده سازي شده دارد . هزينه اصلي در اجراي پرس و جو در سيستمهاي پايگاه داده توزيع شده هزينه انتقال داده هنگام انتقال يک رابطه در موقع درخواست پرس و جو از يک سايت و انتقال آن از يک سايت متفاوت مي باشد[2] . هدف اصلي الگوريتم هاي تخصيص داده تعيين نسبت دادن فرگمنتها به سايتهاي مختلف براي کمينه کردن هزينه انتقال داده در اجراي[ Static] يک مجموعه از پرس و جو ها مي باشد که معادل کمينه کردن زمان متوسط اجراي پرس و جو مي باشد که اهميت اصلي در محيط هاي توزيع شده و پايگاه داده چند رسانه اي دارد .