Sirix - Versioned Open Source XML Storage with Temporal Hierarchies
Sirix is an open source XML storage system which is capable of storing and querying hierarchical data efficiently. It is especially well suited for flash disks (SSDs), taking into account fast random reads and log-structured sequential writes. Several versioning algorithms are available, to provide efficient access to each revision (snapshot) and to balance between fast queries as well as fast updates. All, but the full versioning algorithm store page-deltas.
The system supports N-reading transactions in parallel to 1-write transaction. XQuery-functions are extended to take versioning into account. Furthermore temporal XPath-axis namely next::, previous::, first::, last::, future::, future-or-self::, past::, past-or-self:: are provided to efficiently navigate not only in space but also in time.
In order to import several snapshots of a temporal XML-(or in the future JSON-) document a diff-algorithm encounters differences. These changes are stored in addition to an initial import of the document. Furthermore a fast ID-based diff-algorithm which optionally utilizes hashes to speed up the computation facilitates the comparison of several revisions of a resource once stored in Sirix. Note that an optional postprocessing step even detects moves. A heuristic might optionally be used to detect certain kinds of replaced subtrees.
To assist a fast XQuery processor, in addition to user-defined, versioned path- and element-indexes typed content-and-structure index-structures will be available very soon which take the structure as well as an optional content-predicate into account. Note that both the index-structures as well as a small in-memory path summary are always kept up-to-date.
In stark contrast to other approaches, hashes are stored to guarantee integrity and to speed up the diff-algorithm. Furthermore the number of descendants of each node, the number of children of each structural node and DeweyIDs (to provide fast document-order determination and in the future probably intention locks on parent-nodes) are optionally stored. Thus, a very wide range of application-scenarios is covered.
Moreover, Sirix just stores bytes which are really needed and doesn't pad the size of a datapage until a predefined threshold is filled during serialization of the buffered in-memory pages to disk. The commit-strategy also facilitates recursively applying checksums in the future, such that it's possible to detect whole page-subtrees which are inconsistent.
Note, that in general the system by no means is restricted to versioning XML. JSON will soon follow, thus arrays and objects will be natively stored. Furthermore any kind of Java-objects might be stored provided that a custom serializer is plugged in.
Besides supporting the XQuery compiler Brackit with the versioned index-structures through sophisticated rewrite-rules, distribution will be our next major focus, possibly using Scala and Akka(.io). Furthermore a novel versioning approach will balance reading / writing of data without introducing write-peaks during intermittant full snapshots of data-pages to fasttrack their in-memory reconstruction.