Web services are often used for search computing where data is retrieved from servers providing information of different kinds. Such data providing web services return a set of objects for a given set of parameters without any side effects. There is need to enable general and scalable search capabilities of data from data providing web services, which is the topic of this Thesis. The Web Service MEDiator (WSMED) system automatically provides relational views of any data providing web service operations by reading the WSDL documents describing them. These views can be queried with SQL. Without any knowledge of the costs of executing specific web service operations the WSMED query processor automatically and adaptively finds an optimized parallel execution plan calling queried data providing web services. For scalable execution of queries to data providing web services, an algebra operator PAP adaptively parallelizes calls in execution plans to web service operations until no significant performance improvement is measured, based on monitoring the flow from web service operations without any cost knowledge or extensive memory usage. To comply with the Everything as a Service (XaaS) paradigm WSMED itself is implemented as a web service that provides web service operations to query and combine data from data providing web services. A web based demonstration of the WSMED web service provides general SQL queries to any data providing web service operations from a browser. WSMED assumes that all queried data sources are available as web services. To make any data providing system into a data providing web service WSMED includes a subsystem, the web service generator, which generates and deploys the web service operations to access a data source. The WSMED web service itself is generated by the web service generator. / eSSENCE

This thesis is concentrated around the problem of query evaluation. Given a query q and a database D it is to compute the set q(D) of all tuples in the output of q on D. However, the set q(D) may be larger than the database itself as it can have a size of the form n^l where n is the size of the database and l the arity of the query. It can therefore require too many of the available resources to compute it entirely. The main focus of this thesis is a particular solution to this problem: a scenario where in stead of just computing, we are interested in enumerating q(D) with constant delay. Intuitively, this means that there is a two-phase algorithm working as follows: a preprocessing phase that works in time linear in the size of the database, followed by an enumeration phase outputting one by one all the elements of q(D) with a constant delay (which is independent from the size of the database) between any two consecutive outputs. Additionally, four more problems related to enumeration are also considered in the thesis. These are model-checking (where the query q is boolean), counting (where one wants to compute just the size |q(D)| of the output set), testing (where one is interested in an efficient test for whether a given tuple belongs to the output of the query or not) and j-th solution (where, one wants to be able to directly access the j-th element of q(D)). The results presented in the thesis address the above problems with respect to: - first-order queries over the classes of structures with bounded degree, - monadic second-order queries over the classes of structures with bounded treewidth, - first-order queries over the classes of structures with bounded expansion.

Web services have been developed as an attractive paradigm for publishing, discovering and consuming services. They are loosely-coupled applications that can be run alone or be composed to create new value-added services. They can be consumed as individual services which provide a unique interface to receive inputs and return outputs; or they can be consumed as components to be integrated into business processes. We call the first consumption case individual use and the second case business process use. The requirement of specific tools to assist consumers in the two service consumption cases involves many researches in both academics and industry. On the one hand, many service portals and service crawlers have been developed as specific tools to assist users to search and invoke Web services for individual use. However, current approaches take mainly into account explicit knowledge presented by service descriptions. They make recommendations without considering data that reflect user interest and may require additional information from users. On the other hand, some business process mechanisms to search for similar business process models or to use reference models have been developed. These mechanisms are used to assist process analysts to facilitate business process design. However, they are labor-intense, error-prone, time-consuming, and may make business analyst confused. In our work, we aim at facilitating the service consumption for individual use and business process use using recommendation techniques. We target to recommend users services that are close to their interest and to recommend business analysts services that are relevant to an ongoing designed business process. To recommend services for individual use, we take into account the user's usage data which reflect the user's interest. We apply well-known collaborative filtering techniques which are developed for making recommendations. We propose five algorithms and develop a web-based application that allows users to use services. To recommend services for business process use, we take into account the relations between services in business processes. We target to recommend relevant services to selected positions in a business process. We define the neighborhood context of a service. We make recommendations based on the neighborhood context matching. Besides, we develop a query language to allow business analysts to formally express constraints to filter services. We also propose an approach to extract the service's neighborhood context from business process logs. Finally, we develop three applications to validate our approach. We perform experiments on the data collected by our applications and on two large public datasets. Experimental results show that our approach is feasible, accurate and has good performance in real use-cases

