A Software Framework For Matchmaking Based on Semantic Web Technology

Lei Li
Department of Computer Science
University of Manchester
Manchester, United Kingdom
lil@cs.man.ac.uk

Ian Horrocks
Department of Computer Science
University of Manchester
Manchester, United Kingdom
horrocks@cs.man.ac.uk

Abstract:

An important objective of the Semantic Web is to make Electronic Commerce interactions more flexible and automated. To achieve this, standardization of ontologies, message content and message protocols will be necessary.

In this paper we investigate how Semantic and Web Services technologies can be used to support service advertisement and discovery in e-commerce. In particular, we describe the design and implementation of a service matchmaking prototype which uses a DAML-S based ontology and a Description Logic reasoner to compare ontology based service descriptions. We also present the results of initial experiments testing the performance of this prototype implementation in a realistic agent based e-commerce scenario.

Categories and Subject Descriptors

General Terms

Keywords

1 Introduction

The Semantic Web requires that data be not only machine readable (just like the Web nowadays does), it also wants the data to be machine understandable. To quote Tim Berners-Lee, the director of the World Wide Web consortium (W3C), and prime architect of the Semantic Web:

With a Semantic Web, it will be easy to realise a whole range of tools and applications that are difficult to handle in the framework of the current web. Examples include knowledge-repositories, search agents, information parsers, etc. Moreover, the developers of end user applications will not need to worry about how to interpret the information found on the Web, as ontologies will be used to provide vocabulary with explicitly defined and machine understandable meaning [14]. One important Semantic Web application area is e-commerce. In particular, a great deal of attention has been focused on semantic web services, the aim of which is to describe and implement web services so as to make them more accessible to automated agents. Here, ontologies can be used to describe services so that agents (both human and automated) can advertise and discover services according to a semantic specification of functionality (as well as other parameters such as cost, security, etc.) [23].

As a first step in realising the Semantic Web, new standards for defining and using ontologies are already being developed. RDF, which is being developed by the W3C RDF Core working group, is a web markup language that provides basic ontological primitives [5]; DAML+OIL is an ontology language that extends RDF with a much richer set of primitives (e.g., boolean operators and cardinality constraints), and which is now the basis for the W3C Web Ontology Language working group's development of the OWL ontology language standard [7, 6].

Moreover, if applications are to exchange semantic information, they will need to use common ontologies. One such ontology (written in DAML+OIL), which has been designed for the purpose of describing web services, is the DAML-S ontology [1]. In this paper, we present a case study of an e-commerce application in which the DAML-S service ontology is used to provide the vocabulary for service descriptions. These descriptions are used in a matchmaking prototype, i.e., a repository where agents can advertise and search for services that match some semantic description. We used JADE [13] as the agent platform for our prototype and we used the Racer DL reasoner in order to compute semantic matches between service advertisements and service requests. We illustrate some difficulties both in the application of the DAML-S ontology and in the use of the DL reasoner, and show how these were overcome in the prototype implementation. Finally, we carry out a performance analysis using the prototype in order to discover if the approach is likely to be feasible in large scale web applications.

2 Background

In this section we will give an overview of Semantic Web languages and technologies that are relevant to the prototype implementation.

2.1 Ontology Languages

As we have already mentioned, ontologies play a key role in the Semantic Web by providing vocabularies that can be used by applications in order to understand shared information.

DAML+OIL is an ontology language that has been designed specifically to be used in the Semantic Web. DAML+OIL is the result of merging two ontologies languages: OIL and DAML. OIL integrates the features from Frame-based systems and Description logics (DLs), and has an RDF based syntax; DAML is more tightly integrated with RDF, enriching it with a larger set of ontological primitives [9].

Because DAML+OIL is based on a Description Logic, we can use a DL reasoner to compare (semantically) descriptions written in DAML+OIL. We believe that this provides a powerful framework for defining and comparing e-commerce service descriptions. In Section 3 we will discuss in more detail DLs in general and DAML+OIL in particular.

2.2 Service Description Languages

2.2.1 WSDL

WSDL (Web Services Description Language) is an XML format for describing network services in abstract terms derived from the concrete data formats and protocols used for implementation [26].

As communication protocols and message formats are standardized in the web community, it becomes increasingly possible and important to be able to describe the communications in some structured way. WSDL addresses this need by defining an XML grammar for describing network services as collections of communication endpoints capable of exchanging messages. WSDL service definitions provide documentation for distributed systems and serve as a recipe for automating the details involved in application communications.

However, WSDL does not support semantic description of services. For example, it does not support the definition of logical constraints between its input and output parameters although it has the concept of input and output types as defined by XSD.

2.2.2 UDDI

