In dieser Arbeit schlagen wir die Verwendung von materialisierten Anfragen als Indexstruktur für RDF-Daten vor. Wir streben eine Reduktion der Bearbeitungszeit durch die Minimierung der Anzahl der Vergleiche zwischen Anfrage und RDF Datenmenge an. Darüberhinaus betonen wir die Rolle von Kostenmodellen und Indizes für die Auswahl eines efizienten Ausführungsplans in Abhängigkeit vom Workload. Wir geben einen Überblick über das Problem der Auswahl von materialisierten Anfragen in relationalen Datenbanken und diskutieren ihre Anwendung zur Optimierung der Anfrageverarbeitung. Wir stellen RDFMatView als Framework für SPARQL-Anfragen vor. RDFMatView benutzt materializierte Anfragen als Indizes und enthalt Algorithmen, um geeignete Indizes fur eine gegebene Anfrage zu finden und sie in Ausführungspläne zu integrieren. Die Auswahl eines effizienten Ausführungsplan ist das zweite Thema dieser Arbeit. Wir führen drei verschiedene Kostenmodelle für die Verarbeitung von SPARQL Anfragen ein. Ein detaillierter Vergleich der Kostmodelle zeigt, dass ein auf Index-- und Prädikat--Statistiken beruhendes Modell die genauesten Informationen liefert, um einen effizienten Ausführungsplan auszuwählen. Die Evaluation zeigt, dass unsere Methode die Anfragebearbeitungszeit im Vergleich zu unoptimierten SPARQL--Anfragen um mehrere Größenordnungen reduziert. Schließlich schlagen wir eine einfache, aber effektive Strategie für das Problem der Auswahl von materialisierten Anfragen über RDF-Daten vor. Ausgehend von einem bestimmten Workload werden algorithmisch diejenigen Indizes augewählt, die die Bearbeitungszeit des gesamten Workload minimieren sollen. Dann erstellen wir auf der Basis von Anfragemustern eine Menge von Index--Kandidaten und suchen in dieser Menge Zusammenhangskomponenten. Unsere Auswertung zeigt, dass unsere Methode zur Auswahl von Indizes im Vergleich zu anderen, die größten Einsparungen in der Anfragebearbeitungszeit liefert. / In this thesis, we propose to use materialized queries as a special index structure for RDF data. We strive to reduce the query processing time by minimizing the number of comparisons between the query and the RDF dataset. We also emphasize the role of cost models in the selection of execution plans as well as index sets for a given workload. We provide an overview of the materialized view selection problem in relational databases and discuss its application for optimization of query processing. We introduce RDFMatView, a framework for answering SPARQL queries using materialized views as indexes. We provide algorithms to discover those indexes that can be used to process a given query and we develop different strategies to integrate these views in query execution plans. The selection of an efficient execution plan states the topic of our second major contribution. We introduce three different cost models designed for SPARQL query processing with materialized views. A detailed comparison of these models reveals that a model based on index and predicate statistics provides the most accurate cost estimation. We show that selecting an execution plan using this cost model yields a reduction of processing time with several orders of magnitude compared to standard SPARQL query processing. Finally, we propose a simple yet effective strategy for the materialized view selection problem applied to RDF data. Based on a given workload of SPARQL queries we provide algorithms for selecting a set of indexes that minimizes the workload processing time. We create a candidate index by retrieving all connected components from query patterns. Our evaluation shows that using the set of suggested indexes usually achieves larger runtime savings than other index sets regarding the given workload.

In dieser Arbeit untersuchen wir Algorithmen für Scheduling-Probleme. Wir betrachten semi-online Makespan-Scheduling und generalisiertes Bin Covering. Im online Makespan- Scheduling-Problem sind m Maschinen und n Jobs gegeben, wobei letztere jeweils eine individuelle Bearbeitungszeit haben. Es wird zu jedem Zeitpunkt ein Job offengelegt und muss sofort und unwiderruflich einer Maschine zugewiesen werden, ohne Wissen über zukünftige Jobs. Die Last einer Maschine wird als die Summe der Bearbeitungszeiten der ihr zugewiesenen Jobs definiert. Das Ziel ist es, eine Zuweisung von Jobs zu Maschinen zu finden, sodass die höchste Last einer Maschine minimiert wird. Im semi-online Scheduling-Modell wird dieses strikte Szenario relaxiert. Wir untersuchen drei verschied- ene Modelle. Im ersten ist uns die kumulierte Bearbeitungszeit der Jobs vor Ankunft der einzelnen Jobs bekannt. Im zweiten Modell dürfen wir bis zu einem gewissen Grade bereits zugewiesene Jobs anderen Maschinen neu zuordnen.Im dritten semi-online Scheduling-Modell darf ein Algorithmus mehrere Lösungen parallel konstruieren, von denen die beste ausgegeben wird. Beim generalisierten Bin Covering sind uns m Bintypen und n Objekte gegeben. Ein Bintyp Mj hat einen Bedarf dj und einen Profit rj. Jedes Objekt Jt hat eine Größe pt. Ein Bin vom Typ Mj heißt abgedeckt, wenn die Summe der Größen der ihm zugewiesenen Objekte mindestens dj ist. Wenn ein Bin vom Typ Mj abgedeckt ist, erzielen wir einen Profit von rj. Ziel ist es, die Objekte Bins zuzuweisen, sodass der erzielte Gesamtprofit maximiert wird. Wir untersuchen zwei Modelle, die sich in der Verfügbarkeit von Bintypen unterscheiden. Im Unit-Supply-Modell steht uns von jedem Bintyp genau ein Bin zur Verfügung. Im Gegensatz dazu stehen uns im Infinite-Supply-Modell von jedem Bintyp beliebig viele Bins zur Verfügung. Das Unit-Supply-Modell ist daher eine Verallgemeinerung des Infinite-Supply-Modells. Für alle Modelle zeigen wir beinahe scharfe obere und untere Schranken. / In this thesis we study algorithms for scheduling problems. We investigate semi-online minimum makespan scheduling and generalized bin covering. In online minimum makespan scheduling we are given a set of m machines and n jobs, where each job Jt is specified by a processing time. The jobs arrive one by one and we have to assign them to the machines without any knowledge about future incoming jobs. The load of a machine is defined to be total processing time of the assigned jobs. The goal is to place the jobs on the machines such that the maximum load of a machine is minimized. In semi-online minimum makespan scheduling this strict setting is softened. We investigate three different models. In the first setting an algorithm is given an advice on the total processing time of the jobs. In the second setting we may reassign jobs upto a limited amount. The third semi-online setting we study is minimum makespan scheduling with parallel schedules. In this problem an algorithm may maintain several schedules, the best of which is output after the arrival of the entire job sequence. In generalized bin covering we are given m bin types and n items. Each bin type Mj is specified by a demand dj and a revenue rj. Each item Jt has a size pj. A bin of type Mj is said to be covered if the total size of the assigned items is at least the demand dj. Then the revenue rj is earned. The goal is to find an assignment of items to bins maximizing the total obtained revenue. We study two models of bin supply. In the unit supply model there is only one bin of each type available. By contrast in the infinite supply model each bin type is available arbitrarily often, and hence the former is a generalization of the latter. We provide nearly tight upper and lower bounds for all models.

