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.

The Burrows-Wheeler transform (BWT) is integral to the FM-index, which is used extensively in text compression, indexing, pattern search, and bioinformatic problems as de novo assembly and read alignment. Thus, efficient construction of the BWT in terms of time and memory usage is key to these applications. We present a novel external-memory algorithm called Improved-Bucket Burrows-Wheeler transform (IBB) for constructing the BWT of DNA datasets with highly diverse sequence lengths. IBB uses a right-aligned approach to efficiently handle sequences of varying lengths, a tree-based data structure to manage relative insert positions and ranks, and fine buckets to reduce the necessary amount of input and output to external memory. Our experiments demonstrate that IBB is 10% to 40% faster than the best existing state-of-the-art BWT construction algorithms on most datasets while maintaining competitive memory consumption.

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.

We consider information disclosure caused by answering queries to an XML database. We introduce an audit framework to determine ‘suspicious’ user queries, i.e. those queries that returned results being sufficient to derive disclosed secret information. We describe secret information in form of a se cret query and provide a formal definition of ‘suspicious’ user queries based on what we call ‘readset fragments’, i.e. XML fragments that have been read to produce certain query result nodes. Our approach performs two steps to detect ‘suspicious’ user queries. First, we analyze the structure of user queries and of the secret query to exclude ‘non-suspicious’ queries. Second, we derive a formula from user query, query result and secret query, which is satisfiable if and only if the query is ‘non-suspicious’.

We present an XML data exchange technique suitable for mobile commerce systems involving thousands of mobile users and massive data loads. A key idea of our technique is that it is based on an XML information repository that is logically split into several disjoint data fragments. Thus, each mobile user's device can determine those parts of the information repository that are required for answering a given query locally at the device. The benefit of this local query processing is that our technique allows participating user devices to make their cached data fragments available to other participating devices and relieves the central information repository, resulting in a significant reduction of the overall data transfer and improved query response times.

Whenever secret information has been shared among multiple partners and has been illegally leaked to a third party, it is important for the trust among the partners to identify the information leak. We present a forensic approach to privacy violation control that after information has been leaked identifies those partners that had access to the leaked information. Our approach represents secret information as a boolean formula and compares it with the queries and the relational database state to which the queries were applied. We use this technique to identify suspicious queries, i.e., queries that have got sufficient information to infer secret information that has been leaked. Furthermore, we prove that checking where a select-project query is suspicious with respect to a given secret information is NP-complete, but a polynomial time solution exists for interesting subclasses.

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.

Transaction processing in mobile ad hoc networks must take network problems like node disconnection, message loss, and network partitioning into consideration. We present a distributed cross-layer atomic commit protocol called CLCP that uses multiple coordinators and makes use of acknowledgement messages to piggyback information. We evaluated transaction processing in mobile ad hoc networks by using two mobility models (i.e. Attraction Point and Manhattan Geometry), and compared CLCP with both atomic commit protocols, 2PC and Paxos Commit, each implemented in 3 versions, i.e. without acknowledgements, with Relay Routing, and with Nearest Forward Progress Routing. Special to our simulation environment is the use of the quasi-unit-disc model, which assumes a non-binary message reception probability that captures real-world behavior much better than the classical unit-disc-model, often used in theory. Using the quasi-unit-disc model, our evaluation shows the following results. CLCP and "2PC without acknowledement messages" have a significantly lower energy consumption than the other protocols, and CLCP is able to commit significantly more distributed transactions than all the other atomic commit protocols for each of the mobility models.

When applications require a union calculation of different distributed datasets, two requirements are often necessary to fulfil: anonymity and security. Anonymity means for scenarios with more than 2 participants that the owner of a certain data item cannot be identified. Security means that no participant can prevent that data items of other participants will be included in the union set. In this paper, we present a union protocol that guarantees both properties: anonymity and security even if participants act malicious, i.e. to modify messages or change the protocol. We prove the correctness of protocol and give experimental results that show the applicability of our protocol in a common environment

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.>