Another emerging XML based standard for web service description is UDDI (Universal Description, Discovery and Integration) [24]. It enables a business to (i) describe its business and its services, (ii) discover other businesses that offer desired services, and (iii) integrate with these other businesses by providing a registry of businesses and web services.

UDDI describes businesses by their physical attributes such as name, address and the services that they provide. In addition, UDDI descriptions are augmented by a set of attributes, called tModels, which describe additional features such as the classification of services within taxonomies such as NAICS (North American Industry Classification System).

However, because UDDI does not represent service capabilities, the tModels they use only provide a tagging mechanism, and the search performed is only done by string matching on some fields they have defined. Thus, it is of no use for locating services on the basis of a semantic specification of their functionality.

2.2.3 DAML-S

DAML-S supplies Web service providers with a core set of markup language constructs for describing the properties and capabilities of their Web services in unambiguous, computer-interpretable form. DAML-S markup of Web services is intended to facilitate the automation of Web service tasks including automated Web service discovery, execution, interoperation, composition and execution monitoring [1].

In DAML-S, service descriptions are structured into three essential types of knowledge: a ServiceProfile, a ServiceModel (which describes the ServiceProfile), and a ServiceGrounding. In a matchmaking process, the ServiceProfile is typically required, since it provides the information needed for an agent to discover a service that meets its requirements.

In [18], Paolucci et al. have described some experiments designed to prove that DAML-S and its Service Profile can take up the challenge of representing the functionalities of web services.

2.3 Matchmaking Systems

2.3.1 InfoSleuth

InfoSleuth [16, 15], an agent-based information discovery and retrieval system, adopts ``broker agents'' to perform the syntactic and semantic matchmaking.

The broker agent matches agents that require services with other agents with agents that can provide those services. By maintaining a repository containing up-to-date information about the operational agents and their services, the broker enables the querying agent to locate all available agents that provide appropriate services.

Syntactic brokering is the process of matching requests to agents on the basis of the syntax of the incoming messages which wrap the requests; semantic brokering is the process of matching requests to agents on the basis of the requested agent capabilities or services, with the agent capabilities and services being described in a common shared ontology of attributes and constraints. This single domain-specific ontology is a shared vocabulary that all agents can use to specify advertisements and requests to the broker.

In InfoSleuth, the service capability information is written in LDL++ [27], a logical deduction language. Agents use a set of LDL++ deductive rules to support inferences about whether an expression of requirements matches a set of advertised capabilities. In contrast, we prefer to adopt a more standardized service description language in our work.

2.3.2 RETSINA/LARK

Sycara et al. have developed a multiagent infrastructure named RETSINA (Reusable Task Structure-based Intelligent Network Agents) [21, 20,19]. Mediation in this system also relies on service matchmaking, although their specification of capability and service descriptions is different from ours.

They distinguished three general agent categories in Cyberspace: service provider, service requester, and middle agent. To describe these agents' capabilities in the matchmaking process, they have defined and implemented an ACDL (Agent Capability Description Language), called Larks (Language for Advertisement and Request for Knowledge Sharing). Larks offers the option to use application domain knowledge in any advertisement or request by using a local ontology, written in a specific concept language ITL, to describing the meaning in a Larks specification.

As with InfoSleuth, our methodology differs from this system in the aspects of service description language, agent platform and matching engine. Moreover, in our approach we want to be sure that the service description language also lends itself to the negotiation process,¹ i.e., the same service description language should be applicable to the negotiation stage.

3 DL and DAML+OIL

The use of Description Logics and DAML+OIL are central to our approach. Some details of the two formalisms will therefore be helpful in understanding the remainder of the paper.

3.1 Description Logic

Description Logics are a well-known family of knowledge representation formalisms. They are based on the notion of concepts (unary predicates, classes) and roles (binary relations), and are mainly characterized by constructors that allow complex concepts and roles to be built from atomic ones [11]. A DL reasoner can check whether two concepts subsume each other [8]. In the following sections, we will use DL notations to express our design. Hence it will be useful to give an overview of DL languages and notations.

A detailed discussion of DLs is, however, beyond the scope of this paper, and the interested reader is referred to [2] for further details.

3.1.1 Description logics syntax

Elementary descriptions are atomic concepts and atomic roles. Complex descriptions can be built from them inductively with concept constructors. In the following, we will use abstract notation. We use the letters A and B for atomic concepts, the letter R for atomic roles, and the letters C and D for concept descriptions. Description languages are distinguished by the constructors they provide, the language $\mathcal{AL}$ is a minimal language that is of practical interest. Concept descriptions in $\mathcal{AL}$ are formed according to the following syntax rule [2]:

