Hypergraphs model complex, non-binary relationships such as co-authorships, social group memberships, and recommendation systems. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. We propose HyperCSA, a novel compression method for hypergraphs that maintains support for standard queries over the succinct representation. HyperCSA achieves compression ratios of 26 % to 79 % of the original file size on real-world hypergraphs-outperforming existing methods on all large hypergraphs in our experiments. HyperCSA also scales to larger datasets than existing approaches and evaluates neighbor queries 6 to 40 times faster on common real-world hypergraphs.

Constructing the Burrows-Wheeler transform (BWT) for long strings poses significant challenges regarding construction time and memory usage. We enable the use of multi-string BWT construction algorithms to construct the BWT of a long string by partitioning it into shorter substrings using a prefix of the suffix array. We prove that except for a single run of sentinel symbols $, the BWT of the shorter substrings is equal to the BWT of the long string. The proposed partitioning idea is applicable to string collections of any alphabet.

Neighborhood queries are the most common queries on graphs; thus, it is desirable to answer them efficiently on compressed data structures. Our full paper [1] presents a grammar-based compressor called Incidence-Type-RePair (ITR) for graphs with labeled nodes and labeled edges based on RePair. We applied ITR to network, version, and RDF graphs and we compared the performance of triple SPO queries on these compressed datasets generated by ITR and 4 state-of-the-art graph compression approaches. As shown in the figure below and in our full paper [1] , ITR outperforms the other graph compressors for all triple SPO queries except for the query-type ? P ?, while providing a compression size comparable to the other compressors. Thereby, ITR is 2 to 6 times faster than the fastest compared query-evaluation technique and up to 100 times faster than the slowest approach in our tests.

A fundamental operation on large graphs is the search of occurrences of a given pattern in the graph. Like [1], we consider an original graph OG and a query pattern Q of labeled nodes and unlabeled edges and aim to compute a relation called simulation of Q in OG, which determines a superset of the occurrences of Q in OG. An algorithm in [1] computes the simulation of Q in OG in time O(n*m) for n vertices and m edges of OG. In comparison, we have developed an algorithm [2] that works on a compressed graph grammar GG of OG, instead of operating on OG itself. The speed-up of our algorithm [2] compared to the algorithm in [1] grows with the size |OG| of OG and with the compression strength |OG| / |GG| of the graph grammar GG.

Huge amounts of tree structured data (such as JSON, XML, etc.) can be compressed to straight-line context-free (SLCF) tree grammars. This compression of tree-structured data of size O(N) reduces the number of edges ideally to O(log N), which reduces the memory footprint and speeds-up search algorithms. Nevertheless, grammar-based tree compression has two major limitations resulting in an unnecessary high number of edges: first, updates of SLCF grammars by path extraction over time increase the grammar size, second, a given sibling-order prohibits a compression of arbitrary combinations of siblings. A way out of the first limitation is re-compression, i.e. to find a stronger compressed SLCF tree grammar of the tree without decompressing the given grammar. A way out of the second limitation is an extension of re-compression to unordered trees. RECUT provides not only re-compression for unordered trees, but also for partially ordered trees. Furthermore, whenever parts of the data are unordered - as it is the case for data-centric data - RECUT significantly improves grammar-based compression by further reducing the number of edges in the compressed data by a factor of up to 30.

XML tree structures can be effectively compressed using straight-line grammars. It has been an open problem how to update straight-line grammars, while keeping them compressed. Therefore, the best previous known methods resort to periodic decompression followed by compression from scratch. The decompression step is expensive, potentially with exponential running time. We present a method that avoids this expensive step. Our method recompresses the updated grammar directly, without prior decompression; it thus greatly outperforms the decompress-compress approach, in terms of both space and time. Our experiments show that the obtained grammars are similar or even smaller than those of the decompress-compress method.

Summary form only given. Grammar-based compression yields high compression ratios for XML document trees. However, the holy grail of grammar-based compression has been how to support incremental updates. Supporting updates is a crucial demand for many applications. The best available method decompresses the grammar, performs the update, and compresses the result. The new Online Repair algorithm presented here recompresses a given updated tree grammar directly, without decompression. Surprisingly, the algorithm yields the same compression ratios as the decompress-update-compress strategy, while being much more efficient in time and space.

We present LECQTER, a tool for generating a 'perfect example' database, called exemplar, for a given conjunctive query. Indeed, exemplars separate the given query from any non-equivalent query. Therefore, LECQTER reduces the query equivalence problem to an evaluation of the queries on the exemplar. LECQTER can thus be used for applications ranging from testing coded conjunctive SQL queries to learning how to write sound conjunctive SQL queries, as it provides immediate feedback about the semantic correctness of a query, and not just the correctness of the query answer on some database as, e.g., other SQL tutoring systems. This key novelty of LECQTER relies on the bag semantics of SQL since exemplars do not always exist under set semantics. Detailed experiments show that our construction of exemplars is efficient in practice, and that they can separate a number of non-equivalent user queries that is exponential in the size of the exemplar for the target query. We identify natural parameters to control the time and size of the exemplars constructed. Finally, we offer a solution that overcomes the non-existence of exemplars under set semantics.

