Balisage Paper: XSAQCT: XML Queryable Compressor

3.1. Basic Terminology

XSAQCT can be characterized as (1) a database application, that concentrates on queryable compression with random access, and decompression speed; (2) an interactive compressor that can expect any kind of queries (rather than a batch compressor that know a priori the so-called workloads (containing queries that can be used); (3) a compressor that supports both lossless compression (the only differences between the recreated document and the input document are those permitted by the XML canonicalization process, such as the order of occurrence of attributes; see [can]), and compression, which also allows removal of spurious whitespace; and (4) uses indexing and caching. To our knowledge, currently there is no compressor available with all four attributes.

Two absolute paths are called similar if they are identical, possibly with the exception of the last component, which is the data value. For example, the paths /a/b/t1 and /a/b/t2 are similar while the paths /a/b/t1 and /a/c/t1 are not.

3.2. Architecture of XSAQCT

The top-level description of the architecture of the XSAQCT compressor is as follows. First, the input file is compressed. Then the user can start a session, during which the compressed file is queried and/or decompressed to recreate the original file. More details of the architecture are provided in Figure 1, in which shaded boxes represent intermediate stages of the compression.

fig_process

The architecture of XSAQCT.

Given a document D, we perform a single SAX traversal of D to encode it; creating an annotated tree (T_A,D). At the same time, data values are written to the appropriate data containers. Note that T_A,D provides a faithful but succinct representation of the structure of the input document D. Next, T_A,D is compressed by first writing its annotations to one container and the skeleton tree (T_D) without annotations to another container. Finally, all remaining containers are compressed, using user specified back-end compressors, and written to create the compressor’s output C_D.

This approach resembles a permutation-based approach, in which a document is re-arranged to localize repetitions. However, in our work, T_A,D preserves all information about the ordering of elements, and a single container stores only related data values (specifically, we use a single container to store text values for all similar paths). Each container may be compressed using different back-end compressor, depending on the type of value in the container (the encoded information about the selected back-end compressor is added to the container). In other words, our approach is in a sense a homomorphic approach, but the annotated tree never has two or more similar paths (they have been “merged” into a single path). The main back-end compressors used include GZIP [gzip], BZIP2 [bzip2] and PAQ8 [paq], but the user can add more compressors.

The decompressor has the following logical passes (more details of the actual implementation are provided in Section 4.2):

Example 1. Consider the document D, shown as the document tree without any data values, in Figure 2. Here, there are three similar paths /a/b/c and two similar paths /a/b/e.  Note that in this example, we concentrate on handling elements and describe handing attributes and text values in Section 3.3.

fig2

The document D.

The annotated tree T_A,D, which represents D, is shown in Figure 3. Similar paths have been merged, for this example there is only one path /a/b/c and one path /a/b/e. To support decompression, annotations have been added to the nodes of the tree T_A,D.

fig_annotated_tree

The annotated tree T_A,D.

Let’s use this example to explain the idea behind annotations. In this example, as well in most examples we investigated, the document tree is wide, while the corresponding annotated tree is much narrower (both trees always have the same height). The annotation associated with node n, which is a child of the node m, provides the information as to the number of children of m, labeled by n. Specifically, in this example, the node “b” in T_A,D is annotated with [3], because there are three children labeled by “b” of the node “a” in the document D. Now, consider the node “e” in T_A,D. This node is annotated with [0,0,2], because in the document D, there are no children labeled “e” for the first two occurrences of the node “b”, and there are two children labeled “e” for the third occurrence of the node “b”.

Now, we summarize some properties of the annotated tree T_A,D for the document D. First of all, the height of D is equal to the height of T_A,D.  For a node A of T_A,D, consider its annotation ann(A) = [a1,…,ak] and let |ann(A)| be the number of integers in the ann(A), {A} be the sum of a₁,…,a_k. Then, the following properties hold:

3.1 In D, there are a₁,…,a_k occurrences of A

3.2 If A has children B₁,…,B_m in T_A,D, then

For Example 1, and the node “b” in T_A,D, we have ann(b) = [3] and from 3.1, there are three occurrences of the node “b” in D. From 3.2 a), annotations of children of this node have three integers. To show an example of 3.2b), consider Figure 11 and the node ”$”, which is a child of the node “a”, and has two children; “s”, annotated by [1,2,0,1,0] and “z”, annotated by [0,1,1,0,0]. As the Figure 12 shows, there are five corresponding occurrences of the node “$” in D; with the following children:

For any element s, which may appear a various number of times as a child of the same node, in our figures, the element s will have an appended *. Element s is called dirty if it has an appended *; otherwise it is called clean. The only clean element in Figure 2 is the one labeled with “c”.  Since clean nodes always appear exactly once, they are not actually being annotated. However, for the sake of clarity in Figure 3, we showed all annotations.

The next section describes handing of attributes and mixed content.

3.3. Attributes and Mixed Content

Attributes are treated as if they were elements, i.e. their names (preceded by “@”), and annotations are recorded in T_A,D. Figure 4 shows a simple document with various text nodes, including mixed content. The tree T_A,D is shown in Figure 5, and text containers (the bottom of the figure). Nodes of the tree are marked with a asterisk in Figure 5, if the corresponding element has mixed content, and in such a case empty text (shown as a box containing “0”) is inserted in the text container when needed. All annotations appear in a separate container, with the pointer from each node pointing to the beginning of its annotations (the length of the annotation can be computed using the property 3.2 from Section 3.2). Note that the Figure 5 shows the logical format for the annotated tree T_A,D,  more details of the actual implementation are provided in Section 4.