Semantika informacinių technologijų kontekste yra duomenų apdorojimas pagal prasmę ir kontekstą. Tam įgyvendinti yra taikomas natūralios kalbos apdorojimas, pritaikytas informacijos paieškai, išrinkimui, analizavimui.Taikant semantines technologijas, kūrėjams dažnai kyla klausimas, kaip sukurti semantinės paieškos sąsają, kad ji būtų patogi ir duotų kuo tikslesnius atsakymus į vartotojų užklausas. Šiame darbe aprašomas sukurtas metodas, kuris padeda vartotojui palaipsniui formuoti SPARQL užklausą iš atskirų elementų, dinamiškai keičiant vartotojo sąsają. / Increasing popularity of Semantic Web raises a question how we could make a simple user interface for building semantic queries while keeping high precision of results returned. This thesis presents a method that helps users to create SPARQL queries by allowing to dynamically add components to user interface. The goal of the work is to improve of user interface model for semantic queries by allowing users to construct and change it dynamically till obtaining the desirable answer results. That model was created on the base of analysis of Semantic Web languages, tools and existing portals, their functions and user interfaces. Algorithms for dynamic user interface generation based on user actions were developed that allow creating queries of various complexities with minimal amount of user interface components. Implementation and testing the prototype of the system using movie and wine ontologies has shown that dynamic construction and generation of query interface has desirable functionality and is easily applicable to various ontologies. Experimental comparison with existing semantic search portals has shown that the proposed dynamic user interface generation method could improve precision and recall of semantic queries and may be applied in semantic search portal applications.

Business processes are fundamental to the operations of a company. Each product manufactured and every service provided is the result of a series of actions that constitute a business process. Business process management is an organizational principle that makes the processes of a company explicit and offers capabilities to implement procedures, control their execution, analyze their performance, and improve them. Therefore, business processes are documented as process models that capture these actions and their execution ordering, and make them accessible to stakeholders. As these models are an essential knowledge asset, they need to be managed effectively. In particular, the discovery and reuse of existing knowledge becomes challenging in the light of companies maintaining hundreds and thousands of process models. In practice, searching process models has been solved only superficially by means of free-text search of process names and their descriptions. Scientific contributions are limited in their scope, as they either present measures for process similarity or elaborate on query languages to search for particular aspects. However, they fall short in addressing efficient search, the presentation of search results, and the support to reuse discovered models. This thesis presents a novel search method, where a query is expressed by an exemplary business process model that describes the behavior of a possible answer. This method builds upon a formal framework that captures and compares the behavior of process models by the execution ordering of actions. The framework contributes a conceptual notion of behavioral distance that quantifies commonalities and differences of a pair of process models, and enables process model search. Based on behavioral distances, a set of measures is proposed that evaluate the quality of a particular search result to guide the user in assessing the returned matches. A projection of behavioral aspects to a process model enables highlighting relevant fragments that led to a match and facilitates its reuse. The thesis further elaborates on two search techniques that provide concrete behavioral distance functions as an instantiation of the formal framework. Querying enables search with a notion of behavioral inclusion with regard to the query. In contrast, similarity search obtains process models that are similar to a query, even if the query is not precisely matched. For both techniques, indexes are presented that enable efficient search. Methods to evaluate the quality and performance of process model search are introduced and applied to the techniques of this thesis. They show good results with regard to human assessment and scalability in a practical setting. / Geschäftsprozesse bilden die Grundlage eines jeden Unternehmens, da jedes Produkt und jede Dienstleistung das Ergebnis einer Reihe von Arbeitsschritten sind, deren Ablauf einen Geschäftsprozess darstellen. Das Geschäftsprozessmanagement rückt diese Prozesse ins Zentrum der Betrachtung und stellt Methoden bereit, um Prozesse umzusetzen, abzuwickeln und, basierend auf einer Auswertung ihrer Ausführung, zu verbessern. Zu diesem Zweck werden Geschäftsprozesse in Form von Prozessmodellen dokumentiert, welche die auszuführenden Arbeitsschritte und ihre Ausführungsbeziehungen erfassen und damit eine wesentliche Grundlage des Geschäftsprozessmanagements bilden. Um dieses Wissen verwerten zu können, muss es gut organisiert und leicht auffindbar sein – eine schwierige Aufgabe angesichts hunderter bzw. tausender Prozessmodelle, welche moderne Unternehmen unterhalten. In der Praxis haben sich bisher lediglich einfache Suchmethoden etabliert, zum Beispiel Freitextsuche in Prozessbeschreibungen. Wissenschaftliche Ansätze hingegen betrachten Ähnlichkeitsmaße und Anfragesprachen für Prozessmodelle, vernachlässigen dabei aber Maßnahmen zur effizienten Suche, sowie die verständliche Wiedergabe eines Suchergebnisses und Hilfestellungen für dessen Verwendung. Diese Dissertation stellt einen neuen Ansatz für die Prozessmodellsuche vor, wobei statt einer Anfragesprache Prozessmodelle zur Formulierung einer Anfrage verwendet werden, welche exemplarisch das Verhalten der gesuchten Prozesse beschreiben. Dieser Ansatz fußt auf einem formalen Framework, welches ein konzeptionelles Distanzmaß zur Bewertung gemeinsamen Verhaltens zweier Geschäftsprozesse definiert und die Grundlage zur Suche bildet. Darauf aufbauend werden Qualitätsmaße vorgestellt, die einem Benutzer bei der Bewertung von Suchergebnissen behilflich sind. Verhaltensausschnitte, die zur Aufnahme in das Suchergebnis geführt haben, können im Prozessmodell hervorgehoben werden. Die Arbeit führt zwei Suchtechniken ein, die konkrete Distanzmaße einsetzen, um Prozesse zu suchen, die das Verhalten einer Anfrage exakt enthalten (Querying), oder diesem in Bezug auf das Verhalten ähnlich sind (Similarity Search). Für beide Techniken werden Indexstrukturen vorgestellt, die effizientes Suchen ermöglichen. Abschließend werden allgemeine Methoden zur Evaluierung von Prozessmodellsuchansätzen vorgestellt, mit welchen die genannten Suchtechniken überprüft werden. Im Ergebnis zeigen diese eine hohe Qualität der Suchergebnisse hinsichtlich einer Vergleichsstudie mit Prozessexperten, sowie gute Skalierbarkeit für große Prozessmodellsammlungen.

