Table of contents

1 Introduction
2 The Language
  2.1 Overview of SWSL-Rules and SWSL-FOL
  2.2 Basic Definitions
  2.3 Horn Rules
  2.4 The Monotonic Lloyd-Topor Layer
  2.5 The NAF Layer
  2.6 The Nonmonotonic Lloyd-Topor Layer
  2.7 The Courteous Rules Layer
  2.8 The HiLog Layer
  2.9 The Equality Layer
  2.10 The Frames Layer
  2.11 Reification
  2.12 Skolemization in SWSL-Rules
  2.13 SWSL-Rules and XML Schema Data Types
  2.14 Overview of the Semantics of SWSL-Rules
  2.15 Future Extensions
3 Serialization of SWSL-Rules in RuleML
   3.1 Serialization of the HiLog Layer
   3.2 Serialization of Explicit Equality
   3.3 Serialization of the Frames Layer
   3.4 Serialization of Reification
4 Application Scenarios
   4.1 Service Discovery with SWSL-Rules
   4.2 Policy Rules for E-Commerce
   4.3 Using Defaults in Domain-Specific Service Ontologies
5 Glossary
6 References

1 Introduction

SWSL-Rules is a rule-based language, which can be used both as a specification and an implementation language for the Semantic Web. The semantics of SWSL-Rules has non-monotonic flavor, which makes it well-suited for tasks that naturally rely on default information and inheritance. These tasks include ontology specification, service discovery, contracting, policy specification, and others. In addition, rule-based languages are quite common both in the industry and research, and many people are more comfortable using them even for tasks that may not require defaults, such as service profile specification. Some applications of SWSL-Rules are discussed in Section 4.

SWSL-Rules includes a novel combination of features that hitherto have not been present in a single system. However, almost all of the features of SWSL-Rules have been implemented in either FLORA-2 [Yang04], SweetRules [Grosof2004b], or the commercial Ontobroker [Ontobroker] system. Extensive feedback collected from the users of these systems has been incorporated in the design of the corresponding features in SWSL-Rules.

The layered structure of SWSL-Rules. SWSL-Rules is presented as a layered language. Unlike OWL, the layers are not organized based on the expressive power and computational complexity. Instead, each layer includes a number of new concepts that enhance the modeling power of the language. This is done in order to make it easier to learn the language and to help understand the relationship between the different features. Furthermore, most layers that extend the core of the language are independent from each other -- they can be implemented all at once or in any partial combination. This can provide certain guidance to vendors who might be interested only in a particular subset of the features.

Complexity. The layers of SWSL-Rules are not organized around the complexity. In fact, except for the equality layer, which boosts the complexity, all layers have the same complexity and decidability properties. For SWSL-Rules, the most important reasoning task is query answering. The general problem of query answering is known to be only semi-decidable. However, there are large classes of problems that are decidable in polynomial time. The best-known, and perhaps the most useful, subclass consists of rules that do not use function symbols. However, several decidable classes of rules with function symbols are also known [Lindenstrauss97].

Related languages. SWSL-Rules is closely related to the recently proposed language WSML-Rule [Bruijn05b] and its subset, WRL. Technically, SWSL-Rules is a more featurefull language than WSML-Rule. However, WSML-Rule has a different layering structure, which facilitates interoperability with OWL [OWL Reference], and it pays particular attention to the end-user issues. SWRL [SWRL] is another related rule language. SWRL extends OWL with Datalog-style rules, but instead of predicates rule body and head can contain class OWL descriptions. The main difference is that SWSL-Rules is a language with non-monotonic semantic in the tradition of logic programming and deductive databases. The syntax and the knowledge representation paradigm of SWSL-Rules are also derived from that tradition. In contrast, the semantics of SWRL is strictly first-order and it imposes the syntactic restrictions that stem from the Description Logic heritage of OWL. While there is rich experience both with implementation and use of the languages such as SWSL-Rules, it is unclear whether scalable implementation exist for SWRL, and there is little experience with the use of such a rules language. SPARQL [SPARQL] is yet another related, recently proposed language, which is expected to become popular in querying RDF. From the technical standpoint, SPARQL is a basic language, which is akin to the SQL language in relationship to relational data. In contrast, all the other languages surveyed above are much more expressive and are designed to support more advanced needs in knowledge representation on the Web.

2 The Language

2.1 Overview of SWSL-Rules

The SWSL-Rules language is designed to provide support for a variety of tasks on the Semantic Web. These tasks range from ontology specification to semantic descriptions of Web services, to policy specification, to representation of the knowledge of intelligent agents. The language is layered to make it easier to learn and to simplify the use of its various parts for specialized tasks that do not require the full expressive power of SWSL-Rules. The layers of SWSL-Rules are shown in Figure 2.1.

Figure 2.1: The Layered Structure of SWSL-Rules

The core of the language consists of the pure Horn subset of SWSL-Rules. The monotonic Lloyd-Topor (Mon LT) extension [Lloyd87] of the core permits disjunctions in the rule body and conjunction and implication in the rule head. NAF is an extension that allows negation in the rule body, which is interpreted as negation-as-failure. More specifically, negation is interpreted using the so called well-founded semantics [VanGelder91]. The nonmonotonic Lloyd-Topor extension (Nonmon LT) further permits quantifiers and implication in the rule body. The Courteous rules [Grosof99a] extension introduces two new features: restricted classical negation and prioritized rules. HiLog and Frames extend the language with a different kind of ideas. HiLog [Chen93] enables high degree of meta-programming by allowing variables to range over predicate symbols, function symbols, and even formulas. Despite these second-order features, the semantics of HiLog remains first-order and tractable. It has been argued [Chen93] that this semantics is more appropriate for many common tasks in knowledge representation than the classical second-order semantics. The Frames layer of SWSL-Rules introduces the most common object-oriented features, such as the frame syntax, types, and inheritance. The syntax and semantics of this extension is inspired by F-logic [Kifer95] and the followup works [Frohn94, Yang02, Yang03]. Finally, the Reification layer provides a mechanism for making objects out of a large class of SWSL-Rules formulas, which puts such formulas into the domain of discourse and allows reasoning about them.

All of the above layers have been implemented in one system or another and have been found highly valuable in knowledge representation. For instance, FLORA-2 [Yang04] includes all layers except Courteous rules and Nonmonotonic Lloyd-Topor. SweetRules [Grosof2004b] supports Courteous extensions, and Ontobroker [Ontobroker] supports Nonmonotonic Lloyd-Topor and frames.

Four points should be noted about the layering structure of SWSL-Rules.

1. The lines in Figure 2.1 represent inclusion dependencies among layers. For instance, Nonmonotonic LT layer includes both NAF and Monotonic LT. Reification includes HiLog and Frames, Courteous includes NAF, etc.
2. The different branches of Figure 2.1 are orthogonal and they all can be combined. For instance, the Frames and HiLog layers can be combined with the Courteous and Nonmon LT layers. Likewise, the equality layer can be combined with any other layer. Thus, SWSL-Rules is a unified language that combines all the layers into a coherent and powerful knowledge representation language. Its semantics will be described in a separate document. The semantics of the individual layers has been described in other publications and an overview of the overall semantics is provided in Section 2.14.
3. The Lloyd-Topor extensions and the Courteous rules extensions endow SWSL-Rules with all the normal first-order connectives. Therefore, syntactically SWSL-Rules contains all the connectives of the full first-order logic. However, semantically SWSL-Rules is not first-order. Its semantics agrees with first-order logic only over a relatively small, but important Horn Layer, which is described in Section 2.3.
4. Because of its non-monotonic flavor, SWSL-Rules distinguishes between connectives with the classical first-order semantics and connectives that have nonmonotonic semantics. For instance, it uses two different forms of negation—naf, for negation-as-failure, and neg, for classical negation. Likewise, it distinguishes between the classical implication, <== and ==>, and the if-then connective :- used for rules.

2.2 Basic Definitions

In this section we define the basic syntactic components that are common to all layers of SWSL-Rules. Additional syntax will be added as more layers are introduced.

A constant is either a numeric value, a symbol, a string, or a URI.

• A numeric value is either an integer, a decimal, or a floating point number. For instance, 123, 34.9, 45e-11. See the section on SWSL-Rules data types for more details on the relationship between the SWSL-Rules data types and the primitive data types in XML Schema.
• A symbol is a string of characters enclosed between a pair of single quotes. For instance, 'abc#$%'. Single quotes that are part of a symbol are escaped with the backslash. For instance, the symbol a'bc''d is represented as 'a\'bc\'\'d'. The backslash is escaped with another backslash. Symbols that consist exclusively of alphanumeric characters and the underscore (_) and begin with a letter or an underscore do not need to be quoted.
• Strings are sequences of characters that are enclosed between a pair of double quote symbols, e.g., "ab'%#cd". A double quote symbol that occurs in a string must be escaped with the backslash. For instance, the string ab"cd"""gf is represented as "ab\"cd\"\"\"gf".
• A SWSL-URI can come either in the form of a full URI or in the abbreviated form of an sQName.

  A full URI is a sequence of characters that has the form of a URI, as specified by IETF, and is enclosed between _" and ". For instance, _"http://w3.org/".

  An sQName has the form prefix#local-name. Here prefix is an alphanumeric symbol that is defined to be a shortcut for a URI as specified below; local-name is a string that must be acceptable as a path component in a URI. If local-name contains non-alphanumeric symbols, it must be enclosed in double quotes: e.g., "ab%20". An sQName is treated as a macro that expands into a full URI by concatenating the expansion of prefix (the URI represented by the prefix) with local-name. For the rationale behind the use of sQName see the entry for sQName in the Glossary.

A prefix declaration is a statement of the form

The prefix can then be used instead of the URI in sQNames. For instance, if we define

then the SWSL-URI _"http://www.w3.org/TR/xquery/" is considered to be the same as w3#"TR/xquery/". Prefix declarations are treated as nothing more than macros and macro-expansion is expected to be done prior to any syntactic or semantic considerations (such as considering whether two SWSL-Rules expressions are identical).

A variable is an alphanumeric symbol (plus the underscore), which is prefixed with the ?-sign. Examples: ?_, ?abc23.

A first-order term is either a constant, a variable, or an expression of the form t(t1,...,tn), where t is a constant, t1,...,tn are first-order terms, and n > 0. Here the constant t is said to be used as a function symbol (or a functor) and t1,...,tn are used as arguments. Variable-free terms are also called ground. The set of all ground terms is known as Herbrand universe.

Following Prolog, we also introduce special notation for lists: [t1,...,tn] and [t1,...,tn|rest], where t1,...,tn and rest are first-order terms. The first form shows all the elements of the list explicitly and the latter shows explicitly only a prefix of the list and uses the first-order term rest to represent the tail. We should note that, like in Prolog, this is just a convenient shorthand notation. Lists are nothing but first-order terms that are representable with function symbols. For instance, if cons denotes a function symbol that prepends a term to the head of a list then [a,b,c] is represented as first-order term cons(a,cons(b,c)).

A first-order atomic formula has the same form as first-order terms except that a variable cannot be a first-order atomic formula. We do not distinguish predicates as a separate class of constants, as this is usually not necessary, since first-order atomic formulas can be distinguished from first-order terms by the context in which they appear.

As many other rule-based languages, SWSL-Rules has a special unification operator, denoted =. The unification operator is always interpreted as an identity relation over the Herbrand universe. Therefore, an atomic formula of the form

where both terms are ground, is true if and only if the two terms are identical. Since the semantics of the unification operator is fixed and is the same for all rulebases, it cannot appear in the head of a rule.

The = predicate is related to the equality predicate, :=:, which is introduced by the Equality Layer.

To test that two terms can never be made identical, SWSL-Rules uses the disunification operator !=. It is interpreted as negation of = so, for ground terms, term₁ != term₂ iff the two terms are not identical.

A conjunctive formula is either an atomic formula or a formula of the form

where and is a conjunction connective. Here and henceforth in similar definitions, italicized words will be meta-symbols that denote classes of syntactic entities. For instance, atomic formula above means ``any atomic formula.'' An and/or formula is either a conjunctive formula or a formula of either of the forms

In other words, an and/or formula can be an arbitrary Boolean combination of atomic formulas that involves the connectives and and or.

To disambiguate the syntax, the user should use parentheses. When parentheses are not given, we assume the standard precedence rules where and binds stronger than or.

Comments. SWSL-Rules has two kinds of comments: single line comments and multiline comments. The syntax is the same as in Java. A single-line comment is any text that starts with a // and continues to the end of the current line. If // starts within a string ("...") or a symbol ('...') then these characters are considered to be part of the string or the symbol, and in this case they do not start a comment. A multiline comment begins with /* and end with a matching */. The combination /* does not start a comment if it appears inside a string or a symbol. The /* - */ pairs can be nested and a nested occurrence of */ does not close the comment. For instance, in

only the second */ closes the comment.

2.3 Horn Rules

A Horn rule has the form

where head is an atomic formula and body is a conjunctive formula.

A Horn query is of the form

where query is a conjunctive formula.

Rules can be recursive, i.e., the predicate in the head of a rule can occur (with the same arity) in the body of the rule; or they can be mutually recursive, i.e., a head predicate can depend on itself through a sequence of rules.

All variables in a rule are considered implicitly quantified with ∀ outside of the rule, i.e., ∀?X,?Y,...(head :- body). A variable that occurs in the body of a rule but not its head can be equivalently considered as being implicitly existentially quantified in the body. For instance,

is equivalent to

The semantics of a set of Horn rules can be characterized in several different ways: through the regular first-order entailment, as a minimal model (which in this case happens to be the intersection of all Herbrand models of the rule set) and as a least fixpoint of the immediate consequence operator corresponding to the rule set [Lloyd87].

2.4 The Monotonic Lloyd-Topor Layer

This layer extends the Horn layer with three kinds of syntactic sugar:

1. Disjunction in the rule body
2. Conjunction in the rule head
3. It introduces the new symbols of classical implication and allows their use in the rule head.

