Working Paper    Version of July 29 2005

Rule-based Policies across Multiple E-Services Tasks, using Courteous Logic Programs in RuleML, SWSL, and SweetRules

by Benjamin Grosof (1), Chitravanu Neogy (1), and Shashidhara Ganjugunte (2).


(1) Massachusetts Institute of Technology, Sloan School of Management, Cambridge, MA, USA.
       {bgrosof,chitro}@mit.edu ; http://ebusiness.mit.edu/bgrosof; http://www.chitro.com
(2) Duke University, Durham, NC, USA. Work done while at: University of Maryland Baltimore County, Baltimore, MD, USA. shashi1@cs.umbc.edu

Abstract

We give an application-focused overview of our rule-based semantic web approach to representing a variety of policy application scenarios, including for knowledge-based web e-commerce and services, using the Courteous Logic Programs (CLP) knowledge representation (KR) encoded in RuleML / SWSL-Rules. The rules can also be combined with ontologies, e.g., in the Description Logic Programs subset of OWL which is also an expressive subset of CLP. CLP is an extension of normal/ordinary declarative logic programs that includes prioritized conflict handling and has attractive expressive power, modularity, robustness, and tractability. It is well suited to represent available knowledge and desired patterns of reasoning for several categories of semantic web services tasks, including: authorization/trust policies; contracts; monitoring; advertising/discovery; semantic/contextual mediation; and object-oriented ontologies. We have implemented the approach using the SweetRules V2.1 open source toolkit which supports powerful interoperable inferencing, merging, and translation of CLP rules in RuleML (in combination with ontologies including in OWL). We describe one such implemented application scenario about policies for refunds in an e-tailer. Beyond that, we briefly discuss a number of our other implemented application scenarios, which include: price discounting; supply chain ordering lead time; creditworthiness; credit card transaction authorization; and e-contracting with exception handling / monitoring.

1 Overview of Approach and Position

Semantic, knowledge-based descriptions of services on the web are useful for many tasks. One cluster of such Semantic Web Services (SWS) -- or knowledge-based electronic services -- tasks revolves around what can be viewed as policies as a kind of knowledge. Rules are a good knowledge representation (KR) for such policies, in combination with ontologies that define the predicates appearing in the rules. (In this position paper, we focus primarily on the rules rather than the ontologies.) More specifically, Courteous Logic Programs (CLP) [Grosof2004a] is a good KR for such policies, because of its attractive expressive power, modularity, robustness, and tractability properties. CLP is an extension of normal/ordinary declarative logic programs that includes prioritized conflict handling.

In more detail, the Courteous extension of LP expressively adds rule labels, a syntactically reserved prioritization predicate ("overrides"), limited classical negation (in addition to negation-as-failure), and mutual-exclusion integrity constraints ("mutex's"). The prioritization predicate specifies the partial order of prioritization between rules. Rules (with "overrides" in their head) can be used to infer this prioritization ordering. Mutex's specify what constitutes the scope of possible conflict, e.g., specify that a predicate (such as "price") is partial-functionality or that two predicates (such as "truck" and "airplane") are disjoint.

The set of conclusions in CLP is consistent -- an important kind of robustness when merging. Such robustness is especially important when doing large-scale knowledge sharing of rules that originate from multiple authors/organizations and are used in multiple contexts. Conflicts between rules may be resolved on the basis of priorities. Conflicts unresolved by priority simply result in no conclusion being drawn one way or the other about the subject of the conflict. By contrast, classical logic -- e.g., First Order Logic (FOL), including its fragments Description Logic (DL) and Horn FOL -- is extremely brittle in the face of conflict; the smallest conflict produces in effect a semantic meltdown. Consider a set of a thousand or a million or billion premises forming a large knowledge base (KB) on the web, say formed from merging together multiply-authored rulebases/KB's. If just two of these are in conflict -- say one says Betsy is a sheep and the other says Betsy is a goat, while a background axiom says that sheep and goats are disjoint categories -- then every sentence in the language is sanctioned as a conclusion.

