ارائه روش جديد زمانبندی قواعد در پايگاه داده پويا

صفحه 1:
® Dew Rue Crbkeduiay Opprowk bused oo Csivutos oP Rub Cxevuton Probublliy 1 Brive Outubuse Gystew 5 دانشجو: عباس رسول زادگان استاد راهنما: دکتر احمد عبداله زاده 03/11/1385 0 ‏لاي‎ Dover: of 1| ‏مسج 0 , ماسجا‎ (Canpeeriny Pandy, htc Osten baborstny 

صفحه 2:
روش پيشنهادي این پایان نامه محیط شبیه سازي پایگاه داده پویا (۸55) بستر آزمایشات يارامترهاي ارزيابي مقايسه تطبيقي انتيجه كيري دستاوردهاي بايان نامه كارهاي آيتده مراجع مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 3:
‎shoal soley as‏ قواعد در کزايي سیستم بابگاهدده وا عدم وجود يك روش با كارابي لازم براى يمانبندي قواعد ‏هدف ‏طراحى و يياده سازى الكوريتمى براى بهبود فرايند زمانبتدي فواعد در سيستم بايكاه دادة بويا ‎ ‎ 

صفحه 4:
لا سیستم مدیریت پایگاه داده ایستا ‎Ml‏ نداشتن ابتکار عمل در هنگام رخ دادن شرایط خاص در سب ‏انجام دادن اعمللي نظیر پرس و جوء بهنگام سازي, درج» حذف گزارش گيري و غیره فقط هر زمان که صریحا توسط کاربر درخواست شوند ‎ ‎ ‎ll‏ سیستم مدیریت پایگاه داده پویا ‏6 داشتن امکان تعریف مجموعه اي از رویدادها و واکنش هاي متناظر آنها به منظور انجام واکنش مقتضي در صورت وقوع رويدادي خاص به صورت خودکار (رفتار واکنشي) ‎ee lM ‎ 

صفحه 5:
[ه قالب رويداد (4ه1876). شرط (2050168008©) و عمل (متاعه) ‏ - ‎eine Ml‏ پایگاه ده پوابرای خرید و فروش سهام: DEFINE LowRisk ON Stock.UpdatePricg—mmm ‏رويداد‎ IF (Stock.policy = Low risk) and , (Stock.price < Stock.initpricé*"e) DO Stock.Buy e<0>1 sit ee 

صفحه 6:
رويدادهاي زماني فعال سازي قواعد مرتبط 

صفحه 7:
زمان اجراي واقي يك قاعده با توجه به مفهوم تولید پوياي قواعد در حین اجراي آن 

صفحه 8:
روش اتفا روش مبتني گروههاي bert | ay, “ricky POSRGR ES HiPAC Real Time ADS General purpose يف0 

صفحه 9:
بینی مجموعه قواعد فعال استخراج كراف وابستكي هاي موجود بین قواعد از تعریف قواعد ساخت درخت هاي اجراي قواعد از گراف وابستگی ها استخراج قواعداتراکنشهای مجازي از درخت های اجرای قواعد | تخمین احتمال اجرای قواعد کر ۳[ 6 و۳[ ‎E,-SJFpgo-V-1.8 0‏ ‎E,-SJFpgo-V-2.8‏ مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 10:
استخراج گر افقورولفسبتگیو این تقبو طود بين قواعد يويا FINE R, ON Bank Table.Update DEFINE R, ON Stock.Changeprice IF (Stock.Policy=Low risk) aRghm | IF Bank Table.Money<1000000$ (Stock. Price<Stock.Initprice*e) DO Stock.Buy O<e<1 "Admi DEFINE R, ON Stock.Buy IF (Stock.Price<Bank Table.Money) DO StocksInfo_Table.Update 

صفحه 11:
بدیل کرش ویب هابد رت فاي اجري قواعه 

صفحه 12:
omy a MR =UR)+ S XR) + ‏هید ها ار دیس و‎ 2...) 2 2 

صفحه 13:
در حالت كلي براي محاسبه احتمال شرط (۲۱۰.۱2 400800) ور ۰ ۱ ۰ 1) 7 .. ۸۰8۰0 مستقل از هم هستند ‎P(A)=P(B)=P(C)=...P(Z)=1/2 (2‏ ‎FA(An Bu (Cn D)=PAn Bt ACn D)- RAN BACND)‏ A(An Bu (Cr D)\=AA)* A B)+ AC)* AD)- PA)* A B)* AC)* AD) AA - ۳-۳0 -...- ۵ * * + Nine FA(An Bu (Cn D))=: NIB ی ۶ 2 2 2 @eorhebir Ortrersty oP Poche, Orwemer Cexpeerin 

صفحه 14:
ها اضافه كردن بيمانه تخمين احتمال وقوع قواعد به روش لا افزایش دقت در محاسبه زمان اجرای قواعد الا روش کار: ‎Ml‏ درهربار ارزیابی بخش شرط قاعدما: أ محاسبه و ذخیره احتمال درستی هر یک از عبارات شرطي (05) موجود در بخش شرط قاعده 8 یعنی 318,15 طبق رابطه: تعدد فمتی که نلاع تکنون اریابی شده و هرست بوده است. تعداد دفعاتی که 8 تاکنون قعال شد: = ‎P(CSIR)‏ oe 

صفحه 15:
متالی از نحوه تخمین ‎EGR op -0..0 L‏ ی ار تراک 9 A(An Bu (Co D))=P(An B+ ACn D)- RAN BNCn D) 85 84 3 2 1 0 | ۸ | ‎CS ۳ ۱6۱۳ ۱6/۱/۳۱۱۴ (۶ | ۴‏ ‎A 95 |۲۱ 1 || | 5 | ۲| 0.659 |‏ ۶ موه ۱ موجه 2۲ | 1 | ۱۸۲ 5 8 98 | 07۵6 ۱ ۲ ۱ ی | 1 9 | ۲ ۱۱ 95 0 ‎|x) 0.333 |] 0.329‏ یز ۲ ۱۶ ظ 2 9 wn ۸ 3 ‏ا‎ ‎& ‎۲ ‎3 ‎3 مسرت سای مرا سیر ‎Fetched‏ 

صفحه 16:
112 S| 75 ۰ 03001 : 0.688 زک جد ابد ص ‎ee‏ 111 9 0.495 0.694 0.396 186 |] 8 0489 0,699 200 6 ۳ NI 0.495 | P 05 05 05 0 0.5 0.5 tal ۲ جات خسف ات6 

