Approximate Matching of Service Description Using Ontologies and Rules

網路服務是用於在互聯網上的遠端的共享資源。而組合基本的網路服務可以變成複合的網路服務。服務的能力等等的服務的特微，可以被特別彰顯並記錄於服務描述檔中。而服務描述可以用於比較該服務是否合乎某種特定需求。如果用合適的知識本體語言來記錄服務描述，則電腦可以直接了解服務描述所內含的語義。則電腦可以自動地找尋並執行遠端服務。但使用者仍會面臨一個窘境－找不到合乎要求的服務。這個窘境肇因於使用者所定義的需求過於狹隘。而幸運的是，使用者通常不是要找到一個與需求完全相同的服務，而替代服務很有可能就可以滿足使用者的需求。 在本論文中，我們提出一個模糊比對的方法。這個方法可在完美的服務不存在時找尋到替代服務。在該方法中，服務和需求是利用某個特定的知識本體語言所定義的概念體所組合而成的描述。則比對服務是否滿足需求可以轉變成比較兩者之間是否存在包含的關係。為了要找到替代服務，我們利用改寫原始需求中的基元概念體為較廣義的基元概念體的方式來使需求找到更多的服務。我們提出了制定基本概念體之間相似度的計算方式，並利用相似度來找到較廣義的概念體。我們實作了一個旅行計畫系統來驗證此模糊比對的方法。在該系統中，我們以OWL-DL作為我們的知識本體語言，並利用Racer的推理能力來驗證包含關係。但限於OWL-DL的表達能力，我們無法用數字的模式表現出線段。為了解決這個問題，我們利用概念體來表達線段，並利用限定兩者之間的關係來表達兩線段在數線上的前後關係。而這個前後關係也是轉變成驗證兩者的包含關係。利用我們的模糊比對方法，旅行計畫系統可以在找不到使用者限定的服務時替使用者找到替代服務。而且每一個替代服務皆會給予一個評價值，使用者可以參考評價值選擇自己需求的服務。Web services, which are heterogeneous application accessible over the Internet, may be integrated into more sophisticated compound services. Features of a service such as its functionalities can be characterized and recorded in its service description as a basis for determining if the service satisfies some particular needs. Expressed with a suitable ontology language, service descriptions become machine-interpretable, making it possible to discover and compose services automatically. We are then faced with a situation when no perfect services can be found because the requirement is too strict. Fortunately, perfect matches may not be necessary in most cases, and the requester may be satisfied with “good enough” services. In this thesis, we propose an approximate matching scheme, which returns reasonable substitute services when no exact matches can be found. In our scheme, service descriptions and requirements are both expressions coded with concepts predefined in some ontology language, and service matching is reduced to subsumption checking. To find approximate matches, a requirement is loosened by replacing primitive concepts in the original expression with substitute concepts. Substitute concepts are selected against the similarity values derived from how many features they have in common with the original ones. Substitute concepts are also found by relation compositions which can be revealed with domain-specific inference supported by rule engines. We apply the approximate scheme in a trip planning system where service descriptions are coded with OWL-DL and subsumption checking is done by Racer. OWL-DL, which implements concrete domains with datatypes, disallows user defined datatypes and therefore concepts cannot be constrained with upper/lower bounds of concrete domains. To represent intervals in a service description, we propose two approaches to model quantitative relations where upper/lower bounds are defined with concept subsumptions and object properties, and inference problems in concrete domains such as linear inequality is translated into subsumption checking. With our approximate matching scheme, the trip planning system is able to find exactly matched or approximately matched services, and chooses among them against the ranks automatically produced by our ranking mechanism to compose his own trip.1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Related Work 5 2.1 Web Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 WSDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 UDDI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 SOAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 SemanticWeb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 OWL-S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 WSMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Concept Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5 Service Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6 Concept Rewriting and Approximation Rule . . . . . . . . . . . . . . . . 18 3 Preliminaries 21 3.1 Basics of Description logic . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Concrete Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Relationship Between DL and OWL . . . . . . . . . . . . . . . . . . . . . 23 3.4 Inference Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 SemanticWeb Rule Language: SWRL . . . . . . . . . . . . . . . . . . . 26 3.5.1 SWRL Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.5.2 SWRL Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 MatchingScheme 30 4.1 Service Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Quantitative Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4 SystemArchitecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.4.1 OWL Knowledge Repository . . . . . . . . . . . . . . . . . . . . . 37 4.4.2 OntologyMerge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4.3 Concept Approximator . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4.4 Matching Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4.5 DL Reasoner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.4.6 Rule Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.4.7 Rule Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5 Service Matching Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5.1 Idea of Approximation . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5.2 Symbol Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.5.3 Unfolding Service Descriptions . . . . . . . . . . . . . . . . . . . . 41 4.5.4 Find Substitute Concepts . . . . . . . . . . . . . . . . . . . . . . 42 4.5.5 Construct Approximate Requests . . . . . . . . . . . . . . . . . . 44 4.5.6 Ranking Services . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5 Prototype System 49 5.1 Inference Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2 TourismDomain Ontology . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2.1 Value Partition Ontology . . . . . . . . . . . . . . . . . . . . . . . 52 5.2.2 Time Ontology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.2.3 Location and Transportation Ontologies . . . . . . . . . . . . . . 56 5.2.4 Requirement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.3 Issues of Service Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.3.1 Defining with Intervals . . . . . . . . . . . . . . . . . . . . . . . . 58 5.3.2 OntologyMerge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3.3 Working with the Rule Engine . . . . . . . . . . . . . . . . . . . . 60 5.4 SystemDemonstration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6 Conclusion 65 6.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6