Diplomarbeit DIP-2781

Lu, Wei: A Graph-based Approach for Querying Structural Information of Business Processes.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 2781 (2008).
95 Seiten, englisch.
CR-Klassif.E.1 (Data Structures)
F.2.2 (Nonnumerical Algorithms and Problems)
G.2.2 (Discrete Mathematics Graph Theory)
H.3.3 (Information Search and Retrieval)
H.4.1 (Office Automation)
KeywordsBusiness Process; BPEL; Suchen; Search; Query; Graph Pattern Matching

Business process specifications can be transformed into attributed directed acyclic graphs. Querying structural information of business process specifications means that find business processes that match the query pattern and its query predicates. In this thesis, we reduce the problem of answering queries against business process specifications to the graph matching problem and present an approach to find exact or approximate answers to such queries. We defined two matching semantics, i.e. exact match and inexact match. We first present a family of stack-based structure join algorithms for an efficient query processing under the exact matching semantic. The worst case time complexity is quadratic in the average size of the query variable bindings. Then we present a new inexact graph matching algorithm to answer approximate queries on process structures by using a new similarity metric called connected component based metric and a new data structure called solution stream. The time complexity of the inexact matching algorithm is polynomial in both the size of the query graph and the size of the process graph in worst case. The algorithms presented in this thesis have been developed for querying business processes in general, as long as the corresponding graph mapping is defined. To evaluate our algorithms we apply them to query BPEL processes by taking into account BPEL-specific characteristics.

Volltext und
andere Links
PDF (1524473 Bytes)
Zugriff auf studentische Arbeiten aufgrund vorherrschender Datenschutzbestimmungen nur innerhalb der Fakultät möglich
Abteilung(en)Universität Stuttgart, Institut für Architektur von Anwendungssystemen
BetreuerMa, Zhilei
Eingabedatum25. September 2008
   Publ. Institut   Publ. Informatik