Darbe nagrinėjama plačiausiai praktikoje paplitusiems duomenų šaltiniams – reliacinėms duomenų bazėms ir XML dokumentams – skirtų užklausų kalbų - SQL, XQuery ir XPath - užklausų struktūra ir savybės. Remiantis analizės rezultatais, sudarytas bendrinis užklausų modelis, kurio paskirtis – padėti formuoti vartotojų užklausas nepriklausomai nuo to, kokiomis technologijomis realizuoti duomenų šaltiniai. Sukurto modelio praktinio taikomumo galimybėms pademonstruoti pateikta juo paremta paieškos sistemos kūrimo metodika. / The thesis presents the analysis of SQL, XQuery and XPath query languages that are intended for the most widely used data sources, namely relational databases and XML documents. Based on the results of the analysis, a generic query model has been developed. The model should serve to help compose user queries without the context of a specific data source implementation technology. The applicability of the model in practice is demonstrated by creating methods for search system development, based on this model.

An increasing amount of data is published as semistructured documents formatted with presentational markup. Examples include data objects such as mathematical expressions encoded with MathML or web pages encoded with XHTML. Our intention is to improve the state of the art in retrieving, manipulating, or mining such data. We focus first on mathematics retrieval, which is appealing in various domains, such as education, digital libraries, engineering, patent documents, and medical sciences. Capturing the similarity of mathematical expressions also greatly enhances document classification in such domains. Unlike text retrieval, where keywords carry enough semantics to distinguish text documents and rank them, math symbols do not contain much semantic information on their own. Unfortunately, considering the structure of mathematical expressions to calculate relevance scores of documents results in ranking algorithms that are computationally more expensive than the typical ranking algorithms employed for text documents. As a result, current math retrieval systems either limit themselves to exact matches, or they ignore the structure completely; they sacrifice either recall or precision for efficiency. We propose instead an efficient end-to-end math retrieval system based on a structural similarity ranking algorithm. We describe novel optimization techniques to reduce the index size and the query processing time. Thus, with the proposed optimizations, mathematical contents can be fully exploited to rank documents in response to mathematical queries. We demonstrate the effectiveness and the efficiency of our solution experimentally, using a special-purpose testbed that we developed for evaluating math retrieval systems. We finally extend our retrieval system to accommodate rich queries that consist of combinations of math expressions and textual keywords. As a second focal point, we address the problem of recognizing structural repetitions in typical web documents. Most web pages use presentational markup standards, in which the tags control the formatting of documents rather than semantically describing their contents. Hence, their structures typically contain more irregularities than descriptive (data-oriented) markup languages. Even though applications would greatly benefit from a grammar inference algorithm that captures structure to make it explicit, the existing algorithms for XML schema inference, which target data-oriented markup, are ineffective in inferring grammars for web documents with presentational markup. There is currently no general-purpose grammar inference framework that can handle irregularities commonly found in web documents and that can operate with only a few examples. Although inferring grammars for individual web pages has been partially addressed by data extraction tools, the existing solutions rely on simplifying assumptions that limit their application. Hence, we describe a principled approach to the problem by defining a class of grammars that can be inferred from very small sample sets and can capture the structure of most web documents. The effectiveness of this approach, together with a comparison against various classes of grammars including DTDs and XSDs, is demonstrated through extensive experiments on web documents. We finally use the proposed grammar inference framework to extend our math retrieval system and to optimize it further.