Petrinetze werden in vielen Bereichen als Modellierungstechnik verwendet. Die verschiedenen Einsatzgebiete und Modellierungsziele erfordern dabei unterschiedliche Typen von Petrinetzen. Einen Petrinetz-Typ kennzeichnen -- neben den üblichen Stellen, Transitionen und Kanten -- eine Menge zusätzlicher, spezifischer Elemente, sowie eine spezifische Schaltregel. In der Literatur findet man zahlreiche verschiedene Petrinetz-Typen. Diese Vielfalt an Petrinetz-Typen lässt sich nicht ohne weiteres überblicken. Deshalb fehlt es auch nicht an Versuchen, allgemeine Petrinetz-Typen oder Klassifikationen -- auch einzelner Aspekte -- zu etablieren. Allerdings erfassen die bisherigen Ansätze nur einen kleinen Teil aller Petrinetz-Typen. Unser semantisch orientierter Klassifizierungsansatz des Petrinetz-Hyperwürfels umfasst deutlich mehr Petrinetz-Typen und erhebt den Anspruch, universell zu sein. Der Petrinetz-Hyperwürfel hat einen syntaktisch orientierten Klassifizierungsansatz als Grundlage. Dieser Ansatz führt einerseits zum Vorschlag der Petri Net Markup Language. Damit können Petrinetze aller Typen einheitlich beschrieben werden. Andererseits führt derselbe Ansatz zu einer Basis für Petrinetz-Werkzeuge, in der die einzelnen Teile eines Petrinetz-Typs unabhängig voneinander implementiert werden. Der Petrinetz-Kern ist eine derartige Basis mit dessen Hilfe Petrinetz-Werkzeuge gebaut werden. Er implementiert Konzepte, die allen Petrinetzen gemein sind, unabhängig von konkreten Petrinetz-Typen. Gemeinsam mit dem Petrinetz-Hyperwürfel bildet der Petrinetz-Kern ein weiteres Basiswerkzeug für einen parametrisierten Petrinetz-Typ mit einer parametrisierten Schaltregel. Die Petri Net Markup Language und der Petrinetz-Kern sind die wesentlichen Beiträge der vorliegenden Arbeit. Gemeinsam bilden sie ein mächtiges Grundgerüst für Petrinetz-Werkzeuge beliebiger Petrinetz-Typen. / Petri nets are widely used for modelling systems. The different areas and goals require different types of Petri nets. Each Petri net contains beside places, transitions, and arcs several further specific elements. Furthermore, a Petri net type defines a specific firing rule. There are many different Petri net types. It is not easy to have a general view on this bulk of Petri net types. Thus, there are attempts to establish general Petri net types or classifications of Petri net types (even of particular aspects). But, current approaches include only a few of all Petri net types. Our approach is a classification by semantics of Petri nets. We call this classification Petri Net Hypercube. It is meant to be universal for all Petri net types. A syntactical classification approach is the base of the Petri Net Hypercube. This approach leads on the one hand to the proposal of the Petri Net Markup Language. This language describes Petri nets of all types. On the other hand, the same approach leads to a base of Petri net tools. The parts of a Petri net type are implemented in this base independently of each other. The Petri Net Kernel is such a base for building Petri net tools. It implements those concepts which are general concepts of each Petri net. The Petri Net Kernel forms together with the Petri Net Hypercube a further basic Petri net tool for a parameterized Petri net type with a parameterized firing rule. The Petri Net Markup Language and the Petri Net Kernel are the main contributions of this thesis. Together, they are a powerful base for Petri net tools of each Petri net type.

