Skew effects are still a significant problem for efficient query processing in parallel database systems. Especially in shared-nothing environments, this problem is aggravated by the substantial cost of data redistribution. Shared-disk systems, on the other hand, promise much higher flexibility in the distribution of workload among processing nodes because all input data can be accessed by any node at equal cost. In order to verify this potential for dynamic load balancing, we have devised a new technique for skew-tolerant join processing. In contrast to conventional solutions, our algorithm is not restricted to estimating processing costs in advance and assigning tasks to nodes accordingly. Instead, it monitors the actual progression of work and dynamically allocates tasks to processors, thus capitalizing on the uniform access pathlength in shared-disk architectures. This approach has the potential to alleviate not only any kind of data-inherent skew, but also execution skew caused by query- external workloads, by disk contention, or simply by inaccurate estimates used in predictive scheduling. We employ a detailed simulation system to evaluate the new algorithm under different types and degrees of skew.

Shared Disk database systems offer a high flexibility for parallel transaction and query processing. This is because each node can process any transaction, query or subquery because it has access to the entire database. Compared to Shared Nothing, this is particularly advantageous for scan queries for which the degree of intra-query parallelism as well as the scan processors themselves can dynamically be chosen. On the other hand, there is the danger of disk contention between subqueries, in particular for index scans. We present a detailed simulation study to analyze the effectiveness of parallel scan processing in Shared Disk database systems. In particular, we investigate the relationship between the degree of declustering and the degree of scan parallelism for relation scans, clustered index scans, and non-clustered index scans. Furthermore, we study the usefulness of disk caches and prefetching for limiting disk contention. Finally, we show the importance of dynamically choosing the degree of scan parallelism to control disk contention in multi-user mode.

本研究之主要目標在於建構一個能評估分散式關聯資料庫中之特色的需求導向績效評估方法。在過去的績效評估研究中，已經有許多人對於關聯式資料庫績效評估做了多方面的努力。但是，過去的關聯式資料庫資效評估方法如：Wisconsin、AS3AP、TPC系列的Benchmarks都有著一些限制及不足的地方。 過去的關聯式資料庫績效評估方法並無法完全的評估出分散式資料庫的特殊需求及其表現。所以本研究嘗試要建立出一個能專門適用於分散式資料庫導向的績效評估方法。為了要作出此績效評估方法，本研究採用了工作量模式的研究方法。先建出分散式資料庫績效評估的工作量模式，再以其來實作出績效評估方法。工作量模式分成三部分：資料模式、交易模式、控制模式。 / This thesis is intended to design a requirements-centric database benchmark, which can evaluate the general performance of the distributed relational database systems. In the past, there are many relational database benchmarks. But the relational database benchmarks like Wisconsin, AS3AP, TPC, TP1 have some constraints. In this study, we aim to design a general-purpose distributed database workload model and implement it. To design this benchmark, we need to build our workload model. The workload model consists of three components：data model, transaction model, control model. Each model has the requirement specification language to accommodate user's workloads.

Im Kontext von In-Memory-Datenbanksystemen nehmen leichtgewichtige Kompressionsalgorithmen eine entscheidende Rolle ein, um eine effiziente Speicherung und Verarbeitung großer Datenmengen im Hauptspeicher zu realisieren. Verglichen mit klassischen Komprimierungstechniken wie z.B. Huffman erzielen leichtgewichtige Kompressionsalgorithmen vergleichbare Kompressionsraten aufgrund der Einbeziehung von Kontextwissen und erlauben eine schnellere Kompression und Dekompression. Die Vielfalt der leichtgewichtigen Kompressionsalgorithmen hat in den letzten Jahren zugenommen, da ein großes Optimierungspotential über die Einbeziehung des Kontextwissens besteht. Um diese Vielfalt zu bewältigen haben wir uns mit der Modularisierung von leichtgewichtigen Kompressionsalgorithmen beschäftigt und ein allgemeines Kompressionsschema entwickelt. Durch den Austausch einzelner Module oder auch nur eingehender Parameter lassen sich verschiedene Algorithmen einfach realisieren.

