18680044
Benchmarking Performance-Critical Components in a Native XML Database System
The rapidly increasing number of XML-related applications indicates a growing need for efficient, dynamic, and native XML support in database management systems (XDBMS). So far, both industry and academia primarily focus on benchmarking of high-level performance figures for a variety of applications, queries, or documents --- frequently executed in artificial workload scenarios --- and, therefore, may analyze and compare only specific or incidental behavior of the underlying systems. To cover the full XDBMS support, it is mandatory to benchmark performance-critical components bottom-up, thereby removing bottlenecks and optimizing component behavior. In this way, wrong conclusions are avoided when new techniques such as tailored XML operators, index types, or storage mappings with unfamiliar performance characteristics are used. As an experience report, we present what we have learned from benchmarking a native XDBMS and recommend certain setups to do it in a systematic and meaningful way.
2745798
Autonomous Management of Soft Indexes
In recent years the support for index tuning as pan of physical database design has gained focus in research and product development, which resulted in index and design advisors. Nevertheless, these tools provide a one-off solution for a continuous task and are not deeply integrated with the DBMS functionality by only applying the query optimizer for index recommendation and profit estimation and decoupling the decision about and execution of index configuration changes from the core system functionality. In this paper we propose an approach that continuously collects statistics for recommended indexes and based on this, repetitively solves the Index Selection Problem (lSP).A key novelty is the on-the-fly index generation during query processing implemented by new query plan operators In-dexBuildScan and SwitchPlan. Finally, we present the implementation and evaluation of the introduced concepts as part of the PostgreSQL system.
14265278
An Adaptive Storage Manager for XML Documents
Effective and efficient management and manipulation of XML documents requires stable decisions at the time a document enters the XML DBMS to provide for storage structures which are adjusted to the document characteristics and which reflect the future processing needs. While some of the critical parameters require a kind of pre-specification, others can be determined by pre-analysis or sampling of the incoming document or by just making experience-driven “educated guesses”. Important parameters are related to node labeling, path synopsis, document container layout, and indexing. In this paper, we discuss approaches to achieve an adaptive behavior of the storage manager to provide tailor-made native XML storage structures to the extent possible.
12054008
Tailor-Made Native XML Storage Structures
Automatically choosing suitable native storage structures for XML doc- uments arriving at the XML DBMS is a challenging task for its storage manager. While some of the critical parameters require pre-specification, others can be deter- mined by pre-analysis or sampling of the incoming document or by just making ex- perience-driven "educated guesses". In this paper, we discuss approaches to achieve an adaptive behavior of the storage manager to provide tailor-made native XML stor- age structures to the extent possible. 1I ntroduction The XML data model allows for a great deal of modeling flexibility with which order, op- tional and multi-valued concepts, as well as deeply nested relationships can be captured. Therefore, the resulting tree structures of natively represented XML documents exhibit large variations in breadth and depth. Furthermore, XML documents may be data-centric having relatively little 'content' stored as short text values or they may be document-cen- tric where a single content node may contain huge portions of text, e.g., an entire book in a digital library. For these reasons, it is highly advisable to equip the storage manager with the ability to select reasonable or even optimal storage structures for documents. Furthermore, two cas- es have to be considered: a document sent by a client arrives at a time—the so-called block mode, i.e., the document can be pre-parsed and analyzed before a storage structure is cho- sen—or it arrives at the DBMS interface in stream mode where fragments present, due to their size, have to be allocated in a suitable storage structure on disk before the entire "streamed" document is available for the DBMS. In the latter case, the storage manager must decide—based on imprecise structural information—on the storage structure to be chosen and, at best, can make some educated guesses based on context or sampling infor- mation.
15442183
Usage-driven storage structures for native XML databases
There are numerous and influential parameters associated with the selection of suitable native storage structures for XML documents within an XML DBMS. The most important parameters are related to node labeling, path synopsis, document container layout, indexing, and text compression. While node labeling and the presence of a path synopsis greatly determine flexibility and efficiency of the entire DBMS-internal XML processing, the remaining issues primarily address I/O demand and space consumption. In particular, text compression---considered orthogonal to the design choices affected by the other parameters---implies additional algorithmic costs for encoding/decoding during document processing. Having the vision in mind that future storage managers can autonomously figure out optimal choices for all of these parameters, we discuss how various storage options favor different usage patterns and how they can be specified beforehand to influence native XML storage options by the anticipated usages.
42183436
Adaptive Resource Management in a Native XDBMS
A graphite reinforced glass composite is described comprising discontinuous graphite fibers in substantially planar orientation in a glass matrix with strength and fracture toughness greater than the unreinforced glass matrix. The resulting composite has superior strength, fluid impermeability, wear resistance, failure strain and fracture toughness. In fact, the stress-strain, curve for composites of the invention resembles that of metal making it particularly suitable for a variety of moldable shapes and machinable designs.
172504304
LoLA wird Pfadfinder.
LoLA ist ein erreichbarkeitsgraphbasiertes Werkzeug f ur Stellen/Transitions{Netze. Hier geht es um LoLAs Fahigkeit, erreichbare Zustande mit vorgegebenen Eigenschaften zu suchen und im Erfolgsfall einen solchen Zustand mit einem Weg von der Anfangsmarkierung dorthin anzugeben. Die Besonderheit besteht darin, da wahrend der Suche nur zwei Zustande gespeichert werden: der Anfangszustand und der aktuelle Zustand. Anstatt also den Zustandsraum systematisch zu durchmustern (und dabei meist am Speicherende zu scheitern), navigiert LoLA ohne Kenntnis der schon betretenen Zustande durch den Erreichbarkeitsgraph. Da sie trotzdem ihre Aufgabe erfolgreich lost, liegt an ihren spezi schen Fahigkeiten: Schnelligkeit, Bescheidenheit, Zielstrebigkeit, Neugier und Ausdauer.
195610218
LoLA: a low level analyser
With LoLA, we put recently developed state space oriented algorithms to other tool developers disposal. Providing a simple interface was a major design goal such that it is as easy as possible to integrate LoLA into tools of different application domains. LoLA supports place/transition nets. Implemented verification techniques cover standard properties (liveness, reversibility, boundedness, reachability, dead transitions, deadlocks, home states) as well as satisfiability of state predicates and CTL model checking. For satisfiability, both exhaustive search and heuristically goal oriented system execution are supported. For state space reduction, LoLA features symmetries, stubborn sets, and coverability graphs.
118703657
Verification of Siphons and Traps for Algebraic Petri Nets
Siphons and traps are structures which allow for some implications on the net's behaviour and can be used in manual correctness proofs for concurrent systems. We introduce symbolic representations of siphons and traps which work quite well even in infinite cases and are still intuitively readable. The verification of symbolic siphons and traps is traced back to unification and structural induction on the terms. This approach is motivated by some additional considerations. For unification and other proposed structural reasoning mechanisms tool support is given by completeness proof tools studied in the theorem-proving community.
117881226
Narrowing Petri Net State Spaces Using the State Equation
Given a (possibly partially defined) state, all count vectors of transition sequences reaching that state are solutions to a corresponding Petri net state equation. We propose a search strategy where sequences corresponding to a minimal solution of the state equation are explored first. Then step by step the search space is relaxed to arbitrary count vectors. This heuristics relies on the observation that in many (though provably not in all) cases, minimal solutions of the state equation can be realized as a firing sequence. If no target state is reachable, either the state equation does not have solutions, or our search method would yield the full state space. We study the impact of the state equation on reachability, present an algorithm that exploits information from the state equation and discuss its application in stateless search as well as its combination with stubborn set reduction.
118762514
Stubborn Sets for Standard Properties
Stubborn sets are a tool for state space reduction preserving certain system properties. We present stubborn set approaches for all popular Petri net standard properties. This extends the list of properties that can be analysed successfully (including boundedness, reversibility). For other properties, our approach can lead to larger reductions (reachability) than previous ones. Furthermore, shortest and chepest witness paths for several properties are now preserved.