Seit Jahrhunderten wird menschliches Wissen in Form von natürlicher Sprache ausgetauscht und in Dokumenten schriftlich aufgezeichnet. In den letzten Jahren konnte man auf dem Gebiet der Lebenswissenschaften eine exponentielle Zunahme wissenschaftlicher Publikationen beobachten. Diese Dissertation untersucht die automatische Extraktion von Beziehungen zwischen Eigennamen. Innerhalb dieses Gebietes beschäftigt sich die Arbeit mit der Steigerung der Robustheit für die Relationsextraktion. Zunächst wird der Einsatz von Ensemble-Methoden anhand von Daten aus der "Drug-drug-interaction challenge 2013" evaluiert. Ensemble-Methoden erhöhen die Robustheit durch Aggregation unterschiedlicher Klassifikationssysteme zu einem Modell. Weiterhin wird in dieser Arbeit das Problem der Relationsextraktion auf Dokumenten mit unbekannten Texteigenschaften beschrieben. Es wird gezeigt, dass die Verwendung des halb-überwachten Lernverfahrens self training in solchen Fällen eine höhere Robustheit erzielt als die Nutzung eines Klassifikators, der lediglich auf einem manuell annotierten Korpus trainiert wurde. Zur Ermittlung der Robustheit wird das Verfahren des cross-learnings verwendet. Zuletzt wird die Verwendung von distant-supervision untersucht. Korpora, welche mit der distant-supervision-Methode erzeugt wurden, weisen ein inhärentes Rauschen auf und profitieren daher von robusten Relationsextraktionsverfahren. Es werden zwei verschiedene Methoden untersucht, die auf solchen Korpora trainiert werden. Beide Ansätze zeigen eine vergleichbare Leistung wie vollständig überwachte Klassifikatoren, welche mit dem cross-learning-Verfahren evaluiert wurden. Um die Nutzung von Ergebnissen der Informationsextraktion zu erleichtern, wurde die semantische Suchmaschine GeneView entwickelt. Anforderungen an die Rechenkapazität beim Erstellen von GeneView werden diskutiert und Anwendungen auf den von verschiedenen Text-Mining-Komponenten extrahierten Daten präsentiert. / For several centuries, a great wealth of human knowledge has been communicated by natural language, often recorded in written documents. In the life sciences, an exponential increase of scientific articles has been observed, hindering the effective and fast reconciliation of previous finding into current research projects. This thesis studies the automatic extraction of relationships between named entities. Within this topic, it focuses on increasing robustness for relationship extraction. First, we evaluate the use of ensemble methods to improve performance using data provided by the drug-drug-interaction challenge 2013. Ensemble methods aggregate several classifiers into one model, increasing robustness by reducing the risk of choosing an inappropriate single classifier. Second, this work discusses the problem of applying relationship extraction to documents with unknown text characteristics. Robustness of a text mining component is assessed by cross-learning, where a model is evaluated on a corpus different from the training corpus. We apply self-training, a semi-supervised learning technique, in order to increase cross-learning performance and show that it is more robust in comparison to a classifier trained on manually annotated text only. Third, we investigate the use of distant supervision to overcome the need of manually annotated training instances. Corpora derived by distant supervision are inherently noisy, thus benefiting from robust relationship extraction methods. We compare two different methods and show that both approaches achieve similar performance as fully supervised classifiers, evaluated in the cross-learning scenario. To facilitate the usage of information extraction results, including those developed within this thesis, we develop the semantic search engine GeneView. We discuss computational requirements to build this resource and present some applications utilizing the data extracted by different text-mining components.

