Diplomarbeit: Konzeption und Realisierung von Dienstkomposition für DIANE Service Descriptions Mirco Stern Betreuender Mitarbeiter: Michael Klein Betreuer:

Diplomarbeit:

Konzeption und Realisierung von Dienstkomposition für DIANE Service

Descriptions

Mirco Stern

Betreuender Mitarbeiter: Michael KleinBetreuer: Prof. Dr. Böhm

http://www.ipd.uka.de/DIANE/de/inhalte/home.html

02.12.2005 Mirco Stern 2

Hintergrund: Dienstvermittlung

• Übergeordnetes Problem:"Dienstvermittlung“: Zusammenbringen von Dienstnehmer & Dienstgeber

• Beispiel:

– Dienstnehmer: „Suche irgendeine Info I- Klausur von Prof. Dr. Abeck der letzten 5 Jahre...“

– Dienstgeber: KlausurVerzeichnis.hole(Fach f, Professor p, Datum d)



Schematischer Ablauf einer Dienstvermittlung

1. Dienstgeber beschreibt angebotenen Dienst

2. Dienstgeber veröffentlicht Dienst (Dienstverzeichnis)

3. Dienstnehmer beschreibt gesuchten Dienst

4. Dienstnehmer sucht nach passendem Angebot (Dienstverzeichnis; Vergleich: Anfrage- Angebote)

5. Dienstnehmer erfährt von passendem Dienstgeber

6. Dienstnehmer ruft passenden Dienstgeber auf

Dienstverzeichnis

DG DN



Dienstvermittlung in DIANE

• Ziel von DIANE Service Descriptions:

Vollständige Automatisierung der Dienstnutzung

• Finden eines Dienstgebers (Vergleich Anfrage- Angebot)• Korrekter Aufruf (Belegung der Schnittstelle)

Semantische Beschreibung von Diensten:„DSD- DIANE Service Descriptions“



Schwerpunkt der DA:„Dienstkomposition“

• „Suche irgendeine Info I- Klausur von Prof. Dr. Abeck der letzten 5 Jahre...“

• Dienst: KlausurVerzeichnis.hole(Fach f, Professor p, Datum d)




• „Suche irgendeine Info I- Klausur von Prof. Dr. Abeck der letzten 5 Jahre und die dazugehörige Musterlösung“

Beschreibung?

• Möglichkeit 1- Dienst: KlausurVerzeichnis.holeKlausurMitMusterLösung(Fach f, Professor p, Datum d)

• Möglichkeit 2 – Dienstkomposition: KlausurVerzeichnis.hole(Fach f, Professor p, Datum d) + MusterLösungsVerzeichnis. hole(Fach f, Professor p, Datum d)

Bei gleicher Belegung der Parameter!!!




• „Suche irgendeine Info I- Klausur von Prof. Dr. Abeck der letzten 5 Jahre...“

• Dienst: KlausurVerzeichnis.holeInfoI(Datum d) ???

• Dienstkomposition:„Wann hat Prof. Dr. Abeck Info I gelesen?“ date!

+KlausurVerzeichnis.hole(date)



Ziele der DA:„Dienstkomposition“

• Allgemein (Definition):– Situation: Anfrage kann nicht durch einzelnen verfügbaren Dienst

erfüllt werden Zusammensetzen verfügbarer Dienste

• Problem: Definition deckt verschiedene Arten von Dienstkomposition ab

• Ziele der DA:– Herausarbeiten dieser verschiedenen Fälle– Erweiterung der DIANE Dienstbeschreibung– Realisierung des dazugehörigen Vergleichs



Inhalt• Ziele der Diplomarbeit (Thema)

• Hintergrund: Dimensionen von „Dienstkomposition“

• Überblick über die zugrunde liegende Technologie: DIANE Service Descriptions (DSD)

• Konzeption: Erweiterung der DIANE Dienstbeschreibung

• Realisierung des dazugehörigen Vergleichs

• Zusammenfassung




• Hintergrund: Dimensionen von „Dienstkomposition“1. Erfüllen von Vorbedingungen2. Erbringen mehrerer Effekte3. Umgang mit fehlendem Wissen




• Zusammenfassung



Dimension I:Erfüllen von Vorbedingungen

• Situation: Dienst existiert, der Effekt anbietet- Vorbedingungen nicht erfüllt

