Diploma Thesis DIP-2781

BibliographyLu, Wei: A Graph-based Approach for Querying Structural Information of Business Processes.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2781 (2008).
95 pages, english.
CR-SchemaE.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.

Full text and
other links
PDF (1524473 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Architecture of Application Systems
Superviser(s)Ma, Zhilei
Entry dateSeptember 25, 2008
   Publ. Institute   Publ. Computer Science