A classical implication is a statement of either of the following forms:

The Lloyd-Topor implication (abbr., LT implication) is a special case of the classical implication where the formula in the head is a conjunction of atomic formulas and the formula in the body can contain both conjunctions and disjunctions of atomic formulas.

A classical bi-implication is a statement of the form

The Lloyd-Topor bi-implication (abbr., LT bi-implication) is a special case of the classical bi-implication where both formulas are conjunctions of atomic formulas.

The monotonic LT layer extends Horn rules in the following way. A rule still has the form

but head can now be a conjunction of atomic formulas and/or LT implications (including bi-implications) and body can consist of atomic formulas combined in arbitrary ways using the and and the or connectives.

This extension is considered a syntactic sugar: the semantics of an extended set of rules is defined by a transformation to a set of rules that does not contain the above extensions. Under the classical first-order semantics, these transformations are known to preserve equivalence, and this fact motivates their use logic programming and SWSL-Rules. The monotonic Lloyd-Topor transformations are listed below.

• head :- body1 or body2.

  reduces to

        head :- body1.
      head :- body2.
• head1 and head2 :- body.

  reduces to

        head1 :- body.
      head2 :- body.
• (head1 <== head2) :- body.

  reduces to

        head1 :- head2 and body.
• (head1 ==> head2) :- body.

  reduces to

        head2 :- head1 and body.

Complex formulas in the head are broken down using the last three reductions. Rule bodies that contain both disjunctions and conjunctions are first converted into disjunctive normal form and then are broken down using the first reduction rule.

2.5 The NAF Layer

The NAF layer adds the negation-as-failure symbol, naf, in the rule body. For instance,

More precisely, if φ is a subformula that is allowed to appear in the rule body, then naf(φ) is also an allowed subformula in the rule body. When φ is an atomic formula then no parentheses are required.

In SWSL-Rules we adopt the well-founded semantics [VanGelder91] as a way to interpret negation as failure. This semantics has good computational properties when no first-order terms of arity greater than 0 are involved, and the well-founded model is always defined and is unique. This model is three-valued, so some facts may have the ``unknown'' truth value.

We should note one important convention regarding the treatment of variables that occur under the scope of naf and that do not occur anywhere outside of naf in the same rule. The well-founded semantics was defined only for ground atoms and the interpretation of unbound variables was left open. Therefore, if Z does not occur elsewhere in the rule then the meaning of

can be informally defined as

(i.e., naf r(?X) is considered true if naf r(t) is determined to be true for some ground term t) or as

where naf r(?X) is considered true if naf r(t) is determined to be true for all ground terms t. In practice, the second interpretation is preferred, and this is also a convention used in SWSL-Rules.

2.6 The Nonmonotonic Lloyd-Topor Layer

This layer introduces explicit bounded quantifiers (both exist and forall), classical implication symbols, <== and ==>, and the bi-implication symbol <==> in the rule body. This essentially permits arbitrary first-order-looking formulas in the body of SWSL-rules. We say "first-order-looking" because it should be kept in mind that the semantics of SWSL-Rules is not first-order and, for example, classical implication A <== B is interpreted in a non-classical way: as (A or naf B) rather than (A or neg B) (where neg denotes classical negation).

Recall that without explicit quantification, all variables in a rule are considered implicitly quantified with forall outside of the rule, i.e., forall ?X,?Y,...(head :- body). A variable that occurs in the body of a rule but not its head can be equivalently considered as being implicitly existentially quantified in the body. For instance,

is equivalent to

In the scope of the naf operator, unbound variables have a different interpretation under negation as failure. For instance, if ?X is bound and ?Y is unbound then

is actually supposed to mean

If we allow explicit universal quantification in the rule bodies then implicit existential quantification is not enough and explicit existential quantifier is needed. This is because forall and exist do not commute and so, for example, forall ?X exist ?Y and exist ?Y forall ?X mean different things. If only implicit existential quantification were available, it would not be possible to differentiate between the above two forms.

Formally, the Nonmonotonic Lloyd-Topor layer permits the following kinds of rules. The rule heads are the same as in the monotonic LT extension. The rule bodies are defined as follows.

• Any atomic formula is a legal rule body
• If f and g are legal rule bodies then so are
  •   f and g
  •   f or g
  •   naf f
  •   f ==> g
  •   f <== g
  •   f <==> g
• If f is a legal rule body then so is
  •   exist ?X1,...,?Xn(f)
  where ?X1, ..., ?Xn are variables that occur positively (defined below) in f.
• If g₁, g₂ are legal rule bodies then
  •   forall ?X1,...,?Xn(g₁ ==> g₂)
  •   forall ?X1,...,?Xn(g₂ <== g₁)
  are legal rule bodies provided that ?X1, ..., ?Xn occur positively in g₁

Positive occurrence of a free variable in a formula is defined as follows:

• Any variable occurs positively in an atomic formula
• A free variable occurs positively in f and g iff it occurs positively in either f or g.
• A free variable occurs positively in f or g iff it occurs positively in both f and g.
• A free variable occurs positively in f ==> g iff it occurs positively in g. Similarly for f <== g, except that now the variable must occur positively in f. Since f <==> g is a conjunction of two clauses, the definition of positive occurrence follows from the previous cases: the variable must occur positively in f or g.
• A free variable occurs positively in exist ?X1,...,?Xn(f) or forall ?X1,...,?Xn(f) iff it occurs positively in f.

The semantics of Lloyd-Topor extensions is defined via a transformation into the NAF layer as shown below. As with monotonic Lloyd-Topor transformations, the nonmonotonic transformations are inspired by the fact that they are known to preserve equivalence under the classical semantics (if naf is interpreted as classical negation). Further discussion of these transformations can be found in [Lloyd87].

Lloyd-Topor transformations: These transformations are designed to eliminate the extended forms that may occur in the bodies of the rules and reduce the rules to the NAF layer. These extended forms involve the various types of implication and the explicit quantifiers. Note that the rules, below, must be applied top-down, that is, to the conjuncts that appear directly in the rule body. For instance, if the rule body looks like

then one should first apply the rule for <==, then the rules for forall should be applied to the result, and finally the rules for exist.

• Let the rule be of the form

        head :- body₁ and (f ==> g) and body₂.

  Then the LT transformation replaces it with the following pair of rules:

        head :- body₁ and naf f and body₂.
        head :- body₁ and g and body₂.

  The transformations for <== and <==> are similar.

• Let the rule be

        head :- body₁ and forall ?X1,...,?Xn(g₁ ==> g₂) and body₂.
  where ?X1,...,?Xn are free variables that occur positively in g₁.

  The LT transformation replaces this rule with the following pair of rules, where q(?X'1,...,?X'n) is a new predicate of arity n and ?X'1,...,?X'n are new variables:

        head :- body₁ and naf q(?X'1,...,?X'n) and body₂
        q(?X1,...,?Xn) :- g₁ and naf g₂.

  The transformation for <== is similar.

• Let the rule be

        head :- body₁ and exist ?X1,...,?Xn(f) and body₂.

  where ?X1,...,?Xn are free variables that occur positively in f.

  The LT transformation replaces this rule with the following:

        head :- body₁ and f and body₂

  That is, explicit existential quantification can be replaced in this case with implicit quantification.

The above transformations are inspired by (but are not derived from, due to a significant difference between naf and neg!) the classical tautologies (f ==> g) <==> (neg f or g)   and   forall X (f) <==> neg exist neg X (f), and by the fact mentioned in section The NAF Layer that naf p(X), when X does not occur anywhere else in the rule, is interpreted as forall X (naf p(X)).

2.7 The Courteous Rules Layer

The courteous layer introduces prioritized conflict handling. Four new features are introduced into the syntax:

• rule labels, which declare names used for prioritization between rules;
• classical negation of atoms;
• a syntactically reserved prioritization predicate, which is used to specify the prioritization ordering between rules;
• mutual exclusion (mutex) statements, which specify the scope of what constitutes conflict.

The theory behind the courteous logic programs is described in [Grosof2004a, Grosof99a].

The courteous layer builds upon the NAF layer of SWSL-Rules.

Rule Labels: Each rule has an optional label, which is used for specifying prioritization in conjunction with the prioritization predicate (below). The syntactic form of a rule label is a term enclosed by a pair of braces: { ... }. Thus, a labeled rule has the following form:

A label is a term, which may have variables. If so, these variables are interpreted as having the same scope as the implicitly quantified variables appearing in the rule expression. E.g., in the rule

the label specialoffer(?X) names the instance of the rule corresponding to the instance ?X. However, the label term may not itself be a variable, so the following is illegal syntax:

In general, labels are not unique; two or more rules (or instances of rules) may have the same label term. However, often it is convenient to specify rule labels uniquely within a particular given rulebase.

Classical Negation: The classical negation connective, neg, is permitted to appear within the head and/or the body of a rule. Its scope is restricted to be an atomic formula, however. Thus classical negation is restricted to appearing within a classical literal. For example:

However, the following example is illegal syntax because neg negates a non-atomic formula.

Note that the classical negation connective (neg) is also used in SWSL-FOL, the first-order subset of SWSL-Language. However, the semantics of classical negation in Courteous LP (and thus SWSL-Rules) is somewhat weaker than in FOL (and thus SWSL-FOL).

Prioritization Predicate: The prioritization predicate _"http://www.ruleml.org/spec/vocab/#overrides" specifies the prioritization ordering between rule labels, and thus between the rules labeled by those rule labels. The name of the prioritization predicate is syntactically reserved. In this document we will use the following prefix declaration

and abbreviate the prioritization predicate using the sQName r#overrides. In the future, we might adopt a different prefix, such as "http://www.swsi.org/swsl/reserved/#".

A statement r#overrides(label1,label2) indicates that the first argument, label1, has higher priority than the second argument, label2. For example, consider the following rulebase RBC1:

Here, the prioritization atom r#overrides(rep,qua) specifies that rep has higher priority than qua. Continuing that example, suppose the rulebase RBC1 also includes the facts:

Then, under the courteous semantics, the literal neg pacifist(nixon) is entailed as a conclusion, and the literal pacifist(nixon) is not entailed as a conclusion, because the rule labeled rep has higher priority than the rule labeled qua.

The prioritization predicate r#overrides, while its name is syntactically reserved, is otherwise an ordinary predicate -- it can appear freely in rules in the head and/or body. This is useful for reasoning about the prioritization ordering.

Mutual exclusion (mutex) statements: The scope of what constitutes conflict is specified by mutual exclusion (mutex) statements, which are part of the rule base and can be viewed as a kind of integrity constraint. Each such statement says that it is contradictory for a particular pair of literals (known as the "opposers") to be inferred, if an optional condition (known as the "given") holds true. The courteous LP semantics enforce that the set of sanctioned conclusions respects (i.e., is consistent with) all the mutexes within the given rulebase. Common uses for mutexes include specifying that two unary predicates are disjoint, or that a relation is functional; examples of these uses are given below.

A mutex without a given condition has the following syntactic form:

where lit1 and lit2 are classical literals. Intuitively, this statement means that it is a contradiction to derive both lit1 and lit2. For example:

says that it is a contradiction to conclude that the discount offered to the same customer ?CUST is both fivepercent and tenpercent. As another example,

specifies that it is a contradiction to conclude that the same individual is both a lion and an elephant.

A mutex with a condition has the following syntactic form:

Here condition is syntactically similar to a rule body, and lit1 and lit2 are classical literals. The symbol "|" is a language keyword, which separates the opposing literals from the condition. For example:

says that it is a contradiction to conclude that the discount offered to the same customer, ?CUST, is both ?Y and ?Z if ?Y and ?Z are distinct values. This means that the relation pricediscount is functional.

Courteous LP also assumes that there is an implicit mutex between each atom A and its classical negation neg A. This implicit mutex is also known as a "classical" mutex.

2.8 The HiLog Layer

HiLog [Chen93] extends the first-order syntax with higher-order features. In particular, it allows variables to range over function symbols, predicate symbols, and even atomic formulas. These features are useful for supporting reification and in cases when an agent needs to explore the structure of an unknown piece of knowledge. HiLog further supports parameterized predicates, which are useful for generic definitions (illustrated below).

• HiLog term (abbr., H-term): A HiLog term is either a first-order term or an expression of the following form: t(t1,...,tn), where t, t1, ..., tn are HiLog terms.

This definition may seem quite similar to the definition of complex first-order terms, but, in fact, it defines a vastly larger set of expressions. In first-order terms, t must be a constant, while in HiLog it can be any HiLog term. In particular, it can be a variable or even another first-order term. For instance, the following are legal HiLog terms:

• Regular first-order terms:   c, f(a,?X), ?X
• Variables over function symbols:   ?X(a,?Y), ?X(a,?Y(?X))
• Parameterized function symbols:   f(?X,a)(b,?X(c)), ?Z(?X,a)(b,?X(?Y)(d)), ?Z(f)(g,a)(p,?X)

We will see soon how such terms can be useful in knowledge representation.

• HiLog atomic formula: Any HiLog term is also a HiLog atomic formula.

Thus, expressions like ?X(a,?Y(?X)) are atomic formulas and thus can have truth values (when the variables are instantiated or quantified). What is less obvious is that ?X is also an atomic formula. What all this means is that atomic formulas are automatically reified and can be passed around by binding them to variables and evaluated. For instance, the following HiLog query

succeeds with the above database and ?X gets bound to p(a).

Another interesting example of a HiLog rule is

This can be viewed as a logical definition of the meta-predicate call/1 in Prolog. Such a definition does not make sense in first-order logic (and is, in fact, illegal), but it is legal in HiLog and provides the expected semantics for call/1.

We will now illustrate one use of the parameterized predicates of the form p(...)(...). The example shows a pair of rules that defines a generic transitive closure of a binary predicate. Depending on the actual predicate passed in as a parameter, we can get different transitive closures.

For instance, for the parent predicate, closure(parent) is defined by the above rules to be the ancestor relation; for the edge relation that represents edges in a graph, closure(edge) will become the transitive closure of the graph.

