Beyond Monotonic Inheritance: Towards Non-Monotonic Semantic Web Process Ontologies

Authors:: Abraham Bernstein (University of Zurich)
Benjamin Grosof (Massachusetts Institute of Technology)
Michael Kifer (State University of New York at Stony Brook)

Introduction

In the SWS vision (see http://www.swsi.org), semantic service descriptions, i.e., process knowledge represented using Semantic Web (SW) KR, will enable various kinds of reasoning in support of several key tasks including advertising/discovery, matchmaking, negotiation/contracting, composition, execution monitoring, etc., of Web Services. Some early, relatively simple SWS prototypes have already been developed. To realize the whole vision, however, SWS developers will need large amounts of process knowledge that is represented declaratively, i.e., in semantically clean fashion cf. SW KR. A key part of process knowledge is ontological: definitional knowledge in the form of class hierarchies (where some (sub)classes are specializations of superclasses) and property information associated with those classes. A central kind of reasoning in ontologies is inheritance, in which each subclass (specialization) inherits the values of the properties associated with its superclasses (generalizations). In monotonic inheritance, a subclass can add new properties and/or property values. Inheritance is useful since it enables reuse: to specify a new subclass’s set of associated property info – one can just specify the differences from its superclass(es)’s property info.
Experience in the Process Handbook (PH) project, which has been under development at the MIT Center for Coordination Science (CCS) for over ten years, including the contributions of a diverse and highly distributed group of over 40 scientists, students and industrial sponsors [Process Handbook] [Malone99] has shown that in practice users of inheritance often – perhaps, usually – desire non-monotonic inheritance, which is more general. In non-monotonic inheritance, unlike monotonic inheritance, one can change what’s inherited: either to replace/override (i.e., modify) or to cancel (i.e., delete) an inherited property value. Non-monotonic inheritance is a.k.a. default inheritance or inheritance with exceptions. Permitting inheritance to be non-monotonic enables more reuse/modularity. When inheritance is restricted to be monotonic, if one needs to change (both override or cancel) some inherited property info, then one has to manually/explicitly repeat the specification of much or all of the property info that one wants to reuse from previously-defined classes, without benefit of inheritance. Non-monotonic inheritance thus enables easier specification: not only initially but also especially during updating and merging (e.g., in maintenance). Non-monotonic inheritance is found ubiquitously in object-oriented programming languages and design tools, including Java, C++, and the PH.
Consequently, the experience within the PH project has reconfirmed findings [MacLean90] that allowing cancellation aids ease of understanding/specification.
OWL [VanHarmelen03] can represent expressively complex kinds of monotonic inheritance but is fundamentally incapable of representing any kind of non-monotonic reasoning, including non-monotonic inheritance. The same is true for most classical first-order reasoning mechanisms in use within all the semantic web services initiatives we are aware of.
Our position, which is supported by the findings of the Process Handbook project as well as two decades of experience with object-oriented programming, is therefore, that it is imperative that semantic web services description languages have to support non-monotonic inheritance to preserve the ease of use while maintaining an bounded acceptable reasoning complexity. As such we point out the drawbacks of current semantic web-service description languages, which are based on OWL, while proposing a remedy, which we implemented in SWSL-Rules [ Grosof2005, http://www.daml.org/services/swsl/report/].
To further support our position the remainder of this paper provides an example of a simple use of non-monotonic inheritance in an application scenario, which can be used for service discovery, service execution, service composition, contract formation and negotiation, as well as contract or process monitoring and exception handling.

Using Defaults in Domain-Specific Service Ontologies

The SWSL Ontology is a core service ontology. However, it is also often useful to represent other, e.g., domain-specific, ontologies as well. Such ontologies might be represented in SWSL-Rules or in SWSL-FOL. An important and frequently-found flavor of domain-specific service ontologies is object-oriented framework knowledge of the kind found in software class hierarchies specified in object-oriented programming languages or in AI frame-based systems. In such object-oriented framework knowledge the values of a property P of a (super)class (say, C1) are inherited by each of its subclasses (say, C2). These subclasses are known as the specializations of the parent (super)class. For example, the property P might be a data attribute or a method definition. This inheritance is default in nature/flavor: explicitly specified information about the property for the subclass may override -- or cancel -- the inheritance. Such default inheritance, and thus such an ontology, is logically non-monotonic. They thus cannot be represented in SWSL-FOL. However, they can be represented in SWSL-Rules, e.g., using the Courteous Inheritance approach of [Bernstein2003] [Grosof2004d] (see also [Yang02] for an analogous approach). In that approach, such ontology is represented using the Courteous Logic Programs knowledge representation, i.e., the Courteous feature of SWSL-Rules, along with a set of approximately 20 generic background rules (in that KR) that axiomatize the generic behavior of default inheritance.
In this section, we next give an example, called the Sell Product example, of such a domain-specific service ontology, using that Courteous Inheritance approach. The ontology is about the Sell Product business process and a few of its specializations. The form and domain of this ontology are similar to those in the Process Handbook [Process Handbook] [Malone99]. This kind of ontology is useful for business process modeling and design, and thus is useful -- along with other rules knowledge -- for a number of SWS tasks, including:

service discovery [Bernstein2002];
service execution [Bernstein2000];
service composition;
contract formation and negotiation [Grosof2004e]; and
contract or process monitoring and exception handling [Grosof2004e].

The example is a reformatted variant of the example in [Bernstein2003], where we give an approach to representing default inheritance about process ontologies in terms of Courteous Logic Programs. Another approach to representing default inheritance in a similar spirit is shown in [Yang02] who use Logic Programs with NAF(negation as failure) but without Courteous, instead defining special constructs that extend the LP KR (logic programs knowledge representation).
Below, we give an approach similar in spirit to both of the above, that is relatively simple -- simple enough for a self contained brief presentation here -- although lacking some of the advantages and subtleties of the above two approaches.

Modeling the parent service "Sell Product"

Suppose we need to design a sales process that is used in an organization in two ways. One version is used in a mail-order business and the other in a retail store. First, we need to model a generic sales process for which one can find a template in a process repository (e.g., the Process Handbook). The "Sell product" service consists of five subtasks: "Identify potential customers," "Inform potential customers," "Obtain Order," "Deliver product ," and "Receive payment." In this example, we do not model any sequencing dependencies between the subtasks.

One way to represent this situation is to treat the main service as a class and its subtasks as attributes (note that the semantics of the notation used here is defined via a transformation to non-monotonic logic programs [Bernstein2003, Yang02]):

 SellProduct[
 identifyCustomers *-> genericFindCust,
 informCustomers *-> genericInformCust,
 obtainOrder *-> genericGetOrder,
 deliverProduct *-> genericDeliver,
 receivePay *-> genericGetPay
 ].

Here the attribute names represent the names of the subtasks and the values of these attributes are the names of the actual procedures to be used to perform these tasks. These procedures can be written in a procedural programming language, such as Java, or even in SWSL-Rules [Grosof2005]. For instance,

 ?Product[genericInformCust] :-
 ?Product[genericFindCust -> ?Cust] and
 generateFlyer(?Cust) and
 informMailRoom.

Some of the formulas in the body of the above rule could be purely declarative and be defined by other rules in the knowledge base (e.g., genericFindCust) while others could have side effects in the physical world (such as generateFlyer and informMailRoom). Such side-effectful statements are not currently part of SWSL-Rules, but they are planned for future extensions.

Note that the method genericFindCust returns a set of customers (based on some marketing criteria), and the method genericFindCust is executed for each such customer.

Overriding and Canceling Inherited Features

Continuing the example, we specify the "Sell by mail order" and "Sell in retail store" services as subclasses of the "Sell Product" process, as shown in Figure 1.

Non-mon Example Diagram

Figure 1: The "Sell Product" service with two subclasses. The grayed out subtasks are overwritten with more specific alternatives; the subtask with the red cross is deleted ("canceled").

This subclassing approach has several advantages. First, it provides a simple way of reusing the elements already defined in an object-oriented manner. Second, taxonomic organization of processes has been found useful for human browsing [Malone99].

For "Sell by mail order," inheritance of three of the subtasks of the parent service "Sell product" is overwritten by other subtasks, and two subtasks are inherited. For "Sell in retail store", one subtask is inherited, inheritance of three others is overwritten, and one subtask is "canceled" (i.e., is no longer defined for the subsprocess).

Since nonmonotonic inheritance is one of the basic concepts of SWSL-Rules, modeling of the service "Sell by mail order" is straightforward. First, we need to specify it as a subclass of SellProduct. Then we need to explicitly define the three overwritten subtasks and provide new values (new procedures) for them. We do not need to mention the two tasks that are inherited:

 SellByMailOrder::SellProduct[
 identifyCustomers *-> obtainMailLists,
 informCustomers *-> junkmailAds,
 obtainOrder *-> getOrderByMail
 ].

Because of the overriding in the SellByMailOrder subclass, the subtask informCustomers is no longer performed using the previously defined method genericInformCust. Instead, the method junkmailAds is used; it could be defined in SWSL-Rules as follows:

 ?Product[junkmailAds] :-
 ?Product[obtainMailLists -> ?List] and
 ?List[address -> ?Addr] and
 affixLabelToAd(?Addr) and
 informMailRoom.

To model the "Sell in retain store" we first specify a new subclass of the "Sell Product" service. According to the figure, this subclass inherits the deliverProduct attribute, while three other attributes, identifyCustomers, obtainOrder, and receivePay, are overwritten. This is modeled similarly to the SellByMailOrder subclass:

 SellInRetail::SellProduct[
 identifyCustomers *-> attractToBrickAndMortar,
 obtainOrder *-> getOrderAtRegister,
 receivePay *-> getPayAtRegister
 ].

The more interesting case is the cancellation of the informCustomers attribute. One way to achieve this is to introduce a special null subtask and use it to override inheritance of the genericInformCust procedure. A more interesting way it to take advantage of the semantics of multiple inheritance in SWSL-Rules according to which conflicting multiple inheritance for the same attribute makes the value undefined. To achieve this, we can introduce a family of classes parameterized by the features that need to be canceled:

 FeatureTerminator(?Feature)[?Feature *-> null].

For each concrete attribute, the above statement says that the value of that attribute in the corresponding class is null. As a special case (when ?Feature = informCustomers), the value of the attribute informCustomers in class FeatureTerminator(informCustomers) is null. To cancel the inheritance of informCustomers we now need to add the following fact:

 SellInRetail::FeatureTerminator(informCustomers).

With this statement, SellInRetail becomes a subclass of two classes, SellProduct and FeatureTerminator(informCustomers). Each of these classes has an explicit definition of the attribute informCustomers, but those definitions are in conflict. According to the semantics of inheritance in SWSL-Rules, this makes the value of informCustomers in class SellInRetail undefined and thus the inheritance of that attribute is "canceled."

Summary

As the example shows the use of non-monotonic and canceling inheritance provides the means to elegantly model the "Sell product" example. Modeling the example in a monotonic setting would have required either required a refactoring of the ontology resulting in the removal of information (i.e., assertions) from the ontology, which would result in a poorer basis for reasoning about the problem domain, or the use of other modeling approaches, which would reduce the understandability of the ontology to users.
Consequently, it is imperative that semantic web services description languages have to support non-monotonic inheritance to preserve the ease of use while maintaining tractability (the latter is shown in [Grosof2004a]). We believe that to attain the expressability desired one needs to use non-monotonic LP (logic programs) to that end, as we did in the SWSL-Rules language.

Acknowledgments

We are grateful for the support and input by the SWSL committee.

References

[Bernstein2000]: How can cooperative work tools support dynamic group processes? Bridging the specificity frontier. A. Bernstein. In Proc. Computer Supported Cooperative Work (CSCW'2000), 2000.

[Bernstein2002]: Towards High-Precision Service Retrieval. A. Bernstein, and M. Klein. In Proc. of the first International Semantic Web Conference (ISWC'2002), 2002.

[Bernstein2003]: Beyond Monotonic Inheritance: Towards Semantic Web Process Ontologies. A. Bernstein and B.N. Grosof (NB: authorship sequence is alphabetic). Working Paper, Aug. 2003. Available at: http://ebusiness.mit.edu/bgrosof/#beyond-mon-inh-basic.

[Grosof99a]: A Courteous Compiler From Generalized Courteous Logic Programs To Ordinary Logic Programs. B.N. Grosof. IBM Report included as part of documentation in the IBM CommonRules 1.0 software toolkit and documentation, released on http://alphaworks.ibm.com. July 1999. Also available at: http://ebusiness.mit.edu/bgrosof/#gclp-rr-99k.

[Grosof99b]: A Declarative Approach to Business Rules in Contracts. B.N. Grosof, J.K. Labrou, and H.Y. Chan. Proceedings of the 1st ACM Conference on Electronic Commerce (EC-99). Also available at: http://ebusiness.mit.edu/bgrosof/#econtracts+rules-ec99.

[Grosof99c]: DIPLOMAT: Compiling Prioritized Default Rules Into Ordinary Logic Programs (Extended Abstract of Intelligent Systems Demonstration). B.N. Grosof. IBM Research Report RC 21473, May 1999. Extended version of 2-page refereed conference paper appearing in Proceedings of the National Conference on Artificial Intelligence (AAAI-99), 1999. Also available at: http://ebusiness.mit.edu/bgrosof/#cr-ec-demo-rr-99b.

[Grosof2003a]: Description Logic Programs: Combining Logic Programs with Description Logic. B.N. Grosof, I. Horrocks, R. Volz, and S. Decker. Proceedings of the 12th International Conference on the World Wide Web (WWW-2003). Also available at: http://ebusiness.mit.edu/bgrosof/#dlp-www2003.

[Grosof2004a]: Representing E-Commerce Rules Via Situated Courteous Logic Programs in RuleML. B.N. Grosof. Electronic Commerce Research and Applications, 3:1, 2004, 2-20. Preprint version is also available at: http://ebusiness.mit.edu/bgrosof/#.

[Grosof2004b]: SweetRules: Tools for Semantic Web Rules and Ontologies, including Translation, Inferencing, Analysis, and Authoring. B.N. Grosof, M. Dean, S. Ganjugunte, S. Tabet, C. Neogy, and D. Kolas. http://sweetrules.projects.semwebcentral.org. Software toolkit and documentation. Version 2.0, Dec. 2004.

[Grosof2004c]: Hypermonotonic Reasoning: Unifying Nonmonotonic Logic Programs with First Order Logic. B.N. Grosof. http://ebusiness.mit.edu/bgrosof/#HypermonFromPPSWR04InvitedTalk. Slides from Invited Talk at Workshop on Principles and Practice of Semantic Web Reasoning (PPWSR04), Sep. 2004; revised Oct. 2004. Paper in preparation.

[Grosof2004d]: SweetPH: Using the Process Handbook for Semantic Web Services. B.N. Grosof and A. Bernstein. http://ebusiness.mit.edu/bgrosof/#SweetPHSWSLF2F1204Talk. Slides from Presentation at SWSL Meeting, Dec. 9-10, 2004. Note: Updates the design in the 2003 Working Paper "Beyond Monotonic Inheritance: Towards Semantic Web Process Ontologies" and describes implementation.

[Grosof2004e]: SweetDeal: Representing Agent Contracts with Exceptions using Semantic Web Rules, Ontologies, and Process Descriptions. B.N. Grosof and T.C. Poon. International Journal of Electronic Commerce (IJEC), 8(4):61-98, Summer 2004 Also available at: http://ebusiness.mit.edu/bgrosof/#sweetdeal-exceptions-ijec.

[Grosof2004f]: Semantic Web Rules with Ontologies, and their E-Business Applications. B.N. Grosof and M. Dean. Slides of Conference Tutorial (3.5-hour) at the 3rd International Semantic Web Conference (ISWC-2004). Available at: http://ebusiness.mit.edu/bgrosof/#ISWC2004RulesTutorial.

[Grosof2005]: Rules in the Semantic Web Services Language (SWSL): An Overview for Standardization Directions. B.N. Grosof, M. Kifer, and D. L. Martin. Position Paper for W3C Workshop on Rule Languages for Interoperability. Available at: http://www.w3.org/2004/12/rules-ws/paper/124/.

[MacLean90]: User-tailorable Systems: Pressing the Issues with Buttons. A. MacLean, K. Carter, L. Lövstrand, T. Moran. SIGCHI Conference, 1990 Seattle, Washington, ACM-SIGCHI.

[Malone99]: Tools for inventing organizations: Toward a handbook of organizational processes. T. W. Malone, K. Crowston, J. Lee, B. Pentland, C. Dellarocas, G. Wyner, J. Quimby, C. Osborne, A. Bernstein, G. Herman, M. Klein, E. O'Donnell. Management Science, 45(3), pages 425--443, 1999.

[OWL Reference]: OWL Web Ontology Language 1.0 Reference. Mike Dean, Dan Connolly, Frank van Harmelen, James Hendler, Ian Horrocks, Deborah L. McGuinness, Peter F. Patel-Schneider, and Lynn Andrea Stein. W3C Working Draft 12 November 2002. Latest version is available at http://www.w3.org/TR/owl-ref/.

[OWL-S 1.1]: David Martin, editor, OWL-S: Semantic Markup for Web Services, Technical Overview (associated with OWL-S Release 1.1).

[VanHarmelen03]: OWL Web Ontology Language Reference. F. Van Harmelen, J. Hendler, I. Horrocks, D. McGuinness, P. Patel-Schneider, L.-A. Stein. w3c Proposal, 2003.

[Yang02]: Well-Founded Optimism: Inheritance in Frame-Based Knowledge Bases. G. Yang, M. Kifer. Intl. Conference on Ontologies, DataBases, and Applications of Semantics for Large Scale Information Systems (ODBASE), October 2002.