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.
60532280
Distributed verification with LoLA
We report work in progress on a distributed version of explicit state space generation in the Petri net verification tool LoLA. We propose a data structure where all available memory of all involved workstations can be fully exploited, and load balancing actions are possible at any time while the verification is running. It is even possible to extend the set of involved workstations while a verification is running.
119954332
How to calculate symmetries of Petri nets
Abstract. Symmetric net structure yields symmetric net behaviour. Thus, knowing the symmetries of a net, redundant calculations can be skipped. We present a framework for the calculation of symmetries for several net classes including place/transition nets, timed nets, stochastic nets, self–modifying nets, nets with inhibitor arcs, and many others. Our approach allows the specification of different symmetry groups. Additionally it provides facilities either to calculate symmetries on demand while running the actual analysis algorithm, or to calculate them in advance. For the latter case we define and calculate a ground set of symmetries. Such a set has polynomial size and is sufficient for an efficient implementation of the for all symmetries loop and the partition of net elements into equivalence classes. These two constructions are the usual way to integrate symmetries into an analysis algorithm.
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.
195220837
Model-Checking with Coverability Graphs
We show that several formulas of a temporal logic can be verified using the coverability graph of the underlying system. Of course, the procedure is not capable of verifying all formulae, since already the reachability problem for (unbounded) Petri nets is computationally hard. Thus, the procedure returns true, false, or unknown for a query. The formulae that can be verified cover most of the well known standard properties which have been listed in the context of coverability graph analysis so far.
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.
10752832
Comparison of Complete and Elementless Native Storage of XML Documents
Because XML documents tend to be very large, are accessed by declarative and navigational languages, and often are processed in a collaborative way using read/write transactions, their fine-grained storage and management in XML DBMSs is a must for which, in turn, a flexible and space-economic tree representation is mandatory. In this paper, we explore a variety of options to natively store, encode, and compress XML documents thereby preserving the full DBMS processing flexibility on the documents required by the various language models and usage characteristics. Important issues of our empirical study are related to node labeling, document container layout, indexing, as well as structure and content compression. Encoding and compression of XML documents with their complete structure leads to a space consumption of ~40% to ~60% compared to their plain representation, whereas structure virtualization (elementless storage) saves in the average more than 10%, in addition.
17363995

 Storing and indexing XML documents upside down

AbstractXML documents contain substantial redundancy in their structure part, because each path from the root
 node to a leaf node is explicitly represented and typically large sets of such path instances belong to
 a path class, i.e., the nodes of the path instances are labeled by the same sequence of element (or attribute)
 names. To save storage space and I/O cost, we want to get rid of this structural redundancy to the extent
 possible. While all known methods for the physical representation (storage) of XML documents proceed from
 the root via the element/attribute hierarchy (internal nodes) down to the leaves (values), we follow an
 upside-down approach which explicitly stores the values and only reconstructs
 the internal nodes, if needed. The cornerstones for such a solution are suitable node labels and a path
 synopsis which efficiently represents all path classes of an XML document. As a solution, we propose a compact
 internal storage format for native XML database systems where the inner structure of the stored documents
 is virtualized. Because this elementless storage format provides an efficient reconstruction of a document
 using its path synopsis, all processing properties are preserved and the semantics of navigational and declarative
 operations of XML languages remains unchanged. Adjusted indexes support the full spectrum of so-called
 content-and-structure single path queries. Apart from greatly reduced storage consumption, our approach
 demonstrates its superiority, compared to competing methods, not only for a substantial fraction of those
 queries, but also for storing, reconstructing, and navigating XML documents.

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.
11969863
Towards Flash Disk Use in Databases - Keeping Performance While Saving Energy?
Green computing or energy saving when processing information is primarily considered a task of processor development. We, however, advocate that a holistic approach is necessary to reduce power consumption to a minimum. We explore the potential of NAND flash memory in comparison to magnetic disks for DBMS-based architectures. For this reason, we attempt to identify the IO performance of both storage types at the device level and file system interface, before we approach the most important question how DBMS applications can take advantage of the flash performance characteristics. Furthermore, based on an analysis of storage structures and related benchmark runs in our XTC system, we discuss how IO-intensive DBMS algorithms have to be adjusted to take most out of the flash technology which is entering the server area with dramatic pace. The ultimate goal is to substantially improve energy efficiency while comparable performance as in disk-based DB servers is maintained.
15429796
Essential Performance Drivers in Native XML DBMSs
As a multi-layered XML database management system, we have designed, implemented, and optimized over the recent five years our prototype system XTC, a native XDBMS providing multi-lingual query interfaces (XQuery, XPath, DOM). In particular in higher system layers, we have compared competing concepts and iteratively found salient solutions which drastically improved the overall XDBMS performance. XML query processing is critically affected by the smooth interplay of concepts and methods on all architectural layers: node labeling and mapping options for storage structures; availability of suitable index mechanisms; provision of a spectrum of path processing operators; query language compilation and optimization. Furthermore, effective and efficient locking protocols must be present to guarantee the ACID properties for XML processing and to achieve high transaction throughput. 
 
In this survey, we outline our experiences gained during the implementation and optimization of XTC. We figure out the "key drivers" to maximize throughput while keeping the response times at an acceptable level. Because we have implemented all options and alternatives in XTC, dedicated benchmark runs allow for comparisons in identical environments and illustrate the benefit of all implementation decisions.