2.9 The Equality Layer

This layer introduces the full equality predicate, :=:. The equality predicate obeys the usual congruence axioms for equality. In particular, it is transitive, symmetric, reflexive, and the logical entailment relation is invariant with respect to the substitution of equals by equals. For instance, if we are told that bob :=: father(tom) (bob is the same individual as the one denoted by the term father(tom)) then if p(bob) is known to be true then we should be able to derive p(father(tom)). If we are also told that bob :=: uncle(mary) is true then we can derive father(tom):=: uncle(mary).

Equality in a Semantic Web language is important to be able to state that two different identifiers represent the same resource. For that reason, equality was part of OWL [OWL Reference]. Although equality drastically increases the computational complexity, some forms of equality, such as ground equality, can be handled efficiently in a rule-based language.

The equality predicate :=: is different from the unification operator = in several respects. First, for variable free terms, term₁ = term₂ if and only if the two terms are identical. In contrast, as we have just seen, two distinct terms can be equal with respect to :=:. Since :=: is reflective, it follows that the relation that is used as an interpretation of :=: always contains the interpretation of =. Second, the unification operator = cannot appear in a rule head, while the equality predicate :=: can. When :=: occurs in the rule head (or as a fact), it is an assertion (conditioned on the truth value of the rule body) that two terms are equal. For instance, given the above definitions,

entails the following equalities between distinct terms: f(a,1):=:g(2,b) and f(a,2):=:g(3,b).

Informally, when term₁ :=: term₂ occurs in the body of a rule and term₁ and term₂ have variables, this predicate is interpreted as a test that variables can be consistently replaced with ground terms so that term₁ and term₂ will become equal with respect to :=: (note: equal, not identical!). For instance, in the query

one answer substitution is ?X/1,?Y/2 and the other is ?X/2,?Y/3. The formal definition follows the standard outline of [Lloyd87] and will be given in a separate document. Section 2.14 provides an overview of the semantics.

2.10 The Frames Layer

The Frames layer introduces object-oriented syntax modeled after F-logic [Kifer95] and its subsequent enhancements [Yang02, Yang03]. The main syntactic additions of this layer include

• Frame syntax. Frames are called molecules here (following the F-logic terminology).
• Path expressions.
• Notation for class membership and subclasses.
• Notation for type specification, which is given by signature molecules.

The object-oriented extensions introduced by the Frames layer are orthogonal to the other layers described so far and can be combined with them within the SWSL-Rules language.

As in most object-oriented languages, the three main concepts in the Frames layer of SWSL-Rules are objects, classes, and methods. (We are borrowing from the object-oriented terminology here rather than AI terminology, so we are refer to methods rather than slots.) Any class is also an object, and the same expression can denote an object or a class represented by this object in different contexts.

A method is a function that takes arguments and executes in the context of a particular object. When invoked, a method returns a result and can possibly alter the state of the knowledge base. A method that does not take arguments and does not change the knowledge base is called an attribute. An object is represented by its object Id, the values of its attributes, and by the definitions of its methods. Method and attribute names are represented as objects, so one can reason about them in the same language.

An object Id is syntactically represented by a ground term. Terms that do have variables are viewed as templates for collections of object Ids—one Id per ground instantiation of all the variables in the term. By term we mean any expression that can bind a variable. What constitutes a legal term depends on the layer. In the basic case, by term we mean just a first-order term. If the Frames layer is combined with HiLog, then terms are meant to be HiLog terms. Later, when we introduce reification, reification terms will also be considered.

Molecules. Molecules play the role of atomic formulas. We first describe atomic molecules and then introduce complex molecules. Although both atomic and complex molecules play the role of atomic formulas, complex molecules are not indivisible. This is why they are called molecules and not atoms. Molecules come in several different forms:

• Value molecule. If t, m, v are terms then t[m -> v] is a value molecule.

  Here t denotes an object, m denotes a method invocation in the scope of the object t, and v denotes a value that belongs to a set returned by this invocation. We call m ``a method invocation'' because if m = s(t1,...,tn), i.e., has arguments, then t[s(t1,...,tn) -> v] is interpreted as an invocation of method s on arguments t1,...,tn in the context of the object t, which returns a set of values that contains v.

  The syntax t[m -> {v1,...,vk}] is also supported; it means that if m is invoked in the context of the object t then it returns a set that contains v1,...,vk. Thus, semantically, such a term is equivalent to a conjunction of t[m -> v1], ..., t[m -> vk], so the expressions t[m -> {v1,...,vk}] is just a syntactic sugar.

• Boolean valued molecule. These molecules have the form t[m] where t and m are terms.

  Boolean molecules are useful to specify things like mary[female]. The same could be alternatively written as mary[female -> true], but this is less natural.

• Class membership molecule. If t and s are terms then t:s is a membership molecule.

  If t and s are variable free, then such a molecule states that the object t is a member of class s. If these terms contain variables, then such a molecule can be viewed as many class membership statements, one per ground instantiation of the variables.

• Subclass molecule: If t and s are terms then t::s is a subclass molecule.

  If t and s are variable free, then such a molecule states that the object t is a subclass of s. As in the case of class membership molecules, subclass molecules that have variables can be viewed as statements about many subclass relationships.

• Signature molecule: If t, m, v are terms then t[m => v] is a signature molecule.

  If t, m, and v are variable-free terms then the informal meaning of the above signature molecule is that t represents a class, which has a method invocation m which returns a set of objects of type v (i.e., each object in the set belongs to class v). If these terms are non-ground then the signature represents a collection of statements—one statement per ground instantiation of the terms.

  When m itself has arguments, for instance m = s(t1,...,tn), then the arguments are interpreted as types. Thus, t[s(t1,...,tn) => v] states that when the n-ary method s is invoked on object of class t with arguments that belong to classes t1, ..., tn, the method returns a set of objects of class v.

• Boolean signature molecules: A Boolean signature molecule has the form t[m=>]. Its purpose is to provide type information for Boolean valued molecules. Namely, if m=s(t1,...,tn), then when the method s is invoked on an object of class t, the method arguments must belong to classes t1, ..., tn.

• Cardinality constraints: Signature molecules can have associated cardinality constraints. Such molecules have the form

        t[s(t1,...,tn) {min : max} => v]

  where min and max are non-negative integers such that min ≤ max. Max can also be *, which means positive infinity.

  Such a signature states not only that the invocation of the method s with arguments of type t1,...,tn on an object of class t returns objects of class v, but also that the number of such objects in the result is no less than min and no more than max.

  The semantics of constraints in SWSL-Rules is similar to constraints in databases and is unlike the cardinality restrictions in OWL [OWL Reference]. For instance, if a cardinality constraint says that an attribute should have at least two values and the rule base derives only one then the constraint is violated. In contrast, OWL would infer that there is another, yet unknown, value. Likewise, if a cardinality constraint says that the number of elements is at most three while the rule base derives four unequal elements then the constraint is, again, violated. This should be compared to the OWL semantics, which will infer that some pair of derived values in fact consists of equal elements.

Signatures and type checking: Signatures are assertions about the expected types of the method arguments and method results. They typically do not have direct effect on the inference (unless signatures appear in rule bodies). The signature information is optional.

The semantics of signatures is defined as follows. First, the intended model of the knowledge base is computed (which in SWSL-Rules is taken to be the well-founded model). Then, if typing needs to be checked, we must verify that this intended model is well-typed. A well-typed model is one where the value molecules conform to their signatures. For the precise definition of well-typed models see [Kifer95]. (There can be several different notions of well-typed models. For instance, one for semi-structured data and another for completely structured data.)

A type-checker can be written in SWSL-Rules using just a few rules. Such a type checker is a query, which returns "No", if the model is well-typed and a counterexample otherwise. In particular, type-checking has the same complexity as querying. An example of such type checker can be found in the FLORA-2 manual [Yang04].

It is important to be aware of the fact that the semantics of the cardinality constraints in signature molecules is inspired by database theory and practice and it is different from the semantics of such constraints in OWL [OWL Reference]. In SWSL-Rules, cardinality constraints are restrictions on the intended models of the knowledge base, but they are not part of the axioms of the knowledge base. Therefore, the intended models of the knowledge base are determined without taking the cardinality constraints into the account. Intended models that do not satisfy these restrictions are discarded. In contrast, in OWL cardinality constraints are represented as logical statements in the knowledge base and all models are computed by taking the constraints into the account. Therefore, in OWL it is not possible to talk about knowledge base updates that violate constraints. For instance, the following signature married[spouse {1:1} => married] states that every married person has exactly one spouse. If john:married is true but there is no information about John's spouse then OWL will assume that john has some unknown spouse, while SWSL-Rules will reject the knowledge base as inconsistent. If, instead, we know that john[spouse -> mary] and john[spouse -> sally] then OWL will conclude that mary and sally are the same object, while SWSL-Rules will again rule the knowledge base to be inconsistent (because, in the absence of the information to the contrary — for example, if no :=:-statements have been given — mary and sally will be deemed to be distinct objects).

Inheritance in SWSL-Rules: Inheritance is an optional feature, which is expressed by means of the syntactic features described below. In SWSL-Rules, methods and attributes can be inheritable and non-inheritable. Non-inheritable methods/attributes correspond to class methods in Java, while inheritable methods and attributes correspond to instance methods.

The value- and signature-molecules considered so far involve non-inheritable attributes and methods. Inheritable methods are defined using the *-> and *=> arrow types, i.e., t[m *-> v] and t[m *=> v]. For Boolean methods we use t[*m] and t[m*=>].

Signatures obey the laws of monotonic inheritance, which are as follows:

• t:s and s[m *=> v] entails t[m *=> v]
• t::s and s[m *=> v] entails t[m => v]

These laws state that type declarations for inheritable methods are inherited to subclasses in an inheritable form, i.e., they can be further inherited. However, to the members of a class such declarations are inherited in a non-inheritable form. Thus, inheritance of signatures is propagated through subclasses, but stops once it hits class members.

Inheritance of value molecules is more involved. This type of inheritance is nonmonotonic and it can be overridden if the same method or attribute is defined for a more specific class. More precisely,

• t:s and s[m *-> v] entails t[m *-> v]   unless overridden or in conflict
• t::s and s[m *-> v] entails t[m -> v]   unless overridden or in conflict

Similarly to signatures, value molecules are inherited to subclasses in the inheritable form and to members of the classes in the non-inheritable form. However, the key difference is the phrase "unless overridden or in conflict." Intuitively, this means that if, for example, there is a class w in-between t and s such that the inheritable method m is defined there then the inheritance from s is blocked and m should be inherited from w instead. Another situation when inheritance might be blocked arises due to multiple inheritance conflicts. For instance, if t is a subclass of both s and u, and if both s and u define the method m, then inheritance of m does not take place at all (either from s or from u; this policy can be modified by specifying appropriate rules, however). The precise model-theoretic semantics of inheritance with overriding is based on an extended form of the Well-Founded Semantics. Details can be found in [Yang02].

Note that signature inheritance is not subject to overriding, so every inheritable molecule is inherited to subclasses and class instances. If multiple molecules are inherited to a class member or a subclass, then all of them are considered to be true.

Inheritance of Boolean methods is similar to the inheritance of methods and attributes that return non-Boolean values. Namely,

• t:s and s[m*=>] entails t[m*=>]
• t::s and s[m*=>] entails t[m =>]
• t:s and s[*m] entails t[*m]   unless overridden
• t::s and s[*m] entails t[m]   unless overridden

Complex molecules: SWSL-Rules molecules can be combined into complex molecules in two ways:

• By grouping.
• By nesting.

Grouping applies to molecules that describe the same object. For instance,

is, by definition, equivalent to

Molecules connected by the or connective can also be combined using the usual precedence rules:

becomes

The and connective inside a complex molecule can also be replaced with a comma, for brevity. For example,

Nesting applies to molecules in the following ``chaining'' situation, which is a common idiom in object-oriented databases:

is by definition equivalent to

Nesting can also be used to combine membership and subclass molecules with value and signature molecules in the following situations:

are equivalent to

respectively.

Molecules can also be nested inside predicates and terms with a semantics similar to nesting inside other molecules. For instance, p[a->c] is considered to be equivalent to p(a) and a[b->c]. Deep nesting and, in fact, nesting in any part of another molecule or predicate is also allowed. Thus, the formulas

are considered to be equivalent to

respectively. Note that molecule nesting leads to a completely compositional syntax, which in our case means that molecules are allowed in any place where terms are allowed. (Not all of these nestings might look particularly natural, e.g., a[b -> c](q,r) or p(a[b -> c](?X)), but there is no good reason to reject these nestings and thus complicate the syntax either.)

Path expressions: Path expressions are useful shorthands that are widely used in object-oriented and Web languages. In a logic-based language, a path expression sometimes allows writing formulas more concisely by eliminating multiple nested molecules and explicit variables. SWSL-Rules defines path expressions only as replacements for value molecules, since this is where this shorthand is most useful in practice.

A path expression has the form

or

The former corresponds to non-inheritable molecules and the latter to inheritable ones. In fact, "." and "!" can be mixed within the same path expression.

A path expression can occur anywhere where a term is allowed to occur. For instance, a[b -> c.d], a.b.c[e -> d], p(a.b), and X=a.b are all legal formulas. The semantics of path expressions in the body of a rule and in its head are similar, but slightly different. This difference is explained next.

In the body of a rule, an occurrence of the first path expression above is treated as follows. The conjunction

is added to the body and the occurrence of the path expression is replaced with the variable ?Var_n. In this conjunction, the variables ?Var1, ..., ?Varn are new and are used to represent intermediate values. The second path expression is treated similarly, except that the conjunction

is used. For instance, mary.father.mother = sally in a rule body is replaced with

In the head of a rule, the semantics of path expressions is reduced to the case of a body occurrence as follows.. If a path expression, ρ, occurs in the head of a rule, it is replaced with a new variable, ?V, and the predicate ?V=ρ is conjoined to the body of the rule. For instance,