Ontologijos užklausų rašymas paprastiems vartotojams yra per daug sudėtingas. Vartotojai labiausiai mėgsta pateikti užklausas natūralia kalba. Tačiau dar nėra sukurtų programų, kurios suprastų tikrą natūralią kalbą. Šiuo metu galimas sprendimas yra naudoti ribotą (struktūrizuotą) natūralią kalbą, kuri sudaroma pagal tam tikrus šablonus. Sukūrus SBVR metamodeliu grindžiamą struktūrizuotos natūralios kalbos užklausų redaktorių, vartotojui nereikėtų specialistų pagalbos norint peržiūrėti ontologijų duomenis. Informaciją būtų galima peržiūrėti rašant klausimus struktūrizuota natūralia kalba. Šiame darbe nekeliamas tikslas iš struktūrizuotos kalbos klausimų gauti SPARQL užklausas, kadangi tai būtų per didelis uždavinys. Šio darbo tikslas yra atpažinti ir struktūrizuoti įvedamą tekstą, kad vėliau būtų galima generuoti XMI schemą ir transformuoti ją į SPARQL užklausas. / Ontology query writing for ordinary users too complicated. People mostly like to submit queries in natural language. However, software systems that could understand natural language do not exist yet. A possible solution is to use a limited (structured) natural language, which is formed according to certain patterns. Users having a structured natural language question editor based on SBVR metamodel would be able to analyse ontology data without help of professionals. They could write questions in structured natural language which is understandable for humans and computers. This work is not intended to transform structured questions into SPARQL queries, since it would be too big task. The aim of this work is to identify and formalize textual questions, typed by users, for subsequent generation of XMI schema and transforming them into a SPARQL queries.

The problems associated with the effective design and uses of databases are increasing. The information contained in a database is becoming more complex and the size of the data is causing space problems. Technology must continually develop to accommodate this growing need. An inquiry was conducted in order to find effective guidelines that could support queries in general in terms of performance and productivity. Two database management systems were researched to compare die theoretical aspects with the techniques implemented in practice. Microsoft SQL Sewer and MySQL were chosen as the candidates and both were put under close scrutiny. The systems were researched to uncover the methods employed by each to manage queries. The query optimizer forms the basis for each of these systems and manages the parsing and execution of any query. The methods employed by each system for storing data were researched. The way that each system manages table joins, uses indices and chooses optimal execution plans were researched. Adjusted algorithms were introduced for various index processes like B+ trees and hash indexes. Guidelines were compiled that are independent of the database management systems and help to optimize relational databases. Practical implementations of queries were used to acquire and analyse the execution plan for both MySQL and SQL Sewer. This plan along with a few other variables such as execution time is discussed for each system. A model is used for both database management systems in this experiment. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2007.

Regular path queries (RPQ’s) are given by means of regular expressions and ask for matching patterns on labeled graphs. RPQ’s have recently received great attention in the context of semistructured data, which are data whose structure is irregular, partially known, or subject to frequent changes. One of the most important problems in databases today is the integration of semistructured data from multiple sources modeled as views. In this setting, the database is not available, and given a user query, the system has to answer based solely on the information provided by the views. The problem is computationally hard, and the well-known algorithm for solving it runs in 2EXPTIME. In this paper, we provide practical evidence that this algorithm performs poorly on the average as well. Then, we propose automata- theoretic techniques which make the view-based answering of RPQ’s more feasible in practice.