$\displaystyle C,D$	$\displaystyle \rightarrow$	$\displaystyle A \mid \ \ (atomic \ concept)$
		$\displaystyle \top \mid \ \ (universal \ concept)$
		$\displaystyle \perp \mid \ \ (bottom \ concept)$
		$\displaystyle \neg A \mid \ \ (atomic \ negation)$
		$\displaystyle C \sqcap D \mid \ \ (intersection)$
		$\displaystyle \forall R.C \mid \ \ (value \ restriction)$
		$\displaystyle \exists R.\top \ \ (limited \ existential \ quantification)$

To give examples of what can be expressed in $\mathcal{AL}$ , we suppose that Person and Female are atomic concepts. Then $Person \sqcap Female$ and $Person \sqcap \neg Female$ are $\mathcal{AL}$ -concepts describing, intuitively, those persons that are female, and those that are not female. If, in addition, we suppose that hasChild is an atomic role, we can form the concepts $Person \sqcap \exists hasChild.\top$ and $Person \sqcap \forall hasChild.Female$ , denoting those persons that have a child, and those persons all of whose children are female. Using the bottom concept ( $\bot$ ), we can also describe those persons without a child by the concept $Person \sqcap \forall hasChild.\perp$ [2].

This basic $\mathcal{AL}$ -language does not fulfil the requirements of our investigation as we need to be able to reason with DAML+OIL descriptions, which include, e.g., cardinality restrictions on roles, and datatypes (integers, strings, etc.). We therefore use the DL $\mathcal{SHIQ}({\mathbf D})$ , whose expressive power is (almost) equivalent to that of DAML+OIL [12, 10,7]. This language consists of the basic $\mathcal{AL}$ -language plus the negation of arbitrary concepts, (qualified) cardinality restrictions, role hierarchies, inverse roles, transitive roles and datatypes (a restricted form of DL concrete domains). A detailed discussion of these and other DL constructors can be found in [2].

The increased expressive power of the language is manifested in a range of additional constructors, including:

	$\displaystyle \exists R.C$	$\displaystyle \ (full \ existential \ quantification)$
	$\displaystyle \neg C$	$\displaystyle \ (negation \ of \ arbitrary \ concepts)$
	$\displaystyle \leq n \ R$	$\displaystyle \ (atmost \ cardinality \ restriction)$
	$\displaystyle \geq n \ R$	$\displaystyle \ (atleast \ cardinality \ restriction)$
	$\displaystyle = n \ R$	$\displaystyle \ (exactly \ cardinality \ restriction)$
	$\displaystyle \leq n \ R.C$	$\displaystyle \ (qualified \ atmost \ cardinality \ restriction)$
	$\displaystyle \geq n \ R.C$	$\displaystyle \ (qualified \ atleast \ cardinality \ restriction)$
	$\displaystyle = n \ R.C$	$\displaystyle \ (qualified \ exactly \ cardinality \ restriction)$
	$\displaystyle \leq_n \ \textstyle{R}$	$\displaystyle \ (concrete \ domain \ max \ restriction)$
	$\displaystyle \geq_n \ \textstyle{R}$	$\displaystyle \ (concrete \ domain \ min \ restriction)$
	$\displaystyle =_n \ \textstyle{R}$	$\displaystyle \ (concrete \ domain \ exactly \ restriction)$

As examples of what can be expressed with these new constructors, if $Woman \equiv Person \sqcap Female$ , then $Woman \sqcap \exists hasChild.Person$ intuitively denotes ``mothers''; $\neg Woman$ denotes individuals that are not women; $Mother \sqcap$ $\mbox{$\geq$}$ $\, 3\, hasChild$ denotes a mother with more than three children; $Mother \sqcap$ $\mbox{$=$}$ $\, 3\, hasChild.female$ denotes a mother with exactly three daughters; $Person \sqcap$ $\mbox{$\geq$}$ $_{18}\, \textstyle{hasAge}$ denotes ``adults'', i.e., a person whose age is greater than 18.

3.1.2 DL Semantics

In order to define a formal semantics of DLs, we consider interpretations $\mathcal{I}$ that consist of a non-empty set $\Delta^\mathcal{I}$ (the domain of the interpretation) and an interpretation function, which assigns to every atomic concept A a set $A^\mathcal{I} \subseteq \Delta^\mathcal{I}$ and to every atomic role R a binary relation $R^\mathcal{I} \subseteq \Delta^\mathcal{I} \times \Delta^\mathcal{I}$ . The interpretation of complex concepts are built up from the interpretation of primitive concepts, e.g., $(C \sqcap D)^\mathcal{I} = C^\mathcal{I} \cap D^\mathcal{I}$ and $(\exists R.\top)^\mathcal{I} = \{a \in \Delta^\mathcal{I} \mid \exists b.(a,b) \in R^\mathcal{I}\}$ .

