سیستم پردازشگر تصویر با قابلیت تعقیب هدف متحرک در دهه 1980

سیستم پردازشگر تصویر با قابلیت تعقیب هدف متحرک در دهه 1980 استفاده از تکنولوژی تصاویر دیجیتال تحولات عظیمی را در عرصه جهانی بوجود آورد

دسته بندی	کامپیوتر و IT
فرمت فایل	doc
حجم فایل	724 کیلو بایت
تعداد صفحات فایل	108

در دهه 1980 استفاده از تکنولوژی تصاویر دیجیتال تحولات عظیمی را در عرصه جهانی بوجود آورد . استفاده از این تکنولوژی که در مراحل اولیه منحصر به شرکت های محدودی بود ، در دهه های اخیر رشد و گسترش شدیدی را موجب شده بطوری که در این زمان کمتر کسی از تصاویر دیجیتالی و ادوات و دستگاههای آن استفاده نمی کند . در عصر حاضر با ظهور فناوری های پیچیده در زمینه قطعات الکترونیک نظیر میکروپروسسورها و پردازنده های کامپیوتری و میکروکنترلرها کار و تحقیق پیرامون این مسئله فراگیر تر شده است .

در این پایان نامه با استفاده از مفاهیم اولیه پردازش تصویر و الگوریتم Subtraction & Compare تصاویر دریافتی از یک دوربین را مورد پردازش قرار داده و از آن جهت دنبال نمودن هدف متحرک استفاده کرده ایم .

همانطور که می دانیم تصاویر دیجیتالی از عناصری بنام پیکسل تشکیل شده اند که در تصاویر رنگی هر پیکسل از سه مولفه R,G,B تشکیل شده اند . تصاویر خروجی ارسال شده از دوربین دارای فرمت RGB می باشد . در برنامه ای که به زبان ویژوال بیسیک نوشته شده ، پس از دریافت این تصاویر و پردازش آنها ، با توجه به موقعیت جسم متحرک در صفحه ، اطلاعاتی به یک کنترل کننده دوربین فرستاده می شود . این کنترل کننده از یک میکروکنترلر خانواده AVR به شماره Atmga16 استفاده می نماید و با کنترل یک موتور که به دوربین متصل می باشد آنرا همواره در جهت تعقیب هدف هدایت می نماید .

فهرست مطالب

چکیده1

مقدمه. 2

تصاویر دیجیتال. 4

تصاویر دیجیتال. 5

فرمت تصویر RGB.. 8

ویژوال بیسیک... 13

زبانی شیء گرا13

ویژوال بیسیک زبانی شیءگرا14

میکروکنترلر های AVR.. 22

مقدمه ای بر میکروکنترلرهای AVR.. 23

کامپایلر بسکام. 30

معرفی منوهای محیط BASCOM... 31

منوی FILE.. 31

مراجع104

پردازش دیجیتالی تصویر ، معرفی میکرو کنترلر 8051

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

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

پردازش دیجیتالی تصویر ، معرفی میکرو کنترلر 8051

پیشگفتار:

با ساخت وسایل الکترو مغناطیسی نظیر انواع الکتروموتورها، بوبین ها ،رله ها وغیریه ،انسان قادر شد با بهره گیری از الکترونیک  ، کنترل ابزارهای مکانیکی را در دست گیرد و سر انجام با پیدایش میکرو پروسسورها و با توجه به توانایی آنها در پردازش اطلاعات و اعمال کنترلی و همچنین قابلیت مهم برنامه پذیر بودن آنها تحول شگرفی در ساخت تجهیزات الکترونیکی و صنعتی وغیره به‌وجودآمد.

پیشرفت ها و تحولات اخیر باعث پیدایش اتوماسیون صنعتی شده که در بسیاری از موارد جایگزین نیروی انسانی می گردد.به عنوان نمونه انجام امور سخت در معادن و یا کارخانه ها و یا کارهایی که نیازمند دقت وسرعت بالا می‌باشد و یا انجام آن برای نیروی انسانی خطر آفرین است به انواع دستگاهها و رباتها سپرده شده است. همچنین با پیشرفت الکترونیک در زمینه ساخت سنسورها . بالا رفتن دقت آن ها،  امروزه انواع گوناگونی از حس گرها در دنیا تولید می شود که در ساخت رباتها و در زمینه اتوماسیون نقش مهمی را ایفا می‌کنند.
در این پایان نامه پس از مباحثی در مورد  پردازش دیجیتالی تصویر ، معرفی میکرو کنترلر 8051  بصورت مختصر و در حد نیاز و بخش کوچکی در مورد استپ موتورها  به طراحی وپیاده سازی نمونه ای کوچک از یک ماشین مسیر یاب پرداخته شده است .شایان ذکر است که مطالب مربوط به طراحی وساخت ماشین بگونه ای بیان شده که توسط هر فردی که آشنایی مختصری با میکرو کنترلرها داشته باشد، قابل پیاده سازی است.

در خاتمه از استاد گرانقدر جناب آقای همایون موتمنی و نیز تمام کسانی که  در این امر مرا یاری دادند، از جمله مهندس فیض ا... خاکپور و نیز دوست عزیزم مهدی جعفری ، تشکر و قدردانی می نمایم.

فصل اول 

آشنایی با ماشین بینایی و تصویر برداری د

1-1کلیات  

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

1-        ایجاد تصویر به شکل دیجیتالی

2-        بکارگیری تکنیکهای کامپیوتری جهت پردازش ویا اصلاح داده های تصویری

3-    بررسی و استفاده از نتایج پردازش شده برای اهدافی چون هدایت ربات یا کنترل نمودن تجهیزات خود کار ، کنترل کیفیت یک فرایند تولیدی ، یا فراهم آوردن اطلاعات جهت تجزیه و تحلیل آماری در یک سیستم تولیدی کامپیوتری (MAC)

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

در طی سه دهه گذشته تکنولوژی بینایی یا کامپیوتری بطور پراکنده در صنایع فضایی نظامی و بطور محدود در صنعت بکار برده شده است . جدید بودن تکنولوژی ، نبودن سیستم مقرون به صرفه  در بازار و نبودن متخصصین این رشته باعث شده است تا این تکنولوژی بطور گسترده استفاده نشود .