is understood as

Note that since molecules can appear wherever terms can, path expressions of the form a.b[c -> d].e.f[g -> h].k are permitted. They are conceptually similar to XPath expressions with predicates that control the selection of intermediate nodes in XML documents. Formally, such a path expression will be replaced with the variable ?V and will result in the addition of the following conjunction:

It is instructive to compare SWSL-Rules path expressions with XPath. SWSL-Rules path expressions were originally proposed for F-logic [Kifer95] several years before XPath. The purpose was to extend the familiar notation in object-oriented programming languages and to adapt it to a logic-based language. It is easy to see that the ``*'' idiom of XPath can be captured with the use of a variable. For instance, b/*/c applied to object e is expressed as e.b.?X.c. The ``..'' idiom of XPath is also easy to express. For instance, a/../b/c applied to object d is expressed as ?_[?_ -> d.a].b.c. On the other hand, there is no counterpart for the // idiom of XPath. The reason is that this idiom is not well-defined when there are cycles in the data (for instance, a[b -> a]). However, recursive descent into the object graph can be defined via recursive rules.

2.11 Reification

The reification layer allows SWSL-Rules to treat certain kinds of formulas as terms and therefore to manipulate them, pass them as parameters, and perform various kinds of reasoning with them. In fact, the HiLog layer already allows certain formulas to be reified. Indeed, since any HiLog term is also a HiLog atomic formula, such atomic formulas are already reifiable. However, the reification layer goes several steps further by supporting reification of arbitrary rule or formula that can occur in the rule head or rule body. (Provided that it does not contain explicit quantifiers -- see below.)

Formally, if F is a formula that has the syntactic form of a rule head, a rule body, or of a rule then F is also considered to be a term. This means that such a formula can be used wherever a term can occur.

Note that a reified formula represents an objectification of the corresponding formulas. This is useful for specifying ontologies where objects represent theories that can be true in some worlds, but are not true in the present world (and thus those theories cannot be asserted in the present world). Examples include the effects of actions: effects of an action might be true in the world that will result after the execution of an action, but they are not necessarily true now.

In general, reification of formulas can lead to logical paradoxes [Perlis85]. The form of reification used in SWSL-Rules does not cause paradoxes, but other unpleasantries can occur. For instance, the presences of a truth axiom (true(?X) <--> ?X) can render innocently looking rule-bases inconsistent. However, as shown in [Yang03], the form of reification in SWSL-Rules does not cause paradoxes as long as

• rule heads do not contain classical negation; and
• a rule head cannot be a variable, i.e., as long as the rules of the form  ?X :- body  (which are legal in HiLog) are disallowed.

We therefore adopt the above restrictions for all layers of SWSL-Rules.

As presented above, reification introduces syntactic ambiguity, which arises due to the nesting conventions for molecules. For instance, consider the following molecule:

Suppose that t is a reification of another molecule, c[d -> e]. Since we have earlier said that any formula suitable to appear in the rule body can also be viewed as a term, we can expand the above formula into

But this is ambiguous, since earlier we defined the above as a commonly used object-oriented idiom, a syntactic sugar for

Similarly, if we want to write something like t[b -> c] where t is a reification of f[g -> h] then we cannot write f[g -> h][b -> c] because this nested molecule is a syntactic sugar for f[g -> h] and f[b -> c]. To resolve this ambiguity, we introduce the reification operator, ${...}, whose only role is to tell the parser that a particular occurrence of a nested molecule is to be treated as a term that represents a reified formula rather than as syntactic sugar for the object-oriented idiom.

Note that the explicit reification operator is not required for HiLog predicates because there is no ambiguity. For instance, we do not need to write ${p(?X)} below (although it is permitted and is considered the same as p(?X)):

This is because a[b -> p(?X)] does not mean   a[b -> p(?X)] and p(?X), since the sugar is used only for nested molecules.

In contrast, explicit reification is needed below, if we want to reify p(?X[foo -> bar]):

Otherwise p(?X[foo -> bar]) would be treated as syntactic sugar for sugar for

Therefore, to reify p(?X[foo -> bar]) in the above molecule one must write this instead:

Example. Reification in SWSL-Rules is very powerful and yet it doesn't add to the complexity of the language. The following fragment of a knowledge base models an agent who believes in the modus ponens rule:

Since the agent believes in p(a) and in the modus ponens rule, it can infer q(a). Note that in the above we did not need explicit reification of p(a), since no ambiguity can arise. However, we used the explicit reification anyway, for clarity.

Syntactic rules. Currently SWSL-Rules does not permit explicit quantifiers under the scope of the reification operator, because the semantics for reification given in [Yang03, Kifer04] does not cover this case. So not every formula can be reified. More specifically, the formulas that are allowed under the scope of the reification operator are:

• The formulas that are allowed in the rule head or quantifier-free formulas in the rule body.
• Quantifier-free rules.

The implication of these restrictions is that every term that represents a reification of a SWSL-Rules formula has only free variables, which can be bound outside of the term. Each such term can therefore be viewed as a (possibly infinite) set of reifications of the ground instances of that formula.

2.12 Skolemization in SWSL-Rules

It is often necessary to specify existential information in the head of a rule or in a fact. Due to the limitations of the logic programming paradigm, which trades the expressive power for executional efficiency, such information cannot be specified directly. However, existential variables in the rule heads can be approximated through the technique known as Skolemization [Chang73]. The idea of Skolemization is that in a formula of the form ∀Y1...Yn ∃X ... φ the existential variable X can be removed and replaced everywhere in φ with the function term f(Y1...Yn), where f is a new function symbol that does not occur anywhere else in the specification. The rationale for such a substitution is that, for any query, the original rule base is unsatisfiable if and only if the transformed rule base is unsatisfiable [Chang73]. This implies that the query to the original rule base can be answered if and only if it can be answered when posed against the Skolemized rule base. However, from the point of view of logical entailment, the Skolemized rule base is stronger than the original one, and this is why we say that Skolemization only approximates existential quantification, but is not equivalent to it.

Skolemization is defined for formulas in prenex normal form, i.e., formulas where all the quantifiers are collected in a prefix to the formula and apply to the entire formula. A formula that is not in the prenex normal form can be converted to one in the prenex normal form by a series of equivalence transformations [Chang73].

SWSL-Rules supports Skolemization by providing special constants _# and _#1, _#2, _#3, and so on. As with other constants in SWSL-Rules, these symbols can be used both in argument positions and in the position of a function. For instance, _#(a,_#,_#2(c,_#2)) is a legal function term.

Each occurrence of the symbol _# denotes a new constant. Generation of such a constant is the responsibility of the SWSL-Rules compiler. For instance, in _#(a,_#,_#2(c,_#2)), the two occurrences of _# denote two different constants that do not appear anywhere else. In the first case, the constant is in the position of a function symbol. The numbered Skolem constants, such as _#2 in our example, also denote a new constant that does not occur anywhere else in the rule base. However, the different occurrences of the same numbered symbol in the same rule denote the same new constant. Thus, in the above example the two occurrences of _#2 denote the same new symbol. Here is a more complete example:

In the first line, the two occurrences of _#1 denote the same new Skolem constant, since they occur in the scope of the same rule. In the second line, the occurrence of _# denotes a new Skolem function symbol. Since we used _# here, this symbol is distinct from any other constant. Note, however, that even if we used _#1 in the second rule, that symbol would have denoted a distinct new function symbol, since it occurs in a separate rule and there is no other occurrence of _#1 in that rule.

The Skolem constants in SWSL-Rules are in some ways analogous to the blank nodes in RDF. However, they have the semantics suitable for a rule-based language and it has been argued in [Yang03] that the Skolem semantics is superior to RDF, which relies on existential variables in the rule heads [Hayes04].

2.13 SWSL-Rules and XML Schema Data Types

SWSL-Rules supports the primitive XML Schema data types. However, since SWSL-Rules is quite different from XML, it adapts the lexical representation for XML data types to the form that is more suitable for a logic-based language. The translation from the XML lexical representation of primitive data types to SWSL-Rules is straightforward.

The general rule is that each primitive value is represented by a function term whose functor symbol is the name of the primitive data type prefixed with an underscore (_). The arguments of the term represent the various components of the primitive data type. For instance, _string("abc"), _date(2005,7,18), _decimal(123.56), _integer(321), _float(23e5), and so on.

The string, decimal, integer, and float data types have a shorthand notation (some of which had been seen before). Thus, _string("abc") is abbreviated to "abc", _decimal(123.56) to 123.56, _integer(321) to 321, and _float(23e5) to 23e5.

Other primitive data types are represented using a similar notation. For instance, the duration of 1 year, 2 months, 3 days, 10 hours, and 30 minutes is represented as _duration(1,2,3,10,30,0) where the first argument of _duration represents years and the last seconds. The same negative duration is represented as -_duration(1,2,3,10,30,0). For another example, the values of the dateTime type are represented as _dateTime(2005,10,29,15,55,40).

It is often necessary to exchange values of primitive data types between applications. Since the internal representations of the data types vary from language to language, serialization into a commonly agreed representation has been used for this purpose. SWSL-Rules supports serialization of primitive data types via the built-in predicate _serialize. It takes three arguments: a SWSL-Rules value of a SWSL-Rules data type, a URI that denotes the target of serialization, and a result, which is a string that contains the serialized value. Currently, the only target is http://www.w3.org/2001/XMLSchema, which refers to XML Schema 1.0. Other targets will be added as necessary (for example, for XML Schema 1.1 when it is released). Example: _serialize(_date(2005,1,1),_"http://www.w3.org/2001/XMLSchema",?Result) binds ?Result to "2005-01-01".

The predicate _serialize is intended to work both ways: for serialization and deserialization. Deserialization occurs when the last argument is bound to a string representation of a data type and the first argument is unbound. For instance, _serialize(?Result,_"http://www.w3.org/2001/XMLSchema","2005-01-01") binds ?Result to _date(2005,1,1).

2.14 Overview of the Semantics of SWSL-Rules

A single point of reference for the model-theoretic semantics of SWSL-Rules will be given in a separate document. Here we will only give an overview and point to the papers where the semantics of the different layers were defined separately.

First, we note that the semantics of the Lloyd-Topor layers -- both monotonic and nonmonotonic -- is transformational and was given in Sections 2.4 and 2.6. Similarly, the Courteous layer is defined transformationally and is described in [Grosof2004a].

The model theory of NAF is given by the well-founded semantics as described in [VanGelder91]. The model theory behind HiLog is described in [Chen93] and F-logic is described in [Kifer95]. The semantics of inheritance that is used in SWSL-Rules is defined in [Yang02]. The model theory of reification is given in [Yang03] and was further extended to reification of rules in [Kifer04].

The semantics of the Equality layer is based on the standard semantics (for instance, [Chang73]) but is modified by the unique name assumption, which states that syntactically distinct terms are unequal. This modification is described in [Kifer95], and we summarize it here. First, without equality, SWSL-Rules makes the unique name assumption. With equality, the unique name assumption is modified to say that terms that cannot be proved equal with respect to :=: are assumed to be unequal. In other words, SWSL-Rules makes a closed world assumption about explicit equality.

Other than that, the semantics of :=: is standard. The interpretation of this predicate is assumed to be an equivalence relation with congruence properties. A layman's term for this is "substitution of equals by equals." This means that if, for example, t:=:s is derived for some terms t and s then, for any formula φ, it is true if and only if ψ is true, where ψ is obtained from φ by replacing some occurrences of t with s.

Overall, the semantics of SWSL-Rules has nonmonotonic flavor even without NAF and its extension layers. This is manifested by the use of the unique name assumption (modified appropriately in the presence of equality) and the treatment of constraints. To explain the semantics of constraints, we first need to explain the idea of canonic models.

In classical logic, all models of a set of formulas are created equal and are given equal consideration. Nonmonotonic logics, on the other hand, carefully define a subset of models, which are declared to be canonical and logical entailment is considered only with respect to this subset of models. Normally, the canonical models are so-called minimal models, but not all minimal models are canonical.

Any rule set that does not use the features of the NAF layer and its extensions is known to have a unique minimal model, which is also its canonical model. This is an extension of the well-known fact for Horn clauses in classical logic programming [Lloyd87]. With NAF, a rule set may have multiple incomparable minimal models, and it is well-known that not all of these models appropriately capture the intended meaning of rules. However, it turns out that one such model can be distinguished, and it is called the well-founded model [VanGelder91]. A formula is considered to be true according to the SWSL-Rules semantics if and only if it is true in that one single model, and the formula is false if and only if it is false in that model.

Now, in the presence of constraints, the semantics of SWSL-Rules is defined as follows. Given a rulebase, first its canonical model is determined. In this process, all constraints are ignored. Next, the constraints are checked in the canonical model. If all of them are true, the rulebase is said to be consistent. If at least one constraint is false in the canonical model, the constraint is said to be violated and the rulebase is said to be inconsistent.

2.15 Future Extensions

To enhance the power of the SWSL-Rules language, a number of extensions are being planned, as described below.

• If-then-else. The if test then test1 is sometimes more convenient and familiar than the ==> operator. More important, however, is the fact that the more complete idiom, if test then test1 else test2, is known to be very useful and common in rule-based languages. Although the else-part can be expressed with negation as failure, this is not natural and most well-developed languages support the if-then-else idiom directly. This idiom may be added to SWSL-Rules later.

• Aggregate operators. Aggregate operators, such as sum, average, etc., are important database operations. XML languages such as XPath, XSLT, and XQuery all have support for aggregation. Of these, only XQuery permits aggregation over general set comprehension. A future extension of SWSL-Rules will allow aggregation in the style of FLORA-2, which supports explicit set comprehension and nested aggregation. The general syntax of such aggregation is:

        ?Result = aggregate{?Var [GroupingVarList] | Query }

  where aggregate can be max, min, avg, count, sum, collectset, collectbag. The last two aggregates return lists of the instantiations of ?Var that satisfy Query without the duplicates (collectset) and with possible duplicates (collectbag).

  The grouping variables provide the functionality similar to GROUP BY of SQL. They have the effect that the aggregation produces one list of results per every instantiation of the variables in GroupingVarList for which Query has a solution. The variable ?Result gets successively bound to each such list (one list at a time).

• Constraints. Constraints play a very important role in database and knowledge base applications. As a future extension, SWSL-Rules will have database-style constraints. Database constraints are different in nature from restrictions used in Description Logic. Whereas restrictions in Description Logic are part of the same logical theory as the rest of the statements and are used to derive new statements, constraints in databases are not used to derive new information. Instead, they serve as tests of correctness for the canonical models of the knowledge base. In this framework, canonical models (e.g., the well-founded model [VanGelder91]) are first computed without taking constraints into account. These models are then checked against the constraints. The models that do not satisfy the constraints are discarded. In the case of the well-founded semantics, which always yields a single model, testing satisfaction of the constraints validates whether the knowledge base is in a consistent state.

• Procedural attachments, state changes à la Transaction Logic, situated logic programs. A procedural attachment is a predicate or a method that is implemented by an external procedure (e.g., in Java or Python). Such a procedure can have a side effect on the real world (e.g., sending an email or activating a device) or it can receive information from the outside world. First formalizations of these ideas in the context of database and rule based languages appeared in [Maier81, Chimenti89]. These ideas were recently explored in [Grosof2004a] in the context of e-commerce. Transaction Logic [Bonner98] provides a seamless integration of these concept into the logic.

  An attached procedure can be specified by a link statement, which associates a predicate or a method with an external program. The exact details of the syntax have not been finalized, but the following is a possibility:

        attachment relation/Arity name-of-java-procedure(integer,string,...)

  This syntax can be generalized to include object-oriented methods.

  Another necessary extension involves update primitives - primitives for changing the underlying state of the knowledge. These primitives can add or delete facts, and even add or delete rules. A declarative account of such update operations in the context of a rule-based language is given by Transaction Logic [Bonner98]. This logic also can also be used to represent triggers (also known as ECA rules) [Bonner93].

• Predicates with named arguments. For predicates with ordered arguments, named attributes are essentially supported by the current syntax. For instance, if -> is viewed as an infix binary function symbol, then p(foo -> 1, bar -> 2) is a valid term in SWSL-Rules. Predicates with unordered arguments can make unification exponential and are unlikely to be supported in the future.

• The "rest"-variables. The ``rest'' notation à la SCL can be useful in metaprogramming. A rest-variable binds to a list of variables or terms and it always occurs as the last variable of a term. During unification with another term, such a variable binds to a list of arguments of that term beginning with argument corresponding to the variable till the rest of the term (whence the name of such variables). For instance, in the following term, ?R is a rest-variable:

        p(?X,?Y | ?R)

  If this term is unified with p(?Z,f,?Z,q), then ?X binds to ?Z, ?Y to f, and ?R to the list [?Z,q].

• Non-ground identity relation, ==. This predicate is true if the arguments are identical up to variable renaming. This predicate is not declarative but can be very useful, as demonstrated by the extensive practice of logic programming.

3 Serialization of SWSL-Rules in RuleML

SWSL-Rules is serialized in XML using RuleML. RuleML-style serialization enables interoperation with other XML applications for rules and provides an encoding for transporting SWSL-Rules via the SOAP infrastructure of Web services.

RuleML integrates various rule paradigms via common set of concepts and defines a family of rule-based, Web-enabled sublanguages with various degrees of expressiveness. This section applies the RuleML approach to serialization of SWSL-Rules. This is done mostly by reusing and sometimes extending the existing RuleML sublanguages. In addition, a new sublanguage for the serialization of HiLog is developed.

Serialization of the presentation syntax of SWSL-Rules amounts to construction of explicit parse trees and then representing these trees linearly as XML markup that is compliant with XML Schema of the appropriate RuleML sublanguages. Starting with Version 0.89, the XML Schema specification of RuleML supports SWSL-Rules.

Conceptually, RuleML models XML trees as objects and thus divides all XML tags into class descriptors, called type tags (which are capitalized), and property descriptors, called role tags (which start with lowercase letters). This conceptual object-oriented model implies that type tags and role tags must alternate, which is known as striped XML syntax. For instance, in F-logic and RDF, classes can have properties, which point to classes, which have properties that point to classes, etc. Similarly, in the striped XML syntax, a type tag has role tags as subelements, whose children are again type tags, etc. When the role of a subelement is clear from the context, its tag may be skipped for brevity, as in RDF's StripeSkipping.

3.1 Serialization of the HiLog Layer

HiLog terms. The HiLog serialization uses the type tag Hterm for HiLog terms, Con for constants, and Var for variables. Since HiLog allows arbitrary terms to be used in the position of predicate and function symbols, the RuleML serialization allows not only constants but also variables and Hterms under the op role tag . The following illustrates the main aspects of the HiLog serialization.

• Regular first-order terms. For instance, the HiLog terms c, f(a,?X), ?X are represented by the following three XML fragments, respectively:

  	    <Con>c</Con>
  	  

  	    <Hterm>
  	       <op><Con>f</Con></op>
  	       <Con>a</Con>
  	       <Var>X</Var>
  	    </Hterm>
  	  

  	    <Var>X</Var>
  	  

• Variables over function symbols. For instance, the terms ?X(a,?Y), ?X(a,?Y(?X)) are serialized as follows:

  	    <Hterm>
  	       <op><Var>X</Var></op>
  	       <Con>a</Con>
  	       <Var>Y</Var>
  	    </Hterm>
  	  

  	    <Hterm>
  	       <op><Var>X</Var></op>
  	       <Con>a</Con>
  	       <Hterm>
  	          <op><Var>Y</Var></op>
  	          <Var>X</Var>
  	       </Hterm>
  	    </Hterm>
  	  

• Parameterized function symbols. For instance, the HiLog terms f(?X,a)(b,?X(c)), ?Z(?X,a)(b,?X(?Y)(d)), ?Z(f)(g,a)(p,?X) will be serialized as shown below:

  	    <Hterm>
  	       <op>
  	          <Hterm>
  	             <op><Con>f</Con></op>
  	             <Var>X</Var>
  	             <Con>a</Con>
  	          </Hterm>
  	       </op>
  	       <Con>b</Con>
  	       <Hterm>
  	          <op><Var>X</Var></op>
  	          <Con>c</Con>
  	       </Hterm>
  	    </Hterm>
  	  

  	    <Hterm>
  	       <op>
  	          <Hterm>
  	             <op><Var>Z</Var></op>
  	             <Var>X</Var>
  	             <Con>a</Con>
  	          </Hterm>
  	       </op>
  	       <Con>b</Con>
  	       <Hterm>
  	          <op>
  	             <Hterm>
                          <op><Var>X</Var></op>
                          <Var>Y</Var>
  	             </Hterm>
  	          </op>
  	          <Con>d</Con>
  	       </Hterm>
  	    </Hterm>
  	  

  	    <Hterm>
  	       <op>
  	          <Hterm>
  	             <op>
                          <Hterm>
                             <op><Var>Z</Var></op>
                             <Con>f</Con>
                          </Hterm>
  	             </op>
  	             <Con>g</Con>
  	             <Con>a</Con>
  	          </Hterm>
  	       </op>
  	       <Con>p</Con>
  	       <Var>X</Var>
  	    </Hterm>
  	  

HiLog atomic formulas. Since any HiLog term is also a HiLog atomic formula, the RuleML serialization for these formulas is the same as for HiLog terms. The following example shows an encoding of a query, which uses the Query element of RuleML:

	?- q(?X) and ?X.
      

	<Query>
	   <And>
	      <Hterm>
	         <op><Con>q</Con></op>
	         <Var>X</Var>
	      </Hterm>
	      <Var>X</Var>
	   </And>
	<Query>
      

Another interesting example is a HiLog rule

	call(?X) :- ?X.
      

which is a logical definition of the meta-predicate call/1 in Prolog. This is translated using the RuleML tags Implies, head, and body, as follows:

	<Implies>
	   <head>
	      <Hterm>
	         <op><Con>call</Con></op>
	         <Var>X</Var>
	      </Hterm>
	   </head>
	   <body>
	      <Var>X</Var>
	   </body>
	</Implies>
      

3.2 Serialization of Explicit Equality

The explicit equality predicate :=: is serialized using the RuleML's element Equal. For example,

	f(a,?X):=:g(?Y,b) :- p(?X,?Y).
      

is serialized as

	<Implies>
	   <head>
	      <Equal>
	         <Hterm>
	            <op><Con>f</Con></op>
	            <Con>a</Con>
	            <Var>X</Var>
	         </Hterm>
	         <Hterm>
	            <op><Con>g</Con></op>
	            <Var>Y</Var>
	            <Con>b</Con>
	         </Hterm>
	      </Equal>
	   </head>
	   <body>
	      <Hterm>
	         <op><Con>p</Con></op>
	         <Var>X</Var>
	         <Var>Y</Var>
	      </Hterm>
	   </body>
	</Implies>
      

3.3 Serialization of the Frames Layer

To serialize the Frames layer of SWSL-Rules we need to show the serialization of the various molecules and path expressions introduced by F-logic.

Molecules. The serialization of molecules uses slotted atoms, which have an oid but often do not have an op. The overall structure of F-logic molecules (except for class membership and subclassing) is as follows:

	Atom ::= oid op? slot*
      

• Value molecules. If t, m, v are terms then the value molecule t[m -> v] is serialized as follows:

  	    <Atom><oid>t'</oid><slot>m' v'</slot></Atom>
  	  

  Here and elsewhere we use primes to represent recursive RuleML serialization. For instance, t', m', and v' denote RuleML serializations of t, m, and v, respectively. For instance, o[f(a,b) -> 3] would be represented by the following fragment:

  	    <Atom>
  	       <oid><Con>o</Con></oid>
  	       <slot>
  	          <Hterm><Con>f</Con><Con>a</Con><Con>b</Con></Hterm>
  	          <Con>3</Con>
  	       </slot>
  	    </Atom>
  	  

  The syntax t[m -> {v1,...,vk}] is also supported: the set-valued result is serialized using the Set tag:

  	    <Atom>
  	       <oid>t'</oid>
  	       <slot>
  	          m'
  	          <Set>v1',...,vk'</Set>
  	       </slot>
  	    </Atom>
  	  

• Boolean molecules. These molecules have the form t[m] where t and m are terms. They are serialized using singleton slot elements. For instance, mary[female] is represented as follows:

  	    <Atom>
  	       <oid><Con>mary</Con></oid>
  	       <slot>
  	          <Con>female</Con>
  	       </slot>
  	    </Atom>
  	  

• Class membership molecule. Class membership molecules of the form t:s are serialized using the InstanceOf element:

  	    <InstanceOf>t' s'</InstanceOf>
  	  

  where t' and s' represent RuleML serializations of t and s.

• Subclass molecule. The subclass molecules of the form t::s are represented using the SubclassOf element as follows:

  	    <SubclassOf>t' s'</SubclassOf>
  	  

  As before, t' and s' represent RuleML serializations of t and s, respectively.

• Signature molecule. Signature molecules of the form t[m => v] are represented using the Signature element, where the prime represents RuleML serialization of the corresponding term:

  	    <Signature><oid>t'</oid><slot>m' v'</slot></Signature>
  	  

• Boolean signature molecules. A Boolean signature molecule has the form t[=>m]. Its RuleML serialization uses singleton slot elements within a Signature element:

  	    <Signature><oid>t'</oid><slot>m'</slot></Signature>
  	  

• Cardinality constraints. Signature molecules can have associated cardinality constraints. Such molecules have the form

  t[s(t1,...,tn) {min : max} => v]

  In RuleML this becomes:

  	    <Signature>
  	       <oid>t'</oid>
  	       <slot mincard="min" maxcard="max">
  	          <Hterm><Con>s'</Con>t1'...tn'</Hterm>
  	          v'
  	       </slot>
  	    </Signature>
  	  

Nested molecules. Direct serialization of nested molecules is not currently supported. Instead, they must first be broken into conjunctions of non-nested molecules and then serialized.

Slot access and path expressions. Serialization of slot access uses the RuleML Get primitive. Serialization of path expressions is supported via the polyadic RuleML SlotProd element. For example, room.ceiling.color becomes the following:

        <Get>
           <oid><Con>room</Con></oid>
           <SlotProd><Con>ceiling</Con><Con>color</Con></SlotProd>
        </Get> 
      

3.4 Serialization of Reification

SWSL-Rules supports reification of F-logic molecules, formulas that can occur in the head or the body of a rule, and of the rules themselves. The only restriction is that explicit quantifiers cannot occur under the scope of the reification operator. The main idea behind RuleML serialization of such statements is that the corresponding serialized statement must be embedded within a Reify element.

To illustrate, consider the following molecule:

	a[b -> ${p(X[foo -> bar])}] 
      

Since the reified statement (p(X[foo -> bar]) is an Hterm, this tag becomes the child of the Reify element.

	<Hterm>
	   <oid><Con>a</Con></oid>
	   <slot>
	      <Con>b</Con>
	      <Reify>
	         <Hterm>
	            <op><Con>p</Con></op>
	            <Hterm>
	               <oid><Var>X</Var></oid>
	               <slot><Con>foo</Con><Con>bar</Con></slot>
	            </Hterm>
	         </Hterm>
	      </Reify>
	   </slot>
	</Hterm>
      

The following example illustrates serialization of a reified rule.

	john[believes -> ${p(?X) implies q(?X)}].
      

The corresponding serialization is shown below. Since the top-level tag of a rule is Implies, this tag becomes the child of the Reify element.

	<Hterm>
	   <oid>john</oid>
	   <slot>
	      <Con>believes</Con>
	      <Reify>
	         <Implies>
	            <body>
	               <Hterm>
	                  <op><Con>p</Con></op>
	                  <Var>X</Var>
	               </Hterm>
	            </body>
	            <head>
	               <Hterm>
	                  <op><Con>q</Con></op>
	                  <Var>X</Var>
	               </Hterm>
	            </head>
	         </Implies>
	      </Reify>
	   </slot>
	</Hterm>
      

4 Application Scenarios

In this part of the document we present three use cases that illustrate some of the more interesting features of SWSL-Rules. Section 4.1 focuses on the problem of Web service discovery and shows how services, user goals, mediators, and the discovery engine itself can be defined in SWSL-Rules. Section 4.2 presents use cases for policy specification in e-commerce and shows how these cases can be specified in SWSL-Rules. Finally, Section 4.3 uses SWSL-Rules to illustrate the need for non-monotonic inheritance and overriding in domain-specific service ontologies.

4.1 Service Discovery with SWSL-Rules

This example illustrates the use of SWSL-Rules for Web service discovery. The particular features of the language that this example relies on include frame-based representation, reification, and nonmonotonic Lloyd-Topor extensions. In addition, logical updates à la Transaction logic [Bonner98] are used in the discovery queries. Transaction Logic was mentioned in Section 3.15 as a possible extension for SWSL-Rules.

To make the example manageable, services are described only by their names and conditional effects. To discover a service, users must represent their goals using the goal ontology described below. These goals are described in terms of user requests, which represent formulas that the user wants to be true in the after-state of the service (i.e., the state that would result after the execution of the service).

User goals and services may be expressed in different ontologies and so mediators are needed to translate between those ontologies. This type of mediators is known as wgMediators [Bruijn05a]. In this example, we assume that each service advertises the mediators that can be used to talk to this service though the attribute mediators.

Ontologies

Geographical ontology. To begin, we assume the following simple geographic taxonomy, which is shared by user goals and services. It defines several regions and subregions, such as America, USA, Europe, Tyrol. Each region is viewed as a class of cities. For instance, Innsbruck is a city in Tyrol and 'Stony Brook' is a town in the New York State (NYState).

    USA::America.
    Germany::Europe.
    Austria::Europe.
    France::Europe.
    Tyrol::Austria.
    NewYorkState::USA.
    StonyBrook:NewYorkState.
    NewYork:NewYorkState.
    Innsbruck:Tyrol.
    Lienz:Tyrol.
    Vienna:Austria.
    Bonn:Germany.
    Frankfurt:Germany.
    Paris:France.
    Nancy:France.

    Europe:Region.
    America:Region.

    ?Reg:Region :- ?Reg1:Region and ?Reg::?Reg1.
    ?Loc:Location :- ?Reg:Region and ?Loc:?Reg.
  

To make it easier to specify what is a region and what is not, we use a rule (the penultimate statement above) to say that a subclasses of a region are also regions and, therefore, such subclasses do not need to be explicitly declared as regions. The last rule simply says that any object that is a member of a geographical region is a location.

Goal ontology. Services write their descriptions to conform to specific ontologies. Likewise, clients describe their goals in terms of goal ontologies. Here we will not describe these ontologies, but rather the forms of the inputs and outputs that the services expect to produce and the structure of the user goals. Furthermore, since users and service designers are unlikely to be skilled knowledge engineers, we assume that the inputs, the outputs, and the goals are fairly simple and that most of the intelligence lies in the mediators.

We assume that there is one ontology for goals and two for services. Consequently, there are two mediators: one translating between the goal ontology and the first service ontology, and the other between the goal ontology and the second service ontology.

The goal ontology looks as follows:

    Goal[requestId *=> Request,
         request   *=> TravelSearchQuery,
         result    *=> Service
    ].
  

The classes Request and Service will be specified explicitly by placing specific object Ids in them. The class TravelSearchQuery consists of the following search queries:

    searchTrip(?From,?To):TravelSearchQuery :- 
                  ?From:(Region or Location) and ?To:(Region or Location).
    searchCitipass(?Loc):TravelSearchQuery :- ?Loc:(Region or Location).

The meaning of the query searchTrip(?X,?Y) depends on whether the parameters are regions or just locations. For location-parameters, the query is assumed to fetch the services that serve those locations. For region-parameters, the query is assumed to find services that service every location in the region that is known to the knowledge base. For instance, searchTrip(Paris, Germany) is a request for travel services that can sell a ticket from Paris to any city in Germany. Similarly, searchCitipass(NewYork) is interpreted as a search for travel services that can sell city passes for New York and the request searchCitipass(USA) is looking for services that can sell city passes for every location in USA. The result attribute is provided by the ontology as a place where the discovery mechanism is supposed to put the results.

Domain-specific service ontologies. A service ontology is intended to represent the inputs and outputs of the service as well as the effects of the service. Since the inputs are not generally provided in the user goal (since the user is not expected to know anything about such inputs), the job of translating goal queries into the inputs to the services lies with the mediator.

Service ontology #1 is defined as follows:

  // Service input
  search(?requestId,?fromLocation,?toLocation):ProcessInput :-
		   ?requestId:Request and
                   ?fromLocation:Location and ?toLocation:Location.
  search(?requestId,?city):ProcessInput  :-
		   ?requestId:Request and ?city:Location.
  // Service output
  ItineraryInfo::ServiceOutput.
  PassInfo::ServiceOutput.
  ItineraryInfo[from*=>Location, to*=>Location].
  PassInfo[city*=>Location].
  itinerary(?reqNumber):ItineraryInfo :- ?reqNumber:Request.
  pass(?reqNumber):PassInfo :- ?reqNumber:Request.

Note that services expect locations as part of their input and they know nothing about regions. In contrast, as we have seen, user goals can have region-wide requests. It is one of the responsibilities of the mediators to bridge this mismatch.

Service ontology #2 is similar to ontology #1 except that it understands only requests for citipasses and the formats for the input and the output are slightly different.

  // Service input
  discover(?requestId,?city):ProcessInput  :-
		   ?requestId:Request and ?city:Location.
  // Service output
  ServiceOutput[location*=>Location].
  ?reqNumber:ServiceOutput :- ?reqNumber:Request.

Shared core ontology for services. In addition, we need a core ontology that is shared by everyone in order to provide a common ground for the service infrastructure. In this example, the core ontology is represented by a single class Service, which is declared as follows:

   prefix xsd = "http://www.w3.org/2001/XMLSchema".
   Service[
      name        *=> xsd#string,
      process     *=> Process[effect(ProcessInput) *=> Formula],
      mediators   *=> Mediator
   ].

Note that the definition of the class Service belongs to the core ontology and therefore it is shared by everybody. The method effect represents the conditional effect of the service. It takes an input to the service as a parameter and returns a set of rules that specify the effects of the service for that input. Formula is a predefined class. The attribute mediators indicates the mediators that the service advertises for anywho would want to talk to that service.

Note that the class ProcessInput belongs to the core ontology, but it's extension (the set of objects that are members of that class) is defined by domain-specific ontologies.

Examples of Concrete Services

We now present instances of concrete services.

// This service uses ontology #1, and mediator med1 bridges it to the goal ontology
serv1:Service[
   name -> "Schwartz Travel, Inc.",

   // Input must be a request for ticket from somewhere in Germany to somewhere
   // in Austria  OR  a request for a city pass for a city in Tyrol
   // Depending on the input, output is either an itinerary object with Id
   // itinerary(requestId) or a citipass object with Id
   // pass(requestId).
   process ->
       _#[effect(?Input) -> ${
	       (itinerary(?Req)[from->?From,to->?To] :-
			   Input = search(?Req, ?From:Germany, ?To:Austria))
	       and
	       (pass(?Req)[city->?City] :- ?Input=search(?Req,?City:Tyrol))
			     }],
    mediators -> med1
].

// Another ontology #1 service
serv2:Service[
    name -> "Mueller Travel, Inc.",
    process ->
	_#[effect(?Input)-> ${
		itinerary(?Req)[from->?From, to->?To] :-
		     ?Input = search(?Req,?From:(France or Germany),?To:Austria)
			      }],
    mediators -> med1
].

// An ontology #2 service
serv3:Service[
    name -> "France Citeseeing, Inc.",
    process ->
	_#[effect(?Input)-> ${
	         ?Req[location->?City] :- ?Input=discover(?Req,?City:France)
		               }],
    mediators -> med2
].

// Another ontology #2 service
serv4:Service[
    name -> "Province Travel",
    process ->
        _#[effect(?Input)-> ${
	       ?Req[location->?City] :-
			?Input = discover(?Req,?City:France) and ?City != Paris
			      }],
    mediators -> med2
].

User Goals

Next we show examples of user goals. Note that the value of the attribute result is initially the empty set. When the goal is posed to the discovery engine, this value will be changed to contain the result of the discovery.

goal1:Goal[
   requestId -> _#:Request,
   request   -> searchTrip(Bonn,Innsbruck),
   result    -> {}
].

// search for services that serve all cities in France and Austria
goal2:Goal[
   requestId -> _#:Request,
   request   -> searchTrip(France,Austria),
   result    -> {}
].

goal3:Goal[
   requestId -> _#:Request,
   request   -> searchCitipass(Frankfurt),
   result    -> {}
].

goal4:Goal[
   requestId -> _#:Request,
   request   -> searchCitipass(Innsbruck),
   result    -> {}
].

// services that can sell citipasses for every city in France
goal5:Goal[
   requestId -> _#:Request,
   request   -> searchCitipass(France),
   result    -> {}
].

Mediators

Each of the two mediators, med1 and med2, consists of several main clauses. The first clause in each mediator takes a user goal and translates it into input (to services) that is appropriate for the corresponding domain-specific service ontology.

The remaining clauses define the mediator's method getResult. This method is supposed to be invoked in the after-state of the service execution. It takes as parameters the user goal and the service (in whose after-state the method is invoked). Depending on the form of the goal's request, getResult poses a query that is appropriate for that request and the service ontology of the service. For instance, if the request is searchCitipass(?City:Location), i.e., finding services that can sell citipasses for a specific location, then the query appropriate for services that use ontology #1 is pass(?)[city->?City] and the query for ontology #2 is ?[location->?City]. Finally, if the query yields results, the mediator constructs output that can be used to return results to the user and this output is compliant with our goal ontology.

Each form of the input has two cases: one assumes that the parameters are locations (e.g., searchCitipass(?City:Location)) and the other that they are regions (e.g., searchCitipass(?City:Region)). Therefore, for each form of the input our mediators have two clauses. Since ontology #2 understands only one input, med2 uses only two clauses to define getResult. The mediator for ontology #1, med1, needs four clauses to cover both forms of the input.

Finally, we remark that the clauses that deal with region-based requests have to construct more sophisticated queries to be asked in the after-state of the services. In our example, we use nonmonotonic Lloyd-Topor extensions to simplify such queries.

// mediator for ontology #1
med1:Mediator.
med1[constructInput(?Goal)->?Input] :- 
	?Goal[requestId->?ReqId, request->?Query] and
        if ?Query = searchTrip(?From,?To)
        then ?Input = search(?ReqId,?From1,?To1)
        else if ?Query = searchCitipass(?City)
        then ?Input = search(?ReqId,?City1).

med1[getResult(?Goal,?Serv) -> ${?Goal[result->?Serv]}] :-
	?Goal[request->searchCitipass(?City:Location)] and
        pass(?)[city->?City].
med1[getResult(?Goal,?Serv) -> ${?Goal[result->?Serv]}] :-
	?Goal[request->searchCitipass(?Region:Region)] and
        forall ?City (?City:?Region ==> pass(?)[city->?City]).

med1[getResult(?Goal,?Serv) -> ${?Goal[result->?Serv]}] :-
	?Goal[request->searchTrip(?From:Location,?To:Location)] and
        itinerary(?)[from->?From, to->?To].
med1[getResult(?Goal,?Serv) -> and ?Result = ${?Goal[result->?Serv]}] :-
	?Goal[request->searchTrip(?From:Region,?To:Region)] and
	forall ?From,?To (?City1:?FromReg and ?City2:?ToReg
                          ==> itinerary(?)[from->?City1, to->?City2]).

// mediator for ontology #2
med2:Mediator.
med2[constructInput(?Goal)->?Input] :- 
	?Goal[requestId->?ReqId, request->?Query] and
        if ?Query = searchCitipass(?City)
        then ?Input = discover(?ReqId,?City1).

med2[getResult(?Goal,?Serv) -> ${?Goal[result->?Serv]}] :-
	?Goal[request->searchCitipass(?City:Location)] and
        ?[location->?City].
med2[getResult(?Goal,?Serv) -> ${?Goal[result->?Serv]}] :-
	?Goal[request->searchCitipass(?Region:Region)] and
        forall ?City (?City:?Region ==> ?[location->?City]).

The Discovery Engine

The final piece of the puzzle is the actual engine that performs service discovery. It relies on the features, borrowed from Transaction Logic [Bonner98], which are currently not in SWSL-Language, but are considered for future extensions. These features include modifications to the current state of the knowledge base and hypothetical execution of such modifications.

findService(?Goal) :-
	?Serv[mediators -> ?Mediator] and
        ?Mediator[constructInput(?Goal) -> ?Input] and
	?Serv.process[effect(?Input) -> ?Effects] and
        hypothetically(
	    insert{?Effects} and
            ?Mediator[getResult(?Goal,?Serv) -> ?Result]
        ) and
	insert{?Result}.

The findService transaction performs the following tasks:

1. For each service instance, s, it finds the mediator that the service advertises.
2. It then uses the mediator to construct the input for that service based on the user goal.
3. Using the input, it computes the effects that the service guarantees to be true in the after-state of the execution.

4. It then hypothetically does the following:

   1. It inserts the effects (which are rules in this case) into the knowledge base. This simulates the execution of the service s and temporarily creates the after-state of the service execution.
   2. Using the mediator, it checks whether the user goal is true in the after-state of the service s and then returns the result.

5. If the above hypothetical execution fails for a particular service, no result is returned and the subsequent insert operation is not executed. If the hypothetical execution succeeds, it means that the service s matches the goal. After the hypothetical execution, the state of the knowledge base returns to what was before the execution of the service, but the variable ?Result is now bound to a result, which is a formula of the form

    goal[result->s] 

   This is then inserted into the knowledge base. In this way, the set of answers to the goal is built as the value of the result attribute of the goal object.

For instance, if

 ?- findService(goal1). 

is executed then the following will become true:

 goal1[result -> {serv1,serv2}]

Similarly, executing

 ?- findService(goal2).

yields goal2[result -> serv2]. The third goal, goal3, matches none of the services listed above, so only goal3[result->{}] can be derived. Executing

 ?- findService(goal4).

yields goal4[result -> serv1].

A more interesting goal is goal5, because it requests citipasses for an entire region (France). Given the information available in our knowledge base, only serv3 should match. Note that serv4 does not match because it does not serve Paris, while the goal specifies only those services that can sell citipasses for every location in France.

4.2 Policy Rules for E-Commerce

In this subsection, we discuss in detail how SWSL-Rules can be used to represent several (fictional) examples of policies for e-commerce. Some of these examples are given directly in the remainder of this section, in full detail. These include:

price discounting example;
refunds example;
supply chain ordering lead time example;
creditworthiness example; and
credit card transaction authorization example.

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 service contract specification. Most of these detailed examples are rather brief, for the sake of expository simplicity. However, the example dealing with authorization of credit card transactions is significantly longer and more realistic.

Additional examples of policy rules are available that use the same fundamental knowledge representation as SWSL-Rules. [Grosof2004e] gives a long example of e-contracting policy rules that combines rules with ontologies and deals with exception handling / monitoring. The [Grosof2004f] tutorial gives a collection of use cases and examples, including those for semantic mediation. The SweetRules [Grosof2004f] downloadable includes a collection of examples.

Overall, the SWSL-Rules is especially well suited to represent available knowledge and desired patterns of reasoning for several of the SWS tasks, including:

• authorization policies (for security, access control, confidentiality, privacy, and other kinds of trust);
• contracts (partial or complete, proposed or finalized), e.g., terms and conditions, service provisions, or surrounding business process policies;
• monitoring of processes to recognize and handle exceptions or other dynamic conditions (e.g., monitoring of performance of contracts to detect and respond to violations of contract provisions such as late delivery or non-payment);
• advertising, discovery, and matchmaking (e.g., advertisements and requests for quotation or requests for proposals can be regarded as partial contract proposals);
• semantic mediation, especially translation mappings that mediate between different ontologies or contexts and thus between knowledge expressed in those different ontologies or contexts (e.g., to translate from the output of one service to the input expected by another service); and
• object-oriented ontologies that use default inheritance with priorities and/or cancellation (e.g., in the manner of the Process Handbook [Process Handbook, Bernstein2003, Grosof2004d]).

In particular, the capabilities of SWSL-Rules for logical nonmonotonicity (negation-as-failure and/or Courteous prioritized conflict handling) is used heavily in many use case scenarios for each of the above tasks and its associated kinds of knowledge.

Personalized Price Discounting in an E-Bookstore

Next, we give an example of a set of policy rules that specify personalized price discounting in an e-bookstore. These rules are useful in advertising, and also as part of a contract (proposed or final).

The policy rules specify that by default, a shopper gets no discount (i.e., gets a zero percent discount). However, there are some particular circumstances which do warrant a discount. Loyal purchasers get a five percent discount. Members of the Platinum Club get a ten percent discount. However, customers who have been late in making payments during the last year get no discount. Also there is a mutex (integrity constraint) rule which specifies that it is a contradiction to conclude two different values of the discount percentage for the same customer, i.e., that the discount percentage should be unique.

/* price discounting policy rules */