صفحه 17:
شرطي موجود در آن شرط بهنگام شده باشند به كمك فرمول هاي احتمال و با توجه به عملكرهاي منطقي موجود بين عبارات شرطي احتمال درستى عبارات شرطى نهابى اولیه 065 0.5 0.49 05 0.69 0.5 0.39 0.5 NA cs حن 00 |0۱60 A(An Bu (Co (1-۵۸ ۶9+ 20*20 - 4۸* 0 -ظ 66 + ظ 24۲( 66) با ظ 40) ‎B)U(C AD) =05*0 5+0 5*0 5-05۳05۸05-677‏ معام ‎= 0.65 * 0.49 + 0.69 *0.39 — 0.65 "0.49 * 0.69 *0.39 5019 ‎PAN BWC AD) ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 18:
ال بهنگام سازي زمان اجراي يك قاعده؛ زمانیکه احتمال درستي شرط کلیه قواعد تعويقي و فوري خود آن قاعده ۰ فرزندان و نوه هایش بهنگام شده باشند ‎Ml‏ با پیمایش عمقي درخت قاعده مجازي متناظر آن قاعده و به کمك فرمول: ( یهار ‎LR)‏ ‎4S PRO RR)‏ سير جره ‎X(R) =UR) + SAR‏ I={n- 1n- 2,...} مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 19:
بهبود فرایند محاسبه زمان اجراي قواعد در 8 با اعمال دو تغییر: 1 استفاده از اطلاعات بالقوه موجود در شرط قواعد: © دامنه متغيرهاي عبارات شرطي 4 نحوه تركيب متغيرهاي عبارا خرطي سار به منظور محاسبه دقيقتر احتمال اوليه درستي شرط قواعد به جاي محاسبه احتمال اجراي قواعد برمبناي تخصیص مقدار 5/0 به عنوان احتمال اولیه درستي هريك از عبارات شرطي موجود در بخش شرط قواعد بخش شرط قواعد 2 _ توجه به عدم یکنواختی احتمال وقوع مقادیر دامنه متغيرهاي عبارات شرطي مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 20:
بخش شرط چند قاعده بخش شرط قاعده نام قاعده وآطدياط ‎R‏ ‏[سیمان 016 مس 01 قولاد) م1 ‎Ry‏ ‎R3 DIp=20 AND DIp<=DI,,‏ ‎Ry DI,<20 AND Dic= {2}‏ دامته متفيرهاي موجود در ببار ۳ شرطم ‎ -2000>25>50 |‏ | 1>50ظ>110- ‎0<DL,<100‏ ‏(فولاد. مس, سيمان. برنج. طلل برنز. فرش. نقره. يرتقال. كفش) -م2[1 احتمال اجراي قاعده ب8؟ مرا یر ‎eked‏ رش موه متا يساسحا 1 حل رها میت 

صفحه 21:
60 مه و2 له 40 30 20 لد نش ۵ 0 40 3 DI,>DI, 

صفحه 22:
ال پس از محاسبه احتمال اجراي قواعد به روش مذکوره زمان قاعده را با پیملیش عمقی درخت قاعده مجازي متناظر آن قاعد: کمك فرمول زیر محاسبه مي نماییم: LR) af RY CR) = RE) +S ‏ا‎ KR) I={n- 1,n- 2,...} مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 1 

صفحه 23:
# پس از شروع کار سیستم. در بازه های زمانی مشخص (ا0 ) برای هر یک از متغیرهای بخش شرط قواعد. تمامی مقاددری که اخذ شده. به همراه مدت زمان اخذ آنها ثبت می گردد. در پایان هر براساس اطلاعات بدست آمده و۱۳ احتمال متفیرها اصلاح و د احتمال درستي بخش شرط قواعد و زمان اجرای آنها مجدداً محاسبه و بهنگام مى شوند ۳ ۵7۲, < 17 12 | 10 80,20min, B___|-50.10mia | 0.8mia 44.2min مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 24:
۱۳۹۰۹۵ ‏ی یه سار پایگاه‎ a 1 Database System Simulator (ADSS) ‏لا واحد مدیریت اشیاء داده‎ ‏واحد مدیریت قواعد‎ Ml ‏واحد مدیریت تراکنش‎ Ml مم ا ا اا 

صفحه 25:
‎(oo, |) Koo,‏ ]| ,00 مه ‎ ‎ ‎ ‎ ‎kd0, |] (DO,} + | ۵ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏کنترل همزماني ‎ ‎ ‎ ‎ ‎ ‎ ‎gb ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏واحد مدیریت ترا ‎ekg yates beboretory 2‏ رش ببسي فا سجن يساسحا 1 حل رها مایت ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 26:
‘Time of i" Rule RISD Start of Execution F = (QP + Execution? ime of N® Rule) - 17 x 2۳ > Re af Execution Time of i® Rule a sls Throughput N= Number of Executed Rules ART= Average Response Time RTSD= Response Time Standard Deviation Uepu= CPU Utilization 7 [eon - ‏0ج‎ TOPT = Time Overhead Per Transaction vo 11 مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 27:
مم ا ا اا 

صفحه 28:
بت ت9بوان ‎FE PEEESEEISSEESES‏ اد یی ندش مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 29:
| يم جبخ ف ةا اه ‎ee‏ ‘SPP PPPPPPPPP OP اد رنه ندش مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 1 

صفحه 30:
تعداد تراش در واحد زمان تبي يي تبي تبي بي “فى ثبي ثبي لبي ني “ان “لي “لو لي تعاد راكتشهلى توليد شد مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 

صفحه 31:
حي تي عي في فى في فى علي في في في كي تعداد توانشهلى توليد ده مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 

