A SIMULATION BASED STUDY ON THE CONCURRENT EXECUTI

1AppearsinJournalofParallelandDistributedComputing,Vol.20,No.1,pp.20-42,Jan.1994Firstversionsubmitted:March1990.Revised:December1990,December1991,March1992ASIMULATIONBASEDSTUDYONTHECONCURRENTEXECUTIONOFRULESINADATABASEENVIRONMENTLouiqaRaschid,1,3,5TimosSellis2,4,5andAlexiosDelis4UniversityofMarylandCollegePark,MD20742ABSTRACTThispaperpresentsourresearchontheconcurrentexecutionofrulesinadatabasemanagementsystem(DBMS).Concurrentaccesstothedatabasewillresultinahigherthroughputforruleexecution,anditwillallowmultipleuserstoaccessthedatabase.Traditionally,serializabilityhasbeenusedasacorrect-nesscriterioninDBMSanditisdefinedonthebasisofread/writeconflictsbetweentransactions.Ruleexecutionhastheadditionalconstraintthattheconditionsofrulesmustbetrueinthedatabasefortheactionstoexecute,andrulesmustfailwhentheirconditionsarenolongertrue.Acorrectnesscriterionfortheconcurrentexecutionofrulesisthusdefinedonthebasisoftheconflictsbetweentheconditionsandtheactionsoftherules.ThisapproachiscomparedtoAIconflictresolutiontechniques.Wedevelopalockingbasedprotocoltoguaranteeacorrectexecution.Wediscusstheextensionstoaconventionaltransactionmanagertosupportthisprotocol.Oneextensiondealswithlockmanagement;informationonthepossibleconflictsbetweenconditionsandactionsofrulesisusedtoprovidegreaterconcurrentaccesstotherelations,basedonanewlockcompatibilitymatrix.Thesecondextensionusestheconceptofnestedsubtransactionstoallowconcurrentexecutionwithinasingletransaction.TheperformanceoftheconcurrentexecutionofrulesisstudiedbysimulatingaDBMStransactionprocessingenvironment.Per-formancemeasuresincludetransactionthroughputcomparedtoaserialexecution,percentageofdiskutil-ization,andthenumberoftransactionsrestartedduetodeadlocks.Weidentifysomecharacteristicfeaturesoftherulesandthedatabase,andstudytheirimpactontheperformance.Theimpactofusingdifferentschemesthatcontrolconcurrentaccesstotherelationsandpages,theeffectofvaryingthesizeofthedatabaseandthenumberofrulesexecutingconcurrently,andtheeffectofskewinthedistributionofthelocksarestudied.Keywords:concurrentruleexecution,productionrules,serializability,nestedsubtransactions,locking-basedprotocols.1ResearchsponsoredpartiallybytheNationalScienceFoundationunderGrantsDMC-8814989andIRI-9008208andbyUMIACS.2ResearchsponsoredpartiallybytheNationalScienceFoundationunderGrantsIRI-8719458andIRI-9057573(PYIAward),byDECandBellcore,bytheAirForceOfficeforScientificResearchunderGrantAFOSR-89-0303andbyUMIACS.3DepartmentofInformationSystems4DepartmentofComputerScience.5AlsowithUniversityofMarylandInstituteforAdvancedComputerStudies(UMIACS).11.INTRODUCTIONFutureapplicationssuchasengineeringinformationsystemsanddesigndatabasesformanufactur-ingproblems,willrequiretheintegrationofrule-basedreasoningwithdatabaseprocessing,sinceitisexpectedthattheseapplicationswillinvolvetheuseoflargeknowledgebases.ThecurrentfunctionalityofDataBaseManagementSystems(DBMS)mustbeenhancedtoprovidesupportforrule-basedreason-ing.Inthispaper,wefocusourattentiononintegratingforward-chainingrules,whicharesimilartopro-ductionrules[19],withrelationaldatabasesystems,andimplementingrulesub-systemsusingDBMStechnology.InthecontextoftheDBMS,therulescouldsupportintegrityconstraintmaintenance,imple-menttriggersandalerterswhichmonitordatabasestates,derivenewinformationorcheckforsecurityorotherviolations.Unlikedeductivedatabases[23],wheretherulesprimarilyretrievedata,rulesinDBMSprimarilyexecuteviaupdatesmadetothedatabase.RuleshavethegeneralformIFCONDITIONTHENACTION.TheCONDITIONisalook-upoverthedatabase.TheACTIONpartofarulespecifiesasequenceofprimitiveoperations,suchasinsertionsanddeletionsofdata,tobeperformedonthedatabasewhentheCONDITIONissatisfied.Efficiencyisofmajorconcernwhendealingwithlargerulebases.OneresearcheffortinDBMSruleprocessinghasbeentoextendthesyntaxofproductionrulelanguageswithset-orientedconstructsandusemoreefficientset-orientedDBMSqueryprocessingstrategiestoevaluateconditionsandexecuteactionsofrules.Thisresearchhasbeenreportedin[8,9,10,15,36,37,44].Parallelismhasalsobeenusedtoimprovetheefficiencyinexecutingruleactionsaswellasinevaluatingconditions[2,6,16,17,18,20,24,27,34,35,39].Researchreportedin[2,6,18,34,35,39]hasinvestigatedtheexecutionofanumberofrulesinparallel,andthecorrespondingspeedupinexecutiontimeinmultiprocessorsystems.Ourresearchisinasimilardirection,butfocusesontheproblemofconcurrentexecutionofrulesinaDBMS.InaDBMSenvironment,averyimportantissueisthegreateraccessibilityofthediskresidentdatabase,duringexecution.Higheraccessibilityprovidesgreaterthroughputanddiskutilization;thisisincontrasttospeedupinexecutiontime,whichismorerelevantinaparallelimplementationofAIruleenvironments.Traditionally,inrule-basedAIapplications,thedatahasresidedinmainmemory.Executingtherulesinaprogramissimilartoexecutingasingleprogramwithexclusiveaccesstomainmemoryresidentdata.Incontrast,aDBMStraditionallysupportsaccessesfrommultipleuserstoalarge,diskresidentdatabase.Theoperationsofeachuserareencapsulatedwithinatransaction,whichhasthepro-pertyofindivisibility,i.e