{ordinary}
giveDiscount(percent00,?Cust) :- shopper(?Cust).

{loyal}
giveDiscount(percent05,?Cust) :- shopper(?Cust) and loyalPurchaser(?Cust).

{platinum}
giveDiscount(percent10,?Cust) :- shopper(?Cust) and member(?Cust,platinumClub).

{slowPayer}
giveDiscount(percent00,?Cust) :- slowToPay(?Cust,last1year).

overrides(loyal,ordinary).

overrides(platinum,loyal).
overrides(platinum,ordinary).

overrides(slowPayer,loyal).
overrides(slowPayer,platinum).

!- giveDiscount(?X,?Cust) and giveDiscount(?Y,?Cust) | notEquals(?X,?Y).


/* some "case" facts about particular customers ann, cal, kim, and peg. */

shopper(ann).

shopper(cal).
loyalPurchaser(cal).

shopper(kim).
member(kim,platinumClub).

shopper(peg).
loyalPurchaser(peg).
slowToPay(peg,last1year).

The above premises (policy rules and case facts) together entail the following conclusions about the discount percentages for the particular customers Ann, Cal, Kim, and Peg.

/* the entailed discount percentages for the particular customers */

giveDiscount(percent00,ann).

giveDiscount(percent05,cal).

giveDiscount(percent10,kim).

