Business Rule Computation in Distributed Organizations

Business Rule Computation in Distributed Organizations

Business Rule Computation in Distributed Organizations George Dimitoglou Research Advisor Prof. Shmuel Rotenstreich Outlin e Introduction Related Work Problem Description Solution & Results Conclusions Future Work 2

Environme nt Complex, dynamic, distributed organizations Activities Acquisition of services, resources Collaboration, team formation Rules & Constraints Business Rules are statements of How to do business Faster, systematic decisions 3 Objective s To investigate Business Rule Management Distribution Execution Develop a general computational model for constraint computation 4 Outlin e

Introduction Background and Related Work Problem Description Solution & Results Conclusions Future Work 5 Related Work: Organization Theory Organizational Design Formalization (standardization): Number of rules, documentation and policy manuals Theories Bureaucracy: order, uniformity, consistency, well-defined hierarchy, record-keeping, rules. Systems Theory: inputs, outputs, transformations and prescribed

interactions Organization Structure Complexity Horizontal (specialization), Vertical (hierarchy), Spatial (geographic) Centralization/decentralization decision-making locations (not spatial) within the organization Theories Closed vs Open Systems: Simple, static, introverted environments Complex, dynamic, environment-interacting 6 Related Work: Computer Science 7 Related Work: Data-Centric Approach 8

Related Work: Process-Centric Approach 9 Outline Introduction Background and Related Work Problem Description Methodology and Solution Results Conclusion Future Work 10

Problem Description Managing Constraints in distributed environments Existing approaches Small, static, contained, monolithic systems Shortcomings Centralization Lack of operation capability in dynamic environments Application-only interaction Lack of distributed operation Lack of Dynamic Rule support No real-time rule changes 11 Outlin e

Introduction Background and Related Work Problem Description Solution & Results Conclusion Future Work 12 Methodolog y Business Rules Formulation Developed/Extended a simple rule type classification Software prototype Devised methods for Rule processing Developed architecture for multiple rule engines and repositories Developed distributed and non-distributed processing algorithms Added features to enhance distributed processing 13

Business Rule Formulation Declarative statements that constraint, validate, compute, approve or perform any operation. Example rule (Stimulus/Response): R: if P1 PP2 P PPn then A1 P PA2 P PAk where n 1 is a conjunction of n predicates (conditions) k 1 is the set of conjunctions of k results (actions) Predicates (Pn) and results (Ak) express values of operands using relational operators from the set S ={>, <, , =, , } 14 Formulation Example Each Business Rule is described using XML 15 Business Rule Elements value

(Unique rule identifier) value (Matching applicable rules to tasks) LHS RHS (Administrative elements) 16 Business Rule Types Stimulus/Response Define what conditions must be met before an activity can legally take place: RSR: if P1 P2 ... Pn then A1 A2 ... Ak or,

RSR': when P1 P2 ... Pn then A1 A2 ... Ak Example: Task: check account balance, print a statement. Rule: RSR: if (client has an account) then (check account balance) (print statement) Task: add quarterly interest dividends to account. RSR: when (end of quarter) then (calculate interest) (add interest to balance) 17 Business Rule Types Operation Constraint Rules Define constraints that must hold before and/or after an activity. ROC: if P1 P2 ... Pn then [Q] A1 A2 ... Ak [S] where Q: pre-condition stating properties that must hold when activity is to be performed S: post-condition stating properties that will hold after the activity is completed. Example:

Task: withdrawing funds from a bank account ROC: if (client has an account) then [check account has funds] (withdraw amount) (print statement) [balance 0] 18 Business Rule Types Structure Constraint Rules Specify constraints on tasks, which must never be violated. Software Engineering class and loop invariants Class invariant: assertion describing a property, holding for all class instances. Loop invariant: assertion to be satisfied prior to the first loop execution, preserved at each iteration, and still hold on loop termination. Rule R has an invariance property for task T i: if R is valid in every computation state ("must Palways Phold") during processing of Ti. RSC: it must always hold that P1 P2 ... Pn or, RSC: it must always hold that