We say that two concepts C, D are equivalent, and write $C \equiv D$ , iff $C^\mathcal{I} = D^\mathcal{I}$ for all interpretations $\mathcal{I}$ . For instance, going back to the semantics of concepts, one can easily verify that $\forall hasChild.Female \sqcap \forall hasChild.Student$ and $\forall hasChild.(Female \sqcap Student)$ are equivalent. A complete interpretation function for concept description can be found in [2].

3.1.3 Terminologies

In DLs, a knowledge base (equivalent to an ontology) consists of a set of terminological axioms that assert how concepts or roles are related to each other. In the most general case, terminological axioms have the form:

where C, D are concepts (and R, S are roles). The first kind of axiom is called an inclusion, while the second one is called an equivalence.

An equivalence whose left-hand side is an atomic concept is sometimes called a definition, and can be thought of as introducing symbolic names for complex descriptions [2].²

3.2 DAML+OIL

DAML+OIL is a DL based Web ontology language. As with any other DL, DAML+OIL describes the structure of a domain in terms of classes (concepts in DL) and properties (roles in DL). DAML+OIL is in fact based on the $\mathcal{SHIQ}({\mathbf D})$ DL, and provides an almost equivalent set of class constructors and class and property axioms (DAML+OIL extends $\mathcal{SHIQ}({\mathbf D})$ with the oneOf constructor for defining classes extensionally). Like $\mathcal{SHIQ}({\mathbf D})$ , DAML+OIL also supports the use of datatypes and data values in class description, with DAML+OIL relying on XML Schema datatypes for this purpose. For a complete description of DAML+OIL, the interested reader is referred to [25].

4 The DAML-S Service Ontology

We have chosen to use the DAML-S web service ontology as the basis to represent e-commerce constructs like advertisements and service queries.

DAML-S [1] is a DAML+OIL service description ontology. Through the tight connection with DAML+OIL, DAML-S supports our need for the semantic representation of services. DAML+OIL allows for subsumption reasoning on concept taxonomies, it allows for the definition of relations between concepts and it makes it possible to apply property restrictions on the parameters of service concepts. This means that we can use DAML-S to define the entities in e-commerce life-cycles, such as advertisements and requests, and implement the matchmaking functionalities by using a DL reasoner to compute the subsumption relationships of those concepts.

DAML-S aims at facilitating discovery, execution, interoperation, composition and execution monitoring of web services. It defines the notions of a Service Profile (what the service does), a Service Model (how the service works) and a Service Grounding (how to use the service).

A service profile describes who provides the service, the expected quality of the service and the transformation produced by the service in terms of what it expects in order to run correctly and what results it produces. Specifically, it specifies the preconditions that have to be satisfied to use the service effectively; the inputs that the service expects; the expected effects that result from the execution of the service and the outputs returned [1]. Since the behavioural aspects of a service profile are outside the scope of this work, we will only interest ourselves in the fact that a service can be represented by inputs and outputs properties (which represent the functional attributes of a service).

Through our investigation, we have concluded that the ability of DAML-S to describe the semantics of web services meets the requirements of our matchmaking framework:

5 Service Description

In this section, we explain how we use DAML+OIL and the DAML-S ontology to capture the various descriptions that are used in the e-commerce life-cycle.

5.1 A Sample Ontology

Service description ontologies will have an important role to play in our work, so we have designed a domain-specific sample ontology about the sales of computers in order to achieve agreement at the semantic level between various parties. In our prototype, we used the OilEd [17] ontology editor to build DAML+OIL ontologies. For the purpose of clarity and compactness, however, in this paper we will use the DL notions in place of the DAML+OIL syntax.

In our ontology, we use the DAML-S ServiceProfile class as a common superclass for concept Advertisement, Query, Template and Proposal, so they can be expressed as:

$\displaystyle ServiceProfile$	$\displaystyle \sqsubseteq$	$\displaystyle \top$
$\displaystyle Advertisement$	$\displaystyle \sqsubseteq$	$\displaystyle ServiceProfile$
$\displaystyle Query$	$\displaystyle \sqsubseteq$	$\displaystyle ServiceProfile$
$\displaystyle Template$	$\displaystyle \sqsubseteq$	$\displaystyle ServiceProfile$
$\displaystyle Proposal$	$\displaystyle \sqsubseteq$	$\displaystyle ServiceProfile$

We also defined two kinds of services in this ontology: Sales and Delivery. Sales describes the sale of an item of EEquipment through constraints on the object properties and datatype properties such as the unit price. Delivery describes the structure of delivery information by specifying, e.g., that there must be exactly one DeliveryLocation and exactly one DeliveryDate.

