ارائه الگوریتمی برای بهینه سازی پرس و جوهای تو در تو

 

 

ارائه الگوریتمی برای بهینه سازی پرس و جوهای تو در تو

mohsen_mahyar@yahoo.com

mo-mah.persianblog.ir

چکیده

بهینه سازی پرس و جوهای تودرت و ی پیچیده، مشگل است، خصوصا اگر از توابع تعریف شده کاربر در پرس و جو استفاده

شده باشد . بیشترین روشی که برای بهینه سازی پرس و جوهای تودرتو پیشنهاد شده، تبدیل پرس و جو از حالت تودرتویی به شکل

غیر تودرتو اس ت . اما این روش همیشه اجرایی و مناسب نمی باشد، همچنین اگر پرس و جو از توابع تعریف شده کاربر استفاده نماید

تبدیل سخت تر هم می شو د . در این تحقیق نشان داده می شود روشهای موجود برای پردازش پرس و جو و زیر پرس و جوهای

به دلیل این که دستورات داخل ت و ابع برای هر سطر از پرس و جوی فراخواننده (SELECT شامل توابع تعریف شده کاربر (در شرط

بطور مستقل اجرا می گردند، موثر نیستن د . سپس یک روش برای بهینه سازی پرس و جوها و زیر پرس و جوهایی که شامل توابع

تعریف شده کاربر هستند در قالب الگوریتم ارائه می گرد د . در نهایت، یک بهینه ساز شبیه سازی می شود و نتایجش د ر محیط

ثبت می گردد که صحتی بر خاصیت این تحقیق می باشد. Microsoft SQL Server

کلمات کلیدی

بهینه سازی پرس و جو، بهینه سازی پرس و جوهای تو در تو ، توابع تعریف شده کاربر، غیر همبستگی، غیر تودرتویی.

2

۱- مقدمه

ما از بهینه سازی پرس و جو برای حل مسائل زیادی استفاد ه می

کنیم. زمانی که یک پرس و جو مطرح می شود، سیستم مدیریت

بانک اطلاعات می تواند از روش های مختلفی برای پردازش آن

پرس و جو و رسیدن به جواب استفاده کند . همه آن روش ها در

نهایت یک نتیجه را تولید می کنند ولی از نظر هزینه های انجام

شده مانند کل زمان مورد نیاز برای اجرا متفاوت اند . چه روشی

حداقل زمان را برای اجرا نیاز دارد؟ در زمینه بانک اطلاعات،

محدوده بهینه سازی پرس و جوها بسیار وسیع است . این مورد از

زوایای مختلفی می تواند مطالعه و بررسی شود، که در هر مورد به

بخش های متعددی تقسیم می شود، هدف این تحقیق بررسی

روشهای بهینه سازی پرس و جوهای تودرتو (پرس و جوهایی که

دارای زیر پرس و جو هستند ) و ارائه روشی برای بهینه سازی

پرس و جوها و زیرپرس و جوهایی که شامل توابع تعریف شده

کاربر هستند . بیشترین روشی که برای بهینه سازی پرس و

جوهای تودرتو پیشنهاد شده است [ 11,14 ] تبدیل پر س و جو از

حالت تودرتویی به شکل غیر تودرتو است . اما این روش همیشه

اجرایی و مناسب نمی باشد، همچنین اگر پرس و جو از توابع

تعریف شده کاربر استفاده نماید تبدیل سخت تر هم می شود . به

پرس و جوی مثال زیر که از یک تابع تعریف شده کاربر در

استفاده می نماید توجه کنید. SELECT قسمت

که شامل سه TestTree مثال : ساختار درختی هر نود جدول

فیلد نام گره ، پدر گره و شرح گره میباشد را مشخص نمایید.

SELECT dbo.fullname(@nodeid)

FROM TestTree

CREATE FUNCTION dbo.fullname (@nodeid int)

RETURNS varchar(500) AS

BEGIN

declare @pid int

declare @Str varchar(500)

declare @CurrentName varchar(500)

SET @Str = ''

SELECT @Pid = ParentId , @CurrentName =

NodeName

FROM TestTree

WHERE NodeId = @nodeid

SET @Str = @CurrentName

WHILE (@PId <>0)

BEGIN

SELECT @PId = ParentId,@CurrentName =

NodeName

FROM TestTree

WHERE NodeId = @PId

SET @Str = @CurrentName + ' -> ' +@Str

END

RETURN @Str

END

روش بهینه سازی ارائه شده در این تحقیق برای چنین پرس و

جوهایی طرحهایی را بواسطه ساختار پارامترهای موجود در بدنه

تابع تولید می کند که موثرتر از تعامل تودرتوی ساده میباشد.

سایر بخش های این تحقیق به این صورت سازماندهی شده

اند : بخش ۲ پیشینه این تح قیق شرح داده شده است . عملکرد

پرس و جوهای تودرتو و روش بهینه سازی پرس و جوهایی که

شامل توابع تعریف شده کاربر هستند در بخش ۳ مطرح می

گردد. سپس در بخش ۴ این روش را مورد آزمایش و ارزیابی قرار

می دهیم و نتایجش را ثبت می کنیم، سرانجام پیشنهاداتی برای

تحقیقات آینده مطرح می کنیم.

۲- پیشینه تحقیق

تحقیقات بسیار زیادی در زمینه بهینه سازی پرس و جوهای

تودرتو انجام گرفته است که بیشترین آنها بر غیر تودرتویی پرس

و جوها تاکید دارند. برای غیر تودرتویی پرس و جوهایی که درگیر

گزاره های عطفی می باشند در [ 11,14 ] به درستی مشخص شده

که SQL است ، اما اخیر ًا [ 2] به غیر تودرتویی پرس و جوهای

شامل گزاره های فصلی می باشد اشاره شده است . شروع روش

داخل جبر رابطه ای توسعه یافته با SQL مطرح شده تبدیل

عملگرهای انشعابی است . سپس اجرای معادلهای غیر تودرتوی

جدید که با ترکیبات فصلی بوجود می آید . همانگونه که اشاره شد

روش غیر تودرتویی مذکور فقط برا ی پرس و جوهای ی که شامل

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

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

که در همه شرایط پرس وجو را از حالت تودرتویی خارج می سازد

و به معادل بهتری تبدیل می کند.

غیر تودرتویی زیر پرس وجوها را م ؤثر نمی داند [ 4] و یک Cao

SQL روش رابطه ای تودرتو برای پردازش زیر پرس وجوهای

پیشنهاد می کند . این روش توانایی رسیدگی کردن به پرس

وجوهای تودرتو از هر نوع و هر سطحی دارد (با استفاده از جبر

رابطه ای تودرتو ). انگیزه استف اده از جبر رابطه ای تودرتو آنست

که نتیجه یک زیر پرس وجو یک مجموعه ای از سطرهاست

(وقتی که توابع غیر جمعی هستند )، که در مدل رابطه ای تودرتو

می تواند همانند مجموع مقدار صفت مشخصه رفتار کند . بنابراین

مقایسه بین یک صفت مشخصه و نتیجه یک زیر پرس وجو می

تواند به و سیله مقایسه کردن یک صفت با یک مجموعه مقدار

SELECTION صفت به انجام برسد که با اندکی تغییرات عملگر

در جبر رابطه ای تودرتو حاصل می شود . بصورت کلی روش رابطه

ای تودرتوی توضیح داده شده [ 4]، در ابتدا غیر تودرتویی یک

پرس و جوی تودرتو بوسیله استرات ژی های غیر تودرتو ی رایج و

سپس استفاده از جبر رابطه ای توسعه یافته بنابر محاسبه گزاره

3

های درگیر زیر پرس وجوها، از پایین به بالا انجام می گردد. روش

رابطه ای تودرتو برای پرس وجوهایی که درگیر گزاره های منفی

هستند مناسب است ، اما در مورد پرس وجوهایی که شامل گزاره

های مثبت و توابع تعریف شده کاربر هستند برتری ویژه ای ندارد.

اعتقاد دارد اگرچه غیرهمبستگی اغلب نتایج Guravannavar

(طرحهای غیرتودرتو ) ارزانتری دارد ، ولی همیشه برای زیر پرس

وجوهای تودرتو کاربردی نمی باشد [ 9]. و اگر تعامل تودرتو

بدرستی پیاده سازی شود بر غیرهمبستگی برای چندین رده از

پرس وجوها غلبه می کند . همچنین تاکید داشت غیرهمبستگی

برای اجرای تعامل تودرتو در رویه ها و توابع تعریف شده کاربر

سخت است . بدینسان روشی پیشنهاد کرد که به اجرای تعامل

تودرتو با استفاده از پارامتر ترتیب مرتب ساز ی تسریع بخشد .

تکنیکی که برای این روش در نظ ر گرفته شده است مرتب سازی

پرس وجوی بیرونی با ملاحظه عبارات موجود در بدنه تابع (پرس

وجوی درونی) است.

۳- روش بهینه سازی پرس و جوهایی که

شامل توابع تعریف شده کاربر هستند

ما در این بخش روشی برای بهینه سازی پرس و جوهایی که

شامل توابع تعریف شده کاربر هستند، ارائه م ی دهیم . اما قبل از

پرداختن به این موضوع ابتدا عملکرد زیر پرس و جوهای تودرتو

را مورد بررسی قرار می دهیم.

۱- عملکرد زیر پرس و جوهای تودرتو -۳

بصورت مفهومی با زیر پرس و جو ها که در بخش شرط SQL

قرار دارند، شبیه به یک تابع رفتار می کند که Where موجود در

این تابع پار امترهایی را می گیرد و مقدار یا مقادیری (یا احتمالا

یک مجموعه تهی ) را بعنوان نتیجه بر م ی گرداند . پارامترها

متغیرهایی از سطح بالاتر هستند که در بخش زیر پرس و جو

های تودرتو استفاده می شوند (به این متغیرها متغیرهای

/ 2 نظر / 44 بازدید
مهدی

سلام مطلبتون خیلی خوب بود.استفاده کردم.همینجور ادامه بدید.باتشکر از شما آقا محسن[چشمک]

محمود

ممنون بابت مطلب خوبتون