Beispiel: – Anfrage: Übersetzung Chinesisch – Deutsch– Angebot: Englisch - Deutsch

• Effekt: Deutsche Version von Text t• Vorbedingung: Englische Version von Text t

• Dienstkomposition als „Chaining“ von Diensten: Rekursives Betrachten einer Vorbedingungen eines Dienstes als Effekt eines zu Suchenden



Dimension I:Erfüllen von Vorbedingungen

• Existieren einige Ansätze:[2, 3, 4, 5, 6, 7, 8, A classification of Issues...]

Im Rahmen dieser DA nicht betrachtet!



Dimension II:Erbringen mehrerer Effekte

• Merkmal: Komposition inhärent in der Anfrage enthalten

• Beispiel: Suche eine alte Info I- Klausur und zugehörige Lösung

• Andere Betrachtung: „Zerlegung“ in Komponenten, für die Dienste verfügbar sind

• Einige Ansätze verfügbar:[1, 9, 10, 11, 12, 13, A classification of Issues...]

• Probleme: – Basieren auf semantisch schwachen Dienstbeschreibungen– „Feste“ Zerlegungen (nicht an verfügbaren Diensten ausgerichtet)



Dimension II:Erbringen mehrerer Effekte

• Besondere Unterklasse: Quantifizierte Anfragen

• Beispiel: Suche alle Klausuren zu Info I der Jahre 2000 bis 2005

• Abgrenzung: Nicht: „Alle Dienste“, die Effekt erbringen

• Unterschied:– Semantisch: Duplikate– Prozedural: Lokalisierung vs. Komposition

• Fall wurde in der Literatur bisher nicht betrachtet



Dimension III:Umgang mit fehlendem Wissen

• Situation: Wissen für die Auswahl eines Dienstes fehlt• Beispiel: Suche Info I-Klausur von Prof. Dr. Abeck -

Gefundener Dienst: Biete Info I- Klausur vom 29. Februar 2000

• Unrealistische Annahme: Vergleicher hat vollständiges Wissen

Erkennen, dass Wissen fehlt & Beschaffen

• Einige Ansätze existieren [5, 8, 10, 11, 14]

• „Erkennen“ abhängig von der zugrunde liegenden Dienstbeschreibung



Dimension von „Dienstkomposition“

• Fokus dieser DA:

Erbringen mehrerer Effekte (Erbringung der Effekte einer Anfrage durch eine Menge verfügbarer Dienste)

Umgang mit fehlendem Wissen








• Zusammenfassung



Beispielontologie

Exam

covers

OralExam WrittenExam

DateTimedate

Durationduration

domain.universityCourse

domain.universityProfessor

examiner

domain.universityStudent

Grade grade

examinee

ONTOLOGY: domain.university.exam



Instanzen

Exam

covers

OralExam WrittenExam

DateTimedate

Durationduration

domain.universityCourse

domain.universityProfessor

examiner

domain.universityStudent

Gradegrade

examinee

info I- Exam:WrittenExam

coversdate

prof. Dr. Abeck:Professor duration

examiner

info I: Course

<2000-02-29T14:00>

<PT1H>

Entsprechende Instanz:



DSD-Anfrage

Dienstnehmer suchteine Funktionalität,keinen bestimmten Dienst!

Menge

Direkte Bedingung Attribut-

Bedingung

:Service

:ServiceProfile

presents

effect

entity

File

contains

format

coversexaminer

date

WrittenExamCourse

== info I

Professor

== prof. Dr. Abeck

DateTime

<= <2005-12-31T23:59>>= <2000-01-01T00:00>

Accessible

Format

in { pdf [1.0], ps [0.5] }



DSD-Angebot

Aufgaben des Vergleichers: 1) Vergleichsergebnis 2) Belegen der Variablen

Variable

:Service

:ServiceProfile

presents

effect

entity

File

contains

format

covers

date

WrittenExamCourse

== info I

Format

== pdf

DateTime

>= <2000-02-29T14:00>

IN

Accessible



Vergleich Anfrage- Angebot

• Ergebnis є [0, 1]

• Vergleich rekursiv entlang der Anfrage:

„Sind die Elemente des Angebots in der Anfragemenge enthalten?“

1) Typ2) Direkte Bedingungen3) Attribute