Text compression techniques like bzip2 lack the possibility to delete the nth word or to insert text be-fore the nth word of compressed texts without prior decompression of the compressed texts. We present a text compression technique that supports fast insertion into and deletion from compressed texts without full decompression of the compressed text. Our approach combines Indexed Reversible Transformation (IRT) [1], Run-Length-Encoding (RLE), and the Wavelet Tree (WT). For a reasona-ble size of inserted or deleted texts (more details are given in [2]), our approach is faster than modifying uncompressed text preceded by a decompression step and followed by a compression step.

Text compression techniques like bzip2 lack the possibility to search or to update substrings at given positions of texts that have been compressed without prior decompression of the compressed text. We have developed Indexed Reversible Transformation (IRT), a modified version of the Burrows-Wheeler-Transformation (BWT) that in combination with run length encoding (RLE) and wavelet trees (WT) allows for position-based searching and updating substrings of compressed texts without prior decompression of the compressed text. As a result, IRT may be useful for a huge class of applications that due to space limitations prefer to search or to modify compressed texts instead of uncompressed texts.

The use of atomic commit protocols in mobile ad-hoc networks involves difficulties in setting up reasonable time-outs for aborting a pending distributed transaction. This paper presents the non-blocking adjourn state, a concurrency control modification which makes time-outs in an atomic commit protocol for aborting a transaction unnecessary. Further, it enhances concurrency among transactions performing conflicting accesses to resources used by completed distributed transactions waiting for the commit protocol to be initiated.

When a transaction commit decision is lost or delayed in a mobile network, most transaction protocols cannot terminate the transaction and delay conflicting transactions. In contrast to this, we present a concept called Bi-State- Termination (BST) that allows transactions to terminate into two states: one state having the changes applied, and the other state having the transaction aborted. Conflicting transactions that work on these states are not blocked. We prove that BST guarantees atomicity and serializability, and describe a possible implementation using version numbers. Furthermore, our experimental results show that BST is feasibility for mobile networks, and that it enhances the transaction throughput whenever transactions are blocked for a long time.

Whenever nodes in a mobile network try to access an XML database server, the offered data must be somehow queried and transported by a mobile network to the querying node. For this purpose, two mechanisms are possible: query shipping and data shipping. Which one is better depends among other aspects on the query result size, more precisely on the overhead that data shipping incorporates compared to query shipping. In this paper, we present a query result size estimator that allows each mobile user to estimate the resulting size and cardinality of an XPath query by means of special distributed meta data in order to decide between query shipping or data shipping by comparing the estimated size of the result with the data that must be requested for data shipping. We show how the meta data is generated for certain query classes, how the meta data can be used to predict the result size and cardinality, and we give experimental results on the deviation of the predicted results.

In traditional fixed-wired networks, standard protocols like 2-Phase-Commit are used to guarantee atomicity for distributed transactions. However, within mobile networks, a higher probability of failures including node failures, message loss, and even network partitioning makes the use of these standard protocols difficult or even impossible. To use traditional database applications within a mobile scenario, we need an atomic commit protocol that reduces the chance of infinite blocking. In this paper, we present an atomic commit protocol called multi coordinator protocol (MCP) that uses a combination of the traditional 2-Phase-Commit, 3-Phase-Commit, and consensus protocols for mobile environments. Simulation experiments comparing MCP with 2PC show how MCP enhances stability for the coordination process by involving multiple coordinators, and that the additional time needed for the coordination among multiple coordinators is still reasonable.

While traditional fixed-wired network protocols like 2-phase-commit guarantee atomicity, we cannot use them in mobile low bandwidth networks where network partitioning, node failure, and message loss may result in blocking. To deploy traditional database applications easily into a mobile environment, there is a demand for a protocol which guarantees an atomic commit of transactions. This paper introduces a protocol which can guarantee such atomic commitment in mobile environments using a combination of commit and consensus protocols. In addition, it takes advantage of mobile network sub-structures like single-hop environments to reduce message transfer costs.

An implementation technique which solves integrity checking, query evaluation, and transaction synchronization tasks in database systems with multiple attribute inheritance and uses the support of a relational database system is presented. It is shown how to implement an integrity checker and a transaction synchronization component of a database system with attribute inheritance. The basic idea is to map arbitrary integrity constraints, queries, and locks associated with classes of an inheritance lattice onto integrity constraints, queries, and locks associated with relations of an underlying relational database.>