if P1 P2 ... Pn then A1 A2 ... Ak Example: RSC: it must always hold that (minimum balance=$100) RSC: it must always hold that if ( account = savings) then (minimum balance=$500) 19 Business Rule Types Computation Describe algorithm processing or equations. Extension (or general case) of Stimulus/Response Rules. Predicates are TRUE and activity is an algorithm execution or a computation. Example: RCR: y=f(x)

COMPUTE interest AS interest = principal * years * rate/100 Instantiate class Computation that parses parameters of the rule XML and call the relevant methods for execution. 20 Business Rule Lifecycle Rule execution can be formally expressed as a DFA R by the tuple: R= (Q, , q0, F, ) where Q: finite set of states : finite set of input events e. ={activate, trigger, execute, deactivate} F: set of final states. F={new, active, dormant} : transition function from Q x to Q so that (q, e) is a state for each state q and input event e. 21 Task Processing 22 The Business Rule Engine

(BRE) Components FIFO Queue Engine Repository (RuleBase) Interfaces Functionality Rule storage Search Enforcement 23 Task Processing Search-Match-ProcessEnforce

Search Collect Match Enforce (modify task) 1) Create candidate set 2) Resolve any conflicts 3) Create execution sequence 24 Rule Processing Algorithm ProcessTask ParseTask Parameters RetrieveRules Search Repository Store in candidate set CategorizeRules

Type-specific processing ResolveConflicts Check for conflicts Resolve Create execution sequence ApplyRules Modify task 25 Rule Processing Algorithm Time-Complexity Analysis Methods Time-Complexity Analysis Hash-based repository operations (search, retrieval) perform in constant time O(1). PARSETASK, RETRIEVERULES, CATEGORIZERULES, APPLYRULES perform in linear time O(n). Overall complexity depends on

RESOLVECONFLICTS Quick sort with O(nlogn) Empirical data Overall O(nlogn) 26 Conflict Resolution Conflict categories Sequence Conflicts. Affect rule execution sequence. Two applicable rules, one accepting the task and the other rejecting it. Parameter Conflicts. Two or more rules modify same task parameter, but compute its value using different formulas and produce different results. a) Rule A: modifies parameter - Rule B: with different values b) Rule A: Removes parameter - Rule B: adds it c) Rule A: Modifies parameter - Rule B: eliminates it

d) Rule A & B: Compute same parameter using different formulas. Resolution Dynamic (each time) while in the candidate set Execution sequence Resolution factors Rule Type Priority Timestamp 27 Distributed Rule Processing Overall Environment Multiple units of one or more organizations Some units collaborate others dont BREs scattered throughout BRE Locality BRE infrastructure

Underlying network of peer BREs BREs: Uniquely identifiable and addressable Shared and interconnected rule-sets Example: IF operand=value THEN . 28 Distributed Rule Processing Contd. Team Formation Team Leader Ad hoc team formation (TTL=2) BRE0: Team Leader Hash-table sharing. All rule results to team leader BRE0 Membership New members Existing members removed

Leader failure dealt via LEA Memory (Caching) Optimistic Fault Tolerance 29 Distributed Rule Processing Algorithm Additional Functionality Interaction with Resource Discovery mechanisms Query Propagation TTL for control Ad hoc team maintains storage of shared rule sets 30 Distributed Rule Processing Time-Complexity Analysis Multiple P2P-connected BREs Add network and communication costs Performance of processing a single task: where

k is the number of rule engines m represents a communication costs constant Overall: O(nlogn*m) 31 Nested Rules Single BRE IF operand=value THEN * Problem: Termination Solution: forbid loops during formulation (smart interface) Max occurrence limits in candidate set Multiple BREs IF operand=value THEN . Problem: Termination, Cascading rules - no global control Solution: Max cycle occurrence in candidate set Max depth-limit enforcement * All rule types are subject to nesting