Format

in { pdf [1.0], ps [0.5] }

formatFormat

== pdf

(Anfrage:)

(Angebot:)

entity

contains

File

...

...

entity

contains

File

...

...

format








• Zusammenfassung



Verbinden mehrerer Effekte

entity

contains

:Service

:ServiceProfile

presents

effect effect

Fileformat

entity

ExamSolution

contains

solutionTo

formatFile

Format

in { pdf [1.0], ps [0.5] }

Accessible Accessible

coversexaminer

date

Course

== info I

Professor

== prof. Dr. Abeck

DateTime

<= <2005-12-31T23:59>>= <2000-01-01T00:00>

WrittenExam

coversexaminer

date

Course

== info I

Professor

== prof. Dr. Abeck

DateTime

<= <2005-12-31T23:59>>= <2000-01-01T00:00>

WrittenExam

Format

in { pdf [1.0], ps [0.5] }




entity

contains

:Service

:ServiceProfile

presents

effect effect

Fileformat

entity

ExamSolution

contains

solutionTo

formatFile

Format

in { pdf [1.0], ps [0.5] }


coversexaminer

date

Course

== info I

Professor

== prof. Dr. Abeck

DateTime

<= <2005-12-31T23:59>>= <2000-01-01T00:00>

WrittenExam

Format

in { pdf [1.0], ps [0.5] }




• Lösung: Trennung der Forderung „gleiche Belegung“ von der Berechnung des Vergleichswerts

„Wertübergabe“-Semantik




entity

contains

:Service

:ServiceProfile

presents

effect effect

Fileformat

entity

ExamSolution

contains

WrittenExam

== x

solutionTo

formatFile

Format

in { pdf [1.0], ps [0.5] }

coversexaminer

date

Course

== info I

Professor

== prof. Dr. Abeck

DateTime

<= <2005-12-31T23:59>>= <2000-01-01T00:00>

WrittenExam

defined as: x


Format

in { pdf [1.0], ps [0.5] }




• „Wertübergabe“-Semantik

• Hintergrund: Trennung der Forderung „gleiche Belegung“ von der Berechnung des Vergleichswerts

• Reihenfolge der Belegung durch den Benutzer vorgegeben (Präferenzen)

• Vorteile (u.a.):– Lokalität bei der Berechnung des Vergleichsergebnisses– Dienstnehmer kann Präferenzen festlegen



Quantifizierte Anfragen

• Quantifizierte Anfragen sind notwendig für Wissensdienste(Schwerpunkt 2 der DA: Umgang mit fehlendem Wissen- Nutzung von Wissensdiensten)

Konzept für Quantifizierung erarbeitet (DSD Erweiterungen und Semantik).








• Zusammenfassung



Architektur des Vergleichers

Anfrage Endlichkeits-Tester

Vor-Vergleicher

TopologischeSortierungder Effekte

Angebots-Verzeichnis

Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe





Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe

• Quantifizierte Anfragen können unendlich viele Effekte enthalten

• „Billiger“ Test

• Fehler sonst spät gemerkt!




Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe

• Wertübergabe-Semantik (Binden von Variablen)

Reihenfolge der Effekte

• Meta-Information (Steuerung des Vergleichs)




Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe

• Möglichst viele unpassende Angebote aussortieren.

• Keine Passenden verwerfen!

• Idee: Typ-Prüfung

• Dazu: Berechnung einer Überdeckung der Effekte




Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe


Kern- Vergleich I

• „Plug- In“- Idee als Grundlage der Komposition (sowohl mehrere Effekte als auch Quantoren): Ist Angebot Teil der Anfrage?

• Problem bei verbundenen Effekten: Verlust der Lokalität des Vergleichs! (Möglichkeit der Belegung)




entity

contains

:Service

:ServiceProfile

presents

effect effect

Fileformat

entity

ExamSolution

contains

WrittenExam

== x

solutionTo

formatFile

Format

in { pdf [1.0], ps [0.5] }

coversexaminer

date

Course

== info I

Professor

== prof. Dr. Abeck

DateTime

<= <2005-12-31T23:59>>= <2000-01-01T00:00>

WrittenExam

defined as: x


Format

in { pdf [1.0], ps [0.5] }

Anfrage:


Kern- Vergleich I

entity

contains

