An Update Strategy for the WaterFowl RDF Data Store

Abstract

The WaterFowl RDF Store is characterized by its high compression rate and a self-indexing approach. Both of these characteristics are due to its underlying architecture. Intuitively, it is based on a stack composed of two forms of Succinct Data Structures, namely bitmaps and wavelet trees. The ability to e ciently retrieve information from these structures is performed via a set of operations, i.e., rank, select and access, which are used by our query processor. The nice properties, e.g. compactness and e cient data retrieval, we have observed on our rst experimentations come at the price of poor performances when insertions or deletions are required. For instance, a naive approach has a dramatic impact on the capacity to handle ABox updates. In this paper, we address this issue by proposing an update strategy which uses an hybrid wavelet tree (using both pointer-based and pointerless sub-wavelet trees).

-

Large amount of RDF data are being produced in diverse domains. Such a data deluge is generally addressed by distributing the workload over a cluster of commodity machines. We believe that this will soon not be enough and that in order to respond to the exponential production of data, the next generation of systems will distribute highly compressed data. One valuable property of such systems would be to perform some data oriented operations without requiring a decompression phase.

We have recently proposed the rst building blocks of such a system, namely WaterFowl, for RDF data [ 1 ]. The current version corresponds to an in-memory, self-indexed, operating at the bit level approach which uses data structures with a compression rate close to theoretical optimum. These so-called Succinct Data Structures (SDS) support e cient decompression-free query operations on the compressed data. The rst components we have developed for this architecture are a query processor and an inference engine which supports the RDFS entailment regime with inference materialization limited to rdfs:range and rdfs:domain. Both of these components take advantage of the SDS properties and highly performant operations. Of course, SDS are not perfect and a main limitation corresponds to their inability to e ciently handle update operations, i.e., inserting or deleting a bit. In the worst case, one has to completely rebuild the corresponding SDS (bitmap or wavelet tree) to address such updates. Even if we consider that the sweet spot for RDF stores is OnLine Analytic Processing (OLAP), rather than OnLine Transactional Processing (OLTP), such a drawback is not acceptable when managing data sets of several millions of triples.

The main contribution of this paper is to present an update strategy that addresses instance updates. Due to space limitations, we do not consider updates at the schema level (i:e:, TBox). This approach is based on a set of heuristics and the de nition of an hybrid wavelet tree using both pointer-based and pointerless sub-wavelet trees. 2

WaterFowl architecture

3 Due to space limitations, we let the reader refer to [ 1 ] for corresponding de nitions space e ciency. More details on these components are proposed in [ 1 ]. That paper presents some evaluations where di erent wavelet tree implementations have been used: with and without pointers and one so-called matrix [ 3 ]. The characteristics of the rst two motivated our update approach. As previously mentioned, one of the bene ts of using wavelet trees in our system is the ability to compress drastically the data while being able to query it without decompression. The main drawback of such SDS lies in its requirement to precompute and store some small but neccessary extra informations. More formally, the bitmaps used in the inner construction of the wavelet trees requires n + o(n) bits of storage space (the original bit array and an o(n) auxiliary structure) to support rank and select in constant time. Note that while the implementaton of rank is simple and practical, this is not the case for select which should be avoided whenever possible, e.g., in our SPARQL query translations. Recently, some attempts were done in order to provide faster and smaller structure for select [ 4 ]. These precomputed auxiliary informations are used during query processing in order to get constant time complexity. This is why, by de nition, the bitmaps are static and cannot be updated. In our context, it implies an immutable RDF store (which is quite restrictive).

In order to overcome this issue, we propose an update strategy using the inner tree structure of the wavelet trees. First, recall that there are mainly two implementations of the wavelet trees: with and without pointers. On one hand, the implementation without pointers uses less memory space and provides better time performances. On the other hand, any modi cation to the represented sequence implies a full reconstruction of the wavelet tree; while, in the case where pointers are used, only a subset of the nodes (and the corresponding bitmaps) have to be rebuilt which in our rst experiments is much faster than a total reconstruction. A second important point of our approach is based on the fact that in wavelet trees, each bit of an encoded entry speci es a path in the tree. That is, the instance data only in uence the size of nodes but not their placement in the tree. Considering these two assumptions together with the huge amount of data we want to handle, our strategy supports an hybrid approach based on the natural de nition of a tree. Indeed, a tree can be de ned recursively as a node with a sequence of children which are themselves trees. Our hybrid wavelet tree is then de ned as a node representing a wavelet tree without pointers of height k and a sequence of 2k children which are themselves hybrid wavelet trees. In practice, considering a querying scenario composed of read (e.g., select) and write (e.g., add, delete, update) operations, for performance purpose the hybrid wavelet tree can adapt its composition to the scenario by minimizing and maximizing the numbers of pointers in the depth traversal of respectively a read and write operation. Note that this approach of cracking the database into manageable pieces is reminiscent to dynamic indexing solution presented in [ 2 ]. 4

Conclusion

This poster exploits available wavelet tree implementations to address the issue of updating an ABox. We have already implemented a prototype of the WaterFowl system and of the updating system. They so far provide interesting performance results but we have yet to test with real use cases. This will enable us to observe practical modi cations and to study their e ciency. These observations should provide directions for optimizations. Our future work, we will consist in the development of two new components. A rst one will address updates at the schema level, i.e., insertions or removals of concepts and properties of the underlying ontology. The second one will consider the partitioning of a data set over a machine cluster together with both ABox and TBox updates.

References

1. Olivier Cure , Guillaume Blin, Dominique Revuz, and David Celestin Faye. Waterfowl: A compact, self-indexed and inference-enabled immutable rdf store . In ESWC , pages 302 { 316 , 2014 .

2. Stratos Idreos , Martin L. Kersten , and Stefan Manegold . Database cracking . In CIDR , pages 68 { 78 , 2007 .

3. Gonzalo Navarro . Wavelet trees for all . J. Discrete Algorithms , 25 :2{ 20 , 2014 .

4. Gonzalo Navarro and Eliana Providel . Fast, small, simple rank/select on bitmaps . In Ralf Klasing, editor, Experimental Algorithms , volume 7276 of Lecture Notes in Computer Science, pages 295 { 306 . Springer Berlin Heidelberg, 2012 .