With the ongoing expansion of information technology, new fields of application requiring data management emerge virtually every day. In our knowledge culture increasing amounts of data and work force organized in more creativity-oriented ways also radically change traditional fields of application and question established assumptions about data management. For instance, investigative analytics and agile software development move towards a very agile and flexible handling of data. As the primary facilitators of data management, database systems have to reflect and support these developments. However, traditional database management technology, in particular relational database systems, is built on assumptions of relatively stable application domains. The need to model all data up front in a prescriptive database schema earned relational database management systems the reputation among developers of being inflexible, dated, and cumbersome to work with. Nevertheless, relational systems still dominate the database market. They are a proven, standardized, and interoperable technology, well-known in IT departments with a work force of experienced and trained developers and administrators. This thesis aims at resolving the growing contradiction between the popularity and omnipresence of relational systems in companies and their increasingly bad reputation among developers. It adapts relational database technology towards more agility and flexibility. We envision a descriptive schema-comes-second relational database system, which is entity-oriented instead of schema-oriented; descriptive rather than prescriptive. The thesis provides four main contributions: (1)~a flexible relational data model, which frees relational data management from having a prescriptive schema; (2)~autonomous physical entity domains, which partition self-descriptive data according to their schema properties for better query performance; (3)~a freely adjustable storage engine, which allows adapting the physical data layout used to properties of the data and of the workload; and (4)~a self-managed indexing infrastructure, which autonomously collects and adapts index information under the presence of dynamic workloads and evolving schemas. The flexible relational data model is the thesis\' central contribution. It describes the functional appearance of the descriptive schema-comes-second relational database system. The other three contributions improve components in the architecture of database management systems to increase the query performance and the manageability of descriptive schema-comes-second relational database systems. We are confident that these four contributions can help paving the way to a more flexible future for relational database management technology.

No description available.

With the ongoing expansion of information technology, new fields of application requiring data management emerge virtually every day. In our knowledge culture increasing amounts of data and work force organized in more creativity-oriented ways also radically change traditional fields of application and question established assumptions about data management. For instance, investigative analytics and agile software development move towards a very agile and flexible handling of data. As the primary facilitators of data management, database systems have to reflect and support these developments. However, traditional database management technology, in particular relational database systems, is built on assumptions of relatively stable application domains. The need to model all data up front in a prescriptive database schema earned relational database management systems the reputation among developers of being inflexible, dated, and cumbersome to work with. Nevertheless, relational systems still dominate the database market. They are a proven, standardized, and interoperable technology, well-known in IT departments with a work force of experienced and trained developers and administrators. This thesis aims at resolving the growing contradiction between the popularity and omnipresence of relational systems in companies and their increasingly bad reputation among developers. It adapts relational database technology towards more agility and flexibility. We envision a descriptive schema-comes-second relational database system, which is entity-oriented instead of schema-oriented; descriptive rather than prescriptive. The thesis provides four main contributions: (1)~a flexible relational data model, which frees relational data management from having a prescriptive schema; (2)~autonomous physical entity domains, which partition self-descriptive data according to their schema properties for better query performance; (3)~a freely adjustable storage engine, which allows adapting the physical data layout used to properties of the data and of the workload; and (4)~a self-managed indexing infrastructure, which autonomously collects and adapts index information under the presence of dynamic workloads and evolving schemas. The flexible relational data model is the thesis\' central contribution. It describes the functional appearance of the descriptive schema-comes-second relational database system. The other three contributions improve components in the architecture of database management systems to increase the query performance and the manageability of descriptive schema-comes-second relational database systems. We are confident that these four contributions can help paving the way to a more flexible future for relational database management technology.