:Service

:ServiceProfile

presents

effect effect

Fileformat

entity

ExamSolution

contains

solutionTo

formatFile


covers

date

Course

== info IWrittenExam

covers

date

WrittenExam

Format

== pdf

DateTime

>= <2000-02-29T14:00>

IN

Format

== pdf

DateTime

>= <2005-01-01T00:00>

Course

in { info I, info II, info III,info IV }

IN

Angebot:


Kern- Vergleich I

• „Plug- In“- Idee als Grundlage der Komposition (sowohl mehrere Effekte als auch Quantoren): Ist Angebot Teil der Anfrage?

• Problem bei verbundenen Effekten: Verlust der Lokalität des Vergleichs! (Möglichkeit der Belegung)

Wiederherstellung durch Ignorieren von Verbindungen: Zunächst Vergleich je eines Anfrage- Effekts mit einem Angebots- Effekt (keine Belegung von Variablen)

Nutzung des rekursiven Vergleichsvorgehens möglich

• Sehr selektiver Vergleich!


Erweiterungen des Kern- Vergleichers

(Betreffen Nutzung von Wissensdiensten für den Vergleich)

1) Generierung und Ausführung von Wissensanfragen falls Instanzen für den Vergleich „hilfreich“ sind (Dienstkomposition)- Ausgeführt durch Instanzen-Manager

• „Hilfreich“: Ohne weitere Informationen müsste Angebot als unpassend verworfen werden Wdh. Beispiel:

• Anfrage: Alte Info I-Klausuren von Prof. Dr. Abeck • Angebot: Alte Info I-Klausuren; Eingabe: Datum

2) Vergleich der Anfrage nach Instanzen (Sonderfall)





Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe




Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe


MultiEffekt-Manager

Aufgabe: Bearbeitung der Einschränkungen, die durch gemeinsame Mengen in

der Anfrage entstehen

1. Einelementige Mengen?2. Kombination3. Schnitt-Berechnung



MultiEffekt-Manager

1. Einelementige Mengen?• Verbindung auch im Angebot oder• Entsprechende Menge einelementig

Anfrage: Angebot 1: Angebot 2:

BA

CC

A

C

B



MultiEffekt-Manager

2. Kombination• Berechnung der möglichen Überdeckungen der Anfrageeffekte

Anfrage:

BA

C

Angebote:

C

A

C

B

C C

BA



MultiEffekt-Manager

3. Schnitt-Berechnung

Anfrage: Angebot:

BA

C

C C

BA





Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe




Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe

• Optimale Belegung der Variablen in Reihenfolge der Effekte

• Nicht implementiert: Quantifizierung/ Kombination von Diensten zur vollständigen Überdeckung der Anfrageeffekte




Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe

• Berechung des Vergleichswerts unter Beachtung der gewählten Belegungen

• Wieder isoliert möglich




Vor-Vergleicher



Kern-Vergleicher

(III)

Instanzen-Manager

Iterations-Manager

[Kern-Vergleicher

(II)]

Ausgabe-Binder

MultiEffekt-Manager

Kern-Vergleicher

(I)Ausgabe

• Wenn passendes Angebot gefunden: Ausgabe- Variablen binden.

• Im Wesentlichen wie bisher!


Evaluation

• Relevanz von Dienstkomposition(Am Beispiel Wissensanfragen:)– Diplomarbeit von Thomas Fischer (35 Anfragen bei Buchhandel)– 1 unpassend– 3 ohne Instanzen– 22 mit Instanzen auf Book– 34 mit Instanzen auf CopyOfBook

• Vergleich mit anderen Ansätzen(Am Beispiel mehrerer Effekte:)– Grundlage: Semantische Dienstbeschreibung– Algorithmische Komposition

• Vorläufige Laufzeitmessung– Pentium 3, 700MHz, 512MB– 1.6144 s, 0.025s


Evaluation

entity

validFor

:Service

:ServiceProfile

presents

effect effect

entity

startTimedate

Owned

CinemaTicket

SeatInShow

Seat

seat

Movie

visible

Date

== <2005-12-02>

Time

~>= <20:00>~<= <22:00>

OUT

Row

within

within

Hall

within

Cinema

address

Address

city

City

name

String

== "Karlsruhe"

Genre

== drama

String

defined as x

genre title

