DOC

Measuring the Inconsistencies Between Process Model and Process Execution

By Dean Ortiz,2014-12-15 02:45
7 views 0
Measuring the Inconsistencies Between Process Model and Process Execution

    Measuring the Inconsistencies Between

    Process Model and Process Execution ChineseJournalofElectronics

    Vo1.16,No.2,Apr.2007

    MeasuringtheInconsistenciesBetweenProcess

    ModelandProcessExecution

    LIZhi,HUANGShangteng,GONGBo.andHEXingui.

    (1.DepartmentofComputerScienceandEngineering,ShanghaiJiaotongUniversity,Shanghai200030,China)

    (2.InstituteofCommandandTechnologyofEquipment,Beijing101416,China) (3.SchoolElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871,China)

    Abstract——Atpresent.usingProcessmodelstosimu-

    late,validateandguidesoftwaredevelopmentisanimpor-

    tantapproachtoimprovesoRwaredevelopmentprocesses,

    andenhancethequalityofsoftwareproducts,butinreality

    theactualexecutingProcessalwaysdeviatesfromtheex-

    pectedprocessmode1.HowtodetectandmeasuresuchiIl_

    consistenciesisachallengingtask.Thehighlydynamicand

    exceptionalnatureofsoftwareprocessesmeansthatsim-

    pieyes-noanswerscarl?Ytoolittleinformationaboutthe

    significanceofanygiveninconsistency.Managersneedto

    anderstandwhereaninconsistencyoccursandhowsevere

    thatinconsistencymightbebeforetakinganycorrective

    action.ThisPaPeruseseventtreestorepresentthePro-

    cessmodelandProcessexecution,putsforwardsMinCost

    andSimilaritymetricstomeasuretheseverityofincon.

    sistencies,anddesignsanalgorithmtoassistincompare eventtreesandcomputemetrics.

    Keywords——Processmodel,Processexecution,Incon-

    sistency.

    I.Introduction

    Inrecentyears,therehasbeenanincreasinginterestinpro- cesstechnologiestosimulate,improve,andsupportsoftware developmentprocesses.BasedonProcessmodelinglanguages (PML),processtechnologiesexploitanexplicitrepresentation oftheprocess(calledprocessmode1)thatspecifieshowpeople shouldinteractandwork,andhowandwhenthecomputerized toolsusedintheprocessshouldbeusedand/orautomatically activated.Theprocessmodelcanthenbeenactedbyaprocess engine,whichguidesandsupportsthehumanagentspartici- patingintheprocessandautomatestheexecutionofanumber ofprocesssteps(calledprocessexecution).

    Whendesigningprocessandprocessmodels,itisimpos- sibletoforeseeallunexpectedsituationsanddeviationsfrom processexecution,andcompletelyspecifyinadvanceandonce foral1.Theinconsistenciesbetweenactualprocessbehaviors andexpectedprocessbehaviorswillemerge.Emergingsuch inconsistenciesisnotterrible;sometimeweneedsuchdevia.- tionswhichdenotetheimprovementfocuses.Wemustbeable todetect,measure,tolerate,andsolvesuchinconsistencies. CookandWolftcallrelatedtechniquesasprocessvalidation. rhetechniquesborrowfromvariousareasofcomputersci- ence,includingdistributeddebugging,concurrencyanalysis, andpatternrecognition.

    Thispaperdescribestheprocessmodelandprocessexe

    cutionastwoeventtrees,putsforwardamethodtomeasure

    andanalyzeinconsistenciesbetweentwoeventtrees,compute theSimilaritymetricbetweenthemandminimalcostofcon- vertingprocessexecutioneventtreetocorrespondingprocess modeleventtree.Thesemetricsaretailorableandgivepro- cessengineerscontroloverdeterminingtheseverityofdifferent typesofdiscrepancies.

    Theremainderofthispaperisorganizedasfollows.Sec. tionIIintroducestheresearchonthearea,andcompareswith thesolutiondescribedinthispaper.SectionIIIdefinesevent treesforprocessmodelandprocessexecution.SectionIV putsforwardtwometrics:MinCostandSimilarity,andde. signsaconversionalgorithmofconvertingprocessexecution eventtreetoprocessmodeleventtree.SectionVisacase,il- lustratinghowtousethetwometricsandconversionalgorithm tomeasureandanalyzeinconsistenciesbetweenaspecificpro- cessmodelandprocessexecution.Asummaryofthiswork andconclusionsarethereofinSectionVI.

    II.RelatedDrk

    Firstofall,relatedworkfocusingontheinconsistencies anddeviationsisdiscussed:

    ?CookandWolfJdescribeprocessmodelandprocessex_ ecutionaseventstreams,whichisakindofsequentevent characterstring;Andthen,usesimplestringdistanceand nonlinearstringdistancetoquantitativelymeasurethecor- respondencebetweentwoeventstreams.Theshortcomingsof themethodareveryobvious:(1)Usingeventstreamstringsto representdevelopmentactivitiesistoosimple,whichisunable tosimulatethecomplexrelationshipsbetweendifferentactiv. ities,suchasconcurrence,repetition,andembranchment,and soon.(2)Themethodca4-1onlymeasurethecorrespondence

    betweenprocessmodelandprocessexecution,itdoesn'tpro- videoptimalconversionmethods.

    ManuscriptReceivedJan.2006;AcceptedDec.2006

