Balisage Paper: TNTBase: Versioned Storage for XML

Subversion

Subversion (SVN) is one of the most popular open-source client-server version control systems. On a server side SVN maintains versions and history of documents and directories in a repository. Users work with such a repository by checking out to a local working space the directory tree (a working copy). This maintenance is performed by the SVN client utility. After a working copy is checked out users can perform various actions with it [CSFP04]: change, update from a repository or propagate changes back to a repository, changing properties of directories or files, merging different source trees, etc. The update command performs merging of a local working copy with the latest version in a repository. In case when automated merging is not solvable, a user has to edit conflicting files manually. Afterwards in order to propagate local changes back to a repository a user performs a commit. Using above mentioned commands comprises the typical workflow encountered by SVN users. We have covered only the basic concepts, but that is enough to get a rough conception of SVN. In Section xSVN we will show that the TNTBase core is a substitution of an SVN server.

SVN is not aware of content inside a repository (apart from distinguishing binary and text files). For SVN users it does not make a difference whether they store text files, PDFs or XSLT stylesheets. In particular, SVN does not support native XML processing like XML databases. By XML-processing we mean possibilities to query XML-documents, index them in order to improve querying performance, benefit from XQuery Update facilities [XQU08] or utilize transactional mechanism in order to keep collection of XML documents consistent. Thus when we are talking about XML storing we should look at the XML-databases which is a subject of the next subsection.

Another limitation of SVN is that the smallest versioned entity in its repository is a file. But for some users it might be desirable to abstract away from the notion of files, and work with XML objects like a section in scientific papers in the DocBook format or theorems or proofs in mathematical documents. Roughly speaking, a user should be able to get away from the file metaphor (see [MK08] for further ideas).

Berkeley DB XML

Berkeley DB XML (DB XML) is an open-source, XML-native embedded database. Embeddedness means that it is distributed as a library with a number of API for various programming languages like C++, Java, Perl, Ruby and some others. This approach does not have an overhead by having surrounding environment like servlets or stand-alone servers. Also the embeddedness eliminates some database administration costs. DB XML is built on top of Berkeley DB [Ber09a] which is used by such applications as SVN (the consequences of this are discussed in Section xSVN), the RPM Package Manager RPM09, the MySQL database MyS08 and Postfix Pos09, to name just a few of the most notable. Berkeley DB is an open source, embeddable database with zero administration; and DB XML inherits its advantages and features (e.g. portability, transactions, replications, easy deployment, etc.) from it. Naturally DB XML extends this with the typical XML-native database features: XQuery-based [XQu07] access to documents (with XQuery Update facilities support), support of transactions, preparsed queries, content-based indexing, scalability, recovery and locking mechanisms and the ability to work in multi-threaded and multi-process environments. Furthermore DB XML has established a reputation of being a scalable and very productive XML-native database that makes it a good choice to base the TNTBase system on.

But unfortunately DB XML does not support versioning which is becoming more and more important when managing collections of XML documents. Some of the products [Ipe09, Mar09, Ora09b] on the XML-native databases market actually support versioning in a way, but this versioning has a bunch of limitations in comparison to ordinary version control systems like SVN or CVS, and moreover they all have a commercial license. On the other hand there is no popular version control systems which treat XML in a special way. This should be a goal of TNTBase as well.

Querying XML Documents

We will start with a short description how querying is done in DB XML and in DB XML Accessor. As in nearly every XML-native database, the query language in DB XML is XQuery. To address the whole container in DB XML we use collection('dbxml:/<container_name>'). To access a particular document in a container DB XML uses doc('dbxml:/<container_name>/<doc_name_inside_container>') syntax.

DB XML Accessor utilizes slightly extended and simplified syntax of accessing documents in a DB XML container. Since we have only one container in xSVN, to access all documents in a container just use collection(), to access a particular document use doc(<path_to_doc>).