32 Procedure s Ordered rule sequences Executed/enforced on task(s) as a single rule Precedence of execution over individual rules Advantages Additional, useful construct, controlling the order of rule execution For repetitive tasks, performance improvement (no conflict resolution) Disadvantages Black box User must ensure no conflicts 33

Procedure s Implementation (a) Sample procedure expression using XML and (b) the corresponding XML tree 34 Global Variables Distributed System View Variables with scope over organizational segments Lack of global control facilities No monitoring or controlling of activities Local & Global inter-dependent constraints Rule processing is unaware of such variables GVAR types: Counters (establish limits, tasks accepted/rejected) Advisories (express an advise or suggestion, BRE may enforce/ignore

35 Global Variables Implementation VALUE simultaneous_travel 5 wireless_connections 100 min_rescue_crew 3 GLOBAL VAR IABLE APPLICABLE TASKS TYPE SCOPE faculty_travel-request counter department wireless_net_access counter subnet rescue_operation (all) advisory universal

Distributed GVAR Network Master (read/write) Proxies (read) replicate everywhere algorithm Proxies faster GVAR lookups no bottlenecks Master consistency 36 Environment Snapshot 37 Task Temporal Relations BRE Memory Organizational Memory Learning Task Temporal Sequences

T1 happens before T2 (T 1 T2 ) T1 overlaps T2 Time delay Task Causal Sequences 1 T2) T1 causes a task T2 (T anti-symmetric irreflexive 38 Task Temporal Relations Implementation TEMPORAL SEQUENCES DEFINITION Def_ID 243 Scope

Task1 CS Dept, EE Dept. Law Schl. advising 567 Global : : 809 : : Global doctoral proposal

: : probation 335 pay_loans Relation Length before start during/ complete after delay : : causes Unit of

Time Task2 registration graduation 6 : : months doctoral defense : : : : send letter Distributed TSEQ Network Proxies contain both: Read-only Master contains both: Read/Write

REAL-TIME SEQUENCES Seq_ID 243 243 809 : : 567 Owner Task1 Timestamp1 Status1 Task2 Timestamp2 Status2 stdnt,181 meetAdvsr 1/3/01 12;15 Y RegForClass 2/3/01 9:30 Y stdnt.344 meetAdvsr 6/3/01 11:45 Y stdnt.676 : :

: : : : : : : : stdnt.852 onProbation 39 Performance Analysis Measurements Capacity Response Time (latency) Throughput Methodology Creation of multiple synthetic rule sets For Capacity Testing: Multiple, variable size rule loads For Latency and Throughput, multiple variable size rule loads with variable percentages of applicable rules: 1%, 10%, 25%, 75% and 100%

40 Performance Analysis Capacity Testing Repository type Synthetic data set (1 x rule=1342b) 55K (Java tuning required) > 105K, SAX limitation Memory-bound, CPU: idle Physical Memory (K) ID 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 BRE Memory Number of Rules Memory Usage (K) Foootprint (K) 1 17,084

117,820 100 17,992 118,092 1,000 18,896 120,124 2,000 19,876 119,576 5,000 22,684 122,404 10,000 28,104 135,408 15,000 33,584 135,860 20,000 39,116 150,676 25,000 44,432 149,736

30,000 48,812 149,144 35,000 55,568 172,224 40,000 60,240 172,748 45,000 66,140 174,784 50,000 71,076 173,616 55,000 75,052 180,760 60,000 80,796 180,696 65,000 86,688 206,996 100,000

125,264 255,248 105,000 163,840 303,500 150,000 179,816 344,808 200,000 232,084 351,844 250,000 292,332 501,508 300,000 337,144 502,924 350,000 389,432 499,180 400,000 425,196 531,164 450,000 464,156

582,704 460,000 457,116 581,348 Available File Cache 425,196 426,888 432,500 433,480 432,816 425,732 422,324 415,144 411,268 406,264 404,600 398,696 394,152 388,280 385,588 378,948

354,352 327,812 301,272 280,540 224,688 172,380 123,364 70,604 37,284 5,488 5,116 26,292 24,188 22,348 21,100 19,920 19,848 19,504 19,668 19,584 19,604 17,488 17,868 17,632

17,524 17,664 17,540 23,676 22,048 20,420 18,064 20,952 14,408 18,548 18,156 19,516 14,508 11,876 41 Performance Analysis Response Time (Latency) Testing Objective: BRE time to process single task with variable loads. Methodology: Load synthetic rule sets with variable applicable rule loads and send task. Results: strong relation between latency - % of applicable rules

Increase by a factor of ~11 Just doubles the latency 10-fold increase From 200 to 2000 rules 10-fold increase From 200 to 2000 rules 42 Performance Analysis Response Time (Latency) Results Task latency has little variation with same number of applicable rules, even with variable total loads. Same number of Applicable Rules over Single Task Latency (mm:ss.SSS) 10K/100K 00:08.905

10K/40K 00:08.156 00:08.750 10K/20K 00:01.375 100/100 00:00.000 100/1K 00:01.578 100/10K 00:01.172 00:01.728 00:03.456

00:05.184 00:06.912 00:08.640 00:10.368 43 Performance Analysis Throughput Objective: Determine max number of tasks that can be processed during a given period of time (sec, min, hr). Methodology: Same synthetic rule sets as with latency experiments. Results: throughput affected by % of applicable rules AND total rules 44 Performance Analysis Queuing Theory

Objective: BRE response times as a function of utilization (stress test) Methodology: used Throughput results (service rate). Results: 45 Performance Analysis Queuing Theory Results Result: a consistent way of identifying optimal BRE utilization at any rule load Utilization Stability Condition at p < 1 Max Throughput Saturation unstable BRE Utilization 1.0

46 Outline Introduction Related Work Problem Description Solution & Results Conclusions Future Work 47 Conclusions & Research Contributions

Original approach computation of distributed constraints. Software prototype proof-of-concept novel ideas (in the context of BR): minimalist expression of constraints in XML flexible rule formulation, minimal semantic specification Lightweight standalone/distributed rule engines Fast rule-searching algorithm Rule Management, Task Processing, Conflict Resolution Conflict resolution algorithm Building local caches for fault tolerance Managing global variables and ensuring consistency of temporal sequences Development of general computational model to solve problems in domains with

similar computation and distribution requirements. Tool-set to understand dynamic environments. 48 Future Work Variable rule enforcement Task generation Business rules and context: distributed BREs as context awareness processors Business rules and policy Automatic "bottom-up" and "top-down", business rule generation Bottom-up: local computations contribute in creating rules with global scope Top-down: automatic distribution of global rules and variables to local rule engines 49 Business Rule Computation in Distributed Organizations

George Dimitoglou Research Advisor Prof. Shmuel Rotenstreich Performance Analysis Compared to What? Repository Capacity (number of rules) 120000 BlazeAdvisor Repository GW BRE (single) 100000 Environment BlazeAdvisor System: Unknown Software footprint: > 500K GW BRE System: DELL 1.1Ghz, 512Mb RAM Software footprint: > 400K

80000 60000 GW BRE 40000 BlazeAdvisor 20000 0 51 Rule Processing as a Computational Model Objects Contain data, access methods, resources (i.e. BRE) Multiple interfaces Operations Service primitives with method handles Activities Collections of operations treated as a unit of work for the objects Environment Distributed, P2P (and client-server)

Constraints 52 Applying the Computational Model Model Military Nature/E cology Objects Contain data, access methods, resources and have multiple interfaces Personnel (soldiers, units), assets or resources (ships, planes, radars) they all interface differently. Operations

Service primitives with method handles Activities P(also procedures) Collections of operations treated as a unit of work for the objects Environment Distributed, P2P, c/s Personnel acquiring and using resources. Assets providing feedback and reporting. Personnel preparing aplane for mission. Assets participating n i an exercise. Distributed (geographically),

P2P (multi-national forces), c/s within own hierarchies. Distributed (where the nectar is), centralized hive. Constraints Military code, contextspecific rules, guidelines according to operational plans. Rules of flight, rules of nectar load, rules of hierarchy and reproduction. Biology Bees (guard, colony bees), assets (wings, stingers) and

interface differently (sting, fetch nectar, mate). Flying to flowers. Returning and reporting to hive. Ants (queen, female workers, males) Cells (store and retrieve signals) transmitted via assets (nerve cells) Carry food, mate. Chemical reactions. Build hives, collect nectar.

Build chambers, store food. Sequence of operations (chain reactions) Distributed Distributed or, (multiple ant centralized colonies) or centralized. Rules for Chemical and avoiding biological rules. obstacles, chamber usage. Complex Systems 53 Distributed nested rule

example Starting from BRE001: BRE001: 001.123: IF x=4 BRE003: 003.997: IF y=7 BRE019: 019.789: IF k=2 BRE678: 678.778: IF v=1 a) b) THEN THEN THEN THEN 003.977 019.789 678.778 001.123 Depth=3 does not mean stopping at BRE019. Depth=3 means above sequence 3X in the candidate set 54