224ChineseJournalofElectronics2007

    ?Cugolaeta1.tzJdefneaformalframeworkforreasoning aboutinconsistenciesanddeviationsinaprocess.Theirap- proachisdirectedtowardprocessesthatarecontrolledbya processsupportsystemusinganenactedmode1.Theirgoalis toenablethesesystemstoallow,coordinate,andresolvede- viationsfromthemode1.Inthisrespect.theirworkissimilar toours,buttheydonotusedataderivedfromtheprocessex- ecutiontomeasurethedeviations.Ourworkeffectivelycom- plementstheseotherapproachestoprocessimprovementby raisingconfidenceinthecorresDondencebetweenformalmod- elsandexecutionsofprocesses.Cugolausesinconsistencyand deviationtodescribethedifferentkindsofdiscrepanciesbe- tweenhuman-centersystemandprocesssupportsystem.This paperdoesn'tdistinguishthesetwoconcepts.

    1.Event

    III.EventTrees

    Thispaperviewsprocessesasatreestructureofactions performedbyagents,eitherhumanorautomaton,possibly workingconcurrently.FollowingWl0lfandRosenblum.weuse anevent.basedmodelofprocessactions,whereaneventisused tocharacterizethedynamicbehaviorofaprocessintermsof identifiable,instantaneousactions,suchasinvokingadevelop- menttoolordecidinguponthenextactivitytobeperformed. TheconceptanddefinitionofeventborrowsfromRefs.1and

    [7].

    Thetimethataneventconsumesisshorterthanarelative timegranularity.Ifallactivityspanssomesignificantperiod oftime.itshouldberepresentedbytwoormoreevents.For example,ameetingcouldberepresentedbya"begin?meeting'' eventand"end-meeting"eventpair.

    Thispaperfocusesonbehavioralprocess-modelingfor? malisms,includingmodelsbasedonstatemachines(e.g., Statemate),Petrinets(egSLANGandFUNSOFTNets), procedurallanguages(e.g.,APPL/A),andrule-basedlan- guages(e.g.,Oz).Thesebehavioralprocess-modelingfor- malismscanbeeasilymappedtotheeventbasedtree.

    2.Eventtrees

    Thispapersimulatesdevelopmentactivitiesandprocess modelsastwotreescomposedofevents(calledeventtree). Sucharchitecturecanrepresentcomplexrelationshipbetween developmentactivities.ThesetwoeventtreesarecalledExe- cutioneventtreeandModeleventtreerespectively.Execution eventtreerepresentsanactualeventstructureofprocessexe- cution:ontheotherside,Modeleventtreerepresentsadesired orprescribedeventstructureofprocessmode1.Measuringthe inconsistenciesbetweenprocessmodelandprocessexecution iscastasquantitativelymeasuringhowcloseExecutionevent treeresemblesModeleventtree.

    Wleexpecttodetectinconsistenciesbetweenthesetwo eventtrees,usemetricstomeasuretheseverityofsuchin? consistencies,andcomputetheminimalcostofconvertingEx- ecutioneventtreetoModeleventtree.Themetricsthatwe willuseareMinCostandSimilarity

    formanceofprocessmodelandprocessexecution.

    1.MinCost

    MinCostmetricreferstotheminimalcostofconverting ExecutioneventtreetoModeleventtree,usingthreetypesof conversionoperations,insertions,deletions,andsubstitutions. Everyconversiontypeisweighted.BeforedefiningMinCost metric,thispaperdefinesthesethreeconversiontypesofevent trees.

    Definition1aandareExecutioneventtreeand

    Modeleventtreerespectively.Let'sdefineconversionT: Da>D.Tincludesfollowingthreeconversiontypes: (1)Substitutionconversion(0)>b,r

    (2)Insertionconversion()>b,q

    (3)Deletionconversion(0)>,P

    Inupperdefinition,a?Da,b?D;isblanksymbol;P,

    qandrarethecorrespondingcostsofo-,and.

    Forconversion,ifa(0)?(6),0-performsonesubstitu-

    tionconversion,andr>0;otherwiser=0.

    SupposeT_.representsthebackwardconversionofT, T:D口一>Da.Itisclearlythatisequivalentto,

    andisequivalentto.

    Tofacilitatecomputerstoprocessupperelements,thispa- perusesthefollowingconstrictiveformtorepresentconversion path,whichcanbeeasilyexpressinarrays.

    T=[(ll,ol,6l,rlplq),…】

    Definition2aandareExecutioneventtreeand

    Modeleventtreerespectively.Theweighteddistancebetween aandisMinCost.MinCostistheminimalcostoftrans- formingainto.

    MinCost=Ni×q+Nd×P+Ns×r(1)

    Followingcriterionsmustbesatisfied.

?Supposing0?D,b?D,ifa<b,thenT(a)<(6);

    Ifaandbareincomparable,thenT(a)andT(b)areincom- parable,whichmeaJlstherelationshipoffather?sonremains unchangeable.

    ?Supposinga?D,b?D,ifa=b,thenT(a)=(6);

    Ifa?b,then(0)?(6),whichmeanstheeventnodesofa

    wouldnotbesplitormerged.

    ?Supposing0?D,b?D,andT(a)orT(b)isn'tblank,

    ifha(0)<ha(6),then((0))<((6)),whichmeansthe sortingsequencesofpostfixesremainunchangeable. Inupperdefinition,whenP=1,q=1,andperforms conversions.r=1.

    InEq.(1),Ni,NdandNsarethecountsofconversion insertions,deletions,andsubstationsduringtransformingot into.q,P,andraretheweightsofconversioninsertions, deletions,andsubstations.

    Toprompttheunderstandingofuppertwodefinitions,fol- lowingdefinitionsandconceptsareneeded.

    Definition3Imagingthedomainofasignedtreeais D:aisthefunctionfromDto?,a:D>?.?isalim-

    itedsetofsigns;?(a)isthecountofeventnodesofa,Da

    representsthedomainofa.

    IV.MetricsandConversionAlgorithmD

    Thispaperputsforwardtwometricstomeasurethecon- Definition4Supposing0and6istwDeVentnodesof Iffthereisa,?and0.=6,then06

MeasuringtheInconsistenciesBetweenProcessModelandProcessExecution225

    Ifz=0.thena=b.

    Ifa<b,thenaiscalledthefatherofb,andbistheson

ofa.

    Iffa<bandbaareallfalse,thenaandbareincompa- rable.

    DIefinition5Deftneoperatorh.:D>N(Nisthe

    setofpositiveinteger),hsortseventnodesofDaccording

    topostfixrepresentation.

    Definition6Supposeaissignedeventtree,a?Da,

    thensigna/representsthesub-treeofawhoserootnodeis a.

    2.Similarity

    Whencomparingtheinconsistenciesbetweentwoevent trees.howserioustheinconsistenciesare?Ifthereisnota settledbenchmark,comparingtheseverityofdifferentincon

    sistenciesofeventtreespairsisimpossible.Thispaperputs forwardSimilaritymetric.

    Definition7aandareExecutioneventtreeand

    Modeleventtreerespectively.TheSimilaritymetricbetween themisdefinedas:

    m=l一而MinCost

    where?(a)and?()arethenumbersofeventnodesofaand

    8respectively.Thedivisoristheutmostconversioncost.The valueofSimilaritymetriciswithin0and1.Whentheseevent treesareidentica1.Similaritymetricisl:whentheseevent treesaredifferententirely,Similaritymetricis0.Although technicallythevalueofSimilaritymetricmaybenegative(e.g., ifalleventsaredeletedandsomeothersareinserted),thisis impractica1.

    ThisPaperusesthestandardstatisticalcorrelationrules ofthumbt6Jtojudgetheseverityofcorrespondence.When Similaritymetricisbounded0and0.5,thecorrespondence

    betweentwoeventtreesisweak;whenSimilaritymetricis bounded0.5and0.7,thecorrespondencebetweentwoevent treesismoderate;whenSimilaritymetricisbounded0.7and 1,thecorrespondencebetweentwoeventtreesisstrong. 3.Conversionalgorithm

    Wledevelopasupportingsoftwaretoassistinmeasuring theinconsistenciesbetweenprocessmodelandprocessexecu- tion;thecorealgorithmcancomputethevaluesofMinCost andSimilaritymetrics.

    ThealgorithmexpressestwoeventtreesasamatrixD: thelengthandwidthofDarethecountsofeventnodesplus 1(thatism+1,n+1).ThevalueofD(i,)theconversion

    costoftransforming/6intoa/,meetingtherules(1)(3)

    inDefinition2.D(n,m)istheminimalcostofconvertinga into.

    Supposinga=^:(),b=^();aisaneventnodeof

    a,bisaneventnodeof;andhaa)=J,(6)=i.

    Inputthecountsofeventnodesofeventtreesand8. ?(a)=m,?()=n.

    OutputMinCostmetricandSimilaritymetric. Followingcodeillustratesthebasicstructureofthealgo- rithm.

    1D(0,0)=O;

    2LoopJ=1,m

    3D(O,J)=?(a/0)g;//a:hal(j)

    4Endloop

    5Loopi=1."

    6D(i,0)=N(fl/b)p;//b=^l)

    7Endloop

    8Loopi=1.n