giveDiscount(percent00,peg).

Refunds in an E-Retailer

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 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).

Ordering Lead Time in Supply Chain (B2B)

In B2B commerce, e.g., in supply chains (especially in manufacturing), sellers often specify how much lead time, i.e., minimum advance notice, is required when a buyer places or modifies a purchase order. Next, we give an example of a part supplier vendor's (here, Samsung supplying computer equipment) lead time policies as a set of rules. 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 first policy rule says "14 days lead time if the buyer is a preferred customer". This might be authored by the marketing part of the seller's organization. The second policy rule says "30 days lead time if the ordered item is a minor part". This might be authored by the financial accounting part of the seller's organization. The third policy rule says "2 days lead time if: the ordered item is backlogged at the vendor (i.e., the seller is having trouble fulfilling its overall set of existing orders), and the order is a modification to reduce the quantity of the item, and the buyer is a preferred customer". This might be authored by the operations part of the seller's organization. The third rule is given higher priority than the first rule, say, because operations' authority (about lead time) is greater than that of marketing. A mutex says that the lead time is unique per purchase order.

/* ordering lead time policy rules */

{leadTimeRule1}
orderModificationNotice(?Order,days14) :-
        preferredCustomerOf(?Buyer,?Seller) and purchaseOrder(?Order,?Buyer,?Seller).

