سیده آمین ارمان
کاربر نگاه دانلود
روش های مختلفی برای بهینه سازی پرس و جو پیشنهاد شده است که در اینجا به سه روش مهم اشاره می کنیم
پرس و جو مبتنی بر پیمایش مسیر ، پرس و جو مبتنی بر شاخص دهی و پرس و جو مبتنی بر شماره گذاری
پرس و جو مبتنی بر پیمایش مسیر
سه روش برای پردازش پیمایش مسیر پیشنهاد شده است: پیمایش بالا به پایین، پایین به بالا و ترکیبی.
روش بالا به پایین، پیمایش را از ریشه اغاز نموده به هر گره از طریق هر مسیر رفته و گره های هدف را با تطبیق عبارت مسیر به دست می اورد.
لازمه این عمل جستجوی تمام فرزندان یک گره در هر بار جستجوی مسیر می باشد.
عکس این عمل در روش پایین به بالا صورت می گیرد، پیمایش از پایین درخت، از برگ ها اغاز می شود و ادامه می یابد تا به ریشه برسد.
روش ترکیبی با ترکیب دو روش بالا به پایین و پایین به بالا پیمایش را انجام می دهد و با همگرایی این دو روش، زمانی که در گرهی از درخت به هم می رسند، پیمایش به پایان می رسد.
در بدترین حالات هر سه این روش ها لازم است تمام گراف داده ها را پیمایش کنند که با عث می شود این روش ها بسیار نا کارا باشند.
پرس و جو مبتنی بر شاخص دهی
ساختار های شاخص دهی به وجود امدند تا مشکلات ناکارایی حاصل از پیمایش بیش از حد را بهبود بخشند.
این تکنیک ها میزان بخش هایی از درخت XML را که در طول پردازش پرس و جو مورد پویش قرار می گیرد را به طور قابل توجهی کاهش می دهند.
از میان انها می توان به [ DataGuide ، 1-index، 2-index، T-index ، A(k)-index ، Index Fabric ، APEX Index] ، و توسعه لیست وارونه اشاره نمود.
پرس و جو مبتنی بر شماره گذاری
روش های زیادی برای شماره گذاری به عنوان جایگزینی برای شاخص دهی ساختاری پیشنهاد شده است که می توان ان ها را به دو دسته برچسپ گذاری محدوده و برچسپ گذاری پیشوندی تقسیم نمود.
در روش برچسپ گذاری محدوده برچسپ هر گره به صورت جفت عدد start position, end position).) ترجمه می شود. زمانی که یک گره اضافه می شود، برچسپ معمولا باید دوباره ایجاد شود.
بنابراین به روش برچسپ گذاری محدوده، روش برچسپ گذاری غیردائمی نیز گفته می شود. در روش برچسپ گذاری پیشوندی، برچسپ یک گره تنها یک عدد است .
تحت به روز رسانی سنگین، روش برچسپ گذاری پیشوندی نیازی به محاسبه مجدد ندارد، از این رو به ان روش برچسپ گذاری دائمی گفته می شود.
پرس و جو مبتنی بر پیمایش مسیر ، پرس و جو مبتنی بر شاخص دهی و پرس و جو مبتنی بر شماره گذاری
پرس و جو مبتنی بر پیمایش مسیر
سه روش برای پردازش پیمایش مسیر پیشنهاد شده است: پیمایش بالا به پایین، پایین به بالا و ترکیبی.
روش بالا به پایین، پیمایش را از ریشه اغاز نموده به هر گره از طریق هر مسیر رفته و گره های هدف را با تطبیق عبارت مسیر به دست می اورد.
لازمه این عمل جستجوی تمام فرزندان یک گره در هر بار جستجوی مسیر می باشد.
عکس این عمل در روش پایین به بالا صورت می گیرد، پیمایش از پایین درخت، از برگ ها اغاز می شود و ادامه می یابد تا به ریشه برسد.
روش ترکیبی با ترکیب دو روش بالا به پایین و پایین به بالا پیمایش را انجام می دهد و با همگرایی این دو روش، زمانی که در گرهی از درخت به هم می رسند، پیمایش به پایان می رسد.
در بدترین حالات هر سه این روش ها لازم است تمام گراف داده ها را پیمایش کنند که با عث می شود این روش ها بسیار نا کارا باشند.
پرس و جو مبتنی بر شاخص دهی
ساختار های شاخص دهی به وجود امدند تا مشکلات ناکارایی حاصل از پیمایش بیش از حد را بهبود بخشند.
این تکنیک ها میزان بخش هایی از درخت XML را که در طول پردازش پرس و جو مورد پویش قرار می گیرد را به طور قابل توجهی کاهش می دهند.
از میان انها می توان به [ DataGuide ، 1-index، 2-index، T-index ، A(k)-index ، Index Fabric ، APEX Index] ، و توسعه لیست وارونه اشاره نمود.
پرس و جو مبتنی بر شماره گذاری
روش های زیادی برای شماره گذاری به عنوان جایگزینی برای شاخص دهی ساختاری پیشنهاد شده است که می توان ان ها را به دو دسته برچسپ گذاری محدوده و برچسپ گذاری پیشوندی تقسیم نمود.
در روش برچسپ گذاری محدوده برچسپ هر گره به صورت جفت عدد start position, end position).) ترجمه می شود. زمانی که یک گره اضافه می شود، برچسپ معمولا باید دوباره ایجاد شود.
بنابراین به روش برچسپ گذاری محدوده، روش برچسپ گذاری غیردائمی نیز گفته می شود. در روش برچسپ گذاری پیشوندی، برچسپ یک گره تنها یک عدد است .
تحت به روز رسانی سنگین، روش برچسپ گذاری پیشوندی نیازی به محاسبه مجدد ندارد، از این رو به ان روش برچسپ گذاری دائمی گفته می شود.
