{'fraction_non_alphanumeric': 0.03329571106094808, 'fraction_numerical': 0.011931634956465657, 'mean_word_length': 4.513333333333334, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RadegastXDB - Prototype of Native XML Database Management System: Technical Report

A lot of advances in the processing of XML data have been proposed in last two decades. There were many approaches focused on the efficient processing of twig pattern queries (TPQ). However, including the TPQ into an XQuery compiler is not a straightforward task and current XML DBMSs process XQueries without any TPQ detection. In this paper, we demonstrate our prototype of a native XML DBMS called RadegastXDB that uses a TPQ detection to accelerate structural XQueries. Such a detection allows us to utilize state-of-the-art TPQ processing algorithms. Our experiments show that, for the structural queries, these algorithms and state-of-the-art XML indexing techniques make our prototype faster than all of the current XML DBMSs, especially for large data collections. We also show that using the same techniques is also efficient for the processing of queries with value predicates.


Introduction
A lot of advances in the processing of XML data have been proposed in last two decades. Especially in 2000 -2010, there were many approaches focused on an efficient processing of XQueries modeled by twig pat-tern queries (TPQ) (e.g., [19,2,6,16,7,15,14,17]). In general, there are two major groups of TPQ processing algorithms: binary structural joins [2,1,16,10] and holistic twig joins [6,7,14,4], where the latter group is considered as the state-of-the-art. However, the most of the current XML database management systems (DBMSs) do not utilize holistic twig joins, since these DBMSs are not capable to detect TPQs in XQueries. Instead, they rely on rather naive techniques such as nested loops or the traditional relational merge join algorithms. In other words, they ignore the most of the advances in the XML query processing introduced in last two decades and, therefore, they perform poorly even on simple structural queries on large data collections.
A TPQ is a rooted labeled tree, where each node corresponds to one location step in an XQuery. A sample TPQ is illustrated in Figure 1b and it corresponds to the XQuery in Figure 1a. The single and double lined edges represent the parent-child (PC) and ancestor-descendant (AD) structural relationships corresponding to the child and descendant axes, respectively 1 . We call query nodes the nodes in a TPQ and we denote them by the '#' character.
Additionally, the circled query nodes represent output query nodes (also called extraction points [12]) which correspond to the last location steps in the 'for' clauses. In a nutshell, the processing of a TPQ means to find all mappings from the TPQ to an XML document such that the query nodes are mapped to XML nodes of the corresponding name and these XML nodes satisfy the relationships specified by the query edges. For more details about the processing of a TPQ, we refer to [3]. In this paper, we demonstrate our prototype of a native XML DBMS called RadegastXDB. The prototype mainly focuses on an efficient processing of structural XQueries which is primarily possible due to the proper detection of TPQs. Such a detection allows us to utilize state-of-the-art query processing algorithms. Our experiments show that, for the structural queries, these algorithms and state-of-the-art XML indexing techniques make our prototype faster than all of the current XML DBMSs. We also show that using the same techniques is also efficient for the processing of queries with value predicates.
The rest of this paper is organized as follows. In Section 2, we outline the architecture of our prototype including index data structures and query processing techniques, and in Section 3, we provide an experimental comparison with the current XML DBMSs. Section 4 concludes the paper.

Architecture
The RadegastXDB native XML DBMS consists of two main subsystems: the storage and the XQuery processor. The storage is a set of indexes to store a collection of XML documents and to perform lowlevel data access operations. The XQuery processor represents the front-end of our prototype. We outline the storage and the XQuery processor in the following subsections.

Storage
The storage consists of three indexes, namely: the document index, the partition index, and the value index. Let us note that similar indexes are described in [18].
The document index (see Figure 2) represents the main index that stores all data of any inserted XML document. It maps node labels to the corresponding XML nodes. The node labels have two purposes: (1) to identify XML nodes uniquely and (2) to resolve structural relationships in a constant time 2 . The document index consists of a B + -tree and a paged array, where a node label is the key of the B + -tree. Each leaf entry of the B + -tree also includes an XML node name, a type of the XML node (element, attribute, text, etc.), and a pointer to the paged array where values of attributes and text nodes are stored. We can either perform a point query on the B + -tree to retrieve data of a specific XML node or a range query to retrieve data of all descendants of an XML node. B + -tree node label node label node name node type node label node name node type · · · text value text value · · · The partition index (see Figure 3) is also a combination of a B + -tree and a paged array, but an XML node name is the key of the B + -tree and each leaf entry of the B + -tree points to a distinct paged array of node labels of the specific name. In such a way, the partition index can retrieve a list of node labels cor-responding to a specific name which mainly supports the processing of structural XQueries. B + -tree node name node label node label · · · . . . node label node label · · ·

Figure 3: Partition index
Finally, the value index has a similar structure as the partition index, but the key of the B + -tree is composed of an XML node name and value. Therefore, it supports the processing of XQueries with value predicates including both equality and inequality comparisons.

XQuery Processor
The XQuery processor is based on the Galax XQuery algebra [15]. The prototype currently does not support the whole XQuery, since we mainly focus on the processing of structural queries. These queries can be modeled using TPQs which we detect using the rewriting rules similarly as in [13]. However, our experiments show that, using the value index, we can also efficiently process queries with value predicates.
In our prototype, we have implemented three approaches to process a TPQ: a holistic join GTPStack [4], a cost-based holistic join CostTwigJoin [5], and fully-pipelined query plans of binary structural joins (FP-BJ) [11]. All of the three approaches require the detection of a TPQ. GTPStack represents a state-ofthe-art holistic join and it utilizes the partition index or the value index to retrieve lists of XML nodes specified by query nodes or value predicates, respectively, CostTwigJoin extends GTPStack to combine the partition and document index, which is efficient especially for highly selective queries. The FP-BJ approach improves the binary join query processing; it uses the partition index and the value index and it is especially advantageous for XQueries with a low number of output query nodes.

Experiments
We picked 5 native XML DBMSs with the highest ranking according to http://db-engines.com (September 2018). We added MonetDB, which we consider as one of the most efficient native XML DBMSs despite the fact that it is no longer supported. We also included two relational DBMSs supporting XML querying. All of these XML DBMSs are summarized in Table 1. The table also includes abbreviations we use in the following text. For the license purposes, we cannot provide the names of the both relational DBMSs (CR1, CR2) and one of the XML DBMSs (CX). We employed five XML data collections used by many approaches [13,8,9,4]. XMark is a well-known XML benchmarking synthetic collection whose size can be controlled using a factor f . We worked with two factors f = 1 and f = 10. Swis-sProt is a real database of protein sequences, Tree-Bank contains partially encrypted English sentences and DBLP is a real bibliographical database. These collections and their statistics are summarized in Table 2. Unfortunately, the DBMSs CX and E-DB were not able to store any of the tested XML collections. Therefore, these two DBMSs were omitted from the following experiments. For the other DBMSs, we created structural and value indexes, if it was possible. We used the Intel Xeon E5-2690@2.9GHz processor, 384 GB RAM, and the Microsoft Windows Server 2016 Datacenter operating system as the testbed.   Table 2: Statistics of data collections pendix B, respectively. We measured the query processing time without the result materialization (i.e., without retrieving the whole subtrees of data nodes searched by the queries). Therefore, we wrapped the queries with the XQuery function count(). The queries were run 5 times on each database; we considered the arithmetic means of the processing times without the best and the worst run. The processing times for all the queries, collections and DBMSs can be found in Table 3. The best processing times are in bold. Let us first focus on the structural queries whose results are summarized in Figure 4. The FP-BJ, CTJ (CostTwigJoin), and GTP (GTPStack ) represent the approaches implemented in our prototype. We omitted the relational databases CR1 and CR2 in the figure, since the most of the queries did not finished until 5 minutes. For the same reason, we also omitted the results of BX for the TreeBank collection.
We can observe, that our FB-BJ approach gives the best overall performance on all collections. It processed 23 (out of 25) queries with the best processing time compared to the other DBMSs in Table 1, and 17 queries with the best time (including CTJ and GTP in the comparison). FP-BJ performed  Table 1 which was usually M-DB. 7 queries were processed most efficiently by CTJ and 1 query by M-DB.  For queries with value predicates, we omitted the TreeBank collection because of its encrypted content for which it is not reasonable to perform such queries. We also do not include results of CTJ, since it requires statistics of distribution of values which are currently not supported in our prototype. Summarized results for queries with value predicates are in Figure 5.
Similarly as in the previous experiment, we can see that FP-BJ gives the best overall performance on all collections. It processed 18 (out of 20) queries with the best processing time compared to the other DBMSs in Table 1, and 15 queries with the best time (including GTP in the comparison). FP-BJ performed from 2.60× to 130.43× better than the best of the other DBMSs in Table 1. 2 queries were processed most efficiently by BX, but M-DB gave the best overall performance out of the other tested DBMSs again.
Finally, we tried to find out whether the other DBMSs utilize any detection of a TPQ. We measured query processing times of two semantically equivalent queries (these two times should be nearly the same, if the same TPQ is detected) and we examined plans of these queries. We realized that any of the DBMSs in Table 1 do not utilize any detection of a TPQ.

Conclusions
Our experiments clearly show that our prototype, RadegastXDB, performs better compared to the current XML DBMSs for both structural queries and queries with value predicates. This is caused by utilizing state-of-the-art XML indexing techniques and TPQ processing algorithms. The experiments also show that the current XML DBMSs ignore the most of the advances in the XML query processing introduced during the past years. For example, holistic twig joins have been introduced in 2002 [6], and since then, they have been considered as a state-of-the-art XML query processing technique. Now, in 2019, they are still not integrated in any of the current XML DBMSs. Although, there is still a plenty of future work on our prototype including, e.g., the complete support of XQuery or the transactional processing, we believe that it already gives valuable results. [8] Z. Chen, H. Jagadish, L. V. Lakshmanan, and S. Paparizos. From tree patterns to generalized tree patterns: On efficient evaluation of xquery.
In Proceedings of the 29th international conference on Very large data bases-Volume 29, pages 237-248. VLDB Endowment, 2003.