TU Darmstadt / ULB / TUbiblio

Efficient Matchmaking of Business Processes in Web Service Infrastructures

Mahleko, Bendick (2006)
Efficient Matchmaking of Business Processes in Web Service Infrastructures.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

The problem addressed in this dissertation can be stated as follows: given as a query, a business process description within a Web service infrastructure, efficiently find business processes from a large repository that complementarily support the input query. In particular, the input business process enforces that some parts of the business process be mandatory. For example, a buyer organization using RosettaNet PIPs and the corresponding data dictionary might want to find suppliers that use the same RosettaNet standard that fulfill his business process. In this case, for instance, a mandatory cancellation procedure of the processing would be executed after the order had been placed with the supplier. The current Web service standards around Universal Description, Discovery and Integration (UDDI) and related technologies do not address this problem as they offer only service discovery based on attribute/ value queries, that is limited to atomic service discovery. Research has shown that Business Process Execution Language for Web Services (BPEL4WS or BPEL for short), which is currently used to express business processes in Web service environments, does not have a solid formal model and thus lacks formal semantics for querying business process descriptions. This means that a formal model is required to express business processes and to enable their querying. Based on this formal model, appropriate indexing techniques are needed for efficient querying in large service repositories. A business process can be described as a set of message sequences each representing a potential execution sequence of the process. Based on this model, business processes are queried by finding matching business processes within the repository; the matching operation can be defined by computing a common set of message sequences covering the mandatory parts. The business process matchmaking semantics can be formalized by modelling business processes using an enrichment of finite state automata (FSAs) with propositional logical expressions. We call the enriched FSAs annotated finite state automata (aFSAs). aFSAs can express message sequences (potentially infinite) in a business process while logical expressions express mandatory as well as optional parts of the business process. A business process matchmaking is formally defined as the non-empty intersection of aFSAs, covering mandatory parts of the business process description. Computing the intersection of aFSAs is computationally expensive being more than quadratic on the number of states and transitions. Further, sequentially scanning large service repositories to find matching business processes will not scale even if individual query operations were simple. The traditional way to speed-up query performance operations in databases is to use indexes. However, indexes for intersection-based queries on aFSAs are also not supported by standard database indexing techniques such as B+-trees. An option is to construct an index based on aFSA message sequences and annotations, and using message sequence equivalence as well as the evaluation of annotations to realize intersection operations. However, the number of message sequences in an aFSA may be infinite due to cycles in the business process specification. In this dissertation a formal model for indexing and querying business processes is developed. The indexing approach is based on abstractions to transform aFSAs via their grammars into forms that can be indexed by available indexing mechanisms like B+-trees. The indexing approach is implemented and evaluated. Evaluation results show that the index outperforms sequential scanning by several orders of magnitude. An analysis of evaluation results also shows that the index scales well with increasing data set sizes and exhibits good computational properties for searching, being approximately linear on the number of aFSAs in the data collection.

Typ des Eintrags: Dissertation
Erschienen: 2006
Autor(en): Mahleko, Bendick
Art des Eintrags: Erstveröffentlichung
Titel: Efficient Matchmaking of Business Processes in Web Service Infrastructures
Sprache: Englisch
Referenten: Lin, Prof. Ph.D Kwei-Jay
Berater: Neuhold, Prof. Dr. Erich
Publikationsjahr: 3 August 2006
Ort: Darmstadt
Verlag: Technische Universität
Datum der mündlichen Prüfung: 11 Juli 2006
URL / URN: urn:nbn:de:tuda-tuprints-7197
Kurzbeschreibung (Abstract):