{leadTimeRule2}
orderModificationNotice(?Order,days30) :-
        minorPart(?Order) and purchaseOrder(?Order,?Buyer,?Seller).

{leadTimeRule3}
orderModificationNotice(?Order,days2) :-
        preferredCustomerOf(?Buyer,?Seller) and orderModificationType(?Order,reduce) and
        orderItemIsInBacklog(?Order) and purchaseOrder(?Order,?Buyer,?Seller).

overrides(leadTimeRule3,leadTimeRule1).

!- orderModificationNotice(?Order,?X) and orderModificationNotice(?Order,?Y) | notEquals(?X,?Y).


/* some "case" facts about particular purchase orders */

purchaseOrder(po1234567,compUSA,samsung).
preferredCustomerOf(compUSA,samsung).

purchaseOrder(po5678901,microCenter,samsung).
preferredCustomerOf(microCenter,samsung).
orderModificationType(po5678901,reduce).
orderItemIsInBacklog(po5678901).

The above premises (policy rules and case facts) together entail the following conclusions about the ordering lead time for the particular purchase orders po1234567 and po5678901.

/* the entailed lead times for the particular purchase orders */

orderModificationNotice(po1234567,days14).

orderModificationNotice(po5678901,days2).

Creditworthiness using Credit Report and Fraud Alert Services

Policies about authorization, including creditworthiness and other kinds of trustworthiness to access information or perform transactions, are often naturally expressed in terms of necessary and sufficient conditions. Such conditions include: credentials, e.g., credit ratings or professional certifications; third-party recommendations; properties of a transaction in question, e.g., its size or mode of payment; and historical experience between the agents, e.g., familiarity or satisfaction.

Next, we give a simple example of policy rules of a merchant about creditworthiness (of customers) using a credit report service and a fraud alert service. These rules are useful for representing authorization policies, as part of contract negotiation, and in contract monitoring and exception handling (e.g., if the fraud alert arrives after contractual agreement has been reached).

The first policy rule says that, by default, the merchant deems a requester customer to be creditworthy if the requester has a good rating from a particular credit report service (CreditReportsRUs, a source trusted by the merchant). The second policy rule says that the merchant deems a requester to be not creditworthy if the requester has a bad rating from any fraud alert service that is recommended as expert by a particular security consultant (recommenderServiceD, again, a source trusted by the merchant). The second rule is given higher priority than the first rule. The merchant is called "self" (as is conventional in the security policy literature for the granting authority institution).

/* creditworthiness policy rules */

{credSelf}
honest(self,?Requester) :- creditRating(creditReportsRUs,?Requester,good).

{frauSelf}
neg honest(self,?Requester) :-
        creditRating(?BlackballService,?Requester,bad) and
        fraudExpert(recommenderServiceD,?BlackballService).

overrides(frauSelf,credSelf).

fraudExpert(recommenderServiceD,studentLoanAgency).


/* some "case" facts about particular requester customers */

creditRating(creditReportsRUs,sue,good).

creditRating(creditReportsRUs,joe,good).
creditRating(studentLoanAgency,joe,bad).

The above premises (policy rules and case facts) together entail the following conclusions about the creditworthiness of the particular requester customers Sue and Joe.

/* the entailed creditworthiness of the particular requester customers */

honest(self,sue).

neg honest(self,joe).

Credit Card Transaction Authorization by Merchant and Bank

Next, we give a longer and more realistic example of authorization in e-commerce: authorization by a merchant of credit card transactions requested by customers. In this example, the merchant ("eSellWow") merges the authorization policies of credit card issuer (called the "bank") with the merchant's own additional authorization policies. These rules are useful for specifying authorization policies, contracts, and exception handling.

/* Some terminological abbreviations:
CVC: Card Verification Code (the three or so numbers found on the back of a credit card)
"Bank": the credit card company that is the issuer of the credit card (e.g., Mastercard)
*/
/* Predicates' meaning:

transactionRequest: a credit card transaction requested by a customer
merchant: a merchant who is established to do credit card transactions
with the credit card company
ccInGoodStanding: credit card is in good standing with the credit card company that is
the issuer of the credit card
ccInfo: credit card info about the account and its status, that is on file with the bank
authorize: the credit card transaction is authorized
transactionExpirationDateOf: customer-supplied expiration date that is part of the transaction
transactionCardholderNameOf: customer-supplied cardholder name that is part of the transaction
transactionCVCOf: customer-supplied CVC that is part of the transaction
transactionCardholderAddressOf: customer-supplied cardholder billing address
that is part of the transaction
ccFraudRating: rating of a credit card by a fraud alerting/tracking service
fraudExpert: a service is a legitimate expert in fraud alerting/tracking
fraudRecommenderFor: trusted recommender of fraud experts
customerRating: the rating of customer based on the merchant's own/other experience

Built-in predicates (used):
notEquals
lessThan
*/


/* The following group of rules are policies of the bank,
then adopted/imported as a group/module by the merchant, in this case eSellWow. */

/* bankGoodStanding: Bank says by default the transaction is authorized if the card is in
good standing */
/* expiredCard: Bank says the transaction is disallowed if the card is expired. */
/* overLimit: Bank says the transaction is disallowed if the card is above its account limit. */
/* mismatchExpirationDate: Bank says the transaction is disallowed if the expiration date from
the customer or card in the transaction does not match what's on file for the card.
However, the expiration date may not be available as part of the transaction. */
/* mismatchCVC: Bank says the transaction is disallowed if the Card Verification Code
does not match what's on file for the card.
However, note that the CVC may not be available as part of the transaction. */
/* mismatchAddress: Bank says the transaction is disallowed if customer-supplied cardholder
billing address does not match what's on file for the card.
However, the customer-supplied cardholder billing address may not be available. */
/* mismatchName: Bank says the transaction is disallowed if customer-supplied cardholder
name does not match what's on file for the card.
However, the customer-supplied cardholder billing address may not be available. */
/* The expiredCard, overLimit, mismatchExpirationDate, mismatchCVC, mismatchAddress, and
mismatchName rules all have higher priority than bankGoodStanding. */

/* The following group of rules are additional policies of the merchant eSellWow,
which it adopted/imported from a vendor and consultant when setting up its e-store website */
/* merchantRespectBank: Merchant say a transaction is disallowed if the bank does. */
/* merchantTrustBank: Merchant says, by default, that a transaction is allowed if the bank does. */
/* fraudAlert: Merchant says transaction is disallowed if a trusted fraud tracking service
rates the fraud risk as high for the card. */
/* trustTRW: Merchant relies on recommenderServiceTRW for establishing such trust. */
/* badCustomer: Merchant says transaction is disallowed if its own/other experience indicates that the
customer is a bad customer to deal with. */
/* The fraudAlert and badCustomer rules both have higher priority than merchantTrustBank. */

/* The following are additional background fact rules, known to the merchant eSellWow and the bank. */
/* eSellWow is an established merchant for mastercard and visa. */

/* The following are additional background fact rules, known to the merchant eSellWow. */
/* recommenderServiceTRW recommends fraudscreen */



