مقدمه
پیشرفت های اخیر در تکنولوژی های شبکه و پایگاه داده باعث ایجاد سیستم های پایگاه داده توزیع شده شده است. سیستم پایگاه داده توزیع شده، مجموعه ای از سایت ها است که از طریق شبکه به یکدیگر متصل هستند. هر سایت پایگاه داده خاص خود را دارد، اما قادر است با دیگر سایت ها همکاری کند. در نتیجه، هر کاربر در هر سایتی می تواند به تمام داده های موجود در شبکه دسترسی پیدا کند، به گونه ای که گویی تمامی داده ها در سایت خود کاربر ذخیره شده اند.
یکی از چالش های اصلی سیستم های پایگاه داده توزیع شده، قطعه قطعه کردن و تخصیص پایگاه داده اصلی است. واحد قطعه داده می تواند یک فایل باشد، که در این صورت تخصیص فایل مسئله اصلی خواهد بود. مشکل تخصیص داده، یک مسئله NP-complete است و به همین دلیل نیاز به هیوریستیک های سریع برای پیدا کردن راه حل های مؤثر وجود دارد. علاوه بر این، تخصیص بهینه اشیای پایگاه داده به طور قابل توجهی به استراتژی های اجرای پرس و جو بستگی دارد که توسط سیستم پایگاه داده توزیع شده پیاده سازی می شود.
هزینه اصلی اجرای پرس و جو در سیستم های پایگاه داده توزیع شده، هزینه انتقال داده است. این هزینه به هنگام انتقال یک رابطه در زمان درخواست پرس و جو از یک سایت به سایت دیگر ایجاد می شود. هدف اصلی الگوریتم های تخصیص داده، تعیین نحوه تخصیص فرگمنت ها به سایت های مختلف برای کمینه کردن هزینه انتقال داده در هنگام اجرای مجموعه ای از پرس و جوها است. این امر معادل با کمینه کردن زمان متوسط اجرای پرس و جو است که اهمیت ویژه ای در محیط های توزیع شده و پایگاه داده های چندرسانه ای دارد.