Die Telekommunikation und die ihr zuliefernde Industrie stellen einen softwareintensiven Bereich dar - der durch einen sehr hohen Anteil von Eigenentwicklungen gekennzeichnet ist. Eine wesentliche Ursache dafür sind spezielle Anforderungen an Telekommunikationssoftwaresysteme, die i.allg. nicht durch Standardsoftwareprodukte sichergestellt werden können. Diese Anforderungen ergeben sich aus den besonderen Eigenschaften solcher Softwaresysteme wie die Verteilung der Komponenten von Softwaresystemen sowie die Verteilung der Entwicklung dieser Komponenten, die Heterogenität der Entwicklungs- und Einsatzumgebungen für diese Komponenten und die Komplexität der entwickelten Softwaresysteme hinsichtlich nichtfunktionaler Charakteristika. Die industrielle Entwicklung von Telekommunikationssoftwaresystemen ist ein schwieriger und bisher nicht zufriedenstellend gelöster Prozeß. Aktuelle Forschungsarbeiten thematisieren Softwareentwicklungsprozesse und -techniken sowie unterstützende Werkzeuge zur Erstellung und Integration wiederverwendbarer Softwarekomponenten ("Componentware"). Das Ziel dieser Dissertation besteht in der Unterstützung der industriellen Entwicklung offener, verteilter Telekommunikationssoftwaresysteme. Dazu wird die Entwicklungstechnik Objektorientierte Modellierung mit dem Einsatz von Komponentenarchitekturen durch die automatische Ableitung von Softwarekomponenten aus Modellen zusammengeführt. Die zentrale Idee ist dabei eine präzise Definition der zur Entwicklung von verteilten Softwaresystemen einsetzbaren Modellierungskonzepte in Form eines Metamodells. Von diesem Metamodell ausgehend werden dann zur Konstruktion und Darstellung objektorientierter Entwurfsmodelle eine graphische und eine textuelle Notation definiert. Da die Notationen die Konzepte des Meta- Modells visualisieren, haben sie diesem gegenüber einen sekundären Charakter. Für die Transformation von Entwurfsmodellen in ausführbare Applikationen wurde auf der Grundlage von CORBA eine Komponentenplattform realisiert, die zusätzlich zu Interaktionen zwischen verteilten Softwarekomponenten auch Entwicklungs-, Deployment- und Ausführungsaspekte unterstützt. Wiederum ausgehend vom Metamodell wird durch die Anwendung wohldefinierter Ableitungsregeln die automatische Überführung von Entwurfsmodellen in Softwarekomponenten des zu entwickelnden Systems ermöglicht. Die von den Autoren erarbeiteten Konzeptionen und Vorgehensweisen wurden praktisch in eine Werkzeugumgebung umgesetzt, die sich bereits erfolgreich in verschiedenen Softwareentwicklungsprojekten bewährt hat. / The telecommunication industry and their suppliers form a software intensive domain. In addition, a high percentage of the software is developed by the telecommunication enterprises themselves. A main contributing factor for this situation are specific requirements to telecommunication software systems which cannot be fulfilled by standard off-the-shelf products. These requirements result from particular properties of those software systems, e.g. distributed development and execution of their components, heterogeneity of execution and development environments and complex non-functional characteristics like scalability, reliability, security and manageability. The development of telecommunication software systems is a complex process and currently not satisfactory realized. Actual research topics in this arena are software development processes and development techniques as well as tools which support the creation and integration of reusable software components (component ware). The goal of this thesis work is the support of the industrial development and manufacturing of open distributed telecommunication software systems. For that purpose, the development technique object oriented modelling and the implementation technique usage of component architectures are combined. The available modelling concepts are precisely defined as a metamodel. Based on that metamodel, graphical and textual notations for the presentation of models are developed. To enable a smooth transition from object oriented models into executable components a component architecture based on CORBA was also developed as part of the thesis. This component architecture covers besides the interaction support for distributed components deployment and execution aspects. Again on the basis of the metamodel code generation rules are defined which allow to automate the transition from models to components. The development techniques described in this thesis have been implemented as a tool chain. This tool chain has been successfully used in several software development projects.

Die Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemerédi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphen mit derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurden Regularitätslemmata für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen und dünne Graphen verallgemeinert. Ziel der vorliegenden Arbeit ist die Weiterentwicklung der Regularitätsmethode und deren Anwendung auf Probleme der theoretischen Informatik. Im Besonderen wird gezeigt, dass vererbbare (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche solche Eigenschaften haben und solchen die „weit“ davon entfernt sind, unterscheidet. / About 30 years ago Szemerédi developed the regularity method for graphs, which was a key ingredient in the proof of his famous density result concerning the upper density of subsets of the integers which contain no arithmetic progression of fixed length. Roughly speaking, the regularity lemma asserts, that the vertex set of every graph can be partitioned into a constant number of classes such that almost all of the induced bipartite graphs are quasi-random, i.e., they mimic the behavior of random bipartite graphs of the same density. The regularity lemma had have many applications mainly in extremal graph theory, but also in theoretical computer science and additive number theory, and it is considered one of the central tools in modern graph theory. A few years ago the regularity method was extended to other discrete structures. In particular extensions for uniform hypergraphs and sparse graphs were obtained. The main goal of this thesis is the further development of the regularity method and its application to problems in theoretical computer science. In particular, we will show that hereditary, decidable properties of hypergraphs, that are properties closed under isomorphism and vertex removal, are testable. I.e., there exists a randomised algorithm with constant running time, which distinguishes between Hypergraphs displaying the property and those which are “far” from it.

Diese Arbeit nutzt und verfeinert Methoden der Komplexitätstheorie, um mit diesen die Komplexität dünner Instanzen zu untersuchen. Dazu gehören etwa Graphen mit wenigen Kanten oder Formeln mit wenigen Bedingungen beschränkter Weite. Dabei ergeben sich zwei natürliche Fragestellungen: (a) Gibt es einen effizienten Algorithmus, der beliebige Instanzen eines NP-schweren Problems auf äquivalente, dünne Instanzen reduziert? (b) Gibt es einen Algorithmus, der dünne Instanzen NP-schwerer Probleme bedeutend schneller löst als allgemeine Instanzen gelöst werden können? Wir formalisieren diese Fragen für verschiedene Probleme und zeigen, dass positive Antworten jeweils zu komplexitätstheoretischen Konsequenzen führen, die als unwahrscheinlich gelten. Frage (a) wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine NP-schwere Sprache entscheiden möchten und dabei möglichst wenig kommunizieren. Unter der komplexitätstheoretischen Annahme, dass coNP keine Teilmenge von NP/poly ist, erhalten wir aus unseren Ergebnissen erstaunlich scharfe untere Schranken für interessante Parameter aus verschiedenen Teilgebieten der theoretischen Informatik. Im Speziellen betrifft das die Ausdünnung von Formeln, die Kernelisierung aus der parameterisierten Komplexitätstheorie, die verlustbehaftete Kompression von Entscheidungsproblemen, und die Theorie der probabilistisch verifizierbaren Beweise. Wir untersuchen Fragestellung (b) anhand der Exponentialzeitkomplexität von Zählproblemen. Unter (Varianten) der bekannten Exponentialzeithypothese (ETH) erhalten wir exponentielle untere Schranken für wichtige #P-schwere Probleme: das Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel, das Berechnen der Zahl aller unabhängigen Mengen in einem Graphen, das Berechnen der Permanente einer Matrix mit Einträgen 0 und 1, das Auswerten des Tuttepolynoms an festen Punkten. / In this thesis, we use and refine methods of computational complexity theory to analyze the complexity of sparse instances, such as graphs with few edges or formulas with few constraints of bounded width. Two natural questions arise in this context: (a) Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances? (b) Is there an algorithm that solves sparse instances of an NP-hard problem significantly faster than general instances can be solved? We formalize these questions for different problems and show that positive answers for these formalizations would lead to consequences in complexity theory that are considered unlikely. Question (a) is modeled by a communication process, in which two players want to cooperatively decide an NP-hard language and at the same time communicate as few as possible. Under the complexity-theoretic hypothesis that coNP is not in NP/poly, our results imply surprisingly tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. We study the question (b) for counting problems in the exponential time setting. Assuming (variants of) the exponential time hypothesis (ETH), we obtain asymptotically tight, exponential lower bounds for well-studied #P-hard problems: Computing the number of satisfying assignments of a 2-CNF formula, computing the number of all independent sets in a graph, computing the permanent of a matrix with entries 0 and 1, evaluating the Tutte polynomial at fixed evaluation points.

Mit dem Resource Description Framework (RDF) können Eigenschaften von und die Beziehungen zwischen Ressourcen maschinenverarbeitbar beschrieben werden. Dadurch werden diese Daten für Maschinen zugänglicher und können unter anderem automatisch Daten zu einer Ressource lokalisieren und verarbeiten, unterschiedliche Bedeutungen einer Zeichenkette erkennen und implizite Informationen ableiten. Das Datenmodell von RDF und der zugehörigen Anfragesprache SPARQL basiert auf gerichteten und beschrifteten Multigraphen. Forschungsergebnisse haben gezeigt, dass relationale DBMS zum Verwalten von RDF-Daten ungeeignet sind. Native basierende RDF-DBMS können Anfragen in kürzerer Zeit verarbeiten. Der Leistungsgewinn wird durch redundantes Speichern von Tripeln in mehreren B+-Bäumen erzielt. Jedoch sind Join-ähnliche Operationen zum Berechnen des Ergebnisses erforderlich, was bei größeren Anfragen zu Leistungseinbußen führt. In dieser Arbeit wird der Resource Centered Store (RCS) entwickelt, dessen Speichermodell RDF-inhärente Eigenschaften ausnutzt, um Anfragen ohne die Notwendigkeit redundanter Speicherung effizient beantworten zu können. Die grundlegende Idee des RCS-Speichermodells besteht im Gruppieren der Daten als sternförmigen Teilgraphen auf Datenbankseiten. Die verwendeten Prinzipien ähnelt denen in RDBMS und daher können deren Algorithmen zur Beantwortung von Anfragen wiederverwendet werden. Darüber hinaus werden Transformationsregeln und Heuristiken zum Optimieren von SPARQL-Anfragen zum Finden eines möglichst optimalen Ausführungsplans definiert. In diesem Kontext wurden auch graphmusterbasierte Indexe spezifiziert und deren Nutzen für die Verarbeitung von Anfragen untersucht. Das RCS-Speichermodell wurde prototypisch implementiert und im Vergleich zum nativen RDF-DBMS Jena TDB evaluiert. Die durchgeführten Experimenten zeigen, dass das System insbesondere für das Beantworten von Anfragen mit großen sternförmigen Teilmustern geeignet ist. / The Resource Description Framework (RDF) is the conceptual foundation for representing properties of real-world or virtual resources and describing the relationships between them. Standards based on RDF allow machines to access and process information automatically and locate additional data about resources. It also supports the discovery of relationships between concepts. The smallest information unit in RDF are triples which form a directed labeled multi-graph. The query language SPARQL is also based on a graph model which makes it difficult for relational DBMS to store and query RDF data efficiently. The most performant DBMS for managing and querying RDF data implement a RDF-specific storage model based on a set of B+ tree indexes. The key disadvantages of these systems are the increased usage of secondary storage in cause of redundantly stored triples as well as the necessity of expensive join operation to compute the solutions of a SPARQL query. In this work we develop and describe the Resource Centered Store which exploits RDF inherent characteristics to avoid the requirement for storing triples redundantly while improving the query performance of larger queries. In the RCS storage model triples are grouped by their first component (subject) and storing these star-shaped subgraphs on database pages -- similar to relational DBMS. As a result the RCS can benefit from principles and algorithms that have been developed in the context of relational databases. Additionally, we defined transformation rules and heuristics to optimize SPARQL queries and generate an efficient query execution plan. In this context we also defined graph pattern based indexes and investigated their benefits for computing the solutions of queries. We implemented the RCS storage model prototypically and compared it to the native RDF DBMS Jena TDB. Our experiments showed that our storage model is especially suited to speed up the query performance of large star-shaped graph pattern.

Die vorliegende Dissertation hat einen technologischen und einen anwendungsbezogenen Schwerpunkt. Technologisch ordnen sich die präsentierten Forschungsergebnisse in das Gebiet der "Swarm Intelligence" (dt.: Schwarm-Intelligenz) ein. Swarm Intelligence ist ein Teilbereich der Informatik, der sich an der Überschneidung zwischen der Multi-Agenten Systeme Forschung der Künstlichen Intelligenz und dem Forschungsgebiet "Artificial Life" (dt.: Künstliches Leben) befindet. Im Gegensatz zur Swarm Intelligence im allgemeinen, überträgt der spezielle Ansatz "Synthetic Ecosystems" (dt.: synthetische Ökosysteme) nicht nur Koordinationsmechanismen aus biologischen Multi-Agenten Systemen, wie zum Beispiel Insekten Kolonien, in den Entwurf künstlicher Systeme. Vielmehr sollen die grundlegenden Prinzipien "natürlich" entstandener komplexer Systeme, also auch zum Beispiel einer Aktienbörse, übernommen werden. Als anwendungsbezogener Hintergrund der Dissertation wurde die verteilte Steuerung moderner industrieller Fertigungsanlagen gewählt. Die Fertigungssteuerung ist ein geeignetes Anwendungsfeld für die Technologien, die im Rahmen der Forschungsarbeiten entwickelt wurden. Damit dient die Präsentation eines synthetischen Ökosystems für die Fertigungssteuerung der Demonstration des neuartigen Ansatzes zum Entwurf, Realisierung und Evaluierung komplexer, industriell relevanter Systeme. Gleichzeitig leistet die vorgestellte Architektur der Fertigungssteuerung und die darin verwandten Koordinationsverfahren einen Beitrag zur Weiterentwicklung holonischer Produktionssysteme. Der holonische Ansatz zur Produktionsplanung und -steuerung genießt derzeit große Aufmerksamkeit sowohl in der Forschung als auch in der Industrie. Als Teilgebiet der Entwicklung intelligenter Fertigungssysteme (engl.: IMS - Intelligent Manufacturing Systems), propagiert der holonische Ansatz eine Abkehr von der traditionell zentralistischen und hierarchischen Planung und Steuerung hin zu selbst-organisierenden Systemen autonom (inter-)agierender Individuen ("Holone"). Bei der praktischen Umsetzung holonischer Systeme werden sehr häufig Technologien aus der Multi-Agenten Systeme Forschung angewandt. Mit dieser Dissertation rücken auch synthetische Ökosysteme in das Blickfeld holonischer Systeme. Natürliche Agentensysteme im allgemeinen und Kolonien sozialer Insekten im besonderen faszinieren durch ihre Robustheit, ihre Flexibilität und ihre Anpassungsfähigkeit. Solche Systeme bestehen häufig aus sehr vielen, sehr einfachen Individuen und doch weisen sie ein komplexes und koordiniertes Gesamtverhalten auf. Es gibt mehrere Zweige in unterschiedlichen Wissenschaften, zum Beispiel in der Biologie, Physik, Ökonomie oder in der Informatik, die sich mit verteilten Systemen lokal interagierender Individuen beschäftigen. Ihre Erforschung resultiert in einer Reihe wiederholt beobachteter grundlegender Eigenschaften. Um künstlich erschaffene Systeme mit ähnlichen Eigenschaften auszustatten werden Entwurfsprinzipien für das Design von Multi-Agenten Systemen in dieser Dissertation vorgeschlagen. Jedes Entwurfsprinzip wird systematisch eingeführt, motiviert und in seinen Konsequenzen für Anwendungen in der Fertigungssteuerung diskutiert. Stigmergie ist ein grundlegendes Konzept der Koordination einer großen Anzahl von Individuen unter anderem in Kolonien sozialer Insekten. Die Formulierung dieses Konzepts ist auf den Biologen Grassè zurückzuführen, welcher in der Mitte des zwanzigsten Jahrhunderts das Schwarmverhalten von Termiten untersuchte. Stigmergie beruht auf der Tatsache, daß das Verhalten eines jeden Individuums durch die aktuelle Konfiguration seiner lokalen Umwelt bestimmt wird. Die Umwelt wiederum, wird durch die Aktivitäten der Individuen verändert. Diese Wechselwirkung führt in Verbindung mit entsprechend ausgelegten individuellen Verhaltensmustern zur Emergenz einer global koordinierten Erfüllung der anstehenden Aufgaben der Kolonie. Im Detail wird sematektonische von marker-basierter Stigmergie unterschieden, wobei bei sematektonischer Stigmergie der Zustand der Aufgabenerfüllung selbst (z.B. Stand des Nestbaus) das Individualverhalten beeinflußt, während marker-basierte Stigmergie aufgabenunabhängige Marker (z.B. Pheromone) in der Umwelt platziert. Multi-Agenten Systeme finden ihre Realisierung in Software, welche gegebenenfalls an physische Aktuatoren gekoppelt ist. Im allgemeinen besteht diese Software aus einer Laufzeitumgebung und den darin ausgeführten Agenten. Die vorliegende Dissertation präsentiert eine Erweiterung von Laufzeitumgebungen um eine anwendungsunabhängige Pheromon Infrastruktur (PI). Die PI ermöglicht es den Softwareagenten des jeweiligen synthetischen Ökosystems, künstliche Pheromone als Datenstrukturen in einem virtuellen Raum abzulegen und wahrzunehmen. Diese Datenstrukturen dienen als Marker in stigmergetischen Koordinationsmechanismen. Die Algorithmen der PI operieren auf diesen künstlichen Pheromonen und emulieren die natürlichen Vorgänge der räumlichen Ausbreitung und Verdunstung von Pheromonen auf abstrakter Ebene. Zusätzlich wird das natürliche Vorbild um eine automatische Aufbereitung von Informationen erweitert. Die Funktionalität der PI wird in dieser Dissertation spezifiziert. Des weiteren wird ein formales Modell erstellt, welches die Grundlage einer numerischen Analyse der Eigenschaften der PI bildet. Die Analyse liefert Vorhersagen für das Entstehen von räumlichen Mustern von Pheromonkonzentrationen in der PI. Diese Vorhersagen können dann in der Feineinstellung und der Evaluierung von Koordinationsmechanismen verwendet werden. Außerdem dient das formale Modell als Grundlage für den Beweis der globalen Stabilität der PI. Damit ist gesichert, daß unabhängig von der gewählten räumlichen Struktur und den von der jeweiligen Anwendung generierten Pheromonen die Konzentrationen der Pheromone immer in ihrer Stärke begrenzt sind. Der Beweis der globalen Stabilität ist eine wichtige Voraussetzung für die Verwendung der PI in praktischen Anwendungen. Die Spezifikation einer verteilten Realisierung der PI bildet den Abschluß der allgemeinen Betrachtung. Die Agenten, welche die (virtuelle) räumliche Struktur der PI widerspiegeln, werden im Detail spezifiziert. Auf der Basis dieser Spezifikation ist im Rahmen der Dissertation ein Prototyp der PI realisiert worden. Dieser Prototyp diente dem Nachweis des vorhergesagten Verhaltens der Infrastruktur und der späteren Evaluierung des entwickelten Fertigungssteuerungssystems. Im weiteren Verlauf der vorliegenden Dissertation wird ein neuartiger Ansatz zur Fertigungssteuerung betrachtet. Die absehbaren Veränderungen der äußeren Bedingungen der industriellen Produktion, ausgelöst durch den globalen Übergang von Anbieter- zu Verbrauchermärkten, erfordert die Fertigung immer komplexerer und variantenreicherer Produkte in ständig schwankenden Stückzahlen und deutlich verkürzten Lebenszyklen bei gleichzeitig sinkenden Kosten. Zur Erfüllung dieser Anforderungen in der Massenproduktion wandelt sich die traditionell starr verkettete Strangfertigung (z.B. Transferstraßen) zur flexiblen Fließfertigung (z.B. flexible Bearbeitungszentren). Die Steuerung einer flexiblen Fließfertigung erfordert neue Herangehensweisen. In einer holonischen Fertigung, zum Beispiel, organisiert sich die Produktionsplanung und Produktionssteuerung selbst um die Erfüllung der aktuellen Aufträge. Dabei werden in der Steuerung verteilte, reaktive Verfahren verwendet, welche eine deutlich gesteigerte Robustheit und Flexibilität gegenüber Störungen und Veränderungen aufweisen. Der Übergang zur flexiblen Fließfertigung bedeutet die Einführung von Flexibilität in der Bearbeitung aber auch im Transport des Materials. Es ist eine grundlegende Eigenschaft dieser Fertigungssysteme, daß zu einem beliebigen Zeitpunkt eine Reihe möglicher Transportwege und damit eine Vielzahl möglicher Muster im Materialfluß zur Verfügung stehen. Dabei führt aber nur eine kleine Menge dieser Muster zu einer bestmöglichen Erfüllung der globalen Produktionsziele (z.B. hoher globaler Durchsatz). Es ist also die Aufgabe der Fertigungssteuerung in jeder Situation das bestmögliche Materialflußmuster zu erreichen. Ist ein verteilter Ansatz für die Steuerung gewählt worden, so muß diese Optimierung nach globalen Produktionszielen in die lokalen Steuerungsentscheidungen integriert werden, ohne die Autonomie der lokalen Einheiten zu verletzen. Die Dissertation präsentiert ein sogenanntes geführtes Fertigungssteuerungssystem (GFSS), welches einen verteilten und reaktiven Steuerungsansatz mit einer Flußoptimierung unter Beachtung globaler Produktionsziele in neuartiger Weise verbindet. Der Entwurf des GFSS folgte den vorgeschlagenen Prinzipien für synthetische Ökosysteme und die Agenten im GFSS werden mit Hilfe der Pheromon Infrastruktur koordiniert. Die Agenten und Pheromone des GFSS werden detailliert spezifiziert und in einem realistischen Beispiel aus der Automobilindustrie evaluiert. In der Evaluierung wird von den Ergebnissen der Analyse der PI Gebrauch gemacht. Die dabei gewählte numerische Beschreibung des Einzelverhaltens und die darauf aufbauende Betrachtung des emergierenden Gesamtverhaltens weist den Weg zu einer systematischen Evaluierung von emergenten Systemeigenschaften in synthetischen Ökosystemen. In einem abschließenden Kapitel werden die drei inhaltlichen Schwerpunkte der Dissertation noch einmal betrachtet. Vor dem Hintergrund des GFSS werden die vorgeschlagenen Entwurfsprinzipien für synthetische Ökosysteme systematisch auf ihre Anwendbarkeit und praktische Bedeutung hin überprüft. Außerdem wird die allgemeine Verwendung der PI für den Austausch von Informationen zwischen Agenten untersucht. Und schließlich wird die Fertigungssteuerung aus der Sicht abstrakter Zustandsräume diskutiert. Die vorliegende Dissertation weist den Weg für eine Reihe weiterführender Forschungsarbeiten. So werden zum einen detaillierte Konzepte für die Erweiterung des GFSS um eine automatische Strategiebewertung und -generierung und um ein Visualisierungssystem vorgestellt. Zum anderen werden aber auch notwendige Ergänzungen der Entwurfsprinzipien und mögliche Verbesserungen der PI und des darauf basierenden Evaluierungsansatzes vorgeschlagen. / The synthetic ecosystems approach attempts to adopt basic principles of natural ecosystems in the design of multiagent systems. Natural agent systems like insect colonies are fascinating in that they are robust, flexible, and adaptive. Made up of millions of very simple entities, these systems express a highly complex and coordinated global behavior. There are several branches in different sciences, for instance in biology, physics, economics, or in computer science, that focus on distributed systems of locally interacting entities. Their research yields a number of commonly observed characteristics. To supply engineered systems with similar characteristics this thesis proposes a set of principles that should be observed when designing synthetic ecosystems. Each principle is systematically stated and motivated, and its consequences for the manufacturing control domain are discussed. Stigmergy has shown its usefulness in the coordination of large crowds of agents in a synthetic ecosystem. Sign-based stigmergy through synthetic pheromones is supported by an extension to runtime environments for software agents called the pheromone infrastructure. In this thesis the operation of the pheromone infrastructure is specified, formally modeled and analyzed, and an implementation is presented. The guided manufacturing control system for flexible flow shops is designed following the proposed principles and it uses the pheromone infrastructure to coordinate its agents. It comprises two subsystems. The control (sub)system, which enables production, is distributed and reactive. The advisory (sub)system observes the operation of the control system and advises the manufacturing execution under global considerations. This thesis specifies the guided manufacturing control system and evaluates its operation in a simple but realistic example adapted from the automotive industry. The applicability of the design principles, the usage of the pheromone infrastructure, and the operation of manufacturing control in abstract state spaces are considered on the basis of the guided manufacturing control system.

Die Untersuchung des Phänotyps bringt z.B. bei genetischen Krankheiten ein Verständnis der zugrunde liegenden Mechanismen mit sich. Aufgrund dessen wurden neue Technologien wie RNA-Interferenz (RNAi) entwickelt, die Genfunktionen entschlüsseln und mehr phänotypische Daten erzeugen. Interpretation der Ergebnisse solcher Versuche ist insbesondere bei heterogenen Daten eine große Herausforderung. Wenige Ansätze haben bisher Daten über die direkte Verknüpfung von Genotyp und Phänotyp hinaus interpretiert. Diese Dissertation zeigt neue Methoden, die Entdeckungen in Phänotypen über Spezies und Methodik hinweg ermöglichen. Es erfolgt eine Erfassung der verfügbaren Datenbanken und der Ansätze zur Analyse ihres Inhalts. Die Grenzen und Hürden, die noch bewältigt werden müssen, z.B. fehlende Datenintegration, lückenhafte Ontologien und der Mangel an Methoden zur Datenanalyse, werden diskutiert. Der Ansatz zur Integration von Genotyp- und Phänotypdaten, PhenomicDB 2, wird präsentiert. Diese Datenbank assoziiert Gene mit Phänotypen durch Orthologie über Spezies hinweg. Im Fokus sind die Integration von RNAi-Daten und die Einbindung von Ontologien für Phänotypen, Experimentiermethoden und Zelllinien. Ferner wird eine Studie präsentiert, in der Phänotypendaten aus PhenomicDB genutzt werden, um Genfunktionen vorherzusagen. Dazu werden Gene aufgrund ihrer Phänotypen mit Textclustering gruppiert. Die Gruppen zeigen hohe biologische Kohärenz, da sich viele gemeinsame Annotationen aus der Gen-Ontologie und viele Protein-Protein-Interaktionen innerhalb der Gruppen finden, was zur Vorhersage von Genfunktionen durch Übertragung von Annotationen von gut annotierten Genen zu Genen mit weniger Annotationen genutzt wird. Zuletzt wird der Prototyp PhenoMIX präsentiert, in dem Genotypen und Phänotypen mit geclusterten Phänotypen, PPi, Orthologien und weiteren Ähnlichkeitsmaßen integriert und deren Gruppierungen zur Vorhersage von Genfunktionen, sowie von phänotypischen Wörtern genutzt. / In diseases with a genetic component, examination of the phenotype can aid understanding the underlying genetics. Technologies to generate high-throughput phenotypes, such as RNA interference (RNAi), have been developed to decipher functions for genes. This large-scale characterization of genes strongly increases phenotypic information. It is a challenge to interpret results of such functional screens, especially with heterogeneous data sets. Thus, there have been only few efforts to make use of phenotype data beyond the single genotype-phenotype relationship. Here, methods are presented for knowledge discovery in phenotypes across species and screening methods. The available databases and various approaches to analyzing their content are reviewed, including a discussion of hurdles to be overcome, e.g. lack of data integration, inadequate ontologies and shortage of analytical tools. PhenomicDB 2 is an approach to integrate genotype and phenotype data on a large scale, using orthologies for cross-species phenotypes. The focus lies on the uptake of quantitative and descriptive RNAi data and ontologies of phenotypes, assays and cell-lines. Then, the results of a study are presented in which the large set of phenotype data from PhenomicDB is taken to predict gene annotations. Text clustering is utilized to group genes based on their phenotype descriptions. It is shown that these clusters correlate well with indicators for biological coherence in gene groups, such as functional annotations from the Gene Ontology (GO) and protein-protein interactions. The clusters are then used to predict gene function by carrying over annotations from well-annotated genes to less well-characterized genes. Finally, the prototype PhenoMIX is presented, integrating genotype and phenotype data with clustered phenotypes, orthologies, interaction data and other similarity measures. Data grouped by these measures are evaluated for theirnpredictiveness in gene functions and phenotype terms.