{bankGoodStanding}
authorize(?Bank,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInGoodStanding(?Bank,?CreditCardNumber).

{expiredCard}
neg authorize(?Bank,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        notEquals(?ExpiredFlag,"false").

{overLimit}
neg authorize(?Bank,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        lessThan(?AccountLimit,?Amount).

{mismatchExpirationDate}
neg authorize(?Bank,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        transactionExpirationDateOf(?TransactionID,?TransactionExpirationDate) and
        notEquals(?TransactionExpirationDate,?ExpirationDate).

{mismatchName}
neg authorize(?Bank,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        transactionCardholderNameOf(?TransactionID,?TransactionCardholderName) and
        notEquals(?TransactionCardholderName,?CardholderName).

{mismatchCVC}
neg authorize(?Bank,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        transactionCVCOf(?TransactionID,?TransactionCVC) and notEquals(?TransactionCVC,?CVC).

{mismatchAddress}
neg authorize(?Bank,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        transactionCardholderAddressOf(?TransactionID,?TransactionCardholderAddress),
        notEquals(?TransactionCardholderAddress,?CardholderAddress).

overrides(expiredCard,bankGoodStanding).
overrides(overLimit,bankGoodStanding).
overrides(mismatchExpirationDate,bankGoodStanding).

overrides(mismatchName,bankGoodStanding).
overrides(mismatchCVC,bankGoodStanding).
overrides(mismatchAddress,bankGoodStanding).

{merchantTrustBank}
authorize(?Merchant,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        authorize(?Bank,?TransactionID).

{merchantRespectBank}
neg authorize(?Merchant,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        neg authorize(?Bank,?TransactionID).

{fraudAlert}
neg authorize(?Merchant,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        fraudRecommenderFor(?Merchant,?recommenderService) and
        fraudExpert(?recommenderService,?FraudFirm) and
        ccFraudRiskRating(?FraudFirm,?CardholderName,high).

{badCustomer}
neg authorize(?Merchant,?TransactionID) :-
        transactionRequest(?TransactionID,?Merchant,?CreditCardNumber,?Amount) and
        issuer(?CreditCardNumber,?Bank) and merchant(?Merchant,?Bank) and
        ccInfo(?CreditCardNumber,?Bank,?CardholderName,?AccountLimit,
                ?ExpiredFlag,?ExpirationDate,?CardholderAddress,?CVC) and
        customerRating(?Merchant,?CardholderName,bad).

overrides(fraudAlert,merchantTrustBank).

overrides(badCustomer,merchantTrustBank).

fraudRecommenderFor(eSellWow,recommenderServiceTRW).

merchant(eSellWow,mastercard).

merchant(eSellWow,visa).

fraudExpert(recommenderServiceTRW,fraudscreen).


/* The following groups of "case" facts each specify a
particular case scenario of a requested customer transaction. */

/* Joe Goya has a card in good standing, unexpired, and
the transaction amount is below the account limit.
His customer rating is good.
Transaction expiration date, address, and CVC are unavailable, as
is fraud alert rating.
The policies thus imply that his transaction ought to be authorized
by the merchant as well as by the bank. */

/* Mary Freund has a card in good standing, unexpired, and
the transaction amount is below the account limit.
Her address matches, and her fraud report and customer rating are fine.
But the transaction CVC and address do not match the ones on file.
Thus the policies imply that the transaction on her card
ought to be disallowed by the merchant as well as the bank. */

/* Andy Lee has a card in good standing, unexpired,
and the transaction amount is under the account limit.
But his customer rating is bad.
Thus the policies imply that his transaction ought to be disallowed
by the merchant (regardless of whether the bank allows it). */

transactionRequest(trans1014,eSellWow,"999912345678",70).
issuer("999912345678",mastercard).
ccInfo("999912345678",mastercard,joeGoya,1100,"false","2007_08","43 Garden Drive, Cincinnati OH",702).
ccInGoodStanding(mastercard,"999912345678").
customerRating(eSellWow,joeGoya,good).

transactionRequest(trans2023,eSellWow,"999987654321",410).
issuer("999987654321",visa).
ccInfo("999987654321",visa,maryFreund,2400,"false","2008_02","325 Haskell Street, Seattle, WA",684).
ccInGoodStanding(visa,"999987654321").
ccFraudRiskRating(fraudscreen,maryFreund,low).
customerRating(eSellWow,maryFreund,excellent).
transactionCVCOf(trans2023,524).
transactionTransactionAddressOf(trans2023,"1493 Belair Place, Los Angeles, CA").

transactionRequest(trans3067,eSellWow,"999956781234",120).
issuer("999956781234",mastercard).
ccInfo("999956781234",mastercard,andyLee,900,"false","2006_05","1500 Seaview Boulevard, Daytona Beach, FL",837).
ccInGoodStanding(mastercard,"999956781234").
customerRating(eSellWow,andyLee,bad).

The above premises (policy rules and case facts) together entail the following conclusions about the authorization of the particular requested transactions by customers Joe Goya, Mary Freund, and Andy Lee. Notice that in the case of Andy Lee's, the merchant denies authorization even though the bank approves it, because of the merchant's own customer rating info and policies.

/* the entailed approval vs. denial by the bank, and by the merchant, of
authorization of the particular requested credit card transactions. */

authorize(mastercard, trans1014).
authorize(eSellWow, trans1014).

neg authorize(visa, trans2023).
neg authorize(eSellWow, trans2023).

authorize(mastercard, trans3067).
neg authorize(eSellWow, trans3067).

4.3 Using Defaults in Domain-Specific Service Ontologies

It is often necessary to represent domain-specific ontologies. An important and frequently-used flavor of domain-specific service ontologies uses frameworks of the kind found in object-oriented programming languages and in AI frame-based systems. In such frameworks, the values of a property P of a superclass are inherited by each of its subclasses. These subclasses are known as the specializations of the parent superclass. For example, the property P might be a data attribute or a method definition. This inheritance has default flavor: explicitly specified information about the property for the subclass overrides -- or cancels -- the inheritance. Such default inheritance (and, by extension, such an ontology) is logically nonmonotonic and cannot be represented in first-order logic. However, it can be represented in SWSL-Rules, which is object-oriented and includes inheritance as a basic feature.

To illustrate this point, we give an example of a service, Sell Product, which relies on such a domain-specific service ontology. The ontology describes a Sell Product business process and a some of its specializations. The form and domain of this ontology are similar to those found 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 knowledge -- for a number of SWS tasks, including:

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

In [Bernstein2003] we introduced an example about Sell Product. The example below is adapted from that. There  we give an approach to representing default inheritance about process ontologies in terms of Courteous LP. Another approach to representing default inheritance in a similar spirit is shown in [Yang02] who use LP with NAF but without Courteous, instead defining special constructs that extend the LP KR.
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:

  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. 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 6.1.

Figure 6.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."

Adding Exception Handling

Next, suppose that we need to extend the repertoire of selling services with a third process, "Sell electronically," which can be executed electronically.

Figure 6.2: The "Sell Product" service with three subclasses; the third subclass has an exception handler.

Figure 6.2 shows that the new process has an exception attached to the second subtask "Inform potential customers by email" in order to addresses the issue of unwanted email solicitations. The exception permits people to remove themselves from the mailing list by putting their addresses on the opt-out list.

Inheritance and overriding of the attributes from the parent class is modeled as before:

  SellElectronically::SellProduct[
           identifyCustomers *-> obtainByDataMining,
           informCustomers *-> informByEmail,
           obtainOrder *-> getOrderByEMail
  ].

The method informByEmail could be defined as follows:

  ?Product[informByEmail] :-
           ?Product[obtainByDataMining -> ?Email] and
           sendEmail(?Email).

One way to incorporate the opt-out exception to the general policy is by adding the premise naf optOutList(?Email) to the body of the above rule. However, this approach is not modular, since it requires modification of the existing rules (the method informByEmail may have already been defined). Even if it were acceptable to make this change now, further changes to the opt-out policy might require additional changes to the existing rules. A more scalable approach is to express the above opt-out exception using constraints, and this is where the mutex primitive of the Courteous layer of SWSL-Rules comes in:

 !- sendEmail(?Email) and optOut(?Email).

This constraint says that sendEmail(?Email) and optOut(?Email) cannot be true together for the same individual. For people who put their names on the opt-out list, optOut(?Email) will be true and, therefore, sendEmail(?Email) will be false. On the other hand, for an email address, e, that is not found on the opt-out list, the corresponding predicate predicate optOut(e) will not be provable and, by negation-as-failure, optOut(e) will be assumed false. Therefore, sending email to that address will not be blocked.

5 Glossary

QName

Qualified name. A pair (URI, local-name). The URI represents a namespace and local-name represents a name used in an XML document, such as a tag name or an attribute name. In XML, QNames are syntactically represented as prefix:local-name, where prefix is a macro that expands into a concrete URI. See Namespaces in XML for more details.

sQName

Serialized QName. A serialized QName is a shorthand representation of a URI. It is a macro that expands into a full-blown URI. sQNames are not QNames: the former are URIs, while the latter are pairs (URI, local-name). Serialized QNames were originally introduced in RDF as a notation for shortening URI representation. Unfortunately, RDF introduced confusion by adopting the term QName for something that is different from QNames used in XML. To add to the confusion, RDF uses the syntax for sQNames that is identical to XML's syntax for QNames. SWSL-Rules distinguishes between QNames and sQNames, and uses the syntax prefix#local-name for the latter. Such an sQName expands into a full URI by concatenating the value of prefix with local-name.

URI

Universal Resource Identifier. A symbol used to locate resources on the Web. URIs are defined by IETF. See Uniform Resource Identifiers (URI): Generic Syntax for more details. Within the IETF standards the notion of URI is an extension and refinement of the notions of Uniform Resource Locator (URL) and Relative Uniform Resource Locators.

6 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.

[Bonner93]

Database Programming in Transaction Logic. A.J. Bonner, M. Kifer, M. Consens. Proceedings of the 4-th Intl.~Workshop on Database Programming Languages, C. Beeri, A. Ohori and D.E. Shasha (eds.), 1993. In Springer-Verlag Workshops in Computing Series, Feb. 1994: 309-337.

[Bonner98]

A Logic for Programming Database Transactions. A.J. Bonner, M. Kifer. Logics for Databases and Information Systems, J. Chomicki and G. Saake (eds.). Kluwer Academic Publishers, 1998: 117-166.

[Bruijn05a]

Web Service Modeling Ontology (WSMO). J. de Bruijn, C. Bussler, J. Domingue, D. Fensel, M. Hepp, M. Kifer, B. König-Ries, J. Kopecky, R. Lara, E. Oren, A. Polleres, J. Scicluna, M. Stollberg. DERI Technical Report, 2005.

[Bruijn05b]

The Web Service Modeling Language WSML. J. de Bruijn, Holger Lausen, Reto Krummenacher, Axel Polleres, Livia Predoiu, Michael Kifer, Dieter Fensel. DERI Technical Report, 2005.

[Chang73]

Symbolic Logic and Mechanical Theorem Proving. C.L. Chang and R.C.T. Lee. Academic Press, 1973.

[Chen93]

HiLog: A Foundation for Higher-Order Logic Programming. W. Chen, M. Kifer, D.S. Warren. Journal of Logic Programming, 15:3, February 1993, 187-230.

[Chimenti89]

Towards an Open Architecture for LDL. D. Chimeti, R. Gamboa, R. Krishnamurthy, VLDB Conference, 1989: 195-203.

[Frohn94]

Access to Objects by Path Expressions and Rules. J. Frohn, G. Lausen, H. Uphoff. Intl. Conference on Very Large Databases, 1994, pp. 273-284.

[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.

[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.

[Hayes04]

RDF Model Theory. Hayes, P. W3C, February 2004.

[Helland05]

Data on the Outside Versus Data on the Inside. P. Helland. Proc. 2005 Conf. on Innovative Database Research (CIDR), January, 2005.

[Kifer95]

Logical Foundations of Object-Oriented and Frame-Based Languages, M. Kifer, G. Lausen, J. Wu. Journal of ACM, 1995, 42, 741-843.

[Kifer04]

A Logical Framework for Web Service Discovery, M. Kifer, R. Lara, A. Polleres, C. Zhao. Semantic Web Services Workshop, November 2004, Hiroshima, Japan.

[Klein00a]

Towards a Systematic Repository of Knowledge About Managing Collaborative Design Conflicts. Klein, Mark. 2000.  Proceedings of the Conference on Artificial Intelligence in Design. Boston, MA, USA.

[Klein00b]

A Knowledge-Based Approach to Handling Exceptions in Workflow Systems. Klein, Mark, and C. Dellarocas. 2000.  Computer Supported Cooperative Work: The Journal of Collaborative Computing 9:399-412.

[Lloyd87]

Foundations of logic programming (second, extended edition). J. W. Lloyd. Springer series in symbolic computation. Springer-Verlag, New York, 1987.

[Lindenstrauss97]

Automatic Termination Analysis of Logic Programs. N. Lindenstrauss and Y. Sagiv. International Conference on Logic Programming (ICLP), 1997.

[Maier81]

Incorporating Computed Relations in Relational Databases. D. Maier, D.S. Warren. SIGMOD Conference, 1981: 176-187.

[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.

[Ontobroker]

Ontobroker 3.8. Ontoprise, GmbH.

[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]

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

[Perlis85]

Languages with Self-Reference I: Foundations. D. Perlis. Artificial Intelligence, 25, 1985, 301-322.

[Preist04]

A Conceptual Architecture for Semantic Web Services, C. Preist, 1993. In Proceedings of Third International Semantic Web Conference, Nov. 2004: 395-409.

[SPARQL]

SPARQL Query Language for RDF. Eric Prud'hommeaux, Andy Seaborne (eds.). W3C Working Draft, 2004.

[SWRL]

SWRL: A Semantic Web Rule Language Combining OWL and RuleML. I. Horrocks, P.F. Patel-Schneider, H. Boley, S. Tabet, B. Grosof, M. Dean. W3C Report, 2004.

[VanGelder91]

The Well-Founded Semantics for General Logic Programs. A. Van Gelder, K.A. Ross, J.S. Schlipf. Journal of ACM, 38:3, 1991, 620-650.

[XQuery 1.0]

XQuery 1.0: An XML Query Language. S. Boag, D. Chamberlin, et al, editors. W3C Working Draft 04 April 2005.

[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.

[Yang03]

Reasoning about Anonymous Resources and Meta Statements on the Semantic Web. G. Yang, M. Kifer. Journal on Data Semantics, Lecture Notes in Computer Science 2800, Springer Verlag, September 2003, 69-98.

[Yang04]

FLORA-2 User's Manual. G. Yang, M. Kifer, C. Zhao, V. Chowdhary. 2004.