In accordance with the DAML-S 0.6 specification, in Sales, we also include the providing and requesting Actors as the values of providedBy and requestedBy properties. By doing so, we allow the advertiser and the requester to specify who they are and restrict who they would like to do business with.

$\displaystyle Sales$	$\displaystyle \sqsubseteq$	$\displaystyle (= 1 \: providedBy.Actor) \sqcap$
		$\displaystyle (= 1 \: requestedBy.Actor) \sqcap$
		$\displaystyle (= 1 \: item.EEquipment) \sqcap$
		$\displaystyle (= 1 \: hasQuantity.positiveInteger) \sqcap$
		$\displaystyle (= 1 \: hasUnitPrice.nonNegInteger) \sqcap$
		$\displaystyle (= 1 \: canDeliver.Delivery)$

$\displaystyle Delivery$	$\displaystyle \sqsubseteq$	$\displaystyle (= 1 \: location.DeliveryLocation) \sqcap$
		$\displaystyle (= 1 \: date.DeliveryDate)$

$\displaystyle Actor$	$\displaystyle \sqsubseteq$	$\displaystyle (= 1 \: hasName.ActorName) \sqcap$
		$\displaystyle (= 1 \: hasCreditLevel.Integer)$

To express the concept computer we used in this example, a class PC is defined as a subclass of EEquipment, and must have several properties, like hasProcessor and memorySize.

$\displaystyle PC$	$\displaystyle \sqsubseteq$	$\displaystyle EEquipment \sqcap$
		$\displaystyle (= 1 \: hasProcessor.Processor) \sqcap$
		$\displaystyle (= 1 \: memorySize.positiveInteger)$
$\displaystyle Processor$	$\displaystyle \equiv$	$\displaystyle PentiumIII \sqcup Pentium4 \sqcup Athlon$

As noted in Section 4, the service is represented by input and output properties of the profile. The input property specifies the information that the service requires to proceed with the computation.

For example, our pc-selling service could require information like unit price and quantity as the inputs to sell. The outputs specify what is the result of the operation of the service. In the pc-selling case the output could be a item description that acknowledges the sale.

In our work, we divide these restriction properties into inputs and outputs according to the context in which they are used³. In particular, inputs are used by buyers and sellers to describe business constraints (e.g., unit quantity, unit price and delivery information), while outputs are used to describe the product itself.

$\displaystyle inputs$	$\displaystyle \sqsubseteq$	$\displaystyle parameter$
$\displaystyle outputs$	$\displaystyle \sqsubseteq$	$\displaystyle parameter$

$\displaystyle hasQuantity$	$\displaystyle \sqsubseteq$	$\displaystyle inputs$
$\displaystyle hasUnitPrice$	$\displaystyle \sqsubseteq$	$\displaystyle inputs$
$\displaystyle canDeliver$	$\displaystyle \sqsubseteq$	$\displaystyle inputs$

$\displaystyle item$	$\displaystyle \sqsubseteq$	$\displaystyle outputs$

These simple constructs allowed us to express the concepts we needed in this context, but arbitrarily complex DAML+OIL constructs can be used if required. The next several sections will show the examples we used in our matchmaking process.

5.2 Advertisement

Here we show an example of an advertisement. Suppose that we want to specify the concept of an advertisement by which the Actor would like to sell some PCs. In particular, there are some restrictions on the Sales and the Delivery such as the following:

$\displaystyle Advert1$	$\displaystyle \equiv$	$\displaystyle ServiceProfile \sqcap$
		$\displaystyle (Sales \sqcap$
		$\displaystyle \forall providedBy.(Actor \sqcap \forall hasName.Georgia) \sqcap$
		$\displaystyle \forall requestedBy.(Actor \ \sqcap \geq_{5} \ \textstyle{hasCreditLevel}) \sqcap$
		$\displaystyle \forall item.(PC \ \sqcap \geq_{128} \ \textstyle{memorySize}) \sqcap$
		$\displaystyle \geq_{700} \ \textstyle{hasUnitPrice} \sqcap$
		$\displaystyle \leq_{200} \ \textstyle{hasQuantity} \sqcap$
		$\displaystyle \forall delivery.(Delivery \sqcap$
		$\displaystyle \leq_{20020915} \ \textstyle{date} \sqcap \forall location.Bristol))$

Note that, in DAML+OIL, the way to express a concept like ``has unit price more than 700'' is to define a new datatype ``more700'' and describe it like `` $\forall \ hasUnitPrice.more700$ ''. However, for the purpose of achieving concept reasoning with datatypes using the Racer reasoner, we have used Racer syntax to express this kind of concept, e.g., `` $(\geq_{700}\, \textstyle{hasUnitPrice})$ ''.

In addition, intuitively, an advertisement should be an instance instead of a concept, i.e., it looks more reasonable to express it as $Advert1 \in ServiceProfile \sqcap \cdots$ . Because TBox reasoning is much more effective then ABox reasoning, what we did is to express the instance advertisement as a special concept; in contexts such as our e-commerce application, where individuals are not related to each other via properties, this does not lead to any loss of inferential power. This issue is, however, beyond the scope of this paper, and the interested reader is referred to [22].

5.3 Query

Similarly to the advertisement, we can define a query by which the Actor would like to buy some PCs. E.g., restrictions to Sales and Delivery could express the following:

From the Description Logic point of view, the query and the advertisement are almost identical, both of them are subsumed by the concept ServiceProfile.

Note that the query does not specify anything about the delivery--the flexibility of DL based languages like DAML+OIL allows us to do this while still being able to find relevant matches.

$\displaystyle Query1$	$\displaystyle \equiv$	$\displaystyle ServiceProfile \sqcap$
		$\displaystyle (Sales \sqcap$
		$\displaystyle \forall providedBy.(Actor \ \sqcap \geq_{5} \ \textstyle{hasCreditLevel}) \sqcap$
		$\displaystyle \forall item.(PC \sqcap \forall hasProcessor.Pentium4$
		$\displaystyle \leq_{700} \ \textstyle{hasUnitPrice}))$

5.4 Revised Design

As discussed in Section 5.1, in accordance with DAML-S the providing and requesting Actors have been included as the values of providedBy and requestedBy properties in both the definition of advertisements and queries. It looks reasonable and rational, but there is a fatal problem lying in this design.

Consider the advertisement Advert1 in Section 5.2, which has the property $providedBy.(Actor \sqcap \forall hasName.Georgia)$ . Consider the request Query1 in Section 5.3, and suppose that we perform a matchmaking operation between Advert1 and Query1 using a DL reasoner to (semantically) compare the DAML+OIL descriptions. Due to the existence of $providedBy.(Actor \sqcap \forall hasName.Georgia)$ , there is no subsumption relationship between Query1 and Advert1: all we can do is prove that the two descriptions are not incompatible (their intersection is not equivalent to the bottom concept). This is always likely to be the case as the requester could not have the knowledge that the service he is looking for will be provided by an Actor with the name ``Georgia''. This kind of match is quite weak, and does not allow for result selection via a hierarchy of match types with varying specificity (this will be discussed in detail in Section 6.2).

We believe that this design problem is inherent in the DAML-S specification: there is too much information inside the service profile, and this makes it difficult to use automated reasoning techniques to compute semantic matches between service descriptions.

In order to fix this problem, we have modified the design of advertisements and queries. The new design treats advertisements and queries as objects with various properties, one of which is the profile. Information about who is providing and requesting services is removed from the service profile and attached to advertisements and queries via the providedBy and requestedBy properties (this could be thought as some extra information provided by the advertiser/querier). The core ServiceProfile component is attached to advertisements and queries via the profile property, and includes constraints like item information, unit price, unit quantity and delivery information. Later, in the matchmaking phase, we will only use this ServiceProfile part of an advertisement when computing semantic matches. Constraints such as hasCreditLevel might also be used in realistic e-commerce applications such as eBay⁴ or Amazon,⁵ but we do not consider them in our prototype.

In our modified design, we use the following notation to separate the different components of an advertisement:

$\displaystyle Advert1$	$\displaystyle =$	$\displaystyle (providedBy \ (Actor \sqcap \forall hasName.Georgia),$
		$\displaystyle requestedBy \ (Actor \sqcap \geq \scriptstyle{5} \ \textstyle{hasCreditLevel}),$
		$\displaystyle profile \ (ServiceProfile \sqcap$
		$\displaystyle \forall item.(PC \ \sqcap \geq \scriptstyle{128} \ \textstyle{memorySize}) \sqcap$
		$\displaystyle \leq \scriptstyle{700} \ \textstyle{hasUnitPrice} \sqcap$
		$\displaystyle \leq \scriptstyle{200} \ \textstyle{hasQuantity} \sqcap$
		$\displaystyle \forall delivery.(Delivery \sqcap$
		$\displaystyle \leq \scriptstyle{20020915} \ \textstyle{date} \sqcap \forall location.Bristol)))$

$\displaystyle Query1$	$\displaystyle =$	$\displaystyle (providedBy \ (Actor \sqcap \geq \scriptstyle{5} \ \textstyle{hasCreditLevel}),$
		$\displaystyle profile \ (ServiceProfile \sqcap$
		$\displaystyle \forall item.(PC \sqcap \forall hasProcessor.Pentium4) \sqcap$
		$\displaystyle \leq \scriptstyle{700} \ \textstyle{hasUnitPrice}))$