صفحه 32:
بي ني لي ل وى لي لي لي ني و لي 0 داد تراكنشياي توليد ده رورا سیر تمرطه ‎(Pardly,‏ رهظ جفم() رواخ روف( سلطا 1 

صفحه 33:
: 4 2 ۳ 7 7 ۶ 1 erty Par, tcl Gyo bebortory ب حمست يمسا 1 Random Static Priority. FCFS EDFrp EDFory 2079 ملظ 0 8 وله بط 28 -موططله ی هه یه 

صفحه 34:
a a ee 111 لخ مش ۰ “ل لي في ل حي ف لي لي لي طني ل في لي لي اد کی ولد شد مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 35:
مك اب ‎cr.‏ ‎wo}‏ ‎wl‏ ‎ero |‏ (as del SPPPPPPPPPPIPP دا تراكنشهلى ولد شده 31 مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 36:
و ور همیب تعداد تواكنش در واحد زعي م في حي في في في فى في في © © كي دا تراکنشهلی وید شم ما مسرت موش ‎Oncemter Borgen (Pomdy,‏ رنوطامله اه رهمسف) ات 

صفحه 37:
aoe. 3 ar. 9 ‏مه‎ ‏6ه‎ ‎0 ‎ce LPF PIPPPPPPPPP تعدا تواتشهلى توليد شد مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 

صفحه 38:
7 Deore Oewernny of Pechckys, Omernter (Baprmernny Peri, tcp (Syme ‏روما‎ 

صفحه 39:
Sil tel ‏]ی | سین | و‎ ‏رن | کت‎ OP Random ۲ a ۲ ۲ ۳ Static Priority ۲ ۵ ۲ ۳ ۳ ECES ۲ ۵ ۲ ۱ ۱ EDFep ۴ ¥ ۱ \ ۲ =DFow ۴ ۴ | ۱ ۲ 7 7 ۴ ۲ 1 ا 7 ۳ 8 ۲ ۲ قي ۲ ۲ ۴ ۴ ۲ ی 2 5۳8 ۱ ۲ ۳ 7 ۲ E,-SlForo-V.28 ۱ ۱ ۳ ۲ 3 مرا سیر ‎Pe erty Par, tcl‏ سره سمل یب sel Oeste: Cd 

صفحه 40:
با ‎oie‏ ‏في حي فى في ل ف ل ني فلي في الى فى كي اد کی ولد شم مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 1 

صفحه 41:
سح ‎Jeans ron‏ | ‘SPP PPP PPPP PPO? تعداد ترکنشهلی ولد شده رورا سیر تمرطه ‎(Pardly,‏ رهظ جفم() رواخ روف( سلطا 1 

صفحه 42:
نمودار وان عملياتي تعداد تراكنش در واحد يملن مه "FP PEEP PEEPS OPS تعدا تراكتشيلى تيد شد مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 

صفحه 43:
‘un Ga da ep dempocuDeraD coup san FOND EHRIDARAD A RD cal ay ‏اتنا‎ مم ا ا اا 

صفحه 44:
۳ sab ty aa مسا سي مهد ‎Center Park,‏ موس سس ‎of‏ رمد 11 ا 

صفحه 45:
م بعردى بردازشكر erty Par, tcl Gyo bebortory مانگین سرباز زمانی به ازای هر تراكنش ‎Oe‏ هت 1 نا ‎0 ‎ ‎Random ‎Static Priority FCES ‏ومد ‎EDED ‎EDFs, ‏وله‎ ‏مود لقي ‏8 موه 5۳06و ‎ ‏هه یه ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 46:
‎aes,‏ ش ها احرای قما ‎JS Saye‏ اتود رش رمک که یه 75۳ رز هلح لو چاو تلف تلف ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏حالت ترکیبی | حالت فوری | حالت تعویقی ‎Random ۳ ۷ 2‏ ام 8 ‎۲ eb! | ‎fel eter tone ‏اتسراف‎ SEE | ‏ماي‎ ‎foe 8 ۹ 5 whe ‏ل‎ ‎Gp ae | eee | OE one ‏كور 7 7 أ‎ ۳ Fare Han, ‏كعووقيه‎ ‏ناخ‎ Haale Ever ‏حالت‎ |S E,-SJFEXA 1 9 3 E,-SIFpro Ls Ey 5 E,-SJFpro-V.1.8 ۳ ۲ ۳ E,-SJFpro-V.2.3 1 \ ۱ ‎ ‎ ‎ ‎ ‏مرا سیر نموه ‎Ocarerony oP Pecheobra, Oveopnter Barpareriny Parl,‏ ات0 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 47:
طراحی و پیاده سازی دو روش جدید برای تخمین. احتمال اجراي قواعد به منظور بهبود فرایند زمان بندی اجرای قواعد ‎a‏ ارلیه چارچوبي جدید براي شبیه سازی رفتار پایگاه داده پویا و ارزیابی عملکرد روشهاي زمانبندي قواعد ‏مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 1 ‎ 

صفحه 48:
وه روش هي بر با استفاده از تکنیک مورد. استفاده در ‎E,-SJF‏ اقلا مقايسه تطبيقي روشهاي زمانبندي به جز 17 براساس پایگاه قاعده با تعداد سطوح بیشتر از دو ‎lb‏ و پیاده سازي سیستم مدیریت پایگاه داده پویا برمبناي عامل ها ‏مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا ‎ 

صفحه 49:
مهم ترین مراجع مورد استفاده R Alesheykh, An Effective Rule Selection approach in Active Database Systems, MSc Thesis, Amirkabir University of Technology (Tehran PolyTechnic), 2005. U. Schreier, H. Pirahesh, R. Agrawal and C. Mohan, “Alert: an Architecture for Transforming a Passive DBMS into an Active DBMS’, in proc. of ¢ 17th VLDB Conference , Barcelona, September, 1991. E.N. Hanson, “Rule Condition Testing and Action Execution in Ariel’, in proc. of the ACM SIGMOD International Conference on Management of Data, San Diego (Calif), 1992 A. Vadua, “Rule Development for active database’, PhD Thesis, CS Department, University of Zurich, 2001 A. Geppert, S. Gatziu, K. R. Dittrich, H. Fritschi, and A. Vaduva, “Architecture and implementation of the active object- oriented database management system SAMOS", Technical Report 95.29, CS Department, University of Zurich, 2001. Rohollah_ Alesheykh, A. Abdollahzadeh, “Evaluation and Comparison of Rule Scheduling Approaches in Active Database Systems’, in Proceedings of the 2™ IASTED international" Multi-Conference_on Automation, Control, and Information Technology (ACIT’05), June 20-24, 2005, Novosibrisk, Russia. 

صفحه 50:
مهم ترین مراجع مورد استفاده- ادامه A. ‏بط‎ “Architecture of Active Database Systems’, in the Active Rules in Database Systems. Springer, 1999. S. Chakravarthy. “Architectures and monitoring techniques for active databases: An evaluation’, Technical Report TR-92-041, University of Florida, Gainesville, FL, 1992. P. Rénn, “Iwo Approaches to Event Detection in Active Database Systems”, MSc Thesis, CS Department, University of Skévde,Sweden, 2001. S. Ceri, C. Gennaro, S. Paraboschi, G. Serazzi, “Effective Scheduling of Detached Rules in Active Databases”, [EEE Transaction Knowledge and Data Engineering, 15(1), 2003. مرا سیر ‎Ocarerony oP Pecheobra, Oveopnter Barpareriny Parl, teed‏ ات0 

صفحه 51:
اب ند ‎vy‏ pee R; Abdollahzadeh, A; “A New 6 mnt Triggering Probability Estimation » Systems to Rule Scheduling Improvement”, _ International Conference on It & n Technologies: From Theory To Aj Damascus, , April Rasoolzadegan, A; Alesheykh, R.; Abdollahzadeh, A; “Measuring Evaluation Parameters in Benchmarking Rule Scheduling ‘Methods in Active Database Systems”, The IEEE International Conference on Computer and Communication Engineering, Kuala ‎Lumpur, Malaysia, 2006.‏ عباس رسولزادكان. روح الله لل شیخ. احمد عبدلله زاده. (ارلنه روشي جسید براي تخمین احتمال وقوع قواعد در پایگاهدادهپوبابه منظور بهبود زمانبندي اجراي قواعد د رآن 16 در مجوعه مقالات یازدهمین کنفرانس سالانه انجمن کامپیوتر ایران. 6-4 بهمن ۰1384 تهران. ایران. ‏ابران. ‎ 

صفحه 52:
Active Database System Simulator to Compare and Evaluate Rule Scheduling Methods”, Technical Report, Department of Computer Engineering, Amirkabir University of Technology, Tehran - Iran, September 2006. مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 1 

صفحه 53:
احمد عبدلله زاده. « ارلئه روش جدید پایگاهداده پویا برمبنای بهبود فرایند تخمین احتمال اجرای ‏ علمی و پژوهشی دانشگاه صنعتی امیر کبیر. ‎Ml‏ عباس رسولزادگان. احمد عبداله ‎ ‏» ۲۷۰2.8 ویر کر روش جدید زمانبندي قواعد بر مبناي تخمین احتمال اجراي قواعد در پایگاه داده ۰ پویا». پانزدهمین کتفرلنس مهندسي برق ایران: 27-25 اردیبهشت 1386 مرکر تحقیقات مخابرات ایرلن. تهران» ايران. ‏لا عباس رسولزادگان. احمد عبدلله زاده. « ۵55 شبیه ساز سیستم پایگاه داده پویا براي مقایسه تطبيقي روشهاي زمانبندي قواعد». پانزدهمین کنفرانس مهندسي برق ایران. 27-25 اردیبهشت 1386 مرکز تحقیقات مخابرات اييلن» تهران» ایران. ‏اس نب هن ۳ ‎ 

صفحه 54:


صفحه 55:
58 توليد قواعد فرآیندضم افاری تولید قواعد ‎Oudua 5 ¢‏ 8 ۹ ‎I‏ ‎ew!‏ مهو وود رویدادهای ترکیبی رویداد توزیع شده ‏زبانهای برنامه زبانهای پرس و جوی ‎ ‏اع فاخ نویسی همه منظوره يايكاءداده که و ‎Bite pee‏ ‎he‏ 5 ۲ 

صفحه 56:
تشخیص رویدادهای ترکیبی K. Dittrich, S.Gatziu, A.Geppert, eds.(The ACT-NET Consortium), “The active database management system manifesto: a rulebase of ADBMS features”, Sigmod Record, 25(3): 40-49, 1996. H. Fritschi and Z. Flaach, “A Component Framework to Construct Active Database Management Systems”, PhD Thesis, cs Department, University of Zurich, 2002. R. M. Sivasankaran, J. A. Stankovic, D. Towsley, B. Purimetla) and K. Ramamritham, “Priority Assignment in Real-Time Active Databases”, The International Journal on Very Large Data Bases, 5(1), 1996. A. Kotz Dittrich and E. Simon, “Active Database Systems: Expectations, Commercial Experience, and Beyond”, Active Rules in Database Systems, سسا سمه سرهم حسمن رعبي998 ‎Begins, SRE GORVET AG,‏ 

صفحه 57:
روش های جلوگیری از ایجاد چرخه اجرا A. Vadua, “Rule Development for active database’, PhD Thesis, CS Department, University of Zurich, 1999. A. Kotz Dittrich and E. Simon, “Active Database Systems: Expectations, Commercial Experience, and Beyond”, Active Rules in Database Systems, Berlin: Springer-Verlag, 1999. J. Bailey , A. Poulovassilis and P. Newson, “A Dynamic Approach to Termination Analysis for Active Database Rules”, in proc. of the First International Conference on Computational Logic, 2000. J. Bailey and A. Poulovassilis “An Abstract Interpretation Framework for Termination Analysis of Active Rules”, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, 1999. مرا یر ‎eked‏ رش موه متا يساسحا 1 حل رها میت 

صفحه 58:
60 R. Alesheykh, An Effective Rule Selection approach in Active Database Systems, MSc esis, Amirkabir University of Technology (Tehran PolyTechnic), 2005. R, Alesheykh, A. Abdollahzadeh, "Evaluation of Shortest Dob First Approach for Rule Scheduling in Active Database 1 in the Proceedings of the 9th IASTED International Conference on Artificial Intelligence & Soft Compunng) (ASC'05), Benidorm, Spain, September 2005. R. Alesheykh, A. Abdollahzadeh, "Evaluation and Comparison of Rule Scheduling Approaches in Active Database Systems", in the Proceedings of the 2nd IASTED international Multi-Conference on Automation, Control, and Information Technology (ACIT’05), Russia, June 2005. A. Kotz Dittrich and E. Simon, “Active Database Systems: Expectations, Commercial Experience, and Beyond”, Active Rules in Database Systems, Berlin: Springer-Verlag, 1999. سسا سسسة هده مقس ع سيق مس ساس ل رفسي 11 | 

صفحه 59:
ژمانبندی اجرای قواعد WE. N. Hanson and J. Widom, “An Overview of Production Rules in Database Systems”, In the Ragwiedge Engineering Review, 8(2):121-143, 1993. ®R. M. Sivasankaran, J. A. Stankovic, D. Towsley, B. Purimetla and K. Ramamritham, “Priority Assignment in Real-Time Active Databases”, The International Journal on Very Large Data Bases, 5(1), 1996. Ws. Ceri, C. Gennaro, S. Paraboschi, G. Serazzi, “Effective Scheduling of Detached Rules in Active Databases”, IEEE Transaction Knowledge and Data Engineering, 15(1), 2003. رواخ خسف لباب 

صفحه 60:
Development for active database”, PhD Thesis nt, University of Zurich, 1999. W. Paton and O. Diaz editor, “Active Rules for Database ‘Systems’, Springer-Verlag, 1998. «8 A.P. Buchmann. “Architecture of Active Database Systems”, in the Active Rules in Database Systems. Springer, 1999. مسا سي مهد ‎Park,‏ سسب سس سس ‎of‏ رمد 11 ا 1 

صفحه 61:
کاربرد سیستم های پایگاه داده ‎Lg‏ K. Dittrich, S.Gatziu, A.Geppert, eds.(The ACT-NET Consortium), “The active database management system manifesto: a rulebase of ADBMS features”, igmod Record, 25(3): 40-49, 1996. M. Berndtsson and J. Hansson, “Workshop Report: The First International Workshop on Active and Real- Time Database Systems (ARTDB-95)”, ACM Sigmod Record, 25(1): 64-66, 1996. A. P. Buchmann, C. Liebig, “Distributed, Object- Oriented, Active, Real-Time DBMSs: We Want It All -- Do We Need Them (At) All?”, Annual Reviews in Control, Vol. 25, Elsevier, January 2001, Selected aper from IFAC/IFIP Workshop on Real-Time rogramming, 1999. R. E. Iliffe, P. W. H. Chung, T. A. Kletz and M. Preston, “The application of active database to the roblems of human error in industry’, Journal of Loss po in the Process Industries, (13): 19-26, مرا یر ‎eked‏ رش موه متا يساسحا 1 حل رها میت 

صفحه 62:
معماری سیستم های پایگاه داده پوپا A. Vadua, “Rule Development for active database”, He ce CS Department, University of Zurich, A. P. Buchmann. “Architecture of Active Database Systems”, in the Active Rules in Database Systems. Springer, 1999. S. Chakravarthy. “Architectures and monitoring techniques for active databas An_ evaluation”, Technical Report TR-92-041, University of Florida, Gainesville, FL, 1992. N. W. Paton and O. Diaz, “Active database systems”, ACM Computing Surveys (CSUR), 31(1):63-103, 1999. A. P. Buchmann, C. Liebig, “Distributed, Object- Oriented, Active, Real-Time DBMSs: We Want It All -- Do We Need Them (At) All?”, Annual Reviews in Control, Vol. 25, Elsevier, January 2001, Selected pepe from IFAC/IFIP Workshop on Real-Time rogramming, 1999. مرا یر ‎eked‏ رش موه متا يساسحا 1 حل رها میت 

دانشگاه صنعتي اميركبير به نام خدا دانشكده مهندسي كامپيوتر و فناوری اطالعات ارائه روش جديد زمانبندي قواعد در پايگاه داده پويا برمبناي تخمين احتمال اجراي قواعد ‏A New Rule Scheduling Approach based on Estimation of ‏Rule Execution Probability in Active Database System دانشجو: عباس رسول زادگان استاد راهنما: دكتر احمد عبداله زاده 1 03/11/1385 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory فهرست مطالب لزوم و هدف از انجام اين پژوهش تعريف سيستم پايگاه داده پويا فرآيند پردازش قواعد روشهاي موجود براي زمانبندي قواعد روش پيشنهادي اين پايان نامه محيط شبيه سازي پايگاه داده پويا ()ADSS بستر آزمايشات پارامترهاي ارزيابي مقايسه تطبيقي نتيجه گيري دستاوردهاي پايان نامه کارهاي آينده مراجع 2 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory لزوم و هدف از انجام اين پژوهش لزوم انجام اين پژوهش كاربرد بسيار گسترده پايگاه داده پويا در سيستم هايي كه نياز به نظارت خودكار دارند تأثير مستقيم فرايند زمانبندي اجراي قواعد در كارايي سيستم پايگاه داده پويا عدم وجود يك روش با کارايي الزم برای زمانبندي قواعد هدف طراحی و پياده سازی الگوريتمی برای بهبود فرايند زمانبندي قواعد در سيستم پايگاه داده پويا 3 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory سيستم پايگاه داده پويا سيستم مديريت پايگاه داده ايستا نداشتن ابتكار عمل در هنگام رخ دادن شرايط خاص در سيستم انجام دادن اعمالي نظير پرس و جو ،بهنگام سGGازي ،درج ،حGGذف، گزارش گيري و غيره فقGGط هGGر زمGGان کGGه صGGريحا توسGGط کGGاربر درخواست شوند سيستم مديريت پايگاه داده پويا داشGGتن امکان تعريGGف مجموعGGه اي از رويGGدادها و واکنش هGGاي متناظر آنها بGGه منظGGور انجGGام واکنش مقتضGGي در صGGورت وقGGوع رويدادي خاص به صورت خودكار (رفتار واكنشي) 4 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory قواعد پويا در پايگاه داده پويا .رفتار واکنشي اين سيستم بوسيله مجموعه اي از قواعد پويا سازماندهي مي شود )Action( ) و عملCondition( شرط،)Event( قالب رويداد :سيستم پايگاه داده پويا برای خريد و فروش سهام DEFINE LowRisk ON Stock.UpdatePrice رويداد IF (Stock.policy = Low_risk) and شرط )Stock.price < Stock.initprice * e( DO Stock.Buy عمل e< 0< 1 با فرض Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 5 چرخه پردازش قاعده برنامه كاربردي ………………. ………………. )raise-event(e1 ……………….. اجراي قواعد 5 تشخيص رويدادها رويدادهاي داخلي 1 پشته قواعد معلق 44 6 رويدادهاي خارجي 2 رويدادهاي زماني فعال سازي قواعد مرتبط 3 اب انتخ ارزشيابي شرط پشتهپشتهپشته يك قاعده پشتهپشتهپشته مستقل تعويق فوري مستقل تعويق فوري مجموعهي قواعد مجموعه يقواعد ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory جريان داده جريان كنترل زمان اجراي واقعي يك قاعده با توجه به مفهوم توليد پوياي قواعد در حين اجراي آن زمان واقعي اجراي تراكنش T زمان ظاهري اجراي تراكنش T ‏T1def T2def ‏Ind 1 ‏T ‏T2imm ‏T1imm تراکن ش فرزند تراکن ش پدر ‏def 1 ‏T ‏def 2 ‏T ‏T ‏t10 ‏t9 ‏t8 ‏t7 ‏t6 ‏t5 ‏t4 ‏t3 ‏t2 ‏t1 )S(T اتمام واقعي 7 اتمام ظاهري ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory ‏t0 مقايسه روشهاي زمانبندي اجراي قواعد موجود انتخاب اتفاقي برچسب زماني گروههاي اولويتي ضرب العجل زمان اجرا نوع فعال سازي فوري تعويقي مستقل سيستم مورد استفاده تحليل روش قوت :سادگي ضعف :عدم کارايي روش اتفاقي ‏Ode , ‏RPL روش مبتني برچسب زماني ‏SAMOS قوت :سادگي ضعف :عدم کارايي روش اولويت ايستا ‏POSRGR ‏ES قوت :سادگي ضعف :عدم کارايي روش اجراي موازي ‏HiPAC روش نزديکترين ضرب العجل ‏RealTime ‏ADS روش مبتني بر SJF 9 ‏Ariel, قوت :سادگي ضعف :بستر سخت افزاري قوت :کارايي ضعف :پايگاه قاعده دو سطحي ،بالدرنگ قوت :كاراترين ،به كارگيري در هر سيستمي بجز ‏General purposeبالدرنگ ضعف :عدم دقت زمان ‏Amirkabir قواعد University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratoryاجراي گام های مورد نياز برای بکارگيری SJFدر زمانبندی قواعد پيش بينی مجموعه قواعد فعال استخراج گراف وابستگي هاي موجود بين قواعد از تعريف قواعد ساخت درخت هاي اجراي قواعد از گراف وابستگی ها استخراج قواعد/تراکنشهای مجازي از درخت های اجرای قواعد تخمين احتمال اجرای قواعد ‏Ex-SJFEXA ‏Ex-SJFPRO ‏Ex-SJFPRO-V.1.8 ‏Ex-SJFPRO-V.2.8 10از 55 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory موجود بين قواعد پويا وابستگي استخراج گراف هاي پويا قواعد تعريف قواعد گذاري برچسب DEFINE R3 R1 ON Bank_Table.Update DEFINE R1 ON Stock.Changeprice IF (Stock.Policy=Low_risk) and imm (Stock.Price<Stock.Initprice*e) DO Stock.Buy 0<e<1 imm DEFINE R2 R4 IF Bank_Table.Money<1000000$ DO R2Send.Message("Warning","Admi n", "No Enough Money") imm ind Else DO Increase(e) ON Stock.Buy IF (Stock.Price<Bank_Table.Money) DO StocksInfo_Table.Update R3DEFINE RR4 5 ON defStocksInfo_Table.Update IF DO StockType-code<>9 Check-Consistency Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems DEFINE R Laboratory 5 11 استخراج قواعد مجازي از درخت هاي وابستگي ها به درخت هاي اجراي گراف تبديل اجراي قواعد RحذفRيالهاي R داراي برچسب R ind 5 ‏R هاي اجراي احتمالي R1 2 موجود حذف 4چرخه 3 اصالح تعريف قواعد مولد چرخه ‏R ‏R تبديل آنها به حالت يك پدر و يك فرزند 5 ‏R2 3 ‏imm ‏R5 ‏def ‏R3 قاعده مجازی R2 12 1 ‏imm بيش از يك مولد دارند شناسايي قواعدي كه R 5 قواعد ‏R ‏R 4 2 ‏imm ‏R 5 ‏R4 ‏R ‏R 3 4 قاعده مجازی ‏R1 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory Ex-SJFEXA محاسبه زمان اجراي قواعد به كمك قواعد مجازي در روش RR 1,24 1,1 R R22,13 ,2 def imm imm imm R3,3 R R44,3 ,1 R R55,16 ,2 R6,5 ,2 R77,11 ,5 R def imm R8,2 R9,7 ,4 def R13,2 X (RI )  L(RI )  nimm( RI ) X imm(RiI  i 1 1 ) def imm def R10,7 imm R14,1 ndef ( RI ) R11,3 def imm R15,3 R16,2 X def (RIj  j 1 R ,6 R12 12,1 1 ) , I {n  1, n  2,...,1} Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 13 Ex-SJFPRO نحوه محاسبه احتمال وقوع شرط قواعد در : ( فرض شده استA  B  C  ... Z) در حالت کلي براي محاسبه احتمال شرط مستقل از هم هستندA ، B ، C … Z )1 P(A)=P(B)=P(C)=…P(Z)=1/2 )2 P[(A  B)  (C  D)]  P( A  B)  P(C  D)  P( A  B  C  D) P[(A B)  (C  D)] P( A) * P(B)  P(C) * P(D)  P( A) * P(B) * P(C) * P(D) P( A)  P(B)  P(C) ... P(Z)  1 2 1 1 1 1 1 1 1 1 7  *  * * *  2 2 2 2 2 2 2 2 16 P[(A  B)  (C  D)]  * Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 14  Ex-SJFPRO-V.1.8روش اول ارائه شده برای تخمين احتمال اجرای قواعد : اضافه کردن پيمانه تخمين احتمال وقوع قواعد به روش EX-SJFPRO افزايش دقت در محاسبه زمان اجرای قواعد روش كار: درهربار ارزيابی بخش شرط قاعده: R محاسبه و ذخيره احتمال درستی هر يک از عبارات شرطي ( )CSموجود در بخش شرط قاعده Rيعنی ) P(R,LSiطبق رابطه: 16 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory Ex-SJFPRO-V.1.8 مثالی از نحوه تخمين اجرای قواعد توسط P[(A  B)  (C  D)]  P( A  B)  P(C  D)  P( A  B  C  D) 0.65 Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 17 0.39 0.70 0.49 Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 18 مثالی از نحوه تخمين اجرای قواعد توسط Ex-SJFPRO-V.1.8 بهنگام سازي احتمال درستي يك شرط ،زمانيكه احتمال درستي تمام عبارات شرطي موجود در آن شرط بهنگام شده باشند به كمك فرمول هاي احتمال و با توجه به عملگرهاي منطقي موجود بين عبارات شرطي )P[(A  B)  (C  D)]  P( A  B)  P(C  D)  P( A  B  C  D اوليه )P[(A B)  (C  D)] P( A) * P(B)  P(C) * P(D)  P( A) * P(B) * P(C) * P(D نهايي 19 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory روش - Ex-SJFPRO-V.1.8ادامه بهنگام سازي زمان اجراي يك قاعده ،زمانيكه احتمال درستي شرط كليه قواعد تعويقي و فوري خود آن قاعده ،فرزندان و نوه هايش بهنگام شده باشند با پيمايش عمقي درخت قاعده مجازي متناظر آن قاعده و به كمك فرمول: )) * X def (RIj 1 ‏1 ) ndef ( RI ‏P(RIj ‏ ‏j ‏1 ) * X imm(RiI 1)  ‏1 ) nimm( RI ‏P(RiI ‏ ‏i ‏X (RI )  L(RI )  ‏1 }I {n 1, n 2,...,1 20از 55 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory  :Ex-SJFPRO-V.2.8روش دوم ارئه شده برای تخمين احتمال اجرای قواعد بهبود فرايند محاسبه زمان اجراي قواعد در روش Ex-SJFPRO- V.1.8با اعمال دو تغيير: .1 استفاده از اطالعات بالقوه موجود در شرط قواعد: دامنه متغيرهاي عبارات شرطي نحوه تركيب متغيرهاي عبارات شرطي سازنده بخش شرط قواعد به منظور محاسبه دقيقتر احتمال اوليه درستي شرط قواعد به جاي محاسGGبه احتمال اجراي قواعد برمبناي تخصيص مقدار 5/0بGGه عنGGوان احتمGGال اوليGGه درستي هريك از عبارات شرطي موجود در بخش شرط قواعد .2توجه به عدم يكنواختي احتمال وقوع مقادير دامنه متغيرهGGاي عبارات شرطي 21 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory بخش شرط چند قاعده دامنه متغيرهاي موجود در عبارات شرطي ؟R1 احتمال اجراي قاعده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 22 DIA>DIB توزيع احتمال متغيرها به صورت يکنواخت فرض شده است Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 23  ادامه- Ex-SJFPRO-V.2.8 روش رGG زمان اجراي ه،پس از محاسبه احتمال اجراي قواعد به روش مذكور قاعده را با پيمايش عمقي درخت قاعده مجازي متناظر آن قاعده و به :كمك فرمول زير محاسبه مي نماييم X (RI )  L(RI )  nimm( RI ) P(RiI  i 1 1 ) * X imm(RiI 1)  ndef ( RI ) P(RIj  j 1 ) * X def (RIj 1) 1 I {n 1, n 2,...,1} Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 24 روش - Ex-SJFPRO-V.2.8ادامه حذف تدريجي فرض يكنواختي توزيع احتمال متغيرهاي عبارات شرطي پس از شروع کار سيستم ،در بازه هGGای زمGGانی مشGGخص ( ) بGGرای هGGر يGGک از متغيرهای بخش شرط قواعد ،تمامی مقاديری که اخذ شده ،به همراه مدت زمGGان اخذ آنها ثبت می گردد .در پايGGان هGGر براسGGاس اطالعGGات بدسGGت آمGGده توزيGGع احتمال متغيرها اصالح و درنتيجه احتمGGال درسGGتي بخش شGGرط قواعGGد و زمGGان اجرای آنها مجددًا محاسبه و بهنگام می شوند 25 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory بستر آزمايشات محيط شبيه ساز پايگاه داده پويا Active Database System Simulator (ADSS) واحد مديريت اشياء داده واحد مديريت قواعد واحد مديريت تراکنش Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 26 واحد مديريت اشياء داده ‏DO3 DO4 … ‏DOn ‏DO1 ‏DO2 ‏DO5 DO6 کنترل همزماني ‏ حساس به زمان بخش ميانگيري قواعد غير حساس به زمان پايگاه قاعده فعال سازي قواعد قواعد فوري ‏Deferred ‏Rules تعويقي قواعد ‏Independent ‏Rulesمستقل قواعد اطالع دادن به واحد مديريت قواعد از وقوع رويدادهاي داده اي ارتباط و ارسال داده اطالع دادن به واحد مديريت قواعد از وقوع رويدادهاي تراکنشي ارتباط و ارسال داده بين بخش توليد تراکنش و واحد مديريت اشياء تراكنش هاي تراکنش هاي رويدادنگار بالک شده بالك شده تراکنشها بخش اجراي تراکنش 27 ارزشيابي شرط تراکنش فوري بخش زمانبندي ارسال تراکنش تراکنش تعويقي تراکنش مستقل واحد مديريت تراکنش درست بخش ميانگيري تراکنش ها تراکنشهاي توليد تراکنش بخش توليد تراکنش واحد مديريت قواعد کاربر ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory پارامترهاي ارزيابي تعريف پارامترهاي ارزيابي به صورت ميانگين زمان پاسخگويي فرمالپاسخگويی هر تراکنش عبارتست از فاصله زمانی بين زمان توليد زمان تراکنش و زمان اتمام آن. انحراف معيار زمان پاسخگويي اين معيار ميزان تجمع زمانهای پاسخگويی تراکنش ها حول نقطه ميانگين را نشان می دهد. توان عملياتي تعداد تراکنش هايی که در واحد زمان در يک روش زمانبندی اجرا می شوند را نشان می دهد. ميزان زمان سربار محاسباتي به ازاي هر تراکنش بهره پردازشگر درصد استفاده بهينه از پردازشگر را نشان می دهد. 28 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory حاالت در نظر گرفته شده برای مقايسه تطبيقي روش های زمانبندی حالت تعويقي حالت فوري حالت ترکيبي Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 29 ميانگين زمان پاسخگويي در حالت تعويقي زمانپاسخگويی ميانگين زمان نمودار پاسخگويي ميانگين نمودار 100000 90000 Rand o m St at ic Prio rit y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 80000 )زمان (ميلی ثانيه 70000 60000 50000 40000 30000 20000 10000 0 0 10 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 55 از30 انحراف معيار زمان پاسخگويي در حالت تعويقي نمودار انحراف معيار زمان پاسخگويی پاسخگويي نمودار انحراف معيار زمان 2000 1800 1600 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 )زمان (ميلی ثانيه 1400 1200 1000 800 600 400 200 0 0 10 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 31 توان عملياتی حالت تعويقي تعداد تراکنش در واحد زمان توانعملياتی نمودار توان نمودار عملياتي 7 6.8 6.6 6.4 6.2 6 5.8 5.6 5.4 5.2 5 4.8 4.6 4.4 4.2 4 Ra ndo m St a t i c Pri ori t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 32 ميانگين سربار محاسباتی به ازای هر تراکنش در حالت تعويقي تراکنش به ازای محاسباتی به سربار ميانگين زمان نمودار ميانگين تراکنش ازايهرهر محاسباتي سربار نمودار 10.5 ‏Ra nd o m ‏St a t i c Pri o ri t y ‏FCFS ‏EDF-PD ‏EDF-DIV ‏EDF-SL ‏Ex-SJF-EXA ‏Ex-SJF-PRO ‏Ex-SJF-PRO-V.1.8 ‏Ex-SJF-PRO-V.2.8 10 9 8.5 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 0 40 0 20 0 10 تعداد تراکنشهای توليد شده 33 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory زمان (ميلی ثانيه) 9.5 بهره پردازشگر حالت تعويقي بهرهپردازشگر نموداربهره نمودار پردازشگر 96 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 درصد بهره پردازشگر 95.75 95.5 95.25 95 94.75 94.5 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 34 مقايسه دو روش ارائه شده با ساير روش ها در حالت تعويقي Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 1 32 35 ميانگين زمان پاسخگويي در حالت فوري زمانپاسخگويی ميانگين زمان نمودار پاسخگويي ميانگين نمودار 3200 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-RRO-V.1.8 Ex-SJF-RRO-V.2.8 3000 )زمان (ميلی ثانيه 2800 2600 2400 2200 2000 1800 1600 0 10 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 36 انحراف معيار زمان پاسخگويي در حالت فوري پاسخگويی معيارزمان انحراف معيار پاسخگويي زمان نمودارانحراف نمودار 490 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-RRO-V.1.8 Ex-SJF-RRO-V.2.8 440 )زمان (ميلی ثانيه 390 340 290 240 190 140 90 40 0 10 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 37 توان عملياتی در حالت فوري عملياتی نمودارتوان نمودار عملياتي توان 3.97 3.87 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-RRO-V.1.8 Ex-SJF-RRO-V.2.8 تعداد تراکنش در واحد زمان 3.77 3.67 3.57 3.47 3.37 3.27 3.17 3.07 2.97 2.87 0 10 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 38 ميانگين سربار محاسباتی به ازای هر تراکنش در حالت فوري تراکنش ازايهر هر سربار نمودار تراکنش محاسباتي بهبهازای سربار محاسباتی ميانگينزمان نمودار ميانگين 10.2 9.8 ‏Ra nd o m ‏St a t i c Pri o ri t y ‏FCFS ‏EDF-PD ‏EDF-DIV ‏EDF-SL ‏Ex-SJF-EXA ‏Ex-SJF-PRO ‏Ex-SJF-RRO-V.1.8 ‏Ex-SJF-RRO-V.2.8 9.4 8.6 8.2 7.8 7.4 7 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 0 40 0 20 0 10 تعداد تراکنشهای توليد شده 39 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory زمان (ميلی ثانيه) 9 بهره پردازشگر در حالت فوري بهرهپردازشگر نمودار بهره پردازشگر نمودار 97.8 Ra nd o m درصد بهره پردازشگر St a t i c Pri o ri t y FCFS 97.55 EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA 97.3 Ex-SJF-PRO Ex-SJF-RRO-V.1.8 Ex-SJF-RRO-V.2.8 97.05 100 200 400 800 1200 1800 2100 2500 3000 4000 5000 6000 7000 8000 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 55 از40 مقايسه دو روش ارائه شده با ساير روش ها در حالت فوري Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 1 32 41 ميانگين زمان پاسخگويي در حالت ترکيبي زمانپاسخگويی ميانگين زمان نمودار پاسخگويي ميانگين نمودار 11 0000 100000 90000 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 )زمان (ميلی ثانيه 80000 70000 60000 50000 40000 30000 20000 10000 0 0 10 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 42 انحراف معيار زمان پاسخگويي در حالت ترکيبي پاسخگويي انحرافمعيار انحراف زمانپاسخگويی معيار زمان نمودارنمودار 2500 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 )زمان (ميلی ثانيه 2000 1500 1000 500 0 0 10 0 20 0 40 0 0 0 0 0 0 0 0 0 0 0 80 1 20 1 80 21 0 250 300 400 500 600 700 800 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 43 توان عملياتی در حالت ترکيبي توان عملياتی نمودار عملياتي توان نمودار 8.3 8 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 7.4 7.1 6.8 6.5 6.2 5.9 5.6 5.3 12 00 18 00 21 00 25 00 30 00 40 00 50 00 60 00 70 00 80 00 80 0 40 0 20 0 5 10 0 تعداد تراکنش در واحد زمان 7.7 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 44 ميانگين سربار محاسباتی به ازای هر تراکنش در حالت ترکيبي تراکنش به ازای محاسباتی به سربار ميانگين زمان نمودار ميانگين تراکنش ازايهرهر محاسباتي سربار نمودار 11 10.5 ‏Ra nd o m ‏St a t i c Pri o ri t y ‏FCFS ‏EDF-PD ‏EDF-DIV ‏EDF-SL ‏Ex-SJF-EXA ‏Ex-SJF-PRO ‏Ex-SJF-PRO-V.1.8 ‏Ex-SJF-PRO-V.2.8 10 9 8.5 8 7.5 7 100 200 400 800 1200 1800 2100 2500 3000 4000 5000 6000 7000 8000 تعداد تراکنشهای توليد شده 45 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory زمان (ميلی ثانيه) 9.5 بهره پردازشگر در حالت ترکيبي بهرهپردازشگر نمودار بهره پردازشگر نمودار 96 Ra nd o m St a t i c Pri o ri t y FCFS EDF-PD EDF-DIV EDF-SL Ex-SJF-EXA Ex-SJF-PRO Ex-SJF-PRO-V.1.8 Ex-SJF-PRO-V.2.8 95.5 95.25 95 94.75 12 00 18 00 21 00 25 00 30 00 40 00 50 00 60 00 70 00 80 00 80 0 40 0 20 0 94.5 10 0 درصد بهره پردازشگر 95.75 تعداد تراکنشهای توليد شده Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 46 مقايسه دو روش ارائه شده با ساير روش ها در حالت ترکيبي Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 1 32 47 رتبه بندي روش هاي زمانبندي اجراي قواعد مختلف هايهاي حالت درE نسبت -V.2.8روش روش بودن كاراتر رصد مختلف حالت درx-SJF Ex-SJF نسبت EE -V.1.8 بودن كاراتر درصد PRO-V.1.8 x-SJF PRO PRO به به x-SJF PRO Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 48 دستاوردهاي پايان نامه طGGراحی و پيGGاده سGGازی دو روش جديGGد بGGرای تخمين احتمال اجراي قواعد به منظور بهبود فرايند زمان بنGGدی اجرای قواعد ارايه چارچوبي جديد براي شبيه سازی رفتار پايگاه داده پويا و ارزيابی عملکرد روشهاي زمانبندي قواعد 49 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory کارهاي آينده توسعه روش مبتني بر EDFبGGا اسGGتفاده از تکنيGGک مGGورد استفاده در Ex-SJF مقايسه تطبيقي روشهاي زمانبندي به جGGز EDFبراسGGاس پايگاه قاعده با تعداد سطوح بيشتر از دو طراحي و پياده سGGازي سيسGGتم مGGديريت پايگGGاه داده پويGGا برمبناي عامل ها 50 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory مهم ترين مراجع مورد استفاده R. Alesheykh, An Effective Rule Selection approach in Active Database Systems, MSc Thesis, Amirkabir University of Technology (Tehran PolyTechnic), 2005. U. Schreier, H. Pirahesh, R. Agrawal and C. Mohan, “Alert: an Architecture for Transforming a Passive DBMS into an Active DBMS”, in proc. of the 17th VLDB Conference , Barcelona, September, 1991. E.N. Hanson, “Rule Condition Testing and Action Execution in Ariel”, in proc. of the ACM SIGMOD International Conference on Management of Data, San Diego (Calif), 1992. A. Vadua, “Rule Development for active database”, PhD Thesis, CS Department, University of Zurich, 2001. A. Geppert, S. Gatziu, K. R. Dittrich, H. Fritschi, and A. Vaduva, “Architecture and implementation of the active objectoriented database management system SAMOS”, Technical Report 95.29, CS Department, University of Zurich, 2001. Rohollah Alesheykh, A. Abdollahzadeh, “Evaluation and Comparison of Rule Scheduling Approaches ndin Active Database Systems”, in Proceedings of the 2 IASTED international Multi-Conference on Automation, Control, and Information Technology (ACIT’05), June 20-24, 2005, Novosibrisk, Russia. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 51  ادامه-مهم ترين مراجع مورد استفاده A. P. Buchmann. “Architecture of Active Database Systems”, in the Active Rules in Database Systems. Springer, 1999. S. Chakravarthy. “Architectures and monitoring techniques for active databases: An evaluation”, Technical Report TR-92-041, University of Florida, Gainesville, FL, 1992. P. Rönn, “Two Approaches to Event Detection in Active Database Systems”, MSc Thesis, CS Department, University of Skövde,Sweden, 2001. S. Ceri, C. Gennaro, S. Paraboschi, G. Serazzi, “Effective Scheduling of Detached Rules in Active Databases”, IEEE Transaction Knowledge and Data Engineering, 15(1), 2003. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 52 مقاالت چاپ شده Rasoolzadegan, A.; Alesheykh, R.; Abdollahzadeh, A.; “A New Approach for Event Triggering Probability Estimation in Active Database Systems to Rule Scheduling Improvement ”, 2nd IEEE International Conference on Information & Communication Technologies: From Theory To Applications, ISBN: 0-7803-9521-2, Damascus, Syria , April 24 - 28, 2006, Available in: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=16848 78&isnumber=35471. Rasoolzadegan, A.; Alesheykh, R.; Abdollahzadeh, A.; “Measuring Evaluation Parameters in Benchmarking Rule Scheduling Methods in Active Database Systems”, The IEEE International Conference on Computer and Communication Engineering, Kuala Lumpur, Malaysia, 2006. راي تخمينKK «ارائه روشي جديد ب، احمد عبداله زاده، روح الله آل شيخ،عباس رسولزادگان ،»د در آنKKاحتمال وقوع قواعد در پايگاه داده پويا به منظور بهبود زمانبندي اجراي قواع ،رانGG ته،1384 بهمن6-4 ،رانGGامپيوتر ايGGاالنه انجمن کGGدر مجوعه مقاالت يازدهمين کنفرانس س .ايران Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 53 گزارش فنی مرتبط با موضوع پايان نامه Rasoolzadegan, A ., Abdollahzadeh, A., “ADSS: Active Database System Simulator to Compare and Evaluate Rule Scheduling Methods”, Technical Report, Department of Computer Engineering, Amirkabir University of Technology, Tehran – Iran, September 2006. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 54 مقاالت ارسال شده عباس رسولزادگان ،احمد عبداله زاده « ،ارائه روش جديد زمانبندی قواعKKد در پايگاه داده پويا برمبنای بهبود فرايند تخمين احتمال اجرای قواعد» ،نشريه علمی و پژوهشی دانشگاه صنعتی اميرکبير. عبGGاس رسGGولزادگان ،احمGGد عبدالGGه زاده EX-SJFPRO­-V.2.8 « ،روش جديKد زمانبندي قواعد بر مبناي تخمين احتمKKال اجKKراي قواعKKد در پايگKKاه داده پويا» ،پانزدهمين كنفرانس مهندسي برق ايران 27-25 ،ارديبهشGGت ،1386مركز تحقيقات مخابرات ايران ،تهران ،ايران. عباس رسولزادگان ،احمد عبداله زاده :ADSS « ،شبيه ساز سيسKKتم پايگKKاه داده پويا براي مقايسه تطبيقي روشKKهاي زمانبنKKدي قواعKKد» ،پGGانزدهمين كنفرانس مهندسي برق ايران 27-25 ،ارديبهشت ،1386مركز تحقيقGGات مخGGابرات ايران ،تهران ،ايران. 55 ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory دانشكده مهندسي كامپيوتر و فناوری اطالعات دانشگاه صنعتي اميركبير با تشكر و سپاس از حضور و توجه شما Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 56 زمينه هاي تحقيقاتي سيستم هاي پايگاه داده پويا معماري پردازش قواعد ‏FCFS ‏EDF ‏Ex-SJF ماشينهاي حالت محدود گراف وابستگي رويداد ‏Petri Net اليه اي يکپارچه پايه اي ؟ زبانهاي برنامه زبانهاي پرس و جوي نويسي همه منظوره پايگاه داده توزيع شده رويداد توزيع شده … ‏SQL99 ‏SAMOS ؟ ... کنترل ترافيک هوايي تشخيص همزمان توزيع شده ؟ New زبانهاي تعريف و توصيف قواعد زبان شرط-عمل سطح برنامه کاربردي 57 ‏Vadua سيستم هاي مبادله سهام رويدادهاي ترکيبي ؟ فرآيند نرم افزاري توليد قواعد سيستم مديريت بازار اتفاقي اولويت ايستا نگهداري توليد قواعد ‏Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory تجزيه و تحليل زماني ‏Vadua قواعد مديريت جريان کار تشخيص زمانبندي چرخه اجرا رويداد کاربرد تشخيص رويدادهای ترکيبی K. Dittrich, S.Gatziu, A.Geppert, eds.(The ACT-NET Consortium), “The active database management system manifesto: a rulebase of ADBMS features”, Sigmod Record, 25(3): 40-49, 1996. H. Fritschi and Z. Flaach, “A Component Framework to Construct Active Database Management Systems”, PhD Thesis, CS Department, University of Zurich, 2002. R. M. Sivasankaran, J. A. Stankovic, D. Towsley, B. Purimetla and K. Ramamritham, “Priority Assignment in Real-Time Active Databases”, The International Journal on Very Large Data Bases, 5(1), 1996. A. Kotz Dittrich and E. Simon, “Active Database Systems: Expectations, Commercial Experience, and Beyond”, Active Rules in Database Systems, Berlin: 1999. AmirkabirSpringer-Verlag, University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 58 روش های جلوگيری از ايجاد چرخه اجرا A. Vadua, “Rule Development for active database”, PhD Thesis, CS Department, University of Zurich, 1999. A. Kotz Dittrich and E. Simon, “Active Database Systems: Expectations, Commercial Experience, and Beyond”, Active Rules in Database Systems, Berlin: SpringerVerlag, 1999. J. Bailey , A. Poulovassilis and P. Newson, “A Dynamic Approach to Termination Analysis for Active Database Rules”, in proc. of the First International Conference on Computational Logic, 2000. J. Bailey and A. Poulovassilis “An Abstract Interpretation Framework for Termination Analysis of Active Rules”, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, 1999. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 59 زمانبندی اجرای قواعد An Effective Rule Selection approach in Active Database Systems, MSc R. Alesheykh, Thesis, Amirkabir University of Technology (Tehran PolyTechnic), 2005. R. Alesheykh, A. Abdollahzadeh, "Evaluation of Shortest Job First Approach for Rule Scheduling in Active Database Systems", in the Proceedings of the 9th IASTED International Conference on Artificial Intelligence & Soft Computing (ASC'05), Benidorm, Spain, September 2005. R. Alesheykh, A. Abdollahzadeh, "Evaluation and Comparison of Rule Scheduling Approaches in Active Database Systems", in the Proceedings of the 2nd IASTED international Multi-Conference on Automation, Control, and Information Technology (ACIT’05), Russia, June 2005. A. Kotz Dittrich and E. Simon, “Active Database Systems: Expectations, Commercial Experience, and Beyond”, Active Rules in Database Systems, Berlin: Springer-Verlag, 1999. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 60 زمانبندی اجرای قواعد E. N. Hanson and J. Widom, “An Overview of Production Rules in Database Systems”, In the Knowledge Engineering Review, 8(2):121-143, 1993. R. M. Sivasankaran, J. A. Stankovic, D. Towsley, B. Purimetla and K. Ramamritham, “Priority Assignment in Real-Time Active Databases”, The International Journal on Very Large Data Bases, 5(1), 1996. S. Ceri, C. Gennaro, S. Paraboschi, G. Serazzi, “Effective Scheduling of Detached Rules in Active Databases”, IEEE Transaction Knowledge and Data Engineering, 15(1), 2003. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 61  توليد و توسعه قواعد،توصيف A. Vadua, “Rule Development for active database ”, PhD Thesis, CS Department, University of Zurich, 1999. N. W. Paton and O. Diaz editor, “ Active Rules for Database Systems ”, Springer-Verlag, 1998. A. P. Buchmann. “Architecture of Active Database Systems”, in the Active Rules in Database Systems. Springer, 1999. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 62 کاربرد سيستم های پايگاه داده پويا K. Dittrich, S.Gatziu, A.Geppert, eds.(The ACT-NET Consortium), “The active database management system manifesto: a rulebase of ADBMS features”, Sigmod Record, 25(3): 40-49, 1996. M. Berndtsson and J. Hansson, “Workshop Report: The First International Workshop on Active and Real-Time Database Systems (ARTDB-95)”, ACM Sigmod Record, 25(1): 64-66, 1996. A. P. Buchmann, C. Liebig, “Distributed, Object- Oriented, Active, Real-Time DBMSs: We Want It All -- Do We Need Them (At) All?”, Annual Reviews in Control, Vol. 25, Elsevier, January 2001, Selected paper from IFAC/IFIP Workshop on Real-Time Programming, 1999. R. E. Iliffe, P. W. H. Chung, T. A. Kletz and M. Preston, “The application of active database to the problems of human error in industry”, Journal of Loss Prevention in the Process Industries, (13): 1926, 2000. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 63 معماری سيستم های پايگاه داده پويا A. Vadua, “Rule Development for active database”, PhD Thesis, CS Department, University of Zurich, 1999. A. P. Buchmann. “Architecture of Active Database Systems”, in the Active Rules in Database Systems. Springer, 1999. S. Chakravarthy. “Architectures and monitoring techniques for active databases: An evaluation”, Technical Report TR-92-041, University of Florida, Gainesville, FL, 1992. N. W. Paton and O. Díaz, “Active database systems”, ACM Computing Surveys (CSUR), 31(1):63-103, 1999. A. P. Buchmann, C. Liebig, “Distributed, Object- Oriented, Active, Real-Time DBMSs: We Want It All -- Do We Need Them (At) All?”, Annual Reviews in Control, Vol. 25, Elsevier, January 2001, Selected paper from IFAC/IFIP Workshop on Real-Time Programming, 1999. Amirkabir University of Technology, Computer Engineering Faculty, Intelligent Systems Laboratory 64