تا مدتی قبل دوربین ها و سنسورهای استفاده شده معمولا بصورت سفارشی ومخصوص ساخته می شدند تا بتوانند برا ی منظورخاصی مورد استفاده قرار گیرند همچنین فرایند ساخت مدارهای مجتمع بسیار بزرگ آنقدر پیشرفت نکرده بود تا سنسورهای حالت جامد با رزولوشن بالا ساخته شود .

استفاده از سنسورهای ذکر شده مستلزم این بود که نرم افزار ویژه ای برای آن تهیه شود و معمولا این نرم افزارها نیز نیاز به کامپیوتر هایی با توان پردازش بالا داشتند. علاوه بر همه این مطالب مهندسین مجبور بودند که آموزشهای لازم را پس از فراغت از تحصیل فرا گیرند . زیرا درس ماشین بینایی در سطح آموزشهای متداول مهندسی در دانشگاهها وبه شکل کلاسیک ارائه نمی شد .

تکنولوژی ماشین بینایی در دهه آینده تاثیر مهمی بر تمامی کارهای صنعتی خواهد گذاشت که دلیل آن پیشرفتهای تکنولوژی اخیر در زمینه های مرتبط با ماشین بینایی است واین پیشرفتها در حدی است که استفاده از این تکنولوژی هم اکنون حیاتی می باشد .

2-1-بینایی واتوماسیون کارخانه

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

1-        کنترل

2-        بازرسی

3-        ورود داده

کنترل در ساده ترین شکل آن مرتبط با تعیین موقعیت و ایجاد دستورات مناسب می باشد تا یک مکانیزم را تحریک نموده ویا عمل خاصی صورت گیرد . هدایت نقاله های هدایت شونده خود کار (AGVS) در عملیات انتقال مواد در یک کارخانه هدایت مشعل جوشکاری در امتداد یک شمایر یا لبه یا انتخاب یک سطح بخصوص برای انجام عملیات رنگ پاشی توسط ربات ، مثلهایی از بکار گیری ، ماشین بینایی در کنترل می باشند . کاربردهای ماشین بینایی در بازرسی مرتبط با تعیین برخی پارامترها می باشد . ابعاد مکانیکی وهمچنین شکل آن ، کیفیت سطوح ، تعداد سوراخها در یک قطعه ، وجود یاعدم وجود یک ویژگی یا یک قطعه در محل خاصی از جمله پارامترهایی هستند که توسط ماشین بینایی ممکن است ، بازرسی می شوند عمل اندازه گیری توسط ماشین بینایی کم و بیش مشابه بکار‌گیری روشهای سنتی استفاده از قیدها و سنجه های مخصوص و مقایسه ابعاد می باشد . سایر عملیات بازرسی بجز موارد اندازه گیری شامل مواردی چون کنترل وجود بر چسب بر روی محصول بررسی رنگ قطعه ، وجود مواد خارجی در محصولات غذایی نیز با تکنیکهای خاصی انجام می گیرد . کار بازرسی ممکن است حتی شامل مشخص نمودن خواص یا ویژگیهایی الکتریکی یک محصول گردد . با مشاهده خروجی اندازه گیرهای الکتریکی می توان صحت عملکرد محصولات الکتریکی را بازرسی نمود . هر چند که در چنین مواردی چنانچه سیستم بینایی کار دیگری بجز مورد ذکر شده انجام ندهد معمولا روش ساده تر و مقرون به صرفه ترین بدین صورت خواهد بود که کار بازرسی فوق توسط یک ریز پردازنده و ابزارهای مربوط انجام گیرد .

اطلاعات مربوط به کیفیت محصول ویا مواد وهمچنین تعقیب فرایند تولید را می توان توسط ماشین بینایی گرفته ودر بانک اطلاعاتی سیستم تولید کامپیوتری جامع بطور خود کار وارد نمود . این روش ورود اطلاعات بسیار دقیق و قابل اعتماد است که دلیل آن حذف نیروی انسانی از چرخه مزبور می باشد . علاوه بر این ورود اطلاعات بسیار مقرون به صرفه خواهد بود چرا که اطلاعات بلافاصله پس از بازرسی وبه عنوان بخشی از آن جمع آوری و منتقل می شوند .

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

3-1 سرعت واکنش