Here we should say something about how the latter query is transformed to DB XML syntax. As we mentioned in Section xSVN, we use reference keys from the representations table as documents names in DB XML. There is another way to preserve a path and a document name in DB XML. To accomplish this DB XML document metadata are used. Each document in a container can have an arbitrary set of metadata fields of different types. This metadata could be also indexed by DB XML, which might improve performance of particular queries. So when xSVN adds a new XML document into a container, it also sets a document location in a repository, a document name and a full path of a document. For instance, if we have a document paper.xml in the /Balisage folder, then the location in a repository would be /Balisage, the document name - paper.xml, and the full path - /Balisage/paper.xml. At first glance this information might seem redundant, especially taking into account that xSVN stores all of these in BDB tables. But by this approach we do not lose much except some storage space and writing performance when index of metadata should be updated. But we gain much more, now we are independent in DB XML Accessor from BDB tables, and each of the metadata fields can improve performance on particular queries which deal with documents paths.

Thanks to the mentioned above metadata fields, it is possible to access a subset of documents in a container. For this one should use collection(<arbitrary_path>) in DB XML Accessor. For example collection(/doc*//test//paper??.xml) would address all documents which names corresponds to the pattern paper??.xml (a '?' is just a wildcard) and they contain test directory in the path and the first directory of which starts with doc.

Also DB XML Accessor exposes methods for retrieving contents and paths of documents which are located at some arbitrary paths. Wildcards or '//', which stands for an arbitrary number of subfolders in a path, could also be used. All these queries would not be so efficient if we did not introduce a file system concept in xSVN container. Why did we have to introduce a file system? The answer is simple: DB XML does not have any hierarchical structure inside its containers. The next sections explains how we have introduced it.

File System in an xSVN Container

We already introduced the file path metadata fields in Section Querying XML Documents. Using them it is possible to reproduce the file system tree, but unfortunately it is not always efficiently. Assume that we want to find out what directories and files are located in a particular folder. For this we would have to execute a substring query on our file path metadata field. If a DB XML container contains a huge collection of documents then we could have a big delay while performing a seemingly simple task. The solution was to introduce ad-hoc XML documents in an xSVN container, one for each directory. We call such XML documents as file system documents (FSDs). FSDs have a special name format: tnt:<directory_path>. Each of these FSDs contains a list of directory entries in XML format. For example for directory /Balisage/papers we might have the following FSD inside an xSVN container (its name is tnt:/Balisage/papers/):

                <entries xmlns="http://tntbase.mathweb.org/ns">
                    <dir name="sources"/>
                    <dir name="references"/>
                    <file name="paper_zholudev.xml"/>
                    <file name="paper_kohlhase.xml"/>
                    <vfile name="notations.vf" id="dbxml_54"/>  <!--will be explained later -->
                </entries>
            

Now we can easily and efficiently find out about entries in the particular directory using XQuery. Here we should mention that such FSDs exist only for a folder which contain XML files or folders which contain XML files. Thereby we do not interfere with other content of an xSVN repository like text files or images. xSVN takes care about consistency in such FSDs, e.g. if a folder becomes empty after deletion of XML files, then the corresponding FSD is removed from a DB XML container and the folder is removed from the parent's folder entries and so on recursively. Also if we add some XML files to a newly created folder, then the file system structure is created recursively.

Write Access to TNTBase

So far we discussed only how to retrieve content and query an xSVN container by DB XML Accessor. But is it possible to write to xSVN using DB XML Accessor, or perform an XQUpdate query? The answer is positive. Then the next question arises, what would happen with revisions of XML files inside an xSVN repository? Shortly the answer is that the updated XML files will get a new revision in xSVN, then will be deltified, and a delta will be stored in BDB. Thus all history of modifications will be preserved. Let us discuss how we have accomplished that.

In DB XML Accessor we use the SVNKitAdapter library, which is based on the SVNKit - a Java library that re-implements the SVN client functionality. This allows us to work directly with an xSVN repository without a need to have a local working copy. In particular, SVNKit follows the SVN protocol to makes sure that no changes are lost on a commit; it forces an in-memory update and construct a delta between the local and the (updated) head revision. Only this delta is sent to a repository by SVNKit. But things get more complicated if we intend to modify an XML document by XQUpdate facilities. Then DB XML Accessor substitutes the original XQUpdate with a transform function (see [XQU08] for more details), which returns a modified document but does not modify a document internally in DB XML. Then this modified part is sent via SVNKitAdapter to xSVN in the usual way: SVNKit creates a new revision of a file and stores a delta against the previous version. Thus we can again retrieve a version of a file before executing XQUpdate. The xSVN log message would tell users how this change has occurred.

Querying Previous Revisions

Even though the xSVN container only stores the head revision of XML files we can query previous revisions of XML files: DB XML Accessor can cache XML files in the same xSVN container for the respective revision. Then we are able to query XML files exactly like we describe it in Section Querying XML Documents but additionally providing a revision of interest. Note that only those files that have been cached before will be queried. Analogously we can remove a set of documents from a cache. Then they will not be queried. The advantage of this approach is that we choose manually the interesting subset of a revision thereby avoiding redundant filling of an xSVN container and eliminating unnecessary results. Also we are able to cache the single file unlike SVN when we are able to checkout or export only folders. Note that we can even cache the head revision, even though the head xSVN container already contains it. This can be useful when we intend to query against the documents of an exact revision: documents of the head revision can evolve, but cached documents remain the same.

All caching is mediated by SVNKitAdapter, which retrieves the necessary revisions from an xSVN repository. Then these revisions are added to a DB XML container with a special metadata field that denotes a revision number. This metadata field is also indexed, which improves performance on querying. All XML documents of the latest revision have a revision meta field equal to '-1'. This field allows us to distinguish different revisions when querying without loosing performance. In order to cache the latest revision, one should provide the exact number of it.

Caching Query Results

DB XML Accessor can cache query results in situations where a query incurs a large processing load, but the files that contribute to a query result change rarely. The user must simply pass a corresponding option to a query engine and receive a unique access handle with the computed result. Of course it is also possible to clean an xSVN container from cached results if they are not needed any longer or became obsolete. Internally, DB XML Accessor stores query results as separate documents. To distinguish them from e.g. FSDs introduced in Section Virtual Files, we introduce a type metadata field which is also applied for virtual files (see Section Virtual Files).

Creating a Virtual File and Getting Information about Virtual Files

A VF is a file system entity that records the following information:

For instance, if somebody is interested in all definitions from mathematical documents in a folder where a VF is being created, then (s)he can provide the following information to DB XML Accessor:

After a VF has been created, one can easily retrieve its 'content', i.e. in our example all definitions in OMDoc documents in the /omdoc/theories folder. For the sake of example, a reader might also find useful Figure Definitions virtual file.

Definitions virtual file

Definitions virtual file

That is a typical creation procedure that is supported by DB XML Accessor. When a VF is created a new entity is added to a corresponding FSD. This entity is called vfile and also contains a name of a newly created DB XML document that encapsulates information about a VF. We call such a document as a VF encapsulated document (VFED). To retrieve the content of a VF the corresponding FSD is checked for the VF. If a VF exists, then a name of a VFED is read. When we know the name of a VFED, then we are able to receive an XQuery expression from that document. As soon as we have an XQuery expression we can execute it and deliver results to a user. Namespace declarations which have been provided during a creation of a VF are used during XQuery execution and are stored in a VFED.

VFEDs are tagged with the metadata field type discussed in Section Caching Query Results. Therefore we can easily pick out only VFs and retrieve information about them in an xSVN container like their descriptions, revisions they operate on, their names, etc. Thus we are not get lost in the variety of VFs that users might have created.

Caching and Querying Virtual Files

To make VFs more like VIEWS in relational data bases, DB XML Accessor also allows them to be queried, but only if their content has been cached. This allows the user to specify which VFs participate in querying. Note that if XML files which form the content of a VF have been changed, the cache of a VF is not changed. This is a target for a future work^[6]. Caching also might be useful when a user intends to receive a content of a VF quickly and is sure that the cache contains up-to-date data. This is especially worthwhile when an XQuery expression of a VF is computationally expensive.

When DB XML Accessor receives a command to cache a content of a VF (during creation of a VF, receiving VF's content or just via simple re-cache command), then the VF's content is stored in an xSVN container in the corresponding VFED. Results are wrapped in the special XML elements that are indexed. When querying VFs a user should use the same query syntax as (s)he uses for usual XML documents. That is possible because each VFED contains metadata fields for a VF path and its name. So for DB XML Accessor it does not make too much difference what is being queried: XML documents of the latest revision, cached documents of former revisions or VFs.

Editing Virtual Files

We complete this section by introducing another operation that could be performed on VFs. We are talking about editing VFs, i.e. in some cases (which we will explain a bit later) it is possible to retrieve a VF for editing, modify it and submit changes back. Then the files from which a VF was formed will be modified in xSVN and will receive a new revision. Returning back to our example with a VF that contains definitions of mathematical objects, if we modify all definitions in this file, then all OMDoc files in the folder /omdoc/theories that contain definitions will be modified accordingly and committed to xSVN.

This approach has a number of limitations, some of them are quite obvious and straightforward:

This allow us to get rid of a notion of files in a way and operate on the level of objects and version them, although internally in xSVN the minimal versioned entity is still a file. Let us provide an example of the VF that contains a list of creators in OMDoc files.

                <?xml version="1.0" encoding="UTF-8"?>
                <tnt:vfile name="defs.vf" mode="edit" xmlns:tnt="http://tntbase.mathweb.org/ns" 
                    xmlns="http://www.mathweb.org/omdoc" xmlns:dc="http://purl.org/dc/elements/1.1/">
                    <tnt:note>
                        WARNING: do not edit 'results' elements, edit only within them! 
                        Otherwise TNTBase will not be able to version the corresponding 
                        original files! Appending additional result elements may harm 
                        your TNTBase content. Additional elements under 'tnt:vfile' other 
                        than 'tnt:result' will be ignored 
                    </tnt:note>
                    <tnt:result file_path="/ecc.omdoc" element_path="/omdoc/metadata" 
                        element_name="dc:creator" element_type="element" id="1">
                        <dc:creator role="trl">Michael Kohlhase</dc:creator>
                    </tnt:result>
                    <tnt:result file_path="/ecc.omdoc" element_path="/omdoc/metadata" 
                        element_name="dc:creator" element_type="element" id="2">
                        <dc:creator role="ant">The OpenMath Society</dc:creator>
                    </tnt:result>
                    <tnt:result file_path="/omstd/arithmetics1.omdoc" element_path="/omdoc/
                        symbol/metadata"  element_name="dc:creator" element_type="element" id="3">
                        <dc:creator role="ant">The TNTBase Society</dc:creator>
                    </tnt:result>
                </tnt:vfile>
            

This file is obtained for editing and as was discussed above contain wrappers with a set of attributes. Elements with the same name and path in the same documents are distinguished by the id attribute.

A couple of words how it is realized in DB XML Accessor. As we can see out of the example, every result of a VF is wrapped in a special XML element that contains the information about an original document, a path in the original document, a name of an element, a type of an element (an attribute or a node) and a unique id. All these items allow us to construct a unified XQUpdate expression for an every modified original document. So in our example, if we modify each element, then it means that we should propagate changes to two documents: /ecc.omdoc and /omstd/arithmetics1.omdoc. For the former one XQUpdate will contain two replacement statements, for the latter one - only one replacement statement. Then the technique described in Section Write Access to TNTBase is applied.