Recently Viewed Presentations

  • Introduction to GHG Emissions Verification

    Introduction to GHG Emissions Verification

    Does the frame contain the information necessary to implement the sampling approach? Is the sampling approach suitable, given the nature of the parameters, the data collection method, and the information in the sampling frame? Is the proposed sample size adequate...
  • Basic Plot Types Archetypes - Boyd County Public Schools

    Basic Plot Types Archetypes - Boyd County Public Schools

    The original pattern or model from which all things of the same kind are copied or on which they are based. ... A larger-than-life character that often goes on some kind of journey or quest. ... Basic Plot Types Archetypes
  • NOTES Epiphany: a sudden insight or realization that

    NOTES Epiphany: a sudden insight or realization that

    "A&P" and "Araby" Form groups of 3 or 4. In your group, compare and contrast the epiphanies that the characters have in both "Araby" and "A&P" in at least one paragraph. Then answer the following question.
  • Natural Environments: The Atmosphere GG 101  Spring 2005

    Natural Environments: The Atmosphere GG 101 Spring 2005

    Natural Environments: The Atmosphere GG 101 - Spring 2005 Boston University Natural Environments: The Atmosphere GG 101 - Spring 2005 Boston University Myneni Jan-19-05 Course Info (2 of 6) Three main topical areas (1) basic astronomical relationship between the Earth...
  • งานนำเสนอ PowerPoint

    งานนำเสนอ PowerPoint

    What……nationality? Minsuh and Minjoo. What's. their. nationality? They are. South. Korean.
  • Hampshire Pension Fund Annual Employers Meeting 26 October

    Hampshire Pension Fund Annual Employers Meeting 26 October

    Hampshire Pension Fund Annual Employers Meeting 26 October 2012 10:00 am Hampshire Pension Fund Annual Employers Meeting 26 October 2012 Welcome Councillor Mark Kemp-Gee Chairman, Pension Fund Panel Hampshire Pension Fund Annual Report for 2011/12 Carolyn Williamson Director of Corporate...

    CApture the Flag, Cuisenaire Rods, page 26-28 - Rules to Play Capture the Flag. 1)This game is for 2 player. The object is to cover the last square on the Flag board game with Cuisenaire Rods.
  • FEMA Transportation FEMA Transportation Update April 23, 2014

    FEMA Transportation FEMA Transportation Update April 23, 2014

    FEMA. Plan Manage Sustain. FEMA. FEMA Transportation Update . April 23, 2014. Darrell Ransom. Plan Manage Sustain ... HHS= Health & Human Services IMAT= Incident Management Assistance Teams. MA= Mission Assignment MERS= Mobile Emergency Response System/Support.