The problem addressed in this dissertation can be stated as follows: given as a query, a business process description within a Web service infrastructure, efficiently find business processes from a large repository that complementarily support the input query. In particular, the input business process enforces that some parts of the business process be mandatory. For example, a buyer organization using RosettaNet PIPs and the corresponding data dictionary might want to find suppliers that use the same RosettaNet standard that fulfill his business process. In this case, for instance, a mandatory cancellation procedure of the processing would be executed after the order had been placed with the supplier. The current Web service standards around Universal Description, Discovery and Integration (UDDI) and related technologies do not address this problem as they offer only service discovery based on attribute/ value queries, that is limited to atomic service discovery. Research has shown that Business Process Execution Language for Web Services (BPEL4WS or BPEL for short), which is currently used to express business processes in Web service environments, does not have a solid formal model and thus lacks formal semantics for querying business process descriptions. This means that a formal model is required to express business processes and to enable their querying. Based on this formal model, appropriate indexing techniques are needed for efficient querying in large service repositories. A business process can be described as a set of message sequences each representing a potential execution sequence of the process. Based on this model, business processes are queried by finding matching business processes within the repository; the matching operation can be defined by computing a common set of message sequences covering the mandatory parts. The business process matchmaking semantics can be formalized by modelling business processes using an enrichment of finite state automata (FSAs) with propositional logical expressions. We call the enriched FSAs annotated finite state automata (aFSAs). aFSAs can express message sequences (potentially infinite) in a business process while logical expressions express mandatory as well as optional parts of the business process. A business process matchmaking is formally defined as the non-empty intersection of aFSAs, covering mandatory parts of the business process description. Computing the intersection of aFSAs is computationally expensive being more than quadratic on the number of states and transitions. Further, sequentially scanning large service repositories to find matching business processes will not scale even if individual query operations were simple. The traditional way to speed-up query performance operations in databases is to use indexes. However, indexes for intersection-based queries on aFSAs are also not supported by standard database indexing techniques such as B+-trees. An option is to construct an index based on aFSA message sequences and annotations, and using message sequence equivalence as well as the evaluation of annotations to realize intersection operations. However, the number of message sequences in an aFSA may be infinite due to cycles in the business process specification. In this dissertation a formal model for indexing and querying business processes is developed. The indexing approach is based on abstractions to transform aFSAs via their grammars into forms that can be indexed by available indexing mechanisms like B+-trees. The indexing approach is implemented and evaluated. Evaluation results show that the index outperforms sequential scanning by several orders of magnitude. An analysis of evaluation results also shows that the index scales well with increasing data set sizes and exhibits good computational properties for searching, being approximately linear on the number of aFSAs in the data collection.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Die Problemstellung, die in dieser Dissertation adressiert wird, kann wie folgt beschrieben werden: eine Beschreibung eines Geschäftsvorgangs, die in einer Web Service Infrastruktur in Form einer Abfrage vorgegeben ist, soll in einer großen Datenquelle effizient Geschäftsprozesse aufspüren, die komplementär zur Eingabe-Abfrage sind. Insbesondere kann der Eingabe-Geschäftsprozess vorschreiben, dass einige Teile des Geschäftsvorgangs zwingend erforderlich sind. Zum Beispiel sucht ein Einkäufer, der eine bestimmte RosettaNet PIPs Beschreibung und das dazu gehörige Datenbeschreibungsverzeichnis einsetzt, einen Lieferanten, der ebenfalls demselben RosettaNet Standard folgt und somit auch den Geschäftsprozessen des Einkäufers entspricht. Nach Abschluss der Auftragsvergabe würde hier der Geschäftsvorgang zwingend beendet werden. Die derzeitigen, mit UDDI (Universal Description, Discovery and Integration) erstellten Webservice Technologien sowie verwandte Technologien sind nicht in der Lage dieses Problem zu lösen, da diese zur Dienstfindung nur begrenzte Unterstützung auf Attribute-/Werte-basierenden Abfragen anbieten können und demnach auf die atomare Dienstfindung beschränkt ist. In der Forschung werden BPEL4WS oder BPEL (Business Process Execution Language für Web Services) zur Beschreibung von Geschäftsprozessen verwendet. Es hat sich gezeigt, dass diesen Sprachen ein solides, formales Modell und daher auch eine formale Semantik fehlt, um Abfragen von Geschäftsvorgangsbeschreibungen durchzuführen. Dies bedeutet, dass ein formales Modell benötigt wird, um Geschäftsprozesse darstellen zu können und ihre Abfrage zu ermöglichen. Geeignete, auf einem solchen, formalen Modell aufbauende Techniken werden zur Indizierung benötigt, um Abfragen in großen Datenquellen effizient gestalten zu können. Ein Geschäftsprozess kann als eine Abfolge von Nachrichten beschrieben werden, wobei jede Nachricht eine mögliche Sequenz in der Ausführung eines Vorgangs repräsentiert. Anhand dieses Modells kann durch Abgleichen der Geschäftsprozesse in der Datenquelle nach passenden Prozessen abgefragt werden. Der Abgleichvorgang ist definiert durch die Berechnung einer gemeinsamen Menge an Sequenznachrichten, die die zwingend notwendigen Teile enthalten. Die Semantik des Algorithmus zum Abgleich von Geschäftsprozessen kann durch Modellieren der endlichen Zustandsautomaten (final state automata, FSA), d. h. durch Anreichern mit aussagenlogischen Ausdrücken, formalisiert werden. Diese angereicherten FSAs (aFSAs) können Sequenznachrichten (möglicherweise unendlich) in einem Geschäftsprozess ausdrücken, während logische Ausdrücke sowohl erforderliche als auch wahlfreie Teile des Geschäftsprozesses darstellen können. Der Abgleich von Geschäftsprozessen ist formal definiert als die nicht leere Schnittmenge von aFSAs, die die erforderlichen Teile einer Geschäftsprozessbeschreibung enthalten. Die Schnittmenge von aFSAs zu berechnen ist rechenintensiv und mehr als quadratisch zur Anzahl der Zustände und übergänge. Ferner skaliert ein sequentielles Scannen von großen Datenquellen nicht bei der Suche nach passenden Geschäftsprozessen, auch wenn die einzelnen Abfrageoperationen einfach aufgebaut sind. Herkömmlicherweise werden Indizes verwendet, um Anfragen in Datenbanken zu beschleunigen. Indizes zu schnittmengen-basierten Anfragen von aFSAs werden jedoch von Standard-Datenbank-Indexierungstechniken wie beispielsweise B+-tree nicht unterstützt. Eine Möglichkeit ist, einen Index auf Basis von aFSA Sequenznachrichten und Annotationen zu erzeugen, Hier werden Sequenznachrichten-äquivalenz und die Auswertung der Kommentierungen für die Erstellung der Schnittmengen mit berücksichtigt. Die Anzahl der Sequenznachrichten in einer aFSA kann unendlich sein, da sich Schleifen in der Spezifikation des Geschäftsprozesses bilden können. In dieser Dissertation wird ein formales Modell zur Indexierung und Abfrage von Geschäftsprozessen entwickelt. Der Ansatz zur Indexierung basiert auf Abstraktionen zur Transformation von aFSAs über die Grammatik in eine Struktur, die durch verfügbare Indexierungsmechanismen wie z. B. B+-tree indiziert werden kann . Die Indexierungslösung wird implementiert und ausgewertet. Die Evaluierungsergebnisse zeigen, dass die Indexierung das sequentielle Scannen um mehrere Größenordnungen übertrifft. Eine Analyse der Evaluierungsergebnisse zeigt darüber hinaus, dass der Index auch mit zunehmender Anzahl an Datensätzen gut skaliert und gute Recheneigenschaften bei der Suche aufweist, da die Suche sich linear zur Anzahl der aFSAs in der Datensammlung verhält.

Deutsch
Freie Schlagworte: business process matching, indexing techniques
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
Hinterlegungsdatum: 17 Okt 2008 09:22
Letzte Änderung: 26 Aug 2018 21:25
PPN:
Referenten: Lin, Prof. Ph.D Kwei-Jay
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 11 Juli 2006
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen