Super-/substring problems and super-/subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. Here we investigate the complexity of a new type of such problem that forms a combination of a super-/substring and a super-/subsequence problem. Moreover we introduce different types of minimal superstring and maximal substring problems. In particular, we consider the following problems: given a set L of strings and a string S, (i) find a minimal superstring (or maximal substring) of L that is also a supersequence (or a subsequence) of S, (ii) find a minimal supersequence (or maximal subsequence) of L that is also a superstring (or a substring) of S. In addition some non-super-/non-substring and non-super-/non-subsequence variants are studied. We obtain several NP-hardness or even MAX SNP-hardness results and also identify types of “weak minimal” superstrings and “weak maximal” substrings for which (i) is polynomial-time solvable.

So far only few performance studies on parallel object-relational database systems are available. In particular, the relative performance of relational vs. reference-based join processing in a parallel environment has not been investigated sufficiently. We present a performance study based on the BUCKY benchmark to compare parallel join processing using reference attributes with relational hash- and merge-join algorithms. In addition, we propose a data allocation scheme especially suited for object hierarchies and set-valued attributes.

For complex queries in parallel database systems, substantial amounts of data must be redistributed between operators executed on different processing nodes. Frequently, such intermediate results cannot be held in main memory and must be stored on disk. To limit the ensuing performance penalty, a data allocation must be found that supports parallel I/O to the greatest possible extent. In this paper, we propose declustering even self-contained units of temporary data processed in a single operation (such as individual buckets of parallel hash joins) across multiple disks. Using a suitable analytical model, we find that the improvement of parallel I/O outweighs the penalty of increased fragmentation.

Skew effects are a serious problem in parallel database systems, but the relationship between different skew types and load balancing methods is still not fully understood. We develop and compare two classifications of skew effects and load balancing strategies, respectively, to match their relevant properties. Our conclusions highlight the importance of highly dynamic scheduling to optimize both the complexity and the success of load balancing. We also suggest the tuning of database schemata as a new anti-skew measure.

This paper presents an approach for exchanging presence information between users of an instant messaging system in a mobile ad hoc network. As major feature, presence information is transferred when mobile users get in direct contact, similar to the spread of an infections disease. By exploiting node mobility, presence information is epidemically distributed throughout the network, effectively overcoming network partitions. We show how to apply the Passive Distributed Indexing Protocol, which implements a general-purpose lookup service for mobile applications building upon epidemic data dissemination, for implementing the exchange of presence information. The effectiveness of the approach is illustrated in a simulation study using the network simulator ns-2. Building upon the results, we present the architecture of a mobile instant messaging system that supports the widely adopted Extensible Messaging and Presence Protocol (XMPP), an IETF standardized protocol for instant messaging.

Behandelt werden - Anforderungen an Mehrrechner-DBS - Klassifikation - Verteilte und Parallele DBS - Katalogverwaltung, Namensverwaltung, Schemaarchitektur - Datenallokation in VDBS und PDBS - Verteilte und parallele Anfrageverarbeitung - Transaktionsverwaltung: Deadlock-Behandlung, Commit-Protokolle - Replizierte Datenbanken - Shared-Disk-DBS

1. Architektur von DBS: Schichtenmodelle 2. E/A-Architekturen und Speicherhierarchien - Speichertechnologien - Disk-Arrays - Nutzung nicht-flüchtiger Halbleiterspeicher 3. Speicher- und Seitenzuordnung - Dateikonzept - Update-in-Place - Schattenspeicherkonzept 4. DBS-Pufferverwaltung - Nutzung von Lokalität - Speicherzuordnung - Ersetzungsverfahren

1. Klassen und Einsatzfelder von DBS - Anforderungen neuartiger DB-Anwendungen (CAD etc.) - Beschränkungen des Relationemodells - Datenmodelle: Semantische DM, Objektorientierte DBS, Objektrelationale DBS, Deduktive DBS - Anwendungsfelder: Information-Retrieval, Multimedia-DBS, GIS, Decision Support / Data Warehouses 2. Grundkonzepte von objektorientierten DBS - Grundlagen und Konzepte - Struktureigenschaften - Objektorientierte Verarbeitung 3. ODMG-Standard - Kooperation in heterogenen Umgebungen (CORBA-Standard) - Objektmodell - Objektdefinition (ODL) - Anfragesprache (OQL) 4. Beispielrealisierungen von OODBS - NF² - GemStone - O2

1 Grundbegriffe des relationalen Modells - 2 Einstellige Operatoren - 3 Zweistellige Operatoren - 4 Weiter über Operatoren - 5 Anwendungsbeispiele - 6 Testaufgaben

Das Leistungsverhalten moderner kommerzieller Großrechner wird in ganz besonderem Maße durch die eingesetzte Ein-/Ausgabe (E/A)-Architektur mitbestimmt. Auf diesem Gebiet haben die S/390- und zSeries-Rechner eine Führungsposition mit inne, die auf einer ganzen Reihe von Einrichtungen beruht, die in anderen Rechnerarchitekturen (zum Teil noch) nicht verfügbar sind. Hierzu gehören neben Anderem ein getrenntes E/A-Kanal-Subsystem, das parallel zur CPU arbeitet, die Möglichkeit, über unterschiedliche Pfade dynamisch auf den gleichen Plattenspeicher zuzugreifen, oder eine Prioritätssteuerung, die über einen Work Load Manager eine kontinuierliche Anpassung der E/A-Ressourcen an sich dynamisch ändernde Belastungsprofile ermöglicht. Der vorliegende Beitrag enthält eine Übersicht über moderne E/A-Einrichtungen am Beispiel der S/390- und zSeries-Rechner und ihre Zuordnung in dem kommenden InfiniBand-Standard.