instanceOf

title

Owned

CopyOfBook

Book

String

== x







• Zusammenfassung



Zusammenfassung

• Dienstkomposition- Betrachtung von– Anfragen mit mehreren Effekten– Nutzung von Wissensdiensten

• Erweiterung der Dienstbeschreibung– Elemente zum Verbinden von Effekten– Quantifizierung von Anfragen– Sonderfall zur Beschaffung von Instanzen

• Realisierung des Vergleichs mit Komposition– „Plug-In“- Semantik des Kern-Vergleichs (Grundlage der Komposition)– Wiederherstellung der Lokalität durch Isolierung der Betrachtung gemeinsamer

Mengen vom Rest des Vergleichs– Beschaffung von Instanzen



Literatur

1. Berardi, D., Calvanese, D., Giacomo, G.D., Lenzerini, M., Mecella, M.: Automatic composition of e-services that export their behavior. In: Proc. of 1st Int. Conf. on Service Oriented Computing (ICSOC-03), Trento, Italy. (2003)

2. Zhang, R., Arpinar, I.B., Aleman-Meza, B.: Automatic composition of semantic web services. In: Proc. of the 2003 Int. Conf. on Web Services (ICWS'03), Las Vegas, NV, USA. (2003)

3. Mao, Z.M., Brewer, E.A., Katz, R.H.: Fault-tolerant, scalable, wide-area internet service composition. Technical Report UCB//CSD-01-1129, University of California, Berkeley, USA (2001)

4. Ponnekanti, S.R., Fox, A.: SWORD: A developer toolkit for web service composition. In: Proc. of the 11th Int. WWW Conf. (WWW2002), Honolulu, HI, USA. (2002)

5. Martinez, E., Lesperance, Y.: Web service composition as a planning task: Experiments using knowledge-based planning. In: Proc. of the 14th Int. Conf. on Automated Planning and Scheduling (ICAPS 2004), Whistler, BC, Canada. (2004)

6. Sirin, E., Hendler, J.A., Parsia, B.: Semi-automatic composition of web services using semantic descriptions. In: Proc. of the 1st Workshop on Web Services: Modeling, Architecture and Infrastructure (WSMAI'03), In conjunction with ICEIS'03, Angers, France. (2003)

7. Sheshagiri, M.: Automatic composition and invocation of semantic web services. Master's thesis, University of Maryland, Baltimore County, USA (2004)

8. McDermott, D.V.: Estimated-regression planning for interactions with web services. In: Proc. of the 6th Int. Conf. on Artificial Intelligence Planning Systems (AIPS'02), Toulouse, France. (2002)



Literatur

9. Bultan, T., Fu, X., Hull, R., Su, J.: Conversation specification: a new approach to design and analysis of e-service composition. In: Proc. of the 12th Int. Conf. on World Wide Web (WWW'03), Budapest, Hungary. (2003)

10. Wu, D., Parsia, B., Sirin, E., Hendler, J.A., Nau, D.S.: Automating DAML-S web services composition using SHOP2. In: Proc.of the 2nd Int. Semantic Web Conf.(ISWC2003), Sanibel Island, FL, USA. (2003)

11. McIlraith, S.A., Son, T.C.: Adapting golog for composition of semantic web services. In: Proc. of the 8th Int. Conf. on Principles and Knowledge Representation and Reasoning (KR-02), Toulouse, France. (2002)

12. Thakkar, S., Knoblock, C.A., Ambite, J.L.: A view integration approach to dynamic composition of web services. In: Proc. of the 13th Int. Conf. on Automated Planning and Scheduling (ICAPS'03), Trento, Italy. (2003)

13. Medjahed, B., Bouguettaya, A., Elmagarmid, A.K.: Composing web services on the semantic web. The VLDB Journal The International Journal on Very Large Data Bases 12 (2003) 333-351

14. Kuter, U., Sirin, E., Nau, D.S., Parsia, B., Hendler, J.A.: Information gathering during planning for web service composition. In: Proc. of the 3rd Int. Semantic Web Conf. (ISWC2004), Hiroshima, Japan. (2004)


Documents

Diplomarbeit: Konzeption und Realisierung von Dienstkomposition für DIANE Service Descriptions Mirco Stern Betreuender Mitarbeiter: Michael Klein Betreuer: