This paper presents the implementation of an extension of the XQuery Full-Text language on top of the BaseX query engine. The proposed extension adds to the language two new exible axes that allow users to express structural constraints that are evaluated in an approximate way with respect to a considered path; the constraints evaluation produces a scored set of elements. The implementation and the e ciency evaluations of the constraints are reported in this paper.
For each element matched by the Below and Near, a score is computed by the approximate matching; the score is in the interval ]0; 1] where 1 represents a full satisfaction of the constraint evaluation, while values less than 1 are assigned to target nodes far from the context node.
The constraint Below is de ned as an XPath axis (like, for example, the children, self, etc axes) the evaluation of which is aimed at identifying elements that are direct descendants of a node. The Below constraint is speci ed as: c/below::t, where c is the context node, and t is the target node. The score computed by the Below axis evaluation, is computed by the formula: wbelow(c; t) = jdesc a1rcs(c;t)j . Where desc arcs(c; t) is a function that returns the set of unique descending arcs from c to t.
The constraint Near is speci ed as a exible axis of a path expression; it allows to identify XML elements connected through any path to the context node. The axis allows to de ne a maximum distance n that acts as a threshold on the number of arcs between the context node and the target node; nodes the distance of which is more then n arcs are ltered out from the possible results. The Near syntax is: c/near(n)::t and the score for its evaluation is computed as: wnear(c; t; n) = jarcs1(c;t)j if jarcs(c; t)j n where c is the context node, t 0 else. is the current target node, n is the maximum allowed distance and arcs(c; e) returns the set of arcs in the shortest path between c and t.
The new axes have been integrated into the BaseX XQuery engine by extending
both its language interpreter and its XQuery evaluation processor to include
a new score-structure Score Variable de nition. BaseX has been chosen for
being the rst system (and the only one, to the best of our knowledge) to
implement the full XQuery Full-Text language. As described in [
where Varname is a valid variable name; TypeDeclaration is a variable type declaration; and ExprSingle is the actual query for node selection as de ned in the XQuery language. From the user point of view this approach o ers unlimited possibilities of the usage of the new Structure Score Variable: the user can de ne aggregation functions using the default XQuery constructs.
Fig. 1a shows an example of the Near constraint application: the query person//act/near::title is evaluated and the three gray title nodes are matched with a score of 0:3, for the act/movie/title node, and 0:25 for the other two nodes. In Fig. 1b the evaluation of the query person/below::name is shown: three name nodes are retrieved; person/name node with a score of 1 and 0:3 for the other nodes.
(a) (b) The performed evaluations compare the e ciency of all the new axes constraints with the standard XPath/XQuery counterparts (if available): in particular for the Below axis evaluation we executed each query using both the Below and the descendant axes. Concerning the Near axis evaluation, instead, no counterpart could be identi ed due to the innovative nature of the proposed axis.
The axes evaluations have been performed by using the IMDB INEX DataCentric collection. Performance tests have been executed with an increasing size of the evaluated collection to verify the overhead introduced by the exible axis evaluation in comparison with standard (if applicable) XPath axes constraints. Due to the nature of the BaseX indexing system that caches queries, result set, and opened databases, the evaluations have been performed by unloading the BaseX system between each run. All evaluation tests have been executed 5 times, and the average timings (removing the worst and the best results) are presented.
Below axis evaluation: The Below axis has been compared with the standard descendant axis: both axes have been evaluated by executing the test without any query optimization introduced by BaseX. Five queries containing the Below axis have been evaluated against each collection by measuring its execution time. The same query, with the Below axis replaced by the descendant axis has then been executed and its timings compared. In Fig. 2 the evaluation results are sketched: not surprisingly the Below axis evaluation takes more time than the equivalent descendant axis to obtain the query results, due to the computation of the structural score. The Below axis evaluation takes in average 36% more time than the execution of the descendant counterpart.
Near axis evaluation: The Near axis evaluation has been performed by using the same IMDb collection used for the evaluation of the Below axis. The queries used during the evaluation process have been de ned so as to require the BaseX engine to retrieve all the XML elements without neither adopting any optimization strategy nor any query re-writing; this aspect forced the BaseX system to perform a sequential analysis of the target nodes, and thus to provide a complete execution of the Near axis evaluation. Furthermore the BaseX Full-Text index has been avoided, further enforcing the complete iteration over any target node without using any BaseX pre-pruning strategy. These aspects allowed to measure the e ciency of the Near axis evaluation implementation.
The Below and Near axes, semantically and syntactically de ned in [