زمان مورد نیاز برای تصمیم گیری توسط ماشین بینایی بستگی به اندازه ماتریس تصویر یا زمان پردازش لازم در کارت تصویر گیر و نوع دوربین دارد . دوربیهایی نوع لاچکی که با استاندارد Rs-170 کار می کنند تعداد 30 تصویر در ثانیه تولید می کنند که این تصاویر بر روی مونیتورهای موجود در بازار قابل نمایش هستند . چنانچه از استاندارد Rs-170 استفاده نشود می توان تعداد تصاویر در ثانیه را پنج تا ده برابر افزایش داد . دوربینهای حالت جامد می توانند در زمان بسیار کوتاه معادل ( میکرو ثانیه تصویر گیری کنند زمان لازم جهت خواندن سیگنال تصویر از سنسور دوربین بستگی به اندازه ماتریس سنسور سرعت پردازش و پهنای باند سیستم دارد. با استفاده از تکنیکهای پردازش موازی می توان زمان پردازش را متناسب با تعداد پردازشگرهای موازی کاهش داد .

زمان واکنش سیستم بینایی انسان در حدود 6% ثانیه یا 16/1 ثانیه می باشد این موضوع توسط این حقیقت تائید می شود که وقتی تصاویر ، با سرعت 30 عدد در ثانیه یک صحنه متحرک را نشان می دهند چشم انسان قادر به تشخیص انقطاع بین تصاویر نیست .

سیستم های ماشین بینایی مورد استفاده در صنعت که برای کنترل بر چسب روی بطریها بکار می رود می توانند با سرعتی معادل 900 بطری در دقیقه یا در صورت یک بطری در 7% ثانیه کار کنند . البته می توان با گرفتن تصاویری که بیش از یک بطری را در بر می گیرد سرعت کنترل را بیش از این نیز افزایش داد . سرعت چشم انسان برای انجام کار مشابه حداکثر 60 بطری در دقیقه می باشد که این سرعت در اثر خستگی و شرایط نامساعد محیطی کاهش نیز می یابد .

بطور خلاصه تصویر گیری توسط ماشین بینایی تقریبا 10 برابر سرعت بینایی انسان می باشد این نسبت با پیشرفت تکنولوژی در علوم الکترونیک رو به افزایش می باشد در حالیکه سرعت چشم انسان مقدار مشخصی است سرعت انجام فرایند کامل توسط ماشین بینایی در حدود 15 برابر چشم انسان می باشد .

4-1 واکنش طیف موج

چشم انسان فقط در مقابل نور قابل رویت که طیف محدودی است می تواند اشیاء را ببیند . دامن دید از طول موج بنفش در 390 میکرون تا طول موج قرمز در 790 میلی میکرون می باشد
 واکنش سیستم ماشین بینایی در مقایسه با چشم انسان بسیار وسیع تر بوده و دامنه از پرتو گاما و X در منطقه طول موج کوتاه شروع شده وتا طول موج مادون قرمز در قسمت طول موجهای طویلی ختم می شود .

توانایی چشم انسان در تشخیص رنگها و پیچیده بوده ودر هنگام تشخیص رنگ مولفه های آن بطور مجزا در نظر گرفته نمی شوند . در عوض میانگین ، انرژی در طول موجهای مختلف مورد استفاده قرار گرفته ورنگ دیده شده یکی از طول موجهای مابین آنها می باشد .

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

ذخیره سازی تصاویر رنگی به حافظه ای معادل سه برابر تصاویر غیر رنگی نیاز دارد .

همچنین حجم پردازش تصاویر رنگی که حاوی اجزاء B,G,R می باشند در مقایسه با تصاویر یک رنگ بیشتر می باشد .

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

5-1مقایسه بینایی انسان و ماشین بینایی

ماشین	انسان
محدود به تنظیمات اولیه ،نیازمند داده های عددی	بسیار تطبیق پذیر وانعطاف پذیر در مقابل نوع کار و ورود اطلاعات	انعطاف پذیری
قادر به اندازه گیری ابعادی می باشد مثال : طول یک قطعه برحسب تعداد پیکسل	قادر به تخمین نسبتا دقیق موارد توصیفی مثل : تشخیص میوه بد از روی رنگ و شکل آن	توانایی
اندازه گیری مقدار هر یک از R,B	بیان توصیفی از رنگ	رنگ
حساس به فرکانس و سطح روشنایی	قابلیت تطبیق ، باشرایط نوری ،خواص فیزیکی	حالت

ماشین	انسان
حساس به خواص فیزیکی سطح جسم ، قابلیت بیان سطح خاکستری به صورت عددی دقیق و مشخص ،براحتی قادر به تشخیص 256 سطح خاکستری می باشد	سطح اجسام و فاصله تا جسم ، محدودیت در توانایی تشخیص مقدار سطوح خاکستری بستگی به بیننده دارد و ممکن است در یک زمان متفاوت از زمان دیگر باشد مقدار سطوح خاکستری قابل تشخیص بین 7 تا 10 می باشد	حساسیت
بسیار بالا که البته بستگی به پردازشگر مورد استفاده و پهنای بانددارد سرعت واکنش در حدود    ثانیه بوده وسرعتهای بالاتر نیز از نظر تکنیکی قابل دسترسی است.	سرعت واکنش کند و حداکثر در حدود 10/1ثانیه می باشد	واکنش
صحنه های دو بعدی براحتی قابل تشخیص می باشد ودر صحنه های سه بعدی براحتی مقدور نیست و نیازمند به 2 دوربین بوده وسرعت نیز کم است .	صحنه های سه بعدی براحتی قابل درک می باشد	دو و سه بعدی
اطلاعات اخذ شده بطور خودکار و مداوم وارد بانک اطلاعاتی می شود ، انتقال ورود و اطلاعات دقیق و کم هزینه می باشد.	اطلاعات اخذ شده می بایستی بطور دستی انتقال داده شود هزینه انتقال و ورود اطلاعات زیاد بوده و میزان خطا زیاد می باشد .	خروج داده ها
می تواند به هر دو صورت خطی و لگاریتمی دریافت کند . محدوده طیف از طول موجهای پائین پرتو تا طول موجهای بالای مادون قرمز می باشد .	براساس مقیاس لگاریتمی است و متاثر از رنگ زمینه می باشد محدود به طیف قابل رویت از 300 تا 700میلی میکرون	دریافت داده ها طول موج

6-1 سیستم بینایی چیست ؟

1-6-1 کلیات سیستم

یک سیستم ماشین بینایی شامل تمام اجزاء لازم بمنظور تهیه ، تعریف دیجیتالی یک تصویر تغییر واصلاح داده ها وارائه نمایش داده های تصویری دیجیتالی به دنیای بیرون می باشد چنین سیستمی چنانچه در یک محیط صنعتی بکار گرفته شود ، ممکن است به دلیل اینکه متصل به سایر تجهیزات خط تولید می باشد بسیار پیچیده بنظر می رسد ولی اگر چنانچه با توجه به نقش و وظیفه سیستم بینایی اجزاء اصلی تشکیل دهنده آن بیان شوند ، مشخص خواهد شد که پیچیدگی زیادی در سیستم وجود ندارد اجزاء اصلی سیستم شامل سه قسمت اصلی است :

1-          قسمت تصویر برداری

2-          پردازش

3-          نمایش یا وسایل خروجی اطلاعات

2-6-1 تصویر گیری

تصویر گیری در ماشین بینایی یعنی تبدیل اطلاعات تصویری یک شئی فیزیکی و خواص ظاهری آن بصورت داده های عددی است بگونه ای که این تصویر می تواند از توسط پردازشگر پردازش شود تصویر گیری ممکن است شامل چهار فرایند زیر باشد :

1-    نور پردازی

2-    تشکیل تصویر یا متمرکز کردن آن

3-    تبدیل تصویر به سیگنالهای الکتریکی

4-    قالب بندی کردن سیگنال خروجی تصویر

3-6-1 نور پردازی

نور پردازی یک عامل کلیدی وتاثیر گذ ار بر روی کیفیت تصویر تشکیل شده است که به عنوان ورودی ماشین بینایی مورد استفاده قرار می گیرد ممکن است تا 30 درصد حجم کار و تلاش طراحی اجزاء یک سیستم ماشین بینایی را بخود اختصاص دهد .

بسیاری از سیستم های ماشین بینایی که در گذشته در صنعت بکار رفته اند از نور قابل رویت استفاده کرده اند که علت آن از یک طرف در دسترس بودن آن واز طرف دیگر خود کار نمودن عمل بازرسی که قبلا توسط کارگر انجام می شده است می باشد بازرسی توسط کارگر براساس توانایی چشم ودر محدوده طول موج نور قابل رویت می باشد چهار نوع لامپ از لامپهایی که نور قابل رویت تولید می کنند واغلب در صنعت استفاده شده اند عبارتند از : لامپهای التهابی فلورسنت بخار جیوه وبخار سدیم استفاده از نور غیر قابل رویت شبیه اشعه ایکس ماوراء بنفش و مادون قرمز بدلیل نیاز به انجام بررسی های ویژه که توسط نور قابل رویت انجام پذیر نیست ، روبه افزایش است روشهای نور پردازی جهت کار بردهای صنعتی ماشین بینایی شامل چهار دسته زیر است :

1-    نور پردازی از پشت

2-    نور پردازی از مقابل

3-    نور پردازی دارای ساختار

4-    نور پردازی لحظه ای

نور پیرامون محیط کار که منابعی بجز منبع اصلی نور پردازی سیستم ماشین بینایی بر مجموع میزان نور تابیده شده برجسم اثر گذاشته وبطور کلی بصورت نویز در داده های تصویری ظاهر می شود .

برای کم کردن تاثیر نور پیرامونی می توان از پرده نوری یا دیواره های محافظ استفاده نمود تا از ورود آن به لنز دوربین جلوگیری شود .

1-3-6-1 نور پردازی از پشت :

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

 (شکل 1-1)

مزیت نور پردازی از پشت ایجاد تصاویر با کنتر است بالاو تفکیک آسان مرز جسم می باشد کنتر است بالاباعث کم شدن پردازش های بعدی شده همچنین از حساسیت سیستم به تغییرات نوردهی منبع نور می کاهد در مورد نور پردازی اجسامی که مسطح نیستند ممکن است لازم باشد تا با استفاده از عدسی های مناسب نور به جسم تابانده شود .

روش نور دهی از پشت برای اعمالی از قبیل تشخیص ترک ، مک و وجود اشیاء خارجی در قطعات شفاف ایده آل می باشد . تشخیص ترک الستخوان در تصاویر اشعه X واندازه گیری میزان تنش انرژی و حرارتی از یک ساختمان توسط پرتو مادون قرمز از جمله مثالهای این روش نور پردازی می باشند .

اساسا تصویر حاصل از روش نور دهی از پشت تک رنگ است با توجه به اینکه لب های تصویر بگونه ای بر روی صفحه سنسور تشکیل تصویر می دهند که ممکن است یک پیکسل کامل را پر نکنند .

بنابراین این پیکسلها دارای مقادیر حدود سطحی بین سیاه و سفید مطلق خواهند بود به عنوان مثال مقدار عددی پیکسل که 50 درصد آن توسط جسم پوشیده شده است در یک سیستم دارای 16 سطح خاکستری معادل عدد 7 خواهد بود و بطور کلی مقدار عددی هر پیکسل که نشانگر مرزهای قطعه باشد متناسب با مقدار پوشش آن خواهد بود شی نشان داده شده در صفحه بعد در قسمت مرزها ، فقط بخشی از مساحت پیکسلها را پوششی می دهد که مقادیر عددی پیکسلها یا همان سطح خاکستری بدست آمده برای پیکسلها در ماتریس تصویر نشان داده شده است شایان ذکر است که مقدار عددی پیکسلها وهمچنین مقدار کاهش یافته آن نمی تواند هیچگونه اطلاعاتی در خصوص شکل قطعه ارادئه دهد و بایستی اطلاعات مربوط به اینکه چه شکلی در مقابل دوربین قرار گرفته است با مقادیر عددی پیکسلها توام گردد.

بهینه‌سازی و پردازش پرس و جو در این تحقیق ما به تکنیک‌های بکار رفته توسط DMBS

بهینه‌سازی و پردازش پرس و جو در این تحقیق ما به تکنیک‌های بکار رفته توسط DMBS برای پردازش، بهینه‌سازی و اجرای پرس و جوهای سطح بالا می‌پردازیم پرس و جوی بیان شده در زبان پرس‌و جوی سطح بالا مثل SQL ابتدا باید پویش و تجزیه معتبر شود

دسته بندی	کامپیوتر و IT
فرمت فایل	doc
حجم فایل	458 کیلو بایت
تعداد صفحات فایل	68

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

در این تحقیق ما به تکنیک‌های بکار رفته توسط 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،‌ می‌توانند برای بازیابی ثبت‌ها در دامنه معین بکار روند برای مثال    پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به می‌شوند.

متدهای جستجو برای  انتخاب پیچیده: 

اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشکیل شود، ‌DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده کند: 

S7: انتخاب تقارنی  یا ارتباطی با استفاده از شاخص اختصاص:‌ اگر ویژگی شامل شده در هر شرط ساده متکی در شرط تقارنی، مسیر دستیابی داشته باشد که به کاربرد یکی از متدهای S2 تا S6 امکان عمل دهد، از آن شرط برای بازیابی ثبت‌های استفاده کنید و بعد کنترل کنید  آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌کند یا خیر. 

S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مرکب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مرکب در فیلدهای مرکب وجود داشته باشد، برای مثال اگر شاخص روی کلید مرکب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره کرد.

در این تحقیق ما به تکنیک‌های بکار رفته توسط 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،‌ می‌توانند برای بازیابی ثبت‌ها در دامنه معین بکار روند برای مثال    پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به می‌شوند.متدهای جستجو برای  انتخاب پیچیده: اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشکیل شود، ‌DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده کند: S7: انتخاب تقارنی  یا ارتباطی با استفاده از شاخص اختصاص:‌ اگر ویژگی شامل شده در هر شرط ساده متکی در شرط تقارنی، مسیر دستیابی داشته باشد که به کاربرد یکی از متدهای S2 تا S6 امکان عمل دهد، از آن شرط برای بازیابی ثبت‌های استفاده کنید و بعد کنترل کنید  آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌کند یا خیر. S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مرکب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مرکب در فیلدهای مرکب وجود داشته باشد، برای مثال اگر شاخص روی کلید مرکب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره کرد.

در این تحقیق ما به تکنیک‌های بکار رفته توسط 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،‌ می‌توانند برای بازیابی ثبت‌ها در دامنه معین بکار روند برای مثال    پرس و جوها شامل این شرط‌ها، پرس وجوهای دامنه نیامد به می‌شوند.متدهای جستجو برای  انتخاب پیچیده: اگر شرط عملیات SELECT، شرط تقارنی و مرتبط باشد، در اینصورت اگر از چندین شرط ساده در ارتباط با ارتباط منطقی and مثل op4 فوق تشکیل شود، ‌DBM می‌تواند از متدهای اضافی زیر برای اجرای عملیات استفاده کند: S7: انتخاب تقارنی  یا ارتباطی با استفاده از شاخص اختصاص:‌ اگر ویژگی شامل شده در هر شرط ساده متکی در شرط تقارنی، مسیر دستیابی داشته باشد که به کاربرد یکی از متدهای S2 تا S6 امکان عمل دهد، از آن شرط برای بازیابی ثبت‌های استفاده کنید و بعد کنترل کنید  آیا هر ثبت بازیابی شد، شرایط ساده باقیمانده در شرط تقارنی را برآورده می‌کند یا خیر. S8 : انتخاب تقارنی (ارتباطی) با استفاده از شاخص مرکب: اگر دو یا چند ویژگی در شرایط تساوی در شرط تفاوتی شامل شدند و شاخص مرکب در فیلدهای مرکب وجود داشته باشد، برای مثال اگر شاخص روی کلید مرکب (ESSN, PNO) در فایل Works ON برای OPS ایجاد شده باشد، می توان از شاخص مستقیماً اشاره کرد.

XML دانلود ترجمه مقاله یک الگوریتم پارتیشن بندی جدید برای بهبود عملکرد پردازش امنیتی پیام SOAP

ترجمه مقاله یک الگوریتم پارتیشن بندی جدید برای بهبود عملکرد پردازش امنیتی پیام SOAP ترجمه این مقاله به صورت ورد و در 8 صفحه است فایل دانلودی پس از خرید در فرمت زیپ است که شامل فایل ورد و پی دی اف ترجمه و فایل پی دی اف مقاله اصلی به زبان انگلیسی است

دسته بندی	کامپیوتر و IT
فرمت فایل	zip
حجم فایل	870 کیلو بایت
تعداد صفحات فایل	6

A New Partitioning Algorithm to Enhance Performance of SOAP Message Security Processing

Abstract: Web Service Security (WS-Security) processing suffers from performance bottleneck. With large data centric web services and hardened schema it becomes even worst. A new partitioning algorithm with parallel stream based security processing model is developed for large Simple Object Access Protocol (SOAP) messages. The aim is to partition SOAP message and to distribute the processing load on multiple cores in order to enhance the performance of SOAP message security processing. There are several steps involved in this approach but SOAP message partitioning is mainly focused in this paper. Since the efficiency of SOAP security processing depends on both Extensible Markup Language (XML) data size and its structure, these factors are considered while developing partitioning algorithm. Each partitioned SOAP message data is uniformly distributed to parallel running instances of stream based security processor so that the load among cores can be balanced. It is observed from the results that the implementation of new partitioning algorithm with parallel stream based WS-Security processing model has significantly improved the performance of SOAP message security processing. The fundamental approach presented in this paper is useful for efficient security processing of large SOAP messages. Keywords: Web Services, WS-Security, SOAP message processing, XML security, XML data partitioning.

ترجمه چکیده مقاله:

چکیده:

پردازش امنیت خدمات وب (امنیت-WS) تحت تاثیر تنگنای عملکرد می باشد. با خدمات گسترده وب داده محور و طرح های سخت افزاری، حتی بدتر هم می شود. یک الگوریتم پارتیشن بندی جدید با مدل پردازش امنیت مبتنی بر جریان های موازی برای پیام های پروتکل دسترسی شی ساده (SOAP) توسعه می یابد. هدف این است که پیام SOAP را پارتیشن بندی کنید و بار پردازشی را در هسته های چندگانه به منظور بهبود عملکرد پردازش امنیت پیام SOAP توزیع کنید. چند مرحله در این روش وجود دارد اما عمدتا در این مقاله بر پارتیشن بندی پیام SOAP تمرکز می شود. از آنجا که بهره وری پردازش امنیتی SOAP ، هم به اندازه داده های زبان نشانه گذاری امتدادپذیر (XML) و هم ساختار آن بستگی دارد، این عوامل هنگام توسعه الگوریتم پارتیشن بندی در نظر گرفته می شوند. هر داده پیام SOAP پارتیشن بندی شده، به صورت یکنواخت به نمونه های اجرای موازی جریان براساس پردازنده امنیتی توزیع می شوند تا اینکه این بار را بتوان در میان هسته ها متوازن کرد. از نتایج مشاهده می شود که اجرای الگوریتم پارتیشن بندی جدید با جریان موازی مبتنی بر مدل پردازش امنیت-WS، به صورت قابل توجهی عملکرد پردازش امنیت پیام SOAP را بهبود داده است. رویکرد اساسی که در این مقاله ارائه شد، برای پردازش امنیتی کارآمد پیام های گسترده SOAP، مفید می باشد.

کلمات کلیدی:

خدمات وب، امنیت-WS، پردازش پیام SOAP، امنیت XML، پارتیشن بندی داده های XML

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

بررسی طراحی و ساخت شمارنده فرکانس تا یک گیگاهرتز اصولا عمل یا حاصل مقایسه یک کمیت مفروض با یک استاندارد از پیش تعیین شده را ، اندازه گیری می نامیم برای این که نتیجه عمل اندازه گیری که با اعداد بیان می شود، معنی داشته باشد، باید اولا استانداردی که برای مقایسه به کار می رود، دقیقا معلوم ومورد قبول عام واقع شده باشد ثانیا روش استفاده شده برای این مقایسه باید قابل تکرار بوده و قادر به امتحان کردن د

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

فصل اول

اندازه گیری فرکانس 

1-1- ویژگی های دستگاه اندازه گیری

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

هر دستگاه اندازه گیری دارای ویژگی ها و محدودیت های خاص خود است و برای انتخاب دستگاه اندازه گیری باید کلیه جوانب در نظر گرفته شود و با توجه به و یژگی های مورد نیاز و قیمت دستگاه  اندازه گیری بهترین انتخاب انجام شود.

1-گستره ی اندازه گیری: محدوده ای از تغییرات کمیت تحت اندازه گیری که وسیله قادر به اندازه گیری آن می باشد.

2-ریزنگری یا تفکیک پذیری: کوچکترین اندازه ی تغییرات کمیت تحت اندازه گیری که می تواند توسط            دستگاه، اندازه گیری شود.

3-حساسیت: نسبت میزان تغییرات خروجی به تغییرات کمیت تحت اندازه گیری

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

4-درستی: میزان نزدیکی مقدار قرائت شده با مقدار واقعی کمیت

  معمولا با افزایش گستره ی اندازه گیری درستی کم میشود(یا قیمت ها افزایش قابل توجه می یابد)

5-دقت: نشان دهنده ی میزان پراکندگی آماری مقادیر اندازه گیری شده در چندین بار اندازه گیری یک کمیت است. به عبارت دیگر میزان عاری بودن اندازه گیر از خطای تصادفی میزان دقت را نشان می دهد.

                                      2.473                                2.472

                                      2.563                                2.475                                    

                                      2.425                                2.479        

                                  دقت کمتر                               دقت بیشتر

در شکل (1-1) نمایش مفهومی دقت و درستی مشاهده می شود.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          

                دقت مناسب                                   دقت نامناسب                          دقت مناسب

               درستی مناسب                                درستی نامناسب                        درستی نامناسب

شکل 1-1-نمایش دقت و درستی

1-2- کالیبراسیون(برسنجیدن)

مقایسه عملکرد دستگاه اندازه گیری با مرجع استاندارد (که در رده ی درستی بالاتری قرار دارد) جهت تعیین خطای آن را کالیبراسیون گویند. به عبارت دیگر کالیبراسیون، کنترل دستگاه اندازه گیری به منظور اطمینان از عملکرد مناسب آن است. مرجع استاندارد می تواند یک کمیت یا دستگاه اندازه گیری باشد.

1-3- تنظیم دستگاه اندازه گیری

معمولا در دستگاه های اندازه گیری امکان تنظیم ( به صورت محدود) گذاشته می شود تا در مواردی که اندازه گیر از حالت کالیبره خارج می شود، عملکرد آن را اصلاح کنند. تنظیم می تواند به صورت تنظیم شیب یا آفست باشد.

1-4- قسمت های مختلف دستگاه های اندازه گیری

کار اکثر سیستم های اندازه گیری را می توان در قالب سه مرحله ی اساسی قرار داد:

1-مرحله ی آشکارسازی و مبدل

2-مرحله ی میانی یا تغییر دهنده

3-مرحله ی نمایش، ثبت یا کنترل

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

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

مرحله ی نهایی می تواند شامل قسمت هایی مثل عقربه واشل، لامپ اشعه کاتدی، ستون مایع، قلم متحرک وکاغذ مدرج،  ضبط مغناطیسی و .... باشد. علاوه بر نمایش دهنده  و ضبط کننده که در مرحله ی آخر وجود دارند، از خروجی این بخش می توان برای کنترل قسمت های دیگر استفاده کرد.

در شکل (1-2 ) قسمت های مختلف یک دستگاه اندازه گیری به صورت کلی نمایش داده شده است.

شکل 1-2-قسمت های مختلف دستگاه اندازه گیری

1-5- اندازه گیری فرکانس

یکی از مهم ترین کمیت ها در سیستم های الکتریکی و الکترونیکی فرکانس می باشد. در مدارات مخابراتی فرکانس سیگنال در قسمت های مختلف نقش مهمی را ایفا می کند ودر مراحل مختلف مدولاسیون، دمدولاسیون و پخش باید کنترل واندازه گیری شود. در سیستم های قدرت تغیر فرکانس می تواند باعث تغییر عملکرد سیستم شود، با افزایش فرکانس حجم هسته کاهش می یابد ولی امکان دارد سیستم توانایی تولید گشتاور مورد نیاز را از دست بدهد وهمچنین کاهش فرکانس می تواند باعث به اشباع رفتن هسته و آسیب رسیدن به سیستم شود، بنابراین در سیستم های قدرت هم باید فرکانس به طور دقیق اندازه گیری و کنترل شود. در سیستم های ابزار دقیق برای انتقال سیگنال با تبدیل ولتاژ به فرکانس اثرات نویز را کاهش می دهند.

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

1-6- تقسیم بندی باندها وفرکانس ها

فرکانس های رادیویی مطابق جدول زیر تقسیم بندی شده اند:

گستره ی فرکانسی	نمادها
3-30 KHz	VLF(Very Low Frequency)
30-300 KHz	LF(Low Frequency)
300-3000 KHz	MF(Main Frequency)
3-30 MHz	HF(High Frequency)
30-300 MHz	VHF(Very high Frequency)
300-3000 MHz	UHF(Ultra high Frequency)
3-30 GHz	SHF(Super high Frequency)
30-300 GHz	EHF(Extra high Frequency)

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

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

1-7- فرکانس متر هاو مدارات ارائه شده برای آن

اصولا یکی از ابزار های مهم که در بخش های مهم سیستم های الکترونیکی و مخابراتی به کار گرفته می شود، فرکانس متر می باشد. این ابزار می تواند به صورت آنالوگ یا دیجیتال پیاده سازی گردد، نکته ی مهم درپیاده سازی این ابزار توجه به محل استفاده و نیز محدوده ی فرکانسی مورد نظر می باشد.

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

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

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

1-7-1- فرکانس متر های آنالوگ

این ابزارها شامل یک بخش آشکار ساز می باشند که در این بخش سیگنال های با فرکانس بالا (از آنجا که بیشتر در فرکانس های مایکرویو کاربرد دارند) به یک دیود آشکارساز می تابد واین دیود توان یا ولتاژ متناسب با آن فرکانس را ارائه می دهد.

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

نوع دیگر این دیودها avalanche-transit-time diodes می باشد. این دیودها ساختار متفاوتی با دیودهای معمولی دارند، این دیودها دارای چهار لایه می باشند که به صورت  شکل (1-3) می باشند.

شکل 1-3-ساختار کلی دیود

برای آشنایی بیشتر با این دیودها توضیحات مختصری در ادامه آورده شده است:

دیودهای PIN:

این خانواده از دیودها به عنوان مقاومتی متغیر در فرکانس های مایکروویوی کاربرد دارند. این دیودها این قابلیت را دارند که بدون ایجاد اعوجاج در سیگنالهای مایکروویوی مقاومت مسیر خود را تغییر دهند که این کار با تغییر جریان dc دیود انجام می شود. از ویژگی مهم دیگر این سری از دیودها، قابلیت کنترل سیگنالهای مایکروویوی با دامنه زیاد می باشد. بخش میانی آن تأثیر زیادی در دوام آن و عدم ایجاد اختلال در امواج دریافتی خواهد داشت.

در شکل (1-4) شمای کلی این نوع دیود نشان داده شده است.

شکل 1-4-شمای کلی دیود PIN

شکل (1-5 ) مدار معادل دیود در حالت بایاس مستقیم را نشان می دهد. در این حالت مقاومت R_S  با جریان dc عبوری از دیود رابطه ی عکس دارد.

شکل 1-5-بایاس مستقیم

شکل (1-6 ) مدار معادل دیود در حالت بایاس معکوس را نشان می دهد. در این حالت دیود مانند یک خازن با صفحات موازی و مستقل از ولتاژ بایاس معکوس عمل می کند. در کنار خازن یک مقاومت R_P نیز وجود دارد که بیانگر تلفات در بایاس معکوس است.

شکل 1-6-بایاس معکوس

در مرحله بعدی توان دریافت شده به بخش آشکارساز انتقال می یابد. بخش آشکار ساز حساسیت بالایی دارد و در برخی از موارد و در کاربردهای موجبری و برای اندازه گیری توان منابع مایکروویوی  به دلیل خروجی توان بالایی آن از  انتقالی magic-T استفاده می گردد تا توان خروجی را به میزان مطلوب برای آشکار ساز کاهش دهند. شکل ( 1-7) این قطعه(magic-T ) را نشان می دهد.

شکل1-7-MAGIC-T

البته به جز magic-T ممکن است بسته به نوع خروجی سیگنال از تضعیف کننده های دیگری نیز در صورت نیاز استفاده شود . محل قرار گرفتن این تضعیف کننده ها بسته به موارد کاربرد  مختلف می باشد. بعد از مرحله بالا عملکردهای پردازش وارد سیستم خواهند شد. این عملکردها می توانند به طور کامل دیجیتال یا آنالوگ باشند. که بسته به محل استفاده و نوع مدار می توان  هر یک از بخش ها را مورد استفاده قرار داد.

1-7-2- فرکانس متر های دیجیتال

این گروه از فرکانس متر ها به شکل های مختلف قابل پیاده سازی می باشند. معمولا در انواع پیشرفته ی آن از پردازنده های قوی و پرسرعت استفاده میشود0 انعطاف پذیری این دسته، بسته به فرکانس کاری پردازنده بالا می باشد. علاوه بر استفاده از این پردازشگر ها این امکان را می دهد تا علاوه بر عملیات تعیین فرکانسی برای عملکرد های همزمان دیگر نیز از آن بهره گرفته شود. صورت های دیگری همچون پیاده سازی با گیت ها نیز در برخی موارد مورد استفاده قرار می گیرد که به دلیل حجم زیاد کمتر مورد توجه قرار می گیرد، مگر اینکه این توابع توسط پردازنده هایی با بلوک های گیتی (همچون FPGA و CPLDها) پیاده سازی گردند. مزیت این پردازنده ها سرعت بالای آنها است که این خاصیت به اندازه گیری فرکانس های بالا کمک می کند.

به طور خلاصه عملکرد این سری از مدارها به دو صورت می باشد که باتوجه به مورد استفاده ی آن ممکن است هر یک از آنها انتخاب گردد.

اولین روش آن استفاده از تایمر ومحاسبه ی زمان، از زمان اولین پرش تا پرش بعدی می باشد. به عبارتی دقیقا یک پریود اندازه گیری شده واز روی آن فرکانس تعیین می گردد. واضح است که در این روش با توجه به قابلیت وقفه در پردازنده ها زمان انتظار زیادی مورد نیاز نمی باشد ومعمولا در سیستم هایی مورد استفاده قرار می گیرد که نیاز به سرعت پردازش بالا می باشد. مسلما چنین سیستمی دارای دقت پایین تری خواهد بود، البته برای فرکانس های پایین بسیار مناسب عمل می کند اما در فرکانس های بالا ممکن است با مشکل مواجه شود.

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

در این پروژه از روش دوم برای طراحی فرکانس متر استفاده شده است و برای قسمت پردازنده ی آن از میکروکنترلر AVR استفاده شده است.

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

فصل دوم

پیش تقسیم کننده و شکل دهنده ی سیگنال

2-1- بخش تقسیم کننده ی فرکانس

اصولا مدارات الکترونیکی امکان کار در هر فرکانسی را ندارند و در یک محدوده ی فرکانسی معین کار می کنند. بنابراین برای اندازه گیری فرکانس های بالا ابتدا بایستی با استفاده از پیش تقسیم کننده فرکانس را با نسبت معین کاهش داده و سپس به مدارات شمارنده ی فرکانس داده شود. معمولا شمارنده های فرکانس رادیویی و مایکروویوی به پیش تقسیم کننده نیاز دارند.

اساس کار مدار تقسیم کننده ی فرکانسی با استفاده از شمارنده ها می باشد. شمارنده ها به این صورت عمل می کنند که با اعمال پالس ورودی پایه های آن تغییر وضعیت می دهند و یک رشته اعداد را دنبال میکنند. هر شمارنده با توجه به مدار خود دارای یک دنباله ی اعداد مخصوص به خود است که با توجه به این دنباله ها می توانیم از شمارنده ها استفاده کنیم. مثلا وضعیت پایه های خروجی یک شمارنده ی دودویی به صورت زیر است:

                                                 A₀             A₁             A₂                 A₃                                     0        0        0                                                 0                                             1        0        0        0                                                                              0          1            0       0                                    1        1                                                 0          0                                           0        0        1        0                                                                                 1            0       1        0                                    0                                                 1          1          0                                        1        1        1        0                                                                                       0       0        0        1                                                                            .           .           .             .                                    .         .         .                                                 .                                              .         .         .         .        

                رشته شمارش دودویی

با در نظر گرفتن شکل کلی برای شمارنده ها، همان گونه که در شکل (2-1) و (2-2) نشان داده شده است با استفاده از خروجی های A₀، A₁، A₂، A₃، 000 می توان انواع تقسیم های فرکانسی را به دست آورد:

شکل 2-1-شمارنده ونسبت تقسیم های به دست آمده

شکل 2-2-شکل موج پایه های شمارنده

 یک شمارنده ساده چهاربیتی ساده بااستفاده از فیلیپ فلاپ نوع D می تواند به صورت شکل ( 2-3) باشد.

شکل 2-3-شمارنده 4 بیتی

در تراشه های مقسم فرکانس که کاربرد های زیادی در مدارات مختلف دارند (مثلا در حلقه های قفل شونده در فاز ) علاوه بر قسمت شمارنده که قسمت  میانی است،  طبقه ی ورودی و خروجی  هم اضافه   می شوند. همچنین در اغلب این تراشه ها علاوه بر پایه های ورودی و خروجی وتغذیه پایه هایی هم برای انتخاب نسبت تقسیم در نظر گرفته میشوند.

 شماتیک کلی تراشه های تقسیم کننده ی فرکانس را می توان به صورت  شکل (2-4 ) در نظر گرفت:

شکل2-4-بلوک دیاگرام کلی تقسیم کننده ها

2-1-1- معرفی تقسیم کننده SP8704

تراشه تقسیم کننده ای که در این پروژه استفاده شده است، تراشه ای به نام SP8704 می باشد که دارای مشخصات زیر می باشد:

• عملکرد فرکانسی تا فرکانس 950 مگاهرتز
• کار با ولتاژ تغذیه ی 3 تا 5 ولت
• جریان ورودی کم
• حفاظت ESD (تخلیه ی الکترواستاتیکی) روی تمام پایه ها
• دارای چهار مد کاری تقسیم بر 64، 65، 128، 129
• کار در دمای 40- تا 85 درجه ی سانتیگراد

محدودیت ها :

• ماکزیمم ولتاژ تغذیه ی 7 ولت
• حداکثر ولتاژ ورودی5/2 ولت پیک تا پیک
• حداکثر محدوده ی دمایی 55- تا 125 درجه ی سانتیگراد
• حداکثر دمای پیوند 175 درجه ی سانتیگراد

تعیین نسبت تقسیم به صورت زیر می باشد:

نسبت تقسیم	پایه6	پایه 3
129	L	L
128	H	L
65	L	H
64	H	H

جدول 2-1-نسبت تقسیم تراشه

در این تراشه با تغییر ولتاژ منطقی روی پایه های 3 و 6 مطابق جدول فوق می توان نسبت تقسیم را تغییر داد. سیگنال خروجی این تراشه پالسی شکل و ضعیف می باشد.

2-2- قسمت تقویت و شکل دهی سیگنال

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

شکل 2-5-بخش تقویت و شکل دهی سیگنال

مدار قسمت A یک تقویت کننده با بهره ی بالا است.

نوع فیدبک: موازی – موازی

در این تقویت کننده با تغییر مقاومت R₁   می توان نقطه ی کار مدار را تغییر داد و به این وسیله THD موج خروجی را تغییر داد.

شکل 2-6-تعیین نقطه کار ترانزیستور

در مرحله ی بعدی بایستی موج خروجی از تقویت کننده به یک پالس TTL با شکل مناسب تبدیل شود. برای این کار از اشمیت تریگر از استفاده شده است، اشمیت تریگر یک مدار الکترونیکی دو سطحی است که دارای منحنی هیسترزیس است. با توجه به منحنی هیسترزیس این نوع مدارات اگر سیگنال ورودی آن از یک مقدار مشخص بیشتر شود سیگنال خروجی به سطح دیگر پرش می کند و اگر سیگنال ورودی از یک مقدار مشخص  کمتر شود سیگنال خروجی به سطح دیگر ولتاژ پرش می کند و به این وسیله از اثرگذاری  نویز  بر روی سیگنال جلوگیری به عمل می آید.

در مداراتی که به اشمیت تریگر نیاز می باشد می توان از مدارات اشمیت تریگر آماده موجود در بازار که به صورت تراشه می باشند استفاده کرد. در این پروژه از تراشه 7414 که به صورت NAND اشمیت تریگر می باشد، استفاده شده است. منحنی هیسترزیس این تراشه به صورت شکل (2-7 ) است.