6 Matchmaking operation

6.1 Matching Definition

Matchmaking is defined as a process that requires a repository host to take a query or advertisement as input, and to return all advertisements⁶ which may potentially satisfy the requirements specified in the input query or advertisement. Formally, this can be specified as:

Let $\alpha$ be the set of all advertisements in a given advertisement repository. For a given query or advertisement,

, the matchmaking algorithm of the repository host returns the set of all advertisements which are compatible,

$\displaystyle Query2$	$\displaystyle =$	$\displaystyle (providedBy \ (Actor \sqcap \forall hasName.Alan),$
		$\displaystyle requestedBy \ (Actor \sqcap = \scriptstyle{5} \ \textstyle{hasCreditLevel}),$
		$\displaystyle profile \ (ServiceProfile \sqcap$
		$\displaystyle \forall item.(PC \ \sqcap = \scriptstyle{256} \ \textstyle{memorySize}) \sqcap$
		$\displaystyle = \scriptstyle{500} \ \textstyle{hasUnitPrice}))$

The intersection of this query with Advert1 in Section 5.4 is satisfiable. Formally:

6.2 Matching Algorithm

To understand the matching algorithm we adopted in our prototype, we first need to introduce the definition of the degree of match. This notion is introduced because it is not particularly useful merely to determine that an advertisement and query are not semantically incompatible. Therefore, starting from the matching degree definition described in [18], we extend the match level ``intersection satisfiable'' to:

Degrees of the match are organized in a discrete scale. Exact matches are clearly preferable; PlugIn matches are considered the next best, since we might expect that advertisers also provide some more specific (sub-class) services, e.g., an advertiser selling PCs might be expected to sell some more specific kinds of PC; Subsume matches are considered to be third best, since an advertiser might also provide some more specific (super-class) services, e.g., an advertiser selling used PCs might also sell PCs in general;⁷ Intersection is considered to be fourth best--it only says that the advertisement is not incompatible with the request; and Disjoint is the lowest level, since it shows that no item could satisfy both the advertisement and the request: it is considered to be a failed match.

With these definitions of match degrees, we now introduce the process of matching a request. The Racer system is used to compute a ServiceProfile hierarchy for all advertised services. For an incoming request, Racer is used to classify the request's ServiceProfile $\mathcal{R}$ , i.e., to compute $\mathcal{R}$ 's subsumption relationships w.r.t. all the advertisement ServiceProfiles. Advertisements with ServiceProfiles equivalent to $\mathcal{R}$ are considered to be Exact matches, those with ServiceProfiles subsuming but not equal to $\mathcal{R}$ are considered to be PlugIn matches, and those with ServiceProfiles subsumed by but not equal to $\mathcal{R}$ are considered to be Subsume matches. Racer is then used to classify $\neg\mathcal{R}$ . Advertisements with ServiceProfiles subsuming but not equal to $\neg\mathcal{R}$ are considered to be Intersection matches, while those subsumed by $\neg\mathcal{R}$ are considered to be Disjoint (failed) matches.

7 Prototype Implementation

In this section we describe the implementation of a multi-agent system including matchmaking, advertising and querying agents. The system emulates a simple but realistic e-commerce scenario. Some issues, however, such as security (e.g., fraud), have not been taken into account, as they were not considered relevant to our purpose: the investigation of ontology based service description and a DL based matchmaking service.

7.1 Abstract Roles

To test the usability of service descriptions and matchmaking in the Semantic Web, we will introduce a scenario in which agents play a variety of roles. They are:

All these three kinds of abstract roles might be played by the same entity at different times or even at the same time, e.g., an information broker is an Advertiser and a Seeker at the same time. With this abstract definition, we can cover different types of matchmaking systems by adding one or more roles to the concrete entity in the real system.

7.2 Functionalities

The matchmaking service provides five kinds of functionalities: advertising a service, querying a service, withdrawing the published service, modifying the published service and browsing advertised services in the repository.

7.2.1 Advertising

The Advertiser publishes to the Host a service description of what it is providing or seeking for. This description captures the relevant features of the service, including the service profile component which will be used in matchmaking.

7.2.2 Querying

The Seeker can submit a query to find relevant advertisements among the currently available ones. By adding constraints over aspects that the Seeker is interested in, the query can be used to filter out irrelevant advertisements. There are two kinds of queries that can be defined:

7.2.3 Modifying/Withdrawing

An Advertiser can modify and withdraw the advertisements it has published before. After the advertiser published his advertisement to the Host, the Host notifies an ID indicating the advertisement to the advertiser. Later on, this ID is used between the Host and the advertiser to specify which advertisement is to be modified or withdrawn. There is an obvious security issue involved, but we simply assume that all the partners in this framework are trusted.