Im Kontext von In-Memory-Datenbanksystemen nehmen leichtgewichtige Kompressionsalgorithmen eine entscheidende Rolle ein, um eine effiziente Speicherung und Verarbeitung großer Datenmengen im Hauptspeicher zu realisieren. Verglichen mit klassischen Komprimierungstechniken wie z.B. Huffman erzielen leichtgewichtige Kompressionsalgorithmen vergleichbare Kompressionsraten aufgrund der Einbeziehung von Kontextwissen und erlauben eine schnellere Kompression und Dekompression. Die Vielfalt der leichtgewichtigen Kompressionsalgorithmen hat in den letzten Jahren zugenommen, da ein großes Optimierungspotential über die Einbeziehung des Kontextwissens besteht. Um diese Vielfalt zu bewältigen haben wir uns mit der Modularisierung von leichtgewichtigen Kompressionsalgorithmen beschäftigt und ein allgemeines Kompressionsschema entwickelt. Durch den Austausch einzelner Module oder auch nur eingehender Parameter lassen sich verschiedene Algorithmen einfach realisieren.:1 Einleitung 1 2 Modularisierung von Komprimierungsmethoden 5 2.1 Zum Literaturstand 5 2.2 Einfaches Schema zur Komprimierung 7 2.3 Weitere Betrachtungen 11 2.3.1 Splitmodul und Wortgenerator mit mehreren Ausgaben 11 2.3.2 Hierarchische Datenorganisation 13 2.3.3 Mehrmaliger Aufruf des Schemas 15 2.4 Bewertung und Begründung der Modularisierung 17 2.5 Zusammenfassung 17 3 Modularisierung für verschiedene Kompressionsmuster 19 3.1 Frame of Reference (FOR) 19 3.2 Differenzkodierung (DELTA) 21 3.3 Symbolunterdrückung 23 3.4 Lauflängenkodierung (RLE) 23 3.5 Wörterbuchkompression (DICT) 24 3.6 Bitvektoren (BV) 26 3.7 Vergleich verschiedener Muster und Techniken 26 3.8 Zusammenfassung 30 4 Konkrete Algorithmen 31 4.1 Binary Packing 31 4.2 FOR mit Binary Packing 33 4.3 Adaptive FOR und VSEncoding 35 4.4 PFOR-Algorithmen 38 4.4.1 PFOR und PFOR2008 38 4.4.2 NewPFD und OptPFD 42 4.4.3 SimplePFOR und FastPFOR 46 4.4.4 Anmerkungen zur differenzkodierten Daten 49 5.4 Simple-Algorithmen 49 4.5.1 Simple-9 49 4.5.2 Simple-16 50 4.5.3 Relative-10 und Carryover-12 52 4.6 Byteorientierte Kodierungen 55 4.6.1 Varint-SU und Varint-PU 56 4.6.2 Varint-GU 56 4.6.3 Varint-PB 59 4.6.4 Varint-GB 61 4.6.5 Vergleich der Module der Varint-Algorithmen 62 4.6.6 RLE VByte 62 4.7 Wörterbuchalgorithmen 63 4.7.1 ZIL 63 4.7.2 Sigmakodierte invertierte Dateien 65 4.8 Zusammenfassung 66 5 Eigenschaften von Komprimierungsmethoden 69 5.1 Anpassbarkeit 69 5.2 Anzahl der Pässe 71 5.3 Genutzte Information 74 5.4 Art der Daten und Arten von Redundanz 74 5.5 Zusammenfassung 77 6 Zusammenfassung und Ausblick 79

A transaction-consistent global checkpoint of a database records a state of the database which reflects the effect of only completed transactions and not the re- sults of any partially executed transactions. This thesis establishes the necessary and sufficient conditions for a checkpoint of a data item (or the checkpoints of a set of data items) to be part of a transaction-consistent global checkpoint of the database. This result would be useful for constructing transaction-consistent global checkpoints incrementally from the checkpoints of each individual data item of a database. By applying this condition, we can start from any useful checkpoint of any data item and then incrementally add checkpoints of other data items until we get a transaction- consistent global checkpoint of the database. This result can also help in designing non-intrusive checkpointing protocols for database systems. Based on the intuition gained from the development of the necessary and sufficient conditions, we also de- veloped a non-intrusive low-overhead checkpointing protocol for distributed database systems. Checkpointing and rollback recovery are also established techniques for achiev- ing fault-tolerance in distributed systems. Communication-induced checkpointing algorithms allow processes involved in a distributed computation take checkpoints independently while at the same time force processes to take additional checkpoints to make each checkpoint to be part of a consistent global checkpoint. This thesis develops a low-overhead communication-induced checkpointing protocol and presents a performance evaluation of the protocol.