9LoopJ=1,m//a=halU),b=^1(i)

    10E(0,0)=O;

    11Loopl=1,t//t:r(a)

    12E(0,1)=E(O,l1)+N(a/a.1)g;

    13Endloop

    14E(0,t+1)=E(0,t)+g;

    15Loopk:1,8//8=r(b)

    16E(k,0)=E(k1,0)+N(~/b.k)p;

    17Endloop

    18E(s+1,0)=E(s,0)+p;

    19Loopk=1,8

    20Loopl=1,t

    21E(k,1):min(E(k-1,1)+?(/6.)p,E(k,l1)+N(a/a.f)$ q,E(k1,l1)+D(u,"));//u=hfl(b.),"=ha(a.1) 22Endloop

    23Endloop

    24Loopl:1,t

    25E(s+1,1)=min(E(s+1,l1)+N(a/a.1)q,E(s,1)+P, E(O,l1)+D(i,"));//"=ha(a.1)

    26Endloop

    27Loopk=1,8

    28E(k,t+1)=min(E(k1,t+1)+N(fl/b.k)P,E(k,8)+q, E(k1,0)+D(u,J));//u=^(6.k)

    29Endloop

    30D(i,J)=min(E(s,t+1)+P,E(8+1,t)+q,E(s,t)+r);

    31Println("MCost="+D,m))

    32Println("Similarity="1D(n,m)/Max(p,q,r)*Max(m,))

    Giventwoeventtrees,thecountsofeventnodesaremand

    n,thecomplexitydegreeofthealgorithmisO(mn).

    V.ACaseStudy

Report this document

For any questions or suggestions please email
cust-service@docsford.com