7.2.4 Browsing

The Host offers the functionality of browsing the currently available advertisements. It maintains an advertisement repository, where published advertisements are stored. In finding out about advertised services, browsing parties can make use of this information to tune the advertisements that they will submit in turn, so as to maximize the likelihood of matching.

7.3 Agents

We chose JADE as the agent platform, the goal of JADE being to simplify the development of multi-agent systems while ensuring standard compliance through a comprehensive set of system services and agents in compliance with FIPA specifications. The benefit of JADE is that we can concentrate on the agent functionalities and leave other things, like communication between agents, to the platform.

7.4 Matchmaking

At the beginning of the matchmaking process, the HostAgent initializes Racer with the service ontology described in Section 5, which the Racer system will use to compute the subsumption relations between advertisements and requests throughout the whole matchmaking process. When it receives an advertisement, the HostAgent assigns it a unique ID and stores it in the repository. It then sends the advertisement's ServiceDescription to the Racer system to be added to the subsumption hierarchy.

When it receives a request, the HostAgent uses the Racer system to compute all the match degrees between the request and each advertisement in the repository, as described in Section 6.2. Matching advertisements are returned to the seeker agent, along with their IDs and match degrees (Exact, PlugIn, etc.). For efficiency reasons, match results for a persistent request are maintained until the request expires.

The HostAgent stores persistent requests along with an ID and expiry duration. At the same time as classifying new (and updated) advertisements, the HostAgent will check all persistent requests, delete them if expired, and compute their match degree with respect to the new (or updated) advertisement. If a match is found, the information is added to the stored information from the initial matchmaking, and the complete result for the persistent request is returned to the seeker agent.

8 Evaluation

In terms of functionality, the matchmaking stage has achieved its purpose: it can respond to an input request with the results of matched advertisements. However, in order to find a match for a particular request, the Racer reasoner needs to check the satisfiability of the request with each advertisement that has been previously published to the Matchmaking host, and given the high worst case complexity of reasoning with DAML+OIL descriptions,⁸ the question of scalability arises. We therefore used the prototype implementation to carry out some simple experiments designed to test the system's performance in a realistic agent based e-commerce scenario. The experiment used datasets of between 100 and 1,500 (artificially generated) advertisements, and recorded the time spent for the DL reasoner to find matched advertisements in response to a given request.

Our results showed that, regardless of the number of advertisements, if the advertisements have already been classified (in Racer's TBox), then the reasoning time required to respond to a matching request is always less than 20 milliseconds--so small that accurate measurement was difficult. This would be fast enough for the matchmaking system to handle a high frequency of matching requests.

**Figure 1:** Racer classification times
$\begin{figure}\begin{center} \psfig{file=result.eps,width=\linewidth} \end{center}\end{figure}$

In contrast, classifying the advertisements in the TBox is quite time-consuming. From the comparison of the different sized datasets shown in Figure 1, we can see that the average classification time per advertisement (shown on the Y axis) increases rapidly with the size of the dataset (shown on the X axis). The time rises from 49.57ms per advertisement for dataset size 100, and increases to 715.33ms per advertisement for dataset size 1,500.

Although this test illustrates that dataset size is an important issue in applications that use a DL reasoner, it does not mean that large datasets cannot be handled. For instance, in our prototype, we could do the TBox classification off-line, i.e., for all the published advertisements, we classify the TBox before the matchmaking process starts, and use the classified TBox to reason about requests. As to new incoming advertisements, we can simply insert them into the classified TBox hierarchy, which is much easier than classifying the entire TBox.⁹

9 Discussion

In this paper we have introduced service matchmaking in e-commerce, assessed the requirements for a service description language and ontology, and argued that DAML+OIL and DAML-S fulfill these requirements. This argument is supported by our design and implementation of a prototype matchmaker which uses a DL reasoner to match service advertisements and requests based on the semantics of ontology based service descriptions. By representing the semantics of service descriptions, the matchmaker enables the behaviour of an intelligent agent to approach more closely that of a human user trying to locate suitable web services.

The design of the prototype matchmaker revealed a problem with the use of DAML-S in matchmaking: DAML-S service profiles contain too much information for effective matching. We solved this problem by separating various components of the description; in particular the description of the service being provided was separated from the descriptions of the providing and requesting ``actors''.

Finally, the performance of the prototype implementation was evaluated using a simple but realistic e-commerce scenario. This revealed that, although initial classification of large numbers of advertisements could be quite time consuming, subsequent matching of queries to advertisements could be performed very efficiently. On the basis of these preliminary results, it seems possible that DL reasoning technology could cope with large scale e-commerce applications; future work will include more extensive testing in order to clarify if this is, in fact, the case.

10 Acknowledgments

Bibliography