CLP facilitates modularity in rulebases, since one ruleset can easily be specified as overriding (higher priority than) another rulebase when merging the two rulebases together -- e.g., when the first ruleset is more recent (e.g., updated) more specific/exception-case, more authoritative, or more reliable. CLP has similar qualitative computational complexity to relational databases and pure Prolog. CLP thus meets several important requirements of web-scaleability in terms of its expressiveness, behavior, and computational complexity (see more about computational performance below in the description of SweetRules). In particular, CLP inferencing is computationally tractable (polynomial-time) under the "Datalog VB" expressive restriction. "Datalog" means no logical functions. "VB" means that there is a constant bound on the number of distinct logical variables per rule. The Datalog restriction is commonly imposed/obeyed in forward-inferencing rule systems, e.g., production rules, as well as in relational database systems, e.g., SQL. The VB restriction is typically met in practice, with the constant bound being say 10 or less.

CLP is supported both in RuleML, and in SWSL-Rules. SWSL-Rules is the rule language part of the Semantic Web Services Framework (SWSF), developed by the Semantic Web Services Initiative (SWSI). (SWSF Version 1.0 is due to be released in early May 2005.) SWSL-Rules is closely related to RuleML. SWSL-Rules employs RuleML's XML syntax as its markup syntax, and RuleML employs SWSL-Rules' presentation syntax as its presentation syntax. SWSL-Rules has been developed in close collaboration with RuleML, including to extend RuleML recently with additional expressive features such as Hilog and Frame syntax. The Hilog and Frame syntax features are drawn from F-Logic Programs [Kifer95], which are implemented in Flora. Recently, WSMO (Web Services Mediation Ontology project and its Language effort WSML) have begun to collaborate with RuleML (and SWSL) as well.

A variety of powerful inferencing and translation tools and capabilities supporting CLP are provided in the SweetRules [Grosof2004b] open source platform for semantic web rules and ontologies, including forward inferencing in CLP via Jess and IBM CommonRules, and backward inferencing in CLP via XSB. Jess and XSB are commercial-grade implementations of rule-based inferencing that are fast while handling large rulebases. SweetRules overall revolves around RuleML. SweetRules supports not only the RuleML/SWSL XML markup syntax but also the recently-developed RuleML/SWSL presentation syntax, including for CLP. (Later in this paper, we will give more details about, and examples of, the presentation syntax.) SweetRules V2.1 is the first implementation of that presentation syntax (initially, only a generator).

Ontologies of two kinds can easily be combined with CLP rules:

  1. ontologies that are in the Description Logic Programs KR [Grosof2003a]. expressive subset of Description Logic, e.g., in the DLP subset of OWL-DL; and
  2. object-oriented / frame style ontologies that employ default inheritance, expressed in CLP (or in ordinary/normal LP), e.g., cf. [Bernstein2003] [Yang02].
SweetRules directly supports easy merging-in of KB's that are in the DLP subset of OWL-DL.

Overall, the CLP KR is especially well suited to represent available knowledge and desired patterns of reasoning for several categories of the SWS tasks, including:

In particular, the capabilities of the Rules KR for logical nonmonotonicity (Courteous prioritized conflict handling, which relies on the underlying expressive feature of negation-as-failure) is used heavily in many use case scenarios for each of the above tasks and its associated kinds of knowledge.

CLP can be extended further straightforwardly to include procedural attachments for informational tests/queries/"sensing" and side-effectful actions/"effecting", via the Situated extension of LP, i.e., to become the Situated Courteous LP KR (SCLP) [Grosof2004a]. SCLP is supported in SweetRules, as well as IBM CommonRules. SCLP is useful to represent many kinds of rule-based workflows and other rule-based business processes.