Esta tese apresenta um modelo para representação de atividades em aplicações de escritório, próprio para a modelagem dos aspectos dinâmicos dessas aplicações. Os componentes empregados, para tanto, são atividades e objetos de escritório. A modelagem das atividades de uma aplicação, um diagrama de atividades, representa os trâmites dos objetos de escritório, as transformações realizadas sobre os mesmos pelos agentes do escritório, e a tomada de decisão eventualmente presente nas atividades. Tal modelagem de atividades descreve, portanto, a dinâmica dessa aplicação, respeitada a solução organizacional e funcional da empresa e as atribuições e responsabilidades dos agentes que vela trabalham. Objetos de escritório são complexos e podem ter características multimídia. Entretanto, a particularidade mais acentuada desses objetos, que os diferencia dos objetos .do domínio de outras aplicações não convencionais, é a massiva padronização nas descrições dos mesmos, sejam por razões legais, como ofício e requerimento, sejam por razões comerciais, como ata, procuração e recibo. Como conseqüência, objetos de escrit6rios constituem um domínio de classes que permite reutilização intensiva das mesmas, na modelagem de aplicações de escritório. Esse trabalho considera que modelos que se destinem a representar aplicações de escritório devem ter, como um dos objetivos, buscar reutilizar classes de escritório, próprias do domínio do problema. Para esta tese, a biblioteca de classes de escritório, independente das especificidades das aplicações do escritório, deve estar contemplada em um SGBDOO, e seu ambiente de descrição, e o mesmo deve ter, como recurso de descrição, herança múltipla. Atividade é o componente central do modelo delta tese e representa uma interação de um agente com a aplicação, onde objetos de escritórios podem ser criados, consultados, atualizados e destruídos e, ainda, podem ser enviados para outros agentes. Essa interação entre o agente e uma atividade da aplicação é efetivada no lugar de trabalho do agente, ou seja, em sua estação de trabalho. Os tramites dos objetos de escritório são representados, justamente, pelas seqüências possíveis de lugares que os mesmos podem percorrer dentro dos escritórios. A estrutura de dados e os métodos necessários, para que os objetos de escritório possam tratar lugares, são incorporados, por herança múltipla, a partir de uma classe especial chamada lugar de objeto de escritório. Para serem adequadamente empregados na representação da interação dos objetos com as atividades, os métodos pertencentes a interface pública dos objetos de escritório devem estar classificados pelo tipo de interação (consulta, construção, alteração e destruição) e pelo contexto de atuação (métodos de classe e métodos de instância). Atividade e definida como um objeto, com atributos e métodos próprios, e plenamente reutilizável. Atividade tem uma representação diagramática adequada que mostra quais são os objetos tratados, e a forma de manipulação correspondente, as condições a serem satisfeitas para a realização da mesma e os limites, que os agentes tem, na produção dos resultados. Um diagrama de atividades é um grafo anotado, composto de atividades e objetos de escritório, onde cada atividade esta conectada, por ramos, somente a objetos, assim como cada objeto pode estar conectado, por ramos, somente a atividades. Os ramos identificam as diferentes formas de manipulação, dos objetos de escritório, pelas atividades. Um diagrama de atividades corresponde a modelagem conceitual dos aspectos dinâmicos de uma aplicação de escritórios. Os aspectos estáticos, e de dinâmica intra-classes, são descritos em um modelo de objetos, compatível com o SGBDOO adotado para a descrição e implementação dos objetos de escritório. Pelo diagrama de atividades de uma aplicação, são identificáveis as atividades que podem ser realizadas de maneira independente, que possuam algum conflito na manipulação dos objetos, e que tenham uma ordenação relativa entre si. E representada, desta maneira, a descentralização das atividades e o assincronismo existente entre as mesmas. A construção de um modelo, para uma realidade complexa, é amparada por uma técnica de decomposição de diagramas, permitindo que o projetista divida o problema, dessa realidade, em panes menores. Além disso, as técnicas de abstração generalização e agregação estão disposição, possibilitando a reutilização de modelagens feitas para problemas semelhantes ou correlatos. Essas abstrações, assim como a maioria dos aspectos referentes ao modelo desta tese, estão formalmente descritos. Um tipo especial de conflito entre atividades é particularmente interessante em aplicações de escritório: a tomada de decisão. Para esta tese, tomar uma decisão significa escolher um dos vários possíveis resultados na realização de uma atividade, a partir dos mesmos insumos. O trabalho descreve, precisa e formalmente, o que é tomada de decisão em uma atividade e mostra como identificar, em diagramas de atividades, aquelas com tomadas de decisão. É demonstrado que a modelagem de uma aplicação de escritórios, composta do modelo de atividades e do modelo de objetos, é implementável em computador, considerando a atual realidade das plataformas computacionais presentes em escritórios. Para tanto, e descrita uma arquitetura de um ambiente adequado para descrição e execução de aplicações de escritórios, bem como são descritos os protótipos desenvolvidos para validação dos principais aspectos. Para mostrar a eficiência do processo e a qualidade dos produtos da modelagem de sistemas de informação de escritórios no modelo, são apresentados dois estudos de caso: a preparação de conferencias de trabalho da IFIP e a automação do serviço de envio de fax. / This thesis presents a model for representing activities in office applications that is adequate for the description of the dynamic aspects of such applications. This model has two fundamental concepts, namely activities and office objects. Activity diagrams are used to model office application activities, depicting the flow of office objects, the transformations performed by office agents on those objects, and the decision making eventually involved on these activities. By modeling activities in this way, the dynamics of an application is described respecting the organizational and functional solutions adopted by an enterprise, as well as the assignments and responsibilities of the agents working in the organization. Office objects are complex and may present multimedia characteristics. However, the most striking peculiarity of these objects is the massive standardization of their descriptions, due to either legal or commercial reasons. It is this particularity that distinguishes office objects from objects belonging to other non-conventional application domains. As a consequence, office objects constitute a domain allowing intensive class reuse for modeling office applications. This work assumes that models targeted at representing office applications should have the reuse of office classes as one of their goals. In this thesis, it is considered that the office class library must be supported by an OODBMS and its description environment, independently of the specificity of office applications. Such OODBMS must support multiple inheritance as a description resource. Activity is the main component of the model proposed here. An activity represents the interaction of an agent with an application where office objects can be either created, queried, updated or destroyed, and additionaly be sent to other agents. This interaction between the agent and an application activity is performed in the agent workplace, i.e., in its workstation. The flow of office objects is then represented by the possible sequences of places within the office that those objects may follow. The data structure and the methods needed to allow office objects to deal with places are integrated into the objects themselves. This is achieved through multiple inheritance from a special class called office object place. The methods belonging to the public interface of office objects must be classified by the interaction type (query, creation, update, destruction) and by the action target (class or instance methods). An activiq_is defined as an object containing its own attributes and methods, potentially fully reusable. An activity has an adequate diagrammatic representation that displays the objects handled, the corresponding ways of manipulating objects, the conditions to be fulfilled such that the activity can be performed and, finally, the constraints imposed on agents for the production of results. An activity diagram is an annotated graph, composed of activities and office objects, where activities can only be connected to objects, and objects may only be connected to activities. The edges represent the different ways activities manipulate office objects. An activity diagram corresponds to the conceptual modeling of the dynamic aspects of an office application The static aspects, as well as the internal dynamic aspects of the classes, are described by an object model, which is compatible with the OODBMS adopted for the description and implementation of office objects. Through the activity diagram, one can identify activities that may be executed concurrently, activities presenting conflicts in object handling, and activities with a relative temporal ordering. In this way, one can represent the decentralization of the activities, as well as their relative concurrence. The construction of complex models is supported by a technique of diagram decomposition, which allows the designer to divide the model into smaller parts. In addition, generalization and aggregation abstraction mechanisms are available, allowing the reusability of models created for similar problems. These abstractions, as well as most of the modeling issues used, are formally described in the thesis. A particularly interesting type of conflict in office applications is decision making. For the purposes of this work, decision making is considered to be the choice among the various possible results of an activity, given a same input. This work describes in a precise and formal way what decision making is in the context of an activity, and shows how to identify, in activity diagrams, those activities involving decision making. It is shown that office application modeling, described by an activity model and an object model, can be implemented in a computer, considering the hardware and software platforms presently available in offices. With this purpose, the architecture of an adequate environment for the description and execution of office applications is described in the thesis, together with the prototypes developed for validating the main aspects of this work. To show the efficiency of the process, as well as the quality of the modeling of office applications with the proposed model, two case studies are presented, namely the IFIP working conference preparation and the fax sending service automation case studies.