fig_4

Handling mixed content.

fig_5

Tree T_A,D and text containers.

3.4. Querying

At the time of writing this paper, our query processor was under development, and only simple queries have been implemented (specifically, we have implemented absolute paths; similarly to TREECHOP [tre05], but additionally including some predicates such as “position()=2”). A query, which ends in an element, can be immediately answered using the annotated tree, and therefore it only requires a decompression of this tree. Now, consider a query, which calls for text values for a given path. As mentioned earlier, the compressor creates a separate container storing all values for similar paths (comp. Figure 4 and Figure 5). Therefore, to answer this type of a query it is enough to decompress a single data container, and then return the text values stored in this container. Since text values are stored within a container in a dfs-order, a query that calls for a specific text value (such as the i-th value) can be answered by traversing a single decompressed container to locate the i-th value.

Example 2. Consider the document D shown in Figure 4 and Figure 5. Now, consider the following queries:

4.1. Building an Annotated Tree

We will say that a document D has a cycle if there exists a node n in D such that there are two children x and y of n, which satisfy this condition: x < y and y < x (here, “<” denotes the document order). If there are cycles, then add a “dummy tag name” to the annotated tree T_A,D, here denoted by $, which will be used to avoid cycles. The annotated tree T_A,D may have dummy nodes, and if so they will be removed by the decompressor to recreate the original document.

Cycles may occur in the following two cases:

During parsing, it is unclear whether the Skeleton Tree should place the corresponding element of node a before or after node b. Either choice would cause the compressed file to be incorrect, because either all a's would appear before all b's or all b's would appear before all a's. Therefore, our algorithm creates multiple graphs, which are later topologically sorted. A topological sort can also be used to detect cycles in a graph. Here, the vertices of the graph are the child elements of some parent element in T_A and the edges between these child elements are created during parsing. If the topological sort reveals a cycle in this graph then this situation can be handled by adding a dummy node to the parent element.

Example 3. Document D (which has cycles on x and y) is shown in Figure 6.

fig_6

Sample document D.

The annotated document tree (with dummy nodes) is shown in Figure 7.

fig_7

The annotated document tree.

The restored document tree (with dummy nodes) is shown in Figure 8.

fig_8

Restored document tree of D (with dummy nodes).

Algorithm 4.1

Input: An XML document D.

Output: An annotated document tree T_A,D.

To describe details of the process of building the annotated document tree, we use the following notations:

Method: Elements are added to the annotated tree when they are encountered for the first time. We use a single SAX [SAX] traversal of the document D and perform the following actions:

Example 4. Consider a document D shown in Figure 9. Here, we use indices for explanations, e.g. a1 is just a.

fig_9

Sample document D.

Table 1 shows all major steps in creating the annotated document tree for the document D from Figure 8; for each step there is a description (if required) specifying which node of the document is encountered during the SAX traversal, wherever there is a change then a path and its graph (the graph is not shown if it is empty), and the annotation of $ if it exists. The current node is shown in bold. Entries for leaves (where graphs are empty) are omitted. When appropriate, we show below the path and the graph; e.g. (/r   a[1]) indicates the graph consisting of a single node a, annotated by 1, for the path “/r”). Only the paths/graphs that have changed from the previous step are shown. Sometimes “empty graphs” are omitted.

Note: we will add leading 0’s and 1’s when creating the annotated document tree in order to make sure that the number of positions in the annotations is correct. The annotated document tree created from the above table is shown in Figure 10.

fig_10

The incomplete annotated document tree.

The annotated document tree in which leading 0’s are added to node annotations and leading 1’s are added to $’s annotations is shown in Figure 11.

fig_11

The complete annotated document tree.

The restored document tree obtained from the complete annotated tree, in which dummy nodes are not removed, is shown in Figure 12.

fig_12

The restored document tree (dummy nodes are not removed).

It is easy to see that removing dummy nodes from the tree shown in Figure 12 will produce the original document tree shown in Figure 9.

4.2 Decompression

The skeleton tree T_D is first re-annotated to create the annotated tree T_A,D, and then T_A,D is used to output the restored document. Reannotator performs a dfs-traversal of T_D and fetches annotations from their respective container (see Figure 4), using the property 3.2 from Section 3.2. Details of the reannotator follow.

re-ann(SkeletonTreeNode current) 
{
	for every child c of current 
	{
		if(clean(c)) 
			annotate c with “number” of 1’s
		else 
		{ // dirty c
			fetch “number” digits from Seq and store into the sequence “els”
			annotate c with “els”
			number = sum of all digits in “els”
		}
   		re-ann(c)
   	}
 	number = sum of all digits in the annotation of n
}

re-ann(root of SkeletonTreeNode)
output <tag of the root>
d-dfs(root of SkeletonTreeNode)
output <\end of tag for the root>

d-dfs(SkeletonTreeNode c) 
{
	Node n
	n= LC(c)
	while(n <> 0) 
	{
 		if(ann(n)>0) 
		{
			output “<” + tag_of_n + “>”
			d-dfs(c)
		} 
		else chop(n)
		n = RS(n)
	}
	dec(c)
	output “<\” + tag_of_c + “>”
	if(ann(c)==0) chop(c)
	else {
		output “<” + tag_of_c + “>”
		d-dfs(c)
	}
}