Another interesting use case for CLP in SWS is to represent somewhat-weakened versions of expressively rich FOL ontologies. The expressiveness of such FOL ontologies can go well beyond the Description Logic Programs KR that directly subsets CLP, indeed well beyond Description Logic and OWL-DL. For example, the SWSO effort (i.e., SWSF's Ontology part) has created both a FOL and a Rules (LP) version of an overall core service ontology for SWS. This ontology includes, as a large part, PSL (NIST Process Specification Language -- specifically, PSL Core and Outer Core), which is in expressively rich FOL. The Rules version of this PSL ontology is a CLP in SWSL-Rules/RuleML that was created using an experimental method based on preliminary results about a new theoretical approach called "hypermonotonic" reasoning [Grosof2004c].

2 Specific Examples / Use Cases

The overall RuleML/SWSL-Rules rules language, and CLP in particular, support many kinds of application scenarios.

Several detailed (fictional) examples of policies for services tasks, represented in the CLP KR, encoded in the RuleML/SWSL presentation syntax, are given in the "Policy Rules for E-Commerce" section of the SWSF Applications Scenarios document. These have each been implemented in SweetRules V2.1. They include:

Taken together these examples include both B2C/retailing and B2B/supply-chain aspects, in several industry domains (books, appliances, and computer equipment manufacturing). Each of these policies is useful for not just one but several different kinds of tasks within an application realm. For example, price discounting rules are useful in advertising and in contract negotiation/formation. All of these detailed examples are rather brief, for the sake of expository simplicity -- except the one about credit card transaction authorization, which is significantly longer and more realistic.

In addition, more and longer examples of policy rules are available that use the same CLP fundamental knowledge representation, encoded in RuleML. [Grosof2004e] gives a long example of e-contracting policy rules that combines rules with ontologies and deals with exception handling / monitoring. The [Grosof2004f] tutorial surveys/gives a collection of use cases and examples, including for semantic mediation. The SweetRules downloadable includes a collection of examples. [Grosof99b] [Grosof99c] [Grosof2004a] also give/discuss additional examples that in part include longer versions of the discount, refund, and ordering lead time examples listed above.

2.1 Primer on RuleML/SWSL presentation syntax for CLP

Next, we give a quick primer on RuleML presentation syntax, to aid the beginner to read examples of policies, in particular to read those in the next section and in the Policy Rules for E-Commerce section of the SWSF Application Scenarios (mentioned above). Full details of this presentation syntax are given in the SWSL (i.e., SWSF Language) document. But that's rather long and technical, so it's useful to have this primer. Note this primer only covers/treats part of the overall presentation syntax.

Next we describe some key syntactic constructs:

2.2 Detailed Example: Refunds in an E-Retailer

So as to make this paper more self-contained, we include here a detailed, albeit brief, example -- the one about refunds mentioned above (from the SWSL design report Application Scenarios section) -- using the RuleML/SWSL presentation syntax.

Next, we give a typical example of a seller's refund policy, as a set of policy rules that specify refunds in an e-retailer (here, of small consumer appliances) These rules are useful in advertising, and as part of a contract (proposed or final), and as part of contract monitoring / exception handling (which is in turn part of contract execution). The policy rules knowledge thus can be reused across multiple SWS tasks. This example is a reformatted variant of example 1 of [Grosof99b].

The unconditional guarantee rule says that if the buyer returns the purchased good for any reason, within 30 days, then the purchase amount, minus a 10 percent restocking fee, will be refunded. The defective guarantee rule says that if the buyer returns the purchased good because it is defective, within 1 year, then the full purchase amount will be refunded. A priority rule says that if both of the previous two rules apply, then the defective guarantee rule "wins", i.e., has higher priority. A mutex says that the refund percentage is unique per customer return.

/* refund policy rules */

{unconditionalGuarantee}
   refund(?Return, percent90)
      :- return(?Return) and delay(?Return, ?D) and lessThanOrEqual(?D, days30).

{defectiveGuarantee}
   refund(?Return, percent100)
      :- return(?Return) and reason(?Return, defective) and
            delay(?Return, ?D) and lessThanOrEqual(?D, years1).

overrides(defectiveGuarantee, unconditionalGuarantee).

!- refund(?Refund, percent90) and refund(?Refund, percent100).


/* some background facts (typically provided by lessThanOrEqual
being a built-in predicate */

lessThanOrEqual(days12, days30).
lessThanOrEqual(days44, years1).
lessThanOrEqual(days22, years1).
lessThanOrEqual(days22, days30).

/* some "case" facts about particular customer returns of items */

return(toaster02).
delay(toaster02, days12).

return(blender08).
delay(blender08, days44).
reason(blender08, defective).

return(radio04).
delay(radio04, days22).
reason(radio04, defective).

The above premises (policy rules, background facts, and case facts) together entail the following conclusions about the discount refund percentages for the particular customer returns of the toaster, blender, and radio.

/* the entailed refund percentages for the particular customer returns */

refund(toaster02, percent90).

refund(blender08, percent100).

refund(radio04, percent100).